Circulant matrix

In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is rotated one element to the right relative to the preceding row vector. 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 C n {displaystyle C_{n}} and hence frequently appear in formal descriptions of spatially invariant linear operations. In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is rotated one element to the right relative to the preceding row vector. 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 C n {displaystyle C_{n}} and hence frequently appear in formal descriptions of spatially invariant linear operations. In cryptography, a circulant matrix is used in the MixColumns step of the Advanced Encryption Standard. An n × n {displaystyle n imes n} circulant matrix C {displaystyle C} takes the form A circulant matrix is fully specified by one vector, c {displaystyle c} , which appears as the first column of C {displaystyle C} . The remaining columns of C {displaystyle C} are each cyclic permutations of the vector c {displaystyle c} with offset equal to the column index. The last row of C {displaystyle C} is the vector c {displaystyle c} in reverse order, and the remaining rows are each cyclic permutations of the last row. Note that different sources define the circulant matrix in different ways, for example with the coefficients corresponding to the first row rather than the first column of the matrix, or with a different direction of shift. The polynomial f ( x ) = c 0 + c 1 x + ⋯ + c n − 1 x n − 1 {displaystyle f(x)=c_{0}+c_{1}x+dots +c_{n-1}x^{n-1}} is called the associated polynomial of matrix C {displaystyle C} . The normalized eigenvectors of a circulant matrix are the Fourier modes. This can be understood by realizing that a circulant matrix implements a convolution.They are given by where ω j = exp ⁡ ( i 2 π j n ) {displaystyle omega _{j}=exp left(i{ frac {2pi j}{n}} ight)} are the n {displaystyle n} -th roots of unity and i {displaystyle i} is the imaginary unit.