Oběžná matice - Circulant matrix

v lineární algebra, a cirkulační matice je čtverec matice ve kterém každý řádek vektor je otočen o jeden prvek doprava vzhledem k předchozímu vektoru řádků. Je to zvláštní druh Toeplitzova matice.

v numerická analýza, oběhové matice jsou důležité, protože jsou diagonalizovány a diskrétní Fourierova transformace, a tedy lineární rovnice které je obsahují, lze rychle vyřešit pomocí a rychlá Fourierova transformace.^[1] Oni mohou být interpretován analyticky jako integrální jádro a operátor konvoluce na cyklická skupina ${ displaystyle C_ {n}}$ a proto se často objevují ve formálních popisech prostorově invariantních lineárních operací.

v kryptografie, v systému se používá cirkulační matice MixColumns krok Advanced Encryption Standard.

Definice

An ${ displaystyle n krát n}$ cirkulační matice ${ displaystyle C}$ má formu

${ displaystyle C = { begin {bmatrix} c_ {0} & c_ {n-1} & dots & c_ {2} & c_ {1} c_ {1} & c_ {0} & c_ {n-1} && c_ { 2} vdots & c_ {1} & c_ {0} & ddots & vdots c_ {n-2} && ddots & ddots & c_ {n-1} c_ {n-1} & c_ { n-2} & dots & c_ {1} & c_ {0} end {bmatrix}}}$

nebo provedení tohoto formuláře (výběrem notace).

Matice cirkulace je plně specifikována jedním vektorem, ${ displaystyle c}$, který se zobrazí jako první sloupec (nebo řádek) z ${ displaystyle C}$. Zbývající sloupce (resp. Řádky) z ${ displaystyle C}$ jsou každý cyklické permutace vektoru ${ displaystyle c}$ s posunem rovným indexu sloupce (resp. řádku), pokud jsou řádky indexovány od 0 do ${ displaystyle n-1}$. (Cyklická permutace řádků má stejný účinek jako cyklická permutace sloupců.) Poslední řádek z ${ displaystyle C}$ je vektor ${ displaystyle c}$ posunut o jeden vzad.

Různé zdroje definují cirkulační matici různými způsoby, například jak je uvedeno výše, nebo pomocí vektoru ${ displaystyle c}$ odpovídající prvnímu řádku spíše než prvnímu sloupci matice; a případně s jiným směrem řazení (kterému se někdy říká anti-cirkulační matice).

Polynom ${ displaystyle f (x) = c_ {0} + c_ {1} x + tečky + c_ {n-1} x ^ {n-1}}$ se nazývá přidružený polynom matice ${ displaystyle C}$.

Vlastnosti

Vlastní vektory a vlastní hodnoty

Normalizovaný vlastní vektory cirkulační matice jsou Fourierovy režimy, jmenovitě

${ displaystyle v_ {j} = { frac {1} { sqrt {n}}} (1, omega ^ {j}, omega ^ {2j}, ldots, omega ^ {(n-1 ) j}), quad j = 0,1, ldots, n-1,}$

kde ${ displaystyle omega = exp left ({ tfrac {2 pi i} {n}} right)}$ je primitivní ${ displaystyle n}$-th kořen jednoty a ${ displaystyle i}$ je imaginární jednotka.

(Lze to pochopit, když si uvědomíme, že cirkulační matice implementuje konvoluci.)

Odpovídající vlastní čísla jsou pak dána vztahem

${ displaystyle lambda _ {j} = c_ {0} + c_ {n-1} omega ^ {j} + c_ {n-2} omega ^ {2j} + ldots + c_ {1} omega ^ {(n-1) j}, qquad j = 0,1, ldots, n-1.}$

Rozhodující

V důsledku výslovného vzorce pro vlastní čísla nahoře je určující cirkulační matice lze vypočítat jako:

${ displaystyle det (C) = prod _ {j = 0} ^ {n-1} (c_ {0} + c_ {n-1} omega ^ {j} + c_ {n-2} omega ^ {2j} + dots + c_ {1} omega ^ {(n-1) j}).}$

