Circulant matrices, eigenvectors, and the FFT
A circulant matrix is a sq. matrix through which every row is a rotation of the earlier row. This publish will illustrate a connection between circulant matrices and the FFT (Quick Fourier Rework).
Circulant matrices
Shade within the first row nevertheless you need. Then transfer the final aspect to the entrance to make the subsequent row. Repeat this course of till the matrix is full.
The NumPy operate roll will do that rotation for us. Its first argument is the row to rotate, and the second argument is the variety of rotations to do. So the next Python code generates a random circulant matrix of measurement N.
import numpy as np
np.random.seed(20230512)
N = 5
row = np.random.random(N)
M = np.array([np.roll(row, i) for i in range(N)])
Right here’s the matrix M with entries truncated to three decimal locations to make it simpler to learn.
[[0.556 0.440 0.083 0.460 0.909]
[0.909 0.556 0.440 0.083 0.460]
[0.460 0.909 0.556 0.440 0.083]
[0.083 0.460 0.909 0.556 0.440]
[0.440 0.083 0.460 0.909 0.556]]
Quick Fourier Rework
The Quick Fourier Rework is a linear transformation and so it may be represented by a matrix [1]. This the N by N matrix whose (j, okay) entry is ωjk the place ω = exp(-2πi/N), with j and okay working from 0 to N – 1. [2]
Every aspect of the FFT matrix corresponds to a rotation, so you possibly can visualize the matrix utilizing clocks in every entry or by a cycle of colours. A couple of years in the past I created a visualization utilizing each clock faces and colours:
Eigenvectors and Python code
Right here’s a stunning property of circulant matrices: the eigenvectors of a circulatnt matrix rely solely on the dimensions of the matrix, not on the weather of the matrix. Moreover, these eigenvectors are the columns of the FFT matrix. The eigenvalues depend upon the matrix entries, however the eigenvectors don’t.
Mentioned one other means, whenever you multiply a circulant matrix by a column of the FFT matrix of the identical measurement, this column will likely be stretched however not rotated. The quantity of stretching relies on the actual circulant matrix.
Right here is Python code for example this.
for i in vary(N):
ω = np.exp(-2j*np.pi/N)
col1 = np.array([ω**(i*j) for j in range(N)])
col2 = np.matmul(M, col1)
print(col1/col2)
On this code col1 is a column of the FFT matrix, and col2 is the picture of the column when multiplied by the circulant matrix M. The print assertion reveals that the ratios of every components are the identical in every place. This ratio is the eigenvalue related to every eigenvector. In case you have been to generate a brand new random circulant matrix, the ratios would change, however the enter and output vectors would nonetheless be proportional.