Hispanopedia Wiki
Articulo de referencia

Matriz circulante

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 a la der...

Hispanopedia WikiContenido en espanolLectura gratuita

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 a la derecha con respecto a la fila anterior. Es un tipo particular de matriz de Toeplitz .

En análisis numérico , las matrices circulantes son importantes porque se diagonalizan mediante 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 ] Pueden interpretarse analíticamente como el núcleo integral de un operador de convolución en el grupo cíclico.donorte{\displaystyle C_{n}}y, por lo tanto, aparecen frecuentemente en descripciones formales de operaciones lineales espacialmente invariantes. Esta propiedad también es fundamental en las radios definidas por software modernas, que utilizan multiplexación por división de frecuencia ortogonal para distribuir los símbolos (bits) mediante 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 (AEST) .

Definición

Unnorte×norte{\displaystyle n\times n}matriz circulantedo{\displaystyle C}toma la forma do=[do0donorte−1⋯do2do1do1do0donorte−1do2⋮do1do0⋱⋮donorte−2⋱⋱donorte−1donorte−1donorte−2⋯do1do0]{\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}}} o la transpuesta de esta forma (por elección de notación). Si cadadoi{\displaystyle c_{i}}es unpag×pag{\displaystyle p\times p}matriz cuadrada , entonces lanortepag×nortepag{\displaystyle np\times np}matrizdo{\displaystyle C}se denomina matriz circulante por bloques .

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

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

El polinomioF(incógnita)=do0+do1incógnita+⋯+donorte−1incógnitanorte−1{\displaystyle f(x)=c_{0}+c_{1}x+\dots +c_{n-1}x^{n-1}}se denomina polinomio asociado de la matrizdo{\displaystyle C}.

Propiedades

Vectores propios y valores propios

Los autovectores normalizados de una matriz circulante son los modos de Fourier, a saber: vj=1norte(1,ωj,ω2j,…,ω(norte−1)j)T,j=0,1,…,norte−1,{\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,} dóndeω=exp⁡(2πinorte){\displaystyle \omega =\exp \left({\tfrac {2\pi i}{n}}\right)}es un primitivonorte{\displaystyle n}-raíz enésima de la unidad yi{\displaystyle i}es la unidad imaginaria .

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

