The DFT as a matrix

Here the eight probes of The DFT (13.2) sit in a grid, one per row, beside the column $x=1,2,3,4,3,2,1,0$. Make a guess before you play it: what does row 0, whose arrows never turn, do to the column?

The DFT as one matrix

The DFT (13.2) gave you $N$ bins, and each bin was a probe: eight arrows that turn a fixed amount per sample, multiplied into the signal and added up. That is $N$ sums of $N$ products. In Discrete convolution (5.2) you met a grid of numbers multiplied into a column, and this is the same shape of calculation. This page writes the DFT that way, and then asks what the grid is good for.

Stack the samples $x[0],\dots,x[N-1]$ into one column, $\mathbf{x}$. Stack the bins into another, $\mathbf{X}$. Then

where $\mathbf{F}$ is the DFT matrix, an $N\times N$ grid whose entry in row $k$ and column $n$ is

Here $W_N=e^{-j2\pi/N}$, the arrow from 13.2 that turns $1/N$ of a turn clockwise. Row $k$ of the grid is probe $k$. A row times a column means: multiply entry by entry, then add. This is the dot product, and it is exactly the sum that defined $X[k]$.

In the picture at the top, row 0 is all ones, so its dot product is the plain sum of the samples, 16. Row 1 times $\mathbf{x}$ is the chain of arrows you drew in 13.2, now as one row of the grid, and it gives $X[1]=-4.83-4.83j$. After the clip ends, tap a row, or use the arrow keys, to read its bin.

Notice the two extremes. Row 0 never turns, so it adds the samples as they are. Row 4 turns half a turn per column, so its arrows alternate $+1,-1,+1,\dots$ and every other column is flipped. Every other row is somewhere between.

A small case by hand

Take $N=4$. Then $W_4=e^{-j\pi/2}=-j$, and the four rows of $\mathbf{F}$ are

For $\mathbf{x}=(1,2,3,4)$, the dot product of row 1 with $\mathbf{x}$ is $1-2j-3+4j=-2+2j$. Doing the other rows the same way gives

which is what np.fft.fft returns for the same input.

Rows that cancel

If $\mathbf{F}$ is a grid, can I undo it? To find out, I need to know what happens when I multiply two of its rows against each other. First, three words.

The conjugate transpose of $\mathbf{F}$, written $\mathbf{F}^{\mathsf H}$, swaps rows and columns and conjugates every entry. Because $\mathbf{F}$ is symmetric, $F_{kn}=F_{nk}$, this only conjugates: $(\mathbf{F}^{\mathsf H})_{kn}=e^{+j2\pi kn/N}$. Now take row $p$ and row $q$. Multiply row $p$ by the conjugate of row $q$, entry by entry, and add. Two rows are orthogonal when this sum is 0. The identity matrix $\mathbf{I}$ has 1 on its diagonal and 0 elsewhere, so $\mathbf{I}\mathbf{x}=\mathbf{x}$.

Before you play the clip, make a guess. Row 1 turns $1/8$ of a turn per column. Row 2 turns twice as fast. When I multiply row 1 by the conjugate of row 2, how fast do the products turn? Then watch the chain of products: it closes for every row but one.

A chain that closes adds to 0, which is the fact from The DTFT (12.2) and from Complex numbers for signals (3.3): $N$ equal steps round a circle add to 0. Row 1 against itself is the exception. Each product is $e^{-j2\pi n/8}\,e^{+j2\pi n/8}=1$, so the chain is a straight line of length 8. Only $q=1$ gives a straight chain.

What the cancelling gives

Every row against every row is one entry of the product $\mathbf{F}^{\mathsf H}\mathbf{F}$ (the rows of $\mathbf{F}^{\mathsf H}$ are the conjugated columns, and these match the conjugated rows because $\mathbf{F}$ is symmetric). The clip showed that those entries are $N$ on the diagonal and 0 off it:

Divide by $N$ and you have the inverse, $\mathbf{F}^{-1}=\tfrac1N\mathbf{F}^{\mathsf H}$, so

This is the inverse DFT of 13.2, with $e^{+j2\pi kn/N}$ and the $1/N$ in front. In the $N=4$ case, $\mathbf{F}^{\mathsf H}\mathbf{F}$ comes out as $4\mathbf{I}$, and $\tfrac14\mathbf{F}^{\mathsf H}(10,\,-2+2j,\,-2,\,-2-2j)$ gives back $(1,2,3,4)$.

There is a way to keep every length. A matrix is unitary when its conjugate transpose is its inverse. The matrix $\mathbf{F}$ is not, because $\mathbf{F}^{\mathsf H}\mathbf{F}=N\mathbf{I}$ and not $\mathbf{I}$. But $\tfrac1{\sqrt N}\mathbf{F}$ is, because the two factors of $1/\sqrt N$ multiply to the missing $1/N$. On this site the unitary DFT always shows its scale, and its output is never called $X[k]$, because $X[k]$ is the DFT with no scale.

Length squared is energy, from How big is a signal (1.3). The unitary DFT keeps it:

