Matrice di Toeplitz

In algebra lineare, una matrice di Toeplitz o matrice a diagonali costanti è una matrice in cui ogni diagonale discendente da sinistra a destra è costante. Ad esempio, la seguente matrice è una matrice di Toeplitz:

{\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}}

Queste matrici prendono il loro nome dal matematico tedesco Otto Toeplitz (1881-1940).

Ogni matrice $A$ di ordine $n$ della seguente forma

A={\begin{bmatrix}a_{0}&a_{-1}&a_{-2}&\ldots &\ldots &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}&\ldots &\ldots &a_{2}&a_{1}&a_{0}\end{bmatrix}}

è una matrice di Toeplitz.

Indicando con $A_{ij}$ l'elemento della matrice $A$ della riga $i$ e della colonna $j$ si ottiene:

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

Una matrice di Toeplitz non è necessariamente quadrata.

Proprietà

In generale, un'equazione matriciale

Ax=b

rappresenta un sistema di $n$ equazioni lineari. Se $A$ è una matrice di Toeplitz, allora il sistema ricade in un caso particolare (ha solo $2n-1$ gradi di libertà, invece di $n^{2}$ ). Ci si può quindi aspettare che la soluzione di un sistema di Toeplitz sia ottenibile con un procedimento specifico e semplice.

Ciò può essere verificato dalla trasformazione:

AU_{n}-U_{m}A,

che ha due righe, dove $U_{k}$ è l'operatore di riduzione. Nello specifico, si può, con un semplice calcolo, dimostrare che

AU_{n}-U_{m}A={\begin{bmatrix}a_{-1}&\cdots &a_{-n+1}&0\\\vdots &&&-a_{-n+1}\\\vdots &&&\vdots \\0&\cdots &&-a_{n-n-1}\end{bmatrix}},

dove si intende che gli spazi vuoti nella matrice contengano degli zeri.

Note

Per matrici di tipo Toeplitz l'addizione può essere fatta in un tempo $O(n)$ , il prodotto per un vettore può essere eseguito in un tempo $O(n\log(n))$ . Anche la moltiplicazione di due matrici di Toeplitz può essere eseguita in modo estremamente efficiente, essendo fattibile in un tempo $O(n\log(n))$ .

I sistemi di Toeplitz della forma $Ax=b$ possono essere risolti con l'algoritmo di Levinson-Durbin in un tempo $O(n^{2})$ . È stato dimostrato che le varianti di questo algoritmo sono debolmente stabili (ad esempio, esse presentano stabilità per sistemi lineari dipendenti).

Le matrici di Toeplitz sono anche strettamente connesse con le serie di Fourier, perché l'operatore di moltiplicazione per un polinomio trigonometrico, ridotta a uno spazio a dimensione finita, può essere rappresentato da una matrice di questo genere.

Se una matrice di Toeplitz possiede anche la proprietà che $a_{i}=a_{i+n}$ , allora è una matrice circolante.