Circulant Diagonalization Theorem and discrete Fourier transform

The Circulant Diagonalization Theorem is a result in linear algebra that pertains to circulant matrices. A circulant matrix is a special type of matrix where each row is a cyclic shift of the previous row. Specifically, a circulant matrix $C$ of size $n \times n$ can be defined by its first row $(c_0, c_1, c_2, \ldots, c_{n-1})$ , and its subsequent rows are generated by rotating this first row.

Properties of Circulant Matrices

Structure: A circulant matrix $C$ can be expressed as: $C = \begin{pmatrix} c_0 & c_1 & c_2 & \cdots & c_{n-1} \\ c_{n-1} & c_0 & c_1 & \cdots & c_{n-2} \\ c_{n-2} & c_{n-1} & c_0 & \cdots & c_{n-3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c_1 & c_2 & c_3 & \cdots & c_0 \end{pmatrix}$
Eigenvalues and Eigenvectors: The eigenvalues of a circulant matrix can be computed using the discrete Fourier transform (DFT). If $\omega = e^{2\pi i / n}$ is a primitive $n$ -th root of unity, the eigenvalues $\lambda_k$ of the circulant matrix $C$ are given by: $\lambda_k = \sum_{j=0}^{n-1} c_j \omega^{jk}, \quad k = 0, 1, \ldots, n-1$
Diagonalization: A circulant matrix can be diagonalized using the discrete Fourier transform matrix $F$ . Specifically, if $F$ is the $n \times n$ matrix whose $(j, k)$ -th entry is given by $F_{jk} = \frac{1}{\sqrt{n}} \omega^{jk}$ , then: $C = F D F^$ where $D$ is a diagonal matrix containing the eigenvalues $\lambda_k$ , and $F^$ is the conjugate transpose of $F$ .

Implications

The Circulant Diagonalization Theorem implies that circulant matrices are particularly well-behaved in terms of their spectral properties, making them useful in various applications, including signal processing, systems theory, and numerical analysis. The ability to diagonalize these matrices efficiently allows for fast computations, especially when dealing with large matrices.

An example of a circulant matrix, compute its eigenvalues, and demonstrate how to diagonalize it using Python.

🧠Example

Consider the circulant matrix defined by the first row $(1, 2, 3)$ . The corresponding circulant matrix $C$ is:

$$ C = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \\ 2 & 3 & 1 \end{pmatrix} $$

Eigenvalues and Diagonalization

We will compute the eigenvalues of this matrix and diagonalize it using the discrete Fourier transform.

Python Code Snippet

Here's a Python code snippet that demonstrates how to create the circulant matrix, compute its eigenvalues, and perform the diagonalization:

https://gist.github.com/viadean/099c372790b5727852d9ff4d301f4d78

Explanation of the Code

Creating the Circulant Matrix: The circulant_matrix function generates the circulant matrix by rolling the first row.
Computing Eigenvalues and Eigenvectors: We use np.linalg.eig to compute the eigenvalues and eigenvectors of the matrix $C$ .
Diagonalization: We construct the DFT matrix $F$ using the Fast Fourier Transform (FFT) and then perform the diagonalization using the formula $C = F D F^*$ .