Faktorizace pořadí - Rank factorization

v matematika, vzhledem k m × n matice ${ displaystyle A}$ z hodnost ${ displaystyle r}$, a hodnostní rozklad nebo faktorizace pořadí z ${ displaystyle A}$ je faktorizace ${ displaystyle A}$ formuláře ${ displaystyle A = CF,}$ kde ${ displaystyle C}$ je m × r matice a ${ displaystyle F}$ je r × n matice.

Existence

Každá konečně-dimenzionální matice má hodnostní rozklad: Nechat ${ textový styl A}$ být ${ textový styl krát n}$ matice jehož pořadí sloupců je ${ textstyle r}$. Proto existují ${ textstyle r}$ lineárně nezávislé sloupce v ${ textový styl A}$; ekvivalentně dimenze z sloupcový prostor z ${ textový styl A}$ je ${ textstyle r}$. Nechat ${ textstyle c_ {1}, c_ {2}, ldots, c_ {r}}$ být kdokoli základ pro prostor sloupců ${ textový styl A}$ a umístit je jako vektory sloupců k vytvoření ${ textstyle m krát r}$ matice ${ textstyle C = [c_ {1}: c_ {2}: ldots: c_ {r}]}$. Proto každý vektor sloupce ${ textový styl A}$ je lineární kombinace ze sloupců ${ textový styl C}$. Přesně, pokud ${ textstyle A = [a_ {1}: a_ {2}: ldots: a_ {n}]}$ je ${ textový styl krát n}$ matice s ${ textstyle a_ {j}}$ jako ${ textstyle j}$-tý sloupec

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

kde ${ textstyle f_ {ij}}$Jsou skalární koeficienty ${ textstyle a_ {j}}$ z hlediska základu ${ textstyle c_ {1}, c_ {2}, ldots, c_ {r}}$. To z toho vyplývá ${ textstyle A = CF}$, kde ${ textstyle f_ {ij}}$ je ${ textstyle (i, j)}$-tý prvek ${ textstyle F}$.

Neunikátnost

Li ${ textstyle A = C_ {1} F_ {1}}$ je faktorizace hodnosti, přičemž ${ textstyle C_ {2} = C_ {1} R}$ a ${ textstyle F_ {2} = R ^ {- 1} F_ {1}}$ dává další faktorizaci pořadí pro jakoukoli invertibilní matici ${ textstyle R}$ kompatibilních rozměrů.

Naopak, pokud ${ textstyle A = F_ {1} G_ {1} = F_ {2} G_ {2}}$ jsou dvě faktorizace pořadí ${ textový styl A}$, pak existuje invertibilní matice ${ textstyle R}$ takhle ${ textstyle F_ {1} = F_ {2} R}$ a ${ textstyle G_ {1} = R ^ {- 1} G_ {2}}$.^[1]

Konstrukce

Faktorizace pořadí ze zmenšených řadových řad

V praxi můžeme sestrojit jednu konkrétní faktorizaci pořadí následovně: můžeme vypočítat ${ textový styl B}$, snížená řada echelon forma z ${ textový styl A}$. Pak ${ textstyle C}$ se získá odstraněním z ${ textový styl A}$ všechny non-kontingenční sloupce, a ${ textstyle F}$ odstraněním všech nulových řádků ${ textový styl B}$.

Příklad

Zvažte matici

${ 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 a 0 bmatrix}} = B { text {.}}}$

${ textový styl B}$ je ve formě sníženého sledu.

Pak ${ textstyle C}$ se získá odstraněním třetího sloupce ${ textový styl A}$, jediný, který není otočným sloupcem, a ${ textstyle F}$ zbavením se poslední řady nul, tak

${ 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 a 0 a 0 a 1 end {bmatrix}} { text {.}}}$

Je to jednoduché zkontrolovat

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

Důkaz

Nechat ${ textový styl P}$ být ${ textový styl n krát n}$ permutační matice taková ${ textstyle AP = (C, D)}$ v blok rozdělen formulář, kde jsou sloupce ${ textstyle C}$ jsou ${ textstyle r}$ kontingenční sloupce ${ textový styl A}$. Každý sloupec ${ textstyle D}$ je lineární kombinace sloupců ${ textový styl C}$, takže existuje matice ${ textstyle G}$ takhle ${ textstyle D = CG}$, kde jsou sloupce ${ textstyle G}$ obsahují koeficienty každé z těchto lineárních kombinací. Tak ${ textstyle AP = (C, CG) = C (I_ {r}, G)}$, ${ textstyle I_ {r}}$ být ${ textový styl krát r}$ matice identity. Teď to ukážeme ${ textstyle (I_ {r}, G) = FP}$.

