Steven M. Kay: “Modern Spectral Estimation – Theory and Applications”,p. 34 exercise 2.3

Author: Panagiotis

27 Sep

In exercise [1, p. 34 exercise 2.3] we are asked to prove that the normalized DFT matrix given in [1, p. 21, (2.22)] is unitary.
Solution: The normalized $N\times N$ DFT matrix is given by:

$\mathbf{W}$

$=$

$\frac{1}{{\sqrt N }}\left[ {\begin{array}{*{20}c} 1 & 1 & \cdots & 1 \\ 1 & {e^{( - j\frac{{2\pi }}{N})} } & \cdots & {e^{( - j\frac{{2\pi }}{N} \cdot (N - 1))} } \\ 1 & {e^{( - j\frac{{2\pi }}{N} \cdot 2)} } & \cdots & {e^{( - j\frac{{2\pi }}{N} \cdot 2 \cdot (N - 1))} } \\ \vdots & \vdots & \vdots & \vdots \\ 1 & {e^{( - j\frac{{2\pi }}{N} \cdot (N - 1))} } & \cdots & {e^{( - j\frac{{2\pi }}{N} \cdot (N - 1)^2 )} } \\ \end{array}} \right]$

(1)

$\mathbf{W} \mathbf{W}^H$

$=$

$\frac{1}{N}\left[ {\begin{array}{*{20}c} 1 & 1 & \cdots & 1 \\ 1 & {e^{( - j\frac{{2\pi }}{N})} } & \cdots & {e^{( - j\frac{{2\pi }}{N} \cdot (N - 1))} } \\ 1 & {e^{( - j\frac{{2\pi }}{N} \cdot 2)} } & \cdots & {e^{( - j\frac{{2\pi }}{N} \cdot 2 \cdot (N - 1))} } \\ \vdots & \vdots & \vdots & \vdots \\ 1 & {e^{( - j\frac{{2\pi }}{N} \cdot (N - 1))} } & \cdots & {e^{( - j\frac{{2\pi }}{N} \cdot (N - 1)^2 )} } \\ \end{array}} \right]$

$\cdot \left[ {\begin{array}{*{20}c} 1 & 1 & \cdots & 1 \\ 1 & {e^{(j\frac{{2\pi }}{N})} } & \cdots & {e^{(j\frac{{2\pi }}{N} \cdot (N - 1))} } \\ 1 & {e^{(j\frac{{2\pi }}{N} \cdot 2)} } & \cdots & {e^{(j\frac{{2\pi }}{N} \cdot 2 \cdot (N - 1))} } \\ \vdots & \vdots & \vdots & \vdots \\ 1 & {e^{(j\frac{{2\pi }}{N} \cdot (N - 1))} } & \cdots & {e^{(j\frac{{2\pi }}{N} \cdot (N - 1)^2 )} } \\ \end{array}} \right]$

(2)

The above multiplication results in:

$\mathbf{W}\mathbf{W}^H =\frac{1}{N} \cdot$

$\cdot \left[ {\begin{array}{*{20}c} N & {\sum\limits_{k = 0}^{N - 1} {e^{(j\frac{{2\pi }}{N}k)} } } & \cdots & {\sum\limits_{k = 0}^{N - 1} {e^{(j\frac{{2\pi }}{N} \cdot (N - 1) \cdot k)} } } \\ {\sum\limits_{k = 0}^{N - 1} {e^{ - (j\frac{{2\pi }}{N}k)} } } & N & \cdots & {\sum\limits_{k = 0}^{N - 1} {e^{(j\frac{{2\pi }}{N} \cdot (N - 2) \cdot k)} } } \\ {\sum\limits_{k = 0}^{N - 1} {e^{ - (j\frac{{2\pi }}{N} \cdot 2 \cdot k)} } } & {\sum\limits_{k = 0}^{N - 1} {e^{ - (j\frac{{2\pi }}{N}k)} } } & \cdots & {\sum\limits_{k = 0}^{N - 1} {e^{(j\frac{{2\pi }}{N} \cdot (N - 3) \cdot k)} } } \\ \vdots & \vdots & \vdots & \vdots \\ {\sum\limits_{k = 0}^{N - 1} {e^{ - (j\frac{{2\pi }}{N} \cdot (N - 1) \cdot k)} } } & {\sum\limits_{k = 0}^{N - 1} {e^{ - (j\frac{{2\pi }}{N} \cdot N \cdot k)} } } & \cdots & N \\ \end{array}} \right]$

(3)

The elements of the matrix $\mathbf{W}\mathbf{W}^H=[w_{ml}]$ for $m \neq l$ are sums of geometric series which are given by [2, p. 16] $S=1+a+a^2+....+a^{(N-1)}=\frac{1-a^N}{1-a}$ . Thus e.g. for $w_{12}$ the following result is derived:

$w_{12}$	$=$	$\sum\limits\limits_{k = 0}^{N - 1} {e^{(j\frac{{2\pi }}{N}k)} }$
	$=$	$\frac{1-{e^{(j\frac{{2\pi }}{N}N)} }}{1-{e^{(j\frac{{2\pi }}{N})} }}$
	$=$	$0.$