matriz de toeplitz

Matriz con filas cambiantes

En álgebra lineal , una matriz de Toeplitz o matriz diagonal constante , llamada así en honor a Otto Toeplitz , es una matriz en la que cada diagonal descendente de izquierda a derecha es constante. Por ejemplo, la siguiente matriz es una matriz de Toeplitz:

${\displaystyle \qquad {\begin{bmatrix}a&b&c&d&e\\f&a&b&c&d\\g&f&a&b&c\\h&g&f&a&b\\i&h&g&f&a\end{bmatrix}}.}$

Cualquier matriz de la forma ${\displaystyle n\times n}$ ${\displaystyle A}$

${\displaystyle A={\begin{bmatrix}a_{0}&a_{-1}&a_{-2}&\cdots &\cdots &a_{-(n-1)}\\a_{1}&a_{0}&a_{-1}&\ddots &&\vdots \\a_{2}&a_{1}&\ddots &\ddots &\ddots &\vdots \\\vdots &\ddots &\ddots &\ddots &a_{-1}&a_{-2}\\\vdots &&\ddots &a_{1}&a_{0}&a_{-1}\\a_{n-1}&\cdots &\cdots &a_{2}&a_{1}&a_{0}\end{bmatrix}}}$

es una matriz de Toeplitz . Si se denota el elemento de entonces tenemos ${\displaystyle i,j}$ ${\displaystyle A}$ ${\displaystyle A_{i,j}}$

${\displaystyle A_{i,j}=A_{i+1,j+1}=a_{i-j}.}$

Una matriz de Toeplitz no es necesariamente cuadrada .

Resolver un sistema Toeplitz

Una ecuación matricial de la forma

${\displaystyle Ax=b}$

Se llama sistema de Toeplitz si es una matriz de Toeplitz. Si es una matriz de Toeplitz, entonces el sistema tiene como máximo sólo valores únicos, en lugar de . Por lo tanto, podríamos esperar que la solución de un sistema Toeplitz fuera más fácil, y de hecho así es. ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle n\times n}$ ${\displaystyle 2n-1}$ ${\displaystyle n^{2}}$

Los sistemas de Toeplitz se pueden resolver mediante algoritmos como el algoritmo de Schur o el algoritmo de Levinson en el tiempo. ^{[1] [2]} Se ha demostrado que las variantes de este último son débilmente estables (es decir, exhiben estabilidad numérica para sistemas lineales bien condicionados ). ^[3] Los algoritmos también se pueden utilizar para encontrar el determinante de una matriz de Toeplitz en el tiempo. ^[4] ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{2})}$

Una matriz de Toeplitz también se puede descomponer (es decir, factorizar) en el tiempo . ^[5] El algoritmo de Bareiss para una descomposición LU es estable. ^[6] Una descomposición LU proporciona un método rápido para resolver un sistema de Toeplitz y también para calcular el determinante. ${\displaystyle O(n^{2})}$

Propiedades generales

• Una matriz de Toeplitz se puede definir como una matriz donde , para constantes . El conjunto de matrices de Toeplitz es un subespacio del espacio vectorial de matrices (bajo suma de matrices y multiplicación escalar). ${\displaystyle n\times n}$ ${\displaystyle A}$ ${\displaystyle A_{i,j}=c_{i-j}}$ ${\displaystyle c_{1-n},\ldots ,c_{n-1}}$ ${\displaystyle n\times n}$ ${\displaystyle n\times n}$
• Se pueden sumar dos matrices de Toeplitz en el tiempo (almacenando solo un valor de cada diagonal) y multiplicarlas en el tiempo. ${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$
• Las matrices de Toeplitz son persimétricas . Las matrices simétricas de Toeplitz son centrosimétricas y bisimétricas .
• Las matrices de Toeplitz también están estrechamente relacionadas con las series de Fourier , porque el operador de multiplicación por un polinomio trigonométrico , comprimido en un espacio de dimensión finita, se puede representar mediante una matriz de este tipo. De manera similar, se puede representar la convolución lineal como una multiplicación por una matriz de Toeplitz.
• Las matrices de Toeplitz se conmutan asintóticamente . Esto significa que se diagonalizan sobre la misma base cuando la dimensión de la fila y la columna tiende al infinito.

• Para matrices de Toeplitz simétricas, existe la descomposición

${\displaystyle {\frac {1}{a_{0}}}A=GG^{\operatorname {T} }-(G-I)(G-I)^{\operatorname {T} }}$

¿Dónde está la parte triangular inferior de ? ${\displaystyle G}$ ${\displaystyle {\frac {1}{a_{0}}}A}$

• La inversa de una matriz de Toeplitz simétrica no singular tiene la representación

${\displaystyle A^{-1}={\frac {1}{\alpha _{0}}}(BB^{\operatorname {T} }-CC^{\operatorname {T} })}$

donde y son matrices de Toeplitz triangulares inferiores y es una matriz triangular estrictamente inferior. ^[7] ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle C}$