Transformace ${ textový styl A}$ do své redukované řady echelon formy ${ textový styl B}$ se rovná násobení vlevo maticí ${ textový styl E}$ který je produktem základní matice, tak ${ textstyle EAP = BP = EC (I_ {r}, G)}$, kde ${ textstyle EC = { begin {pmatrix} I_ {r} 0 end {pmatrix}}}$. Pak můžeme psát ${ textstyle BP = { begin {pmatrix} I_ {r} & G 0 & 0 end {pmatrix}}}$, což nám umožňuje identifikovat ${ textstyle (I_ {r}, G) = FP}$nenulová ${ textstyle r}$ řádky formy se sníženým sledem, se stejnou permutací na sloupcích, jakou jsme udělali pro ${ textový styl A}$. Máme tedy ${ textstyle AP = CFP}$, a od té doby ${ textový styl P}$ je invertibilní, z čehož vyplývá ${ textstyle A = CF}$a důkaz je kompletní.

Rozklad singulární hodnoty

Lze také sestrojit faktorizaci celého řádu ${ textový styl A}$ pomocí jeho rozklad singulární hodnoty

${ displaystyle A = U Sigma V ^ {*} = { begin {bmatrix} U_ {1} & U_ {2} end {bmatrix}} { begin {bmatrix} Sigma _ {r} & 0 0 a 0 end {bmatrix}} { begin {bmatrix} V_ {1} ^ {*} V_ {2} ^ {*} end {bmatrix}} = U_ {1} left ( Sigma _ {r} V_ {1} ^ {*} vpravo).}$

Od té doby ${ textstyle U_ {1}}$ je celá matice pořadí sloupců a ${ textstyle Sigma _ {r} V_ {1} ^ {*}}$ je řada řádků matice, můžeme vzít ${ textstyle C = U_ {1}}$ a ${ textstyle F = Sigma _ {r} V_ {1} ^ {*}}$.

Důsledky

pořadí (A) = pořadí (A^T)

Okamžitým důsledkem faktorizace pořadí je, že pořadí ${ textový styl A}$ se rovná hodnosti jeho transpozice ${ textstyle A ^ { textyf {T}}}$. Vzhledem k tomu, že sloupce ${ textový styl A}$ jsou řádky ${ textstyle A ^ { textyf {T}}}$, pořadí sloupců z ${ textový styl A}$ rovná se jeho řada.^[2]

Důkaz: Abychom zjistili, proč je to pravda, definujme nejprve pořadí na střední pořadí sloupců. Od té doby ${ textstyle A = CF}$, z toho vyplývá, že ${ textstyle A ^ { textyf {T}} = F ^ { textyf {T}} C ^ { textyf {T}}}$. Z definice násobení matic, to znamená, že každý sloupec ${ textstyle A ^ { textyf {T}}}$ je lineární kombinace ze sloupců ${ textstyle F ^ { textyf {T}}}$. Proto je prostor sloupců ${ textstyle A ^ { textyf {T}}}$ je obsažen v prostoru sloupců ${ textstyle F ^ { textyf {T}}}$ a tedy hodnost${ textstyle left (A ^ { textyf {T}} vpravo)}$ ≤ pozice${ textstyle left (F ^ { textyf {T}} vpravo)}$.

Nyní, ${ textstyle F ^ { textyf {T}}}$ je ${ textový styl časy$, takže existují ${ textstyle r}$ sloupce v ${ textstyle F ^ { textyf {T}}}$ a tedy hodnost${ textstyle left (A ^ { textyf {T}} vpravo)}$ ≤ ${ textstyle r}$ = pořadí${ textstyle left (A right)}$. To dokazuje tuto hodnost${ textstyle left (A ^ { textyf {T}} vpravo)}$ ≤ pozice${ textstyle left (A right)}$.

Výsledek nyní použijte na ${ textstyle A ^ { textyf {T}}}$ získat obrácenou nerovnost: od ${ textstyle left (A ^ { textyf {T}} doprava) ^ { textyf {T}}}$ = ${ textový styl A}$, můžeme napsat hodnost${ textstyle left (A right)}$ = pořadí${ textstyle left ( left (A ^ { textyf {T}} doprava) ^ { textyf {T}} doprava)}$ ≤ pozice${ textstyle left (A ^ { textyf {T}} vpravo)}$. To dokazuje hodnost${ textstyle left (A right)}$ ≤ pozice${ textstyle left (A ^ { textyf {T}} vpravo)}$.

Proto jsme prokázali hodnost${ textstyle left (A ^ { textyf {T}} vpravo)}$ ≤ pozice${ textstyle left (A right)}$ a pořadí${ textstyle left (A right)}$ ≤ pozice${ textstyle left (A ^ { textyf {T}} vpravo)}$, tak hodnost${ textstyle left (A right)}$ = pořadí${ textstyle left (A ^ { textyf {T}} vpravo)}$. (Viz také první důkaz o pořadí sloupců = pořadí řádků níže hodnost ).

Poznámky

Reference