For the purposes of DFT, is "the" primitive root of unity $w_n = e^{ 2\pi i / n }$ or $w_n = e^{-2\pi i / n }$?

Question

I'm working on the section of Strang's Linear Algebra and Its Applications 4e that discusses discrete Fourier transforms. To make the exercises easier, I wrote myself a Python script that generates the $n$th Fourier matrix as described here:

I've run into trouble regarding the definition of $w$. While any integer value of $k$ in $e^{ 2\pi k i / n }$ will get us a complex root of unity, to fill in the matrix, we need the primitive complex root of unity.

Strang defines $w_n$ as $e^{ 2\pi i / n }$:

But when I coded $w_n$ as such in my DFT matrix function, it kept giving me the complex conjugate of what I wanted, and someone on Stack Overflow pointed out that I need to use $w_n = e^{-2\pi i / n }$ instead.

This is consistent with the definition given on Wikipedia:

But here's what throws me off. Looking at the unit circle, it seems like the primitive root of unity should be the one corresponding to a $2\pi / n$ rotation in the counterclockwise direction. That's what Strang does in this example diagram for $w_8$:

(The omission of $i$ is just a typo, right?)

If we replace that circled bit with $e^{-2\pi i / 8 }$, we get $\bar{w}$, an angle in the fourth quadrant, and taking increasing powers of it will move us around the unit circle in a clockwise direction. If that's correct,

• Why does the Fourier matrix reverse the usual convention of counterclockwise rotation?
• Why does my textbook seem to state one definition and use another?
• In general, when should I use $w_n = e^{ 2\pi i / n }$, and when should I use $w_n = e^{ -2\pi i / n }$?

As always, thank you.

---

Thank you all for your detailed explanations. Indeed, Strang's convention is to work with the inverse of what's described elsewhere, hence the change in sign.

However, this introduces a new issue in one of the assignment problems. Question 3.5.3 asks,

If you form a 3 by 3 submatrix of the 6 by 6 matrix $F_6$, keeping only the entries in its first, third, and fifth rows and columns, what is that submatrix?

The answer text reads simply,

The submatrix is $F_3$.

But using my Python function with $w_n = e^{2\pi i / n }$, I get the following inconsistent result:

F6 matrix:
[[ 1. +0.j     1. +0.j     1. +0.j     1. +0.j     1. +0.j     1. +0.j   ]
 [ 1. +0.j     0.5+0.866j -0.5+0.866j -1. +0.j    -0.5-0.866j  0.5-0.866j]
 [ 1. +0.j    -0.5+0.866j -0.5-0.866j  1. -0.j    -0.5+0.866j -0.5-0.866j]
 [ 1. +0.j    -1. +0.j     1. -0.j    -1. +0.j     1. -0.j    -1. +0.j   ]
 [ 1. +0.j    -0.5-0.866j -0.5+0.866j  1. -0.j    -0.5-0.866j -0.5+0.866j]
 [ 1. +0.j     0.5-0.866j -0.5-0.866j -1. +0.j    -0.5+0.866j  0.5+0.866j]]

F6 submatrix:
[[ 1. +0.j     1. +0.j     1. +0.j   ]
 [ 1. +0.j    -0.5-0.866j -0.5+0.866j]
 [ 1. +0.j    -0.5+0.866j -0.5-0.866j]]

F3 matrix (should match the above)
[[ 1. +0.j     1. +0.j     1. +0.j   ]
 [ 1. +0.j    -0.5+0.866j -0.5-0.866j]
 [ 1. +0.j    -0.5-0.866j -0.5+0.866j]]

You can see the code here.

Answer 1

The 5th edition of Strang's Introduction to Linear Algebra contains the following note (section 9.3, p. 447):

Important note. Many authors prefer to work with $\omega = e^{-2\pi i /N}$, which is the complex conjugate of our $w$. (They often use the Greek omega, and I will do that to keep the two options separate.) With this choice, their DFT matrix contains powers of $\omega$ not $w$. It is $\bar F$, the conjugate of our $F$. $\bar F$ goes from physical space to frequency space.

$\bar F$ is a completely reasonable choice! MATLAB uses $\omega = e^{-2\pi i/N}$. The DFT matrix fft(eye(N)) contains powers of this number $\omega = \bar w$. The Fourier matrix $F$ with $w$'s reconstructs $y$ from $c$. The matrix $\bar F$ with $\omega$'s computes Fourier coefficients as fft(y).

It would be a mistake to assume that, in Strang's notation, the discrete Fourier transform of $x$ is $Fx$. Strang does not make this claim. If we define $F$ as Strang does, using $w = e^{2\pi i/N}$, then the change of basis matrix from the standard basis to the discrete Fourier basis is $F^{-1} = (1/N)F^*$. So $$ \text{DFT}(x) = F^{-1} x = (1/N) F^* x. $$ (If we normalize the discrete Fourier basis, then we don't need the factor of $1/N$.)

Answer 2

There is one linguistic problem. It seems you are asking about "the" primitive root of unity. However, a primitive $n$th root of unity is just a complex number with $z^n = 1$ and $z^m \neq 1$ for $1 \leq m \leq n-1.$ In particular, there are Euler phi $\phi(n)$ such primitive roots.

Answer 3

Note that what Strang computes the matrix $F$ for is what is usually considered the inverse DFT, the reconstruction of the values from the Fourier coefficients, $$ y_k=\sum_{m=0}^{n-1}c_m(z_k)^m=\sum_{m=0}^{n-1}c_me^{i2\pi\frac{mk}n} $$ where the Fourier coefficients occur as polynomial coefficients.

The usually-considered-as-forwards DFT computes the coefficients from the values, $$ \hat y_m=\sum_{k=0}^{n-1}y_ke^{-i2\pi\frac{mk}n}. $$ One easily finds $\hat y_m=nc_m$. This is what other sources present as the primary transform, so that mistaken associations may occur.