Cirkulerende matrix

I lineær algebra er en cirkulerende matrix en firkantet matrix, hvor vi går fra en række til den næste ved cirkulær permutation (skift til højre) af koefficienterne.

En cirkulerende matrix af størrelse n er derfor af formen

C = {\ begin {pmatrix} c_ {0} & c_ {1} & c_ {2} & \ dots & c _ {{n-1}} \\ c _ {{n-1}} & c_ {0 } & c_ {1} && c_ {{n-2}} \\ c _ {{n-2}} & c _ {{n-1}} & c_ {0} && c _ {{n-3} } \\\ vdots &&& \ ddots & \ vdots \\ c_ {1} & c_ {2} & c_ {3} & \ dots & c_ {0} \ end {pmatrix}}

hvor koefficienterne c i er komplekser.

En cirkulerende matrix udgør et bestemt tilfælde af en Toeplitz- matrix, af en Frobenius-matrix (det er den generiske matrix for multiplikationen med et element i gruppealgebra ℂ [ℤ / n ℤ] og også et bestemt tilfælde af den latinske firkant ).

Den nedsættelse af de cirkulerende matrixer involverer formlerne for den diskrete Fourier transformation . I numerisk analyse kan cirkulerende systemer løses meget effektivt ved hurtig Fourier-transformation .

Vi taler undertiden om en anticirkulerende eller venstre cirkulerende matrix, når vi skifter koefficienterne til venstre, mens vi går fra en linje til den næste.

Algebra af cirkulerende matricer

For at forenkle notationerne betegner vi ved C ( c 0 ,…, c n –1 ) den foregående cirkulerende matrix.

Bemærk

J = {\ begin {pmatrix} 0 & 1 & 0 & \ prikker & 0 \\ 0 & 0 & 1 & \ prikker & 0 \\\ vdots &&& \ prikker & \ vdots \\ 0 &&&& 1 \\ 1 & 0 & 0 & \ prikker & 0 \ slut {pmatrix}} = C (0,1, 0, ..., 0),

vi kan se, at enhver cirkulerende matrix er et polynom i J

C (c_ {0}, \ dots, c _ {{n-1}}) = \ sum _ {{j = 0}} ^ {{n-1}} c_ {j} J ^ {j} = P_ {C} (J).

Omvendt eftersom J n er identitetsmatricen , enhver polynomium i J er en cirkulerende matrix.

Således cirkulerer produktet af cirkulerende matricer, og et sådant produkt er kommutativt. Sættet af circulant matrixer er ingen anden end den algebra kommutativ af polynomier i J .

Reduktion af cirkulerende matricer

Diagonalisering af J

Matrixen J , der verificerer J n = I , kan diagonaliseres på ℂ med egenværdier af enhedens n- th rødder .

Vi kalder derfor primitiv grund til enhed. Det kan vi så let kontrollere for alle k $\ omega = e ^ {{{\ frac {2i \ pi} {n}}}}$

X_ {k} = {\ begin {pmatrix} 1 \\\ omega ^ {k} \\\ omega ^ {{2k}} \\\ vdots \\\ omega ^ {{(n-1) k}} \ slut {pmatrix}}

er egenvektor af J associeret med egenværdien $ω k$ .

Derfor udstillet, for k fra 0 til n - 1, en familie af n egenvektorer forbundet med egen særskilte værdier, en ren basis for J .

Diagonalisering af en cirkulerende matrix

Derfor er det et passende grundlag også for ethvert polynom i J , det vil sige enhver cirkulerende matrix. Egenværdierne for C ( c 0 ,…, c n –1 ) er derfor

\ lambda _ {k} = \ sum _ {{j = 0}} ^ {{n-1}} c_ {j} \ omega ^ {{kj}} = P_ {C} (\ omega ^ {k})

som denne gang ikke længere nødvendigvis er forskellige.

Man kan tage matrixen til matrix for passage fra den kanoniske base til den rette base

