Fast Fourier Transform
Assume we have $n$ data points $x_0, x_1, \ldots, x_{n-1}$. For convenience, assume $n$ is a power of two; if it’s different, we can just pad with zeroes. We want to efficiently compute the transformed sequence $y_k = x_0 + w^kx_1 + w^{2k}x_2 + \ldots + w^{(n-1)k}x_{n-1}$, where $w$ is the nth root of unity. We can represent these equations in matrix notation as $\bar y = V_n \bar x$, where $V_n$ is the Vandermonde matrix of $1, w, \ldots, w^{n-1}$.
For illustration purposes, let’s now take $n = 8$. For the first two entries of $\bar y$, we can separate out the even and odd-indexed terms as
$$
\begin{eqnarray}
y_0 &=& (x_0 + x_2 + x_4 + x_6) + (x_1 + x_3 + x_5 + x_7) \\
y_1 &=& (x_0 + x_2w^2 + x_4w^4 + x_6w^6) + (x_1w + x_3w^3 + x_5w^5 + x_7w^7) \\
&=& (x_0 + x_2w^2 + x_4w^4 + x_6w^6) +w (x_1 + x_3w^2 + x_5w^4 + x_7w^6) \\
&=& (x_0 + x_2u + x_4u^2 + x_6u^3) +w (x_1 + x_3u + x_5u^2 + x_7u^3)
\end{eqnarray}
$$
where $u = w^2$ is the $n/2$-th root of unity. Let $\bar x_e = (x_0, x_2, x_4, x_6)^T$ and $\bar x_o = (x_1, x_3, x_5, x_7)^T$. Then we can see that $y_0$ is the first entry in the DFT of $\bar x_e$ plus the first entry in the DFT of $\bar x_o$. Also, $y_1$ is the second entry in the DFT of $\bar x_e$ plus $w$ times the second entry in the DFT of $\bar x_o$. Let’s now look at $y_2$:
$$
\begin{eqnarray}
y_2 &=& (x_0 + x_2w^4 + x_4w^8 + x_6w^{12}) + (x_1w^2 + x_3w^6 + x_5w^{10} + x_7w^{14}) \\
&=& (x_0 + x_2w^4 + x_4w^8 + x_6w^{12}) +w^2 (x_1 + x_3w^4 + x_5w^8 + x_7w^{12}). \\
&=& (x_0 + x_2u^2 + x_4u^4 + x_6u^6) +w^2 (x_1 + x_3u^2 + x_5u^4 + x_7u^6). \\
\end{eqnarray}
$$
As expected, this is the this is the third entry in the DFT of $\bar x_e$ plus $w^2$ times the third entry in the DFT of $\bar x_o$. It’s looking like $y_k$ will equal the kth row of $V_{\frac{n}{2}} \bar x_e + D V_{\frac{n}{2}} \bar x_o$, where $D = diag(1, w, \ldots, w^{k-1})$. Except wait: the matrix in the last expression only has $n/2$ rows, but there are $n$ different $y_k$’s. So what happens to a larger $k$, say $y_5$?
$$
\begin{eqnarray}
y_5 &=& (x_0 + x_2w^{10} + x_4w^{20} + x_6w^{30}) + (x_1w^5 + x_3w^{15} + x_5w^{25} + x_7w^{35}) \\
&=& (x_0 + x_2w^{10} + x_4w^{20} + x_6w^{30}) + w^5(x_1 + x_3w^{10} + x_5w^{20} + x_7w^{30}) \\
&=& (x_0 + x_2u^5 + x_4u^{10} + x_6u^{15}) + w^5 (x_1 + x_3u^5 + x_5u^{10} + x_7u^{15}) \\
&=& (x_0 + x_2u^5 + x_4u^{10} + x_6u^{15})\ -\ w(x_1 + x_3u^5 + x_5u^{10} + x_7u^{15}) \\
&=& (x_0 + x_2u + x_4u^2 + x_6u^3)\ -\ w(x_1 + x_3u + x_5u^2 + x_7u^3)
\end{eqnarray}
$$
because $w^4 = -1$ and $u^4 = w^8 = 1$. So for $k = n/2 + j$, we have $y_k$ equals the jth row of $V_{\frac{n}{2}} \bar x_e\ -\ D V_{\frac{n}{2}} \bar x_o$.
Let’s put this all together. Define $\bar y_e$ and $\bar y_o$ as with $\bar x_e$ and $\bar x_o$. Then we find
$$
\begin{eqnarray}
\bar y_{0:3} &=& V_{\frac{n}{2}}\bar x_e + DV_{\frac{n}{2}}\bar x_o \\
\bar y_{4:7} &=& V_{\frac{n}{2}}\bar x_e – DV_{\frac{n}{2}}\bar x_o \\
\end{eqnarray}
$$
or in other words
\begin{eqnarray}
\bar y &=&
\begin{bmatrix}
I & D \\
I & -D
\end{bmatrix}
\begin{pmatrix}
V_{\frac{n}{2}}\bar x_e \\
V_{\frac{n}{2}} \bar x_0
\end{pmatrix} \\
&=&
\begin{bmatrix}
I & D \\
I & -D
\end{bmatrix}
\begin{bmatrix}
V_{\frac{n}{2}} & 0 \\
0 & V_{\frac{n}{2}}
\end{bmatrix}
\begin{pmatrix}
\bar x_e \\
\bar x_o
\end{pmatrix} \\
&=&
\begin{bmatrix}
I & D \\
I & -D
\end{bmatrix}
\begin{bmatrix}
V_{\frac{n}{2}} & 0 \\
0 & V_{\frac{n}{2}}
\end{bmatrix}
P \bar x
\end{eqnarray}
where P is the appropriate permutation matrix to separate $\bar x$ into its even and odd components. We’ve discovered how to recursively factor $V_n$ in terms of $V_{\frac{n}{2}}$.
Inversion
Note that $V_n^H V_n = nI$ (prove this), so $V_n^{-} = \frac{1}{n}V^H$.