Cirkulační matice - Circulant matrix

${\displaystyle \omega =\exp \left({\tfrac {2\pi i}{n}}\right)}$

${\displaystyle n}$

${\displaystyle i}$

(To lze pochopit tak, že si uvědomíme, že multiplikace s cirkulační maticí implementuje konvoluci. Ve Fourierově prostoru se konvoluce stanou multiplikací. Proto součin cirkulační matice s Fourierovým režimem dává násobek tohoto Fourierova režimu, tj. Jde o vlastní vektor. )

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

$${\displaystyle \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

V důsledku explicitního vzorce pro vlastní čísla výše lze determinant cirkulační matice 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}).}$$

$${\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

Hodnost z circulant matice je rovna , kde je

${\displaystyle C}$

${\displaystyle n-d}$

${\displaystyle d}$

${\displaystyle \gcd(f(x),x^{n}-1)}$

Další vlastnosti

• Jakýkoli oběh je maticový polynom (konkrétně přidružený polynom) v cyklické permutační matici :${\displaystyle P}$
  $${\displaystyle C=c_{0}I+c_{1}P+c_{2}P^{2}+\dots +c_{n-1}P^{n-1}=f(P),}$$

  
  kde je dáno${\displaystyle P}$
  $${\displaystyle 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}}.}$$

  
• Sada z circulant matic tvoří -

${\displaystyle p(x)}$

${\displaystyle n\times n}$

${\displaystyle C}$

${\displaystyle p'(x)}$

${\displaystyle p(x)}$

${\textstyle {\frac {1}{n}}p'(x)}$

${\displaystyle (n-1)\times (n-1)}$

${\displaystyle C}$

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

Analytická interpretace

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

Zvažte vektory jako funkce na

${\displaystyle \mathbb {R} ^{n}}$

${\displaystyle n}$

${\displaystyle \dots ,a_{0},a_{1},\dots ,a_{n-1},a_{0},a_{1},\dots }$

${\displaystyle n}$

${\displaystyle C_{n}}$

${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

${\displaystyle n}$

Pak je z pohledu teorie operátorů cirkulační matice jádrem diskrétní integrální transformace , konkrétně konvolučním operátorem pro funkci ; toto je diskrétní

${\displaystyle (c_{0},c_{1},\dots ,c_{n-1})}$

${\displaystyle (b_{i}):=(c_{i})*(a_{i})}$

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

${\displaystyle (a_{i})}$

${\displaystyle (c_{i})}$

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

Algebra všech circulant matic s

${\displaystyle C^{*}}$

${\displaystyle C^{*}}$

${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

Symetrické cirkulační matice

Pro symetrickou cirkulační matici má člověk další podmínku, že . Je tedy určen prvky. ${\displaystyle C}$${\displaystyle c_{n-i}=c_{i}}$${\displaystyle \lfloor n/2\rfloor +1}$

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

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

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

${\displaystyle n}$

${\displaystyle \Re z}$

${\displaystyle z}$

${\displaystyle \Re \omega _{j}^{k}=\cos(2\pi jk/n)}$

Složité symetrické cirkulační matice

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

Pokud n je dokonce první dva řádky, nutně má formu

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

${\displaystyle r_{3}}$

Pokud n je liché, dostaneme

$${\displaystyle {\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 diskutoval omezení vlastních čísel pro komplexní symetrické podmínky.

Aplikace

V lineárních rovnicích

Daná maticová rovnice

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

${\displaystyle \mathbf {c} }$

${\displaystyle C}$

${\displaystyle \mathbf {c} }$

${\displaystyle \mathbf {x} }$

${\displaystyle \mathbf {b} }$

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

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

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

V teorii grafů

V teorii grafů se graf nebo digraf, jehož maticí sousedství je oběhový, nazývá oběžný graf (nebo digraf). Ekvivalentně je graf v oběhu, pokud jeho skupina automorfismu obsahuje cyklus v plné délce. Na Möbius žebříky jsou příklady circulant grafů, jako jsou grafy Paley na polích v prime pořadí.

Reference

externí odkazy

• RM Gray, Toeplitz a oběhové matrice: recenze
• Weisstein, Eric W. „Cirkulační matice“ . MathWorld .
• IPython Notebook demonstrující vlastnosti cirkulačních matic