January 01, 1970
In the semigroup \(M_2(\mathbb{N}_0)^\bullet\), two-by-two matrices with non-negative integer entries and non-zero determinant, we study the factorization of matrices into atoms, or irreducible matrices. In 2022, Baeth et al. listed some fundamental classes of atoms in \(M_2(\mathbb{N}_0)^\bullet\); however, the factorability of most matrices in \(M_2(\mathbb{N}_0)^\bullet\) remains unknown. We identify two additional classes of atoms: a class of atoms with determinant \(p\), \(2p\), or \(4p\), for \(p\) prime, and a class of atoms in which the main diagonal is much “larger" than the off-diagonal (or vice versa). Finally, we show that bisymmetric matrices with relatively prime entries are a divisor-closed subset of \(M_2(\mathbb{N}_0)^\bullet\) and use a factor search algorithm to classify bisymmetric atoms of \(M_2(\mathbb{N}_0)^\bullet\) with minimum entry up to 4000.
In 1963, Cohn Cohn63? extended the concept of unique factorization to a non-commutative setting. In particular, semigroups of matrices offer a setting where factorization is not necessarily unique. For example, Jacobsen and Wisner JW86? found that factorization is non-unique in the semigroup of two-by-two positive integral matrices with determinant one and is unique in the semigroup of two-by-two non-negative integral matrices with determinant one.
While a semigroup does not have prime elements in a traditional algebraic sense, we can study the atoms, or irreducibles, which do not factor unless one factor is a unit. (See Section 2 for detailed definitions.) In early studies of two-by-two matrix semigroups with positive integer entries, Chuan and Chuan ChuanChuan86?, ChuanChuan1985? classified all atoms in the semigroup of determinant one matrices, and they found all atoms with prime determinant in the semigroup with positive determinant.
In 2006, Geroldinger and Halter-Koch GHK06? summarized the modern theory of non-unique factorization. Baeth et al. Baeth11?, Baeth21? applied many of these concepts to the semigroup of nonnegative integer matrices with non-zero determinant, \(M_n(\mathbb{N}_0)^\bullet\). Specifically, from Baeth21? we know that factorization in \(M_2(\mathbb{N}_0)^\bullet\) is non-unique; in addition, no atom is prime-like in the sense that an atom may appear with different multiplicities in factorizations of the same matrix. A complete classification of the atoms of \(M_2(\mathbb{N}_0)^\bullet\) is unknown; however, Baeth et al. Baeth21? found the following classes of atoms in \(M_2(\mathbb{N}_0)^\bullet\).
Theorem 1. Baeth21? The following are atoms of \(M_2(\mathbb{N}_0)^\bullet\):
\(\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}\),
\(\begin{pmatrix} p & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 0 & p \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ p & 0 \end{pmatrix}. \begin{pmatrix} 1 & 0 \\ 0 & p \end{pmatrix}\), for \(p\) prime,
\(\begin{pmatrix} w & x \\ y & z \end{pmatrix}, \begin{pmatrix} x & w \\ z & y \end{pmatrix}, \begin{pmatrix} x & z \\ w & y \end{pmatrix}, \begin{pmatrix} z & x \\ y & w \end{pmatrix}\), with \(w \in \{1,2,3\}\), \(\gcd{(wz, xy)}=1\), and \(w\leq z<x,y\),
\(\begin{pmatrix} x & x+1 \\ x+1 & x \end{pmatrix},\begin{pmatrix} x+1 & x \\ x & x+1 \end{pmatrix}\), where \(x\in \mathbb{N}\) and \(2x+1\) is prime.
In Proposition 2, Baeth et al. Baeth21? provides additional criteria for us to find other atoms of the semigroup. In particular, all other atoms not described in Theorem 1 must have relatively prime adjacent entries and must be doubly-balanced, meaning not reducible by row or column operations.
We found additional classes of atoms in \(M_2(\mathbb{N}_0)^\bullet\) within those criteria, the first of which we found by investigating determinants. We show in Theorems 5 and 6 that these restrictions imply matrices with certain determinants are atoms. In particular, a doubly-balanced matrix \(X\) with relatively prime adjacent entries is an atom when \[\left|\det\left( X \right)\right|\in \{16,32\}\cup \{p,2p,4p \mid p \text{ prime}\}.\]
We also specialize to the set of bisymmetric matrices and search for bisymmetric atoms in the larger semigroup of \(M_2(\mathbb{N}_0)^\bullet\). If there is a common factor between the entries of a bisymmetric matrix, then the matrix will factor trivially; therefore we consider the subset of bisymmetric matrices with relatively prime adjacent entries, which we denote by \[\mathcal{B}^*=\left\{\begin{pmatrix} x & y \\ y & x \end{pmatrix}\in M_2(\mathbb{N}_0)^\bullet:\gcd(x,y)\right\}.\]
The set of bisymmetric matrices is not divisor-closed; that is, the factors of bisymmetric matrices are not necessarily bisymmetric. However, when we consider the subset of bisymmetric matrices with relatively prime adjacent entries, we prove that the factors must also be bisymmetric.
7 1. Let \(X=\begin{pmatrix} x & y \\ y & x \end{pmatrix}\in \mathcal{B}^*\). If \(X\) factors into \(X=AB\), where \(A,B \in M_2(\mathbb{N}_0)^\bullet\), then \(A,B \in \mathcal{B}^*\).
This shows that the set \(\mathcal{B}^*\) is divisor-closed in \(M_2(\mathbb{N}_0)^\bullet\). Note that it is a necessary condition that \(X\) has relatively prime adjacent entries; see equation 1 for an example of a bisymmetric matrix that factors into non-bisymmetric factors.
This allows us to consider a smaller subset of possible factors when determining if a bisymmetric matrix is an atom. We use an algorithm to search potential factors and classify all bisymmetric atoms in \(M_2(\mathbb{N}_0)^\bullet\) with minimum up to \(4000\). Critically, the assumption that factors must be bisymmetric greatly simplifies the search for factors. For a fixed minimum value, we give lists of factorizations found; all other bisymmetric matrices with this minimum are atoms.
12 1. Let \(X=\begin{pmatrix} x & y \\ y & x \end{pmatrix} \in \mathcal{B}^*\) with \(\min\{x,y\}\leq 4000\). The matrices listed in BisymData26? (and their associates) are not atoms in \(M_2(\mathbb{N}_0)^\bullet\). If \(X\) and its associate matrix \(\begin{pmatrix} y & x \\ x & y \end{pmatrix}\) do not appear in BisymData26?, then \(X\) is an atom.
In 6, we discover an additional class of atoms using bounds on the diagonal or off-diagonal entries. In particular, in 8, we show that for a doubly-balanced, factorable matrix \(X = \begin{pmatrix} w & x \\ y & z \end{pmatrix}\) satisfying \(\gcd(wz, xy)=1\), then \[x,y\le2(z-1)(w-1)\qquad\text{ and}\qquad w, z \leq 2(x-1)(y-1).\] This leads immediately to a new class of atoms where this bound is not satisfied.
9 1. Let \(X=\begin{pmatrix} w & x \\ y & z \end{pmatrix}\in M_2(\mathbb{N}_0)^\bullet\) such that \(w\le z<x,y\) and \(\gcd{(wz, xy)}=1.\) If \[x>2(z-1)(w-1) \text{or} y>2(z-1)(w-1),\] then \(X\) and its associates are atoms in \(M_2(\mathbb{N}_0)^\bullet\).
For bisymmetric matrices, we prove a stronger upper bound on factorable matrices in 10, which we use to find another class of atoms.
11 1. Let \(X=\begin{pmatrix} x & y \\ y & x \end{pmatrix} \in \mathcal{B}^*\). If \(\max\{x,y\}> 1+ \frac{(\min\{x,y\})^2}{4}\), then \(X\) is an atom in \(M_2(\mathbb{N}_0)^\bullet\).
7 has further implications for discovering additional atoms in \(M_2(\mathbb{N}_0)^\bullet\). For example, results of Pomonarenko allow us to conclude in 5 that matrices in the set \[\left \{\begin{pmatrix} 2^n+1 & 2^n-1 \\ 2^n-1 & 2^n+1 \end{pmatrix}:n\in \mathbb{N}_0\right\}\] are atoms in the semigroup of non-negative integer matrices Ponom22?.
We start off with some well-known definitions that we include for convenience. A semigroup is a set \(S\) which is closed under an associative operation, \(*\). A semigroup is cancellative if for all \(x, y, z \in S\), \(x*y=x*z\) implies that \(y=z\) and similarly \(y*x=z*x\) implies that \(y=z\). A unit is an element \(u\in S\) so that \(u*v=v*u=1_S\), the multiplicative identity of \(S\). In a semigroup, our primary interest is in the factorization of elements within that semigroup. An element \(a\in S\) is an atom (or an irreducible element of \(S\)) if \(a=xy\) implies that \(x\) or \(y\) is a unit. A semigroup \(S\) is said to be atomic if each non-unit of \(S\) factors into a product of atoms.
The set \(M_2(\mathbb{N}_0)^\bullet\) under matrix multiplication is a cancellative semigroup with identity. Further, Baeth et al. showed that \(M_2(\mathbb{N}_0)^\bullet\) is atomic and satisfies the finite factorization property, in other words, that there are finitely many ways to factor a given element Baeth21?. However, factorization in \(M_2(\mathbb{N}_0)^\bullet\) is not unique; for example, \[\label{eq1factor} \begin{pmatrix} 15 & 10 \\ 10 & 15 \end{pmatrix}=\begin{pmatrix} 1 & 2 \\ 3 & 1 \end{pmatrix}\begin{pmatrix} 1 & 4 \\ 7 & 3 \end{pmatrix}= \begin{pmatrix} 5 & 0 \\ 0 & 5 \end{pmatrix} \begin{pmatrix} 3 & 2 \\ 2 & 3 \end{pmatrix}.\tag{1}\]
The only two units in \(M_2(\mathbb{N}_0)^\bullet\) are the identity, \(I=\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\), and the exchange matrix, \(J=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\). Given a matrix \(X=\begin{pmatrix} w & x \\ y & z \end{pmatrix}\), the associates of \(X\) are the matrices obtained by multiplying \(X\) by a unit; namely, the associates of \(X\) are \(X\) itself, \[JX=\begin{pmatrix} y & z \\ w & x \end{pmatrix}, \qquad XJ=\begin{pmatrix} x & w \\ z & y \end{pmatrix},\text{ and}\qquad JXJ=\begin{pmatrix} z & y \\ x & w \end{pmatrix}.\] We will often refer to factorization “up to associates” by which we mean that there are additional factorizations which include the associate matrices of the factors presented.
Frequently, we describe a matrix as having relatively prime adjacent entries. This indicates that the matrix meets the condition that the entries in each row are relatively prime and the entries in each column are relatively prime. This condition is equivalent to requiring that \(\gcd(xy, wz)=1\) for a matrix \(X=\begin{pmatrix} w & x \\ y & z \end{pmatrix}\).
One way to obtain atoms in a semigroup is to consider factorization in a smaller subset. A subset \(T\) is divisor-closed in a semigroup \(S\) if when \(X\in T\) factors into \(X=YZ\) , then the factors \(Y\) and \(Z\) are in \(T\). If \(T\) is a divisor-closed semigroup and \(A\) is an atom of \(T\), then \(A\) is an atom of \(S\) Baeth21?.
One such example is the semigroup \[T = \left\{\begin{pmatrix} x & x+1 \\ x+1 & x \end{pmatrix},\begin{pmatrix} x+1 & x \\ x & x+1 \end{pmatrix}: x\in \mathbb{N}_0\right\}\] which was shown to be divisor-closed in \(M_2(\mathbb{N}_0)^\bullet\) Baeth21?. Therefore, any atoms in \(T\) are also atoms in the full semigroup, \(M_2(\mathbb{N}_0)^\bullet\). However, not all elements of this subsemigroup are atoms; for example, \[\begin{pmatrix} 5 & 4 \\ 4 & 5 \end{pmatrix}=\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}\] is not an atom in \(T\) or \(M_2(\mathbb{N}_0)^\bullet\).
In this paper, we consider the subsemigroup \(\mathcal{B}\) of bisymmetric matrices, \[\mathcal{B}= \left\{\begin{pmatrix} x & y \\ y & x \end{pmatrix}: x,y \in \mathbb{N}_0, x\neq y\right\}.\] This is a commutative subsemigroup which is closed under multiplication; however, it is not divisor-closed in \(M_2(\mathbb{N}_0)^\bullet\). See 1 for an example of a bisymmetric matrix which factors into matrices that are not bisymmetric. However, we specify to the subset \(\mathcal{B}^*\) of matrices with relatively prime adjacent entries and prove that this subset is divisor-closed in 7. However, note that \(\mathcal{B}^*\) is not a subsemigroup as it is not closed under multiplication; for example, \[\begin{pmatrix} 3 & 1 \\ 1 & 3 \end{pmatrix} \begin{pmatrix} 1 & 5 \\ 5 & 1 \end{pmatrix}=\begin{pmatrix} 8 & 16 \\ 16 & 8 \end{pmatrix}\] is not in \(\mathcal{B}^*\), although the factors are in \(\mathcal{B}^*\).
We now consider various conditions that must be met for a matrix to be an atom. We borrow some terminology from Raney Raney73?. We say that a row of a matrix is dominant if both entries are greater than or equal to the corresponding entries in the other row. Similarly, a column is dominant if both entries are greater than or equal to the corresponding entries in the other column. If neither row is dominant, then we say that a matrix is row-balanced, and if neither column is dominant, then we say that the matrix is column-balanced. A matrix is doubly-balanced if it is both row- and column-balanced.
If a matrix is row or column dominant, then it can be factored by an elementary row or column operation – in particular, by an associate of \(\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\). Therefore, atoms of \(M_2(\mathbb{N}_0)^\bullet\) must necessarily be doubly-balanced, unless they are associates of \(\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\), which was shown in Baeth21?.
Proposition 2. Baeth21? Suppose that \(X = \begin{pmatrix} w & x \\ y & z \end{pmatrix}\) is an atom in \(M_2(\mathbb{N}_0)^\bullet\). Then one of the following holds:
If \(X\) has at least one zero entry, then \(X\) is equal to one of the matrices listed in (1) or (2) of Theorem 1.
If \(X\) has no zero entries, then, multiplying by \(\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\) to obtain the minimum entry in the upper left, \(w \leq z< x,y\) and \(\gcd(x, wz)=\gcd(y,wz)=1\).
The second condition is equivalent to requiring that the matrix is doubly-balanced with \(\gcd(xy, wz)=1\).
We also obtain that for a doubly-balanced matrix that factors, the first factor must be row-balanced, and the second factor must be column-balanced.
Proposition 3. Suppose that a doubly-balanced matrix \(X\in M_2(\mathbb{N}_0)^\bullet\) factors into \(X=AB\), where \(A, B \in M_2(\mathbb{N}_0)^\bullet\). The first factor \(A\) is row-balanced, and the second factor \(B\) is column-balanced.
Proof. Suppose for contradiction’s sake that \(A=\begin{pmatrix} a & b \\ c & d \end{pmatrix}\) is not row-balanced. Without loss of generality, suppose \(a\geq c\) and \(b\geq d\). Then, \(A\) will factor into \[A= \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} a-c & b-d \\ c & d \end{pmatrix}\] where both matrices are non-negative. Letting \(R=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\) and \(A'=\begin{pmatrix} a-c & b-d \\ c & d \end{pmatrix}\), we see that \(A=RA'\) implies \(X=AB = R(A' B)\) is not row-balanced.
Similarly, if \(B\) is not column-balanced, then \(B\) will factor into \(B=B' R_2\) where \(R_2=\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}\) or \(\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\). But then \(X=AB=(AB')R_2\) is not column-balanced. ◻
If we additionally require that adjacent entries are relatively prime, then we also obtain that the factors must not have any zero entries.
Lemma 1. Let \(X=\begin{pmatrix} w & x \\ y & z \end{pmatrix}\in M_2(\mathbb{N}_0)^\bullet\) be doubly-balanced and \(\gcd{(wz, xy)}=1.\) If \(X=AB\) where \(A, B \in M_2(\mathbb{N}_0)^\bullet\) are not units, then \(A\) and \(B\) have no zero entries.
Proof. Suppose that \(X\) factors into \(X=\begin{pmatrix} a & b \\ c & d \end{pmatrix}\begin{pmatrix} e & f \\ g & h \end{pmatrix}\) and \(a=0\). Then, \[X=\begin{pmatrix} 0 & b \\ c & d \end{pmatrix}\begin{pmatrix} e & f \\ g & h \end{pmatrix}=\begin{pmatrix} bg & bh \\ ce+dg & cf+dh \end{pmatrix}.\] If \(b>1\), then this matrix would not satisfy the condition that \(\gcd(wz,xy)=1\). If \(b=0\), the determinant of the first factor would be zero. Therefore, we must have \(b=1\). Then \(X\) simplifies to \[X=\begin{pmatrix} 0 & 1 \\ c & d \end{pmatrix}\begin{pmatrix} e & f \\ g & h \end{pmatrix}=\begin{pmatrix} g & h \\ ce+dg & cf+dh \end{pmatrix}.\] Note that \(X\) is not row-balanced unless \(d=0\); otherwise \(g\leq ce+dg\) and \(h\leq cf+dh\). Therefore, \(d=0\) and \(X\) simplifies to \[X=\begin{pmatrix} 0 & 1 \\ c & 0 \end{pmatrix}\begin{pmatrix} e & f \\ g & h \end{pmatrix}=\begin{pmatrix} g & h \\ ce & cf \end{pmatrix}.\] However, this contradicts the condition that \(\gcd(wz, xy)=1\) unless \(c=1\), in which case the first factor is the exchange matrix.
If any entry in either factor is zero, we can show by similar argument that the factor is either the exchange or identity matrix. ◻
If we factor a doubly-balanced matrix with relatively prime adjacent entries into atoms, we additionally obtain that the first and last atoms in the factorization have non-zero entries, as opposed to the atoms listed in (1) and (2) from 1. This also results in the first and last atoms in the factorization being of similar character: doubly-balanced with relatively prime adjacent entries.
Corollary 4. Let \(X\in M_2(\mathbb{N}_0)^\bullet\) be factorable, doubly-balanced, and have relatively prime adjacent entries. For all factorizations \(X=X_0\cdots X_n\) into \(X_i\) atoms, it follows that \(X_0\) and \(X_n\) have no zero entries, are doubly-balanced, and have relatively prime adjacent entries.
Proof. Let \(X \in M_2(\mathbb{N}_0)^\bullet\) be a factorable, doubly-balanced matrix with relatively prime adjacent entries. Suppose \(X\) factors into \(X=X_0\cdots X_n\) where each \(X_i\) is an atom. We have factorizations into \(X = X_0 (X_1 \cdots X_n)\) or \(X = (X_0 \cdots X_{n-1}) X_n\), and by 1, then \(X_0\) and \(X_n\) must have no zero entries. (Note that \(X_0\) and \(X_n\) are atoms and so are not units.) Therefore by Proposition 3.1, \(X_0\) and \(X_n\) must be doubly-balanced with relatively prime adjacent entries. ◻
It immediately follows that a factorable, doubly-balanced matrix with relatively prime adjacent entries must factor into at least two matrices of similar character. If it does not, then we conclude it must be an atom.
We now turn our attention to the determinants of matrices. Throughout this section, we focus on matrices in \(M_2(\mathbb{N}_0)^\bullet\) which are doubly-balanced with relatively-prime adjacent entries, since these matrices are the “candidates” to be atoms from 2. First, we will obtain a lower bound on the determinant from the minimum entry of the matrix.
Lemma 2. Suppose \(X\in M_2(\mathbb{N}_0)^\bullet\) is a doubly-balanced matrix with relatively prime adjacent entries, and let \(m\) be the minimum entry of \(X\). Then, \(\left|\det\left( X \right)\right|\ge 2m+1\).
Proof. Let \(X\) be doubly-balanced with relatively prime adjacent entries. Multiply \(X\) by the exchange matrix \(J\) until the matrix is in the form \(\begin{pmatrix} w & x \\ y & z \end{pmatrix}\) where \(w\) is its minimum entry and by 2, \(1\le w\le z<x,y\). Without loss of generality, we will call this reduced form \(X\). Note that the absolute value of the determinant of \(X\) remains unchanged since \(\left|\det\left( J \right)\right|=1\). It follows that \(x,y\ge z+1\) and \(xy \ge (z+1)(z+1).\) Since \(z\ge w\), we find that \[\begin{align} xy &\ge (w+1)(z+1) \\ &= wz+w+z+1 \\ &\ge wz+2w+1. \end{align}\] Subtracting \(wz\) from the final inequality results in \(xy - wz \ge 2w+1\) resulting in the absolute value of the determinant of \(X\), \[\left|\det\left( X \right)\right|=|wz-xy| = xy-wz\ge 2w+1,\] where \(w\) is the minimum entry of \(X\). ◻
Since the entries of matrices in \(M_2(\mathbb{N}_0)^\bullet\) are non-negative, we can use the lower bound in Lemma 2, along with divisibility properties, to get a restriction on the small determinants \(1\), \(2\), and \(4\).
Lemma 3. Suppose \(X\in M_2(\mathbb{N}_0)^\bullet\) is a doubly-balanced matrix with relatively prime adjacent entries. Then \(\left|\det\left( X \right)\right|\not \in \{1,2,4\}.\)
Proof. Let \(X\in M_2(\mathbb{N}_0)^\bullet\) be a doubly-balanced matrix with relatively prime adjacent entries. By 2, \(\left|\det\left( X \right)\right| \ge 2m+1\) where \(m\) is the minimum entry of \(X\). No entry can be zero, so \(m \ge 1\) implies \(\left|\det\left( X \right)\right|\ge 3,\) and \(\left|\det\left( X \right)\right| \not \in \{1,2\}.\)
Now suppose for sake of contradiction that \(\left|\det\left( X \right)\right|=4\). 2 bounds \(2m+1\le 4,\) which implies \(m=1\). Let \(X\) have arbitrary entries \(X=\begin{pmatrix} w & x \\ y & z \end{pmatrix}\), and notice how \(\left|\det\left( X \right)\right|=|wz-xy|=4\). Since their difference is even, \(wz\) and \(xy\) will have the same parity, and we find that they must both be odd; otherwise, an adjacent pair of entries in \(X\) would share a factor of \(2\) and not be relatively prime. Since \(X\) is doubly-balanced, there are two cases to consider. In case 1, we let \(w>x\) and \(z>y\), which implies \(w\geq x+1\) and \(z\geq y+1\) since each entry is an integer. Then, \(wz \ge (x+1)(y+1)\) implies that \[\begin{align} wz=xy+4 &\ge (x+1)(y+1)\\ &= xy+x+y+1. \end{align}\] This simplifies to \(3\ge x+y\), which implies that either \(xy=2\), which is even, and thus a contradiction, or \(xy=1\). If \(xy=1\), then \(|wz-xy|=4\) implies that \(wz=5\) (since \(w\) and \(z\) are non-negative), so the remaining entries are \(1\) and \(5\), contradicting that the matrix is doubly-balanced.
In case 2, we flip the inequalities so \(w<x\) and \(z<y\), and hence \(xy \ge (w+1)(z+1)\). We arrive at a similar inequality, \[\begin{align} xy=wz+4 &\ge (w+1)(z+1)\\ &= wz+w+z+1, \end{align}\] which simplifies to \(3\ge w+z\). Employing the same techniques from case 1, we find that \(wz=1\) or \(2\), which both give contradictions.
Both cases being exhausted, it follows that \(\left|\det\left( X \right)\right|\not \neq {4}\). ◻
Once we eliminate \(1\), \(2\), and \(4\) from possible determinants of doubly-balanced matrices with relatively prime adjacent entries, we can also obtain restrictions on the determinants on factorable matrices, since determinants are multiplicative. In particular, the determinant of a factorable matrix of this type cannot be \(p\), \(2p\), or \(4p\), where \(p\) is prime.
Theorem 5. Suppose \(X\in M_2(\mathbb{N}_0)^\bullet\) is a doubly-balanced matrix with relatively prime adjacent entries. The matrix \(X\) is an atom if the absolute value of the determinant is \(p\), \(2p\), or \(4p\), where \(p\) is prime.
Proof. Let \(X\in M_2(\mathbb{N}_0)^\bullet\) be a doubly-balanced matrix with relatively prime adjacent entries where \(\left|\det\left( X \right)\right|=mp\) for \(p\) prime and \(m\in\{1,2,4\}\). Assume, by way of contradiction, that \(X\) is not an atom. By 4, we know that \(X\) can be expressed as a product of atoms \(X_{0}\cdots X_{n}\) where \(X_0\) and \(X_n\) are also doubly-balanced with relatively prime adjacent entries. Applying Lemmas 4.1 and 4.2, this means that \(d_0=\left|\det\left( X_0 \right)\right|\) and \(d_n=\left|\det\left( X_n \right)\right|\) must be positive with \(d_0,d_n\not \in \{1,2,4\}.\) We show that for all three values of \(m\), the atoms \(X_0\) and \(X_n\) cannot exist.
If \(m=1\), then \(\left|\det\left( X \right)\right|=p\), \[d_0d_n \le p \qquad \text{ and} \qquad d_0,d_n\mid p.\] This implies \(d_0\mid p\) and \(d_n\mid p\). Neither can be \(1\), so \(d_0=d_n=p\) and thus, we arrive at a contradiction where \(d_0 d_n=p^2.\)
If instead \(m=2\), then \[d_0d_n \le 2p \qquad \text{ and} \qquad d_0,d_n\mid 2p.\] Since neither \(d_0\) nor \(d_n\) equals \(1\) or \(2\), this again implies they both divide \(p\), which leads to contradiction.
Finally, if \(m=4\), then \[d_0d_n \le 4p \qquad \text{ and} \qquad d_0,d_n\mid 4p.\] Since \(d_0\) cannot equal \(1\), \(2\), or \(4\), it cannot divide \(4\). Therefore, \(d_0, d_n\mid 4p\) implies that \(d_0\) is equal to \(p\), \(2p\), or \(4p\). But that implies that \(d_n\) is equal to \(4\), \(2\), or \(1\), which is a contradiction. ◻
We also apply Lemma 4.2 to find more determinants that yield additional atoms.
Theorem 6. Suppose \(X\in M_2(\mathbb{N}_0)^\bullet\) is a doubly-balanced matrix with relatively prime adjacent entries. The matrix \(X\) is an atom if the absolute value of its determinant is \(16\) or \(32\).
Proof. Let \(X\in M_2(\mathbb{N}_0)^\bullet\) be a doubly-balanced matrix with relatively prime adjacent entries where \(\left|\det\left( X \right)\right|=32\). If \(X\) is not an atom, then by 4, \(X\) factors into \(X = X_0\cdots X_n\), where \(X_i\) are atoms and \(X_0\) and \(X_n\) are doubly-balanced with relatively prime adjacent entries. By the multiplicative property of determinants, \[\left|\det\left( X \right)\right| = \prod_{i=0}^n \left|\det\left( X_i \right)\right|=32=2^5\] Therefore, we must have that \(\left|\det\left( X_0 \right)\right|=2^a\) and \(\left|\det\left( X_n \right)\right|=2^b\) for non-negative integers \(a\) and \(b\). However, by 3, \(\left|\det\left( X_0 \right)\right|\) and \(\left|\det\left( X_n \right)\right|\) cannot equal \(1\), \(2\), or \(4\), so they must be at least \(8\). But then \(\left|\det\left( X \right)\right| \geq \left|\det\left( X_0 \right)\right| \left|\det\left( X_n \right)\right| \geq 64\) contradicts that \(\left|\det\left( X \right)\right|=32\). Therefore \(X\) is an atom.
The proof that \(|\det (X)|=16\) implies that \(X\) is an atom is identical. ◻
Recall the subset of bisymmetric matrices with relatively prime adjacent entries, \[\mathcal{B}^*=\left\{\begin{pmatrix} x & y \\ y & x \end{pmatrix}\in M_2(\mathbb{N}_0)^\bullet:\gcd(x,y)=1\right\}.\] We will show that this subset is divisor-closed in \(M_2(\mathbb{N}_0)^\bullet\).
Theorem 7. Let \(X=\begin{pmatrix} x & y \\ y & x \end{pmatrix}\in \mathcal{B}^*\). If \(X\) factors into \(X=AB\), where \(A,B \in M_2(\mathbb{N}_0)^\bullet\), then \(A,B \in \mathcal{B}^*\).
Proof. Let \(A=\begin{pmatrix} a & b \\ c & d \end{pmatrix}\) and \(B=\begin{pmatrix} e & f \\ g & h \end{pmatrix}\). By multiplying \(A\) and \(B\) and equating the entries to those in \(X\), we get \[\label{eqn:sys} \begin{cases} ae+bg=cf+dh,\\ af+bh=ce+dg. \end{cases}\tag{2}\] If \(a=c\), then by adding up the equations in 2 , we have \(b(g+h)=d(g+h)\). This implies that \(b=d\), contradicting that the determinant of \(A\) is nonzero. Hence, \(a\neq c\). Assume without loss of generality that \(a>c\); otherwise, we may switch the rows in \(A\) and \(X\) by multiplying by the exchange matrix, \(J\).
By treating 2 as a system of linear equations, we can solve for the variables \(e\) and \(f\) as \[\label{eqn:ef} \begin{cases} e=\dfrac{1}{a^2-c^2}\big((ad-bc)h+(cd-ab)g\big),\\ f=\dfrac{1}{a^2-c^2}\big((ad-bc)g+(cd-ab)h\big), \end{cases}\tag{3}\] and we obtain \[\label{eqn:xy} \begin{cases} x=ae+bg=\dfrac{1}{a^2-c^2}(ad-bc)(ah+cg),\\ y=af+bh=\dfrac{1}{a^2-c^2}(ad-bc)(ag+ch).\\ \end{cases}\tag{4}\] Note that \(ad-bc>0\) since \(x\) and \(y\) are nonnegative with at least one of them positive.
Since \(\gcd(x,y)=1\), we have from 4 that \[\label{eqn:a942-c942first} a^2-c^2=(ad-bc)\gcd(ah+cg,ag+ch).\tag{5}\] In particular, \((ad-bc)\gcd(g,h)\) divides \(a^2-c^2\). Since \((ad-bc)\gcd(g,h)\) divides both \((ad-bc)h\) and \((ad-bc)g\), we deduce from 3 that \((ad-bc)\gcd(g,h)\) divides both \((cd-ab)g\) and \((cd-ab)h\). This implies that \((ad-bc)\gcd(g,h)\) divides \((cd-ab)\gcd(g,h)\), or equivalently \(ad-bc\) divides \(cd-ab\). Consequently, either \(cd-ab=0\), \(cd-ab\leq-(ad-bc)\), or \(cd-ab\geq ad-bc\).
If \(cd-ab\leq-(ad-bc)\), then since both \(e\) and \(f\) are nonnegative, we have \(g=h\) and thus \(e=f\), contradicting that the determinant of \(B\) is nonzero. If \(cd-ab\geq ad-bc\), then \(c(b+d)\geq a(b+d)\), contradicting that \(a>c\). Hence, \(cd-ab=0\), implying that \(a^2-c^2\) divides \((ad-bc)\gcd(g,h)\) since both \(e\) and \(f\) are integers. As a result, \[\label{eqn:a942-c942second} a^2-c^2=(ad-bc)\gcd(g,h).\tag{6}\]
From \(cd-ab=0\), we have \(d=\frac{ab}{c}\), so \(a^2-c^2=\big(\frac{a^2b}{c}-bc\big)\gcd(g,h)=(a^2-c^2)\frac{b}{c}\gcd(g,h)\). This implies that \(c=b\gcd(g,h)\). Combining with \(d=\frac{ab}{c}\), we have \(a=d\gcd(g,h)\). Lastly, if we compare 5 and 6 , we get \(\gcd(a,c)=1\), so \(\gcd(g,h)=1\). Therefore, \(a=d\) and \(b=c\), and we also have \(e=h\) and \(f=g\) from 3 , which leads to the conclusion that \(A,B\in\mathcal{B}^*\). ◻
This result is surprising because bisymmetric matrices are not generally divisor-closed, unless we require that the entries are relatively prime. For example, consider the matrix \(\begin{pmatrix} 15 & 10 \\ 10 & 15 \end{pmatrix}\). This has the non-trivial factorization \[\label{ex1factor} \begin{pmatrix} 15 & 10 \\ 10 & 15 \end{pmatrix}=\begin{pmatrix} 1 & 2 \\ 3 & 1 \end{pmatrix}\begin{pmatrix} 1 & 4 \\ 7 & 3 \end{pmatrix},\tag{7}\] where both factors are atoms by 1, doubly-balanced, have no zero entries, and have relatively-prime adjacent entries. However, when the entries of the bisymmetric matrix are relatively prime, this type of factorization is impossible.
Note that \(\mathcal{B}^*\) is not a semigroup, since it is not closed under multiplication. However, we have shown that \(\mathcal{B}^*\) is a divisor-closed subset of \(M_2(\mathbb{N}_0)^\bullet\). Therefore, bisymmetric matrices that factor in \(\mathcal{B}^*\) will also factor in \(M_2(\mathbb{N}_0)^\bullet\), and matrices that do not factor in \(\mathcal{B}^*\) will not factor in \(M_2(\mathbb{N}_0)^\bullet\). This allows us to use the relatively simple subset to determine if a matrix factors. We will demonstrate this with an example.
The group of bisymmetric matrices is isometric to the group of “perplex numbers”, also called split complex numbers, hyperbolic numbers, or various other names. Pomonarenko proposed the study of “perplex integers.” There are two possible definitions but the first, \(\mathbb{P}_1\), is isomorphic to the semigroup of bisymmetric integer matrices. Although we are studying the semigroup of bisymmetric matrices with non-negative entries, matrices that do not factor into integer bisymmetric matrices will then not factor into non-negative bisymmetric matrices.
Pomonarenko found a class of irreducible perplex integers that correspond to bisymmetric integer matrices which do not factor Ponom22?, namely \[\left\{\begin{pmatrix} 2^n+1 & 2^n-1 \\ 2^n-1 & 2^n+1 \end{pmatrix}:n\in \mathbb{N}_0\right\}.\] Note that these entries are relatively prime since they are odd and differ by 2. By 7, since any factors must be bisymmetric, these matrices must be atoms in \(M_2(\mathbb{N}_0)^\bullet\).
We obtain an additional class of atoms by finding an upper bound on factorable matrices in \(M_2(\mathbb{N}_0)^\bullet\). Then we will tighten this upper bound for bisymmetric matrices.
Theorem 8. Let \(X=\begin{pmatrix} w & x \\ y & z \end{pmatrix}\in M_2(\mathbb{N}_0)^\bullet\) such that \(X\) is doubly balanced and \(\gcd(wz, xy)=1.\) If \(X\) is not an atom then it must satisfy \[x,y\le2(z-1)(w-1),\] \[w, z \leq 2(x-1)(y-1).\]
Proof. Let \(X=\begin{pmatrix} w & x \\ y & z \end{pmatrix}\in M_2(\mathbb{N}_0)^\bullet\) be doubly-balanced with \(\gcd(wz, xy)=1.\) Suppose \(X=\begin{pmatrix} a & b \\ c & d \end{pmatrix}\begin{pmatrix} e & f \\ g & h \end{pmatrix}.\) Then observe the equations \[\begin{align} w&=ae+bg \tag{8}\\ x&=af+bh \tag{9} \\ y&=ce+dg \tag{10} \\ z&=cf+dh \tag{11}. \end{align}\]
We can use the fact that from Lemma 1 all variables are greater than zero to show that \[a\le ae=w-bg \le w-1\] using 8 . The same equation shows that \(b,g,e\le w-1\) by similar logic. Similarly, 11 shows that \(c,d,f,h\le z-1\). We can apply these inequalities to 9 10 to show \[x=af+bh \le (w-1)(z-1)+(w-1)(z-1) \le 2(w-1)(z-1)\] and \[y=ce+dg \le (w-1)(z-1)+(w-1)(z-1) \le 2(w-1)(z-1).\] ◻
One consequence of 8 is that any doubly-balanced matrix with relatively prime adjacent entries which does not satisfy the above bounds is necessarily an atom. This gives an entire class of atoms; if we fix, for example, \(w\) and \(z\), then we can generate atoms by making \(x\) or \(y\) sufficiently large.
Corollary 9. Let \(X=\begin{pmatrix} w & x \\ y & z \end{pmatrix}\in M_2(\mathbb{N}_0)^\bullet\) such that \(w\le z<x,y\) and \(\gcd(wz, xy)=1.\) If \(x>2(z-1)(w-1)\) or \(y>2(z-1)(w-1)\), then \(X\) and its associates are atoms in \(M_2(\mathbb{N}_0)^\bullet\).
Proof. This is the contrapositive of 8. ◻
We will consider a subset of bisymmetric matrices with relatively prime adjacent entries, \[\mathcal{B}^*=\left\{\begin{pmatrix} x & y \\ y & x \end{pmatrix}\in \mathcal{B}: \gcd(x,y)=1\right\}.\] Note that \(\mathcal{B}^*\) is not a subsemigroup as it is not closed under multiplication. Further, not every element of \(\mathcal{B}^*\) is an atom; for example, \(\begin{pmatrix} 5 & 4 \\ 4 & 5 \end{pmatrix}\in \mathcal{B}^*\) but is not an atom. However, the condition that \(x\) and \(y\) are relatively prime is a necessary condition to being an atom. The upper bound in 8 can be improved when the matrix is bisymmetric.
Theorem 10. Let \(X=\begin{pmatrix} x & y \\ y & x \end{pmatrix} \in \mathcal{B}^*\). If \(X\) is not an atom then it must satisfy \[x\leq1+\frac{y^2}{4}\text{ and }y\leq1+\frac{x^2}{4}.\] Furthermore, these bounds are sharp, i.e., there exists \(X\) achieving these bounds.
Proof. By Theorem 7, let \(X=AB\) for some nonunits \(A=\begin{pmatrix} a & b \\ b & a \end{pmatrix}\) and \(B=\begin{pmatrix} c & d \\ d & c \end{pmatrix}\) in \(\mathcal{B}^*\). Note that \(a,b,c,d>0\) by Lemma 1. Now, \(ac+bd=x\), so we let \(ac=\dfrac{x}{2}+t\) and \(bd=\dfrac{x}{2}-t\) for some real number \(t\in\left[1-\dfrac{x}{2},\dfrac{x}{2}-1\right]\). This implies that \(ad\leq abcd=\dfrac{x^2}{4}-t^2\leq\dfrac{x^2}{4}\), \(c=\dfrac{1}{a}\left(\dfrac{x}{2}+t\right)\), and \(b=\dfrac{1}{d}\left(\dfrac{x}{2}-t\right)\). Hence, \[y=ad+bc=ad+\frac{1}{ad}\left(\frac{x^2}{4}-t^2\right)\leq ad+\frac{1}{ad}\frac{x^2}{4}\leq1+\frac{x^2}{4},\] where the last inequality is due to \(1+\dfrac{x^2}{4}-ad-\dfrac{1}{ad}\dfrac{x^2}{4}=(ad-1)\left(\dfrac{1}{ad}\dfrac{x^2}{4}-1\right)\geq0\). (Note that \(ad\leq \frac{x^2}{4}\) implies that \(\frac{1}{ad}\geq \frac{4}{x^2}\), and thus \(\frac{1}{ad}\frac{x^2}{4}\geq 1\).) The inequality \(x\leq1+\dfrac{y^2}{4}\) follows similarly by considering \(\begin{pmatrix} y & x \\ x & y \end{pmatrix}=\begin{pmatrix} b & a \\ a & b \end{pmatrix}\begin{pmatrix} c & d \\ d & c \end{pmatrix}\).
Lastly, we will show that the bounds are sharp. When \(x\) is a positive multiple of \(4\), then \(x\) and \(1+\frac{x^2}{4}\) are non-negative integers and relatively prime. Then, \[\begin{pmatrix} x & 1+\frac{x^2}{4} \\ 1+\frac{x^2}{4} & x \end{pmatrix}=\begin{pmatrix} 1 & \frac{x}{2} \\ \frac{x}{2} & 1 \end{pmatrix}\begin{pmatrix} \frac{x}{2} & 1 \\ 1 & \frac{x}{2} \end{pmatrix}\text{ and }\begin{pmatrix} 1+\frac{y^2}{4} & y \\ y & 1+\frac{y^2}{4} \end{pmatrix}=\begin{pmatrix} \frac{y}{2} & 1 \\ 1 & \frac{y}{2} \end{pmatrix}\begin{pmatrix} \frac{y}{2} & 1 \\ 1 & \frac{y}{2} \end{pmatrix}\] achieve these upper bounds. ◻
After establishing these upper bounds, we can conclude that any matrix which violates these upper bounds is an atom.
Corollary 11. Let \(X=\begin{pmatrix} x & y \\ y & x \end{pmatrix} \in \mathcal{B}^*\). If \(\max\{x,y\}> 1+ \frac{(\min\{x,y\})^2}{4}\), then \(X\) is an atom in \(M_2(\mathbb{N}_0)^\bullet\).
Proof. This is a direct result of 10. ◻
For a fixed minimum value, this theorem establishes a large class of atoms when the maximum value is sufficiently large and the condition that \(\gcd(x,y)=1\) is met. In the next section, we algorithmically search for factors to determine which bisymmetric matrices are atoms up to the upper bound in 11. This gives us a complete description of the atoms and non-atoms, up to the minimum value of our search.
Let \(X=\begin{pmatrix} x & y \\ y & x \end{pmatrix}\in \mathcal{B}^*\) be a bisymmetric matrix which factors into \(X=AB\), where \(A, B \in M_2(\mathbb{N}_0)^\bullet\). Then by 7, both factors are bisymmetric, namely \(A=\begin{pmatrix} a & b \\ b & a \end{pmatrix}\) and \(B=\begin{pmatrix} c & d \\ d & c \end{pmatrix}\), so that \[\label{eq:bisymfactor} \begin{pmatrix} x & y \\ y & x \end{pmatrix}= \begin{pmatrix} a & b \\ b & a \end{pmatrix}\begin{pmatrix} c & d \\ d & c \end{pmatrix}.\tag{12}\]
Note that by 1, \(a,b,c,d>0\) since \(X \in \mathcal{B}^*\). We have created an algorithm to search for possible factorizations. From equation 12 , we know that \(x=ac+bd\) and \(y=ad+bc\). Rather than search through all possible entries for \(A\) and \(B\), which would require four possible entries, we can optimize this algorithm by considering possible non-negative integer partitions of \(x\). The idea is to fix \(x\) and search possible values of \(ac\), which then determines \(bd\). We can then check if these values are divisible by \(a\) and \(b\), respectively, which then determine \(c\), \(d\), and \(y\). Therefore we only need to search through three different variables: \(ac\), \(a\), and \(b\), which minimizes the computational time.
Without loss of generality, we assume that \(x<y\). This will not miss any possible factorizations, because if \(x>y\), then the associate matrix \(\begin{pmatrix} y & x \\ x & y \end{pmatrix}\) will be detected by the algorithm. Note that if \(X=AB\) factors into non-negative integer matrices, then multiplying by the exchange matrix \(J = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\), the matrix \(\begin{pmatrix} y & x \\ x & y \end{pmatrix}=JX=(JA)B\) also factors into non-negative integer matrices. Note that for \(x=1,2,3\), these matrices are already known to be atoms in \(M_2(\mathbb{N}_0)^\bullet\) by Theorem 1.
Using the above restrictions, we now give an outline of the code. The complete code, implemented in Python, can be found at BisymData26?.
FOR x in minimum values:
FOR AC in 1 to x-1:
DEFINE BD=x-AC
FOR a in 1 to AC:
IF AC is divisible by a:
DEFINE c=AC/a
FOR b in 1 to BD:
IF BD is divisible by b:
DEFINE d=BD/b
DEFINE y=a*d-b*c
IF x and y are relatively prime AND x<y
Store factorizationThe factorizations of matrices with minimum entry up to 4000 can be found at BisymData26?. For brevity’s sake, only the matrices \(\begin{pmatrix} x & y \\ y & x \end{pmatrix}\) where \(x<y\) are listed, although the associate matrix \(\begin{pmatrix} y & x \\ x & y \end{pmatrix}\) will also have a factorization. If a matrix with minimum entry up to 4000 or its associate does not appear in this list, then it is an atom.
Theorem 12. Let \(X=\begin{pmatrix} x & y \\ y & x \end{pmatrix} \in \mathcal{B}^*\) with \(\min\{x,y\}\leq 4000\). The matrices listed in BisymData26? (and their associates) are not atoms in \(M_2(\mathbb{N}_0)^\bullet\). If \(X\) and its associate matrix do not appear in BisymData26?, then \(X\) is an atom.
In Appendix 8, we list the factorable bisymmetric matrices with relatively prime entries and minimum up to 42. The bisymmetric non-atoms with minimum up to 12 and their factorizations appear in Table ¿tbl:table:32main?. The bisymmetric matrices from minimum 13 to 42 that are not atoms are listed in Table ¿tbl:table:32extended? (without the factorization). For brevity, only the matrices with \(x<y\) are listed. All other bisymmetric matrices with relatively prime entries and minimum entry up to 42 are atoms.
\(\begin{array}{|c|c|c|} \hline \text{Minimum value}& \text{Non-atoms satisfying }\gcd(x,y)=1& \text{Factors (up to associates)}\\ \hline x=4& \pmx{4}{5}{5}{4} & \pmx{1}{2}{2}{1} \pmx{2}{1}{1}{2}\\ x=5 &\pmx{5}{7}{7}{5} & \pmx{1}{2}{2}{1} \pmx{3}{1}{1}{3}\\ x=6 & \text{none} &\\ x=7 & \pmx{7}{8}{8}{7} & \pmx{1}{2}{2}{1}\pmx{3}{2}{2}{3}\\ & \pmx{7}{11}{11}{7}& \pmx{1}{2}{2}{1}\pmx{5}{1}{1}{5}\\ & \pmx{7}{13}{13}{7}& \pmx{1}{3}{3}{1}\pmx{4}{1}{1}{4}\\ x=8 & \pmx{8}{13}{13}{8} & \pmx{1}{2}{2}{1}\pmx{6}{1}{1}{6}\\ & \pmx{8}{17}{17}{8}&\pmx{1}{4}{4}{1}\pmx{4}{1}{1}{4}\\ x=9 & \pmx{9}{11}{11}{9} & \pmx{1}{3}{3}{1}\pmx{3}{2}{2}{3}\\ & \pmx{9}{19}{19}{9} & \pmx{1}{3}{3}{1}\pmx{6}{1}{1}{6}\\ x=10& \pmx{10}{11}{11}{10} & \pmx{1}{2}{2}{1}\pmx{4}{3}{3}{4}\\ &\pmx{10}{17}{17}{10}& \pmx{1}{2}{2}{1} \pmx{8}{1}{1}{8}\\ x=11& \pmx{11}{13}{13}{11}&\pmx{1}{2}{2}{1}\pmx{5}{3}{3}{5}\\ & \pmx{11}{14}{14}{11}&\pmx{1}{4}{4}{1}\pmx{3}{2}{2}{3}\\ & \pmx{11}{16}{16}{11}&\pmx{1}{2}{2}{1}\pmx{7}{2}{2}{7}\\ &\pmx{11}{17}{17}{11} & \pmx{1}{3}{3}{1}\pmx{5}{2}{2}{5}\\ &\pmx{11}{19}{19}{11} & \pmx{1}{2}{2}{1}\pmx{9}{1}{1}{9}\\ &\pmx{11}{25}{25}{11} & \pmx{1}{3}{3}{1}\pmx{8}{1}{1}{8}\\ & \pmx{11}{29}{29}{11} &\pmx{1}{4}{4}{1}\pmx{7}{1}{1}{7}\\ & \pmx{11}{31}{31}{11} & \pmx{1}{5}{5}{1}\pmx{6}{1}{1}{6}\\ x=12& \pmx{12}{13}{13}{12} & \pmx{2}{3}{3}{2}\pmx{3}{2}{2}{3}\\ & \pmx{12}{37}{37}{12}& \pmx{1}{6}{6}{1} \pmx{6}{1}{1}{6}\\ \hline \end{array}\)
\(\begin{array}{|c|l|} \hline x&y\\ \hline 13 & 14, 15, 17,20,22,23,31,37,41,43\\ 14 & 19,25,41\\ 15 & 29, 37\\ 16 & 17, 19, 23, 29, 49, 61, 65\\ 17 & 18, 19, 22, 23, 25, 27, 28, 31, 32, 35, 37, 38, 43, 53, 61, 67, 71, 73\\ 18 & 73\\ 19 & 20, 21, 23, 25, 26, 29, 31, 32, 33, 35, 37, 41, 44, 46, 47, 49, 61, 71, 79, 85, 89, 91\\ 20 & 29, 31, 37, 97, 101\\ 21 & 23, 29, 31, 47, 55, 109\\ 22 & 23, 27, 29, 35, 41, 43, 73, 97, 113\\ 23 & 25, 26, 27, 28, 29, 31, 32, 33, 34, 37, 40, 43, 45, 47, 53, 58, 61, 62, 65, 67, 68, 77, 91, 103, 113, 121, 127, 131, 133\\ 24 & 25, 31, 109, 145\\ 25 & 26, 27, 29, 31, 32, 38, 41, 43, 44, 47, 51, 52, 53, 59, 67, 74, 77, 79, 101, 127, 137, 151, 157\\ 26 & 29, 31, 37, 43, 49, 51, 59, 89, 121, 145, 161\\ 27 & 28, 29, 38, 41, 49, 65, 73, 83, 92, 127, 163, 181\\ 28 & 29, 37, 41, 47, 53, 67, 97, 181, 193, 197\\ 29 & 31, 34, 36, 37, 39, 40, 41, 43, 46, 47, 49, 52, 55, 56, 59, 62, 63, 69, 71, 73, 79, 86, 92, 97, 101, 104, 106, 107, 121,\\ &139, 155, 169, 181, 191, 199, 205, 209, 211\\ 30 & 217\\ 31 & 32, 34, 35, 37, 38, 39, 41, 44, 45, 46, 47, 49, 50, 53, 56, 59, 61, 64, 67, 69, 73, 77, 79, 81, 83, 85, 86, 94, 101, 107,\\ &109, 112, 116, 119, 121, 122, 131, 151, 169, 185, 199, 211, 221, 229, 235, 239, 241\\ 32 & 33, 37, 43, 49, 53, 55, 59, 61, 67, 83, 87, 113, 157, 193, 221, 241, 253, 257\\ 33 & 35, 37, 43, 47, 58, 59, 67, 83, 91, 128, 137, 163, 217, 271\\ 34 & 35, 41, 43, 47, 53, 59, 61, 65, 83, 91, 99, 121, 169, 209, 241, 265, 281\\ 35 & 37, 41, 43, 46, 52, 53, 57, 58, 61, 64, 67, 73, 79, 81, 89, 97, 101, 103, 127, 134, 149, 151, 152, 197, 251, 277, 307\\ 36 & 41, 49, 85, 181, 289, 325\\ 37 & 38, 39, 40, 41, 43, 44, 47, 48, 50, 51, 53, 55, 56, 58, 59, 61, 62, 63, 65, 67, 68, 71, 73, 79, 82, 87, 88, 89, 93, 95,\\ &103, 107, 113, 115, 117, 118, 128, 133, 137, 145, 152, 158, 161, 163, 167, 170, 172, 173, 187, 211, 233, 253, 271,\\ &287, 301, 313, 323, 331, 337, 341, 343\\ 38 & 39, 43, 47, 49, 53, 55, 61, 67, 73, 77, 83, 107, 115, 123, 137, 193, 241, 281, 313, 337, 353\\ 39 & 41, 46, 49, 53, 56, 59, 61, 77, 85, 94, 101, 109, 137, 164, 191, 199, 271, 361, 379\\ 40 & 41, 47, 51, 53, 59, 71, 77, 79, 103, 131, 257, 301, 337, 397, 401\\ 41 & 43, 44, 46, 47, 49, 50, 51, 52, 54, 55, 58, 59, 61, 63, 64, 67, 69, 70, 71, 73, 74, 75, 76, 79, 83, 85, 89, 91, 92, 95,\\ &99, 104, 106, 107, 109, 113, 115, 119, 121, 129, 133, 134, 139, 141, 143, 146, 149, 157, 167, 176, 181, 184, 191,\\ &197, 202, 206, 209, 211, 212, 239, 265, 289, 311, 331, 349, 365, 379, 391, 401, 409, 415, 419, 421 \\ 42 & 43, 53, 361, 433\\ \hline \end{array}\)