What Is a Toeplitz Matrix?

$T\in\mathbb{C}^{n\times n}$ is a Toeplitz matrix if $t_{ij} = t_{i-j}$ for $2n-1$ parameters $t_{1-n},\dots,t_{n-1}$ . A Toeplitz matrix has constant diagonals. For $n = 4$ :

$\notag T = \begin{bmatrix} t_0 & t_{-1} & t_{-2} & t_{-3}\\ t_1 & t_0 & t_{-1} & t_{-2}\\ t_2 & t_1 & t_0 & t_{-1}\\ t_3 & t_2 & t_1 & t_0 \end{bmatrix}.$

Toeplitz matrices arise in various problems, including analysis of time series, discretization of constant coefficient differential equations, and discretization of convolution equations $\int a(t-s)x(s)\,\mathrm{d} s = b(t)$ .

Since a Toeplitz matrix depends on just $2n-1$ parameters it is reasonable to expect that a linear system $Tx = b$ can be solved in less than the $O(n^3)$ flops that would be required by LU factorization. Indeed methods are available that require only $O(n^2)$ flops; see Golub and Van Loan (2013) for details.

Upper triangular Toeplitz matrices can be written in the form

$\notag T = \sum_{j=1}^n t_{1-j} N^{j-1}, \quad N = \begin{bmatrix} 0 & 1 & & \\ & 0 & \ddots & \\ & & \ddots & 1 \\ & & & 0 \end{bmatrix},$

where $N$ is upper bidiagonal with a superdiagonal of ones and $N^n = 0$ . It follows that the product of two upper triangular Toeplitz matrices is again upper triangular Toeplitz, upper triangular Toeplitz matrices commute, and $T^{-1}$ is also an upper triangular Toeplitz matrix (assuming $t_0$ is nonzero, so that $T$ is nonsingular).

Tridiagonal Toeplitz matrices arise frequently:

$\notag T(c,d,e) = \begin{bmatrix} d & e & & \\ c & d & \ddots & \\ & \ddots & \ddots & e \\ & & c & d \end{bmatrix} \in\mathbb{C}^{n\times n}.$

The eigenvalues of $T(c,d,e)$ are

$\notag d + 2 (ce)^{1/2} \cos\biggl( \displaystyle\frac{k \pi}{n+1} \biggr), \quad k = 1:n.$

The Kac–Murdock–Szegö matrix is the symmetric Toeplitz matrix

$\notag A(\rho) = \begin{bmatrix} 1 & \rho & \rho^2 & \dots & \rho^{n-1} \\ \rho & 1 & \rho & \dots & \rho^{n-2} \\ \rho^2 & \rho & 1 & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & \rho \\ \rho^{n-1} & \rho^{n-2} & \dots & \rho & 1 \end{bmatrix}.$

It has a number of interesting properties.

In MATLAB, a Toeplitz matrix can be constructed using toeplitz(c,r), which produces the matrix with first column c and first row r. Example:

>> n = 5; A = toeplitz(1:n,[1 -2:-1:-n])
A =
     1    -2    -3    -4    -5
     2     1    -2    -3    -4
     3     2     1    -2    -3
     4     3     2     1    -2
     5     4     3     2     1

References

Gene Golub and Charles F. Van Loan, Matrix Computations, fourth edition, Johns Hopkins University Press, Baltimore, MD, USA, 2013. Section 4.7.

Related Blog Posts

What Is a Circulant Matrix? (2022)
What Is a Tridiagonal Matrix? (2022)
What Is the Kac–Murdock–Szegö Matrix? (2020)

This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.

References

Related Blog Posts

Share this:

Related

Leave a Reply Cancel reply