# Circular shift and reflection

I know that in a circulant matrix(C) all other rows are (right) shifted versions of first row. Let $x = [c_{0},c_{N-1},c_{N-2},...,c_{1}]$ be the first row. Then $x(n-j) = [c_{j},c_{j-1},c_{j-1},...,c_{j+1}]$ will be the $j^{th}$ row, where $j = 0,1,...,N-1$. The reflection of x(n) = $\hat{x}(n) = x(-n) = x(N-n)$. How can I find the expression for $i^{th}$ column of C in terms of reflection and delay operators on $x$. I am trying to prove circulant matrices are commutative. Is there any other way to prove this.

-
How is a "delay operator" defined? –  Guess who it is. May 12 '11 at 15:44
@JM,delay operator is $x(n-j)$.Shifting each component of x by j units to the right. –  Vinod May 12 '11 at 15:47

I think you'll find it's easier to express these things using modular arithmetic. For two circulant matrices $A$ and $B$ with entries $a_{ij}$ and $b_{ij}$, respectively, you can write $a_{ij}=\alpha_{i-j}$ and $b_{ij}=\beta_{i-j}$, where the indices on $\alpha$ and $\beta$ are understood mod $N$. Then the two products are

$$\begin{eqnarray} (AB)_{ik} &=& \sum_ja_{ij}b_{jk}\\ &=& \sum_j\alpha_{i-j}\beta_{j-k} \end{eqnarray}$$

and

$$\begin{eqnarray} (BA)_{ik} &=& \sum_jb_{ij}a_{jk}\\ &=& \sum_j\beta_{i-j}\alpha_{j-k} \;. \end{eqnarray}$$

Now you can rename the summation index in one of the products as $j=i+k-j'\pmod{N}$ to see that the two are the same.

-

A circulant matrix is determined by its first row. Take the usual basis for the space of row vectors, and extend each row vector to a circulant matrix. You get a basis for the space of circulant matrices.

Each of these basis matrices is a power of the circulant matrix whose first row is $[0\ 1\ 0\ \dots\ 0]$, so these basis matrices commute with one another. So linear combinations of them also commute; that is, any two circulant matrices commute.

-
In "the usual basis for the space of row matrices", I think you mean "row vectors"? –  joriki May 12 '11 at 16:08
Thanks! Fixed now. –  mac May 12 '11 at 16:11