convolución discreta

La operación de convolución se puede construir como una multiplicación de matrices, donde una de las entradas se convierte en una matriz de Toeplitz. Por ejemplo, la convolución de y se puede formular como: ${\displaystyle h}$ ${\displaystyle x}$

${\displaystyle y=h\ast x={\begin{bmatrix}h_{1}&0&\cdots &0&0\\h_{2}&h_{1}&&\vdots &\vdots \\h_{3}&h_{2}&\cdots &0&0\\\vdots &h_{3}&\cdots &h_{1}&0\\h_{m-1}&\vdots &\ddots &h_{2}&h_{1}\\h_{m}&h_{m-1}&&\vdots &h_{2}\\0&h_{m}&\ddots &h_{m-2}&\vdots \\0&0&\cdots &h_{m-1}&h_{m-2}\\\vdots &\vdots &&h_{m}&h_{m-1}\\0&0&0&\cdots &h_{m}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\vdots \\x_{n}\end{bmatrix}}}$

${\displaystyle y^{T}={\begin{bmatrix}h_{1}&h_{2}&h_{3}&\cdots &h_{m-1}&h_{m}\end{bmatrix}}{\begin{bmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}&0&0&0&\cdots &0\\0&x_{1}&x_{2}&x_{3}&\cdots &x_{n}&0&0&\cdots &0\\0&0&x_{1}&x_{2}&x_{3}&\ldots &x_{n}&0&\cdots &0\\\vdots &&\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\cdots &0&0&x_{1}&\cdots &x_{n-2}&x_{n-1}&x_{n}&0\\0&\cdots &0&0&0&x_{1}&\cdots &x_{n-2}&x_{n-1}&x_{n}\end{bmatrix}}.}$

Este enfoque se puede ampliar para calcular la autocorrelación , la correlación cruzada , la media móvil , etc.

Matriz de Toeplitz infinita

Una matriz de Toeplitz bi-infinita (es decir, entradas indexadas por ) induce un operador lineal en . ${\displaystyle \mathbb {Z} \times \mathbb {Z} }$ ${\displaystyle A}$ ${\displaystyle \ell ^{2}}$

${\displaystyle A={\begin{bmatrix}&\vdots &\vdots &\vdots &\vdots \\\cdots &a_{0}&a_{-1}&a_{-2}&a_{-3}&\cdots \\\cdots &a_{1}&a_{0}&a_{-1}&a_{-2}&\cdots \\\cdots &a_{2}&a_{1}&a_{0}&a_{-1}&\cdots \\\cdots &a_{3}&a_{2}&a_{1}&a_{0}&\cdots \\&\vdots &\vdots &\vdots &\vdots \end{bmatrix}}.}$

El operador inducido está acotado si y sólo si los coeficientes de la matriz de Toeplitz son los coeficientes de Fourier de alguna función esencialmente acotada . ${\displaystyle A}$ ${\displaystyle f}$

En tales casos, se denomina símbolo de la matriz de Toeplitz y la norma espectral de la matriz de Toeplitz coincide con la norma de su símbolo. La demostración es fácil de establecer y se puede encontrar en el Teorema 1.1 de. ^[8] ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle L^{\infty }}$

Ver también

• Matriz circulante , una matriz de Toeplitz cuadrada con la propiedad adicional de que ${\displaystyle a_{i}=a_{i+n}}$
• Matriz de Hankel , una matriz de Toeplitz "al revés" (es decir, con filas invertidas)
• Teoremas del límite de Szegő  : determinante de matrices de Toeplitz grandes
• Operador de Toeplitz  : compresión de un operador de multiplicación en el círculo al espacio de HardyPages displaying wikidata descriptions as a fallback

Notas

1. Prensa y col. 2007, §2.8.2—Matrices de Toeplitz
2. Hayes 1996, Capítulo 5.2.6
3. Krishna y Wang 1993
4. Monahan 2011, §4.5—Sistemas Toeplitz
5. Brent 1999
6. Bojanczyk y col. 1995
7. Mukherjee y Maiti 1988
8. Böttcher y Grudsky 2012

Referencias

