Editing Circulant matrix

{{short description|Linear algebra matrix}}
{{For|the symmetric graphs|Circulant graph}}

In [[linear algebra]], a '''circulant matrix''' is a [[square matrix]] 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]], circulant matrices are important because they are [[Diagonalizable matrix#Diagonalization|diagonalized]] by a [[discrete Fourier transform]], and hence [[linear equation]]s that contain them may be quickly solved using a [[fast Fourier transform]].<ref>{{cite book |author-link=Philip J. Davis |first=Philip J |last=Davis |title=Circulant Matrices |publisher=Wiley |location=New York |date=1970 |isbn=0-471-05771-1 |oclc=1408988930 }}</ref>  They can be [[#Analytic interpretation|interpreted analytically]] as the [[integral kernel]] of a [[convolution operator]] on the [[cyclic group]] <math>C_n</math> 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 [[Rijndael MixColumns|MixColumns]] step of the [[Advanced Encryption Standard]].

==Definition==

An <math>n \times n</math> '''circulant matrix''' <math>C</math> takes the form
<math display="block">C = \begin{bmatrix}
c_0      & c_{n-1} & \cdots  & c_2     & c_1     \\
c_1      & c_0     & c_{n-1} &         & c_2     \\
\vdots   & c_1     & c_0     & \ddots  & \vdots  \\
c_{n-2}  &         & \ddots  & \ddots  & c_{n-1} \\
c_{n-1}  & c_{n-2} & \cdots  & c_1     & c_0     \\
\end{bmatrix}</math>
or the [[transpose]] of this form (by choice of notation). If each <math>c_i</math> is a <math>p \times p</math> square [[matrix (mathematics)|matrix]], then the <math>np \times np</math> matrix <math>C</math> is called a '''block-circulant matrix'''.

A circulant matrix is fully specified by one vector, <math>c</math>, which appears as the first column (or row) of <math>C</math>.  The remaining columns (and rows, resp.) of <math>C</math> are each [[cyclic permutation]]s of the vector <math>c</math> with offset equal to the column (or row, resp.) index, if lines are indexed from <math>0</math> to <math>n-1</math>.  (Cyclic permutation of rows has the same effect as cyclic permutation of columns.)  The last row of <math>C</math> is the vector <math>c</math> shifted by one in reverse.

Different sources define the circulant matrix in different ways, for example as above, or with the vector <math>c</math> 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]] <math>f(x) = c_0 + c_1 x + \dots + c_{n-1} x^{n-1}</math> is called the ''associated polynomial'' of the matrix <math>C</math>.

== Properties ==

=== Eigenvectors and eigenvalues ===

The normalized [[eigenvector]]s of a circulant matrix are the Fourier modes, namely,
<math display="block">v_j=\frac{1}{\sqrt{n}} \left(1, \omega^j, \omega^{2j}, \ldots, \omega^{(n-1)j}\right)^{T},\quad j = 0, 1, \ldots, n-1,</math>
where <math>\omega=\exp \left(\tfrac{2\pi i}{n}\right)</math> is a primitive <math>n</math>-th [[root of unity]] and <math>i</math> 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 [[eigenvalue]]s are given by
<math display="block">\lambda_j = c_0+c_{1} \omega^{-j} + c_{2} \omega^{-2j} + \dots + c_{n-1} \omega^{-(n-1)j},\quad j = 0, 1, \dots, n-1.</math>

=== Determinant ===

As a consequence of the explicit formula for the eigenvalues above, 
the [[determinant]] of a circulant matrix can be computed as:
<math display="block">\det C = \prod_{j=0}^{n-1} (c_0 + c_{n-1} \omega^j + c_{n-2} \omega^{2j} + \dots + c_1\omega^{(n-1)j}).</math>
Since taking the transpose does not change the eigenvalues of a matrix, an equivalent formulation is
<math display="block">\det C
= \prod_{j=0}^{n-1} (c_0 + c_1 \omega^j + c_2 \omega^{2j} + \dots + c_{n-1}\omega^{(n-1)j})
= \prod_{j=0}^{n-1} f(\omega^j).</math>

