The FFT processing gain comes from the fact that the DFT (of which FFT is simply a fast implementation) is a non-normalized linear transformation. This is a mouthful, so let's look at what this means.

I'm going to assume that you know what a linear transformation is. Namely, given vectors $\mathbf{x}$ and $\mathbf{y}$ and a matrix $A$ we have

$$\mathbf{y} = A \mathbf{x}.$$

DFT is just such a transformation. In fact, you can use MATLAB dftmtx command to generate this matrix for you based on the length of vector $\mathbf{x}$. This this case,

$$\mathbf{y} = \text{DFT}(\mathbf{x}).$$

This matrix $A$ has some properties. First of all, it's a square matrix, which means that it's probably invertible (and indeed it is!). It also tells us that we're essentially taking components of x and performing a change of basis given by the columns of $A$ to get its DFT. So far so good.

Now, let's get to some more important properties. Matrix $A$ is orthogonal. This means that every column of $A$ is perpendicular to every other column, or more mathematically, $A^TA$ is a diagonal matrix (you may have to think a little about why this is true). This is a very nice property, since simply transposing the matrix gives us something very close to its inverse.

To make this Transpose $\leftrightarrow$ Inverse relationship strict, we want the matrix $A$ to also be normal. This is a matrix whose every column vector has length 1. In other words, if $a$ is a column of $A$, then $\sqrt{a^Ta} = 1.$ If a matrix is both orthogonal and normal, we call it orthonormal, and in this case $A^TA = I$, so $A^T$ is in fact the inverse of $A$. Neat!

