有名な方法であるが、メモ書き程度に残す。pythonではscipy.linalg.null_spaceで以下のアルゴリズムで計算される行列の零空間の正規直交基底ベクトルを列ベクトルとして並べた行列を得られる。
特異値分解を利用する方法
$A \in \mathbb{R}^{n \times m}$の零空間
\mathrm{Ker}(A) = \{v \in \mathbb{R}^{m}| Av= \boldsymbol{0}_n\}
の正規直交基底を具体的に計算したい。線型写像の次元定理から、
\mathrm{rank}(A) + \mathrm{dim} (\mathrm{Ker}(A)) = m
である。ここでは、$\mathrm{rank}(A) = k, \mathrm{dim} (\mathrm{Ker}(A)) = m - k$とする。
$\mathrm{rank}(A) = k$より、$A$は$0$でない特異値を$k$個持つ。それを$\sigma_1>...>\sigma_k>0$として、Aを特異値分解する。
A = U
\begin{bmatrix}
\mathrm{diag}(\sigma_1, ..., \sigma_k) & O_{k, m-k} \\
O_{n-k, k} & O_{n-k, m-k}
\end{bmatrix}
V^T
$U \in \mathbb{R}^{n \times n}, V \in \mathbb{R}^{m \times m}$は直交行列。$U = [u_1,...,u_n], V=[v_1,...,v_m]$とする。
$V^T = V^{-1}$なので、
A V = \begin{bmatrix}
U \begin{bmatrix} \mathrm{diag}(\sigma_1, ..., \sigma_k) \\ O_{n-k, k}\end{bmatrix} & U O_{n, m-k} \\
\end{bmatrix}
つまり、
\begin{bmatrix}Av_1 &...&Av_m\end{bmatrix} = \begin{bmatrix}
\sigma_1 u_1 &...&\sigma_k u_k & O_{n, m-k} \\
\end{bmatrix}
となる。
したがって、$A[v_{k+1} ... v_{m}] = O_{n, m-k}$である。
$v_{k+1} ... v_{m}$が求めるべき$A$の零空間の$m-k$本の正規直交基底である。
ちなみに、同様の理由で$u_{k+1}, ..., u_{n}$は$A^T$の零空間の正規直交基底になる。