7
$\begingroup$

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

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

2 Answers 2

10
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Nice! What about a symmetric matrix, though? Does it change things if you stipulate symmetry? $\endgroup$ Apr 30, 2013 at 8:31
  • $\begingroup$ I think the question only has a shot at an affirmative answer if $2^n$ is large compared to $p$. $\endgroup$ Apr 30, 2013 at 12:09
  • $\begingroup$ 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$. $\endgroup$
    – Rob Myers
    Apr 30, 2013 at 12:13
  • $\begingroup$ @Gerry Myerson: Would you mind elaborating? I believe the same, but I am having trouble proving it. $\endgroup$
    – Rob Myers
    Apr 30, 2013 at 12:16
  • $\begingroup$ 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). $\endgroup$
    – Rob Myers
    Apr 30, 2013 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.