Wikipedia / Circulant matrix
Wikipedia / Circulant matrix
In linear algebra, a circulant matrix is a square matrix is a single generating vector. Circulant matrices are a special class of Toeplitz matrices.
Every complex circulant matrix is diagonalized by the discrete Fourier transform (DFT). As a consequence, circulant matrices form a commutative algebra of normal matrices; the eigenvalues of a circulant matrix are the DFT of its generating vector; and matrix–vector products and nonsingular linear systems involving a circulant matrix can be computed with a fast Fourier transform arithmetic operations. Algebraically, multiplication by a circulant matrix is circular convolution on the cyclic group.
Circulant matrices arise wherever a linear operation is invariant under cyclic shifts. They can be interpreted analytically as the integral kernel of a convolution operator, and hence appear in signal and image processing with periodic boundary conditions, in discretizations of translation-invariant problems on periodic domains, and in the study of stationary stochastic processes. In orthogonal frequency-division multiplexing, the cyclic prefix prepended to each transmitted block makes the effective channel matrix circulant, so that channel equalization can be carried out separately on each component in the frequency domain.
In cryptography, a circulant matrix is used in the MixColumns step of the Advanced Encryption Standard.
Definition
circulant matrix or the transpose square matrix is called a block-circulant matrix.
are each cyclic permutations shifted by one in reverse.
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.
Properties
Eigenvectors and eigenvalues
The normalized eigenvectors-th root of unity is the imaginary unit.
(This can be understood by realizing that multiplication with a circulant matrix implements a convolution. In Fourier space, convolutions become multiplication. Hence the product of a circulant matrix with a Fourier mode yields a multiple of that Fourier mode, i.e. it is an eigenvector.)
The corresponding eigenvalues
Determinant
As a consequence of the explicit formula for the eigenvalues above, the determinant
Rank
Other properties
Any circulant is a matrix polynomial (namely, the associated polynomial) in the cyclic permutation matrix is given by the companion matrix
The set-dimensionalal vector space with respect to addition and scalar multiplication. This space can be interpreted as the space of functionss on the cyclic group of order, or equivalently as the group ring.
Circulant matrices form a commutative algebra.
For a nonsingular, its inverse is also circulant. For a singular circulant matrix, its Moore–Penrose pseudoinverse is circulant.
The discrete Fourier transform is defined as by
. This product can be readily calculated by a fast Fourier transform.
be the (monic) characteristic polynomial. Then the scaled derivative (see for the proof).
Analytic interpretation
Circulant matrices can be interpreted geometrically, which explains the connection with the discrete Fourier transform.
as functions on the integers) or equivalently, as functions on the cyclic group) geometrically, on (the vertices of) the regular n-gon: 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; this is a discrete circular convolution is
.
The discrete Fourier transform then converts convolution into multiplication, which in the matrix setting corresponds to diagonalization.
-algebra of all circulant matrices with complex entries is isomorphic
Relation to stationary processes
In statistics and signal processing, circulant matrices arise naturally as the covariance matrices of wide-sense stationary processes observed on a circular array or with periodic boundary conditions. More generally, the covariance matrix of a stationary process on a linear array is Toeplitz, and Toeplitz matrices are asymptotically circulant as the dimension grows. This asymptotic equivalence is the reason that DFT-based spectral analysis is asymptotically optimal for stationary processes: the DFT diagonalizes circulant matrices exactly and approximately diagonalizes Toeplitz matrices, so the DFT coefficients are asymptotically uncorrelated for stationary data.
Symmetric circulant matrices
For a symmetric
The eigenvalues of any real even odd denotes the real part even or odd.
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 and its determinant and all eigenvalues are real.
If n in the top second half-row is real.
If n
Tee has discussed constraints on the eigenvalues for the Hermitian condition.
Applications
In linear equations
Given a matrix equation
, we can write the equation as the circular convolution are cyclically extended in each direction. Using the circular convolution theorem, we can use the discrete Fourier transform
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/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 fieldss of prime order.
References
External links