# Problem 43: Rank Lower Bound

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Suggested by Madhu Sudan Bertinoro 2011 https://sublinear.info/43

We want to prove that the following tall matrix has full column rank. The columns are indexed by \$a_1, \ldots ,a_k\$ from the field \$F_{2^n}\$ where \$n\$ is prime; the rows are indexed by degrees \$d_1 \ldots d_r\$. The entry in the \$i\$th column and \$j\$th row is equal to \$a_i^{d_j}\$.

Question: Is it true that for all \$k\$ there exists an \$r\$ such that for all \$d_1,...,d_r\$ that are powers of \$2\$ and for all \$a_1,...,a_k\$ that are linearly independent over \$F_2\$, the rank of the matrix is \$k\$?

Background: Note that if \$d_i = i\$ and \$r \geq k\$, then the matrix is Vandermonde and so has full rank. If \$d_i = 2^i\$, then also the matrix has full rank (Lemma 19 in [GrigorescuKS-08]). The general case, when \$d_i\$'s are arbitrary, and not successive powers of two remains open (Conjecture 5.9 in [BenSassonGMSS-11]).