Complex vectors and the Fourier matrix

Can eight turning arrows be perpendicular to eight others? Watch their products chain tip to tail and close up.

Length needs a conjugate

A complex vector has complex numbers as its entries, such as $\mathbf{z}=(1,\,j)$. Try its length the old way, as $\mathbf{z}\cdot\mathbf{z}=\sum z_q^2$:

A vector that is not $\mathbf{0}$ would have length 0. Something is wrong. The fix is the size of a complex number, from Complex numbers for signals: $\lvert z\rvert^2=z^*z$, where $z^*$ is the conjugate, the same number with the sign of its imaginary part flipped. So the squared length of a complex vector is

For $(1,j)$ that is $1+1=2$. For $\mathbf{z}=(1+j,\;2-j)$ it is $(1+1)+(4+1)=7$.

The conjugate transpose

Flip a matrix across its diagonal and conjugate every entry: that is the conjugate transpose, written $\mathbf{A}^{\mathsf H}$. For a column vector, $\mathbf{z}^{\mathsf H}$ is the row of conjugated entries, so

and the dot product of two complex vectors $\mathbf{v}$ and $\mathbf{w}$ is $\mathbf{v}^{\mathsf H}\mathbf{w}$.

Two complex vectors are perpendicular when $\mathbf{v}^{\mathsf H}\mathbf{w}=0$. Like the transpose of Transposes and permutations, it reverses a product: $(\mathbf{A}\mathbf{B})^{\mathsf H}=\mathbf{B}^{\mathsf H}\mathbf{A}^{\mathsf H}$. For real vectors and matrices nothing is conjugated, and everything here reduces to what you already know.

Hermitian and unitary matrices

Two kinds of real matrix have complex versions.

A Hermitian matrix equals its conjugate transpose, $\mathbf{A}^{\mathsf H}=\mathbf{A}$: the complex version of symmetric. The argument of Symmetric matrices, with $\mathsf H$ in place of the transpose, shows that its eigenvalues are real and its eigenvectors perpendicular. Take

Its trace is 5 and its determinant $6-(1-j)(1+j)=6-2=4$, so its eigenvalues are 1 and 4: real, although the matrix is complex. The eigenvectors are $\mathbf{v}_1=(-1+j,\;1)$ and $\mathbf{v}_2=(1,\;1+j)$, and they are perpendicular in the complex sense:

Without the conjugate the test fails: $(-1+j)+(1+j)=2j$.

A unitary matrix $\mathbf{U}$ has $\mathbf{U}^{\mathsf H}\mathbf{U}=\mathbf{I}$: the complex version of a matrix with orthonormal columns. It keeps every length, $\lVert\mathbf{U}\mathbf{z}\rVert=\lVert\mathbf{z}\rVert$, so its eigenvalues all have size 1.

The Fourier matrix

The Fourier matrix $\mathbf{F}$ of size $N$ has the entry $e^{-j2\pi kn/N}$ in row $k$ and column $n$. On this page its rows and columns count from 0, as in signal processing, while other matrices count from 1. For $N=4$:

Its columns are perpendicular. Take column $k$ and column $l$. Conjugate the first and multiply entry by entry: entry $n$ gives $e^{+j2\pi kn/N}\,e^{-j2\pi ln/N}=e^{-j2\pi(l-k)n/N}$. These are unit arrows that turn by $(l-k)/N$ of a turn from one to the next. Laid tip to tail, they go round a whole number of times and close, so the sum is 0, unless $l=k$, when every arrow is 1 and the sum is $N$. That is the picture at the top of the page. In one line:

So $\mathbf{U}=\mathbf{F}/\sqrt N$ is unitary, and $\mathbf{F}^{-1}=\mathbf{F}^{\mathsf H}/N$. For $N=4$, columns 1 and 2: $1\cdot1+j\cdot(-1)+(-1)\cdot1+(-j)\cdot(-1)=1-j-1+j=0$.

