# How to prove that $N^{-1/2} W_N$ is an unitary matrix?

How to prove that $N^{-1/2} W_N$ is an unitary matrix( Suggestion: Use lemma 2.2 and lemma 1.105 ii.) \ Lemma 1.105 Let $A$ be an $n \times n$ matrix over $C$. Then the following statements are equivalent: i. A is unitary ii. The columns of A form an orthonormal basis for $C^n$ iii. The rows of A form an orthonormal basis for $C^n$ iv. A preserves inner products, that is, $\langle Az, Aw \rangle =\langle z, w \rangle$ for all $z,w \in C^n$ v. $||Az|| = ||z||$, for all $z \in C^n$ \ lemma 2.2 The set ${E_0,...,E_{N-1} }$ is an orthonormal basis for $l^2(Z_N)$.

Also $W_N = \left(\begin{array}{ccccccc} 1 & 1 & 1 & 1 & . & . & 1 \\ 1 & \omega_N & \omega_N^2 & \omega_N^3 & . & . & \omega_N^{N-1} \\ 1 & \omega_N^2 & \omega_N^4 & \omega_N^6 & . & . & \omega_N^{2(N-1)} \\ 1 & \omega_N^3 & \omega_N^6 & \omega_N^9 & . & . & \omega_N^{3(N-1)} \\ . & . & . & . & . & . & . \\ . & . & . & . & . & . & . \\ 1 & \omega_N^{N-1} & \omega_N^{2(N-1)} & \omega_N^{3(N-1)} & . & . & \omega_N^{(N-1)(N-1)} \\ \end{array}\right)$

where $\omega_N = e^{-2 \pi i/N}$. Consequently $\omega_N^{mn} = e^{-2 \pi i mn/N}$ .This homework in linear algebra.I have no idea how to proceed in proving it, because it might become quite a technical proof if one does some computing, but I hope it is done by lemma 1.105 and lemma 2.2.

-
why don't you just compute $W_N^*W_N$????? – user1709 Nov 11 '10 at 11:57
Despite what Slowsolver and I said, my experience is that hints in math books really make problems easier. You could note the common phrase"orthonormal basis" in the lemmas you cite. I don't see enough about the set in 2.2 to know what do with it, but maybe you can find something useful to do with it. – Ross Millikan Nov 11 '10 at 15:43

Following Slowsolver,note that the entries along a row or column are in geometric progression. So just write down $W_N^*W_N$ from the definition of a matrix multiplication. It will be a sum of N terms in geometric progression, which you can sum. The powers in each sum off the main diagonal will form a permutation of $\{0,1,2,\ldots,N-1\}$. As they are all the $N^{th}$ roots of unity, they sum to zero. Along the main diagonal you will get all 1's, which sum to N.