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_\rose{k} = \sum_{i=0}^{n-1} a_{\rose{i}}b_{\rose{k-i}} \) is made clear by the following animation:

The following matrix is a 5x5 cyclic permutation matrix:\( \begin{bmatrix} 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 \end{bmatrix} \)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 reason that will become clear shortly, we order the eigenvalues like so: \( 1, λ, λ^2, λ^3, λ^4 \).

The (unnormalized) eigenvector corresponding to the eigenvalue \( \lambda \) is \( \begin{bmatrix} 1 \\ λ \\ λ^2 \\ λ^3 \\ λ^4 \end{bmatrix} \). The rest of the eigenvectors can be formed by replacing \( λ \) with \( λ^k \) for different values of \( k \). The matrix of all (normalized) eigenvectors looks like:\( V = \frac{1}{\sqrt{5}} \)\( \begin{bmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & λ & λ^2 & λ^3 & λ^4 \\ 1 & λ^2 & λ^4 & λ & λ^3 \\ 1 & λ^3 & λ & λ^4 & λ^2 \\ 1 & λ^4 & λ^3 & λ^2 & λ \end{bmatrix} \)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.

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:

The first point can be verified by simply expanding the polynomial. An example of the second point is the following:\( \begin{bmatrix} a & c & b \\ b & a & c \\ c & b & a \end{bmatrix} \)\( = \)\( a \)\( \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \)\( + b \)\( \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} \)\( + c \)\( \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \)which is equal to \( p(A) = aI + bA + cA^2 \) where \( A \) is the matrix for the permutation 1,2,3 → 3,1,2. Thus the eigenvalues of the above circulant matrix are \( p(λ) = a + bλ + cλ^2 \) for each root of unity \( λ \).

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 square roots of unity:

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

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:$$ \mathcal{F}(f * g) = \mathcal{F}(f) \cdot \mathcal{F}(g) $$Now we look at how it is connected to the eigendecomposition of a circulant matrix \( C \). The convolution \( C x \) is the same as the matrix multiplication \( FDF^{-1}x \) which can be interpreted like so:$$ C x = \underbrace{F \underbrace{D \underbrace{F^{-1}x}_{\amber{\text{x in Fourier basis}}}}_{\rose{\text{element-wise product}}}}_{\text{x in original basis}} $$

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