Circulant matrices commute

A few days ago I wrote that circulant matrices all have the same eigenvectors. This post will show that it follows that circulant matrices commute with each other.

Recall that a circulant matrix is a square matrix in which the rows are cyclic permutations of each other. If we number the rows from 0, then the kth row takes the last k rows of the top row and moves them to the front.

Numerical example

We can generate two random circulant matrices and confirm that they commute by modifying the Python code from the earlier post.

 np.random.seed(42) N = 6 row = np.random.random(N) A = np.array([np.roll(row, i) for i in range(N)]) row = np.random.random(N) B = np.array([np.roll(row, i) for i in range(N)]) AB = np.matmul(A, B) BA = np.matmul(B, A) print(np.absolute(AB - BA).max())

This computes two random 6 by 6 circulant matrices A and B and shows that the difference between AB and BA is on the order of the limit of floating point precision. Specifically, this prints 4.44 * 10^-16.

Proof

Now for a proof. Let A and B be two matrices of size n that have the same set of independent eigenvectors e₁ through e_n. In the case of circulant matrices we can take e_k to be the kth column of the FFT matrix, but the proof here applies to any matrices with common eigenvectors.

Let _k be the eigenvalue for e_k as an eigenvector of A and let _k be the eigenvalue for e_k as an eigenvector of B. Then

and

and so multiplying by AB or BA has the same effect on e_k since the complex numbers _k and _k commute. Since the eigenvalues form a basis, and multiplication by AB and BA has the same effect on each basis vector, AB = BA.

In short, matrices that share eigenvectors commute because eigenvalues commute.

The post Circulant matrices commute first appeared on John D. Cook.