Rangfaktorisering

I matematik , givet ett fält $\mathbb {F}$ , icke-negativa heltal $m,n$ , och en matris $A\in \mathbb {F} ^{m\times n}$ , en ranguppdelning eller rangfaktorisering av A är en faktorisering av A av formen A = CF , där $C\in \mathbb {F} ^{m \times r}$ och $F\in \mathbb {F} ^{r\times n}$ , där $r=\operatörsnamn {rank} A$ är rangen för $A$ .

Existens

Varje finitdimensionell matris har en ranguppdelning: Låt ${\textstyle A}$ vara en ${\textstyle m\times n}$ matris vars kolumnrankning är ${\textstyle r}$ . Därför finns det ${\textstyle r}$ linjärt oberoende kolumner i ${\textstyle A}$ ; på motsvarande sätt är dimensionen på kolumnutrymmet för ${\textstyle A}$${\textstyle r}$ . Låt ${\textstyle \mathbf {c} _{1},\mathbf {c} _{2},\ldots ,\mathbf {c} _{r}}$ vara vilken grund som helst för kolumnutrymmet för ${\textstyle A}$ och placera dem som kolumnvektorer för att bilda ${\textstyle m\times r}$ matrisen ${\textstyle C={\ börja{bmatrix}\mathbf {c} _{1}&\mathbf {c} _{2}&\cdots &\mathbf {c} _{r}\end{bmatrix}}}$ . Därför är varje kolumnvektor av ${\textstyle A}$ en linjär kombination av kolumnerna i ${\textstyle C}$ . För att vara exakt, om ${\textstyle A={\begin{bmatrix}\mathbf {a} _{1}&\mathbf {a} _{2}&\cdots & \mathbf {a} _{n}\end{bmatrix}}}$ är en ${\textstyle m\times n}$ matris med ${\textstyle \mathbf {a} _{j}}$ som ${ \textstyle j}$ -th kolumnen, alltså

$\mathbf {a} _{j}=f_{1j}\mathbf {c} _{1}+ f_{2j}\mathbf {c} _{2}+\cdots +f_{rj}\mathbf {c} _{r},$

där ${\textstyle f_{ij}}$ är skalärkoefficienterna för ${\textstyle \mathbf {a} _{j}}$ i termer av basen ${ \textstyle \mathbf {c} _{1},\mathbf {c} _{2},\ldots ,\mathbf {c} _{r}}$ . Detta innebär att ${\textstyle A=CF}$ , där ${\textstyle f_{ij}}$ är ${\textstyle (i,j)}$ -te elementet i ${\ textstil F}$ .

Icke-unikhet

Om ${\textstyle A=C_{1}F_{1}}$ en rangfaktorisering, tar ${\textstyle C_{2}=C_{1}R}$ och ${\textstyle F_{2}=R^{-1}F_{1}}$ ger en annan rangfaktorisering för varje inverterbar matris ${\textstyle R}$ med kompatibla dimensioner.

Omvänt, om ${\textstyle A=F_{1}G_{1}=F_{2}G_{2}}$ är två rangfaktoriseringar av ${\textstyle A}$ , då det finns en inverterbar matris ${\textstyle R}$ så att ${\textstyle F_{1}=F_{2}R}$ och ${\textstyle G_{1}= R^{-1}G_{2}}$ .

Konstruktion

Rangfaktorisering från reducerade radnivåformer

I praktiken kan vi konstruera en specifik rangfaktorisering enligt följande: vi kan beräkna ${\textstyle B}$ , den reducerade radechelonformen av ${\textstyle A}$ . Sedan erhålls ${\textstyle C} genom att ta bort från$${\textstyle A}$ alla icke- pivotkolumner (vilket kan bestämmas genom att leta efter kolumner i ${\textstyle B}$ som inte innehåller en pivot), och ${ \textstyle F}$ erhålls genom att eliminera alla rader med helt noll av ${\textstyle B}$ .

Obs: För en kvadratisk matris med full rang (dvs. när ${\textstil n=m=r}$ ), kommer denna procedur att ge det triviala resultatet ${\textstil C=A}$ och ${\textstyle F=B=I_{n}}$ (den ${\textstyle n\times n}$ identitetsmatrisen ).

Exempel

Tänk på matrisen

$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\\&end bmatrix}}=B{\text{.}}$

${\textstyle B}$ är i reducerad echelonform.

Sedan erhålls ${\textstyle C} genom att ta bort den tredje kolumnen i$${\textstyle A}$ , den enda som inte är en pivotkolumn, och ${\textstyle F}$ genom att ta bort den sista raden med nollor från ${\textstyle B}$ , alltså

$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}}{\text{.}}$

Det är enkelt att kontrollera det

$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{.}}$

Bevis

Låt ${\textstyle P}$ vara en ${\textstyle n\times n}$ permutationsmatris så att ${\textstyle AP=(C,D)}$ i blockpartitionerad form, där kolumner i ${\textstyle C}$ är ${\textstyle r}$ pivotkolumnerna i ${\textstyle A}$ . Varje kolumn i ${\textstyle D}$ är en linjär kombination av kolumnerna i ${\textstyle C}$ , så det finns en matris ${\textstyle G}$ så att ${\textstyle D=CG}$ , där kolumnerna i ${\textstyle G}$ innehåller koefficienterna för var och en av dessa linjära kombinationer. Så ${\textstyle AP=(C,CG)=C(I_{r},G)}$ , ${\textstyle I_{r}}$ är ${\textstyle r\times r}$ identitetsmatrisen. Vi kommer nu att visa att ${\textstyle (I_{r},G)=FP}$ .

