Matriz circulante

Na álgebra linear , uma matriz circulante é uma matriz quadrada na qual vamos de uma linha para a próxima por permutação circular (deslocamento para a direita) dos coeficientes.

Uma matriz circulante de tamanho n é, portanto, da forma

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}}

onde os coeficientes c i são complexos.

Uma matriz circulante constitui um caso particular de matriz de Toeplitz , de matriz de Frobenius (é a matriz genérica da multiplicação por um elemento da álgebra de grupo ℂ [ℤ / n ℤ] e também um caso particular de quadrado latino ).

A redução das matrizes circulantes envolve as fórmulas da transformação discreta de Fourier . Na análise numérica , os sistemas circulantes podem ser resolvidos de forma muito eficiente pela transformada rápida de Fourier .

Às vezes falamos de uma matriz anticirculante ou circulante à esquerda quando executamos um deslocamento para a esquerda dos coeficientes ao passar de uma linha para a próxima.

Álgebra de matrizes circulantes

Para simplificar as notações, denotamos por C ( c 0 , ..., c n –1 ) a matriz circulante precedente.

Anotando

J = {\ begin {pmatrix} 0 & 1 & 0 & \ dots & 0 \\ 0 & 0 & 1 & \ dots & 0 \\\ vdots &&& \ ddots & \ vdots \\ 0 &&&& 1 \\ 1 & 0 & 0 & \ dots & 0 \ end {pmatrix}} = C (0,1, 0, ..., 0),

podemos ver que qualquer matriz circulante é um polinômio em J

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

Por outro lado, como J n é a matriz identidade , qualquer polinômio em J é uma matriz circulante.

Assim, a soma, o produto das matrizes circulantes estão circulando, e tal produto é comutativo. O conjunto de matrizes circulantes não é outro senão o álgebra conmutativo de polinómios em J .

Redução de matrizes circulantes

Diagonalização de J

A matriz J , verificando J n = I , é diagonalizável em ℂ com autovalores de n- ésimas raízes da unidade .

Chamamos, portanto , raiz primitiva da unidade. Podemos então verificar facilmente que para todos os k $\ omega = e ^ {{{\ frac {2i \ pi} {n}}}}$

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

é o autovetor de J associado ao autovalor $ω k$ .

Portanto afixados, para k de 0 a n - 1, uma família de n vectores próprios associados com próprios valores distintos, uma base limpo para J .

Diagonalização de uma matriz circulante

Conseqüentemente, é uma base adequada também para qualquer polinômio em J , ou seja, qualquer matriz circulante. Os autovalores de C ( c 0 , ..., c n –1 ) são, portanto, o

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

que, desta vez, não são mais necessariamente distintos.

Pode-se tomar, para matriz de passagem da base canônica para a própria base, a matriz

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

Esta matriz U é unitária ( U * U = I ) e as fórmulas das passagens anteriores são escritas, observando-se $Λ$ a matriz diagonal dos coeficientes e os autovalores

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

Verificação direta

Seja a matriz de Vandermonde , vamos verificar isso . ${\ 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 {alinhados} (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 {alinhado}}}

Uma nova definição possível para o conjunto de matrizes circulantes é o conjunto de matrizes da forma UDU * com D diagonal. Geometricamente, isso corresponde a endomorfismos que admitem a base ortonormal de X k como base de autovetores.

Determinante circulante

O determinante circulante é o determinante da matriz circulante; como para qualquer outra matriz, é igual ao produto dos autovalores

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

Qualquer matriz é invertível se e somente se seu determinante for diferente de zero, e no caso de uma matriz circulante sua matriz inversa também é uma matriz circulante.

Intervenção da transformada discreta de Fourier

De particular interesse são as fórmulas de mudança de base usando a matriz U. A fórmula para passar os coeficientes para os autovalores é a definição clássica de uma transformada discreta de Fourier . Podemos encontrar os coeficientes dos valores próprios realizando, desta vez, uma transformação inversa

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

Sistema circulante

Seja o sistema circulante Cx = b , com C matriz circulante de tamanho n . Este sistema pode ser reescrito usando um produto de convolução discreto

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

denotando c a primeira coluna da matriz C e periodizando os componentes dos vetores c , x e b . A transformada discreta de Fourier transforma essa equação convolucional em um produto componente por componente.

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

e entao

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

Esse algoritmo de resolução é muito mais rápido do que a eliminação de Gauss-Jordan , e ainda mais se recorrermos à transformada rápida de Fourier .

Veja também

Quadrado latino

links externos

(en) Eric W. Weisstein , “ Circulant Matrix ” , no MathWorld
(en) Eric W. Weisstein , “ Circulant Determinant ” , no MathWorld