product of the vector by the circulant matrix for . The discrete Fourier transform then converts convolution into multiplication, which in the matrix setting corresponds to diagonalization. The -algebra of all circulant matrices with complex entries is isomorphic to the group -algebra of . Symmetric circulant matrices For a symmetric circulant matrix one has the extra condition that . Thus it is determined by elements. The eigenvalues of any real symmetric matrix are real. The corresponding eigenvalues become: for even, and for odd, where denotes the real part of . This can be further simplified by using the fact that . Symmetric circulant matrices belong to the class of bisymmetric matrices. Hermitian circulant matrices The complex version of the circulant matrix, ubiquitous in communications theory, is usually Hermitian. In this case and its determinant and all eigenvalues are real. If n is even the first two rows necessarily takes the form in which the first element in the top second half-row is real. If n is odd we get Tee has discussed constraints on the eigenvalues for the Hermitian condition. Applications In linear equations Given a matrix equation where is a circulant square matrix of size we can write the equation as the circular convolution where is the first column of , and the vectors , and are cyclically extended in each direction. Using the circular convolution theorem, we can use the discrete Fourier transform to transform the cyclic convolution into component-wise multiplication so that This algorithm is much faster than the standard Gaussian elimination, especially if a fast Fourier transform is used. In graph theory In graph theory, a graph or digraph whose adjacency matrix is circulant is called a circulant graph (or digraph). Equivalently, a graph is circulant if its automorphism group contains a full-length cycle. The Möbius ladders are examples of circulant graphs, as are the Paley graphs for fields of prime order. References External links R. M. Gray, Toeplitz and Circulant Matrices: A Review IPython Notebook demonstrating properties of circulant matrices Numerical linear algebra Matrices Latin squares Determinants