Non-singular matrix with restricted entries

Question

Given a set $S$ of integers with $1 \not\in S$, let us consider the set $\mathcal{M}$ of all the symmetric matrices $M$, such that:

1. All the diagonal entries of $M$ are equal to $1$.

2. All the off-diagonal entries of $M$ are from $S$.

Obviously, if $S$ only consists of numbers divisible by a prime number $p$, then a $M \in \mathcal{M}$ is always non-singular. This can be seen by either analyzing its rank over $\mathbb{F}_p$, or just expanding its determinant.

Now, the question is, is it true that every $S$ such that all satisfiable $M$ are non-singular must be a subset of $\{\cdots, -2p, -p, 0, p, 2p, \cdots\}$ for some prime $p$?

I feel that this must have been studied in the literature but was not able to find it after extensive search. A natural thing to try first is $S=\{k, k+1\}$ for $k \ge 2$, one can actually construct the following singular $2k \times 2k$ (symmetric) matrix:

\begin{bmatrix} (k+1)J_k-kI_k & kJ_k\\ kJ_k & (k+1)J_k-kI_k\\ \end{bmatrix}

It is singular because the sum of the first $k$ rows is equal to the sum of the last $k$ rows.

Answer 1

This is perhaps a minor observation (Edit: thanks to Peter Taylor’s comment below).

If $S$ has every admissible symmetric matrix being non-singular, then $-1\notin S$.

This is due to the singular $2\times 2$ matrix $\begin{pmatrix} 1&-1\\-1& 1\end{pmatrix}$.

Added Later

Additionally,

If $S$ has every admissible symmetric matrix being non-singular, then $\{n,2n^2-1\}\not\subseteq S$ for any integer $n\ne\pm 1$.

Here the counterexample follows from the singular $3\times 3$ symmetric matrix $$\begin{pmatrix} 1&n&n\\n&1&2n^2-1\\n&2n^2-1&1\end{pmatrix}\,.$$

Answer 2

Disclaimer: this is only a partial answer.

If $S = \{x, y\}$ (considered as variables), the determinant must be a polynomial with integer coefficients and constant coefficient 1. Therefore by Gauss's lemma any factors have constant coefficient 1. The problem would be solved by an algorithm which takes coprime $u, v \in \mathbb{Z}$ and constructs an admissible matrix whose determinant has a factor $(ux + vy + 1)$. We could then use Bézout coefficients to show that we can't have two coprime elements in $S$.

This answer gives constructions for singular matrices with the following factors:

