1 2 3 4
4 1 2 3
3 4 1 2
2 3 4 1
By convention, rows shift to the right, so that diagonals are constant. If you want the rows to shift to the left, so that antidiagonals are constant, leave the top row in place and reverse the order of the remaining rows. This does not change the determinant or the rank of M.
It is convenient to number rows and columns starting at 0. Now the top row is a vector v, and Mi,j is vi-j, where subtraction takes place mod n.
The sum of two circulant matrices is circulant, as defined by v+w.
The transpose of a circulant matrix is circulant. Essentially, the first entry v0 remains, and the rest of v, representing the top row, is taken in the reverse order.
Consider the i,j entry of the product of two circulant matrices. For convenience, transpose the second, and rebuild w accordingly. The ith row of the first matrix dotted with the jth row of the second is v shifted by i dotted with w shifted by j. Add 1 to i and j and this does not change. The product is constant along diagonals, and is circulant.
Assume M is nonsingular and consider its inverse. Select i,j and look at its cofactor. Compare this with the cofactor up and to the left, in position i-1,j-1. The sign is the same, and the submatrix is the same, once you move the left column to the right, and the top row to the bottom. (Doing both operations preserves the sign of the subdeterminant.) The cofactors are constant along diagonals, giving a circulant matrix. Take the transpose, and the adjoint is circulant. Divide by the determinant, and the inverse is circulant.
Let r be an nth root of 1. Let x be a column vector with xi = ri, and consider M*x. The first entry is v.x. The second entry is v shifted to the right, then dotted with x. The entry in v that use to line up with r is now multiplied by r2, and so on. The result is r×v.x. The ith> entry is ri×v.x. Therefore M*x is a scale multiple of x, and x is an eigen vector, with eigen value v.x.
There are n nth roots of 1, producing n eigen vectors. These vectors are linearly independent. Why? Because the vectors form a vandermonde matrix, and the determinant of such a matrix is nonzero whenever the lead entries, in this case the n roots of 1, are all distinct.
If k eigen values are nonzero, then the columns of M can be combined to produce k linearly independent vectors. The columns of M span a space whose dimension is at least k. At the same time, n-k eigen values are 0, hwence an n-k dimensional space lies in the kernel of M. In terms of dimensionality, kernel plus range has to equal n, hence the rank of M (as columns) equals k. If you want to know the rank of the rows of M, make x a row vector on the left, and consider x.v, where v is the first column of M. Step through the n eigen vectors, based on the n roots of 1, and compute all n dot products. If there are k nonzero dot products, the rank of M is k.
These results hold forr a division ring, as well as a field; (except perhaps the cofactor calculation of M inverse).