Circulant matrix
In linear algebra, a circulant matrix is a square matrix in which all row vectors are composed of the same elements and each row vector is rotated one element to the right relative to the preceding row vector. It is a particular kind of Toeplitz matrix. In numerical analysis, circulant matrices are important because they are diagonalized by a discrete Fourier transform, and hence linear equations that contain them may be quickly solved using a fast Fourier transform. They can be interpreted analytically as the integral kernel of a convolution operator on the cyclic group formula_1 and hence  frequently appear in formal descriptions of spatially invariant linear operations. This property is also critical in modern software defined radios, which utilize Orthogonal Frequency Division Multiplexing to spread the symbols (bits) using a cyclic prefix. This enables the channel to be represented by a circulant matrix, simplifying channel equalization in the frequency domain. In cryptography, a circulant matrix is used in the MixColumns step of the Advanced Encryption Standard. Definition. An formula_2 circulant matrix formula_3 takes the form formula_4 or the transpose of this form (by choice of notation). When the term formula_5 is a formula_6 square matrix, then the  formula_7 matrix formula_3 is called a block-circulant matrix. A circulant matrix is fully specified by one vector, formula_9, which appears as the first column (or row) of formula_3. The remaining columns (and rows, resp.) of formula_3 are each cyclic permutations of the vector formula_9 with offset equal to the column (or row, resp.) index, if lines are indexed from 0 to formula_13. (Cyclic permutation of rows has the same effect as cyclic permutation of columns.) The last row of formula_3 is the vector formula_9 shifted by one in reverse. Different sources define the circulant matrix in different ways, for  example as above, or with the vector formula_9 corresponding to the first row rather than the first column of the matrix; and possibly with a different direction of shift (which is sometimes called an anti-circulant matrix). The polynomial formula_17 is called the "associated polynomial" of matrix formula_3. Properties. Eigenvectors and eigenvalues. The normalized eigenvectors of a circulant matrix are the Fourier modes, namely, formula_19 where formula_20 is a primitive formula_21-th root of unity and formula_22 is the imaginary unit. The corresponding eigenvalues are given by formula_23 Determinant. As a consequence of the explicit formula for the eigenvalues above , the determinant of a circulant matrix can be computed as: formula_24 Since taking the transpose does not change the eigenvalues of a matrix, an equivalent formulation is formula_25 Rank. The rank of a circulant matrix formula_26 is equal to formula_27, where formula_28 is the degree of the polynomial formula_29. Analytic interpretation. Circulant matrices can be interpreted geometrically, which explains the connection with the discrete Fourier transform. Consider vectors in formula_62 as functions on the integers with period formula_21, (i.e., as periodic bi-infinite sequences: formula_64) or equivalently, as functions on the cyclic group of order formula_21 (formula_1 or formula_67) geometrically , on (the vertices of) the regular : this is a discrete analog to periodic functions on the real line or circle. Then, from the perspective of operator theory, a circulant matrix is the kernel of a discrete integral transform, namely the convolution operator for the function formula_68; this is a discrete circular convolution. The formula for the convolution of the functions formula_69 is formula_70 (recall that the sequences are periodic) which is the product of the vector formula_71 by the circulant matrix for formula_72. The discrete Fourier transform then converts convolution into multiplication, which in the matrix setting corresponds to diagonalization . The formula_73-algebra of all circulant matrices with complex entries is isomorphic to the group formula_73-algebra of formula_67. Symmetric circulant matrices. For a symmetric circulant matrix formula_3 one has the extra condition that formula_77. Thus it is determined by formula_78 elements. formula_79 The eigenvalues of any real symmetric matrix are real. The corresponding eigenvalues become: formula_80 for formula_21 even, and formula_82 for formula_21 odd, where formula_84 denotes the real part of formula_85. This can be further simplified by using the fact that formula_86. 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 formula_87 and its determinant and all eigenvalues are real. If "n" is even the first two rows necessarily takes the form formula_88 in which the first element formula_89 in the top second half-row is real. If "n" is odd we get formula_90 Tee has discussed constraints on the eigenvalues for the Hermitian condition. Applications. In linear equations. Given a matrix equation formula_91 where formula_3 is a circulant square matrix of size formula_21 we can write the equation as the circular convolution formula_94 where formula_95 is  the first column of formula_3, and the vectors formula_95, formula_98 and formula_99 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 formula_100 so that formula_101 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.