Is the Discrete Fourier Transform a Unitary Transformation?

[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?

 

[vela]

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.

 

[Emperor42]

I understand that I haven't 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?

 

[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.

 

[vela]

I understand that I haven't 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?

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.