Chapter 37A: Toeplitz, Hankel, and Circulant Matrices¶

Prerequisites: Matrix Algebra (Ch02) · Matrix Decompositions (Ch10) · Discrete Fourier Transform (Ch30)

Chapter Outline: Motivation for Structured Matrices → Definition of Circulant Matrices → Diagonalization via DFT → Definition of Toeplitz Matrices and Shift Invariance → Definition of Hankel Matrices and Symmetry → Relationship between Toeplitz and Hankel (Reversal Matrix $J$) → Fast Algorithms: Levinson-Durbin Recursion → Generating Function Perspective → Asymptotic Spectral Theory (Szegő’s Limit Theorem) → Applications: Time Series Analysis, Autocorrelation, and Convolution

Extension: Structured matrices are the bedrock of modern communications and signal processing; the diagonalization of circulant matrices reveals the algebraic roots of the Convolution Theorem, while Toeplitz matrices are the standard algebraic expression for all Linear Time-Invariant (LTI) systems.

In general matrix theory, storing an $n \times n$ matrix requires $n^2$ elements. however, many matrices encountered in engineering are generated by a small number of parameters (e.g., $O(n)$). Toeplitz (constant along diagonals), Hankel (constant along anti-diagonals), and Circulant matrices are quintessential examples of such structured matrices. This chapter demonstrates how these structures translate into a leap in computational efficiency.

37A.1 Circulant Matrices and the DFT¶

Definition 37A.1 (Circulant Matrix)

A matrix $C$ is Circulant if each row is a cyclic right shift of the preceding row. It is completely determined by its first row vector $\mathbf{c} = (c_0, c_1, \ldots, c_{n-1})$.

Theorem 37A.1 (Diagonalization Theorem)

Every $n \times n$ circulant matrix $C$ can be diagonalized by the $n \times n$ DFT Matrix $F_n$: $$C = F_n^* \Lambda F_n$$ where the diagonal entries of $\Lambda$ are exactly the discrete Fourier transform of the first row vector $\mathbf{c}$. Corollary: Multiplication and inversion of circulant matrices can be performed in $O(n \log n)$ time.

37A.2 Toeplitz and Hankel Matrices¶

Definition 37A.2 (Toeplitz Matrix)

A matrix $T$ is Toeplitz if its entries satisfy $t_{ij} = t_{i-j}$, meaning entries are constant along lines parallel to the main diagonal.

Definition 37A.3 (Hankel Matrix)

A matrix $H$ is Hankel if its entries satisfy $h_{ij} = h_{i+j}$, meaning entries are constant along lines perpendicular to the main diagonal. Relationship: $T$ is Toeplitz $\iff JT$ is Hankel (where $J$ is the reversal matrix).

37A.3 Fast Algorithms and Generating Functions¶

Technique: Levinson-Durbin Recursion

For symmetric positive definite Toeplitz systems $T\mathbf{x} = \mathbf{b}$, one can exploit the nested nature of the structure to obtain an exact solution in $O(n^2)$ time rather than $O(n^3)$. This is vital in predictive coding and speech processing.

Theorem 37A.2 (Szegő’s Limit Theorem)

As $n \to \infty$, the distribution of eigenvalues of large Toeplitz matrices approaches the range of values taken by its generating function (the symbol) on the unit circle.

Exercises¶

Solution

$\begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \\ 2 & 3 & 1 \end{pmatrix}$.

Solution

$2n - 1$ parameters (the first row has $n$ and the first column provides the remaining $n-1$).

Solution

True. The eigenvectors of any circulant matrix are the columns of the DFT matrix (complex harmonic vectors).

Solution

Yes to both. They are diagonalized by the same $F_n$, so their product is circulant and they commute.

Solution

$a_{ij} = h_{i+j}$ and $a_{ji} = h_{j+i}$. Since scalar addition is commutative, $a_{ij} = a_{ji}$.

Solution

Generally no. However, it possesses a "displacement rank of 2" structure (see Ch37B) and is called a Toeplitz-like matrix.

Solution

It corresponds to the cyclic convolution of signals.

Solution

No. A companion matrix is sparse and has a specific structure in only one row and one column; it does not fit these three classes.

Solution

They are extremely ill-conditioned; their singular values decay exponentially with the size of the matrix, leading to a massive condition number.

Solution

Chapter Summary¶

Structured matrices are the junction of linear algebra and fast algorithms:

****: Toeplitz and circulant structures prove that by exploiting shift invariance, we can describe $O(n^2)$ transformations using $O(n)$ space, greatly reducing storage requirements.

****: The diagonalization theorem for circulant matrices establishes the central role of the Discrete Fourier Transform in operator diagonalization, transforming complex time-domain coupling into simple frequency-domain scaling.

****: Fast algorithms like Levinson-Durbin reveal the overlapping subproblem properties of structured matrices, serving as a brilliant manifestation of dynamic programming in the field of matrix inversion.