Protože převzetí transpozice nemění vlastní hodnoty matice, je ekvivalentní formulace

${ displaystyle det (C) = prod _ {j = 0} ^ {n-1} (c_ {0} + c_ {1} omega ^ {j} + c_ {2} omega ^ {2j} + dots + c_ {n-1} omega ^ {(n-1) j}) = prod _ {j = 0} ^ {n-1} f ( omega ^ {j}).}$

Hodnost

The hodnost cirkulační matice ${ displaystyle C}$ je rovný ${ displaystyle n-d}$, kde ${ displaystyle d}$ je stupeň polynomu ${ displaystyle gcd (f (x), x ^ {n} -1)}$.^[2]

Další vlastnosti

• Libovolný cirkulační prostředek je maticový polynom (konkrétně asociovaný polynom) v cyklické podobě permutační matice ${ displaystyle P}$:

${ displaystyle C = c_ {0} I + c_ {1} P + c_ {2} P ^ {2} + ldots + c_ {n-1} P ^ {n-1} = f (P),}$

kde ${ displaystyle P}$ je dána

${ displaystyle P = { begin {bmatrix} 0 & 0 & ldots & 0 & 1 1 & 0 & ldots & 0 & 0 0 & ddots & ddots & vdots & vdots vdots & ddots & ddots & 0 & 0 0 & ldots & 0 & 1 & 0 end {bmatrix}}.}$

• Sada ${ displaystyle n krát n}$ cirkulační matice tvoří ${ displaystyle n}$-dimenzionální vektorový prostor s ohledem na jejich standardní sčítání a skalární násobení. Tento prostor lze interpretovat jako prostor funkcí na cyklická skupina řádu n, ${ displaystyle C_ {n}}$, nebo ekvivalentně jako skupinové vyzvánění z ${ displaystyle C_ {n}}$.
• Matice oběhového čerpadla tvoří a komutativní algebra, protože pro jakékoli dvě dané cirkulační matice ${ displaystyle A}$ a ${ displaystyle B}$, součet ${ displaystyle A + B}$ je oběh, produkt ${ displaystyle AB}$ je v oběhu a ${ displaystyle AB = BA}$.
• Matice ${ displaystyle U}$ který se skládá z vlastní vektory cirkulační matice souvisí s diskrétní Fourierova transformace a jeho inverzní transformace:

