HOME

TheInfoList



OR:

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 matrix (mathemat ...
, a circulant matrix is a
square matrix In mathematics, a square matrix is a Matrix (mathematics), matrix with the same number of rows and columns. An ''n''-by-''n'' matrix is known as a square matrix of order Any two square matrices of the same order can be added and multiplied. Squ ...
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 Toeplitz matrix. In
numerical analysis Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, circulant matrices are important because they are diagonalized by a
discrete Fourier transform In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced Sampling (signal processing), samples of a function (mathematics), function into a same-length sequence of equally-spaced samples of the discre ...
, and hence
linear equation In mathematics, a linear equation is an equation that may be put in the form a_1x_1+\ldots+a_nx_n+b=0, where x_1,\ldots,x_n are the variables (or unknowns), and b,a_1,\ldots,a_n are the coefficients, which are often real numbers. The coeffici ...
s that contain them may be quickly solved using a
fast Fourier transform A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). A Fourier transform converts a signal from its original domain (often time or space) to a representation in ...
. They can be interpreted analytically as the
integral kernel In mathematics, an integral transform is a type of transform (mathematics), transform that maps a function (mathematics), function from its original function space into another function space via integral, integration, where some of the propert ...
of a convolution operator on the
cyclic group In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...
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 Orthogonal Frequency Division Multiplexing to spread the
symbols A symbol is a mark, sign, or word that indicates, signifies, or is understood as representing an idea, object, or relationship. Symbols allow people to go beyond what is known or seen by creating linkages between otherwise different concep ...
(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 gu ...
. This enables the channel to be represented by a circulant matrix, simplifying channel equalization in the
frequency domain In mathematics, physics, electronics, control systems engineering, and statistics, the frequency domain refers to the analysis of mathematical functions or signals with respect to frequency (and possibly phase), rather than time, as in time ser ...
. In
cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
, 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 variant ...
.


Definition

An n \times n circulant matrix C takes the form C = \begin c_0 & c_ & \cdots & c_2 & c_1 \\ c_1 & c_0 & c_ & & c_2 \\ \vdots & c_1 & c_0 & \ddots & \vdots \\ c_ & & \ddots & \ddots & c_ \\ c_ & c_ & \cdots & c_1 & c_0 \\ \end or the
transpose In linear algebra, the transpose of a Matrix (mathematics), 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 ...
of this form (by choice of notation). If each c_i is a p \times p square
matrix Matrix (: matrices or matrixes) or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the m ...
, then the np \times np matrix C is called a block-circulant matrix. A circulant matrix is fully specified by one vector, c, which appears as the first column (or row) of C. The remaining columns (and rows, resp.) of C are each
cyclic permutation In mathematics, and in particular in group theory, a cyclic permutation is a permutation consisting of a single cycle. In some cases, cyclic permutations are referred to as cycles; if a cyclic permutation has ''k'' elements, it may be called a ''k ...
s of the vector c with offset equal to the column (or row, resp.) index, if lines are indexed from 0 to n-1. (Cyclic permutation of rows has the same effect as cyclic permutation of columns.) The last row of C is the vector c shifted by one in reverse. Different sources define the circulant matrix in different ways, for example as above, or with the vector c 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 a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
f(x) = c_0 + c_1 x + \dots + c_ x^ is called the ''associated polynomial'' of the matrix C.


Properties


Eigenvectors and eigenvalues

The normalized
eigenvector In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by ...
s of a circulant matrix are the Fourier modes, namely, v_j=\frac \left(1, \omega^j, \omega^, \ldots, \omega^\right)^,\quad j = 0, 1, \ldots, n-1, where \omega=\exp \left(\tfrac\right) is a primitive n-th
root of unity In mathematics, a root of unity is any complex number that yields 1 when exponentiation, raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory ...
and i is the
imaginary unit The imaginary unit or unit imaginary number () is a mathematical constant that is a solution to the quadratic equation Although there is no real number with this property, can be used to extend the real numbers to what are called complex num ...
. (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 is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a ...
s are given by \lambda_j = c_0+c_ \omega^ + c_ \omega^ + \dots + c_ \omega^,\quad j = 0, 1, \dots, n-1.


Determinant

As a consequence of the explicit formula for the eigenvalues above, the
determinant In mathematics, the determinant is a Scalar (mathematics), scalar-valued function (mathematics), function of the entries of a square matrix. The determinant of a matrix is commonly denoted , , or . Its value characterizes some properties of the ...
of a circulant matrix can be computed as: \det C = \prod_^ (c_0 + c_ \omega^j + c_ \omega^ + \dots + c_1\omega^). Since taking the transpose does not change the eigenvalues of a matrix, an equivalent formulation is \det C = \prod_^ (c_0 + c_1 \omega^j + c_2 \omega^ + \dots + c_\omega^) = \prod_^ f(\omega^j).


Rank

The
rank A rank is a position in a hierarchy. It can be formally recognized—for example, cardinal, chief executive officer, general, professor—or unofficial. People Formal ranks * Academic rank * Corporate title * Diplomatic rank * Hierarchy ...
of a circulant matrix C is equal to n - d where d is the degree of the polynomial \gcd( f(x), x^n - 1).


Other properties

* Any circulant is a matrix polynomial (namely, the associated polynomial) in the cyclic
permutation matrix In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column with all other entries 0. An permutation matrix can represent a permutation of elements. ...
P: C = c_0 I + c_1 P + c_2 P^2 + \dots + c_ P^ = f(P), where P is given by the
companion matrix In linear algebra, the Frobenius companion matrix of the monic polynomial p(x)=c_0 + c_1 x + \cdots + c_x^ + x^n is the square matrix defined as C(p)=\begin 0 & 0 & \dots & 0 & -c_0 \\ 1 & 0 & \dots & 0 & -c_1 \\ 0 & 1 & \dots & 0 & -c_2 \\ \ ...
P = \begin 0&0&\cdots&0&1\\ 1&0&\cdots&0&0\\ 0&\ddots&\ddots&\vdots&\vdots\\ \vdots&\ddots&\ddots&0&0\\ 0&\cdots&0&1&0 \end. * 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 n \times n circulant matrices forms an n-
dimension 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 coo ...
al
vector space In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
with respect to addition and scalar multiplication. This space can be interpreted as the space of functions on the
cyclic group In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...
of
order Order, ORDER or Orders may refer to: * A socio-political or established or existing order, e.g. World order, Ancien Regime, Pax Britannica * Categorization, the process in which ideas and objects are recognized, differentiated, and understood ...
n, C_n, 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 gi ...
of C_n. * Circulant matrices form a
commutative algebra Commutative algebra, first known as ideal theory, is the branch of algebra that studies commutative rings, their ideal (ring theory), ideals, and module (mathematics), modules over such rings. Both algebraic geometry and algebraic number theo ...
, since for any two given circulant matrices A and B, the sum A + B is circulant, the product AB is circulant, and AB = BA. * For a nonsingular circulant matrix A, its inverse A^ is also circulant. For a singular circulant matrix, its Moore–Penrose pseudoinverse A^+ is circulant. * The
discrete Fourier transform In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced Sampling (signal processing), samples of a function (mathematics), function into a same-length sequence of equally-spaced samples of the discre ...
matrix of order n is defined as by F_n = (f_) \text f_ = e^, \,\text 0 \leq j,k \leq n-1. There are important connections between circulant matrices and the DFT matrices. In fact, it can be shown that C = F_n^\operatorname(F_n c) F_n , where c is the first column of C. The eigenvalues of C are given by the product F_n c. This product can be readily calculated by a
fast Fourier transform A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). A Fourier transform converts a signal from its original domain (often time or space) to a representation in ...
. *Let p(x) be the ( monic)
characteristic polynomial In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...
of an n \times n circulant matrix C. Then the scaled
derivative In mathematics, the derivative is a fundamental tool that quantifies the sensitivity to change of a function's output with respect to its input. The derivative of a function of a single variable at a chosen input value, when it exists, is t ...
\fracp'(x) is the characteristic polynomial of the following (n-1)\times(n-1) submatrix of C: C_ = \begin c_0 & c_ & \cdots & c_3 & c_2 \\ c_1 & c_0 & c_ & & c_3 \\ \vdots & c_1 & c_0 & \ddots & \vdots \\ c_ & & \ddots & \ddots & c_ \\ c_ & c_ & \cdots & c_ & c_0 \\ \end (see for the
proof Proof most often refers to: * Proof (truth), argument or sufficient evidence for the truth of a proposition * Alcohol proof, a measure of an alcoholic drink's strength Proof may also refer to: Mathematics and formal logic * Formal proof, a co ...
).


