Matriz de Toeplitz

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${\displaystyle n\times n}$matriz${\displaystyle A}$de la forma

${\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 la${\displaystyle i,j}$elemento de${\displaystyle A}$se denota${\displaystyle A_{i,j}}$entonces tenemos

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

Una matriz de Toeplitz no es necesariamente cuadrada .

Una ecuación matricial de la forma

${\displaystyle Ax=b}$

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

Los sistemas de Toeplitz se pueden resolver mediante algoritmos como el algoritmo de Schur o el algoritmo de Levinson .${\displaystyle O(n^{2})}$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${\displaystyle O(n^{2})}$tiempo. ^{[ 4 ]}

Una matriz de Toeplitz también puede descomponerse (es decir, factorizarse) en${\displaystyle O(n^{2})}$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. Usando el rango de desplazamiento obtenemos un método que requiere${\displaystyle {\tilde {O}}({\alpha ^{\omega -1}}n)}$operaciones con el uso de algoritmos rápidos de multiplicación de matrices , donde${\displaystyle \alpha }$es el rango y${\displaystyle ^{\sim }2.37\leq \omega <3}$^{[ 7 ]} .

• Un${\displaystyle n\times n}$La matriz de Toeplitz puede definirse como una matriz${\displaystyle A}$dónde${\displaystyle A_{i,j}=c_{i-j}}$, para constantes${\displaystyle c_{1-n},\ldots ,c_{n-1}}$. El conjunto de${\displaystyle n\times n}$Las matrices de Toeplitz son un subespacio del espacio vectorial de${\displaystyle n\times n}$matrices (en suma de matrices y multiplicación escalar).
• Se pueden agregar dos matrices de Toeplitz en${\displaystyle O(n)}$tiempo (al almacenar solo un valor de cada diagonal) y multiplicado en${\displaystyle O(n^{2})}$tiempo.
• Las matrices de Toeplitz son persimétricas . Las matrices de Toeplitz simétricas son tanto centrosimétricas como bisimétricas .
• Las matrices de Toeplitz también están estrechamente relacionadas con las series de Fourier , ya que el operador de multiplicación por un polinomio trigonométrico , comprimido a un espacio de dimensión finita, puede representarse mediante una matriz de este tipo. De manera similar, la convolución lineal puede representarse como una multiplicación por una matriz de Toeplitz.
• Las matrices de Toeplitz son asintóticamente equivalentes a matrices circulantes a medida que aumenta la dimensión, un resultado conocido como el teorema de Grenander-Szegő . ^{[ 8 ]} Esta propiedad de circulación asintótica es la razón por la que la transformada discreta de Fourier diagonaliza aproximadamente matrices de Toeplitz grandes, y subyace a la efectividad de la estimación de densidad espectral basada en DFT para procesos estacionarios .
• Las matrices de Toeplitz conmutan asintóticamente . Esto significa que se diagonalizan en la misma base cuando la dimensión de filas y columnas tiende a 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${\displaystyle G}$es la parte triangular inferior de${\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} })}$

dónde${\displaystyle B}$y${\displaystyle C}$son matrices triangulares inferiores de Toeplitz y${\displaystyle C}$es una matriz triangular inferior estricta. ^{[ 9 ]}

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${\displaystyle h}$y${\displaystyle x}$puede formularse como:

${\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 extender para calcular la autocorrelación , la correlación cruzada , la media móvil , etc.

Una matriz de Toeplitz bi-infinita (es decir, entradas indexadas por${\displaystyle \mathbb {Z} \times \mathbb {Z} }$)${\displaystyle A}$induce un operador lineal en${\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 solo si los coeficientes de la matriz de Toeplitz${\displaystyle A}$son los coeficientes de Fourier de alguna función esencialmente acotada${\displaystyle f}$.

En tales casos,${\displaystyle f}$Se denomina símbolo de la matriz de Toeplitz.${\displaystyle A}$y la norma espectral de la matriz de Toeplitz${\displaystyle A}$coincide con el${\displaystyle L^{\infty }}$norma de su símbolo. La demostración se puede encontrar en el Teorema 1.1 de Böttcher y Grudsky. ^{[ 10 ]}

• 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 "invertida" (es decir, con las filas invertidas).
• Teoremas del límite de Szegő : determinante de matrices de Toeplitz grandes 
• Operador de Toeplitz