階数因数分解

階数因数分解(かいすういんすうぶんかい、英: rank factorization)あるいは階数分解(rank decomposition)とは、数学の線型代数学の分野において、階数が ${\displaystyle r}${\displaystyle r} のある与えられた ${\displaystyle m\times n}${\displaystyle m\times n} 行列 ${\displaystyle A}${\displaystyle A} のある ${\displaystyle m\times r}${\displaystyle m\times r} 行列 ${\displaystyle C}${\displaystyle C} と ${\displaystyle r\times n}${\displaystyle r\times n} 行列 ${\displaystyle F}${\displaystyle F} の積としての表示 ${\displaystyle A=CF}${\displaystyle A=CF} のことを言う。

全ての有限次元行列には階数因数分解が存在する:${\displaystyle A}${\displaystyle A} を、列階数が ${\displaystyle r}${\displaystyle r} であるような ${\displaystyle m\times n}${\displaystyle m\times n} 行列とする。すなわち、${\displaystyle A}${\displaystyle A} には ${\displaystyle r}${\displaystyle r} 個の線型独立な列が含まれる。あるいは同じ意味であるが、${\displaystyle A}${\displaystyle A} の列空間の次元は ${\displaystyle r}${\displaystyle r} である。${\displaystyle c_{1},c_{2},\ldots ,c_{r}}${\displaystyle c_{1},c_{2},\ldots ,c_{r}} を、${\displaystyle A}${\displaystyle A} の列空間の任意の基底とし、それらを列ベクトルとして ${\displaystyle m\times r}${\displaystyle m\times r} 行列 ${\displaystyle C=[c_{1}:c_{2}:\ldots :c_{r}]}${\displaystyle C=[c_{1}:c_{2}:\ldots :c_{r}]} を構成する。したがって、${\displaystyle A}${\displaystyle A} の全ての列ベクトルは、${\displaystyle C}${\displaystyle C} の列の線型結合である。正確に言うと、${\displaystyle A=[a_{1}:a_{2}:\ldots :a_{n}]}${\displaystyle A=[a_{1}:a_{2}:\ldots :a_{n}]} を第 ${\displaystyle j}${\displaystyle j} 列が ${\displaystyle a_{j}}${\displaystyle a_{j}} であるような ${\displaystyle m\times n}${\displaystyle m\times n} 行列とすれば、

${\displaystyle a_{j}=f_{1j}c_{1}+f_{2j}c_{2}+\cdots +f_{rj}c_{r},}${\displaystyle a_{j}=f_{1j}c_{1}+f_{2j}c_{2}+\cdots +f_{rj}c_{r},}

となる。ただし ${\displaystyle f_{ij}}${\displaystyle f_{ij}} は、基底 ${\displaystyle c_{1},c_{2},\ldots ,c_{r}}${\displaystyle c_{1},c_{2},\ldots ,c_{r}} に関する ${\displaystyle a_{j}}${\displaystyle a_{j}} のスカラー係数である。このことは、${\displaystyle f_{ij}}${\displaystyle f_{ij}} を ${\displaystyle (i,j)}${\displaystyle (i,j)}-成分とする行列 ${\displaystyle F}${\displaystyle F} によって ${\displaystyle A=CF}${\displaystyle A=CF} が得られることを意味する。

階数因数分解から直ちに従う帰結として、${\displaystyle A}${\displaystyle A} の階数はその転置行列 ${\displaystyle A^{\text{T}}}${\displaystyle A^{\text{T}}} の階数と等しい、というものがある。すると ${\displaystyle A}${\displaystyle A} の列は ${\displaystyle A^{\text{T}}}${\displaystyle A^{\text{T}}} の行であることから、${\displaystyle A}${\displaystyle A} の列階数と行階数は等しいことが分かる。

