Home > Matrix Theory > Circulant Matrices

Circulant Matrices


Definition.  Given T:\mathbb{C}^n\to \mathbb{C}^n be a linear operator such that for every x=(x_0,x_2,...,x_{n-1}) then

T(x_0,x_1,...,x_{n-1})=(x_{n-1},x_0,x_1,...,x_{n-2})

The matrix with k-row is given by T^{k-1}x, \ k=1,2,...,n will be called circulant and denoted by X=circ(x)=circ(x_0,x_1,...,x_n)

X=\begin{pmatrix}x_0 & x_1 & ... & x_{n-2} & x_{n-1}\\ x_{n-1} & x_0 & ... & x_{n-3} & x_{n-2}\\ ... & ... & ... & ... & ...\\ x_2 & x_3 &... & x_0 & x_1\\ x_1 & x_2 & ... & x_{n-1} & x_0\end{pmatrix}

Theorem 1. \det(X)=\prod_{k=0}^{n-1}\left ( \sum_{j=0}^{n-1}x_j \epsilon_k^j\right ), where \epsilon is a primitive n-th root of unity.

We multiply the  j-columm with \epsilon^{j-1}, \ j=2,3,...,n, and add it onto the first columm, claim that \epsilon^n=1, we have:

 

The j-element of the first columm is a product of x_0+x_1\epsilon+...+x_{n-1}\epsilon^{n-1} with \epsilon^{j-1}, \ j=1,2,...,n. We give \det(X) as a polynomial with n variable x_1,x_2,...,x_n on \mathbb{C}[x], hence \det(X) is devided  by x_0+x_1\epsilon+...+x_{n-1}\epsilon^{n-1}. Claim that \det(X) is a n-degree polynomial and the coefficient of x_0x_1...x_{n-1} is 1.

Thus \det(X)=\prod_{k=0}^{n-1}\left ( \sum_{j=0}^{n-1} \epsilon_k^jx_j \right ) \bigstar

For k=0,1,2,...,n-1, we denote  e_k=\frac{1}{\sqrt{n}}(1,\epsilon_k,...,\epsilon_k^{n-1})^T and
\lambda_k= x_0+x_1\epsilon_k+...+x_{n-1}\epsilon_k^{n-1}

We can easily calculate and receive that Xe_k=\lambda_k e_k and since \{e_0,e_1,...,e_{n-1}\} is a linearly independent system, we conclude that \lambda_0,\lambda_1,...,\lambda_{n-1} are eigenvalues of circulant matrix X

Some results:

i.  trace(X)=\sum_{k=0}^{n-1}\lambda_k=nx_0

ii. With non-singular matrix

 P=\frac{1}{\sqrt{n}} \begin{pmatrix}1 & 1 & ... & 1 & 1\\ 1 & \epsilon & ... & \epsilon^{n-2} & \epsilon^{n-1}\\ ... & ... & ... & ... & ...\\ 1 & \epsilon^{n-2} & ....& \epsilon^{(n-2)^2}& \epsilon^{(n-1)(n-2)}\\ 1 & \epsilon^{n-1} & ... & \epsilon^{(n-2)(n-1)} & \epsilon^{(n-1)^2} \end{pmatrix}

then P^{-1}XP=diag(\lambda_0,\lambda_1,...,\lambda_{n-1})

iii  X=\sum_{k=0}^{n-1}x_kW^k where W=circ(0,1,0,...,0)

(To be continued)

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: