A [[Fourier Transform|Fourier]] [[Basis Vectors|Basis Vector]] is a special vector of the [[Complex Vector Space]] $\C^{N}$ space defined as the following: $\huge \vec u_{k} = \mat{ 1 \\ e^{i\frac{2\pi}{N}k \cdot 1} \\ e^{i\frac{2\pi}{N}k \cdot 2} \\ \vdots \\ e^{i\frac{2\pi}{N}k (N-1)} } $ The [[Fourier Basis]] is always an [[Orthogonal Basis]] that [[Span|spans]] $\C^{N}$. >[!example] >ex. for $N=4$, >$ \large \begin{matrix} >\vec u_{0} = \mat{1\\1\\1\\1} & >\vec u_{1} = \mat{1\\i\\-1\\-i} & >\vec u_{1} = \mat{1\\i\\-1\\-i} & >\vec u_{2} = \mat{1\\-1\\1\\-1} & >\vec u_{3} = \mat{1\\-i\\-1\\ i} >\end{matrix} $ ### Proof of Orthogonality $\huge \begin{align} \omega &= \frac{2\pi}{N}\\ \left< \vec u_{k}, \vec u_{m} \right> &= \sum_{n=0}^{N-1} e^{i\omega n k} e^{-i\omega n m} \\ &= \sum_{n=0}^{N-1} e^{i\omega nk - i\omega nm} \\ &= \sum_{n=0}^{N-1} e^{i\omega n (k-m) } \\ \let \zeta &= e^{i\omega (k-m)}\\ &= \sum_{n=0}^{N-1} \zeta^{n} \\ &= \\ &= \frac{ 1 - \zeta^{N}} {1- \zeta} \\ &=\frac{1 - 1}{1-\zeta} \\ &= 0 \end{align} $ Note that any matrix $\mathcal{F}$ consisting of Fourier basis vectors is not [[Orthonormal]], which can be verified by looking at $\vec u_{0}$ which is a vector consisting of a list of $1$-s. $\huge \begin{align} |\vec u_{k} | &= \sum_{n=0}^{N-1} e^{\frac{2\pi i}{N} kn}\cdot \overline{e^{\frac{2\pi i}{N}kn}} \\ &= \sum_{n=0}^{N-1} e^{\frac{2\pi i}{N} kn}{e^{-\frac{2\pi i}{N}kn}} \\ &= \sum_{n=0}^{N-1} e^{0} \\ &= \sum_{n=0}^{N-1} 1 \\ &= N \end{align} $ $\huge \begin{align} \frac{1}{N} \mathcal{F} &= \mat{ \hat u_{0} & \hat{u}_{1} & \cdots & \hat{u}_{N-1}} \\ \det\left( \frac{1}{N} \mathcal{F} \right) &= \det \left( \mat{ \cdots} \right) \\ \left(\frac{1}{N}\right)^{N} \det \mathcal{F} &= \sqrt{ 1 } \\ \det \mathcal{F} &= \sqrt{ 1 } \frac{1}{N}^{-N} \\ \\ \det \mathcal{F} &= \pm N^{N} \end{align} $ ### Spanning Property For any [[Vector]] $\vec v\in \C^{N}$ can written as a [[Linear Combination]] of our fourier basis. $\huge \vec v =\sum^{N-1}_{k=0} \alpha_{k}\vec u_{k} $ We can solve for this by rewriting this as a [[System of Linear Equations]]. Where $\mathcal F$ is the [[Set]] $U=\set{\vec u_{0}, \vec u_{1}, \dots, \vec u_{N-1}}$ $\huge \begin{align} \vec v &= \mathcal{F} \vec \alpha \\ \mathcal{F}^{-1}\vec v &= \vec \alpha \end{align} $ Because $\mathcal{F}$ is a [[Orthonormal Basis]], its [[Inverse Matrices|Matrix Inverse]] is the [[Transpose Conjugate|Conjugate Transpose]] of $\mathcal{F}$. $\huge \vec \alpha = \mathcal{F}^{*}\vec v $