Circulant matrix explained

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.

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

n x n

circulant matrix

takes the form

C = \beginc_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 of this form (by choice of notation). If each

c_i

is a

p x p

square matrix, then the

np x np

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 permutations of the vector

with offset equal to the column (or row, resp.) index, if lines are indexed from

n-1

. (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).

f(x)=c₀+c₁x+...+c_n-1x^n-1

is called the associated polynomial of the matrix

Properties

Eigenvectors and eigenvalues

The normalized eigenvectors 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{2\pii}{n}\right)

is a primitive

-th root of unity and

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 $\lambda_j = c_0+c_ \omega^j + 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 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 of a circulant matrix

is equal to

n-d

where

is the degree of the polynomial

\gcd(f(x),xⁿ-1)

.^[2]

Other properties

C = c_0 I + c_1 P + c_2 P^2 + \dots + c_ P^ = f(P),

where

is given by the companion matrix

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 of

n x n

circulant matrices forms an

-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

C_n

, or equivalently as the group ring of

C_n

Circulant matrices form a commutative algebra, since for any two given circulant matrices

and

, the sum

A+B

is circulant, the product

is circulant, and

AB=BA

For a nonsingular circulant matrix

, its inverse

A^-1

is also circulant. For a singular circulant matrix, its Moore–Penrose pseudoinverse

A⁺

is circulant.

The matrix

F_n

that is composed of the eigenvectors of a circulant matrix is related to the discrete Fourier transform and its inverse transform:

F_n \text, \text F_n = [v_0,v_1,\dots,v_{n-1}]= \frac(f_) \text f_ = e^, \,\text 0 \leq k,j \leq n-1.

Consequently the matrix

U_n

diagonalizes

. In fact, we have

C = F_n\operatorname(\sqrt n \cdot F_n^ c) F_n^,

where

is the first column of

. The eigenvalues of

are given by the product

	\dagger
F
	n

. This product can be readily calculated by a fast Fourier transform. Conversely, for any diagonal matrix

, the product

F_nDF

	\dagger

	n

is circulant.

p(x)

be the (monic) characteristic polynomial of an

n x n

circulant matrix

. Then the scaled derivative

\fracp'(x)

is the characteristic polynomial of the following

(n-1) x (n-1)

submatrix of

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).

Analytic interpretation

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

Consider vectors in

\Rⁿ

as functions on the integers with period

, (i.e., as periodic bi-infinite sequences:

...,a_0,a_1,...,a_n-1,a_0,a_1,...

) or equivalently, as functions on the cyclic group of order

(denoted

C_n

\Z/n\Z

) 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, 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)

; this is a discrete circular convolution. The formula for the convolution of the functions

(b_i):=(c_i)*(a_i)

b_k=

	n-1
\sum
	i=0

a_ic_k-i

(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 entries is isomorphic to the group

C^*

-algebra of

\Z/n\Z.

Symmetric circulant matrices

For a symmetric circulant matrix

one has the extra condition that

c_n-i=c_i

. Thus it is determined by

\lfloorn/2\rfloor+1

elements.

C = \beginc_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{λ}=\sqrtn ⋅

	\dagger
F
	n

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

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

odd, where

\Rez

denotes the real part of

.This can be further simplified by using the fact that

\Re

	j
\omega
	k

=\Re

-	2\pii	⋅ kj
	n

=\cos(-

	2\pi
	n

⋅ kj)

and

	n/2
\omega
	k

2\pii

⋅ k

	n
	2

=e^-\pi

depending on

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\len/2

and its determinant and all eigenvalues are real.

If n is even the first two rows necessarily takes the form $\beginr_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₃

in the top second half-row is real.

If n is odd we get $\beginr_0 & z_1 & z_2 & z_2^* & z_1^* \\z_1^* & r_0 & z_1 & z_2 & z_2^* \\\dots\\\end.$

Tee^[3] has discussed constraints on the eigenvalues for the Hermitian condition.

Applications

In linear equations

Given a matrix equation

Cx=b,

where

is a circulant matrix of size

, we can write the equation as the circular convolution

\mathbf \star \mathbf = \mathbf,

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 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{(\mathcal{F}_n(\mathbf{b}))_{\nu}}
{(\mathcal{F}_n(\mathbf{c}))_{\nu}} 
\right)_{\!\nu\in\Z}\, \right]^.

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.

External links

Notes and References

[Philip J. Davis|Davis, Philip J.]
A. W. Ingleton . The Rank of Circulant Matrices . J. London Math. Soc. . 1956 . s1-31 . 4 . 445–460 . 10.1112/jlms/s1-31.4.445.
Tee. G J. 2007. Eigenvectors of Block Circulant and Alternating Circulant Matrices. New Zealand Journal of Mathematics. 36. 195–211.