The usual DFT matrix (or the usual DFT transform) is orthogonal, but not orthonormal. In fact, if $D$ is the DFT matrix, then $D^TD = N$ where $N$ is the number of columns (or rows, it's square!) in $D$. To make it orthonormal, we should use $\frac{D}{\sqrt{N}}$ instead. If you look at it long enough, you realize that is we scale both forward and inverse transforms by $\frac{1}{\sqrt{N}}$, we're doing extra work in performing the calculations, so we usually just scale by $\frac{1}{N}$ at the inverse.

There are better theoretical reasons for doing it on one side rather than of both. See my answer here for more information.

The FFT processing gain comes from the fact that the DFT (of which FFT is simply a fast implementation) is a non-normalized linear transformation. This is a mouthful, so let's look at what this means.

I'm going to assume that you know what a linear transformation is. Namely, given vectors $\mathbf{x}$ and $\mathbf{y}$ and a matrix $A$ we have

$$\mathbf{y} = A \mathbf{x}.$$

DFT is just such a transformation. In fact, you can use MATLAB dftmtx command to generate this matrix for you based on the length of vector $\mathbf{x}$. This this case,

$$\mathbf{y} = \text{DFT}(\mathbf{x}).$$

This matrix $A$ has some properties. First of all, it's a square matrix, which means that it's probably invertible (and indeed it is!). It also tells us that we're essentially taking components of x and performing a change of basis given by the columns of $A$ to get its DFT. So far so good.

Now, let's get to some more important properties. Matrix $A$ is orthogonal. This means that every column of $A$ is perpendicular to every other column, or more mathematically, $A^TA$ is a diagonal matrix (you may have to think a little about why this is true). This is a very nice property, since simply transposing the matrix gives us something very close to its inverse.

To make this Transpose $\leftrightarrow$ Inverse relationship strict, we want the matrix $A$ to also be normal. This is a matrix whose every column vector has length 1. In other words, if $a$ is a column of $A$, then $\sqrt{a^Ta} = 1.$ If a matrix is both orthogonal and normal, we call it orthonormal, and in this case $A^TA = I$, so $A^T$ is in fact the inverse of $A$. Neat!

The usual DFT matrix (or the usual DFT transform) is orthogonal, but not orthonormal. In fact, if $D$ is the DFT matrix, then $D^TD = N$ where $N$ is the number of columns (or rows, it's square!) in $D$. To make it orthonormal, we should use $\frac{D}{\sqrt{N}}$ instead. If you look at it long enough, you realize that is we scale both forward and inverse transforms by $\frac{1}{\sqrt{N}}$, we're doing extra work in performing the calculations, so we usually just scale by $\frac{1}{N}$ at the inverse.

There are better theoretical reasons for doing it on one side rather than of both. See my answer here for more information.

The FFT processing gain comes from the fact that the DFT (of which FFT is simply a fast implementation) is a non-unitary linear transformation. This is a mouthful, so let's look at what this means.

I'm going to assume that you know what a linear transformation is. Namely, given vectors $\mathbf{x}$ and $\mathbf{y}$ and a matrix $A$ we have

$$\mathbf{y} = A \mathbf{x}.$$

DFT is just such a transformation. In fact, you can use MATLAB dftmtx command to generate this matrix for you based on the length of vector $\mathbf{x}$. This this case,

$$\mathbf{y} = \text{DFT}(\mathbf{x}).$$

This matrix $A$ has some properties. First of all, it's a square matrix, which means that it's probably invertible (and indeed it is!). It also tells us that we're essentially taking components of x and performing a change of basis given by the columns of $A$ to get its DFT. So far so good.

Now, let's get to some more important properties. Matrix $A$ is orthogonal. This means that every column of $A$ is perpendicular to every other column, or more mathematically, $A^TA$ is a diagonal matrix (you may have to think a little about why this is true). This is a very nice property, since simply transposing the matrix gives us something very close to its inverse.

To make this Transpose $\leftrightarrow$ Inverse relationship strict, we want the matrix $A$ to also be normal. This is a matrix whose every column vector has length 1. In other words, if $a$ is a column of $A$, then $\sqrt{a^Ta} = 1.$ If a matrix is both orthogonal and normal, we call it orthonormal, and in this case $A^TA = I$, so $A^T$ is in fact the inverse of $A$. Neat!

The usual DFT matrix (or the usual DFT transform) is orthogonal, but not orthonormal. In fact, if $D$ is the DFT matrix, then $D^TD = N$ where $N$ is the number of columns (or rows, it's square!) in $D$. To make it orthonormal, we should use $\frac{D}{\sqrt{N}}$ instead. If you look at it long enough, you realize that is we scale both forward and inverse transforms by $\frac{1}{\sqrt{N}}$, we're doing extra work in performing the calculations, so we usually just scale by $\frac{1}{N}$ at the inverse.

There are better theoretical reasons for doing it on one side rather than of both. See my answer here for more information.

The FFT processing gain comes from the fact that the DFT (of which FFT is simply a fast implementation) is a non-normalized linear transformation. This is a mouthful, so let's look at what this means.

I'm going to assume that you know what a linear transformation is. Namely, given vectors $\mathbf{x}$ and $\mathbf{y}$ and a matrix $A$ we have

$$\mathbf{y} = A \mathbf{x}.$$

DFT is just such a transformation. In fact, you can use MATLAB dftmtx command to generate this matrix for you based on the length of vector $\mathbf{x}$. This this case,

$$\mathbf{y} = \text{DFT}(\mathbf{x}).$$

This matrix $A$ has some properties. First of all, it's a square matrix, which means that it's probably invertible (and indeed it is!). It also tells us that we're essentially taking components of x and performing a change of basis given by the columns of $A$ to get its DFT. So far so good.

Now, let's get to some more important properties. Matrix $A$ is orthogonal. This means that every column of $A$ is perpendicular to every other column, or more mathematically, $A^TA$ is a diagonal matrix (you may have to think a little about why this is true). This is a very nice property, since simply transposing the matrix gives us something very close to its inverse.

To make this Transpose $\leftrightarrow$ Inverse relationship strict, we want the matrix $A$ to also be normal. This is a matrix whose every column vector has length 1. In other words, if $a$ is a column of $A$, then $\sqrt{a^Ta} = 1.$ If a matrix is both orthogonal and normal, we call it orthonormal, and in this case $A^TA = I$, so $A^T$ is in fact the inverse of $A$. Neat!

The usual DFT matrix (or the usual DFT transform) is orthogonal, but not orthonormal. In fact, if $D$ is the DFT matrix, then $D^TD = N$ where $N$ is the number of columns (or rows, it's square!) in $D$. To make it orthonormal, we should use $\frac{D}{\sqrt{N}}$ instead. If you look at it long enough, you realize that is we scale both forward and inverse transforms by $\frac{1}{\sqrt{N}}$, we're doing extra work in performing the calculations, so we usually just scale by $\frac{1}{N}$ at the inverse.

There are better theoretical reasons for doing it on one side rather than of both. See my answer here for more information.