LLLアルゴリズムやBabaiのアルゴリズムにグラムシュミットの直交化法が出てきます。
いろんな実装方法がありますが、中国の暗号論文用に列を左から右へとって直交化するコードを用意しました。
numpyを使って書いています。
import numpy as np
def gram_schmidt(v):
vs = np.copy(v)
n = len(vs[0])
u = [0] * n
for i in range(0, n):
for j in range(i):
vs[:, i] -= u[j] * (vs[:, i]@u[j]) / (u[j]@u[j])
u[i] = vs[:, i]/np.linalg.norm(vs[:, i])
return np.array(u).T
たぶんできているはず？です。試してみます。
A = np.array([[1., 0, 0],
[0, 1, 0],
[0, 0, 2],
[22, 35, 51]])
B = gram_schmidt(A)
print(B)
こちらを出力すると、
[[ 0.04540766 -0.84551594 -0.27924526]
[ 0. 0.53256524 -0.44425382]
[ 0. 0. 0.85117538]
[ 0.99896854 0.03843254 0.01269297]]
となり、各列の内積を取ってみます。
B[:, 0] @ B[:, 1]
#=>1.7555401576885288e-15
B[:, 0] @ B[:, 2]
#=>-1.0928757898653885e-16
B[:, 1] @ B[:, 2]
#=>-1.2327378701160185e-16
となっています。念のために直交化するまえのAの行列で計算してみると、
A[:, 0] @ A[:, 1]
#=>770.0
となりました。勉強になりますね。。。以上です。