Complex Matrices

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}

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.

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,
$\begin{matrix} \|\mathbf{z}\|=\mathbf{z}\cdot\mathbf{z}=\mathbf{\overline{z}}^T\mathbf{z};\quad \mathbf{z}\in\mathbb{C}^n \end{matrix}$
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.

\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

\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,

\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})

\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,

\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

DFT matrix is an Orthogonal Matrix, all column vectors are orthogonal to each other.
$\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,

\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

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