証明:これが真であることを示すために、はじめに行列の「階数」とはその「列階数」を意味するものであると定義しておく。${\displaystyle A=CF}${\displaystyle A=CF} より、${\displaystyle A^{\text{T}}=F^{\text{T}}C^{\text{T}}}${\displaystyle A^{\text{T}}=F^{\text{T}}C^{\text{T}}} が従う。行列乗算 (英語版)の定義から、この等式は ${\displaystyle A^{\text{T}}}${\displaystyle A^{\text{T}}} の各列が ${\displaystyle F^{\text{T}}}${\displaystyle F^{\text{T}}} の列の線型結合であることを意味する。したがって、${\displaystyle A^{\text{T}}}${\displaystyle A^{\text{T}}} の列空間は ${\displaystyle F^{\text{T}}}${\displaystyle F^{\text{T}}} の列空間に含まれるものであることが分かり、したがって rank(${\displaystyle A^{\text{T}}}${\displaystyle A^{\text{T}}}) ≤ rank(${\displaystyle F^{\text{T}}}${\displaystyle F^{\text{T}}}) が成立する。今 ${\displaystyle F^{\text{T}}}${\displaystyle F^{\text{T}}} は ${\displaystyle n}${\displaystyle n}×ばつ${\displaystyle r}${\displaystyle r} 行列であるので、${\displaystyle F^{\text{T}}}${\displaystyle F^{\text{T}}} には ${\displaystyle r}${\displaystyle r} 個の列が存在し、したがって rank(${\displaystyle A^{\text{T}}}${\displaystyle A^{\text{T}}}) ≤ ${\displaystyle r}${\displaystyle r} = rank(${\displaystyle A}${\displaystyle A}) が成立する。これより rank(${\displaystyle A^{\text{T}})}${\displaystyle A^{\text{T}})} ≤ rank(${\displaystyle A}${\displaystyle A}) が示された。続いて、その逆の不等式が成立することを示すために、${\displaystyle A^{\text{T}}}${\displaystyle A^{\text{T}}} に対して上述の結果を適用する。${\displaystyle (A^{\text{T}})^{\text{T}}}${\displaystyle (A^{\text{T}})^{\text{T}}} = ${\displaystyle A}${\displaystyle A} なので、rank(${\displaystyle A}${\displaystyle A}) = rank(${\displaystyle (A^{\text{T}})^{\text{T}})}${\displaystyle (A^{\text{T}})^{\text{T}})} ≤ rank(${\displaystyle A^{\text{T}}}${\displaystyle A^{\text{T}}}) と書くことが出来る。このことから rank(${\displaystyle A)}${\displaystyle A)} ≤ rank(${\displaystyle A^{\text{T}}}${\displaystyle A^{\text{T}}}) が示される。したがって、rank(${\displaystyle A^{\text{T}})}${\displaystyle A^{\text{T}})} ≤ rank(${\displaystyle A}${\displaystyle A}) かつ rank(${\displaystyle A}${\displaystyle A}) ≤ rank(${\displaystyle A^{\text{T}}}${\displaystyle A^{\text{T}}}) であることから、rank(${\displaystyle A}${\displaystyle A}) = rank(${\displaystyle A^{\text{T}}}${\displaystyle A^{\text{T}}}) が示された。

実際、特定の階数因数分解を次の手順で構成することが出来る:${\displaystyle A}${\displaystyle A} の行既約階段形 ${\displaystyle B}${\displaystyle B} は計算することで得られる。このとき、上述の行列 ${\displaystyle C}${\displaystyle C} は ${\displaystyle A}${\displaystyle A} から全ての非ピボット列を除くことで得られ、${\displaystyle F}${\displaystyle F} は ${\displaystyle B}${\displaystyle B} から全てのゼロ行を除くことで得られる。

行列

${\displaystyle A={\begin{bmatrix}1&3&1&4\2円&7&3&9\1円&5&3&1\1円&2&0&8\end{bmatrix}}\sim {\begin{bmatrix}1&0&-2&0\0円&1&1&0\0円&0&0&1\0円&0&0&0\end{bmatrix}}=B}${\displaystyle A={\begin{bmatrix}1&3&1&4\2円&7&3&9\1円&5&3&1\1円&2&0&8\end{bmatrix}}\sim {\begin{bmatrix}1&0&-2&0\0円&1&1&0\0円&0&0&1\0円&0&0&0\end{bmatrix}}=B}

を考える。${\displaystyle B}${\displaystyle B} は既約階段形である。このとき、${\displaystyle C}${\displaystyle C} は、${\displaystyle A}${\displaystyle A} の唯一つの非ピボット列である第三列を除くことで得られ、${\displaystyle F}${\displaystyle F} は最後のゼロ行を除くことで得られる。すなわち、

