A system of linear equations related to the geometry of a finite plane

Question

Let $\mathcal L$ denote the set of all lines in $\mathbb F_p^2$ parallel to one of the lines $$ X:=\{(x,0)\colon x\in\mathbb F_p \}, \ Y:=\{(0,y)\colon y\in\mathbb F_p \}, \ Z:=\{(z,z)\colon z\in\mathbb F_p \}. $$ Given a set $S\subseteq\mathbb F_p^2$, with every element $s\in S$ associate a formal variable $x_s$, and consider the system of homogeneous linear equations $$ \sum_{s\in S\cap\ell} x_s = 0,\quad \ell\in\mathcal L; $$ thus, there are $|\mathcal L|=3p$ equations and $|S|$ variables. What is the smallest possible size of the set $S$ for which this system has a solution with all variables $x_s$ distinct from $0$, given that $S$ meets every line in $\mathbb F_p^2$? Are there any sets of size $|S|<3p$, meeting every line, for which there are such "nowhere-zero solutions"? If so, can these sets be characterized in a comprehensible way?

Answer 1

What you want is not possible for $p=3$ but I have an example for $p=5.$ It satisfies a stronger condition given at the end which makes sense for any $n \times n$ matrix.

$$\left[ \begin {array}{ccccc} 3&1&-1&-1&-2\\ 0&-3&0& 1&2\\ -1&1&0&0&0\\ -1&0&1&0&0 \\ -1&1&0&0&0\end {array} \right] $$

Here the origin is at the top left so the lines parallel to $y=x$ are labelled

$$ [3, -3, 0, 0, 0],[1, 0, 0, 0, -1], [-1, 1, 0, -1, 1], [-1, 2, -1, 0, 0], [-2, 0, 1, 1, 0]$$

This was somewhat ad hoc. I'll make a few not especially deep comments and then explain how I got it.

You have a system of $3p$ simultaneous equations in $p^2$ variables. However two are redundant. This means some $p^2-3p+2$ variables can be freely chosen and these uniquely determine the other $3p-2.$ Given such a set of $p^2-3p+2$ free variables (of course there are many) we know that not all of them can be set to $0$ since that will force the all $0$ solution. Setting one of the free variables to $1$ and the rest to $0$ will yield at most $3p-1$ non-zero variables, perhaps less. However the condition that no affine line be bad in that it is labelled with all zeros may fail. If so, then setting one or more free variables to non-zero values may decrease the number of bad lines and perhaps still keep the number of non-zero variables under $3p.$

I tried this with $p=5.$ The $25$ points are as follows (so the point $(i,j)$ is $a_{5i+j+1}$

$$\left[ \begin {array}{ccccc} a_{{1}}&a_{{2}}&a_{{3}}&a_{{4}}&a_{{5}} \\ a_{{6}}&a_{{7}}&a_{{8}}&a_{{9}}&a_{{10}} \\ a_{{11}}&a_{{12}}&a_{{13}}&a_{{14}}&a_{{15}} \\ a_{{16}}&a_{{17}}&a_{{18}}&a_{{19}}&a_{{20}} \\ a_{{21}}&a_{{22}}&a_{{23}}&a_{{24}}&a_{{25}} \end {array} \right]$$

One set of free variables with a candidate assignment is

$a_{{12}}=1,a_{{13}}=a_{{14}}=a_{{15}}=a_{{17}}=a_{{18}}=a_{ {19}}=a_{{20}}=a_{{22}}=a_{{23}}=a_{{24}}=a_{{25}}=0. $

However that leads to $$ \left[ \begin {array}{ccccc} 1&0&0&0&-1\\ 0&-1&0&0& 1\\ -1&1&0&0&0\\ 0&0&0&0&0 \\ 0&0&0&0&0\end {array} \right] .$$

To fix the bottom two horizontal lines I also made $a_{18}=a_{22}=1.$ (Why those? Just a choice of one from each.) That gave the pattern at the top:

$$\left[ \begin {array}{ccccc} 3&1&-1&-1&-2\\ 0&-3&0& 1&2\\ -1&1&0&0&0\\ -1&0&1&0&0 \\ -1&1&0&0&0\end {array} \right] $$

---

As nicely noted by @user44191, the fact that the first row has no zero entries means that every non-horizontal line has a non-zero entry. In fact it shows that a seemingly stronger condition is satisfied. I mention it because the fact that $p$ is prime is not essential to the problem. The condition is:

In an $n \times n$ matrix $M$ define a line to be any of these $2n+n!$ sets of $n$ entries: a row, a column or $m_{1,\sigma(1)},m_{2,\sigma(2)},\cdots , m_{n,\sigma(n)}$ where $\sigma$ is a permutation.

The goal is to find an $n \times n$ matrix with $3n-1$ or fewer non-zero entries such that

• The sums along each row and column are $0.$
• The sums along the main diagonal and the diagonals "parallel" to it are $0.$
• every line has a non-zero entry.

---

I suspect that a symmetric example is possible for any not too small $n.$