Complex Matrix

Say we have a vector $\vec{z}\in\mathbb{C}^n$ here elements of $\vec{z}$ are complex, $z_i=a_i+ib_i$
$\vec{z}=\begin{bmatrix} z_1\\z_2\\ \vdots \\z_n\\ \end{bmatrix}$ how can we find the length of vector $\vec{z}$

note

Magnitude of a complex number $z_i$ is,
$\|z_i\|=\|\overline{z_i}\|\|z_i\|$
$\|z_i\|=(a_i - ib_i)(a_i + ib_i)$
$\|z_i\|=a_i^2 + b_i^2$

We can get the magnitude of $\vec{z}$ by taking dot product $\vec{z}\cdot\vec{z}$, but how to take the dot product of of two complex vectors.

note

We can not compute dot product like $\vec{z}\cdot\vec{z}=\vec{z}^T\vec{z}$
Say $\vec{z}=\begin{bmatrix} 1\\i\\ \end{bmatrix}$ then $\vec{z}^T\vec{z}=a^2+i^2=0$
But we can clearly see that the magnitude of $\vec{z}$ is not $0$

Magnitude of a complex vector is given as,

danger

$$\begin{matrix} \|\mathbf{z}\|=\mathbf{z}\cdot\mathbf{z}=\mathbf{\overline{z}}^T\mathbf{z};\quad \mathbf{z}\in\mathbb{C}^n \end{matrix}$$

note

So for $\vec{z}=\begin{bmatrix} 1\\i\\ \end{bmatrix}$ magnitude of $\mathbf{z}$ is $\|\mathbf{z}\|=\mathbf{\overline{z}}^T\mathbf{z}$
$\|\mathbf{z}\|=\begin{bmatrix} \overline{1} & \overline{i}\\ \end{bmatrix} \begin{bmatrix} 1\\i\\ \end{bmatrix}$
$\|\mathbf{z}\|=1 \times \overline{1} + i\overline{i}$
$\|\mathbf{z}\|= 1 - i^2$
$\|\mathbf{z}\|= 1 + 1$
$\|\mathbf{z}\|= 2$

$\mathbf{\overline{z}}^T\mathbf{z}$ is also written as $\mathbf{z}^H\mathbf{z}$ we pronounce it as "z Hermitian z".
Dot product between two complex vector say $\mathbf{u},\mathbf{v} \in\mathbb{C}^n$ is given as.

danger

$$\begin{matrix} \mathbf{u}\cdot\mathbf{v}=\mathbf{\overline{u}}^T\mathbf{v}=\mathbf{u}^H\mathbf{v};\quad \mathbf{u},\mathbf{v}\in\mathbb{C}^n \end{matrix}$$

Complex symmetric matrices

What we have seen for symmetric matrix is $A^T=A$ but it's only true if all the elements of $A$ are Real.
A Complex matrix is symmetric if

danger

$$\begin{matrix} \overline{A}^T=A \end{matrix}$$

And these matrices are known as Hermitian matrices.

Complex Orthonormal Vectors

Say we have an orthogonal matrix $Q\in\mathbb{C}^{n\times n}$ whose column vectors are perpendicular to each other.

$$Q=\begin{bmatrix} \vdots & \vdots & & \vdots \\ q_1 & q_2 & \cdots & q_n \\ \vdots & \vdots & & \vdots \\ \end{bmatrix}$$

all columns vectors are perpendicular to each other,