Multiplying by $\mathbf{F}$ is the DFT. For $\mathbf{x}=(1,2,3,4)$, $\mathbf{F}\mathbf{x}=(10,\;-2+2j,\;-2,\;-2-2j)$. Lengths change only by the fixed factor $\sqrt N$: $\lVert\mathbf{F}\mathbf{x}\rVert^2=100+8+4+8=120$, which is $4\times30$, and $\lVert\mathbf{x}\rVert^2=30$.

Circulant matrices

A circulant matrix $\mathbf{C}$ is built from one column $\mathbf{c}$: each column is the one before it, rotated down by one place, with the last entry coming round to the top. Multiplying by $\mathbf{C}$ is circular convolution with $\mathbf{c}$. A circular smoother with $\mathbf{c}=(0.5,\,0.25,\,0,\,0.25)$ gives

which averages each sample with half weight and its two neighbours with a quarter each, wrapping round at the ends.

Here is the key fact. Every column of $\mathbf{F}^{-1}$, a pure wave $e^{+j2\pi kn/N}$, is an eigenvector of every circulant matrix. Rotating a pure wave only multiplies it by a number, so a circulant, which is a sum of rotations, does too. The eigenvalues are the entries of $\mathbf{F}\mathbf{c}$, and

Read it right to left: take the DFT, multiply each frequency by its eigenvalue, and transform back. For the smoother, $\mathbf{F}\mathbf{c}=(1,\,0.5,\,0,\,0.5)$: it keeps the constant, halves the next frequencies, and erases the fastest one, the wave $(1,-1,1,-1)$.

Watch the two routes meet. The long way round, through the frequencies, gives exactly what the matrix does in one step.

Worked example

1. Lengths. $\lVert(1+j,\;2-j)\rVert^2=2+5=7$. For $(1,j)$, $\mathbf{z}^\top\mathbf{z}=0$ but $\mathbf{z}^{\mathsf H}\mathbf{z}=2$. And $\lVert(3,\,4j)\rVert=\sqrt{9+16}=5$.

2. A Hermitian matrix. $\begin{bmatrix}2&1-j\\1+j&3\end{bmatrix}$: trace 5, determinant 4, eigenvalues 1 and 4, eigenvectors $(-1+j,\,1)$ and $(1,\,1+j)$, perpendicular with the conjugate.

3. The Fourier matrix. For $N=4$, $\mathbf{F}^{\mathsf H}\mathbf{F}=4\mathbf{I}$, and $\mathbf{F}(1,2,3,4)=(10,\,-2+2j,\,-2,\,-2-2j)$ with $\lVert\mathbf{F}\mathbf{x}\rVert^2=120=4\times30$.

4. A circulant. The smoother $\mathbf{c}=(0.5,0.25,0,0.25)$ has eigenvalues $0.5+0.5\cos(\pi k/2)$ for $k=0$ to 3, which are $(1,0.5,0,0.5)$, and sends $(1,2,3,4)$ to $(2,2,3,3)$. Its eigenvalue 0 belongs to $(1,-1,1,-1)$, which it erases.

Try these before you read the answers.

• What is $\lVert(3,\,4j)\rVert$? 5.
• Is $\begin{bmatrix}0&j\\-j&0\end{bmatrix}$ Hermitian? Yes: transposing gives $\begin{bmatrix}0&-j\\j&0\end{bmatrix}$, and conjugating gives the matrix back. Its eigenvalues are $\pm1$.
• What is $\mathbf{F}^{\mathsf H}\mathbf{F}$ for $N=4$? $4\mathbf{I}$.
• What does a circulant matrix do to a column of $\mathbf{F}^{-1}$? It multiplies it by a number, its eigenvalue.

Where you’ll meet this

OFDM. Wi-Fi and 4G and 5G mobile radio send data on many frequencies at once. Each block starts with a copy of its own end, the cyclic prefix, so the radio channel acts on the block as a circulant matrix. One FFT then turns the channel into one number per frequency, which the receiver divides out. Digital modulation and OFDM builds this.

Fast filtering. Filtering a signal directly costs one product per sample for every filter tap. Through the FFT, a circulant becomes a diagonal matrix, and for long filters the cost per sample grows only slowly with the filter’s length.

Images and scans. Image filters and the reconstruction of MRI scans use the two-dimensional Fourier matrix the same way.

Reference card