Linear algebra matrix
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
diagonalized by a
discrete Fourier transform , and hence
linear equations that contain them may be quickly solved using a
fast Fourier transform .
[1] They can be
interpreted analytically as the
integral kernel of a
convolution operator on the
cyclic group
C
n
{\displaystyle 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 (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
MixColumns step of the
Advanced Encryption Standard .
Definition
An
n
×
n
{\displaystyle n\times n}
circulant matrix
C
{\displaystyle C}
takes the form
C
=
c
0
c
n
−
1
⋯
c
2
c
1
c
1
c
0
c
n
−
1
c
2
⋮
c
1
c
0
⋱
⋮
c
n
−
2
⋱
⋱
c
n
−
1
c
n
−
1
c
n
−
2
⋯
c
1
c
0
{\displaystyle 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}}}
or the
transpose of this form (by choice of notation). If each
c
i
{\displaystyle c_{i}}
is a
p
×
p
{\displaystyle p\times p}
square
matrix , then the
n
p
×
n
p
{\displaystyle np\times np}
matrix
C
{\displaystyle C}
is called a
block-circulant matrix .
A circulant matrix is fully specified by one vector,
c
{\displaystyle c}
, which appears as the first column (or row) of
C
{\displaystyle C}
. The remaining columns (and rows, resp.) of
C
{\displaystyle C}
are each
cyclic permutations of the vector
c
{\displaystyle c}
with offset equal to the column (or row, resp.) index, if lines are indexed from
0
{\displaystyle 0}
to
n
−
1
{\displaystyle n-1}
. (Cyclic permutation of rows has the same effect as cyclic permutation of columns.) The last row of
C
{\displaystyle C}
is the vector
c
{\displaystyle c}
shifted by one in reverse.
Different sources define the circulant matrix in different ways, for example as above, or with the vector
c
{\displaystyle 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
f
(
x
)
=
c
0
+
c
1
x
+
⋯
+
c
n
−
1
x
n
−
1
{\displaystyle f(x)=c_{0}+c_{1}x+\dots +c_{n-1}x^{n-1}}
is called the associated polynomial of the matrix
C
{\displaystyle C}
.
Properties
Eigenvectors and eigenvalues
The normalized
eigenvectors of a circulant matrix are the Fourier modes, namely,
v
j
=
1
n
(
1
,
ω
j
,
ω
2
j
,
…
,
ω
(
n
−
1
)
j
)
,
j
=
0
,
1
,
…
,
n
−
1
,
{\displaystyle v_{j}={\frac {1}{\sqrt {n}}}\left(1,\omega ^{j},\omega ^{2j},\ldots ,\omega ^{(n-1)j}\right),\quad j=0,1,\ldots ,n-1,}
where
ω
=
exp
(
2
π
i
n
)
{\displaystyle \omega =\exp \left({\tfrac {2\pi i}{n}}\right)}
is a primitive
n
{\displaystyle n}
-th
root of unity and
i
{\displaystyle i}
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 are given by
λ
j
=
c
0
+
c
1
ω
j
+
c
2
ω
2
j
+
⋯
+
c
n
−
1
ω
(
n
−
1
)
j
,
j
=
0
,
1
,
…
,
n
−
1.
{\displaystyle \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.}
Determinant
As a consequence of the explicit formula for the eigenvalues above,
the
determinant of a circulant matrix can be computed as:
det
C
=
∏
j
=
0
n
−
1
(
c
0
+
c
n
−
1
ω
j
+
c
n
−
2
ω
2
j
+
⋯
+
c
1
ω
(
n
−
1
)
j
)
.
{\displaystyle \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}).}
Since taking the transpose does not change the eigenvalues of a matrix, an equivalent formulation is
det
C
=
∏
j
=
0
n
−
1
(
c
0
+
c
1
ω
j
+
c
2
ω
2
j
+
⋯
+
c
n
−
1
ω
(
n
−
1
)
j
)
=
∏
j
=
0
n
−
1
f
(
ω
j
)
.
{\displaystyle \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}).}
Rank
The
rank of a circulant matrix
C
{\displaystyle C}
is equal to
n
−
d
{\displaystyle n-d}
where
d
{\displaystyle d}
is the
degree of the polynomial
gcd
(
f
(
x
)
,
x
n
−
1
)
{\displaystyle \gcd(f(x),x^{n}-1)}
.
[2]
Other properties
Any circulant is a matrix polynomial (namely, the associated polynomial) in the cyclic
permutation matrix
P
{\displaystyle P}
:
C
=
c
0
I
+
c
1
P
+
c
2
P
2
+
⋯
+
c
n
−
1
P
n
−
1
=
f
(
P
)
,
{\displaystyle C=c_{0}I+c_{1}P+c_{2}P^{2}+\dots +c_{n-1}P^{n-1}=f(P),}
where
P
{\displaystyle P}
is given by the
companion matrix
P
=
0
0
⋯
0
1
1
0
⋯
0
0
0
⋱
⋱
⋮
⋮
⋮
⋱
⋱
0
0
0
⋯
0
1
0
.
{\displaystyle 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}}.}
The
set of
n
×
n
{\displaystyle n\times n}
circulant matrices forms an
n
{\displaystyle n}
-
dimensional
vector space with respect to addition and scalar multiplication. This space can be interpreted as the space of
functions on the
cyclic group of
order
n
{\displaystyle n}
,
C
n
{\displaystyle C_{n}}
, or equivalently as the
group ring of
C
n
{\displaystyle C_{n}}
.
Circulant matrices form a
commutative algebra , since for any two given circulant matrices
A
{\displaystyle A}
and
B
{\displaystyle B}
, the sum
A
+
B
{\displaystyle A+B}
is circulant, the product
A
B
{\displaystyle AB}
is circulant, and
A
B
=
B
A
{\displaystyle AB=BA}
.
For a
nonsingular circulant matrix
A
{\displaystyle A}
, its
inverse
A
−
1
{\displaystyle A^{-1}}
is also circulant. For a singular circulant matrix, its
Moore–Penrose pseudoinverse
A
+
{\displaystyle A^{+}}
is circulant.
The matrix
U
{\displaystyle U}
that is composed of the eigenvectors of a circulant matrix is related to the
discrete Fourier transform and its inverse transform:
U
n
∗
=
1
n
F
n
,
and
U
n
=
n
F
n
−
1
,
where
F
n
=
(
f
j
k
)
with
f
j
k
=
e
−
2
j
k
π
i
/
n
,
for
0
≤
j
,
k
<
n
.
{\displaystyle U_{n}^{*}={\frac {1}{\sqrt {n}}}F_{n},\quad {\text{and}}\quad U_{n}={\sqrt {n}}F_{n}^{-1},{\text{ where }}F_{n}=(f_{jk}){\text{ with }}f_{jk}=e^{-2jk\pi i/n},\,{\text{for }}0\leq j,k<n.}
Consequently the matrix
U
n
{\displaystyle U_{n}}
diagonalizes
C
{\displaystyle C}
. In fact, we have
C
=
U
n
diag
(
F
n
c
)
U
n
∗
=
F
n
−
1
diag
(
F
n
c
)
F
n
,
{\displaystyle C=U_{n}\operatorname {diag} (F_{n}c)U_{n}^{*}=F_{n}^{-1}\operatorname {diag} (F_{n}c)F_{n},}
where
c
{\displaystyle c}
is the first column of
C
{\displaystyle C}
. The eigenvalues of
C
{\displaystyle C}
are given by the product
F
n
c
{\displaystyle F_{n}c}
. This product can be readily calculated by a
fast Fourier transform .
[3] Conversely, for any diagonal matrix
D
{\displaystyle D}
, the product
F
n
−
1
D
F
n
{\displaystyle F_{n}^{-1}DF_{n}}
is circulant.
Let
p
(
x
)
{\displaystyle p(x)}
be the (
monic )
characteristic polynomial of an
n
×
n
{\displaystyle n\times n}
circulant matrix
C
{\displaystyle C}
. Then the scaled
derivative
1
n
p
′
(
x
)
{\textstyle {\frac {1}{n}}p'(x)}
is the characteristic polynomial of the following
(
n
−
1
)
×
(
n
−
1
)
{\displaystyle (n-1)\times (n-1)}
submatrix of
C
{\displaystyle C}
:
C
n
−
1
=
c
0
c
n
−
1
⋯
c
3
c
2
c
1
c
0
c
n
−
1
c
3
⋮
c
1
c
0
⋱
⋮
c
n
−
3
⋱
⋱
c
n
−
1
c
n
−
2
c
n
−
3
⋯
c
1
c
0
{\displaystyle 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}}}
(see
[4] for the
proof ).
Analytic interpretation
Circulant matrices can be interpreted
geometrically , which explains the connection with the discrete Fourier transform.
Consider vectors in
R
n
{\displaystyle \mathbb {R} ^{n}}
as functions on the
integers with period
n
{\displaystyle n}
, (i.e., as periodic bi-infinite sequences:
…
,
a
0
,
a
1
,
…
,
a
n
−
1
,
a
0
,
a
1
,
…
{\displaystyle \dots ,a_{0},a_{1},\dots ,a_{n-1},a_{0},a_{1},\dots }
) or equivalently, as functions on the
cyclic group of order
n
{\displaystyle n}
(denoted
C
n
{\displaystyle C_{n}}
or
Z
/
n
Z
{\displaystyle \mathbb {Z} /n\mathbb {Z} }
) geometrically, on (the vertices of) the
regular
n
{\displaystyle 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 for the function
(
c
0
,
c
1
,
…
,
c
n
−
1
)
{\displaystyle (c_{0},c_{1},\dots ,c_{n-1})}
; this is a discrete
circular convolution . The formula for the convolution of the functions
(
b
i
)
:=
(
c
i
)
∗
(
a
i
)
{\displaystyle (b_{i}):=(c_{i})*(a_{i})}
is
b
k
=
∑
i
=
0
n
−
1
a
i
c
k
−
i
{\displaystyle b_{k}=\sum _{i=0}^{n-1}a_{i}c_{k-i}}
(recall that the sequences are periodic)
which is the product of the vector
(
a
i
)
{\displaystyle (a_{i})}
by the circulant matrix for
(
c
i
)
{\displaystyle (c_{i})}
.
The discrete Fourier transform then converts convolution into multiplication, which in the matrix setting corresponds to diagonalization.
The
C
∗
{\displaystyle C^{*}}
-algebra of all circulant matrices with
complex entries is
isomorphic to the group
C
∗
{\displaystyle C^{*}}
-algebra of
Z
/
n
Z
.
{\displaystyle \mathbb {Z} /n\mathbb {Z} .}
Symmetric circulant matrices
For a
symmetric circulant matrix
C
{\displaystyle C}
one has the extra condition that
c
n
−
i
=
c
i
{\displaystyle c_{n-i}=c_{i}}
.
Thus it is determined by
⌊
n
/
2
⌋
+
1
{\displaystyle \lfloor n/2\rfloor +1}
elements.
C
=
c
0
c
1
⋯
c
2
c
1
c
1
c
0
c
1
c
2
⋮
c
1
c
0
⋱
⋮
c
2
⋱
⋱
c
1
c
1
c
2
⋯
c
1
c
0
.
{\displaystyle 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}}.}
The eigenvalues of any
real symmetric matrix are real.
The corresponding eigenvalues become:
λ
j
=
c
0
+
2
c
1
ℜ
ω
j
+
2
c
2
ℜ
ω
j
2
+
⋯
+
2
c
n
/
2
−
1
ℜ
ω
j
n
/
2
−
1
+
c
n
/
2
ω
j
n
/
2
{\displaystyle \lambda _{j}=c_{0}+2c_{1}\Re \omega _{j}+2c_{2}\Re \omega _{j}^{2}+\dots +2c_{n/2-1}\Re \omega _{j}^{n/2-1}+c_{n/2}\omega _{j}^{n/2}}
for
n
{\displaystyle n}
even , and
λ
j
=
c
0
+
2
c
1
ℜ
ω
j
+
2
c
2
ℜ
ω
j
2
+
⋯
+
2
c
(
n
−
1
)
/
2
ℜ
ω
j
(
n
−
1
)
/
2
{\displaystyle \lambda _{j}=c_{0}+2c_{1}\Re \omega _{j}+2c_{2}\Re \omega _{j}^{2}+\dots +2c_{(n-1)/2}\Re \omega _{j}^{(n-1)/2}}
for
n
{\displaystyle n}
odd , where
ℜ
z
{\displaystyle \Re z}
denotes the
real part of
z
{\displaystyle z}
.
This can be further simplified by using the fact that
ℜ
ω
j
k
=
cos
(
2
π
j
k
/
n
)
{\displaystyle \Re \omega _{j}^{k}=\cos(2\pi jk/n)}
and
ω
j
n
/
2
=
exp
(
π
i
j
)
=
±
1
{\displaystyle \omega _{j}^{n/2}=\exp \left({\pi ij}\right)=\pm 1}
depending on
j
{\displaystyle j}
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 . In this case
c
n
−
i
=
c
i
∗
,
i
≤
n
/
2
{\displaystyle c_{n-i}=c_{i}^{*},\;i\leq n/2}
and its determinant and all eigenvalues are real.
If n is even the first two rows necessarily takes the form
r
0
z
1
z
2
r
3
z
2
∗
z
1
∗
z
1
∗
r
0
z
1
z
2
r
3
z
2
∗
…
.
{\displaystyle {\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}}.}
in which the first element
r
3
{\displaystyle r_{3}}
in the top second half-row is real.
If n is odd we get
r
0
z
1
z
2
z
2
∗
z
1
∗
z
1
∗
r
0
z
1
z
2
z
2
∗
…
.
{\displaystyle {\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}}.}
Tee
[5] has discussed constraints on the eigenvalues for the Hermitian condition.
Applications
In linear equations
Given a matrix equation
C
x
=
b
,
{\displaystyle C\mathbf {x} =\mathbf {b} ,}
where
C
{\displaystyle C}
is a circulant matrix of size
n
{\displaystyle n}
, we can write the equation as the
circular convolution
c
⋆
x
=
b
,
{\displaystyle \mathbf {c} \star \mathbf {x} =\mathbf {b} ,}
where
c
{\displaystyle \mathbf {c} }
is the first column of
C
{\displaystyle C}
, and the vectors
c
{\displaystyle \mathbf {c} }
,
x
{\displaystyle \mathbf {x} }
and
b
{\displaystyle \mathbf {b} }
are cyclically extended in each direction. Using the
circular convolution theorem , we can use the
discrete Fourier transform to transform the cyclic convolution into component-wise multiplication
F
n
(
c
⋆
x
)
=
F
n
(
c
)
F
n
(
x
)
=
F
n
(
b
)
{\displaystyle {\mathcal {F}}_{n}(\mathbf {c} \star \mathbf {x} )={\mathcal {F}}_{n}(\mathbf {c} ){\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )}
so that
x
=
F
n
−
1
(
(
F
n
(
b
)
)
ν
(
F
n
(
c
)
)
ν
)
ν
∈
Z
T
.
{\displaystyle \mathbf {x} ={\mathcal {F}}_{n}^{-1}\left[\left({\frac {({\mathcal {F}}_{n}(\mathbf {b} ))_{\nu }}{({\mathcal {F}}_{n}(\mathbf {c} ))_{\nu }}}\right)_{\!\nu \in \mathbb {Z} }\,\right]^{\rm {T}}.}
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
fields of
prime order.
References
^
Davis, Philip J. , Circulant Matrices, Wiley, New York, 1970
ISBN
0471057711
^ A. W. Ingleton (1956). "The Rank of Circulant Matrices". J. London Math. Soc . s1-31 (4): 445–460.
doi :
10.1112/jlms/s1-31.4.445 .
^
Golub, Gene H. ;
Van Loan, Charles F. (1996), "§4.7.7 Circulant Systems", Matrix Computations (3rd ed.), Johns Hopkins,
ISBN
978-0-8018-5414-9
^ Kushel, Olga; Tyaglov, Mikhail (July 15, 2016), "Circulants and critical points of polynomials", Journal of Mathematical Analysis and Applications , 439 (2): 634–650,
arXiv :
1512.07983 ,
doi :
10.1016/j.jmaa.2016.03.005 ,
ISSN
0022-247X
^ Tee, G J (2007). "Eigenvectors of Block Circulant and Alternating Circulant Matrices". New Zealand Journal of Mathematics . 36 : 195–211.
External links
Key concepts Problems Hardware Software