LLLアルゴリズムやBabaiのアルゴリズムにグラムシュミットの直交化法が出てきます。いろんな実装方法がありますが、中国の暗号論文用に列を左から右へとって直交化するコードを用意しました。numpyを使って書いています。 <pre class="ql-syntax" spellcheck="false">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
</pre> たぶんできているはず？です。試してみます。 <pre class="ql-syntax" spellcheck="false">A = np.array([[1., 0, 0],
       [0, 1, 0],
       [0, 0, 2],
       [22, 35, 51]])

B = gram_schmidt(A)
print(B)
</pre> こちらを出力すると、 <pre class="ql-syntax" spellcheck="false">[[ 0.04540766 -0.84551594 -0.27924526]
 [ 0. 0.53256524 -0.44425382]
 [ 0. 0. 0.85117538]
 [ 0.99896854 0.03843254 0.01269297]]
</pre> となり、各列の内積を取ってみます。 <pre class="ql-syntax" spellcheck="false">B[:, 0] @ B[:, 1]
#=&gt;1.7555401576885288e-15
</pre> <pre class="ql-syntax" spellcheck="false">B[:, 0] @ B[:, 2]
#=&gt;-1.0928757898653885e-16
</pre> <pre class="ql-syntax" spellcheck="false">B[:, 1] @ B[:, 2]
#=&gt;-1.2327378701160185e-16
</pre> となっています。念のために直交化するまえのAの行列で計算してみると、 <pre class="ql-syntax" spellcheck="false">A[:, 0] @ A[:, 1]
#=&gt;770.0
</pre> となりました。勉強になりますね。。。以上です。

グラムシュミットの直交化法python

Yuichiro Minato