Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
${\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

2 Answers 2

up vote 8 down vote accepted

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 "A note on explicit Ramsey graphs and modular sieve" by Vince Grolmusz.

share|improve this answer
    
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} $$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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