Vandermonde Submatrices and Arithmetic Progressions

[This post, which is based on an ongoing discussion with Alex Russell and Ravi Sundaram, contains some unpublished results.]

Currently, we are asking whether all submatrices of the order- $p$ Vandermonde matrix over a finite extension of $GF(2)$ are invertible where $p$ is prime. The answer is “no” in general: there are examples of fields where the Vandermonde matrix has a singular submatrix.

We can ask an easier(?) question, though. What happens if we randomly sample a set of columns and look into submatrices formed by a subset of the sampled columns. With a touch of beautiful insight, Professor Russell has connected Szemeredi’s theorem on arithmetic progressions with this question.

Let $AP_k$ denote an arithmetic progression of length $latek k$. Let $[N] := \{1, 2, \cdots, N\}$ for $N \in \mathbb{N}$ .

The Szemerédi theorem says, any “sufficiently dense” subset $S \subset [N]$ contains infinitely many $AP_k$ for all $k \in \mathbb{N}$ . A finitary version says: Fix your favourite $k \in \mathbb{N}, \delta \in [0, 1]$ . Then, there exists a natural $N := N_{k, \delta}$ such that if you look any subset $S \subset [N]$ of size at least $\delta N$ , you will find an $AP_k$ . Yet another version says:

Szemerédi’s Theorem. The size of the largest subset $S \subset [N]$ without an $AP_k$ cannot be too large; in particular, it is $o(N)$ .

Recall that a function $f(x)$ is $o(g)$ if it grows too slow compared to $g(x)$ , so that $\lim_{N\rightarrow \infty}{f(x)/g(x) = 0}$ .

Continue reading “Vandermonde Submatrices and Arithmetic Progressions” →

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 $p$ th 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?” →

Discrete Fourier Transform: the Intuition

Every time I think “Now I understand the Fourier Transform,” I am 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 $t$ th coordinate in the new basis will be given by inner product between $u$ and the $t$ th 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 “Discrete Fourier Transform: the Intuition” →