Cirkulerande matris

För de symmetriska graferna, se Cirkulantdiagram .

I linjär algebra är en cirkulerande matris en kvadratisk matris där alla radvektorer är sammansatta av samma element och varje radvektor roteras ett element åt höger i förhållande till föregående radvektor. Det är en speciell typ av Toeplitz-matris .

I numerisk analys är cirkulerande matriser viktiga eftersom de diagonaliseras av en diskret Fouriertransform , och därför kan linjära ekvationer som innehåller dem snabbt lösas med en snabb Fouriertransform . De kan tolkas analytiskt som den integrerade kärnan av en faltningsoperator på den cykliska gruppen $C_{n}$ och förekommer därför ofta i formella beskrivningar av rumsligt invarianta linjära operationer. Denna egenskap är också kritisk i moderna programvarudefinierade radioapparater, som använder Ortogonal Frequency Division Multiplexing för att sprida symbolerna (bitarna) med ett cykliskt prefix . Detta gör att kanalen kan representeras av en cirkulationsmatris, vilket förenklar kanalutjämningen i frekvensdomänen .

I kryptografi används en cirkulerande matris i steget MixColumns i Advanced Encryption Standard .

Definition

En $n\times n$ cirkulerande matris $C$ har formen

$$C={\begin{bmatrix}c_{0}&c_{n-1}&\cdots &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}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}$$

eller införlivandet av denna form (genom val av notation). När termen $c_{i}$ är en $p\times p$ kvadratisk matris, då $np\times np$ -matrisen $C$ kallas en blockcirkulerande matris .

En cirkulerande matris specificeras helt av en vektor, $c$ , som visas som den första kolumnen (eller raden) i $C$ . De återstående kolumnerna (och raderna, resp.) i $C$ är var och en cyklisk permutation av vektorn $c$ med offset lika med kolumn- (eller rad, resp.) index, om linjer är indexerade från 0 till $n-1$ . (Cyklisk permutation av rader har samma effekt som cyklisk permutation av kolumner.) Den sista raden i $C$ är vektorn $c$ skiftad med en i omvänd riktning.

Olika källor definierar den cirkulerande matrisen på olika sätt, till exempel enligt ovan, eller med vektorn $c$ som motsvarar den första raden snarare än den första kolumnen i matrisen; och möjligen med en annan växlingsriktning (som ibland kallas en anti-cirkulationsmatris ).

