# Homework Help: Unitary discrete Fourier transform

1. Dec 11, 2013

### Emperor42

I'm trying to prove that the discrete form of the Fourier transform is a unitary transformation

So I used the equation for the discrete Fourier transform:
$y_k=\frac{1}{\sqrt{N}}\sum^{N-1}_{j=0}{x_je^{i2\pi\frac{jk}{N}}}$

and I put the fourier transform into a N-1 by N-1 matrix form:
$U=\begin{pmatrix} e^0 & e^0 & e^0 & ...\\ e^0 & e^{\frac{i2\pi}{N}} & e^{\frac{i4\pi}{N}} & ...\\ e^0 & e^{\frac{i4\pi}{N}} & e^{\frac{i8\pi}{N}} & ...\\ ... & ... & ... & ...\\ \end{pmatrix}$

and then found the complex conjugate:
$U^*=\begin{pmatrix} e^0 & e^0 & e^0 & ...\\ e^0 & e^{-\frac{i2\pi}{N}} & e^{-\frac{i4\pi}{N}} & ...\\ e^0 & e^{-\frac{i4\pi}{N}} & e^{-\frac{i8\pi}{N}} & ...\\ ... & ... & ... & ...\\ \end{pmatrix}$

But if I multiply these matrices together I get nothing which even approaches the identity matrix. Anyone have any ideas? Is there something wrong with the matrix?

2. Dec 11, 2013

### vela

Staff Emeritus
You omitted the factor of $1/\sqrt{N}$. Without it, the matrix won't be unitary. Also, the inverse of a unitary matrix is its adjoint, not the complex conjugate.

3. Dec 11, 2013

### Emperor42

I understand that I havent put in the $\frac{1}{\sqrt{N}}$. But why do I need the inverse? I'm trying to calculate whether the matrix is unitary so I need to find the inner product of the matrix and its complex conjugate, wouldn't I?

Last edited: Dec 11, 2013
4. Dec 11, 2013

### Emperor42

Ok I think I can get the diagonal elements to go to if I add the $\frac{1}{\sqrt{N}}$ factor but I still don't understand how the off diagonal elements go to zero.

5. Dec 11, 2013

### vela

Staff Emeritus
No. Unitary means that the inverse of the matrix is its adjoint. In other words, if you multiply a unitary matrix by its adjoint (not conjugate), you get the identity matrix, which is what you're trying to show.