I think that considering the DFT from a linear algebraic point of view has some value, so I will attempt to introduce the foundations.
We will assume that our signal is a vector of $N$ complex entries.
$\mathbb{C}^N$ is the vector space of vectors with $N$ complex entries. Let $\mathbf{u}_0,\mathbf{u}_1,\ldots,\mathbf{u}_{N-1}$ be vectors in $\mathbb{C}^{N}$ defined by
\begin{equation}
\begin{split}
\mathbf{u}_k
&=~
\frac{1}{\sqrt{N}}\left(\begin{array}{c}
\exp(2\pi \mathsf{j}\times 0\times(k/N))\\
\exp(2\pi \mathsf{j}\times 1\times(k/N))\\
\exp(2\pi \mathsf{j}\times 2\times(k/N))\\
\exp(2\pi \mathsf{j}\times 3\times(k/N))\\
\vdots\\
\exp(2\pi \mathsf{j}\times (N-1)\times(k/N))
\end{array}\right)\\
&=~
\frac{1}{\sqrt{N}}\left(\begin{array}{c}
1\\
e^{2\pi\mathsf{j}k/N}\\
(e^{2\pi\mathsf{j}k/N})^2\\
\vdots\\
(e^{2\pi\mathsf{j}k/N})^{N-1}
\end{array}\right),
\end{split}
\end{equation}
for $k = 0,1,2,\ldots,N-1$, where $\mathsf{j} = \sqrt{-1}$.
- Every entry of $\mathbf{u}_0$ is $1/\sqrt{N}$, so $\mathbf{u}_0$ might be considered as a sampled DC signal.
- The entries of $\mathbf{u}_1$ are samples of a complex exponential with fequency $\frac{1}{N}$,
- The entries of $\mathbf{u}_2$ are samples of a complex exponential with fequency $\frac{2}{N}$,
- and so on, up through frequency $\frac{N-1}{N}$.
$\mathbf{u}_0,\mathbf{u}_1,\ldots,\mathbf{u}_{N-1}$ form an
orthonormal basis for
$\mathbb{C}^{N}$, which means that each
$\mathbf{u}_k$ has
norm 1, they are all
orthogonal to one another, and each vector in
$\mathbb{C}^{N}$ can be represented unambiguously as a linear combination of them. An important result of this is that, if
$\mathbf{x}\in\mathbb{C}^{N}$, then there is exactly one list of complex numbers
$c_0,c_1,\ldots,c_N$ such that
\begin{equation}
\mathbb{x} = c_0\mathbf{u}_0 + c_1\mathbf{u}_1 + \cdots + c_{N-1}\mathbf{u}_{N-1}.
\end{equation}
The coefficients mentioned above are the entries of the DFT of $\mathbf{x}$:
\begin{equation}
\mathbf{x} = X[0]\mathbf{u}_0 + X[1]\mathbf{u}_1 + \cdots + X[N-1]\mathbf{u}_{N-1}.
\end{equation}
We might interpret $X[0]$ as the strength of the DC component of $\mathbf{x}$, $X[1]$ as the strength of the component of $\mathbf{x}$ with frequency $\frac{1}{N}$, and so on. Since $\mathbf{X} = \mathsf{DFT}\mathbf{x}$ has complex entries, there is some phase information attached to each "strength".
So far, we have considered only components of non-negative frequencies. What if we would rather view
$\mathbf{x}$ as a combination of negative and positive frequency components? Consider a component of frequency
$-\frac{k}{N}$ for
$0< k \leq \frac{N}{2}$:
\begin{equation}
\mathbf{u}_{-k}
~=~
\frac{1}{\sqrt{N}}\left(\begin{array}{c}
\exp(2\pi \mathsf{j}\times 0\times(-k/N))\\
\exp(2\pi \mathsf{j}\times 1\times(-k/N))\\
\exp(2\pi \mathsf{j}\times 2\times(-k/N))\\
\exp(2\pi \mathsf{j}\times 3\times(-k/N))\\
\vdots\\
\exp(2\pi \mathsf{j}\times (N-1)\times(-k/N))
\end{array}\right).
\end{equation}
The
$\ell^{\textrm{th}}$ entry of this vector is
\begin{equation}
\begin{split}
u_{-k}[\ell] &=~ \frac{1}{\sqrt{N}}\exp\left(2\pi\mathsf{j}\times\ell\times\frac{-k}{N}\right)\\
&=~ \frac{1}{\sqrt{N}}\exp\left(2\pi\mathsf{j}\times\ell\times\frac{-k}{N}\right)\times\underbrace{\exp\left(2\pi\mathsf{j}\times\ell\times\frac{N}{N}\right)}_{1}\\
&=~ \frac{1}{\sqrt{N}}\exp\left(2\pi\mathsf{j}\times\ell\times\frac{N-k}{N}\right)\\
&=~ u_{N-k}[\ell].
\end{split}
\end{equation}
In other words,
the negative-frequency component $\mathbf{u}_{-k}$ is exactly the same as the positive-frequency component $\mathbf{u}_{N-k}$.
Suppose that
$N = 2M$ for some positive integer
$M$. Then
\begin{equation}
\begin{split}
\mathbf{x} &=~ X[0]\mathbf{u}_0 + \cdots + X[N/2-1]\mathbf{u}_{N/2-1} + X[N/2]\mathbf{u}_{N/2} + \cdots + X[N-1]\mathbf{u}_{N-1}\\
&=~ X[0]\mathbf{u}_0 + \cdots + X[M-1]\mathbf{u}_{M-1} + X[M]\mathbf{u}_{M} + \cdots + X[N-1]\mathbf{u}_{N-1}\\
&=~ \underbrace{X[0]\mathbf{u}_0 + \cdots + X[M-1]\mathbf{u}_{M-1}}_{\textrm{non-negative-frequency components}}
+ \underbrace{X[M]\mathbf{u}_{N-M} + \cdots + X[N-1]\mathbf{u}_{N-1}}_{\textrm{negative-frequency components}}
\end{split}
\end{equation}
For a full decomposition, one can choose the frequency-sets
\begin{equation}
-\frac{N/2}{N},-\frac{N/2-1}{N},\ldots,-\frac{1}{N},0,\frac{1}{N},\ldots,\frac{N/2-1}{N}
\end{equation}
or
\begin{equation}
0,\frac{1}{N},\ldots,\frac{N-1}{N},
\end{equation}
each of which consists of
$N$ distinct frequencies. In truth, one can choose other frequency-sets of
$N$ frequencies, too, but these are the ones to which we have attached some intuition over the decades.
MATLAB's
fft gives the DFT with all non-negative frequencies. To convert the output of
fft to the vector of coefficients for negative, zero, and positive frequencies, one applies the
fftshift function.
All of this and much more is explained from a linear algebraic point of view in
Linear Algebra, Signal Processing, and Wavelets - A Unified Approach (PDF) by
Øyvind Ryan of the
University of Oslo.