Analytic interpretation

Circulant matrices can be interpreted geometrically, which explains the connection with the discrete Fourier transform. Consider vectors in \R^n as functions on the
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s with period n, (i.e., as periodic bi-infinite sequences: \dots,a_0,a_1,\dots,a_,a_0,a_1,\dots) or equivalently, as functions on the
cyclic group In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...
of order n (denoted C_n or \Z/n\Z) geometrically, on (the vertices of) the regular : this is a discrete analog to periodic functions on the
real line A number line is a graphical representation of a straight line that serves as spatial representation of numbers, usually graduated like a ruler with a particular origin (geometry), origin point representing the number zero and evenly spaced mark ...
or
circle A circle is a shape consisting of all point (geometry), points in a plane (mathematics), plane that are at a given distance from a given point, the Centre (geometry), centre. The distance between any point of the circle and the centre is cal ...
. 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 operato ...
, a circulant matrix is the kernel of a discrete
integral transform In mathematics, an integral transform is a type of transform that 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 charac ...
, namely the convolution operator for the function (c_0,c_1,\dots,c_); this is a discrete circular convolution. The formula for the convolution of the functions (b_i) := (c_i) * (a_i) is : b_k = \sum_^ a_i c_ (recall that the sequences are periodic) which is the product of the vector (a_i) by the circulant matrix for (c_i). The discrete Fourier transform then converts convolution into multiplication, which in the matrix setting corresponds to diagonalization. The C^*-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 In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
to the group C^*-algebra of \Z/n\Z.


