Matriu circulant

En àlgebra lineal, una matriu circulant és una matriu quadrada en la qual totes les files es componen dels mateixos elements i cada fila es gira un element cap a la dreta respecte a la fila anterior. És un tipus particular de matriu de Toeplitz.

En l'anàlisi numèrica, les matrius circulants són importants perquè estan diagonalitzades per una transformada de Fourier discreta i, per tant, les equacions lineals que les contenen es poden resoldre ràpidament utilitzant una transformada de Fourier ràpida. Es poden interpretar analíticament com el nucli integral d'un operador de convolució del grup cíclic $C_{n}$ i per tant apareixen freqüentment en descripcions formals d'operacions lineals espacialment invariants. Aquesta propietat també és fonamental en les ràdios definides per programari modernes, que utilitzen la multiplexació per divisió de freqüència ortogonal per difondre els símbols (bits) mitjançant un prefix cíclic. Això permet que el canal sigui representat per una matriu circulant, simplificant l'equalització del canal en el domini de la freqüència.

En criptografia, s'utilitza una matriu circulant al pas MixColumns de l'estàndard de xifratge avançat.

Definició

An $n\times n$ matriu circulant $C$ pren la forma$$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}}$$o la transposició d'aquesta forma (per opció de notació). Si cadascú $c_{i}$ és un $p\times p$ matriu quadrada, llavors la $np\times np$ matriu $C$ s'anomena matriu bloc-circulant.

Una matriu circulant està totalment especificada per un vector, $c$, que apareix com a primera columna (o fila) de $C$. La resta de columnes (i files, respectivament) de $C$ són cadascuna permutació cíclica del vector $c$ amb un desplaçament igual a l'índex de columna (o fila, respectivament), si les línies s'indexen des de $0$ a $n-1$. (La permutació cíclica de files té el mateix efecte que la permutació cíclica de columnes.) L'última fila de $C$ és el vector $c$ desplaçat d'un al revés.

Diferents fonts defineixen la matriu circulant de diferents maneres, per exemple com l'anterior, o amb el vector $c$ corresponent a la primera fila en lloc de la primera columna de la matriu; i possiblement amb una direcció de desplaçament diferent (que de vegades s'anomena matriu anti-circulant).

El polinomi $f(x)=c_{0}+c_{1}x+\dots +c_{n-1}x^{n-1}$ s'anomena polinomi associat de la matriu $C$.

Aplicacions

En equacions lineals

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

on $C$ és una matriu circulant de mida $n$, podem escriure l'equació com la circumvolució circular$$\mathbf {c} \star \mathbf {x} =\mathbf {b} ,$$on $\mathbf {c}$ és la primera columna de $C$, i els vectors $\mathbf {c}$, $\mathbf {x}$ i $\mathbf {b}$ s'estenen cíclicament en cada sentit. Utilitzant el teorema de la convolució circular, podem utilitzar la transformada discreta de Fourier per transformar la convolució cíclica en una multiplicació per components.

$${\mathcal {F}}_{n}(\mathbf {c} \star \mathbf {x} )={\mathcal {F}}_{n}(\mathbf {c} ){\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )$$de manera que$$\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}}.$$Aquest algorisme és molt més ràpid que l'eliminació de Gauss estàndard, especialment si s'utilitza una transformada de Fourier ràpida.

En teoria de grafs

En teoria de grafs, un graf o dígraf la matriu d'adjacència del qual és circulant s'anomena graf/dígraf circulant. De manera equivalent, un gràfic és circulant si el seu grup d'automorfismes conté un cicle de longitud completa. Les escales de Möbius són exemples de gràfics circulants, com ho són els gràfics de Paley per a camps d'ordre primer.