Proving $(e_{j})(k)=\frac{1}{\sqrt{N}}e^{(2\pi ijk)/N}$ is an orthonormal basis for $\mathbb C^n$

Question

I know that in order to do this I need to show that $\langle e_j,e_l \rangle =\delta_{j,l}$ and I can show the fact that if $j=l$ I get $1$ but I'm really struggling showing $\langle e_j,e_l\rangle =0$, for $j\neq l$. I am fairly sure that once I know it is an orthonormal set I am fine to show it spans and so is a basis, after all it is N orthonormal vectors in a space of dimension N so it must span, making it a basis.

Answer 1

Let $j \neq l$ be elements of $\Bbb Z/N\Bbb Z$ and put $d = j - l$.

Write $\zeta$ for $e^{2\pi id/N}$, so that $\zeta^N = 1$ and $\zeta \neq 1$.

By definition, $\langle e_j, e_l\rangle = \frac 1 N \sum\limits_{k \in \Bbb Z/N\Bbb Z} \zeta^k$, and we want to show that it is equal to $0$.

Let $S$ be the sum $\sum\limits_{k \in \Bbb Z/N\Bbb Z} \zeta^k$. We then have:

$$S = \sum_{k \in \Bbb Z/N\Bbb Z}\zeta^k = \sum_{t \in \Bbb Z/N\Bbb Z}\zeta^{t + 1} = \zeta \sum_{t \in \Bbb Z/N\Bbb Z}\zeta^t = \zeta S,$$ where in the second step we made a change of variable $k = t + 1$.

Therefore we get $(1 - \zeta)S = 0$, and hence $S = 0$, since $\zeta \neq 1$.

Answer 2

I'll offer a slight variant on @WhatsUp's proof. For $N\ge2$ define $\zeta:=\exp 2\pi i(j-l)/N$, an $N$th root of unity differing from $1$ if $j\ne l$. Supposing without loss of generality that (i) our inner product is linear in its leftmost argument and (ii) $j-l$ is coprime to $N$ (since if their highest common factor is $d$ we just get $d$ copies of each term in the sum I'm about to discuss), $N\langle e_j,\,e_l\rangle=\sum_{k=0}^{N-1}\zeta^k$ is a permutation of the sum of the roots of $z^N-1$, which is $0$ because the $z^{N-1}$ coefficient is $0$. By contrast, if $j=l$ our sum is just $N$ copies of $1$, establishing orthonormality.