${ displaystyle U_ {n} ^ {*} = { frac {1} { sqrt {n}}} F_ {n}, quad { text {a}} quad U_ {n} = { frac {1} { sqrt {n}}} F_ {n} ^ {- 1}, quad { text {kde}} quad F_ {n} = (f_ {jk}) quad { text {s }} quad f_ {jk} = e ^ {- 2jk pi i / n}, quad { text {pro}} quad 0 leq j, k$

V důsledku toho matice ${ displaystyle U_ {n}}$ diagonalizuje ${ displaystyle C}$. Ve skutečnosti máme

${ displaystyle C = U_ {n} operatorname {diag} (F_ {n} c) U_ {n} ^ {*} = { frac {1} {n}} F_ {n} ^ {- 1} operatorname {diag} (F_ {n} c) F_ {n},}$

kde ${ displaystyle c}$ je první sloupec ${ displaystyle C}$. Vlastní čísla ${ displaystyle C}$ jsou dány produktem ${ displaystyle F_ {n} c}$. Tento produkt lze snadno vypočítat pomocí a rychlá Fourierova transformace.^[3]

• Nechat ${ displaystyle p (x)}$ být (monický) charakteristický polynom an ${ displaystyle n krát n}$ cirkulační matice ${ displaystyle C}$a nechte ${ displaystyle p '(x)}$ být derivátem ${ displaystyle p (x)}$. Pak polynom ${ displaystyle { frac {1} {n}} p '(x)}$ je charakteristický polynom následujícího ${ displaystyle (n-1) krát (n-1)}$ submatice ${ displaystyle C}$:

${ displaystyle C_ {n-1} = { begin {bmatrix} c_ {0} & c_ {n-1} & dots & c_ {3} & c_ {2} c_ {1} & c_ {0} & c_ {n -1} && c_ {3} vdots & c_ {1} & c_ {0} & ddots & vdots c_ {n-3} && ddots & ddots & c_ {n-1} c_ {n -2} & c_ {n-3} & dots & c_ {1} & c_ {0} end {bmatrix}}}$

(vidět^[4] pro důkaz).

Analytická interpretace

Cirkulační matice lze interpretovat geometricky, což vysvětluje souvislost s diskrétní Fourierovou transformací.

Zvažte vektory v ${ displaystyle mathbf {R} ^ {n}}$ jako funkce na celá čísla s tečkou ${ displaystyle n}$, (tj. jako periodické bi-nekonečné sekvence: ${ displaystyle dots, a_ {0}, a_ {1}, dots, a_ {n-1}, a_ {0}, a_ {1}, dots}$) nebo ekvivalentně jako funkce na cyklická skupina řádu ${ displaystyle n}$ (${ displaystyle C_ {n}}$ nebo ${ displaystyle mathbf {Z} / n mathbf {Z}}$) geometricky, na (vrcholech) pravidelné ${ displaystyle n}$-gon: toto je diskrétní analogický k periodickým funkcím na reálné přímce nebo kružnici.

Pak z pohledu teorie operátorů, cirkulační matice je jádro diskrétní integrální transformace, jmenovitě operátor konvoluce pro funkci ${ displaystyle (c_ {0}, c_ {1}, tečky, c_ {n-1})}$; toto je diskrétní kruhová konvoluce. Vzorec pro konvoluci funkcí ${ displaystyle (b_ {i}): = (c_ {i}) * (a_ {i})}$ je

${ displaystyle b_ {k} = součet _ {i = 0} ^ {n-1} a_ {i} c_ {k-i}}$ (připomeňme, že sekvence jsou periodické)

který je produktem vektoru ${ displaystyle (a_ {i})}$ matricí cirkulace pro ${ displaystyle (c_ {i})}$.

Diskrétní Fourierova transformace pak převádí konvoluci na násobení, což v nastavení matice odpovídá diagonalizaci.

The ${ displaystyle C ^ {*}}$-algebra všech cirkulačních matic se složitými položkami je pro skupinu izomorfní ${ displaystyle C ^ {*}}$-algebra z ${ displaystyle mathbf {Z} / n mathbf {Z}}$.

Symetrické cirkulační matice

Pro symetrickou cirkulační matici ${ displaystyle C}$ jeden má zvláštní podmínku, že ${ displaystyle c_ {n-i} = c_ {i}}$. Určuje to tedy ${ displaystyle lfloor n / 2 rfloor +1}$ elementy.

${ displaystyle C = { begin {bmatrix} c_ {0} & c_ {1} & dots & c_ {2} & c_ {1} c_ {1} & c_ {0} & c_ {1} && c_ {2} vdots & c_ {1} & c_ {0} & ddots & vdots c_ {2} && ddots & ddots & c_ {1} c_ {1} & c_ {2} & dots & c_ {1} & c_ {0} end {bmatrix}}.}$

Vlastní čísla jakékoli skutečné symetrické matice jsou skutečná. Odpovídající vlastní čísla se stanou:

${ displaystyle lambda _ {j} = c_ {0} + 2c_ {1} Re omega _ {j} + 2c_ {2} Re omega _ {j} ^ {2} + ldots + 2c_ { n / 2-1} Re omega _ {j} ^ {n / 2-1} + c_ {n / 2} omega _ {j} ^ {n / 2}}$

pro ${ displaystyle n}$ dokonce, a

${ displaystyle lambda _ {j} = c_ {0} + 2c_ {1} Re omega _ {j} + 2c_ {2} Re omega _ {j} ^ {2} + ldots + 2c_ { (n-1) / 2} Re omega _ {j} ^ {(n-1) / 2}}$

pro liché ${ displaystyle n}$, kde ${ displaystyle Re z}$ označuje skutečnou část ${ displaystyle z}$To lze dále zjednodušit použitím skutečnosti, že ${ displaystyle Re omega _ {j} ^ {k} = cos (2 pi jk / n)}$.

Komplexní symetrické cirkulační matice

Složitá verze cirkulační matice, všudypřítomná v teorii komunikace, je obvykle Hermitian. V tomto případě ${ displaystyle c_ {n-i} = c_ {i} ^ {*}, ; i leq n / 2}$ a jeho determinant a všechny vlastní hodnoty jsou skutečné.

Li n je dokonce první dva řádky nutně mají podobu

${ displaystyle { begin {bmatrix} r_ {0} & z_ {1} & z_ {2} & r_ {3} & z_ {2} ^ {*} & z_ {1} ^ {*} z_ {1} ^ {* } & r_ {0} & z_ {1} & z_ {2} & r_ {3} & z_ {2} ^ {*} tečky end {bmatrix}}.}$

ve kterém je první prvek ${ displaystyle r_ {3}}$ v horní druhé polovině je skutečný.

Li n je divné, že jsme

${ displaystyle { begin {bmatrix} r_ {0} & z_ {1} & z_ {2} & z_ {2} ^ {*} & z_ {1} ^ {*} z_ {1} ^ {*} & r_ {0 } & z_ {1} & z_ {2} & z_ {2} ^ {*} tečky end {bmatrix}}.}$

Tee^[5] diskutoval omezení vlastních čísel pro komplexní symetrickou podmínku.

Aplikace

V lineárních rovnicích

Vzhledem k maticové rovnici

${ displaystyle mathbf {C} mathbf {x} = mathbf {b},}$

kde ${ displaystyle C}$ je cirkulační čtvercová matice velikosti ${ displaystyle n}$ můžeme rovnici napsat jako kruhová konvoluce

${ displaystyle mathbf {c} hvězda mathbf {x} = mathbf {b},}$

kde ${ displaystyle c}$ je první sloupec ${ displaystyle C}$a vektory ${ displaystyle c}$, ${ displaystyle x}$ a ${ displaystyle b}$ jsou cyklicky prodlouženy v každém směru. Za použití věta o kruhové konvoluci, můžeme použít diskrétní Fourierova transformace transformovat cyklickou konvoluci na násobení komponent

${ displaystyle { mathcal {F}} _ {n} ( mathbf {c} star mathbf {x}) = { mathcal {F}} _ {n} ( mathbf {c}) { mathcal {F}} _ {n} ( mathbf {x}) = { mathcal {F}} _ {n} ( mathbf {b})}$

aby

${ displaystyle mathbf {x} = { mathcal {F}} _ {n} ^ {- 1} left [ left ({ frac {({ mathcal {F}} _ {n} ( mathbf {b})) _ { nu}} {({ mathcal {F}} _ {n} ( mathbf {c})) _ { nu}}} vpravo) _ {! nu in mathbf {Z}} vpravo] ^ { rm {T}}.}$

Tento algoritmus je mnohem rychlejší než standardní Gaussova eliminace, zvláště pokud a rychlá Fourierova transformace se používá.

V teorii grafů

v teorie grafů, a graf nebo digraf jehož matice sousedství je cirkulační se nazývá a oběhový graf (nebo digraf). Ekvivalentně je graf v oběhu, pokud je skupina automorfismu obsahuje celovečerní cyklus. The Möbiovy žebříky jsou příklady grafů cirkulace, stejně jako Paleyovy grafy pro pole hlavního řádu.

Reference

externí odkazy

• R. M. Gray, Toeplitz and Circulant Matrices: A Review
• Weisstein, Eric W. "Circulant Matrix". MathWorld.
• IPython Notebook demonstrující vlastnosti cirkulačních matic