Complex Matrices and Fourier Transform

23.1 Complex Vectors/Matrices

Let \(z = \begin{bmatrix} z_1 \\ z_2 \\ ... \\ z_n \end{bmatrix}\) be a complex vector in \(C^n\). The expresson \(z^Tz\) doesn’t represent the length of the vector \(z\). Instead it’s length is represented by \(\overline{z}^Tz\). \(\overline{z}^T\) is also called as \(z^H\) and is called as Hermitian of a matrix. Hence, the length of a complex vector is \(z^Hz = |z_1|^2 + |z_2|^2 + ... + |z_n|^2\). Similarly, for a complex matrix \(A\) to be symmetric, \(A^H = A\) with diagonal elements being real. In a complex domain, we call symmetric matrices as Hermitian Matrices. For two vectors \(x\) and \(y\) in a complex plane are perpendicular to each other if and only if \(y^Hx = 0\). Hence, for an orrhogonal matrix (matrix with orthonormal columns) \(Q\) in complex plane, \(Q^HQ = I\). These orthogonal matrices in the complex plane are called as Unitary Matrices.

23.2 Fast Fourier Transform

A \(n \times n\) Fourier Matrix is shown below.

\[\begin{align} F_n = \begin{bmatrix} 1 & 1 & 1 & ... & 1 \\ 1 & w & w^2 & ... & w^{n-1} \\ 1 & w^2 & w^4 & ... & w^{2(n-1)} \\ .. & .. & .. & .. & .. \\ 1 & w^{n-1} & w^{2(n-1)} & ... & w^{(n-1)(n-1)} \end{bmatrix} \end{align}\]

The entry in the \(i^{th}\) and \(j^{th}\) cell where \(i,j = 0,1,2,...,n-1\) is given as \((F_n)_{ij} = w^{ij}\). \(w\) is a complex number such that \(w^n=1\). Or to be more precise, \(w = e^{i\frac{2\pi}{n}} = \cos \frac{2\pi}{n} + i \sin \frac{2\pi}{n}\). All the \(w^k\) lies on a unit circle. For example, if \(n=6\), \(w = e^{i\frac{2\pi}{6}}\) lies at an angle of \(60^{\circ}\) from the real-axis. Similary the other powers (for \(n=6\)) \(w^2, w^3, w^4, w^5, w^6\) lie at an angle of \(120^{\circ}, 180^{\circ}, 240^{\circ}, 300^{\circ}, 360^{\circ}\) from the real-axis.

For \(n=4\), \(w=e^{i\frac{2\pi}{4}} = i\), \(w^2 = -1\), \(w^3 = -i\) and \(w^4 = 1\). The fourier matrix is given as

\[\begin{align} F_4 = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & i^2 & i^3 \\ 1 & i^2 & i^4 & i^6 \\ 1 & i^3 & i^6 & i^9 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix} \end{align}\]

It should be noted that the columns of this matrix is orthogonal. All the columns have a length \(2\) and hence to make the columns orthonormal, we can divide the matrix by \(2\). As the columns being orthonormal, \(F_4^H\) will be the inverse of \(F_4\), i.e. \(F_4^HF_4 = I\). For \(n=k\) and \(n=2k\), we have \(w_k = e^{i\frac{2\pi}{k}}\) and \(w_{2k} = e^{i\frac{2\pi}{2k}}\), i.e. \(w_{2k}^2 = w_{k}\). Using this property any fourier matrix of size \(2k\) can be written as

\[\begin{align} F_{2k} = \begin{bmatrix} I & D \\ I & -D \end{bmatrix}\begin{bmatrix} F_k & 0 \\ 0 & F_k \end{bmatrix}P \end{align}\]

where \(P\) is a permutation matrix and \(D\) is a diagonal matrix. \(F_k\) can be further reduced using recurrsion. Using this property multiplication of a \(n \times n\) matrix will need \(\frac{1}{2}n \log_2 n\) calculations instead of \(n^2\).