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)}$?

176 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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<u,v\right>=\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<u,\alpha v\right>=\overline\alpha\left<u,v\right>$. This has the advantage that $\left<u,u\right>$ 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)}.$$