Exercises — Lesson 12: Unitary Matrices and the Discrete Fourier Transform
Exercise 12.1. [Hand] Write out the 3-point DFT matrix using \(\omega = e^{-2\pi i/3} = -\tfrac12 - \tfrac{\sqrt3}{2}i\), and compute \(\hat x\) for \(x = (1,1,1)\) and for \(x = (1, \omega^{-1}, \omega^{-2})\). Explain both answers in one sentence each.
Solution. \(N = 3\), \(\omega = e^{-2\pi i/3} = -\tfrac{1}{2} - i\tfrac{\sqrt3}{2}\).
\[ W = \begin{pmatrix} 1 & 1 & 1 \\ 1 & \omega & \omega^2 \\ 1 & \omega^2 & \omega^4 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & \omega & \omega^2 \\ 1 & \omega^2 & \omega \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 \\[4pt] 1 & \left(-\tfrac{1}{2} - i\tfrac{\sqrt3}{2}\right) & \left(-\tfrac{1}{2} + i\tfrac{\sqrt3}{2}\right) \\[4pt] 1 & \left(-\tfrac{1}{2} + i\tfrac{\sqrt3}{2}\right) & \left(-\tfrac{1}{2} - i\tfrac{\sqrt3}{2}\right) \end{pmatrix} \]
\[ W^{-1} = \frac{1}{3}\begin{pmatrix} 1 & 1 & 1 \\[4pt] 1 & \left(-\tfrac{1}{2} + i\tfrac{\sqrt3}{2}\right) & \left(-\tfrac{1}{2} - i\tfrac{\sqrt3}{2}\right) \\[4pt] 1 & \left(-\tfrac{1}{2} - i\tfrac{\sqrt3}{2}\right) & \left(-\tfrac{1}{2} + i\tfrac{\sqrt3}{2}\right) \end{pmatrix} \]
\[ x_1 = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} \qquad \hat x_1 = \begin{pmatrix} 3 \\ 1 + \omega + \omega^2 \\ 1 + \omega^2 + \omega \end{pmatrix} = \begin{pmatrix} 3 \\ 0 \\ 0 \end{pmatrix} \]
\[ x_2 = \begin{pmatrix} 1 \\ \omega^{-1} \\ \omega^{-2} \end{pmatrix} = \begin{pmatrix} 1 \\ \omega^{2} \\ \omega \end{pmatrix} \qquad \hat x_2 = \begin{pmatrix} 1 + \omega^{-1} + \omega^{-2} \\ 3 \\ 1 + \omega + \omega^2 \end{pmatrix} = \begin{pmatrix} 1 + \omega^{2} + \omega \\ 3 \\ 1 + \omega + \omega^2 \end{pmatrix} = \begin{pmatrix} 0 \\ 3 \\ 0 \end{pmatrix} \]
\(\hat x_2\) is \(\hat x_1\) shifted cyclically by one. \(\hat x_1\) is constant, DC frequency; \(\hat x_2\) is one sinusoid.
Exercise 12.2. [Hand] For \(N = 4\), write the circulant matrix \(C\) for \(c = (0,1,0,0)\) (the cyclic shift). Verify directly that \(v = (1, i^{-1}, i^{-2}, i^{-3}) = (1,-i,-1,i)\) satisfies \(Cv = \lambda v\), and identify \(\lambda\) as an entry of \(\hat c\).
Solution. \(N = 4\), \(c = (0,1,0,0)\), and \(\omega = e^{-2\pi i/4} = e^{-i\frac{\pi}{2}} = -i\).
\[ W = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{pmatrix}, \qquad W^{-1} = \frac{1}{4}\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix} \]
\[ C = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}, \qquad c = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}, \qquad v = \begin{pmatrix} 1 \\ i^{-1} \\ i^{-2} \\ i^{-3} \end{pmatrix} = \begin{pmatrix} 1 \\ -i \\ -1 \\ i \end{pmatrix} \]
\[ Cv = \begin{pmatrix} i \\ 1 \\ -i \\ -1 \end{pmatrix} = i\begin{pmatrix} 1 \\ -i \\ -1 \\ i \end{pmatrix} = \lambda v \qquad \boxed{\;\lambda = i\;} \]
\[ \boxed{\; Wc = \hat c = \begin{pmatrix} 1 \\ -i \\ -1 \\ i \end{pmatrix} \;} \qquad C = W^{-1}\operatorname{diag}(\hat c)\,W \]
So \(\lambda = i = \hat c_3\), the last entry of \(\hat c\). Checking against the transform of \(v\) itself:
\[ Wv = \hat v = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 4 \end{pmatrix}, \qquad \hat c \odot \hat v = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 4i \end{pmatrix} \]
Exercise 12.3. [Proof, \(\star\)] Prove that the product of two unitary matrices is unitary and that every eigenvalue \(\lambda\) of a unitary matrix has \(|\lambda| = 1\). (For the latter: apply the norm-preservation form of unitarity to an eigenvector.) Conclude the DFT eigenvalue fact: \(|\hat c_k| \le \sum_j |c_j|\) for a circulant’s eigenvalues, directly from the definition of \(\hat c\) and the triangle inequality.
Proof. Prove the product of two unitary matrices \(Q_1\) and \(Q_2\) (\(n \times n\)) is unitary, and every \(\lambda\) of a unitary matrix has \(|\lambda| = 1\).
Let \(x \in \mathbb{C}^n\).
\[ \begin{aligned} \langle (Q_1Q_2)x,\, (Q_1Q_2)x \rangle &= \langle Q_2x,\, Q_1^{-1}Q_1Q_2x \rangle \\[6pt] &= \langle Q_2x,\, Q_2x \rangle \\[6pt] &= \|x\|^2 && \forall x \in \mathbb{C}^n \end{aligned} \]
\(\Longrightarrow Q_1Q_2\) is unitary. \(\square\)
Suppose \(Qv = \lambda v\) for some \(v \ne 0\), and \(Q\) is unitary. Then
\[ \|Qv\| = \|v\| \qquad\text{and}\qquad \|Qv\| = \|\lambda v\| = |\lambda|\,\|v\|. \]
Thus \(|\lambda|\,\|v\| = \|v\| \Longrightarrow |\lambda| = 1\). \(\square\)
Conclude \(|\hat c_k| \le \sum_{n=0}^{N-1}|c_n|\) for a circulant’s eigenvalues, using the definition of \(\hat c\) and the triangle inequality.
Proof. Let \(W\) be the DFT matrix for circulant matrix \(C\). Then \(C = W^{-1}\operatorname{diag}(\hat c)\,W\), \(\omega = e^{-2\pi i/N}\).
\[ \hat c_k = \sum_{n=0}^{N-1} c_n \omega^{kn} \]
\[ \begin{aligned} |\hat c_k| &= \left| \sum_{n=0}^{N-1} c_n \omega^{kn} \right| \\[6pt] &\le \sum_{n=0}^{N-1} \left| c_n \omega^{kn} \right| && \text{[triangle inequality]} \\[6pt] &= \sum_{n=0}^{N-1} |c_n|\,|\omega^{kn}| \\[6pt] &= \sum_{n=0}^{N-1} |c_n| && \text{[$|\omega^{kn}| = 1$]} \end{aligned} \]
\(\square\)
Exercise 12.4. [Proof] Show that the set of circulant \(N \times N\) matrices is closed under products and that any two circulants commute. (Two lines with the convolution theorem: simultaneous diagonalization.)
Proof. Let \(C_1\) and \(C_2\) be two circulant matrices and let \(C_1 = W^{-1}\operatorname{diag}(\hat c_1)W\) and \(C_2 = W^{-1}\operatorname{diag}(\hat c_2)W\) be their DFT diagonalizations. Then
\[ \begin{aligned} C_1C_2 &= W^{-1}\operatorname{diag}(\hat c_1)\,(WW^{-1})\,\operatorname{diag}(\hat c_2)\,W \\[6pt] &= W^{-1}\operatorname{diag}(\hat c_1)\operatorname{diag}(\hat c_2)\,W \\[6pt] &= W^{-1}\operatorname{diag}(\hat c_2)\operatorname{diag}(\hat c_1)\,W \\[6pt] &= W^{-1}\operatorname{diag}(\hat c_2)\,(WW^{-1})\,\operatorname{diag}(\hat c_1)\,W \\[6pt] &= C_2C_1 \end{aligned} \]
\(\square\)
Note because the product of two diagonal matrices is also a diagonal matrix, that means
\[ C_1C_2 = W^{-1}\operatorname{diag}(\hat c_1)\operatorname{diag}(\hat c_2)\,W \]
is also a circulant matrix, with
\[ \operatorname{diag}(\widehat{c_1c_2}) = \operatorname{diag}(\hat c_1)\operatorname{diag}(\hat c_2). \]
\(\square\)