matriz circulante

Matriz de álgebra lineal

En álgebra lineal , una matriz circulante es una matriz cuadrada en la que todas las filas están compuestas por los mismos elementos y cada fila gira un elemento hacia la derecha con respecto a la fila anterior. Es un tipo particular de matriz de Toeplitz .

En el análisis numérico , las matrices circulantes son importantes porque están diagonalizadas mediante una transformada de Fourier discreta y, por lo tanto, las ecuaciones lineales que las contienen pueden resolverse rápidamente utilizando una transformada rápida de Fourier . ^[1] Pueden interpretarse analíticamente como el núcleo integral de un operador de convolución en el grupo cíclico y, por lo tanto, aparecen con frecuencia en descripciones formales de operaciones lineales espacialmente invariantes. Esta propiedad también es fundamental en las radios modernas definidas por software, que utilizan multiplexación por división de frecuencia ortogonal para difundir los símbolos (bits) utilizando un prefijo cíclico . Esto permite representar el canal mediante una matriz circulante, simplificando la ecualización del canal en el dominio de la frecuencia . ${\displaystyle C_{n}}$

En criptografía , se utiliza una matriz circulante en el paso MixColumns del Estándar de cifrado avanzado .

Definición

Una matriz circulante toma la forma ${\displaystyle n\times n}$ ${\displaystyle C}$

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

transposiciónmatrizmatriz circulante en bloques ${\displaystyle c_{i}}$ ${\displaystyle p\times p}$ ${\displaystyle np\times np}$ ${\displaystyle C}$

Una matriz circulante está completamente especificada por un vector, que aparece como la primera columna (o fila) de . Las columnas (y filas, respectivamente) restantes de son permutaciones cíclicas del vector con un desplazamiento igual al índice de la columna (o fila, respectivamente), si las líneas están indexadas de a . (La permutación cíclica de filas tiene el mismo efecto que la permutación cíclica de columnas). La última fila es el vector desplazado en uno a la inversa. ${\displaystyle c}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle c}$ ${\displaystyle 0}$ ${\displaystyle n-1}$ ${\displaystyle C}$ ${\displaystyle c}$

Diferentes fuentes definen la matriz circulante de diferentes maneras, por ejemplo como se indicó anteriormente, o con el vector correspondiente a la primera fila en lugar de a la primera columna de la matriz; y posiblemente con una dirección de desplazamiento diferente (lo que a veces se denomina matriz anticirculante ). ${\displaystyle c}$

El polinomio se llama polinomio asociado de la matriz . ${\displaystyle f(x)=c_{0}+c_{1}x+\dots +c_{n-1}x^{n-1}}$ ${\displaystyle C}$

Propiedades

Vectores propios y valores propios

Los vectores propios normalizados de una matriz circulante son los modos de Fourier, es decir,

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

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

(Esto puede entenderse al darse cuenta de que la multiplicación con una matriz circulante implementa una convolución. En el espacio de Fourier, las convoluciones se convierten en multiplicación. Por lo tanto, el producto de una matriz circulante con un modo de Fourier produce un múltiplo de ese modo de Fourier, es decir, es un vector propio. )

Los valores propios correspondientes están dados por

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

Determinante

Como consecuencia de la fórmula explícita para los valores propios anteriores, el determinante de una matriz circulante se puede calcular como:

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

Rango

El rango de una matriz circulante es igual a donde está el grado del polinomio . ^[2] ${\displaystyle C}$ ${\displaystyle n-d}$ ${\displaystyle d}$ ${\displaystyle \gcd(f(x),x^{n}-1)}$

Otras propiedades

• Cualquier circulante es un polinomio matricial (es decir, el polinomio asociado) en la matriz de permutación cíclica : ${\displaystyle P}$
  $${\displaystyle C=c_{0}I+c_{1}P+c_{2}P^{2}+\dots +c_{n-1}P^{n-1}=f(P),}$$
  donde está dado por la matriz complementaria ${\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}}.}$$
• El conjunto de matrices circulantes forma un espacio vectorial dimensional con respecto a la suma y la multiplicación escalar. Este espacio puede interpretarse como el espacio de funciones en el grupo cíclico de orden , o equivalentemente como el anillo de grupo de . ${\displaystyle n\times n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle C_{n}}$ ${\displaystyle C_{n}}$
• Las matrices circulantes forman un álgebra conmutativa , ya que para dos matrices circulantes dadas y , la suma es circulante, el producto es circulante y . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A+B}$ ${\displaystyle AB}$ ${\displaystyle AB=BA}$
• Para una matriz circulante no singular , su inversa también es circulante. Para una matriz circulante singular, su pseudoinversa de Moore-Penrose es circulante. ${\displaystyle A}$ ${\displaystyle A^{-1}}$ ${\displaystyle A^{+}}$
• La matriz que está compuesta por los vectores propios de una matriz circulante está relacionada con la transformada discreta de Fourier y su transformada inversa: ${\displaystyle U}$
  $${\displaystyle U_{n}^{*}={\frac {1}{\sqrt {n}}}F_{n},\quad {\text{and}}\quad U_{n}={\sqrt {n}}F_{n}^{-1},{\text{ where }}F_{n}=(f_{jk}){\text{ with }}f_{jk}=e^{-2jk\pi i/n},\,{\text{for }}0\leq j,k<n.}$$
  En consecuencia la matriz se diagonaliza . De hecho, tenemos ${\displaystyle U_{n}}$ ${\displaystyle C}$
  $${\displaystyle C=U_{n}\operatorname {diag} (F_{n}c)U_{n}^{*}=F_{n}^{-1}\operatorname {diag} (F_{n}c)F_{n},}$$
  ¿Dónde está la primera columna de ? Los valores propios de están dados por el producto . Este producto se puede calcular fácilmente mediante una transformada rápida de Fourier . ^[3] Por el contrario, para cualquier matriz diagonal , el producto es circulante. ${\displaystyle c}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle F_{n}c}$ ${\displaystyle D}$ ${\displaystyle F_{n}^{-1}DF_{n}}$
