In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices ...
, a circulant matrix is a
square matrix in which all
row vector
In linear algebra, a column vector with m elements is an m \times 1 matrix consisting of a single column of m entries, for example,
\boldsymbol = \begin x_1 \\ x_2 \\ \vdots \\ x_m \end.
Similarly, a row vector is a 1 \times n matrix for some n, c ...
s 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 linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant. For instance, the following matrix is a Toeplitz matrix:
:\qquad\begin
a & b ...
.
In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods ...
, circulant matrices are important because they are
diagonalized
In linear algebra, a square matrix A is called diagonalizable or non-defective if it is similar to a diagonal matrix, i.e., if there exists an invertible matrix P and a diagonal matrix D such that or equivalently (Such D are not unique.) F ...
by a
discrete Fourier transform
In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a comple ...
, 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
In mathematics (in particular, functional analysis), convolution is a mathematical operation on two functions ( and ) that produces a third function (f*g) that expresses how the shape of one is modified by the other. The term ''convolution'' ...
on the
cyclic group
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
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
In telecommunications, orthogonal frequency-division multiplexing (OFDM) is a type of digital transmission and a method of encoding digital data on multiple carrier frequencies. OFDM has developed into a popular scheme for wideband digital commun ...
to spread the
symbols (bits) using a
cyclic prefix
In telecommunications, the term cyclic prefix refers to the prefixing of a symbol, with a repetition of the end. The receiver is typically configured to discard the cyclic prefix samples, but the cyclic prefix serves two purposes:
* It provides a ...
. This enables the channel to be represented by a circulant matrix, simplifying channel equalization in the
frequency domain
In physics, electronics, control systems engineering, and statistics, the frequency domain refers to the analysis of mathematical functions or signals with respect to frequency, rather than time. Put simply, a time-domain graph shows how a s ...
.
In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, a circulant matrix is used in the
MixColumns step of the
Advanced Encryption Standard
The Advanced Encryption Standard (AES), also known by its original name Rijndael (), is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.
AES is a varian ...
.
Definition
An
circulant matrix
takes the form
or the
transpose
In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal;
that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations).
The tr ...
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 permutation
In mathematics, and in particular in group theory, a cyclic permutation (or cycle) is a permutation of the elements of some set ''X'' which maps the elements of some subset ''S'' of ''X'' to each other in a cyclic fashion, while fixing (that is, ma ...
s 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
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
is called the ''associated polynomial'' of matrix
.
Properties
Eigenvectors and eigenvalues
The normalized
eigenvector
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted ...
s of a circulant matrix are the Fourier modes, namely,
where
is a primitive
-th
root of unity
In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important ...
and
is the
imaginary unit
The imaginary unit or unit imaginary number () is a solution to the quadratic equation x^2+1=0. Although there is no real number with this property, can be used to extend the real numbers to what are called complex numbers, using addition an ...
.
(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
eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted ...
s are given by
Determinant
As a consequence of the explicit formula for the eigenvalues above,
the
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if a ...
of a circulant matrix can be computed as:
Since taking the transpose does not change the eigenvalues of a matrix, an equivalent formulation is
Rank
The
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* ...
of a circulant matrix
is equal to
, where
is the
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
of the polynomial
.
Other properties
* Any circulant is a matrix polynomial (namely, the associated polynomial) in the cyclic
permutation matrix :
where
is given by
* The
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of
circulant matrices forms an
-
dimensional
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coordi ...
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
with respect to addition and scalar multiplication. This space can be interpreted as the space of functions on the
cyclic group
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
of
order ,
, or equivalently as the
group ring
In algebra, a group ring is a free module and at the same time a ring, constructed in a natural way from any given ring and any given group. As a free module, its ring of scalars is the given ring, and its basis is the set of elements of the giv ...
of
.
* Circulant matrices form a
commutative algebra
Commutative algebra, first known as ideal theory, is the branch of algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra. Prom ...
, since for any two given circulant matrices
and
, the sum
is circulant, the product
is circulant, and
.
* For a nonsingular circulant matrix
, its inverse
is also circulant. For a singular circulant matrix, its
Moore–Penrose pseudoinverse is circulant.
* The matrix
that is composed of the
eigenvectors
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted ...
of a circulant matrix is related to the
discrete Fourier transform
In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a comple ...
and its inverse transform:
Consequently the matrix
diagonalizes . In fact, we have
where
is the first column of
. The eigenvalues of
are given by the product
. This product can be readily calculated by a
fast Fourier transform. Conversely, for any diagonal matrix
, the product
is circulant.
*Let
be the (
monic)
characteristic polynomial of an
circulant matrix
, and let
be the
derivative
In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. ...
of
. Then the polynomial
is the characteristic polynomial of the following
submatrix of
:
(see for the proof).
Analytic interpretation
Circulant matrices can be interpreted geometrically, which explains the connection with the discrete Fourier transform.
Consider vectors in
as functions on the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s with period
, (i.e., as periodic bi-infinite sequences:
) or equivalently, as functions on the
cyclic group
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
of order
(
or
) 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
In mathematics, operator theory is the study of linear operators on function spaces, beginning with differential operators and integral operators. The operators may be presented abstractly by their characteristics, such as bounded linear operators ...
, a circulant matrix is the kernel of a discrete
integral transform
In mathematics, an integral transform maps a function from its original function space into another function space via integration, where some of the properties of the original function might be more easily characterized and manipulated than in ...
, namely the
convolution operator
In mathematics (in particular, functional analysis), convolution is a mathematical operation on two functions ( and ) that produces a third function (f*g) that expresses how the shape of one is modified by the other. The term ''convolution'' ...
for the function
; this is a discrete
circular convolution Circular convolution, also known as cyclic convolution, is a special case of periodic convolution, which is the convolution of two periodic functions that have the same period. Periodic convolution arises, for example, in the context of the discre ...
. The formula for the convolution of the functions
is
(recall that the sequences are periodic)
which is the product of the vector
by the circulant matrix for
.
The discrete Fourier transform then converts convolution into multiplication, which in the matrix setting corresponds to diagonalization.
The
-algebra of all circulant matrices with
complex
Complex commonly refers to:
* Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe
** Complex system, a system composed of many components which may interact with each ...
entries is
isomorphic to the group
-algebra of
.
Symmetric circulant matrices
For a symmetric circulant matrix
one has the extra condition that
.
Thus it is determined by
elements.
The eigenvalues of any real symmetric matrix are real.
The corresponding eigenvalues become:
for
even
Even may refer to:
General
* Even (given name), a Norwegian male personal name
* Even (surname)
* Even (people), an ethnic group from Siberia and Russian Far East
** Even language, a language spoken by the Evens
* Odd and Even, a solitaire game w ...
, and
for
odd
Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric.
Odd may also refer to:
Acronym
* ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
, where
denotes the
real part
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
of
.
This can be further simplified by using the fact that
.
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 {{Short description, none
Numerous things are named after the French mathematician Charles Hermite (1822–1901):
Hermite
* Cubic Hermite spline, a type of third-degree spline
* Gauss–Hermite quadrature, an extension of Gaussian quadrature m ...
. In this case
and its determinant and all eigenvalues are real.
If ''n'' is even the first two rows necessarily takes the form
in which the first element
in the top second half-row is real.
If ''n'' is odd we get
Tee
has discussed constraints on the eigenvalues for the Hermitian condition.
Applications
In linear equations
Given a matrix equation
where
is a circulant square matrix of size
we can write the equation as the
circular convolution Circular convolution, also known as cyclic convolution, is a special case of periodic convolution, which is the convolution of two periodic functions that have the same period. Periodic convolution arises, for example, in the context of the discre ...
where
is the first column of
, and the vectors
,
and
are cyclically extended in each direction. Using the
circular convolution theorem, we can use the
discrete Fourier transform
In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a comple ...
to transform the cyclic convolution into component-wise multiplication
so that
This algorithm is much faster than the standard
Gaussian elimination, especially if a
fast Fourier transform is used.
In graph theory
In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
or
digraph whose
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
is circulant is called a
circulant graph (or digraph). Equivalently, a graph is circulant if its
automorphism group
In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...
contains a full-length cycle. The
Möbius ladder
In graph theory, the Möbius ladder , for even numbers , is formed from an by adding edges (called "rungs") connecting opposite pairs of vertices in the cycle. It is a cubic, circulant graph, so-named because (with the exception of (the utili ...
s are examples of circulant graphs, as are the
Paley graph
In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, ...
s for
fields
Fields may refer to:
Music
* Fields (band), an indie rock band formed in 2006
* Fields (progressive rock band), a progressive rock band formed in 1971
* ''Fields'' (album), an LP by Swedish-based indie rock band Junip (2010)
* "Fields", a song b ...
of
prime
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
order.
References
External links
* R. M. Gray
Toeplitz and Circulant Matrices: A Review
*
IPython Notebook demonstrating properties of circulant matrices
{{Matrix classes
Numerical linear algebra
Matrices
Latin squares
Determinants