Krzysztof Onak: updated header

2013-03-07T01:54:39Z

updated header

Krzysztof Onak: Created page with "{{Header |title=Rank Lower Bound |source=bertinoro11 |who=Madhu Sudan }} We want to prove that the following tall matrix has full column rank. The columns are indexed by $a_1,..."

2012-11-17T03:49:01Z

Created page with "{{Header |title=Rank Lower Bound |source=bertinoro11 |who=Madhu Sudan }} We want to prove that the following tall matrix has full column rank. The columns are indexed by $a_1,..."

New page

{{Header
|title=Rank Lower Bound
|source=bertinoro11
|who=Madhu Sudan
}}
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 {{cite|GrigorescuKS-08}}).
The general case, when $d_i$'s are arbitrary, and not successive
powers of two remains open (Conjecture 5.9 in {{cite|BenSassonGMSS-11}}).

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro11
 |who=Madhu Sudan

Open Problems:43 - Revision history

Krzysztof Onak: updated header

Krzysztof Onak: Created page with "{{Header |title=Rank Lower Bound |source=bertinoro11 |who=Madhu Sudan }} We want to prove that the following tall matrix has full column rank. The columns are indexed by $a_1,..."