Los autovalores correspondientes vienen dados por λj=do0+do1ω−j+do2ω−2j+⋯+donorte−1ω−(norte−1)j,j=0,1,…,norte−1.{\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 anterior, el determinante de una matriz circulante se puede calcular como: detdo=∏j=0norte−1(do0+donorte−1ωj+donorte−2ω2j+⋯+do1ω(norte−1)j).{\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}).} Dado que tomar la transpuesta no cambia los valores propios de una matriz, una formulación equivalente es detdo=∏j=0norte−1(do0+do1ωj+do2ω2j+⋯+donorte−1ω(norte−1)j)=∏j=0norte−1F(ω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 circulantedo{\displaystyle C}es igual anorte−d{\displaystyle n-d}dónded{\displaystyle d}es el grado del polinomiomcd(F(incógnita),incógnitanorte−1){\displaystyle \gcd(f(x),x^{n}-1)}. [ 2 ]

Otras propiedades

  • Cualquier circulante es un polinomio matricial (es decir, el polinomio asociado) en la matriz de permutación cíclica.PAG{\displaystyle P}:do=do0I+do1PAG+do2PAG2+⋯+donorte−1PAGnorte−1=F(PAG),{\displaystyle C=c_{0}I+c_{1}P+c_{2}P^{2}+\dots +c_{n-1}P^{n-1}=f(P),}dóndePAG{\displaystyle P}viene dada por la matriz compañeraPAG=[00⋯0110⋯000⋱⋱⋮⋮⋮⋱⋱000⋯010].{\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 denorte×norte{\displaystyle n\times n}Las matrices circulantes forman unanorte{\displaystyle n}- 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 ordennorte{\displaystyle n},donorte{\displaystyle C_{n}}, o equivalentemente como el anillo de grupo dedonorte{\displaystyle C_{n}}.
  • Las matrices circulantes forman un álgebra conmutativa , ya que para cualesquiera dos matrices circulantes dadasA{\displaystyle A}yB{\displaystyle B}, la sumaA+B{\displaystyle A+B}es circulante, el productoAB{\displaystyle AB}es circulante yAB=BA{\displaystyle AB=BA}.
  • Para una matriz circulante no singularA{\displaystyle A}, su inversoA−1{\displaystyle A^{-1}}También es circulante. Para una matriz circulante singular, su pseudoinversa de Moore-PenroseA+{\displaystyle A^{+}}es circulante.
  • La matriz de transformada discreta de Fourier de ordennorte{\displaystyle n}se define como por

Fnorte=(Fjk) con Fjk=mi−2πi/norte⋅jk,para 0≤j,k≤norte−1.{\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 do=Fnorte−1diagnóstico⁡(Fnortedo)Fnorte,{\displaystyle C=F_{n}^{-1}\operatorname {diag} (F_{n}c)F_{n},}dóndedo{\displaystyle c}es la primera columna dedo{\displaystyle C}. Los valores propios dedo{\displaystyle C}son proporcionados por el productoFnortedo{\displaystyle F_{n}c}Este producto se puede calcular fácilmente mediante una transformada rápida de Fourier . [ 3 ]

  • Dejarpag(incógnita){\displaystyle p(x)}sea ​​el polinomio característico ( mónico ) de unnorte×norte{\displaystyle n\times n}matriz circulantedo{\displaystyle C}Luego, la derivada escalada.1nortepag′(incógnita){\textstyle {\frac {1}{n}}p'(x)}es el polinomio característico de lo siguiente(norte−1)×(norte−1){\displaystyle (n-1)\times (n-1)}submatriz dedo{\displaystyle C}:donorte−1=[do0donorte−1⋯do3do2do1do0donorte−1do3⋮do1do0⋱⋮donorte−3⋱⋱donorte−1donorte−2donorte−3⋯do1do0]{\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}}}(véase [ 4 ] para la demostración ).

Interpretación analítica

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

Consideremos vectores enRnorte{\displaystyle \mathbb {R} ^{n}}como funciones sobre los enteros con períodonorte{\displaystyle n}, (es decir, como secuencias bi-infinitas periódicas:…,a0,a1,…,anorte−1,a0,a1,…{\displaystyle \dots ,a_{0},a_{1},\dots ,a_{n-1},a_{0},a_{1},\dots }) o, equivalentemente, como funciones en el grupo cíclico de ordennorte{\displaystyle n}(denotadodonorte{\displaystyle C_{n}}oZ/norteZ{\displaystyle \mathbb {Z} /n\mathbb {Z} }) geométricamente, en (los vértices de) la regularnorte{\displaystyle n}-gon : este es un análogo discreto de las funciones periódicas en la recta real o el círculo .

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(do0,do1,…,donorte−1){\displaystyle (c_{0},c_{1},\dots ,c_{n-1})}; esta es una convolución circular discreta . La fórmula para la convolución de las funciones(bi):=(doi)∗(ai){\displaystyle (b_{i}):=(c_{i})*(a_{i})}es

bk=∑i=0norte−1aidok−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(ai){\displaystyle (a_{i})}por la matriz circulante para(doi){\displaystyle (c_{i})}.

La transformada discreta de Fourier convierte entonces la convolución en multiplicación, que en el contexto matricial corresponde a la diagonalización.

Eldo∗{\displaystyle C^{*}}-álgebra de todas las matrices circulantes con entradas complejas es isomorfa al grupodo∗{\displaystyle C^{*}}-álgebra deZ/norteZ.{\displaystyle \mathbb {Z} /n\mathbb {Z} .}

Relación con los procesos estacionarios

En estadística y procesamiento de señales , las matrices circulantes surgen naturalmente como matrices de covarianza de procesos estacionarios en sentido amplio observados en una matriz circular o con condiciones de contorno periódicas. De manera más general, la matriz de covarianza de un proceso estacionario en una matriz lineal es Toeplitz , y las matrices de Toeplitz son asintóticamente circulantes a medida que aumenta la dimensión. [ 5 ] Esta equivalencia asintótica es la razón por la que el análisis espectral basado en la DFT es asintóticamente óptimo para procesos estacionarios: la DFT diagonaliza las matrices circulantes de forma exacta y diagonaliza aproximadamente las matrices de Toeplitz, por lo que los coeficientes de la DFT son asintóticamente no correlacionados para datos estacionarios.

Matrices circulantes simétricas

Para una matriz circulante simétricado{\displaystyle C}uno tiene la condición adicional de quedonorte−i=doi{\displaystyle c_{n-i}=c_{i}}Por lo tanto, está determinado por⌊norte/2⌋+1{\displaystyle \lfloor n/2\rfloor +1}elementos. do=[do0do1⋯do2do1do1do0do1do2⋮do1do0⋱⋮do2⋱⋱do1do1do2⋯do1do0].{\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λ→=norte⋅Fnorte†do{\displaystyle {\vec {\lambda }}={\sqrt {n}}\cdot F_{n}^{\dagger }c}convertirse en: λk=do0+donorte/2mi−πi⋅k+2∑j=1norte2−1dojporque⁡(−2πnorte⋅kj)=do0+donorte/2ωknorte/2+2do1ℜωk+2do2ℜωk2+⋯+2donorte/2−1ℜωknorte/2−1{\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}}} paranorte{\displaystyle n}incluso , y λk=do0+2∑j=1norte−12dojporque⁡(−2πnorte⋅kj)=do0+2do1ℜωk+2do2ℜωk2+⋯+2do(norte−1)/2ℜωk(norte−1)/2{\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}}} paranorte{\displaystyle n}extraño , dondeℜz{\displaystyle \Re z}denota la parte real dez{\displaystyle z}Esto se puede simplificar aún más utilizando el hecho de queℜωkj=ℜmi−2πinorte⋅kj=porque⁡(−2πnorte⋅kj){\displaystyle \Re \omega _{k}^{j}=\Re e^{-{\frac {2\pi i}{n}}\cdot kj}=\cos(-{\frac {2\pi }{n}}\cdot kj)}yωknorte/2=mi−2πinorte⋅knorte2=mi−πi⋅k{\displaystyle \omega _{k}^{n/2}=e^{-{\frac {2\pi i}{n}}\cdot k{\frac {n}{2}}}=e^{-\pi i\cdot k}}Dependiendo dek{\displaystyle k}par o impar.

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 hermitiana . En este casodonorte−i=doi∗,i≤norte/2{\displaystyle c_{n-i}=c_{i}^{*},\;i\leq n/2}y su determinante y todos sus valores propios son reales.

Si n es par, las dos primeras filas necesariamente toman la forma [r0z1z2r3z2∗z1∗z1∗r0z1z2r3z2∗…].{\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}}.} en el que el primer elementor3{\displaystyle r_{3}}En la parte superior de la segunda mitad de la fila es real.

