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

-
${\bf Z}_{p^k}$ is not a field, unless $k=1$. –  Gerry Myerson Apr 30 '13 at 4:50
Right you are... I mixed up the notation, sorry about that. –  Rob Myers Apr 30 '13 at 11:51

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.

-
Thank you very much for this lovely proof! –  Rob Myers Apr 30 '13 at 16:52

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

-
Nice! What about a symmetric matrix, though? Does it change things if you stipulate symmetry? –  Felix Goldberg Apr 30 '13 at 8:31
I think the question only has a shot at an affirmative answer if $2^n$ is large compared to $p$. –  Gerry Myerson Apr 30 '13 at 12:09
Thanks for that nice example, but this is not what I wanted. This is my fault: I haven't been clear enough. The field should be fixed i.e. we only vary $n$. Let me put it another way. To answer my question negatively, one must find a sequence $(M_n)_{n \geq 0}$ of $2^n \times 2^n$ `filled-in' matrices over a fixed finite field, such that their rank $rk(M_n)$ is not polynomially bounded in $n$. –  Rob Myers Apr 30 '13 at 12:13
@Gerry Myerson: Would you mind elaborating? I believe the same, but I am having trouble proving it. –  Rob Myers Apr 30 '13 at 12:16
Yet another error: in my first comment above the last sentence should read "...such that that their rank $rk(M_n)$ is polynomially bounded in $n$." (delete the not). –  Rob Myers Apr 30 '13 at 12:27