Dimension of incomplete matrix over finite fields. 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$.
 A: I think, it is not true. Choose a prime $p$ with $p>2^n-2$ and consider the two column vectors
$e_1$ and $e_2$ with $2^n$ entries over the field $\mathbb{F}_p$,
$$
e_1=(0,1,1,...,1)^t, \quad e_2=(1,0,p-1,p-2,...,p-2^n+2)^t
$$
Now form the matrix $A$ consisiting of the column vectors
$$
A=(e_1,e_2,e_1+e_2,2e_1+e_2,3e_1+e_2,\ldots ,(2^n-2)e_1+e_2)
$$
Then $A$ has zero entries in the diagonal, and all off-diagonal elements are nonzero.
Nevertheless the rank is $2$, i.e., the space spanned by all column vectors is only $2$.
For example, with $n=3$ we obtain the following $8\times 8$-matrix:
$$
A=\begin{pmatrix}
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \cr
1 & 0 & 1 & 2& 3& 4 & 5 & 6 \cr
1 & p-1 & 0 & 1 & 2 & 3 & 4 & 5 \cr
1 & p-2 & p-1 & 0 & 1 & 2 & 3 & 4 \cr
1 & p-3 & p-2 & p-1 & 0 & 1 & 2 & 3 \cr
1 & p-4 & p-3 & p-2 & p-1 & 0 & 1 & 2 \cr
1 & p-5 & p-4 & p-3 & p-2 & p-1& 0 & 1\cr
1 & p-6 & p-5 & p-4 & p-3 & p-2 & p-1 & 0
\end{pmatrix}
$$
A: 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" by Vince Grolmusz.
