2

The DFT matrix of size $n$ has entries $M_{ij} = \omega^{ij}$ where $\omega$ is the $n$th root of 1. My textbook states that the columns of this matrix are orthogonal because their dot product is 0. The dot product of columns $i$ and $j$ is calculated as $1 + \omega^{j-k} + \omega^{2(j-k)} ... $ but I do not follow. Should it not be $j+k$ in the exponents?

user1299784
  • 2,009

1 Answers1

2

The dot product of vectors $x,y\in\mathbb C^n$ is defined as

$$\sum_{i=1}^nx_i\bar{y_i}\;,$$

where $\bar{y_i}$ is the complex conjugate of $y_i$. Wikipedia gives some motivation for this definition.

joriki
  • 238,052
  • Thanks for the reponse - I understand where j-k comes from. But why does this dot product have the property that when it is 0 the vectors are orthogonal. – user1299784 Jul 11 '15 at 21:53
  • @user1299784: That's the usual definition of orthogonality. To ask that question, you'd need to provide an independent definition of orthogonality. – joriki Jul 11 '15 at 21:54
  • The textbook uses orthogonality to prove that the columns of the matrix are linearly independent, so multiplication by the matrix constitutes a change of basis. If orthogonality is defined using dot product then it must be proven that orthogonality implies linear independence. – user1299784 Jul 11 '15 at 21:56
  • Well, that's not particular to the complex dot product -- it has to be proved for real vectors, too, and the proof is the same in both cases: If $\sum_ic_iv_i=0$, form the dot product with $c_k$. If the $v_i$ are mutually orthogonal, this yields $c_k(v_k\cdot v_k)=0$, which implies $c_k=0$. Incidentally, that last step requires $v_k\cdot v_k\neq0$, and the complex dot product is defined using the complex conjugate to ensure that. – joriki Jul 11 '15 at 22:09
  • I am afraid I still do not follow. You start with a set of linearly dependent vectors $v_1 ...$ that can be summed to 0 using coefficients $c_1... $. But what do you mean by "form the dot product with $c_k$"? – user1299784 Jul 11 '15 at 22:37
  • @user1299784: All vectors can be summed to zero, using zero coefficients. I didn't start with a set of linearly dependent vectors. The (or at least a usual) definition of linear independence is that vectors are linearly independent iff the only way to linearly combine them to zero is with zero coefficients. So I started off with a linear combination that's zero and showed that if the vectors are orthogonal, the coefficients must be zero, thus proving linear independence. By "form the dot product with $c_k$", I mean, derive $c_k\cdot\sum_ic_iv_i=c_k\cdot0$ from $\sum_ic_iv_i=0$. – joriki Jul 11 '15 at 22:44