Atoms in the Semigroup of Non-Negative Integer Matrices

Technical Summary: Atoms in the Semigroup of Non-Negative Integer Matrices

Problem Statement
This paper investigates the factorization properties of the semigroup $M_2(\mathbb{N}_0)^\bullet$, consisting of $2 \times 2$ matrices with non-negative integer entries and non-zero determinants. While the concept of unique factorization does not generally hold in non-commutative settings, the primary focus is on identifying "atoms" (irreducible elements) within this semigroup. An element is an atom if it cannot be factored into a product of two non-unit elements. Although Baeth et al. (2022) established several fundamental classes of atoms in $M_2(\mathbb{N}_0)^\bullet$, a complete classification remains unknown, and the factorability of the majority of matrices in this semigroup is undetermined.

Methodology
The authors employ a combination of theoretical analysis and computational verification to identify new classes of atoms. The methodology relies on the following structural properties and techniques:

1. Structural Constraints: The study focuses on "doubly-balanced" matrices (where no row or column is dominant) with relatively prime adjacent entries. Previous results indicate that atoms not listed in known classes must satisfy these conditions.
2. Determinant Analysis: The authors derive lower bounds on the determinant of factorable matrices based on their minimum entry. By analyzing the multiplicative properties of determinants, they identify specific determinant values (e.g., $p, 2p, 4p$ for prime $p$, and $16, 32$) that preclude factorization for doubly-balanced matrices.
3. Divisor-Closed Subsets: A significant methodological step involves restricting the search to the subset of bisymmetric matrices ($X = \begin{pmatrix} x & y \\ y & x \end{pmatrix}$) with relatively prime entries, denoted as $B^*$. The authors prove that $B^*$ is a divisor-closed subset of $M_2(\mathbb{N}_0)^\bullet$. This implies that if a matrix in $B^*$ factors, its factors must also lie within $B^*$. This reduction simplifies the factorization search space significantly.
4. Bounding Inequalities: The paper derives upper bounds on the entries of factorable matrices. Specifically, for a factorable matrix $X = \begin{pmatrix} w & x \\ y & z \end{pmatrix}$, the off-diagonal entries are bounded by functions of the diagonal entries. Violations of these bounds serve as a sufficient condition for a matrix to be an atom.
5. Algorithmic Search: Leveraging the divisor-closed property of $B^*$, the authors developed a factor search algorithm. Instead of searching all possible $2 \times 2$ factor matrices, the algorithm optimizes the search by fixing the minimum entry and partitioning the diagonal elements, reducing the computational complexity to three variables.

Key Contributions and Results

• New Classes of Atoms via Determinants: The authors identify two new classes of atoms based on determinant values.

  • Theorem 4.3: A doubly-balanced matrix with relatively prime adjacent entries is an atom if its determinant is $p$, $2p$, or $4p$ (where $p$ is prime).
  • Theorem 4.4: Such a matrix is also an atom if its determinant is $16$ or $32$.
  • These results are derived by showing that factorable matrices of these types would require factor determinants that violate established lower bounds (specifically, that factor determinants cannot be $1, 2,$ or $4$).

• New Classes of Atoms via Entry Bounds:

  • Theorem 6.2: For a doubly-balanced matrix $X = \begin{pmatrix} w & x \\ y & z \end{pmatrix}$ with $w \le z < x, y$, if $x > 2(z-1)(w-1)$ or $y > 2(z-1)(w-1)$, then $X$ is an atom.
  • Theorem 6.4: For bisymmetric matrices $X = \begin{pmatrix} x & y \\ y & x \end{pmatrix} \in B^*$, if $\max\{x, y\} > 1 + \frac{(\min\{x, y\})^2}{4}$, then $X$ is an atom.

• Divisor-Closed Property of Bisymmetric Matrices:

  • Theorem 5.1: The subset $B^*$ (bisymmetric matrices with relatively prime adjacent entries) is divisor-closed in $M_2(\mathbb{N}_0)^\bullet$. This means any factorization of a matrix in $B^*$ must consist entirely of matrices within $B^*$. This result allows the authors to restrict the search for factors to the bisymmetric form, greatly simplifying the classification problem.

• Computational Classification:

  • Using the divisor-closed property and the derived bounds, the authors implemented an algorithm to classify all bisymmetric atoms in $M_2(\mathbb{N}_0)^\bullet$ with a minimum entry up to $4000$.
  • Theorem 7.1: Matrices in $B^*$ with $\min\{x, y\} \le 4000$ are atoms if and only if they (and their associates) do not appear in the authors' generated list of factorable matrices. The paper provides this list for matrices with minimum entries up to $42$ and references the full dataset for the range up to $4000$.

Significance
The paper claims to advance the understanding of non-unique factorization in matrix semigroups by expanding the known catalog of atoms in $M_2(\mathbb{N}_0)^\bullet$. By establishing that specific determinant values and entry magnitude ratios guarantee irreducibility, the authors provide concrete criteria for identifying atoms without exhaustive factorization. Furthermore, the proof that bisymmetric matrices with relatively prime entries form a divisor-closed subset is a structural result that reduces the complexity of the factorization problem for this specific class. The computational results offer a complete classification for bisymmetric matrices up to a minimum entry of $4000$, filling a gap in the literature where most factorability questions remain open. The work also connects matrix factorization to the theory of "perplex integers" (split-complex numbers), confirming that certain classes of irreducible perplex integers correspond to atomic matrices in this semigroup.