3
$\begingroup$

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:

Strang's definition of the nth Fourier matrix

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

Strang's definition of w with positive exponent

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:

Definition with negative exponent from wiki DFT page

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$:

Strang's unit circle, positive exponent omitting i

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – littleO Aug 24 '19 at 19:47
  • $\begingroup$ 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. $\endgroup$ – littleO Aug 24 '19 at 19:48
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Max Aug 24 '19 at 1:04
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Does $F^*$ mean "the complex conjugate of $F$"? This is new notation to me. $\endgroup$ – Max Aug 24 '19 at 0:57
  • 2
    $\begingroup$ So, which is "the nth Fourier matrix": $F$, or $F^*$? $\endgroup$ – Max Aug 24 '19 at 1:06
  • 2
    $\begingroup$ @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$.) $\endgroup$ – littleO Aug 25 '19 at 10:36
  • 2
    $\begingroup$ 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$. $\endgroup$ – littleO Aug 25 '19 at 10:37
  • 1
    $\begingroup$ 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. $\endgroup$ – Max Aug 26 '19 at 0:44
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.