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 }$?

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 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.

• By the way, the typo $e^{2\pi/8}$ that you circled has been corrected in the 5th edition of Strang's Introduction to Linear Algebra. – littleO Aug 24 '19 at 19:47
• Strang has many linear algebra books, so it's probably best to use the full title. I think you're referring to Linear Algebra and its Applications. – littleO Aug 24 '19 at 19:48

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.

• This is exactly my question, hence the scare quotes. In order to create a DFT matrix, we need to choose a single value for $w$, but there are many available. – Max Aug 24 '19 at 1:04

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$$.)

• Does $F^*$ mean "the complex conjugate of $F$"? This is new notation to me. – Max Aug 24 '19 at 0:57
• So, which is "the nth Fourier matrix": $F$, or $F^*$? – Max Aug 24 '19 at 1:06
• @Max The only person I've heard use the term "Fourier matrix" is Strang, so I'd say that the $n$th "Fourier matrix" is what Strang calls $F$. (I think it's his term.) The different term "DFT matrix", I think, is supposed to satisfy $\text{DFT}(x) = (\text{DFT matrix})x$. So, the DFT matrix is $(1/N) F^*$. (If we normalize the discrete Fourier basis, we would not need the factor of $1/N$.) – littleO Aug 25 '19 at 10:36
• Even if the terminology is not completely standardized, the important thing to understand is that the columns of $F$ are the discrete Fourier basis vectors, and that $F^{-1}$ is the change of basis matrix from the standard basis to the discrete Fourier basis. And the DFT simply changes basis from the standard basis to the discrete Fourier basis. So $\text{DFT}(x) = F^{-1} x$. – littleO Aug 25 '19 at 10:37
• Thank you for clarifying these conventions quoting from Strang's book (I wish I could find a used 5e here in Korea...). After straightening this issue out, though, it still seems like $F$ is used inconsistently in the assignment problems. I've made an edit to my post; perhaps you could take a look if you get a chance. – Max Aug 26 '19 at 0:44

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.