Polynomet $x)=c_{0}+c_{1}x+\dots +c_{n-1} x^{n-1}}$ ( kallas det associerade polynomet i matrisen $C$ .

Egenskaper

Egenvektorer och egenvärden

De normaliserade egenvektorerna för en cirkulationsmatris är Fourier-moden, nämligen

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

där $\omega =\exp \left({\tfrac {2\pi i}{n}}\right)$ är en primitiv $n$ -th roten av enhet och $i$ är den imaginära enheten .

(Detta kan förstås genom att inse att multiplikation med en cirkulerande matris implementerar en faltning. I Fourierrymden blir faltningar multiplikation. Därför ger produkten av en cirkulerande matris med en Fourier-mod en multipel av den Fourier-moden, dvs det är en egenvektor. )

Motsvarande egenvärden ges av

$$\lambda _{ j}=c_{0}+c_{n-1}\omega ^{j}+c_{n-2}\omega ^{2j}+\dots +c_{1}\omega ^{(n-1) j},\quad j=0,1,\dots ,n-1.$$

Determinant

Som en konsekvens av den explicita formeln för egenvärdena ovan kan determinanten för en cirkulationsmatris beräknas som:

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

Eftersom transponeringen inte ändrar egenvärdena för en matris, är en ekvivalent formulering

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

Rang

Rangen ${ \displaystyle \gcd(f(x),x^{n}-1)}$ en cirkulerande matris $C$ är lika med $nd$ , där $d$ är graden av polynomet − .

Övriga fastigheter

• Varje cirkulant är ett matrispolynom (nämligen det associerade polynomet) i den cykliska permutationsmatrisen $P$ :
  $$C=c_{0}I+c_{1}P+c_{2 }P^{2}+\dots +c_{n-1}P^{n-1}=f(P),$$
  där $P$ ges av
  $$P={\begin{bmatrix}0&0&\cdots &0&1\\1&0&\cdots &0&0\\0&\ddots &\ddots &\vdots &\vdots \\\vdots &\ddots &\ddots &0&0\\0&\ cdots &0&1&0\end{bmatrix}}.$$
• Mängden $n\ gånger n$ cirkulerande matriser bildar ett $\displaystyle n}$ { - dimensionellt vektorrum med avseende på addition och skalär multiplikation . Detta utrymme kan tolkas som rymden av funktioner i den cykliska gruppen av ordning $n$ , $C_{n}$ , eller motsvarande som gruppringen av $C_{n}$ .
• Cirkulantmatriser bildar en kommutativ algebra , eftersom för två givna cirkulerande matriser $A$ och ${\displaystyle B} är$ summan $A+B$ cirkulant, produkten $AB$ är cirkulerande och $AB=BA$ .
• För en icke-singular cirkulerande matris ${\displaystyle A} är$ dess invers $A^{-1}$ också cirkulant. För en singulär cirkulerande matris är dess Moore–Penrose pseudoinvers $A^{+}$ cirkulerande.
• Matrisen $U$ som är sammansatt av egenvektorerna för en cirkulerande matris är relaterad till den diskreta Fouriertransformen och dess inversa transform:
  $$U_{n}^{*}={\frac {1}{\sqrt {n}}}F_{n},\quad {\text{and}}\quad U_{n}={\frac {1}{\sqrt {n}}}F_{n}^{-1},{\text{ där }}F_{n}=(f_{jk}){\text{ med }}f_{jk} =e^{-2jk\pi i/n},\,{\text{för }}0\leq j,k<n.$$
  diagonaliserar matrisen $U_{n}$$C$ . Det har vi faktiskt
  $$C=U_{n}\operatörsnamn {diag} (F_{n} c)U_{n}^{*}={\frac {1}{n}}F_{n}^{-1}\operatörsnamn {diag} (F_{n}c)F_{n},$$
  där $c$ är den första kolumnen i $C$ . Egenvärdena för $C$ ges av produkten $F_{n}c$ . Denna produkt kan lätt beräknas genom en snabb Fouriertransform . Omvänt, för vilken diagonal matris ${\displaystyle D} som helst$ , är produkten $F_{n}^{-1}DF_{n}$ cirkulerande.
• Låt $p(x)$ vara det ( moniska ) karakteristiska polynomet för en $n\times n$ cirkulerande matris $C$ , och låt ${ \displaystyle p'(x)}$ vara derivatan av $p(x)$ . Då är polynomet ${\textstyle {\frac {1}{n}}p'(x)}$ det karakteristiska polynomet för följande $(n-1)\ gånger (n-1)$ submatris av $C$ :
  $$C_{n-1}={\begin{bmatrix}c_{0}&c_{n-1}&\cdots &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}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}$$
  (se för bevis).

Analytisk tolkning

Cirkulanta matriser kan tolkas geometriskt, vilket förklarar sambandet med den diskreta Fouriertransformen.

Betrakta vektorer i $\mathbb {R} ^{n}$ som funktioner på heltal med period $n$ , (dvs som periodiska bi-oändliga sekvenser: $\dots ,a_{0},a_{1},\dots ,a_{n-1},a_{0},a_{1},\dots$ ) eller motsvarande, som funktioner på den cykliska gruppen av ordning $n$ ( $C_{n}$ eller $\mathbb {Z} /n\mathbb {Z}$ ) geometriskt, på (topparna av) den reguljära $n$ -gon : detta är en diskret analog till periodiska funktioner på den reella linjen eller cirkeln.

operatorteorins perspektiv , är en cirkulerande $(c_{0}, c_{1},\dots ,c_{n-1})$ kärnan i en diskret integraltransform , nämligen faltningsoperatorn för funktionen ; detta är en diskret cirkulär faltning . Formeln för faltningen av funktionerna $(b_{i}):=(c_{i})*(a_{i})$ är

