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 .
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
o la transpuesta de esta forma (por elección de notación). Si cada una es una matriz cuadrada , entonces la matriz se llama matriz circulante en bloques .
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.
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 ).
El polinomio se llama polinomio asociado de la matriz .
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 -ésima primitiva de la unidad y es la unidad imaginaria .
(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
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
Rango
El rango de una matriz circulante es igual a donde está el grado del polinomio . [2]
Otras propiedades
- Cualquier circulante es un polinomio matricial (es decir, el polinomio asociado) en la matriz de permutación cíclica : donde está dado por la matriz complementaria
- 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 .
- Las matrices circulantes forman un álgebra conmutativa , ya que para dos matrices circulantes dadas y , la suma es circulante, el producto es circulante y .
- Para una matriz circulante no singular , su inversa también es circulante. Para una matriz circulante singular, su pseudoinversa de Moore-Penrose es circulante.
- 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: En consecuencia la matriz se diagonaliza . De hecho, tenemos 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 rápida transformada de Fourier . [3] Por el contrario, para cualquier matriz diagonal , el producto es circulante.
- 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 : (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 .
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
(recordemos que las secuencias son periódicas) que es el producto del vector por la matriz circulante para .
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
Matrices circulantes simétricas
Para una matriz circulante simétrica se tiene la condición adicional de que . Por tanto, está determinado por elementos.
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 dependiendo de si es par o impar.
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.
Si n es par, las dos primeras filas necesariamente toman la forma
en la que el primer elemento de la segunda mitad superior es real.
Si n es impar obtenemos
Tee [5] ha analizado las restricciones a los valores propios de la condición hermitiana.
Aplicaciones
En ecuaciones lineales
Dada una ecuación matricial
donde es una matriz circulante de tamaño , podemos escribir la ecuación como la convolución circular
donde está 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 discreta de Fourier para transformar la convolución cíclica en una multiplicación por componentes
de modo que
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
- ^ Davis, Philip J. , Matrices circulantes, Wiley, Nueva York, 1970 ISBN 0471057711
- ^ 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.
- ^ 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
- ^ 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
- ^ 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