Si n es impar, obtenemos [r0z1z2z2∗z1∗z1∗r0z1z2z2∗…].{\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 [ 6 ] ha analizado las restricciones sobre los valores propios para la condición hermitiana.

Aplicaciones

En ecuaciones lineales

Dada una ecuación matricial

doincógnita=b,{\displaystyle C\mathbf {x} =\mathbf {b} ,}

dóndedo{\displaystyle C}es una matriz circulante de tamañonorte{\displaystyle n}, podemos escribir la ecuación como una convolución circulardo⋆incógnita=b,{\displaystyle \mathbf {c} \star \mathbf {x} =\mathbf {b} ,} dóndedo{\displaystyle \mathbf {c} }es la primera columna dedo{\displaystyle C}y los vectoresdo{\displaystyle \mathbf {c} },incógnita{\displaystyle \mathbf {x} }yb{\displaystyle \mathbf {b} }se extienden cíclicamente en cada dirección. Utilizando el teorema de convolución circular , podemos usar la transformada discreta de Fourier para transformar la convolución cíclica en una multiplicación componente a componente. Fnorte(do⋆incógnita)=Fnorte(do)Fnorte(incógnita)=Fnorte(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} )} de modo que incógnita=Fnorte−1[((Fnorte(b))ν(Fnorte(do))ν)ν∈Z]T.{\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 digrafo cuya matriz de adyacencia es circulante se denomina grafo /digrafo circulante . De forma equivalente, un grafo es circulante si su grupo de automorfismos contiene un ciclo completo. 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-1OCLC 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", Computación matricial (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. ↑ Grenander, Ulf; Szegő, Gábor (1958). Formas de Toeplitz y sus aplicaciones . Berkeley, CA: University of California Press.
  6. ↑ Tee, GJ (2007). "Autovectores de matrices circulantes por bloques y alternantes" (PDF) . New Zealand Journal of Mathematics . 36 : 195–211 .
  • Gray, RM (2006). "Matrices circulantes y de Toeplitz: una revisión" (PDF) . Foundations and Trends in Communications and Information Theory . 2 (3): 155– 239. doi : 10.1561/0100000006 .
  • Cuaderno IPython que demuestra las propiedades de las matrices circulantes.