U = {\ frac 1 {{\ sqrt n}}} {\ begin {pmatrix} 1 & 1 & \ prikker & 1 \\ 1 & \ omega & \ prikker & \ omega ^ {{n-1}} \\ \ vdots & \ vdots && \ vdots \\ 1 & \ omega ^ {{n-1}} & \ dots & \ omega ^ {{(n-1) ^ {2}}} \ end {pmatrix}}.

Denne matrix U er enhed ( U * U = I ), og de foregående passageformler skrives ved at bemærke $Λ$ den diagonale matrix af koefficienterne egenværdier

C = U \ Lambda U ^ {{- 1}} = U \ Lambda U ^ {*} \ qquad \ Lambda = U ^ {{- 1}} CU = U ^ {*} CU.

Direkte verifikation

Lad være Vandermonde-matrixen , lad os kontrollere det . ${\ displaystyle \ Omega = {\ sqrt {n}} \, U = \ left (\ omega ^ {(i-1) (j-1)} \ right) _ {1 \ leq i, j \ leq n} }$ ${\ displaystyle C \ Omega = \ Omega \ Lambda}$

{\ displaystyle {\ begin {align} (C \ Omega) _ {i, j} & = \ sum _ {k = 1} ^ {n} c_ {k-i + 1 {\ pmod {n}}} \ omega ^ {(k-1) (j-1)} \\ & = \ sum _ {k = 1} ^ {n} c_ {k} \ omega ^ {(k + i-2) (j-1)} \ \ & = \ omega ^ {(i-1) (j-1)} \ sum _ {k = 1} ^ {n} c_ {k} \ omega ^ {(k-1) (j-1)} \ \ & = \ omega ^ {(i-1) (j-1)} \ sum _ {k = 1} ^ {n} c_ {k} (\ omega ^ {(j-1)}) ^ {(k -1)} \\ & = \ omega ^ {(i-1) (j-1)} \ lambda _ {j-1} \\ & = (\ Omega \ Lambda) _ {i, j}. \ End {align}}}

En ny mulig definition for sættet af cirkulerende matricer er sættet af matricer i form UDU * med D diagonal. Geometrisk svarer dette til endomorfismer, der tillader det ortonormale grundlag for X k som basis for egenvektorer.

Cirkulationsdeterminant

Den cirkulerende determinant er determinanten for den cirkulerende matrix; som for enhver anden matrix er den lig med produktet af egenværdierne

\ det C = \ prod _ {{k = 0}} ^ {{n-1}} P_ {C} (\ omega ^ {k}).

Enhver matrix er inverterbar, hvis og kun hvis dens determinant ikke er nul, og i tilfælde af en cirkulerende matrix er dens inverse matrix også en cirkulerende matrix.

Intervention af den diskrete Fourier-transformation

Af særlig interesse er basisændringsformlerne, der bruger U- matrixen . Formlen til overføring af koefficienterne til egenværdierne er den klassiske definition af en diskret Fourier-transformation . Vi kan finde koefficienterne fra egenværdierne ved at udføre denne omvendte transformation

c_ {k} = {\ frac 1n} \ sum _ {{j = 0}} ^ {{n-1}} \ lambda _ {j} \ omega ^ {{- kj}}.

Cirkulationssystem

Lade cirkulerende systemet Cx = b , med C cirkulerende matrix af størrelse n . Dette system kan omskrives ved hjælp af et diskret sammenblandingsprodukt

{\ mathbf {c}} * {\ mathbf {x}} = {\ mathbf {b}}

ved at betegne c den første kolonne i matricen C og ved at periodisere komponenterne i vektorerne c , x og b . Den diskrete Fourier-transformation forvandler denne foldningsligning til et komponent-for-komponent-produkt.

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

også

{\ 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].

Denne algoritme for opløsning er meget hurtigere end eliminering af Gauss-Jordan , og det er så meget mere, hvis man griber til den hurtige Fourier-transformation .

Se også

Latin firkant

eksterne links

(da) Eric W. Weisstein , “ Circulant Matrix ” , på MathWorld
(da) Eric W. Weisstein , ” Determinant cirkulant ” , på MathWorld