Att transformera ${\textstyle A}$ till dess reducerade rad echelonform ${\textstyle B}$ motsvarar vänstermultiplicering med en matris ${\textstyle E}$ som är en produkt av elementära matriser , så ${\textstyle EAP=BP=EC(I_{r},G)}$ , där ${\textstyle EC={\begin{pmatrix}I_{r}\\ 0\end{pmatrix}}}$ . Vi kan sedan skriva ${\textstyle BP={\begin{pmatrix}I_{r}&G\\0&0\end{pmatrix}}} ,$ vilket gör att vi kan identifiera ${\textstyle (I_{r},G)=FP} ,$ dvs raderna som inte är noll ${\textstyle r}$ i den reducerade echelonformen, med samma permutation på kolumnerna som vi gjorde för ${\textstyle A }$ . Vi har alltså ${\textstyle AP=CFP}$ , och eftersom ${\textstyle P}$ är invertibel innebär detta ${\textstyle A=CF}$ , och beviset är komplett.

Singulärvärdesfaktorisering

Om $\mathbb {F} \in \{\mathbb {R} ,\mathbb {C} \},$ så kan man också konstruera en fullrangsfaktorisering av ${\ textstil A}$ via en singular värdenedbrytning

$A=U\Sigma V^{*}={\begin{bmatrix}U_{1}&U_{2}\end{bmatrix}}{\begin{bmatrix}\Sigma _{r}&0\\0&0 \end{bmatrix}}{\begin{bmatrix}V_{1}^{*}\\V_{2}^{*}\end{bmatrix}}=U_{1}\left(\Sigma _{r} V_{1}^{*}\höger).$

Eftersom ${\textstyle U_{1}}$ är en matris med full kolumn och ${\textstyle \Sigma _{r}V_{1}^{*}}$ är en full rad-rankning matris kan vi ta ${\textstyle C=U_{1}}$ och ${\textstyle F=\Sigma _{r}V_{1}^{*}}$ .

Konsekvenser

rang(A) = rang( ^AT )

Se även: Bevisar att kolumnrankning = radrankning

En omedelbar konsekvens av rangfaktorisering är att rangordningen för ${\textstyle A}$ är lika med rangordningen för dess transponering ${\textstyle A^{\textsf {T}}}$ . Eftersom kolumnerna i ${\textstyle A}$ är raderna i ${\textstyle A^{\textsf {T}}}, är$ kolumnrankningen för $\textstyle A}$ { lika med dess radrankning .

Bevis: För att se varför detta är sant, låt oss först definiera rang som kolumnrankning. Eftersom ${\textstyle A=CF}$ , följer det att ${\textstyle A^{\textsf {T}}=F^{\textsf {T}}C^{\textsf {T}}}$ . Från definitionen av matrismultiplikation betyder detta att varje kolumn i ${\textstyle A^{\textsf {T}}}$ är en linjär kombination av kolumnerna i ${\textstyle F^{\textsf {T}} }$ . Därför finns kolumnutrymmet för ${\textstyle A^{\textsf {T}}}$ i kolumnutrymmet för ${\textstyle F^{\textsf {T}}}$ och, följaktligen, ${\textstyle \operatörsnamn {rank} \left(A^{\textsf {T}}\right)\leq \operatörsnamn {rank} \left(F^{\textsf {T }}\right)}$ .

Nu är ${\textstyle F^{\textsf {T}}}$${\textstyle n\times r}$ , så det finns ${\textstyle r}$ kolumner i ${\textstyle F^{\ textsf {T}}}$ och följaktligen ${\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq r =\operatörsnamn {rank} \left(A\right)}$ . Detta bevisar att ${\textstil \operatörsnamn {rank} \left(A^{\textsf {T}}\right)\leq \operatörsnamn {rank} \left(A\ höger)}$ .

Tillämpa nu resultatet på ${\textstyle A^{\textsf {T}}}$ för att erhålla den omvända olikheten: eftersom ${\textstyle \left(A^{\textsf {T}}\ höger)^{\textsf {T}}=A}$ , vi kan skriva ${\textstyle \operatorname {rank} \left( A\right)=\operatörsnamn {rank} \left(\left(A^{\textsf {T}}\right)^{\textsf {T}}\right)\leq \operatörsnamn {rank} \left(A ^{\textsf {T}}\right)}$ . Detta bevisar ${\textstil \operatörsnamn {rank} \left(A\right)\leq \operatörsnamn {rank} \left(A^{\textsf {T}}\right )}$ .

Vi har därför bevisat ${\textstil \operatörsnamn {rank} \left(A^{\textsf {T}}\right)\leq \operatörsnamn {rank} \left (A\right)}$ och ${\textstyle \operatorname {rank} \left(A\right)\leq \operatorname {rank} \left(A^{\textsf { T}}\right)}$ , så ${\textstyle \operatorname {rank} \left(A\right)=\operatörsnamn {rank} \left(A^{\textsf {T}}\right)}$ .

Anteckningar

•   Banerjee, Sudipto; Roy, Anindya (2014), Linjär algebra och matrisanalys för statistik , Texter i statistisk vetenskap (1:a upplagan), Chapman och Hall/CRC, ISBN 978-1420095388
•   Lay, David C. (2005), Linear Algebra and its Applications (3:e upplagan), Addison Wesley, ISBN 978-0-201-70970-4
•   Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations , Johns Hopkins Studies in Mathematical Sciences (3:e upplagan), The Johns Hopkins University Press, ISBN 978-0-8018-5414-9
•   Stewart, Gilbert W. (1998), Matrix Algorithms. I. Basic Decompositions , SIAM, ISBN 978-0-89871-414-2
•   Piziak, R.; Odell, PL (1 juni 1999). "Fullständig rangfaktorisering av matriser". Matematiktidningen . 72 (3): 193. doi : 10.2307/2690882 . JSTOR 2690882 .