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 está rotada 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 por una transformada de Fourier discreta y, por lo tanto, las ecuaciones lineales que las contienen pueden resolverse rápidamente utilizando una transformada de Fourier rápida . ^[1] Se pueden interpretar 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 invariantes espacialmente. Esta propiedad también es fundamental en las radios definidas por software modernas, que utilizan multiplexación por división de frecuencia ortogonal para difundir los símbolos (bits) utilizando un prefijo cíclico . Esto permite que el canal se represente mediante una matriz circulante, lo que simplifica 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 adopta la forma o la transpuesta de esta forma (según la notación elegida). Si cada una es una matriz cuadrada , entonces la matriz se denomina matriz circulante en bloques . ${\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}}}$$ ${\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 restantes (y filas, respectivamente) de son cada una 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 de es el vector desplazado en uno en sentido inverso. ${\displaystyle c}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle c}$ ${\displaystyle 0}$ ${\displaystyle n-1}$ ${\displaystyle C}$ ${\displaystyle c}$

Distintas fuentes definen la matriz circulante de distintas maneras, por ejemplo como se indica más arriba, 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, donde es una raíz primitiva de la unidad y es la unidad imaginaria . $${\displaystyle v_{j}={\frac {1}{\sqrt {n}}}\left(1,\omega ^{j},\omega ^{2j},\ldots ,\omega ^{(n-1)j}\right)^{T},\quad j=0,1,\ldots ,n-1,}$$ ${\displaystyle \omega =\exp \left({\tfrac {2\pi i}{n}}\right)}$ ${\displaystyle n}$ ${\displaystyle i}$

(Esto se puede entender al comprender 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 da como resultado un múltiplo de ese modo de Fourier, es decir, es un vector propio).

Los valores propios correspondientes se dan 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: Dado que tomar la transpuesta no cambia los valores propios de una matriz, una formulación equivalente es $${\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 es 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 : donde viene dada por la matriz compañera ${\displaystyle P}$ $${\displaystyle C=c_{0}I+c_{1}P+c_{2}P^{2}+\dots +c_{n-1}P^{n-1}=f(P),}$$ ${\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 de dimensión - respecto de la adición y la multiplicación escalar. Este espacio puede interpretarse como el espacio de funciones del grupo cíclico de orden , o equivalentemente como el anillo de grupos 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 de transformada de Fourier discreta de orden se define como ${\displaystyle n}$

$${\displaystyle F_{n}=(f_{jk}){\text{ with }}f_{jk}=e^{-2\pi i/n\cdot jk},\,{\text{for }}0\leq j,k\leq n-1.}$$Existen conexiones importantes entre las matrices circulantes y las matrices DFT. De hecho, se puede demostrar que donde es 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] $${\displaystyle C=F_{n}^{-1}\operatorname {diag} (F_{n}c)F_{n},}$$ ${\displaystyle c}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle F_{n}c}$

• 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 : (véase ^[4] para la prueba ). ${\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}}}$$

Interpretación analítica

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

Consideremos los vectores como funciones de los números enteros con período , (es decir, como secuencias periódicas bi-infinitas: ) o, equivalentemente, como funciones del grupo cíclico de orden (denotado o ) geométricamente, en (los vértices del) -gono regular : este es un análogo discreto de las funciones periódicas en la línea real o el círculo . ${\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 de operadores , una matriz circulante es el núcleo de una transformada integral discreta , es decir, el operador de convolución para 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 sucesiones son periódicas) que es el producto del vector por la matriz circulante para . ${\displaystyle (a_{i})}$ ${\displaystyle (c_{i})}$

Luego, la transformada de Fourier discreta convierte la convolución en multiplicación, lo que en el entorno 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 lo tanto, está determinada 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: para par , y para impar , donde denota la parte real de . Esto se puede simplificar aún más utilizando el hecho de que y dependen de si es par o impar. ${\displaystyle {\vec {\lambda }}={\sqrt {n}}\cdot F_{n}^{\dagger }c}$ $${\displaystyle {\begin{array}{lcl}\lambda _{k}&=&c_{0}+c_{n/2}e^{-\pi i\cdot k}+2\sum _{j=1}^{{\frac {n}{2}}-1}c_{j}\cos {(-{\frac {2\pi }{n}}\cdot kj)}\\&=&c_{0}+c_{n/2}\omega _{k}^{n/2}+2c_{1}\Re \omega _{k}+2c_{2}\Re \omega _{k}^{2}+\dots +2c_{n/2-1}\Re \omega _{k}^{n/2-1}\end{array}}}$$ ${\displaystyle n}$ $${\displaystyle {\begin{array}{lcl}\lambda _{k}&=&c_{0}+2\sum _{j=1}^{\frac {n-1}{2}}c_{j}\cos {(-{\frac {2\pi }{n}}\cdot kj)}\\&=&c_{0}+2c_{1}\Re \omega _{k}+2c_{2}\Re \omega _{k}^{2}+\dots +2c_{(n-1)/2}\Re \omega _{k}^{(n-1)/2}\end{array}}}$$ ${\displaystyle n}$ ${\displaystyle \Re z}$ ${\displaystyle z}$ ${\displaystyle \Re \omega _{k}^{j}=\Re e^{-{\frac {2\pi i}{n}}\cdot kj}=\cos(-{\frac {2\pi }{n}}\cdot kj)}$ ${\displaystyle \omega _{k}^{n/2}=e^{-{\frac {2\pi i}{n}}\cdot k{\frac {n}{2}}}=e^{-\pi i\cdot k}}$ ${\displaystyle k}$

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

Matrices circulantes hermíticas

La versión compleja de la matriz circulante, omnipresente en la teoría de las comunicaciones, suele ser hermítica . En este caso , tanto su determinante como 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 en la que el primer elemento de la segunda mitad de la fila superior es real. $${\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 de los valores propios para la condición hermítica.

Aplicaciones

En ecuaciones lineales

Dada una ecuación matricial

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

donde es una matriz circulante de tamaño , podemos escribir la ecuación como la convolución circular donde es la primera columna de , y los vectores , y se extienden cíclicamente en cada dirección. Usando el teorema de convolución circular , podemos usar la transformada de Fourier discreta para transformar la convolución cíclica en una multiplicación por componentes de modo que ${\displaystyle C}$ ${\displaystyle n}$ $${\displaystyle \mathbf {c} \star \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}}.}$$

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 grafo es circulante si su grupo de automorfismos contiene un ciclo de longitud completa. Las escaleras de Möbius son ejemplos de grafos circulantes, al igual que los grafos de Paley para cuerpos de orden primo .

Referencias

1. Davis, Philip J (1970). Matrices Circulantes . Nueva York: Wiley. ISBN 0-471-05771-1.OCLC 1408988930  .
2. AW Ingleton (1956). "El rango de las matrices circulantes". J. London Math. Soc . s1-31 (4): 445–460. doi :10.1112/jlms/s1-31.4.445.
3. Golub, Gene H. ; Van Loan, Charles F. (1996), "§4.7.7 Sistemas circulantes", Cálculos 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. Tee, GJ (2007). "Vectores propios de matrices circulantes en bloque y circulantes alternas" (PDF) . New Zealand Journal of Mathematics . 36 : 195–211.

Enlaces externos

• Gray, RM (2006). Toeplitz y matrices circulantes: una revisión (PDF) . Ahora. doi :10.1561/0100000006. ISBN 978-1-933019-68-0– a través de la Universidad de Stanford.
• Cuaderno de notas de IPython que muestra las propiedades de las matrices circulantes