# Non-singular matrix with restricted entries

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.

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

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}\,.$$

• The first counterexample can be simplified to the $2 \times 2$ matrix $\begin{pmatrix} 1&-1\\-1& 1\end{pmatrix}$ to show that $-1 \not\in S$. Aug 5, 2022 at 10:45
• Ah, yes, that’s true. Missed that observation. Might take another look at the problem....as it remains unanswered. Aug 5, 2022 at 10:54

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

• If we take a $x J_n$, replace one anti-diagonal with $y$s, and replace the principal diagonal with $1$s, we seem to be able to obtain a factor $-2ax^2 + bxy + (2a-2-b)x + y + 1$ for any $0 \le b < a$. This is singular if $$y = 1 + 2(x - 1) \frac{(ax + 1)}{(bx + 1)}$$ and serves e.g. to cover $2, 4k+3$. I think that $S = \{2, 9\}$ is the simplest case that remains unsolved, and a singular matrix for it might give new ideas. Aug 8, 2022 at 13:59
• (Since $1$ is a unit in the multiplicative group modulo $x$, this could be usefully rewritten as $y = 1 + 2(x-1)(kx + 1)$ or $y \equiv 2x - 1 \pmod{2x(x-1)}$). Aug 8, 2022 at 14:10
• There is a $(2,9)$ example in my answer now. Aug 8, 2022 at 15:58
• @BrendanMcKay, thanks. The singularity is due to the vanishing of a quartic factor, so it's not going to be easy to generalise. Aug 8, 2022 at 16:14
• I replaced it by a much more regular example. The automorphism group is 1728. The eigenvector for the 0 eigenvalue is $(-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,20)$. Aug 9, 2022 at 3:30

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

• @PeterTaylor Hi, I entirely missed the requirement that the matrix be symmetric. Ooops. Aug 7, 2022 at 7:14
• @PeterTaylor Yes, that's how I understood your comment. Aug 7, 2022 at 14:28
• @PeterTaylor Having slept on it, I disagree. There is no parity restriction, see my revised version. Aug 8, 2022 at 2:24