• Sea el polinomio característico ( mónico ) de una matriz circulante . Entonces la derivada escalada es el polinomio característico de la siguiente submatriz de : ${\displaystyle p(x)}$ ${\displaystyle n\times n}$ ${\displaystyle C}$ ${\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}}}$$
  (ver ^[4] para la prueba ).

Interpretación analítica

Las matrices circulantes se pueden interpretar geométricamente , lo que explica la conexión con la transformada discreta de Fourier.

Considere los vectores en como funciones sobre los números enteros con período , (es decir, como secuencias bi-infinitas periódicas: ) o de manera equivalente, como funciones sobre el grupo cíclico de orden (denotado o ) geométricamente, sobre (los vértices de) el -gón regular : este es un análogo discreto de las funciones periódicas en la línea o círculo real . ${\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}$

Entonces, desde la perspectiva de la teoría del operador , una matriz circulante es el núcleo de una transformada integral discreta , es decir, el operador de convolución de la función ; esta es una convolución circular discreta . La fórmula para la convolución de las funciones es ${\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}}$

(recordemos que las secuencias son periódicas) que es el producto del vector por la matriz circulante para . ${\displaystyle (a_{i})}$ ${\displaystyle (c_{i})}$

La transformada discreta de Fourier luego convierte la convolución en multiplicación, que en la configuración matricial corresponde a la diagonalización.

El álgebra de todas las matrices circulantes con entradas complejas es isomorfa al álgebra de grupo de ${\displaystyle C^{*}}$ ${\displaystyle C^{*}}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} .}$

Matrices circulantes simétricas

Para una matriz circulante simétrica se tiene la condición adicional de que . Por tanto, está determinado por elementos. ${\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}}.}$$

Los valores propios de cualquier matriz simétrica real son reales. Los valores propios correspondientes se convierten en:

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

par ${\displaystyle n}$

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

imparparte real ${\displaystyle n}$ ${\displaystyle \Re z}$ ${\displaystyle z}$ ${\displaystyle \Re \omega _{j}^{k}=\cos(2\pi jk/n)}$ ${\displaystyle \omega _{j}^{n/2}=\exp \left({\pi ij}\right)=\pm 1}$ ${\displaystyle j}$

Las matrices circulantes simétricas pertenecen a la clase de matrices bisimétricas .

Matrices circulantes hermitianas

La versión compleja de la matriz circulante, omnipresente en la teoría de las comunicaciones, suele ser hermitiana . En este caso , su determinante y todos los valores propios son reales. ${\displaystyle c_{n-i}=c_{i}^{*},\;i\leq n/2}$

Si n es par, las dos primeras filas necesariamente toman la forma

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

Si n es impar obtenemos

$${\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 ^[5] ha analizado las restricciones a los valores propios de la condición hermitiana.

Aplicaciones

En ecuaciones lineales

Dada una ecuación matricial

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

donde hay una matriz circulante de tamaño , podemos escribir la ecuación como la convolución circular ${\displaystyle C}$ ${\displaystyle n}$

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

teorema de convolución circulartransformada discreta de Fourier ${\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}}.}$$

Este algoritmo es mucho más rápido que la eliminación gaussiana estándar , especialmente si se utiliza una transformada rápida de Fourier .

En teoría de grafos

En teoría de grafos , un grafo o dígrafo cuya matriz de adyacencia es circulante se denomina grafo /dígrafo circulante . De manera equivalente, un gráfico circula si su grupo de automorfismo contiene un ciclo completo. Las escaleras de Möbius son ejemplos de gráficos circulantes, al igual que los gráficos de Paley para campos de orden primo .

Referencias

1. Davis, Philip J. , Matrices circulantes, Wiley, Nueva York, 1970 ISBN  0471057711
2. AW Ingleton (1956). "El rango de las matrices circulantes". J. Matemáticas de Londres. Soc . T1-31 (4): 445–460. doi :10.1112/jlms/s1-31.4.445.
3. Golub, gen H .; Van Loan, Charles F. (1996), "§4.7.7 Sistemas circulantes", Computaciones matriciales (3.ª ed.), Johns Hopkins, ISBN 978-0-8018-5414-9
4. Kushel, Olga; Tyaglov, Mikhail (15 de julio de 2016), "Circulantes y puntos críticos de polinomios", Journal of Mathematical Analysis and Applications , 439 (2): 634–650, arXiv : 1512.07983 , doi :10.1016/j.jmaa.2016.03.005 , ISSN  0022-247X
5. Camiseta, GJ (2007). "Vectores propios de matrices circulantes en bloque y circulantes alternas". Revista de Matemáticas de Nueva Zelanda . 36 : 195-211.

enlaces externos

• RM Gray, Toeplitz y matrices circulantes: una revisión doi :10.1561/0100000006
• Cuaderno IPython que demuestra las propiedades de las matrices circulantes