18
$\begingroup$

Let $A$ be a symmetric square matrix with entries in $\mathbb{Z}/p\mathbb{Z}$ for a prime $p$ such that all of its diagonal entries are nonzero. Does there exists always a vector $x$ with all coordinates nonzero in the image of $A$? (this is true for $p=2$, but I don't know the answer for other values of $p$)

$\endgroup$
2
  • 7
    $\begingroup$ I suppose you mean "with all coordinates non-zero"? $\endgroup$ Aug 7 '18 at 16:13
  • $\begingroup$ @GeoffRobinson Yes, I edited the question. $\endgroup$
    – Mostafa
    Aug 7 '18 at 19:34
29
$\begingroup$

This is false. Let $c$ be a quadratic nonresidue modulo $p$. Our matrix will be $(p^2-1) \times (p^2-1)$, with rows and colums indexed by pairs $(x,y) \in \mathbb{F}_p^2 \setminus \{ (0,0) \}$.

Our matrix is defined by $$A_{(x_1,y_1) \ (x_2, y_2)} = x_1 x_2 - c y_1 y_2.$$ This is obviously symmetric. Since $c$ is a nonresidue, we have $x^2-cy^2 \neq 0$ for $(x,y) \in \mathbb{F}_p^2 \setminus \{ (0,0) \}$, so the diagonal entries are nonzero.

Each column of this matrix is a linear function of $(x,y)$. So every vector in the image of this matrix is a linear function $\mathbb{F}_p^2 \setminus \{ (0,0) \} \longrightarrow \mathbb{F}_p$ and, hence, takes the value $0$ somewhere.

We could make a smaller $(p+1) \times (p+1)$ example by just taking one point $(x,y)$ on each line through $0$ in $\mathbb{F}_p^2$.


Moreover, I claim that $(p+1) \times (p+1)$ is optimal. In other words, if $A$ is an $n \times n$ matrix with $n \leq p$ and nonzero entries on the diagonal, then some vector in the image of $A$ has all coordinates nonzero. Interestingly, I don't need the symmetry hypothesis.

Let $W$ be the image of $A$. Note that $W$ is not contained in any of the coordinate hyperplanes.

Let $\vec{u}= (u_1,\ u_2, \ \ldots,\ u_n)$, among all elements of $W$, have the fewest $0$ entries. Suppose for the sake of contradiction that some $u_i$ is $0$. Then there is some other $\vec{v}$ in $W$ with $v_i \neq 0$. Consider the points $(u_j : v_j)$ in $\mathbb{P}^1(\mathbb{F}_p)$ as $j$ ranges over all indices where $(u_j, v_j) \neq (0,0)$. There are fewer then $p+1$ such $j$, so some point of $\mathbb{P}^1(\mathbb{F}_p)$ is not hit, call it $(a:b)$. Then $-b \vec{u} + a \vec{v}$ is in $W$ and has fewer nonzero entries than $\vec{u}$, a contradiction.

$\endgroup$
16
  • $\begingroup$ This is a beautiful answer, and especially great because it works for any $p > 2$. $\endgroup$ Aug 7 '18 at 17:22
  • $\begingroup$ It makes me curious whether there are counterexample matrices of size $\leq p$, though. $\endgroup$ Aug 7 '18 at 18:25
  • 1
    $\begingroup$ I am getting the impression that a Combinatorial Nullstellensatz / Chevalley-Warning argument could work here; any ideas? $\endgroup$ Aug 7 '18 at 19:11
  • 1
    $\begingroup$ Ah, it's easier than that. Assume that no row of $A$ is $0$. (This is weaker than assuming that no diagonal entry of $A$ is $0$.) Consider the homogeneous polynomial $P = \prod\limits_{i=1}^n \left(\sum\limits_{j=1}^n a_{i,j} X_j\right) \in \mathbb{F}_p\left[X_1, X_2, \ldots, X_n\right]$. Then, $P \neq 0$. But the degree $\deg P = n \leq p$ of $P$ is small enough that homogeneous polynomials still behave like polynomial functions in this degree (indeed, they do it all the way until degree $p+1$); thus, $P \neq 0$ as a polynomial function too. In other words, there exists ... $\endgroup$ Aug 7 '18 at 19:21
  • 2
    $\begingroup$ The second part also follows by simply counting: the condition that $(Ax)_j\not= 0$ rules out $p^{n-1}$ vectors, so after considering all conditions, we have at least $p^n-np^{n-1}$ vectors left, which is $\ge 0$ if $n\le p$ (and of course there's overlap, so $n=p$ is fine too). $\endgroup$ Aug 9 '18 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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