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 *k*th 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*_{1} through *e*_{n}. In the case of circulant matrices we can take *e*_{k} to be the *k*th 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.