${\displaystyle C={\begin{bmatrix}1&3&4\2円&7&9\1円&5&1\1円&2&8\end{bmatrix}}{\text{,}}\qquad F={\begin{bmatrix}1&0&-2&0\0円&1&1&0\0円&0&0&1\end{bmatrix}}}${\displaystyle C={\begin{bmatrix}1&3&4\2円&7&9\1円&5&1\1円&2&8\end{bmatrix}}{\text{,}}\qquad F={\begin{bmatrix}1&0&-2&0\0円&1&1&0\0円&0&0&1\end{bmatrix}}}

が得られる。次の関係式が、直ちに確かめられる:

${\displaystyle A={\begin{bmatrix}1&3&1&4\2円&7&3&9\1円&5&3&1\1円&2&0&8\end{bmatrix}}={\begin{bmatrix}1&3&4\2円&7&9\1円&5&1\1円&2&8\end{bmatrix}}{\begin{bmatrix}1&0&-2&0\0円&1&1&0\0円&0&0&1\end{bmatrix}}=CF{\text{.}}}${\displaystyle A={\begin{bmatrix}1&3&1&4\2円&7&3&9\1円&5&3&1\1円&2&0&8\end{bmatrix}}={\begin{bmatrix}1&3&4\2円&7&9\1円&5&1\1円&2&8\end{bmatrix}}{\begin{bmatrix}1&0&-2&0\0円&1&1&0\0円&0&0&1\end{bmatrix}}=CF{\text{.}}}

${\displaystyle P}${\displaystyle P} を、ブロック区分けの形式で ${\displaystyle AP=(C,D)}${\displaystyle AP=(C,D)} が成立するような ${\displaystyle n\times n}${\displaystyle n\times n} 置換行列とする。ただし ${\displaystyle C}${\displaystyle C} はその列が ${\displaystyle A}${\displaystyle A} の ${\displaystyle r}${\displaystyle r} 個のピボット列であるものとする。${\displaystyle D}${\displaystyle D} の全ての列は ${\displaystyle C}${\displaystyle C} の列の線形結合であり、したがって ${\displaystyle D=CG}${\displaystyle D=CG} が成立するような行列 ${\displaystyle G}${\displaystyle G} が存在する。ただし ${\displaystyle G}${\displaystyle G} の列は、それら各線形結合の係数を含むものである。すると、${\displaystyle r\times r}${\displaystyle r\times r} 単位行列 ${\displaystyle I_{r}}${\displaystyle I_{r}} によって ${\displaystyle AP=(C,CG)=C(I_{r},G)}${\displaystyle AP=(C,CG)=C(I_{r},G)} と書くことが出来る。続いて、${\displaystyle (I_{r},G)=FP}${\displaystyle (I_{r},G)=FP} を証明する。

${\displaystyle AP}${\displaystyle AP} を、基本行列の積であるような行列 ${\displaystyle E}${\displaystyle E} を左から掛けることによって、行既約階段形へと変換する。すなわち、${\displaystyle EAP=BP=EC(I_{r},G)}${\displaystyle EAP=BP=EC(I_{r},G)} が得られる。ただし ${\displaystyle EC={\begin{bmatrix}I_{r}\0円\end{bmatrix}}}${\displaystyle EC={\begin{bmatrix}I_{r}\0円\end{bmatrix}}} である。すると、${\displaystyle BP={\begin{bmatrix}I_{r}&G\0円&0\end{bmatrix}}}${\displaystyle BP={\begin{bmatrix}I_{r}&G\0円&0\end{bmatrix}}} と書くことが出来、したがって ${\displaystyle (I_{r},G)=FP}${\displaystyle (I_{r},G)=FP} ということが分かる。これはすなわち、${\displaystyle A}${\displaystyle A} に対して行ったものと同様の置換を列に対して行うことで得られる、行既約階段形に含まれる非ゼロの ${\displaystyle r}${\displaystyle r} 個の行である。したがって、${\displaystyle AP=CFP}${\displaystyle AP=CFP} が得られ、${\displaystyle P}${\displaystyle P} が可逆であることから ${\displaystyle A=CF}${\displaystyle A=CF} が得られる。以上で証明は完成された。

• 行列
• 行列の分解
• 線型代数学
• 数学に関する記事