$$b_{k}=\summa _{i=0}^{n-1}a_{i}c_{ki}$$

(kom ihåg att sekvenserna är periodiska) vilket är produkten av vektorn $(a_{i})$ av den cirkulerande matrisen för $(c_{i})$ .

Den diskreta Fouriertransformen omvandlar sedan faltning till multiplikation, vilket i matrisinställningen motsvarar diagonalisering.

C $C^{*}$ -algebra för alla cirkulerande matriser med komplexa poster är isomorf till gruppen $\displaystyle C^{*}}$ -algebra för $\mathbb { Z} /n\mathbb {Z}$ .

Symmetriska cirkulationsmatriser

För en symmetrisk cirkulationsmatris $C$ har man det extra villkoret att $c_{ni}=c_{i}$ . Det bestäms alltså av $\lfloor n/2\rfloor +1$ element.

$$C={\begin{bmatrix}c_{0}&c_{1}&\cdots &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}&\cdots &c_{1}&c_ {0}\\\end{bmatrix}}.$$

Egenvärdena för en reell symmetrisk matris är reella. Motsvarande egenvärden blir:

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

för $n$ jämn , och

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

för $n$ udda , där $\Re z$ anger den verkliga delen av $z$ . Detta kan förenklas ytterligare genom att använda det faktum att $\Re \omega _{j}^{k}=\cos(2\pi jk/n) )$ .

Symmetriska cirkulerande matriser tillhör klassen bisymmetriska matriser .

Hermitiska cirkulerande matriser

Den komplexa versionen av den cirkulerande matrisen, allmänt förekommande i kommunikationsteori, är vanligtvis hermitisk . I detta fall $c_{ni}=c_{i}^{*},\;i\leq n/2$ och dess determinant och alla egenvärden är verklig.

Om n är jämnt tar de två första raderna nödvändigtvis formen

$${\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}^{*}\\\dots \\\end{bmatrix}}.$$

där det första elementet $r_{3}$ i den övre andra halvraden är reellt.

Om n är udda får vi

$${\begin{bmatrix}r_{0}&z_{1}&z_{2}&z_{2}^{*}&z_{1}^{*}\\z_{1}^{*}&r_{0 }&z_{1}&z_{2}&z_{2}^{*}\\\dots \\\end{bmatrix}}.$$

Tee har diskuterat begränsningar för egenvärdena för det hermitiska tillståndet.

Ansökningar

I linjära ekvationer

Givet en matrisekvation

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

där $C$ är en cirkulerande kvadratisk matris med storleken $n$ kan vi skriva ekvationen som den cirkulära faltningen

$$\mathbf {c} \star \mathbf {x} =\mathbf {b} ,$$

där $\mathbf {c}$ är den första kolumnen i $C$ , och vektorerna $\mathbf {c}$ , $\mathbf {x}$ och ${ \displaystyle \mathbf {b} }$ förlängs cykliskt i varje riktning. Med hjälp av satsen för cirkulär faltning kan vi använda den diskreta Fourier-transformen för att omvandla den cykliska faltningen till komponentvis multiplikation

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

så att

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

Denna algoritm är mycket snabbare än den vanliga Gauss-elimineringen , speciellt om en snabb Fourier-transform används.

I grafteori

I grafteorin kallas en graf eller digraf vars närliggande matris är cirkulerande en cirkulerande graf (eller digraf). På motsvarande sätt är en graf cirkulerande om dess automorfismgrupp innehåller en fullängdscykel. Möbius -stegen är exempel på cirkulerande grafer, liksom Paley-graferna för fält av prime ordning.

externa länkar

• RM Gray, Toeplitz och Circulant Matriser: En recension doi : 10.1561/0100000006
• Weisstein, Eric W. "Circulant Matrix" . MathWorld .
• IPython Notebook som visar egenskaperna hos cirkulerande matriser