Hi,


Suppose one has an incompletely specified $2^n \times 2^n$ matrix over some fixed finite field $\mathbb{F}\_{p^k}$. In fact, one knows that the diagonal entries are zero and all other entries are non-zero. Graphically:


$$\left( \begin{array}{ccccc} 0 & ? & \cdots & ? & ? \\\ ? & 0 & \cdots & ? & ? \\\ ? & ? & \ddots & ? & ? \\\ ? & ? & \cdots & 0 & ? \\\ ?&?&\cdots&?&0 \end{array} \right)$$


where distinct $?$'s needn't be equal, but they must both be non-zero.



> 
> Is it true that, for every possible choice of non-zero entries in $\mathbb{F}\_{p^k}$, the space spanned by the columns has dimension super-polynomial in $n$?
> 
> 
> 


This holds over $\mathbb{F}\_2$ where necessarily every $? =1$, the dimension being at least $2^n - 1$. I would also be very interested in any known methods for dealing with this type of problem.


Any help much appreciated.




---


*Clarification*: The finite field used should be **fixed**. So to answer the question negatively it suffices to find a sequence of filled-in $2^n \times 2^n$ matrices $(M\_n)\_{n \in \mathbb{N}}$ over some fixed finite field, whose ranks $rk(M\_n)$ are bounded polynomially in $n$.



Dimension of incomplete matrix over finite fields.
It is true. Let $N=2^n$ be the dimension, and $q=p^k$ be the size of the field. Let $v\_i$ be the $i$'th column vector. Define multiplication of vectors coordinate-wise, i.e., $uu'$ is vector whose $i$'th coordinate is $u\_i u'\_i$. Similarly, for a vector $u$ define $u^r$ be the result of raising all the elements of $u$ to $r$'th power. Note that the vectors $v\_1^{q-1},\dotsc,v\_N^{q-1}$ are linearly independent.


Suppose, now that the rank of the matrix is $r$, i.e, some $r$ column vectors span the column space. Without loss, every $v\_i$ is a linear combination of $v\_1,\dotsc,v\_r$. Let $S$ be the set of all the products of $q-1$ vectors from $\{v\_1,\dotsc,v\_r\}$ (repetition are allowed). If $$v\_i=\sum\_{j=1}^r \alpha\_j v\_j,$$ then $$v\_i^{q-1}=\left(\sum\_{j=1}^r \alpha\_j v\_j\right)^{q-1}=\sum\_{j\_1,\dotsc,j\_{q-1}=1}^r (\alpha\_{j\_1}\dotsb\alpha\_{j\_{q-1}}) v\_{j\_1}\dotsb v\_{j\_{q-1}}$$ is a linear combination of vectors from $S$. Since $v\_i^{q-1}$'s are linearly independent, we conclude that $|S|\geq N$. Since $|S|\leq r^{q-1}$, it follows that the rank is
$$r\geq N^{1/(q-1)}.$$


This argument is a variation on the proofs of Frankl–Wilson theorem, and of Ray-Chaudhuri–Wilson theorem.


**Added on 25 Jan 2014:** I just discovered that the same proof appeared as Theorem 4 in paper ["Low rank co-diagonal matrices and Ramsey graphs"](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v7i1r15) by Vince Grolmusz.


