### Archive

Posts Tagged ‘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: $\epsilon^n=1$

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)