1. $((k-1)x - ky + 1)$, so that there is a singular matrix if $x = y = 1 \pmod {x - y}$.
2. $(ux + vy + 1)$ where $u, v$ are both positive and are of opposite parity. (The same construction works where they're both even, but we don't care about that case since then $x$ and $y$ can't both be integers). This covers all cases where $x, y$ are coprime and have opposite signs, as pointed out by Brendan McKay.

It also shows how to construct a singular matrix if $\{0, x, y\} \subseteq S$ where $x, y$ are coprime.

---

The example at the end of the question generalises to

$$M = \begin{bmatrix} xJ_k - (x-1)I_k & y J_k \\ y J_k & xJ_k - (x-1)I_k\end{bmatrix} \\ \det M = {((k-1)x - ky + 1)((k-1)x + ky + 1)(x - 1)^{2k-2}} $$

---

A similar idea allows us to construct an admissible symmetric matrix with elements in $\{1, x, y\}$ whose determinant has a factor $(ux + vy + 1)$ for $u, v > 0$ and not both odd. Clearly for our purposes we don't care about the case where both are even, so assume wlog that $u$ is odd and $v$ is even.

Let $n = 1 + u + v$. We construct a symmetric circulant $n \times n$ matrix: $$\begin{bmatrix} c_1 & c_2 & \cdots & c_{n/2} & c_{n/2+1} & c_{n/2} & \cdots & c_2 \\ c_2 & c_1 & \cdots & c_{n/2 - 1} & c_{n/2} & c_{n/2+1} & \cdots & c_3 \\ c_3 & c_2 & \cdots & c_{n/2 - 2} & c_{n/2-1} & c_{n/2} & \cdots & c_4 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\ c_2 & \cdots & c_{n/2} & c_{n/2+1} & c_{n/2} & \cdots & c_2 & c_1 \\ \end{bmatrix}$$ Each column sums to $c_1 + c_{n/2+1} + 2 \sum_{i=2}^{n/2} c_i$, so by setting $c_1 = 1$, $c_{n/2+1} = x$, and any suitably sized subsets of the remaining $c_i$ to $x$ respectively $y$ we get the desired factor.

---

An idea which seems to show some promise for extending the argument combines two of these ideas. Let $C_n$ denote the generic symmetric circulant $n \times n$ matrix with $\lceil \frac{n+1}2 \rceil$ variables. The Cayley table of the cyclic group of order $n$ (with rows and columns ordered canonically) is a symmetric Latin square and a Hankel matrix. If we map its elements to variables $h_i$ and call it $H_n$ then we can make a block construction $\begin{bmatrix}C_n & H_n \\ H_n & C_n\end{bmatrix}$.

• Case $n = 2k$: each column of $C_n$ sums to $c_1 + c_{k+1} + 2 \sum_{i=2}^k c_i$, so the determinant has factors $$\left(c_1 + c_{k+1} + 2 \sum_{i=2}^k c_i - \sum_{j=1}^n h_j\right)\left(c_1 + c_{k+1} + 2 \sum_{i=2}^k c_i + \sum_{j=1}^n h_j\right)$$
• Case $n = 2k+1$: each column of $C_n$ sums to $c_1 + 2 \sum_{i=2}^{k+1} c_i$, so the determinant has factors $$\left(c_1 + 2 \sum_{i=2}^{k+1} c_i - \sum_{j=1}^n h_j\right)\left(c_1 + 2 \sum_{i=2}^{k+1} c_i + \sum_{j=1}^n h_j\right)$$

In both cases, for the matrix to be admissible we require $c_1 = 1$.

If $0 \in S$ then we can choose a large enough $n$ and pad things with zeros so that we get $(ux + vy + 1)$ for any $u, v \in \mathbb{Z}$, so:

Theorem: if $\{0, x, y\} \subseteq S$ where $x, y$ are coprime then there is a singular matrix in $\mathcal{M}$.

If all of the $c_i$, $h_i$ other than $c_1$ are assigned to either $x$ or $y$ then we don't actually get anything new: in general, we can achieve $(ux - (1+u)y + 1)$.

The problem is that there aren't enough degrees of freedom, but I don't see a way to add more. Certainly larger symmetric circulant block matrices don't help. Maybe this idea can't be pushed any further (although the theorem is certainly not nothing).

Answer 3

[EXPANDED]

PART 1 (also done by Peter)

If $x,y$ are coprime and have opposite sign, there is a singular symmetric matrix with 1 on the diagonal and only $x$ and $y$ off the diagonal.

Say $x<0,y>0$. Since $x$ and $y$ are coprime, there are positive integers $n_1,n_2$ such that $n_1 x + n_2 y = -1$. Moreover, $n_1$ and $n_2$ can be chosen to have odd sum, since at least one of $n_1 x + n_2 y = -1$ and $(n_1+y)x + (n2-x)y=-1$ has that property.

Representative examples: $5(-3)+2(7)=-1$, $11(-3)+8(4)=-1$, $4(-4)+5(3)=-1$.

Now make a symmetric matrix of order $n_1+n_2+1$ such that each row has, apart from its diagonal 1, $n_1$ values equal to $x$ and $n_2$ values equal to $y$. This is always possible as a complete graph of even order can be decomposed into hamiltonian cycles and one perfect matching.

The matrix has all row sums equal to 0 so it is singular.

Here is the case $5(-3)+2(7)=-1$ $$\pmatrix{ 1 & -3 & -3 & 7 & -3 & 7 & -3 & -3 \\ -3 & 1 & -3 & -3 & 7 & -3 & 7 & -3 \\ -3 & -3 & 1 & -3 & -3 & 7 & -3 & 7 \\ 7 & -3 & -3 & 1 & -3 & -3 & 7 & -3 \\ -3 & 7 & -3 & -3 & 1 & -3 & -3 & 7 \\ 7 & -3 & 7 & -3 & -3 & 1 & -3 & -3 \\ -3 & 7 & -3 & 7 & -3 & -3 & 1 & -3 \\ -3 & -3 & 7 & -3 & 7 & -3 & -3 & 1 }$$

PART 2

Next, we give a general solution for coprime $x,y$, where $x\ge 2,y\ge x+2$. Find integer $n_2,k$ such that $n_2y+1=kx$; this is possible because $x,y$ are coprime. Now define $n_1=(k-n_2-1)x-k$. It is possible to choose $n_2,k$ such that $n_1,n_2$ are positive and have opposite parity (if necessary add $ty$ to $k$ and $tx$ to $n_2$ for some $t\ge 1$). Also define $n_3=x-1$. Now consider the matrix $$\pmatrix{A&B\\B^T&C}$$ defined like this: $A$ is square of order $n_1+n_2+1$, with each row having one 1 (on the diagonal), $n_1$ of $x$ and $n_2$ of $y$. $C$ is square of order $n_3$. Apart from the diagonal of $C$, which of course is 1, $B$ and $C$ are filled with $x$. This matrix is singular because the vector with first $n_1+n_2+1$ entries equal to $n_3x$ and last $n_3$ entries equal to $-(n_1x+n_2y+1)$ is an eigenvector for eigenvalue 0.

PART 3

Next, we give a general solution for coprime $x,y$, where $x\le -2,y\le x-2$.

This is nearly the same as the previous case. Find integer $n_2,k$ such that $n_2y+1=kx$. Now define $n_1=(n_2-k+1)x-k$. It is possible to choose $n_2,k$ such that $n_1,n_2$ are positive and have opposite parity (if necessary add $ty$ to $k$ and $tx$ to $n_2$ for some $t\ge 1$). Also define $n_3=-x+1$. Now construct the matrix as before.

CONCLUSION

In previous comments it was noted that the cases $-1\in S$, $1\in S$ and $\{k,k+1\}\subseteq S$ have simple constructions. So we have a theorem.

THEOREM If $x,y$ are distinct coprime integers, then there is a singular symmetric matrix with 1 on the diagonal and $x$ or $y$ in every off-diagonal position.

Note that this does not complete the solution to the original problem, as having a set $S$ with no nontrivial common factors does not mean that it contains two coprime elements. Consider $S=\{6,10,15\}$ for example.