Editing Root of unity (section)

==Orthogonality==
From the summation formula follows an [[orthogonality]] relationship: for {{math|1=''j''&nbsp;=&thinsp;1, … , ''n''}} and {{math|1=''j′''&nbsp;=&thinsp;1, … , ''n''}}

:<math>\sum_{k=1}^{n} \overline{z^{j\cdot k}} \cdot z^{j'\cdot k} = n \cdot\delta_{j,j'}</math>

where {{mvar|&delta;}} is the [[Kronecker delta]] and {{mvar|z}} is any primitive {{mvar|n}}th root of unity.

The {{math|''n''&thinsp;×&thinsp;''n''}} [[matrix (mathematics)|matrix]] {{mvar|U}} whose {{math|(''j'', ''k'')}}th entry is

:<math>U_{j,k} = n^{-\frac{1}{2}}\cdot z^{j\cdot k}</math>

defines a [[discrete Fourier transform]].  Computing the inverse transformation using [[Gaussian elimination]] requires {{math|''[[big-O notation|O]]''(''n''<sup>3</sup>)}} operations.  However, it follows from the orthogonality that {{mvar|U}} is [[unitary matrix|unitary]].  That is,

:<math>\sum_{k=1}^{n} \overline{U_{j,k}} \cdot U_{k,j'} = \delta_{j,j'},</math>

and thus the inverse of {{mvar|U}} is simply the complex conjugate. (This fact was first noted by [[Carl Friedrich Gauss|Gauss]] when solving the problem of [[trigonometric interpolation]].)  The straightforward application of {{mvar|U}} or its inverse to a given vector requires {{math|''O''(''n''<sup>2</sup>)}} operations. The [[fast Fourier transform]] algorithms reduces the number of operations further to {{math|''O''(''n'' log ''n'')}}.