# Problem 43: Rank Lower Bound

Suggested by | Madhu Sudan |
---|---|

Source | Bertinoro 2011 |

Short link | 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]).