Circulant matrices

A circulant matrix is a square matrix in which each row (or column) is a rightward (or downward) cyclic shift of the previous one.

Its connection with circular convolution $c_{\textcolor{#e11d48}{k}} = \sum_{i=0}^{n-1} a_{\textcolor{#e11d48}{i}}b_{\textcolor{#e11d48}{k-i}}$ is what makes it interesting: each output $z_k$ is a sum of products $x_i y_j$ where the indices wrap around cyclically.

0. Cyclic permutation matrix

The following matrix is a 5x5 cyclic permutation matrix:

The corresponding permutation only has one cycle of order 5: $(1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5)$. Thus its eigenvalues are the 5th roots of unity $\lambda, \lambda^2, \lambda^3, \lambda^4, \lambda^5 = 1$ where $\lambda = e^{2\pi i / 5}$. For a reason that will become clear shortly, we order the eigenvalues like so: $1, \lambda, \lambda^2, \lambda^3, \lambda^4$.

The (unnormalized) eigenvector corresponding to the eigenvalue $\lambda$ is $\begin{bmatrix} 1 & \lambda & \lambda^2 & \lambda^3 & \lambda^4 \end{bmatrix}$. The rest of the eigenvectors can be formed by replacing $\lambda$ with $\lambda^k$ for different values of $k$. The matrix of all (normalized) eigenvectors looks like:

This is the 5x5 DFT matrix. Thus the eigenvectors of the permutation matrix are the columns of the DFT matrix. We can generalize this to any size of the cyclic permutation matrix.

The eigenvectors of a cyclic n x n permutation matrix are the columns of the n x n DFT matrix. The eigenvalues are the nth roots of unity.

0.1. Spectral properties of any circulant matrix

Now here is a fun fact: any circulant matrix has the same eigenvectors as its corresponding cyclic permutation matrix. It is based on two insights:

1. $Ax = \lambda x \Rightarrow \underbrace{\textcolor{#b45309}{p(A)x = p(\lambda)x}}_{\textcolor{#b45309}{\text{polynomial function of A has the same eigenvectors}}}$

2. A circulant matrix is a polynomial function of cyclic permutation matrices.

The first point can be verified by simply expanding the polynomial. An example of the second point is the following:

which is equal to $p(A) = aI + bA + cA^2$ where $A$ is the matrix for the cyclic permutation 1,2,3 → 3,1,2. Thus the eigenvalues of the above circulant matrix are $p(\lambda) = a + b\lambda + c\lambda^2$ for each root of unity $\lambda$.

1. Connection with the convolution theorem

If $F$ is the DFT matrix and $D$ is the diagonal matrix of eigenvalues of the cyclic permutation matrix, then the eigendecomposition of the permutation matrix is $P = FDF^{-1}$. In the code below, the cyclic matrix is reconstructed using an eigendecomposition product of a DFT matrix and a diagonal matrix of roots of unity:

Verification using Python

import torch
P5 = torch.Tensor([
    [0,0,0,0,1],
    [1,0,0,0,0],
    [0,1,0,0,0],
    [0,0,1,0,0],
    [0,0,0,1,0],
])
F = torch.fft.fft(torch.eye(5)).div(5**0.5)  # DFT matrix
D = torch.arange(5).mul(2 * torch.pi * 1j).div(5).exp().diag()  # Diagonal matrix of roots of unity

P5_reconstructed = F @ D @ F.conj()
print(P5_reconstructed.imag.norm())
print((P5_reconstructed.real - P5).norm())

### Output: ###
tensor(2.0843e-07)  # Imaginary part is very close to zero
tensor(2.1113e-07)  # Real part is very close to the original matrix

1.1. Convolution theorem

The convolution theorem states that the Fourier transform of the convolution of two functions is the product of their Fourier transforms. Mathematically, it can be written as:

Now we look at how it is connected to the eigendecomposition of a circulant matrix $C$. The convolution $Cx$ is the same as the matrix multiplication $FDF^{-1}x$ which can be interpreted like so:

What's convolution in one domain is a product in another domain. Equivalently: what's a matrix-vector product in one basis is an elementwise product in another basis.

In the next section we will look at the geometry of an object whose vertices are these permutation matrices.

← Permutation spectra · Birkhoff polytope →