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$)
$\begingroup$
$\endgroup$
2
-
7$\begingroup$ I suppose you mean "with all coordinates non-zero"? $\endgroup$– Geoff RobinsonAug 7, 2018 at 16:13
-
$\begingroup$ @GeoffRobinson Yes, I edited the question. $\endgroup$– MostafaAug 7, 2018 at 19:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
16
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.
answered Aug 7, 2018 at 16:17
-
$\begingroup$ This is a beautiful answer, and especially great because it works for any $p > 2$. $\endgroup$ Aug 7, 2018 at 17:22
-
$\begingroup$ It makes me curious whether there are counterexample matrices of size $\leq p$, though. $\endgroup$ Aug 7, 2018 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, 2018 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, 2018 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, 2018 at 15:09