Symmetric circulant matrices

For a
symmetric Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is invariant under some transformations ...
circulant matrix C one has the extra condition that c_=c_i. Thus it is determined by \lfloor n/2\rfloor + 1 elements. C = \begin c_0 & c_1 & \cdots & c_2 & c_1 \\ c_1 & c_0 & c_1 & & c_2 \\ \vdots & c_1 & c_0 & \ddots & \vdots \\ c_2 & & \ddots & \ddots & c_1 \\ c_1 & c_2 & \cdots & c_1 & c_0 \\ \end. The eigenvalues of any real symmetric matrix are real. The corresponding eigenvalues \vec= \sqrt n \cdot F_n^ c become: \begin \lambda_k & = & c_0 + c_ e^ + 2\sum_^ c_j \cos \\ & = & c_0+ c_ \omega_k^ + 2 c_1 \Re \omega_k + 2 c_2 \Re \omega_k^2 + \dots + 2c_ \Re \omega_k^ \end for n even, and \begin \lambda_k & = & c_0 + 2\sum_^ c_j \cos \\ & = & c_0 + 2 c_1 \Re \omega_k + 2 c_2 \Re \omega_k^2 + \dots + 2c_ \Re \omega_k^ \end for n odd, where \Re z 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 z. This can be further simplified by using the fact that \Re \omega_k^j = \Re e^ = \cos(-\frac \cdot kj) and \omega_k^=e^ =e^ depending on k 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 {{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 me ...
. In this case c_ = c_i^*, \; i \le n/2 and its determinant and all eigenvalues are real. If ''n'' is even the first two rows necessarily takes the form \begin r_0 & z_1 & z_2 & r_3 & z_2^* & z_1^* \\ z_1^* & r_0 & z_1 & z_2 & r_3 & z_2^* \\ \dots \\ \end. in which the first element r_3 in the top second half-row is real. If ''n'' is odd we get \begin r_0 & z_1 & z_2 & z_2^* & z_1^* \\ z_1^* & r_0 & z_1 & z_2 & z_2^* \\ \dots\\ \end. Tee has discussed constraints on the eigenvalues for the Hermitian condition.


Applications


In linear equations

Given a matrix equation : C \mathbf = \mathbf, where C is a circulant matrix of size n, we can write the equation as the circular convolution \mathbf \star \mathbf = \mathbf, where \mathbf c is the first column of C, and the vectors \mathbf c, \mathbf x and \mathbf b 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 Sampling (signal processing), samples of a function (mathematics), function into a same-length sequence of equally-spaced samples of the discre ...
to transform the cyclic convolution into component-wise multiplication \mathcal_(\mathbf \star \mathbf) = \mathcal_(\mathbf) \mathcal_(\mathbf) = \mathcal_(\mathbf) so that \mathbf = \mathcal_n^ \left \left( \frac \right)_\, \right. This algorithm is much faster than the standard
Gaussian elimination In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can a ...
, especially if a
fast Fourier transform A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). A Fourier transform converts a signal from its original domain (often time or space) to a representation in ...
is used.


In graph theory

In
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, 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 discret ...
or digraph whose
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...
is circulant is called a circulant graph/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 util ...
s are examples of circulant graphs, as are the
Paley graph In mathematics, Paley graphs are 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, which yiel ...
s for fields 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

*
IPython Notebook demonstrating properties of circulant matrices
{{Authority control Numerical linear algebra Matrices (mathematics) Latin squares Determinants