En álgebra lineal , una matriz circulante es una matriz cuadrada en la que cada vector de fila gira un elemento hacia la derecha con respecto al vector de 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 discreta de Fourier y, por lo tanto, las ecuaciones lineales que las contienen pueden resolverse rápidamente utilizando una transformada rápida de Fourier . [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 espacialmente invariantes.
En criptografía , se utiliza una matriz circulante en el paso MixColumns del Estándar de cifrado avanzado .
Definición
Un matriz circulante toma la forma
o la transposición de esta forma (por elección de notación).
Una matriz circulante está completamente especificada por un vector, , que aparece como la primera columna (o fila) de . Las columnas restantes (y filas, respectivamente) deson cada una permutaciones cíclicas del vector con desplazamiento igual al índice de columna (o fila, respectivamente), si las líneas están indexadas de 0 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 por uno en reversa.
Diferentes fuentes definen la matriz circulante de diferentes maneras, por ejemplo, como 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 cambio diferente (que a veces se denomina matriz anticirculante ).
El polinomio se llama polinomio asociado de matriz.
Propiedades
Autovectores y autovalores
Los vectores propios normalizados de una matriz circulante son los modos de Fourier, a saber,
dónde es un primitivo -ésima raíz de la unidad yes la unidad imaginaria .
(Esto se puede entender al darse cuenta de que una matriz circulante implementa una convolución).
Los valores propios correspondientes vienen dados por
Determinante
Como consecuencia de la fórmula explícita para los valores propios anterior, el determinante de una matriz circulante se puede calcular como:
Dado que tomar la transposición no cambia los valores propios de una matriz, una formulación equivalente es
Rango
El rango de una matriz circulante es igual a , dónde es el grado del polinomio. [2]
Otras propiedades
- Cualquier circulante es un polinomio de matriz (es decir, el polinomio asociado) en la matriz de permutación cíclica :
- dónde es dado por
- El conjunto de matrices circulantes forman una - espacio vectorial dimensional con respecto a la suma y la multiplicación escalar. Este espacio se puede interpretar 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 .
- La matriz que se compone de los vectores propios de una matriz circulante se relaciona con la transformada discreta de Fourier y su transformada inversa:
- En consecuencia, la matriz diagonaliza. De hecho, tenemos
- dónde es la primera columna de . Los valores propios de son dados por el producto . Este producto se puede calcular fácilmente mediante una transformada rápida de Fourier . [3]
- Dejar ser el polinomio característico ( monic ) de un matriz circulante , y deja ser el derivado de. Entonces el polinomio es el polinomio característico de los siguientes 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 en los enteros con punto, (es decir, como secuencias periódicas bi-infinitas: ) o de manera equivalente, como funciones en el grupo cíclico de orden ( o ) geométricamente, en (los vértices de) el regular -gon : este es un análogo discreto a 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 para la función; esta es una circunvolución circular discreta . La fórmula para la convolución de las funciones. es
- (recuerda 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 de la matriz corresponde a la diagonalización.
La -álgebra de todas las matrices circulantes con entradas complejas es isomorfa al grupo-álgebra de .
Matrices circulantes simétricas
Para una matriz circulante simétrica uno tiene la condición adicional de que . Por lo tanto, está determinado por elementos.
Los valores propios de cualquier matriz simétrica real son reales. Los valores propios correspondientes se convierten en:
por incluso , y
por extraño , dondedenota la parte real de. Esto se puede simplificar aún más utilizando el hecho de que.
Matrices circulantes simétricas complejas
La versión compleja de la matriz circulante, omnipresente en la teoría de las comunicaciones, suele ser hermitiana . En este caso y su determinante y todos los valores propios son reales.
Si n es par, las dos primeras filas necesariamente toman la forma
en el que el primer elemento en la segunda mitad superior de la fila es real.
Si n es impar obtenemos
Tee [5] ha analizado las restricciones sobre los valores propios para la condición simétrica compleja.
Aplicaciones
En ecuaciones lineales
Dada una ecuación matricial
dónde es una matriz cuadrada circulante de tamaño podemos escribir la ecuación como la convolución circular
dónde es la primera columna de , y los vectores , y se extienden cíclicamente en cada dirección. Usando el teorema de la convolución circular , podemos usar la transformada discreta de Fourier para transformar la convolución cíclica en una multiplicación por componentes
así que eso
Este algoritmo es mucho más rápido que la eliminación gaussiana estándar , especialmente si se usa una transformada rápida de Fourier .
En teoría de grafos
En teoría de grafos , un gráfico o dígrafo cuya matriz de adyacencia es circulante se denomina gráfico circulante (o dígrafo). 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 principal .
Referencias
- ^ Davis, Philip J. , Matrices circulantes, Wiley, Nueva York, 1970 ISBN 0471057711
- ^ 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 .
- ^ Golub, Gene H .; Van Loan, Charles F. (1996), "§4.7.7 Circulant Systems", Matrix Computations (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
- ^ Tee, GJ (2007). "Vectores propios de bloques circulantes y matrices circulantes alternas". Revista de Matemáticas de Nueva Zelanda . 36 : 195–211.
enlaces externos
- RM Gray, Toeplitz y matrices circulantes: una revisión
- Weisstein, Eric W. "Matriz circulante" . MathWorld .
- IPython Notebook que demuestra las propiedades de las matrices circulantes