That is Parseval’s relation from 13.2, $\sum_n\lvert x[n]\rvert^2=\tfrac1N\sum_k\lvert X[k]\rvert^2$, in matrix form. Check it for $\mathbf{x}=(1,2,3,4)$: the energy is $1+4+9+16=30$, and the squared sizes of $\mathbf{X}$ are $100$, $8$, $4$ and $8$, which sum to $120=4\times30$. Divide by $N=4$ and you are back at 30.

Arrows in, the same arrows out

Now the second use of the grid. In Circular vs linear convolution (13.4) you saw that a circular convolution can be written as a matrix. This is the circulant matrix $\mathbf{C}$ of $h$: each row is the row above it, rotated right by one place, and

For the two-point average $h=0.5,\,0.5$ on a ring of $N=8$ samples, the first row of $\mathbf{C}$ has 0.5 in column 0 and in column 7, and the second row has 0.5 in columns 0 and 1. Each output is $(\mathbf{C}\mathbf{x})[n]=0.5\,x[n]+0.5\,x[n-1]$, the average of a sample and its neighbour round the ring.

One more word. An eigenvector of a matrix is a column that comes out of it only scaled, and the scale is its eigenvalue. Where have you met this? In Properties of LTI systems (5.4), a complex exponential went through a system and came out as the same exponential times a number. A circulant is the circular version of that statement.

Before you play the clip, make a guess. Feed $\mathbf{C}$ the arrow $e^{j2\pi kn/8}$ for $n=0,\dots,7$, which is column $k$ of $\mathbf{F}^{\mathsf H}$. What do you expect to come out?

Notice that all eight output dials shrink and turn by the same amount. After the clip ends, drag across the input dials to try any arrow $k$ from 0 to 7.

Why every sample is scaled by the same number

Put the arrow $v_k[n]=e^{j2\pi kn/N}$ through $\mathbf{C}$. For the two-point average,

The bracket does not contain $n$. It is the same number for every sample, and it is the DFT of $h=0.5,\,0.5$ at bin $k$:

For $N=8$ and $k=1$ this has size $\cos(\pi/8)=0.92$ and angle $-\pi/8=-22.5°$, which matches the clip at $k=1$. For $k=4$ it is $\cos(\pi/2)=0$: the arrow alternates $+1,-1$, and the average of a sample and its neighbour is 0. The wrap-around matters here. Because the ring closes, the identity holds at every $n$ including $n=0$, where the neighbour is $x[7]$.

Convolution becomes multiplication

Stack the eight eigenvectors as the columns of $\mathbf{F}^{\mathsf H}$. Feeding all of them in at once gives

where $\mathrm{diag}(\cdot)$ is the matrix with those numbers on its diagonal and 0 elsewhere. Multiply by $\mathbf{F}$ on the right, and use $\mathbf{F}^{\mathsf H}\mathbf{F}=N\mathbf{I}$:

Read it from right to left. First $\mathbf{F}$ takes the DFT. Then the diagonal matrix multiplies each bin by its own $H[k]$, with no bin touching another. Then $\tfrac1N\mathbf{F}^{\mathsf H}$ inverts. This is the rule of Properties of the DFT (13.3), $h\circledast_N x\leftrightarrow H[k]X[k]$, proved a second time with matrices.

Check it with $N=4$ and $h=0.5,\,0.5,\,0,\,0$. Then $H=(1,\ 0.5-0.5j,\ 0,\ 0.5+0.5j)$. For $\mathbf{x}=(1,2,3,4)$, the matrix product $\mathbf{C}\mathbf{x}$ gives $(2.5,\ 1.5,\ 2.5,\ 3.5)$, and taking the inverse DFT of $H[k]X[k]$ gives the same four numbers. The first output is the average of $x[0]=1$ and its neighbour $x[3]=4$.

Worked example

Here is one by hand, to check that the pieces fit. Take $N=4$, $\mathbf{x}=(1,2,3,4)$ and $h=0.5,\,0.5,\,0,\,0$.

1. The DFT matrix gives $\mathbf{X}=\mathbf{F}\mathbf{x}=(10,\ -2+2j,\ -2,\ -2-2j)$.
2. The eigenvalues are the DFT of $h$: $H=(1,\ 0.5-0.5j,\ 0,\ 0.5+0.5j)$.
3. Multiply bin by bin. Bin 1 gives $(0.5-0.5j)(-2+2j)=2j$ and bin 3 gives $(0.5+0.5j)(-2-2j)=-2j$, so $H[k]X[k]=(10,\ 2j,\ 0,\ -2j)$.
4. Invert with $\tfrac14\mathbf{F}^{\mathsf H}$. The first output is $\tfrac14(10+2j+0-2j)=2.5$. The full result is $(2.5,\ 1.5,\ 2.5,\ 3.5)$, which is the circular convolution computed directly.

Each product in step 3 uses $(0.5-0.5j)(-2+2j)=-1+j+j-j^2=-1+2j+1=2j$ and its conjugate partner $-2j$.

Where you’ll meet this

The matrix $\mathbf{F}$ has a lot of structure, and the next page, The FFT (14.1), uses it: $\mathbf{F}$ can be factored into a few sparse matrices, so the $N^2$ products of this page shrink to about $N\log_2N$. The two-dimensional version, a DFT along rows and then along columns, is The 2-D DFT (28.3).

Reference card