=== Rank ===

The [[rank (linear algebra)|rank]] of a circulant matrix <math>C</math> is equal to <math>n - d</math> where <math>d</math> is the [[degree of a polynomial|degree]] of the polynomial <math>\gcd( f(x), x^n - 1)</math>.<ref>{{cite journal |author=A. W. Ingleton |title=The Rank of Circulant Matrices |journal=J. London Math. Soc. |year=1956 |volume=s1-31 |issue=4 |pages=445–460 |doi=10.1112/jlms/s1-31.4.445}}</ref>

=== Other properties ===

* Any circulant is a matrix polynomial (namely, the associated polynomial) in the cyclic [[permutation matrix]] <math>P</math>: <math display="block"> C = c_0 I + c_1 P + c_2 P^2 + \dots + c_{n-1} P^{n-1} = f(P),</math> where <math>P</math> is given by the [[companion matrix]] <math display="block">P = \begin{bmatrix}
 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{bmatrix}.</math>
* The [[set (mathematics)|set]] of <math>n \times n</math> circulant matrices forms an <math>n</math>-[[dimension (vector space)|dimension]]al [[vector space]] with respect to addition and scalar multiplication.  This space can be interpreted as the space of [[function (mathematics)|function]]s on the [[cyclic group]] of [[order of a group|order]] <math>n</math>, <math>C_n</math>, or equivalently as the [[group ring]] of <math>C_n</math>.
* Circulant matrices form a [[commutative algebra (structure)|commutative algebra]], since for any two given circulant matrices <math>A</math> and <math>B</math>, the sum <math>A + B</math> is circulant, the product <math>AB</math> is circulant, and <math>AB = BA</math>.
* For a [[nonsingular matrix|nonsingular]] circulant matrix <math>A</math>, its [[inverse matrix|inverse]] <math>A^{-1}</math> is also circulant. For a singular circulant matrix, its [[Moore–Penrose inverse|Moore–Penrose pseudoinverse]] <math>A^+</math> is circulant.
* The [[Discrete Fourier transform|discrete Fourier transform]] matrix of order <math>n</math> is defined as by
<math display="block">F_n = (f_{jk}) \text{ with } f_{jk} = e^{-2\pi i/n \cdot jk}, \,\text{for } 0 \leq j,k \leq n-1.</math>
There are important connections between circulant matrices and the DFT matrices. In fact, it can be shown that 
<math display="block">C = F_n^{-1}\operatorname{diag}(F_n c) F_n ,</math> where <math>c</math> is the first column of <math>C</math>. The eigenvalues of <math>C</math> are given by the product <math>F_n c</math>. This product can be readily calculated by a [[fast Fourier transform]].<ref>{{Citation | last1=Golub | first1=Gene H. | author1-link=Gene H. Golub | last2=Van Loan | first2=Charles F. | author2-link=Charles F. Van Loan | title=Matrix Computations | chapter=§4.7.7 Circulant Systems | publisher=Johns Hopkins | edition=3rd | isbn=978-0-8018-5414-9 | year=1996}}</ref>
*Let <math>p(x)</math> be the ([[monic polynomial|monic]]) [[characteristic polynomial]] of an <math>n \times n</math> circulant matrix <math>C</math>. Then the scaled [[derivative]] <math display="inline">\frac{1}{n}p'(x)</math> is the characteristic polynomial of the following <math>(n-1)\times(n-1)</math> submatrix of <math>C</math>: <math display="block">C_{n-1} = \begin{bmatrix}
 c_0     & c_{n-1} & \cdots  & c_3     & c_2     \\
 c_1     & c_0     & c_{n-1} &         & c_3     \\
 \vdots  & c_1     & c_0     & \ddots  & \vdots  \\
 c_{n-3} &         & \ddots  & \ddots  & c_{n-1} \\
 c_{n-2} & c_{n-3} & \cdots  & c_{1}   & c_0     \\
