Circulant matrix
Encyclopedia
In linear algebra
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...

, a circulant matrix is a special kind of Toeplitz matrix
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...

 where each row vector is rotated one element to the right relative to the preceding row vector. In numerical analysis
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....

, circulant matrices are important because they are diagonalized by a discrete Fourier transform
Discrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...

, and hence linear equation
Linear equation
A linear equation is an algebraic equation in which each term is either a constant or the product of a constant and a single variable....

s that contain them may be quickly solved using a fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...

. They can be interpreted analytically as the integral kernel of a convolution operator on the cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...

 
In cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, a circulant matrix is used in the MixColumns step of the Advanced Encryption Standard
Advanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...

.

Definition

An circulant matrix takes the form


A circulant matrix is fully specified by one vector, , which appears as the first column of . The remaining columns of are each cyclic permutation
Cyclic permutation
A cyclic permutation or circular permutation is a permutation built from one or more sets of elements in cyclic order.The notion "cyclic permutation" is used in different, but related ways:- Definition 1 :right|mapping of permutation...

s of the vector with offset equal to the column index. The last row of is the vector in reverse order, and the remaining rows are each cyclic permutation
Cyclic permutation
A cyclic permutation or circular permutation is a permutation built from one or more sets of elements in cyclic order.The notion "cyclic permutation" is used in different, but related ways:- Definition 1 :right|mapping of permutation...

s of the last row. Note that different sources define the circulant matrix in different ways, for example with the coefficients corresponding to the first row rather than the first column of the matrix, or with a different direction of shift.

Eigenvectors and eigenvalues

The eigenvectors of a circulant matrix are given by

where are the n-th roots of unity and is the imaginary unit
Imaginary unit
In mathematics, the imaginary unit allows the real number system ℝ to be extended to the complex number system ℂ, which in turn provides at least one root for every polynomial . The imaginary unit is denoted by , , or the Greek...

.

The corresponding eigenvalues are then given by

Circulant determinant

As a consequence of the explicit formula for the eigenvalues above,
the determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...

 of circulant matrix can be computed as:
Since taking transpose does not change the eigenvalues of a matrix, an equivalent formulation is

Properties

  • We have

where P is the 'cyclic permutation' matrix given by
  • The set of circulant matrices forms an n-dimensional vector space
    Vector space
    A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

    ; this can be interpreted as the space of functions on the cyclic group
    Cyclic group
    In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...

     of order n, or equivalently the group ring
    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 one-to-one with the given group. As a ring, its addition law is that of the free...

    .

  • Circulant matrices form a commutative algebra
    Commutative algebra
    Commutative algebra is the branch of abstract algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra...

    , since for any two given circulant matrices and , the sum is circulant, the product is circulant, and .

  • The eigenvectors of a circulant matrix of a given size are the columns of the unitary discrete Fourier transform matrix of the same size. The latter matrix is defined by
Thus, the matrix diagonalizes
Diagonalizable matrix
In linear algebra, a square matrix A is called diagonalizable if it is similar to a diagonal matrix, i.e., if there exists an invertible matrix P such that P −1AP is a diagonal matrix...

 C. In fact, we have
where is the first column of . Thus, the eigenvalues of are given by the product . This product can be readily calculated by a Fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...

.

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
The circular convolution, also known as cyclic convolution, of two aperiodic functions occurs when one of them is convolved in the normal way with a periodic summation of the other function.  That situation arises in the context of the Circular convolution theorem...


where is the first column of , and the vectors , and are cyclically extended in each direction. Using the results of the circular convolution theorem, we can use the discrete Fourier transform
Discrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...

 to transform the cyclic convolution into component-wise multiplication


so that


This algorithm is much faster than the standard Gaussian elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...

, especially if a fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...

 is used.

Analytic interpretation

Circulant matrices can be interpreted geometrically, which explains the connection with the discrete Fourier transform.

Consider vectors in as functions on the integers with period n, (i.e., as periodic bi-infinite sequences: ) or equivalently, as functions on the cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...

 of order n, ( or ) 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
Operator theory
In mathematics, operator theory is the branch of functional analysis that focuses on bounded linear operators, but which includes closed operators and nonlinear operators.Operator theory also includes the study of algebras of operators....

, a circulant matrix is the kernel of a discrete integral transform, namely the convolution operator for the function this is a discrete circular convolution
Circular convolution
The circular convolution, also known as cyclic convolution, of two aperiodic functions occurs when one of them is convolved in the normal way with a periodic summation of the other function.  That situation arises in the context of the Circular convolution theorem...

. The formula for the convolution of the functions is (recall that the sequences are periodic)
which is the product of the vector of by the circulant matrix.

The discrete Fourier transform then converts convolution into multiplication, which in the matrix setting corresponds to diagonalization.

Application in graph theory

In graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 or digraph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...

 whose adjacency matrix
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...

 is circulant is called a circulant graph (or digraph). Equivalently, a graph is circulant if its automorphism group contains a full-length cycle. The Möbius ladder
Möbius ladder
In graph theory, the Möbius ladder Mn is a cubic circulant graph with an even number n of vertices, formed from an n-cycle by adding edges connecting opposite pairs of vertices in the cycle...

s are examples of circulant graphs, as are the Paley graph
Paley graph
In mathematics, and specifically graph theory, Paley graphs, named after Raymond Paley, are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ in a quadratic residue. The Paley graphs form an infinite family of conference...

s for fields of prime order.

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK