I was reading a book on image processing by Bernd Jahne and found what he wrote about the Discrete Fourier transform very interesting. The DFT can be computed as ${\hat{f} = A f}$ (${A}$ has been defined in a previous blog ), so it seems like a linear transformation. A new interpretation is that the rows of ${\hat{A}}$ (or the columns) (${\hat{A}}$ has been defined in a previous blog ) can be thought of as spanning the vector space of all N-tuples of complex numbers denoted by ${\mathbb{C}^N}$. First of all, it can be checked that N-tuples of complex numbers form a vector space. On this vector space, an inner product can be defined as follows :

$\displaystyle = \sum_{k = 0}^{N-1} v_k {\bar{w}_k}$

With this definition of inner product on the vector space, one can easily show that, ${<\frac{1}{\sqrt{N}}u_i,\frac{1}{\sqrt{N}}u_j> = \delta (i-j)}$ where ${u_k}$ is a row (or column) of  ${\hat{A}}$ .

Therefore, if ${C \in \mathbb{C}^N}$ then ${C = \sum_{k = 0}^{N-1} \alpha_k (\frac{1}{\sqrt{N}}u_k)}$ where ${\alpha_k = }$. Clearly the ${\frac{1}{\sqrt{N}}u_k}$ span ${\mathbb{C}^N}$. It can also be checked that ${\alpha_k}$ for ${k \in \{0,1,..,N-1\}}$ is the 1D Fourier transform. Hence the DFT of a vector ${f}$ is just a projection of ${f}$ on the rows of ${\hat{A}}$.

In two dimensions, we consider the set of all ${M\times N}$ complex matrices. This is again a vector space over the field of complex numbers. The basis “vectors” now are the matrices ${(B_{u,v})_{m,n} = D_{m,n} =\frac{1}{\sqrt{MN}} exp(\frac{-2\pi imu}{M}) * exp(\frac{-2\pi inv}{N})}$ for all ${u \in \{0,1,...,M-1\}, v \in \{0,1,...,N-1\}}$. The inner product for two complex matrices is defined as :

$\displaystyle = \sum_{m=0}^{M-1}\sum_{n=0}^{N-1} A_{m,n} {\bar{B}_{m,n}}$

Any complex matrix can then be written as a linear combination of the Basis matrices ${B_{u,v}}$. ${C = \sum_{u=0}^{M-1}\sum_{v=0}^{N-1} \alpha_{u,v} B_{u,v}}$. Then it can be shown that ${\alpha_{u,v}}$ is the 2D Fourier transform for ${u \in \{0,1,..,M-1\}, v \in \{0,1,...,N-1\}}$. So, we are projecting ${C}$ onto the Basis vectors ${B_{u,v}}$. By this reasoning it can be shown that the 2D Fourier transform for a matrix ${C}$ can be written as ${A_M C A_N}$, where ${A_M}$ is the ${M\times M}$ DFT matrix and ${A_N}$ is the ${N \times N}$ DFT matrix.

NOTE: I was only mentioning ${\hat{A}}$ as I was lazy to write the basis vectors. Hope this did not confuse.