\end{bmatrix}</math> (see <ref>{{Citation | last1=Kushel | first1=Olga | last2=Tyaglov | first2=Mikhail | title=Circulants and critical points of polynomials |journal = Journal of Mathematical Analysis and Applications| date=July 15, 2016| issn=0022-247X| pages=634–650|volume=439|issue=2| doi= 10.1016/j.jmaa.2016.03.005|arxiv=1512.07983}}</ref> for the [[mathematical proof|proof]]).

==Analytic interpretation==
Circulant matrices can be interpreted [[geometry|geometrically]], which explains the connection with the discrete Fourier transform.

Consider vectors in <math>\R^n</math> as functions on the [[integer]]s with period <math>n</math>, (i.e., as periodic bi-infinite sequences: <math>\dots,a_0,a_1,\dots,a_{n-1},a_0,a_1,\dots</math>) or equivalently, as functions on the [[cyclic group]] of order <math>n</math> (denoted <math>C_n</math> or <math>\Z/n\Z</math>) geometrically, on (the vertices of) the [[regular polygon|regular {{nowrap|<math>n</math>-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]] for the function <math>(c_0,c_1,\dots,c_{n-1})</math>; this is a discrete [[circular convolution]]. The formula for the convolution of the functions <math>(b_i) := (c_i) * (a_i)</math> is
: <math>b_k = \sum_{i=0}^{n-1} a_i c_{k-i}</math>
(recall that the sequences are periodic)
which is the product of the vector <math>(a_i)</math> by the circulant matrix for <math>(c_i)</math>.

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

The <math>C^*</math>-algebra of all circulant matrices with [[complex number|complex]] entries is [[isomorphic]] to the group <math>C^*</math>-algebra of <math>\Z/n\Z.</math>

==Symmetric circulant matrices==
For a [[symmetric matrix|symmetric]] circulant matrix <math>C</math> one has the extra condition that <math>c_{n-i}=c_i</math>. 
Thus it is determined by <math>\lfloor n/2\rfloor + 1</math> elements. 
<math display="block">C = \begin{bmatrix}
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{bmatrix}.</math>

The eigenvalues of any [[real number|real]] symmetric matrix are real.
The corresponding eigenvalues <math> \vec{\lambda}= \sqrt n \cdot F_n^{\dagger} c</math> become:
<math display="block">\begin{array}{lcl} \lambda_k & = & c_0 + c_{n/2} e^{-\pi i \cdot k} + 2\sum_{j=1}^{\frac{n}{2}-1} c_j \cos{(-\frac{2\pi}{n}\cdot k j )} \\
& = & c_0+ c_{n/2} \omega_k^{n/2} + 2 c_1 \Re \omega_k + 2 c_2 \Re \omega_k^2 + \dots + 2c_{n/2-1} \Re \omega_k^{n/2-1} \end{array}</math>
for <math>n</math> [[parity (mathematics)|even]], and
<math display="block">\begin{array}{lcl} \lambda_k & = & c_0 + 2\sum_{j=1}^{\frac{n-1}{2}} c_j \cos{(-\frac{2\pi}{n}\cdot k j )}  \\ 
 & = & c_0 + 2 c_1 \Re \omega_k + 2 c_2 \Re \omega_k^2 + \dots + 2c_{(n-1)/2} \Re \omega_k^{(n-1)/2} \end{array}
</math>
for <math>n</math> [[parity (mathematics)|odd]], where <math>\Re z</math> denotes the [[complex number|real part]] of <math>z</math>.
This can be further simplified by using the fact that <math>\Re \omega_k^j = \Re e^{-\frac{2\pi i}{n} \cdot kj} = \cos(-\frac{2\pi}{n} \cdot kj)</math> and <math>\omega_k^{n/2}=e^{-\frac{2\pi i}{n} \cdot k \frac{n}{2}} =e^{-\pi i \cdot k}</math> depending on <math>k</math> even or odd.

Symmetric circulant matrices belong to the class  of [[bisymmetric matrix|bisymmetric matrices]].

==Hermitian circulant matrices==
The complex version of the circulant matrix, ubiquitous in communications theory, is usually [[Hermitian matrix|Hermitian]].  In this case <math>c_{n-i} = c_i^*, \; i \le n/2 </math> and its determinant and all eigenvalues are real.

If ''n'' is even the first two rows necessarily takes the form
<math display="block">
\begin{bmatrix}
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{bmatrix}.
</math>
in which the first element <math> r_3 </math> in the top second half-row is real.

If ''n'' is odd we get
<math display="block">
\begin{bmatrix}
r_0     & z_1 & z_2 & z_2^* & z_1^* \\
z_1^*  & r_0   & z_1 & z_2 & z_2^* \\
\dots\\
\end{bmatrix}.
</math>

Tee<ref>{{Cite journal|last=Tee|first=G.J.|date=2007|title=Eigenvectors of Block Circulant and Alternating Circulant Matrices|journal=New Zealand Journal of Mathematics|volume=36|pages=195–211 |url=https://core.ac.uk/download/pdf/148639176.pdf}}</ref> has discussed constraints on the eigenvalues for the Hermitian condition.

== Applications ==

===In linear equations===

Given a matrix equation
: <math>C \mathbf{x} = \mathbf{b},</math>
where <math>C</math> is a circulant matrix of size <math>n</math>, we can write the equation as the [[circular convolution]]
<math display="block">\mathbf{c} \star \mathbf{x} = \mathbf{b},</math>
where <math>\mathbf c</math> is the first column of <math>C</math>, and the vectors <math>\mathbf c</math>, <math>\mathbf x</math> and <math>\mathbf b</math> are cyclically extended in each direction. Using the [[discrete Fourier transform#Circular convolution theorem and cross-correlation theorem|circular convolution theorem]], we can use the [[discrete Fourier transform]] to transform the cyclic convolution into component-wise multiplication
<math display="block">\mathcal{F}_{n}(\mathbf{c} \star \mathbf{x}) = \mathcal{F}_{n}(\mathbf{c}) \mathcal{F}_{n}(\mathbf{x}) = \mathcal{F}_{n}(\mathbf{b})</math>
so that
<math display="block">\mathbf{x} = \mathcal{F}_n^{-1} \left[ \left(
\frac{(\mathcal{F}_n(\mathbf{b}))_{\nu}}
{(\mathcal{F}_n(\mathbf{c}))_{\nu}} 
\right)_{\!\nu\in\Z}\, \right]^{\rm T}.</math>

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 (discrete mathematics)|graph]] or [[directed graph|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 ladder]]s are examples of circulant graphs, as are the [[Paley graph]]s for [[field (mathematics)|field]]s of [[prime number|prime]] order.

==References==
{{reflist|25em}}

==External links==
*  {{cite book |first=R.M. |last=Gray |title=Toeplitz and Circulant Matrices: A Review |series=Foundations and Trends in Communications and Information Theory |date=2006 |volume=2 |issue=3 |pages=155–239 |via=Stanford University |url=http://www-ee.stanford.edu/~gray/toeplitz.pdf |doi=10.1561/0100000006 |publisher=Now |isbn=978-1-933019-68-0}}
* [https://github.com/MMesch/toeplitz_spectrum/blob/master/toeplitz_spectrum.ipynb IPython Notebook demonstrating properties of circulant matrices]

{{Numerical linear algebra}}
{{Matrix classes}}
{{Authority control}}

[[Category:Numerical linear algebra]]
[[Category:Matrices (mathematics)]]
[[Category:Latin squares]]
[[Category:Determinants]]