Sum/multiplication of two circulant matrices is a circulant matrix

Question

I know that the sum/multiplication of two circulant matrices is a circulant matrix. I'm looking for the shortest/easiest way to prove those two theorems. I could represent $A$ and $B$ as full $n\times n$ matrices and prove it easily enough by looking at $a_{ij}+b_{ij}$. But is there a shorter proof?

Answer 1

A matrix is circulant if and only if it commutes with $$J=\pmatrix{0&1&0&\cdots&0\\ 0&0&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&1\\ 1&0&0&\cdots&0}$$ From this observation, it is apparent that sums and products of circulants are circulant.

Answer 2

All circulant matrices are diagonalized by the Fourier matrix $\mathbf W$, (yes, they all have the same eigenvectors). That is we have for all circulant matrices

$\mathbf D = \mathbf W \mathbf C \mathbf W^H$

with $\mathbf D$ a diagonal matrix. Also for any diagonal matrix there exists one circulant matrix ($\mathbf W^H \mathbf D \mathbf W$).

That sum and product of circulant matrices are also circulant follows from that very easily. Essentially because sum and product of diagonal matrices are also diagonal.

Furthermore, the inverse (if it exists) of a circulant matrix is also circulant. Bonus: It is invertible if and only if the corresponding diagonal matrix has has no zeros on its diagonal.