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.


3 Answers 3


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


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

  • 1
    $\begingroup$ 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$. $\endgroup$ Aug 5, 2022 at 10:45
  • $\begingroup$ Ah, yes, that’s true. Missed that observation. Might take another look at the problem....as it remains unanswered. $\endgroup$
    – Jack L.
    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).

  • $\begingroup$ 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. $\endgroup$ Aug 8, 2022 at 13:59
  • $\begingroup$ (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)}$). $\endgroup$ Aug 8, 2022 at 14:10
  • $\begingroup$ There is a $(2,9)$ example in my answer now. $\endgroup$ Aug 8, 2022 at 15:58
  • $\begingroup$ @BrendanMcKay, thanks. The singularity is due to the vanishing of a quartic factor, so it's not going to be easy to generalise. $\endgroup$ Aug 8, 2022 at 16:14
  • $\begingroup$ 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)$. $\endgroup$ Aug 9, 2022 at 3:30


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


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.


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.


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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .