0

I've been trying to learn the Discrete Fourier Transformation (DFT) and the Inverse DFT (IDFT).

From Wikipedia, I gather we can define the matrix transformations for the DFT as follows. Let $\omega= e^{-2\pi i/N}$ and let $$\mathbf{W}= \left[\frac{\omega^{jk}}{\sqrt{N}}\right]_{j,k=0,\cdots,N-1}$$

Then we can take a vector $\mathbf{x}$ and transform it via

$$\mathbf{X} = \mathbf{W}\mathbf{x}$$

Source: https://en.wikipedia.org/wiki/DFT_matrix

Question 1: Does the DFT always involve a $\frac{1}{\sqrt{N}}$ term? I noticed that in many cases it seems defined without that, e.g.

enter image description here

Source: https://en.wikipedia.org/wiki/Discrete_Fourier_transform

Now, $\mathbf{W}$ is a unitary matrix and therefore $\mathbf{W}^{*}\mathbf{W}=\mathbf{I}_{N}$. I have read that the IDFT is then defined as

$$\mathbf{x} = \frac{1}{N}\mathbf{W}^{*}\mathbf{X}$$

Source: https://www.kth.se/social/upload/50919490f2765474b1890dde/lec2.pdf

Ok, so if we put these together

$$\mathbf{x} = \frac{1}{N}\mathbf{W}^{*}\mathbf{X} = \frac{1}{N}\mathbf{W}^{*}\left(\mathbf{W}\mathbf{x}\right)=\frac{1}{N}\mathbf{I}_{N}\mathbf{x}=\frac{1}{N}\mathbf{x}$$

which obviously doesn't make any sense.

Question 2: What is wrong with my definitions of the DFT and IDFT such that it isn't inverting properly?

Stan Shunpike
  • 4,921
  • 2
    Did you read the entire wiki entry? As with the continuous FT, there are different conventions for normalizing. If you make $\mathbf W$ unitary, there is no $1/N$. If there’s no $\sqrt N$ in the original, then you use the $1/N$. – Ted Shifrin Apr 18 '22 at 18:31
  • @TedShifrin ok, that's helpful. Thanks Ted! – Stan Shunpike Apr 18 '22 at 18:35

1 Answers1

2

Since $$ \left[\omega^{jk}\right]\left[\omega^{jk}\right]^\dagger = NI_N $$ your forward and inverse matrices need to be multiplied by a net factor of $1/N$ for normalization. This can be accomplished by giving each a $1/\sqrt{N}$ factor, as in your first link, or by putting the full $1/N$ on the inverse matrix, as in your second two links. The matrix will only be unitary using the first convention.

You could also, hypothetically, split it up in other ways as long as the product is $1/N$, but the above two are most common.

Different normalization conventions are used by different sources, so always check which one they're using.

eyeballfrog
  • 22,485