Toeplitz矩陣

線性代數入面，Toeplitz矩陣，（個名來自Otto Toeplitz），又叫常對角矩陣(diagonal-constant matrix)，即係每條左上到右下嘅對角線都係常值嘅嘅（唔一定要四方形，長方都得）矩陣。例如：

${\begin{bmatrix}a&b&c&d&k\\f&a&b&c&d\\g&f&a&b&c\\h&g&f&a&b\\j&h&g&f&a\end{bmatrix}}$

任何咁樣嘅n×n 矩陣 A ：

$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}}$

都係個Toeplitz矩陣。若我地叫A 嘅 i,j元做A_i,j，咁

$A_{i,j}=a_{i-j}.$

性質

通常，矩陣方程

$Ax=b$

可以睇做一般解n條線性方程嘅問題。如果 A 係個 Toeplitz 矩陣，咁套方程就好特別(自由度得 2n − 1 ，而唔係 n²)。 所以Toeplitz系統我哋可以預咗會易解的。

呢方面可以借以下嘅 2階(rank)轉換

$AU_{n}-U_{m}A,$

來研究；其中 $U_{k}$ 係向下郁算子( down-shift operator)。尤其，由簡短計算，我地可知：

$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}}$

其中空咗嘅都係零。

註

呢啲矩陣嚮電算有用，因為可以證: 加埋兩個 Toeplitz 矩陣只使O(n)時間； Toeplitz 矩陣 x 向量要用 O(n log n) 時間；而兩隻 Toeplitz 矩陣 x Toeplitz矩陣可以只用 O($n^{2}$) 時間。

Toeplitz 系統 $Ax=b$ 可以用 Levinson-Durbin Algorithm 解，需時 Θ($n^{2}$) 。 呢套算法嘅變種，可證係喺 James Bunch 嘅意義上弱穏定(weakly stable) 嘅，(即係話，喺 well-condition 嘅線性系統，佢哋有 numerical stability )。

Toeplitz 矩陣同富理埃級數關係好密，因為「乘以一三角多項式」嘅 算子質埋入一有限維嘅空間時，可以用呢種矩陣表示。

If a Toeplitz matrix has the additional property that $a_{i}=a_{i+n}$, then it is a circulant matrix.

Toeplitz matrices are persymmetric. Symmetric Toeplitz matrices are both centrosymmetric and bisymmetric.

卷積 operation can be constructed as a matrix multiplication, where one of the inputs is converted into a Toeplitz matrix. For example, the convolution of $x$ and $h$ can be formulated as:

${\begin{matrix}y&=&x\ast h\\&=&{\begin{bmatrix}h_{1}\\h_{2}\\h_{3}\\\vdots \\h_{m-1}\\h_{m}\\\end{bmatrix}}{\begin{bmatrix}x_{1}&x_{2}&x_{3}&\ldots &x_{n}&0&0&0&\ldots &0\\0&x_{1}&x_{2}&x_{3}&\ldots &x_{n}&0&0&\ldots &0\\0&0&x_{1}&x_{2}&x_{3}&\ldots &x_{n}&0&\ldots &0\\\vdots &\vdots &\vdots &\vdots &\vdots &\ldots &\vdots &\vdots &\ldots &0\\0&\ldots &0&0&x_{1}&\ldots &x_{n-2}&x_{n-1}&x_{n}&0\\0&0&\ldots &0&0&x_{1}&\ldots &x_{n-2}&x_{n-1}&x_{n}\\\end{bmatrix}}\end{matrix}}$.

This approach can be extended to compute autocorrelation, cross-correlation, moving average etc .

睇吓

• Circulant matrix

出面網頁

• Toeplitz and Circulant Matrices: A Review, by R. M. Gray