$$\overline{q_i}^Tq_j=\left\{\begin{matrix} 0& \text{if }i\neq j\\ 1& \text{if }i=j \\ \end{matrix}\right.$$

And we can also say,

danger

$$\begin{matrix} \overline{Q}^TQ=Q^HQ=\mathcal{I} \end{matrix}$$

Fast Fourier Transform

We discussed about Fourier Series.

$$f(x)=a_0 1+a_1\cos(x)+b_1\sin(x)+a_2\cos(2x)+b_2\sin(2x)+\cdots$$

Now assume we have $n$ samples $(f_0,f_2,\cdots,f_{n-1})$ from a signal $f$, we only have some realizations of $f$ so we can only have a Discrete Fourier Transform .
Using these $n$ samples we want to approximate the there fourier coefficient $(\hat{f}_0, \hat{f}_1, \cdots , \hat{f}_{n-1})$.

danger

$$\begin{matrix} \displaystyle \hat{f}_k=\sum_{j=0}^{n-1}f_j \exp\left(\frac{-i2\pi jk}{n}\right) \end{matrix}$$

$$f_k=\frac{1}{n}\left(\sum_{j=0}^{n-1}\hat{f}_j \exp\left(\frac{ i2\pi jk}{n}\right)\right)$$

Say,

danger

$$\begin{matrix} \displaystyle \omega_n=\exp\left(\frac{i2\pi}{n}\right) \end{matrix}$$

We can rewrite the above equations as,

$$\begin{bmatrix} \hat{f}_0\\\hat{f}_1\\\hat{f}_2\\ \vdots \\\hat{f}_{n-1}\\ \end{bmatrix}= \underbrace{\begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega_n & \omega_n^2 & \cdots & \omega_n^{n-1}\\ 1 & \omega_n^2 & \omega_n^4 & \cdots & \omega_n^{2(n-1)}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega_n^{n-1} & \omega_n^{2(n-1)} & \cdots & \omega_n^{(n-1)^2}\\ \end{bmatrix}}_{\text{DFT matrix say } F_n} \begin{bmatrix} f_0\\f_1\\f_2\\ \vdots \\f_{n-1}\\ \end{bmatrix}$$

$\omega_n$ is an complex number so DFT matrix is a Complex Matrix, so our fourier coefficient $(\hat{f}_0, \hat{f}_1, \cdots , \hat{f}_{n-1})$ are also complex number.

• Magnitude of $\hat{f}_i$ tells us the magnitude of the $i^{th}$ $\sin$ and $\cos$.
• Phase of $\hat{f}_i$ tells us the phase of the $i^{th}$ $\sin$ and $\cos$.

info

DFT matrix is an Orthogonal Matrix, all column vectors are orthogonal to each other.

danger

$$\begin{matrix} \overline{F}_n^TF_n=F_n^HF_n=\mathcal{I}_n \end{matrix}$$

Now the problem is this matrix multiplication, time complexity of this matrix multiplication is $O(n^2)$, for a matrix of size $1024\times 1024$ then it requires $1,048,576$ multiplications.
This problem is solved by Fast Fourier Transform
IDEA behind FFT is we can write $F_n$ as,

danger

$$\begin{matrix} F_n = \begin{bmatrix} \mathcal{I}_{n/2} & -D_{n/2}\\ \mathcal{I}_{n/2} & D_{n/2}\\ \end{bmatrix} \begin{bmatrix} F_{n/2} & 0\\ 0 & F_{n/2}\\ \end{bmatrix} P_n \end{matrix}$$

$D_{n/2}=\begin{bmatrix} 1 & 0 & 0 & \cdots & 0 \\ 0 & \omega_{n/2} & 0 & \cdots & 0 \\ 0 & 0 & \omega_{n/2}^2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \omega_{n/2}^{n/2-1} \end{bmatrix}$

$P_n$ is a $n\times n$ even and odd permutation matrix.

$P_n= \begin{bmatrix} \color{red}{1} & \color{red}{0} & \color{red}{0} & \color{red}{0} & \cdots & \color{red}{0} & \color{red}{0} \\ \color{red}{0} & \color{red}{0} & \color{red}{1} & \color{red}{0} & \cdots & \color{red}{0} & \color{red}{0} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \color{red}{0} & \color{red}{0} & \color{red}{0} & \color{red}{0} & \cdots & \color{red}{1} & \color{red}{0} \\ \color{blue}{0} & \color{blue}{1} & \color{blue}{0} & \color{blue}{0} & \cdots & \color{blue}{0} & \color{blue}{0} \\ \color{blue}{0} & \color{blue}{0} & \color{blue}{0} & \color{blue}{1} & \cdots & \color{blue}{0} & \color{blue}{0} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \color{blue}{0} & \color{blue}{0} & \color{blue}{0} & \color{blue}{0} & \cdots & \color{blue}{0} & \color{blue}{1} \\ \end{bmatrix}$

FFT will have to make $\frac{1}{2}n\log_2(n)$ calculations

info

FFT gives time complexity of $n\log_2(n)$

For $n=1024=2^{10}$

• DFT will have to make $n^2=1,048,576$ calculations
• FFT will have to make only $\frac{1}{2}n\log_2(n)=5,120$ calculations So here FFT is more then $200x$ faster then DFT