When does the Discrete Fourier Transform Matrix have Nonsingular Submatrices?

I am studying a coding theory problem. The question is this:

Open Question: Is there a prime p and a positive integer d such that all submatrices of the p\times p Discrete Fourier Transform matrix over the field GF(2^d) are nonsingular?

Currently, I have only counterexamples: Let d be theĀ degree of the smallest extension over GF(2) which contains a nontrivial pth root of unity. Then, I know a lot of primes p for which the matrix V has a singular submatrix.

In this post, I am going to show a failed attempt to answer this question using the results in this paper by Evra, Kowalski, and Lubotzky.

Continue reading “When does the Discrete Fourier Transform Matrix have Nonsingular Submatrices?”

Advertisements

An Intuitive Explanation of the Discrete Fourier Transform

Every time I thought “Now I understand Fourier Transform,” I was wrong.

fourier2
Jean-Baptiste Joseph Fourier, 1768 – 1830. (Image source: Wikipedia)

Doing the Fourier Transform of a function is just seeing it from “another” point of view. The “usual” view of a function is in the standard basis \{e_1, \cdots, e_n\}. For example, f can be seen as a vector (in the basis given by the elements in the domain) whose coordinates are the evaluations of f on theĀ elements in the domain. It can also be seen as a polynomial (in the monomial basis) whose coefficients are these evaluations. Let us call this vector u.

The same function can also be seen from the “Fourier basis”, which is just another orthogonal basis, formed by the basis vectors \{v_t\}, t. The tth coordinate in the new basis will be given by inner product between u and the tth basis vector v_t. We call these inner products the Fourier coefficients. The Discrete Fourier Transform matrix (the DFT matrix) “projects” a function from the standard basis to the Fourier basis in the usual sense of projection: taking the inner product along a given direction.

In this post, I am going to use elementary group theoretic notions, polynomials, matrices, and vectors. The ideas in this post will be similar to this Wikipedia article on Discrete Fourier Transform.

Continue reading “An Intuitive Explanation of the Discrete Fourier Transform”