Can someone clearly explain the discrete Fourier transform (DFT)?

The Fourier transform is a change of basis ("coordinate system") for the vector space of integrable functions. Specifically, it is a pure rotation onto the basis of complex exponentials (sinusoids). This description is both intuitively geometric, and mathematically precise. Let me explain:

If you have studied linear algebra you have likely run into the concept of a change of basis. Imagine you have a vector on $\mathbb{R}^2$. You construct a basis $\{\hat{a}_x, \hat{a}_y\}$ to represent your vector $v$ as, $$ v = a_1\hat{a}_x+a_2\hat{a}_y $$

To express $v$ on an alternative basis, $\{\hat{b}_x, \hat{b}_y\}$, we make use of the inner product (or "dot" product) that geometrically does the job of computing projections. Basically, we are asking:

Given $\begin{bmatrix}a_1\\a_2\end{bmatrix}$, $\{\hat{a}_x, \hat{a}_y\}$, and $\{\hat{b}_x, \hat{b}_y\}$, compute $\begin{bmatrix}b_1\\b_2\end{bmatrix}$ so that, $$v = a_1\hat{a}_x+a_2\hat{a}_y = b_1\hat{b}_x+b_2\hat{b}_y$$

If we take the inner product of both sides of this equation with $\hat{b}_x$, we get, $$\hat{b}_x\cdot(a_1\hat{a}_x+a_2\hat{a}_y) = \hat{b}_x\cdot(b_1\hat{b}_x+b_2\hat{b}_y)$$ $$a_1(\hat{b}_x\cdot\hat{a}_x)+a_2(\hat{b}_x\cdot\hat{a}_y) = b_1$$

To make the right-hand-side simplification, I assumed that basis $\{\hat{b}_x, \hat{b}_y\}$ is mutually orthonormal, as is common: $$\hat{b}_x\cdot\hat{b}_x=1,\ \ \ \ \hat{b}_x\cdot\hat{b}_y=0$$

Now we have $b_1$ in terms of $a_1$ and $a_2$ with some weights $\hat{b}_x\cdot\hat{a}_x$ and $\hat{b}_x\cdot\hat{a}_y$ that are really equal to the cosines of the angles between these vectors, which we know since we were the ones who chose these coordinate systems. We do the same thing again but dotting with $\hat{b}_y$ to compute $b_2$.

We can construct a matrix representation of this process, $$R \begin{bmatrix} a_1 \\ a_2 \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \end{bmatrix}$$ where $R$ is an orthogonal matrix, $$R = \begin{bmatrix} \hat{b}_x\cdot\hat{a}_x & \hat{b}_x\cdot\hat{a}_y \\ \hat{b}_y\cdot\hat{a}_x & \hat{b}_y\cdot\hat{a}_y \end{bmatrix}$$

What does this have to do with the Fourier transform? We need to generalize our understanding of vectors now. 3Blue1Brown does a great job of explaining this. Put concisely: a function can be thought of as an infinite-dimensional vector. It has one element for every value it can take on, in an ordered array.

$$f(x) = \begin{bmatrix} \vdots \\ f(0.05) \\ f(0.051) \\ f(0.052) \\ \vdots \end{bmatrix}$$

where of course, it has elements for values in between 0.0500000... and 0.051, etc. The indexing is uncountable for continuous functions. For discrete domain functions, the indexing is countably infinite, $$f[n] = \begin{bmatrix} \vdots \\ f[-1] \\ f[0] \\ f[1] \\ f[2] \\ \vdots \end{bmatrix}$$

and for finite domain functions, they are literally just large but finite (ordinary) $N$-dimensional vectors, $$f[n] = \begin{bmatrix} f[0] \\ f[1] \\ \vdots \\ f[N-1]\end{bmatrix}$$

Regardless, they are vectors because they satisfy the properties of vectors. Just consider that everything we do with functions is identical to what we do with ordinary (finite-dimensional) vectors: when you add two functions you add them "element-wise", scalar multiplication does what it should, and furthermore, we even have an inner product! (So these functions are not just members of a vector space, but actually a Hilbert space).

$$f(x)\cdot g(x) = \int_{-\infty}^\infty f(x)g(x) \, dx$$

or on a discrete domain like, say, discrete time (starts at $n=0$),

$$f[n]\cdot g[n] = \sum_{n=0}^\infty f[n]g[n]$$

Read what that integral means: for each $x$ (index), multiply $f(x)$ and $g(x)$ and sum that result down all the $x$. Look familiar?

$$\begin{bmatrix} a_1 \\ a_2 \\ \vdots \end{bmatrix} \cdot \begin{bmatrix} b_1 \\ b_2 \\ \vdots\end{bmatrix} = a_1b_1 + a_2b_2 + \cdots$$

If functions are vectors, then don't they need to be expressed on bases of other functions? Yes. How many basis functions do you need to span an infinite dimensional space? Infinitely many. Is it hard to describe an infinite number of linearly independent functions? No. One example: $$g_1(x)= 1,\ \ g_2(x)=x,\ \ g_3(x)=x^2,\ \ \ldots,\ \ g_n(x)=x^n$$ Notice that we don't have both $x^n$ and $cx^n$, because they are linearly dependent; they span the same direction. We sometimes call linearly dependent functions "like-terms" in the sense that we can combine $x^n + cx^n = (1+c)x^n$ as opposed to linearly independent functions we cannot combine $x^n + x^{n+1}$.

If we took the inner product of one of these $g_i(x)$ with $g_j(x)$ we would certainly not get 0, so they don't have that nice orthogonal property where $\hat{b}_x\cdot\hat{b}_y=0$. The polynomials don't form an orthogonal basis. However, the complex exponentials do. There are plenty of other good demonstrations for many different function bases.

Now lets look at that mysterious Fourier transform (in finite discrete time, since that seems to be your interest). Let $c := 2\pi i / N$. $$\mathscr{F}(f[n]) = \sum_{n=0}^{N-1} e^{ckn}f[n]$$

Imagine all possible values of $e^{ckn}$ in a big (orthogonal) matrix, where each row corresponds to plugging in a specific $k$ and each column corresponds to plugging in a specific $n$. If you select some $k$, you are plucking out a specific value of the function that resulted from the multiplication of this matrix with the vector $f[n]$, a function we call $F[k]:=\mathscr{F}(f[n])$. Specifically, $$F[k=3] = f[n] \cdot e^{(c)(3)(n)}$$

(where that dot is an inner product, not ordinary multiplication). We say that $F[k]$ is just $f[n]$ expressed on a basis of exponential functions. Choosing a specific value of $k=k_1$ is picking out the value of $f[n]$ in the $e^{ck_1 n}$ direction. The entire $e^{ckn}$ can be viewed as the change of basis matrix.

Why would we be interested in something like this? Here are some practical reasons. I like to think about it like this: choice of basis (coordinates) is arbitrary, yes, but depending on the problem / application, a clever choice of basis makes all the difference in solving it. For example, exponentials are the eigenfunctions of the derivative operator, so switching to the basis of exponentials might help with solving differential equations, and it does!

A follow-up Q/A can be found here!