Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Circulant matrix
Summary
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 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.
An circulant matrix takes the form
or the transpose of this form (by choice of notation). When the term is a square matrix, then the matrix is called a block-circulant matrix.
A circulant matrix is fully specified by one vector, , which appears as the first column (or row) of . The remaining columns (and rows, resp.) of are each cyclic permutations of the vector with offset equal to the column (or row, resp.) index, if lines are indexed from 0 to . (Cyclic permutation of rows has the same effect as cyclic permutation of columns.) The last row of is the vector shifted by one in reverse.
Different sources define the circulant matrix in different ways, for example as above, or with the vector 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 is called the associated polynomial of matrix .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related concepts (12)
Fourier transform on finite groups
In mathematics, the Fourier transform on finite groups is a generalization of the discrete Fourier transform from cyclic to arbitrary finite groups. The Fourier transform of a function at a representation of is For each representation of , is a matrix, where is the degree of . The inverse Fourier transform at an element of is given by The convolution of two functions is defined as The Fourier transform of a convolution at any representation of is given by For functions , the Plancherel formula states where are the irreducible representations of .
Eigenvalues and eigenvectors
In linear algebra, an eigenvector (ˈaɪgənˌvɛktər) or characteristic vector of a linear transformation is a nonzero vector that changes at most by a constant factor when that linear transformation is applied to it. The corresponding eigenvalue, often represented by , is the multiplying factor. Geometrically, a transformation matrix rotates, stretches, or shears the vectors it acts upon. The eigenvectors for a linear transformation matrix are the set of vectors that are only stretched, with no rotation or shear.
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.
Related lectures (12)
Signal Representations
Covers the properties of signal/data representations using Fourier transformations and matrices.
Frequency Analysis: FFT Algorithm and Digital Filters
Explores the FFT algorithm, cost analysis, and digital filters in frequency analysis.
Discrete-Time Fourier Transform: Properties
Explores the properties of Discrete-Time Fourier Transform, including linearity, time and frequency shifts, time reversal, and convolution.