• Bojanczyk, AW; Brent, RP; de Hoog, FR; Sweet, DR (1995), "Sobre la estabilidad de los algoritmos de factorización de Bareiss y Toeplitz relacionados", Revista SIAM sobre análisis y aplicaciones de matrices , 16 : 40–57, arXiv : 1004.5510 , doi : 10.1137/S0895479891221563, S2CID  367586
• Böttcher, Albrecht; Grudsky, Sergei M. (2012), Matrices de Toeplitz, álgebra lineal asintótica y análisis funcional, Birkhäuser, ISBN 978-3-0348-8395-5
• Brent, RP (1999), "Estabilidad de algoritmos rápidos para sistemas lineales estructurados", en Kailath, T.; Sayed, AH (eds.), Algoritmos rápidos y confiables para matrices con estructura , SIAM , págs. 103–116, doi :10.1137/1.9781611971354.ch4, hdl : 1885/40746 , S2CID  13905858
• Chan, RH-F.; Jin, X.-Q. (2007), Introducción a los solucionadores iterativos de Toeplitz , SIAM , doi :10.1137/1.9780898718850, ISBN 978-0-89871-636-8
• Chandrasekeran, S.; Chicle.; Sol, X.; Xia, J.; Zhu, J. (2007), "Un algoritmo ultrarrápido para sistemas de ecuaciones lineales de Toeplitz", Revista SIAM sobre análisis y aplicaciones de matrices , 29 (4): 1247–1266, CiteSeerX  10.1.1.116.3297 , doi :10.1137/040617200
• Chen, WW; Hurvich, CM; Lu, Y. (2006), "Sobre la matriz de correlación de la transformada discreta de Fourier y la solución rápida de grandes sistemas de Toeplitz para series temporales de memoria larga", Revista de la Asociación Estadounidense de Estadística , 101 (474): 812–822, CiteSeerX  10.1.1.574.4394 , doi : 10.1198/016214505000001069, S2CID  55893963
• Hayes, Monson H. (1996), Modelado y procesamiento estadístico de señales digitales , John Wiley & Son, ISBN 0-471-59431-8
• Krishna, H.; Wang, Y. (1993), "El algoritmo Split Levinson es débilmente estable" , SIAM Journal on Numerical Analysis , 30 (5): 1498–1508, doi :10.1137/0730078
• Monahan, JF (2011), Métodos numéricos de estadística , Cambridge University Press
• Mukherjee, Bishwa Nath; Maiti, Sadhan Samar (1988), "Sobre algunas propiedades de las matrices de Toeplitz definidas positivas y sus posibles aplicaciones" (PDF) , Álgebra lineal y sus aplicaciones , 102 : 211–240, doi : 10.1016/0024-3795(88)90326- 6
• Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), Recetas numéricas: el arte de la informática científica (tercera ed.), Cambridge University Press , ISBN 978-0-521-88068-8
• Stewart, M. (2003), "Un solucionador Toeplitz ultrarrápido con estabilidad numérica mejorada", SIAM Journal on Matrix Analysis and Applications , 25 (3): 669–693, doi :10.1137/S089547980241791X, S2CID  15717371
• Yang, Zai; Xie, Lihua; Stoica, Petre (2016), "Descomposición de Vandermonde de matrices de Toeplitz multinivel con aplicación a superresolución multidimensional", IEEE Transactions on Information Theory , 62 (6): 3685–3701, arXiv : 1505.02510 , doi : 10.1109/TIT.2016.2553041, S2CID  6291005

Otras lecturas

• Bareiss, EH (1969), "Solución numérica de ecuaciones lineales con matrices de Toeplitz y vectoriales de Toeplitz", Numerische Mathematik , 13 (5): 404–424, doi :10.1007/BF02163269, S2CID  121761517
• Goldreich, O .; Tal, A. (2018), "Rigidez matricial de matrices aleatorias de Toeplitz", Complejidad computacional , 27 (2): 305–350, doi :10.1007/s00037-016-0144-9, S2CID  253641700
• Golub GH , van Loan CF (1996), Computaciones matriciales ( Johns Hopkins University Press ) §4.7—Toeplitz y sistemas relacionados
• Gray RM, Toeplitz y matrices circulantes: una revisión (ahora editores) doi :10.1561/0100000006
• Noor, F.; Morgera, SD (1992), "Construcción de una matriz hermitiana de Toeplitz a partir de un conjunto arbitrario de valores propios", IEEE Transactions on Signal Processing , 40 (8): 2093–2094, Bibcode :1992ITSP...40.2093N, doi :10.1109/ 78.149978
• Pan, Victor Y. (2001), Matrices y polinomios estructurados: algoritmos superrápidos unificados , Birkhäuser , ISBN 978-0817642402
• Sí, Ke; Lim, Lek-Heng (2016), "Cada matriz es un producto de matrices de Toeplitz", Fundamentos de la Matemática Computacional , 16 (3): 577–598, arXiv : 1307.5132 , doi : 10.1007/s10208-015-9254-z, S2CID  254166943