11
$\begingroup$

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.

$\endgroup$
0

3 Answers 3

2
$\begingroup$

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

$\endgroup$
2
  • 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
2
$\begingroup$

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

$\endgroup$
11
  • $\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
2
$\begingroup$

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

$\endgroup$
3
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.