DFT as a Matrix Operation 2.4 2002/12/12 2003/04/21 Rob "The Kid" Nowak nowak@rice.edu Liqun Wang liqun@rice.edu Rob "The Kid" Nowak nowak@rice.edu DFT FFT linear algebra matrix vector This module introduces linear algebra, DFT, FFT, matrix and vector.

Matrix Review Recall: Vectors in N : xi xi x x0 x1 … x N - 1 Vectors in N : xi xi x x0 x1 … x N - 1 Transposition: transpose: x x0 x1 … x N - 1 conjugate: x x0 x1 … x N - 1 Inner product: real: x y i 0 N 1 xi yi complex: x y i 0 N 1 xn yn Matrix Multiplication: A x a 0 0 a 0 1 … a 0 , N - 1 a 1 0 a 1 1 … a 1 , N - 1 ⋮ ⋮ … ⋮ a N - 1 , 0 a N - 1 , 1 … a N - 1 , N - 1 x0 x1 … x N - 1 y0 y1 … y N - 1 yk n 0 N 1 a k ⁢ n xn Matrix Transposition: A a 0 0 a 1 0 … a N - 1 , 0 a 0 1 a 1 1 … a N - 1 , 1 ⋮ ⋮ … ⋮ a 0 , N - 1 a 1 , N - 1 … a N - 1 , N - 1 Matrix transposition involved simply swapping the rows with columns. A A The above equation is Hermitian transpose. A k n A n k A k n A n k

Representing DFT as Matrix Operation Now let's represent the DFT in vector-matrix notation. x x 0 x 1 … x N 1 X X 0 X 1 … X N 1 N Here x is the vector of time samples and X is the vector of DFT coefficients. How are x and X related: X k n 0 N 1 x n 2 N k n where a k ⁢ n 2 N k n WN k n so X W x where X is the DFT vector, W is the matrix and x the time domain vector. W k n 2 N k n X W x 0 x 1 … x N 1 IDFT: x n 1 N k 0 N 1 X k 2 N n k where 2 N n k WN n k WN n k is the matrix Hermitian transpose. So, x 1 N W X where x is the time vector, 1 N W is the inverse DFT matrix, and X is the DFT vector.