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$.