1
$\begingroup$

Let $F_n\in\mathbb{C}^{n\times n}$ be the unitary matrix representing the discrete Fourier transform of length $n$ and so $F_n^{H}\in\mathbb{C}^{n\times n}$ is the inverse DFT of length $n$. For example, for $n = 4$ $$F_4 = \frac{1}{2} \left( \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & \mu & \mu^2 & \mu^3 \\ 1 & \mu^2 & \mu^4 & \mu^6 \\ 1 & \mu^3 & \mu^6 & \mu^9 \\ \end{array} \right) \ \ \text{and} \ \ F_4^{H} = \frac{1}{2} \left( \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^2 & \omega^3 \\ 1 & \omega^2 & \omega^4 & \omega^6 \\ 1 & \omega^3 & \omega^6 & \omega^9 \\ \end{array} \right) $$ where $\theta = 2\pi/n$, $\omega = e^{i\theta}$ and $\mu = e^{-i\theta}$.

Let $Z_n\in\mathbb{C}^{n\times n}$ be the permutation matrix of order $n$ such that $Zv$ represent the circulant "upshift" of the elements of the vector $v$, i.e., $$Z_n = \left(e_n \ \ e_1 \ \ e_2 \ \ \ldots \ \ e_{n-1}\right)$$ For example, for $n = 4$ $$Z_4 = \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ \end{array} \right)$$ Let $C_n\in\mathbb{C}^{n\times n}$ be a circulant matrix of order $n$. The circulant matrix $C_n$ has $n$ parameters (either the first row or first column can be viewed as these parameters). It is a Toeplitz matrix (all diagonals are constant) with the additional constraint that each row (column) is a circulant shift of the previous row (column).

For example, for $n = 4$ and using the first row as the parameters we have $$C_4 = \left( \begin{array}{cccc} \alpha_0 & \alpha_1 & \alpha_2 & \alpha_3 \\ \alpha_3 & \alpha_0 & \alpha_1 & \alpha_2 \\ \alpha_2 & \alpha_3 & \alpha_0 & \alpha_1 \\ \alpha_1 & \alpha_2 & \alpha_3 & \alpha_0 \\ \end{array} \right)$$ Given a polynomial of degree $d$, a matrix polynomial is defined as follows $$P_d(\xi) = \delta_0 + \delta_1\xi + \delta_2\xi^2 + \ldots + \delta_d\xi^d$$ $$P_d(A) = \delta_0 I + \delta_1 A + \delta_2 A^2 + \ldots + \delta_d A^d$$ $$\xi\in\mathbb{C}, \delta_i\in\mathbb{C}, P_d(A),A\in\mathbb{C}^{n\times n}$$

Questions:

i.) Recall, that the set of $n\times n$ matrices is a vector space with dimension $n^2$. Show that the set of $n\times n$ circulant matrices, $C_n$, is a subspace of that vector space with dimension $n$.

ii.) Determine matrices $Q_n$ and $\Gamma_n$ such that $$C_n = Q_n\Gamma_n Q_n^{H}$$ where $Q_n\in\mathbb{C}^{n\times n}$ is a unitary matrix and $\Gamma_n\in\mathbb{C}^{n\times n}$ is a diagonal matrix.

iii.) Describe how you determine if $C_n$ is a nonsingular matrix.

Beginning solution of 1: We have that $C_n\in\mathbb{C}^{n\times n}$ is a circulant matrix of order n. So we have $$ C_n = \begin{bmatrix} \alpha_0 & \alpha_{n-1} & \dots & \alpha_{2} & \alpha_{1} \\ \alpha_{1} & \alpha_0 & \alpha_{n-1} & & \alpha_{2} \\ \vdots & \alpha_{1}& \alpha_0 & \ddots & \vdots \\ \alpha_{n-2} & & \ddots & \ddots & \alpha_{n-1} \\ \alpha_{n-1} & \alpha_{n-2} & \dots & \alpha_{1} & \alpha_0 \\ \end{bmatrix}$$ The associated polynomial is $f(x) = \alpha_0 + \alpha_1 x + \ldots + \alpha_{n-1}x^{n-1}$

I am lost on how to begin these problems, any suggestions is greatly appreciated

$\endgroup$
  • $\begingroup$ Your $Z_4$ is transposed from what it's supposed to be $\endgroup$ – Omnomnomnom Jan 14 '16 at 17:18
  • $\begingroup$ Oh, never mind, you're using row-vectors! Everything is good. $\endgroup$ – Omnomnomnom Jan 14 '16 at 17:33
1
$\begingroup$

Hints:

  • For i: note that as soon as you know the first row of a circular matrix, the entire matrix is determined. Use the first row, then, to construct a basis of $n$ matrices for the space of circulant matrices.

  • Alternatively, note that the circulant matrices is exactly the matrices which can be written in the form $P_{n}(Z_n)$. You may notice that this is equivalent to the first hint. However, this version is more useful to the next step.

  • For ii: By the previous hint, it suffices to find $Q_n$ such that $$ Z_n = Q_n \Gamma_n Q_n^H $$

  • For iii: Think polynomials, and think eigenvalues

$\endgroup$
  • $\begingroup$ Thank you for the hints, but I am still stuck. For i.), do I need to show that: 1. $C_n$ is nonempy, 2. If $x,y\in C_n$ then $x+y\in C_n$, and 3. If $\alpha\in\mathbb{C}$ and $x\in C_n$, then $\alpha x\in C_n$? $\endgroup$ – Wolfy Jan 14 '16 at 18:58
  • $\begingroup$ @MorganWeiss I suppose that is one option. However, I would say that all of these properties follow quickly from the second hint. Whether this is a sufficient explanation or not depends on your instructor. $\endgroup$ – Omnomnomnom Jan 14 '16 at 20:07
  • $\begingroup$ I see, could you go further with your second hint so I can understand it more, sort of struggling still with this. $\endgroup$ – Wolfy Jan 14 '16 at 20:44
  • $\begingroup$ @Morgan try plugging $Z_3$ into a few polynomials and see what happens. The coefficients of the polynomials should become the entries $\endgroup$ – Omnomnomnom Jan 14 '16 at 20:50
  • $\begingroup$ Do you mean $C_3$? $\endgroup$ – Wolfy Jan 14 '16 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.