Editing Discrete Fourier transform (section)

=== The unitary DFT ===
Another way of looking at the DFT is to note that in the above discussion, the DFT can be expressed as the [[DFT matrix]], a [[Vandermonde matrix]],
[[Generalizations of Pauli matrices#Construction: The clock and shift matrices|introduced by Sylvester]] in 1867,
:<math>\mathbf{F} =
\begin{bmatrix}
 \omega_N^{0 \cdot 0}     & \omega_N^{0 \cdot 1}     & \cdots & \omega_N^{0 \cdot (N-1)}     \\
 \omega_N^{1 \cdot 0}     & \omega_N^{1 \cdot 1}     & \cdots & \omega_N^{1 \cdot (N-1)}     \\
 \vdots                   & \vdots                   & \ddots & \vdots                       \\
 \omega_N^{(N-1) \cdot 0} & \omega_N^{(N-1) \cdot 1} & \cdots & \omega_N^{(N-1) \cdot (N-1)} \\
\end{bmatrix}
</math>
where <math>\omega_N = e^{-i 2 \pi/N}</math> is a primitive [[roots of unity|''N''th root of unity]].

For example, in the case when <math>N = 2</math>, <math>\omega_N = e^{-i \pi}=-1</math>, and
:<math>\mathbf{F} =
\begin{bmatrix}
 1    & 1        \\
 1     & -1  \\
\end{bmatrix},
</math>
(which is a [[Hadamard matrix]]) or when  <math>N = 4</math> as in the {{Section link|2=Example}} above, <math>\omega_N = e^{-i \pi/2}=-i</math>, and
:<math>\mathbf{F} =
\begin{bmatrix}
 1 & 1 & 1 & 1       \\
 1 & -i & -1 & i  \\
 1 & -1 & 1 & -1 \\
 1 & i & -1 & -i \\
\end{bmatrix}.
</math>

The inverse transform is then given by the inverse of the above matrix,
:<math>\mathbf{F}^{-1}=\frac{1}{N}\mathbf{F}^*</math>

With [[unitary operator|unitary]] normalization constants <math display="inline">1/\sqrt{N}</math>, the DFT becomes a [[unitary transformation]], defined by a unitary matrix:

:<math>\begin{align}
                   \mathbf{U} &= \frac{1}{\sqrt{N}}\mathbf{F} \\
              \mathbf{U}^{-1} &= \mathbf{U}^* \\
\left|\det(\mathbf{U})\right| &= 1
\end{align}</math>

where <math>\det()</math> is the [[determinant]] function. The determinant is the product of the eigenvalues, which are always <math>\pm 1</math> or <math>\pm i</math> as described below.  In a real vector space, a unitary transformation can be thought of as simply a rigid rotation of the coordinate system, and all of the properties of a rigid rotation can be found in the unitary DFT.

The orthogonality of the DFT is now expressed as an [[orthonormal]]ity condition (which arises in many areas of mathematics as described in [[root of unity]]):
:<math>\sum_{m=0}^{N-1}U_{km}U_{mn}^* = \delta_{kn}</math>

If '''X'''  is defined as the unitary DFT of the vector '''x''', then
:<math>X_k = \sum_{n=0}^{N-1} U_{kn} x_n</math>

and the [[Parseval's theorem]] is expressed as
:<math>\sum_{n=0}^{N-1}x_n y_n^* = \sum_{k=0}^{N-1}X_k Y_k^*</math>

If we view the DFT as just a coordinate transformation which simply specifies the components of a vector in a new coordinate system, then the above is just the statement that the [[dot product]] of two vectors is preserved under a unitary DFT transformation. For the special case <math>\mathbf{x} = \mathbf{y}</math>, this implies that the length of a vector is preserved as well — this is just [[Plancherel theorem]],
:<math>\sum_{n=0}^{N-1} |x_n|^2 = \sum_{k=0}^{N-1} |X_k|^2</math>

A consequence of the [[#Circular convolution theorem and cross-correlation theorem|circular convolution theorem]] is that the DFT matrix {{mvar|F}} diagonalizes any [[circulant matrix]].