# Why is the dot product of two columns $j$ and $k$ in FFT equal to $1+w^{j-k} + \dots + w^{(n-1)(j-k)}$?

The matrix is of the following form:

$$\begin{pmatrix} 1 & 1 & \cdots & 1 & 1 \\ 1 & w & \cdots & w ^{n-2} & w^{n-1} \\ \vdots & \vdots & \ddots & \vdots & w^{2(n-1)} \\ 1 & w^{n-1} & \cdots & w^{(n-2)(n-1)} & w^{(n-1)(n-1)} \\ \end{pmatrix}$$

where $$w$$ is an $$n^{th}$$ root of unity.

The book I am reading now says that if we take any two columns $$j = \overline{0, n-1}$$ and $$k = \overline{0, n-1}$$ then the dot product is $$1 + w^{j-k} + w^{2(j-k)} + \dots + w^{(n-1)(j-k)}$$

Shouldn't be it like $$1 + w^{j+k} + w^{2(j+k)} + \dots + w^{(n-1)(j+k)}$$ with $$j+k$$ in powers, not $$j-k$$?

• This is because this is a Hermitian inner product, not a Euclidean one. – Lord Shark the Unknown Dec 17 '18 at 19:33
• @LordSharktheUnknown, thank you very much. I didn't know about Hermitian products. Should I delete the question? Or you can write this in the answer, so I accept it – Turkhan Badalov Dec 17 '18 at 19:45

Over the complex numbers, the inner product of two vectors $$u=(u_1,\ldots,u_n)$$ and $$u=(v_1,\ldots,v_n)$$ is often defined as $$\left=\sum_{i=1}^n u_i\overline{v_i}$$. This is $$\Bbb C$$-linear in the first argument, but conjugate linear in the second: $$\left=\overline\alpha\left$$. This has the advantage that $$\left$$ is a positive real whenever $$u$$ is a nonzero vector.
Here $$\overline w=w^{-1}$$ so the inner product of $$(1,w^j,w^{2j},\ldots,w^{(n-1)j})$$ and $$(1,w^k,w^{2k},\ldots,w^{(n-1)k})$$ is $$\sum_{i=0}^{n-1}w^{ik}\overline{w^{jk}}=\sum_{i=0}^{n-1}w^{i(j-k)}.$$