階数因数分解のソースを表示

'''階数因数分解'''（かいすういんすうぶんかい、{{Lang-en-short|rank factorization}}）あるいは'''階数分解'''（rank decomposition）とは、[[数学]]の[[線型代数学]]の分野において、[[行列の階数|階数]]が <math>r</math> のある与えられた <math>m \times n</math> [[行列]] <math>A</math> のある <math>m \times r</math> 行列 <math>C</math> と <math>r \times n</math> 行列 <math>F</math> の積としての表示 <math>A=CF</math> のことを言う。

'''全ての有限次元行列には階数因数分解が存在する'''：<math>A</math> を、[[行列の階数|列階数]]が <math>r</math> であるような <math>m\times n</math> 行列とする。すなわち、<math>A</math> には <math>r</math> 個の[[線型独立]]な列が含まれる。あるいは同じ意味であるが、<math>A</math> の[[列空間]]の[[次元 (数学)|次元]]は <math>r</math> である。<math>c_1,c_2,\ldots,c_r</math> を、<math>A</math> の列空間の任意の[[基底 (線型代数学)|基底]]とし、それらを列ベクトルとして <math>m\times r</math> 行列 <math>C = [c_1:c_2:\ldots:c_r]</math> を構成する。したがって、<math>A</math> の全ての列ベクトルは、<math>C</math> の列の[[線型結合]]である。正確に言うと、<math>A = [a_1:a_2:\ldots:a_n]</math> を第 <math>j</math> 列が <math>a_j</math> であるような <math>m\times n</math> 行列とすれば、
:<math>a_j = f_{1j}c_1 + f_{2j}c_2 + \cdots + f_{rj}c_r,</math>   
となる。ただし <math>f_{ij}</math> は、基底 <math>c_1,c_2,\ldots,c_r</math> に関する <math>a_j</math> のスカラー係数である。このことは、<math>f_{ij}</math> を <math>(i,j)</math>-成分とする行列 <math>F</math> によって <math>A = CF</math> が得られることを意味する。

== rank(A) = rank(A<sup>T</sup>) ==
階数因数分解から直ちに従う帰結として、<math>A</math> の階数はその転置行列 <math>A^\text{T}</math> の階数と等しい、というものがある。すると <math>A</math> の列は <math>A^\text{T}</math> の行であることから、<math>A</math> の[[行列の階数|列階数]]と[[行列の階数|行階数]]は等しいことが分かる。

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

== 行階段形からの階数因数分解 == 
実際、特定の階数因数分解を次の手順で構成することが出来る：<math>A</math> の[[行階段形|行既約階段形]] <math>B</math> は計算することで得られる。このとき、上述の行列 <math>C</math> は <math>A</math> から全ての非[[ガウスの消去法|ピボット]]列を除くことで得られ、<math>F</math> は <math>B</math> から全てのゼロ行を除くことで得られる。

== 例 ==
行列
:<math>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 </math>
を考える。<math>B</math> は既約階段形である。このとき、<math>C</math> は、<math>A</math> の唯一つの非ピボット列である第三列を除くことで得られ、<math>F</math> は最後のゼロ行を除くことで得られる。すなわち、
:<math>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} </math>
が得られる。次の関係式が、直ちに確かめられる：
:<math>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{.}</math>

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

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

== 参考文献 ==
{{refbegin}}
* {{Citation | last = Lay | first = David C. | date = 2005 | title = Linear Algebra and its Applications | publisher = Addison Wesley | edition = 3rd | isbn = 978-0-201-70970-4}}
* {{Citation | last = Golub | first = Gene H. | last2 = Van Loan | first2 = Charles F. | date = 1996 | title = Matrix Computations | series = Johns Hopkins Studies in Mathematical Sciences | publisher = The Johns Hopkins University Press | edition = 3rd | isbn = 978-0-8018-5414-9}}
* {{Citation | last = Stewart | first = Gilbert W. | date = 1998 | title = Matrix Algorithms. I. Basic Decompositions  | publisher = SIAM | isbn = 978-0-89871-414-2}}
{{refend}}

{{DEFAULTSORT:かいすういんすうふんかい}}
[[Category:行列]]
[[Category:行列の分解]]
[[Category:線型代数学]]
[[Category:数学に関する記事]]