Circulant matrix

In <a href="/facts/Linear_algebra/8VaB4VWk">linear algebra</a>, a circulant matrix is a <a href="/facts/Square_matrix/5TP9mNNn">square matrix</a> in which all rows are composed of the same elements and each row is rotated one element to the right relative to the preceding row. It is a particular kind of <a href="/facts/Toeplitz_matrix/WAjSdlaW">Toeplitz matrix</a>.
In <a href="/facts/Numerical_analysis/QT9cYa9z">numerical analysis</a>, circulant matrices are important because they are <a href="/facts/Diagonalizable_matrix/y3MkyTCy">diagonalized</a> by a <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">discrete Fourier transform</a>, and hence <a href="/facts/Linear_equation/JfCgALwf">linear equations</a> that contain them may be quickly solved using a <a href="/facts/Fast_Fourier_transform/caT7UUCh">fast Fourier transform</a>. They can be interpreted analytically as the <a href="/facts/Integral_kernel/AB2yjHJJ">integral kernel</a> of a <a href="/facts/Convolution_operator/PVPrdz9J">convolution operator</a> on the <a href="/facts/Cyclic_group/JL5zfFuL">cyclic group</a> 
 
 
 
 
 C
 
 n
 
 
 
 
 {\displaystyle C_{n}}
 
 and hence frequently appear in formal descriptions of spatially invariant linear operations. This property is also critical in modern software defined radios, which utilize <a href="/facts/Orthogonal_Frequency_Division_Multiplexing/YhPkx5ql">Orthogonal Frequency Division Multiplexing</a> to spread the <a href="/facts/Symbols/GS8mTn0h">symbols</a> (bits) using a <a href="/facts/Cyclic_prefix/8PV9mw9k">cyclic prefix</a>. This enables the channel to be represented by a circulant matrix, simplifying channel equalization in the <a href="/facts/Frequency_domain/pyTVrUSq">frequency domain</a>.
In <a href="/facts/Cryptography/e94PEVau">cryptography</a>, a circulant matrix is used in the <a href="/facts/Rijndael_MixColumns/kRWfWEw9">MixColumns</a> step of the <a href="/facts/Advanced_Encryption_Standard/HdXGBY2Q">Advanced Encryption Standard</a>.

Circulant matrix open-in-new

Circulant matrix