Atoms in the Semigroup of Non-Negative Integer Matrices

技术摘要：非负整数矩阵半群中的原子

问题陈述
本文研究了由具有非负整数条目的 $2 \times 2$ 矩阵组成的半群 $M_2(\mathbb{N}_0)^\bullet$ 的分解性质。虽然在非交换设置中，唯一分解的概念通常并不成立，但本文的主要焦点在于识别该半群中的“原子”（不可约元素）。一个元素被称为原子，是指它不能被分解为两个非单位元的乘积。尽管 Baeth 等人 (2022) 已经确定了几类基本的原子类，但完整的分类仍然未知，且该半群中大多数矩阵的可分解性尚未确定。

方法论
作者结合理论分析与计算验证来识别新的原子类。其方法论依赖于以下结构性质和技术：

1. 结构约束： 研究重点关注“双平衡”（即没有行或列占主导地位）且相邻条目互质的矩阵。先前的研究表明，未列入已知类别的原子必须满足这些条件。
2. 行列式分析： 作者根据最小条目推导出了可分解矩阵的行列式下界。通过分析行列式的乘法性质，他们确定了特定的行列式值（例如，对于素数 $p$，值为 $p, 2p, 4p$，以及 $16, 32$），这些值排除了双平衡矩阵的可分解性。
3. 除封闭子集： 一个重要的研究步骤是将搜索范围限制在双对称矩阵（$X = \begin{pmatrix} x & y \\ y & x \end{pmatrix}$）且条目互质的子集 $B^*$ 中。作者证明了 $B^*$ 是 $M_2(\mathbb{N}_0)^\bullet$ 的一个除封闭子集。这意味着，如果 $B^*$ 中的一个矩阵可以分解，那么其因子也必须属于 $B^*$。这种简化显著缩小了分解搜索空间。
4. 边界不等式： 作者推导出了可分解矩阵条目的上界。具体而言，对于可分解矩阵 $X = \begin{pmatrix} w & x \\ y & z \end{pmatrix}$，其非对角线条目受限于对角线条目的函数。违反这些边界是判定一个矩阵为原子的充分条件。
5. 算法搜索： 利用 $B^*$ 的除封闭性质，作者开发了一个因子搜索算法。该算法并非搜索所有可能的 $2 \times 2$ 因子矩阵，而是通过固定最小条目并对对角线元素进行划分来优化搜索过程，将计算复杂度降低到三个变量。

核心贡献与结果

• 通过行列式识别的新原子类： 作者根据行列式值确定了两类新的原子。

  • 定理 4.3： 若一个双平衡矩阵且相邻条目互质，当其行列式为 $p, 2p$ 或 $4p$（其中 $p$ 为素数）时，该矩阵是一个原子。
  • 定理 4.4： 若此类矩阵的行列式为 $16$或$32$，则也是一个原子。
  • 这些结果是通过证明此类类型的可分解矩阵会导致其因子行列式违反已建立的下界（具体而言，即因子行列式不能为 $1, 2$或$4$）而得出的。

• 通过条目边界识别的新原子类：

  • 定理 6.2： 对于满足 $w \le z < x, y$ 的双平衡矩阵 $X = \begin{pmatrix} w & x \\ y & z \end{pmatrix}$，若 $x > 2(z-1)(w-1)$ 或 $y > 2(z-1)(w-1)$，则 $X$ 是一个原子。
  • 定理 6.4： 对于双对称矩阵 $X = \begin{pmatrix} x & y \\ y & x \end{pmatrix} \in B^*$，若 $\max\{x, y\} > 1 + \frac{(\min\{x, y\})^2}{4}$，则 $X$ 是一个原子。

• 双对称矩阵的除封闭性质：

  • 定理 5.1： 子集 $B^*$（具有互质相邻条目的双对称矩阵）在 $M_2(\mathbb{N}_0)^\bullet$ 中是除封闭的。这意味着 $B^*$ 中任何矩阵的分解都必须完全由 $B^*$ 中的矩阵组成。这一结果使得作者可以将搜索范围限制在双对称形式内，从而极大地简化了分类问题。

• 计算分类：

  • 利用除封闭性质和推导出的边界，作者实现了一种算法，用于对 $M_2(\mathbb{N}_0)^\bullet$ 中最小条目不超过 $4000$ 的所有双对称原子进行分类。
  • 定理 7.1： 对于 $B^*$ 中的矩阵，若其 $\min\{x, y\} \le 4000$，则当且仅当它们（及其伴随元）未出现在作者生成的候选可分解矩阵列表中时，它们是原子。论文提供了最小条目在 $42$以下的矩阵列表，并引用了涵盖至$4000$ 范围的完整数据集。

意义
本文声称通过扩大 $M_2(\mathbb{N}_0)^\bullet$ 中已知原子目录的规模，推进了对矩阵半群中非唯一分解性的理解。通过确立特定的行列式值和条目大小比例可以保证不可约性，作者提供了无需穷举分解即可识别原子的具体准则。此外，关于具有互质条目的双对称矩阵构成除封闭子集的证明，是一个结构性结果，它降低了该特定类别的分解问题的复杂性。计算结果为最小条目达 $4000$ 的双对称矩阵提供了完整的分类，填补了文献中大多数可分解性问题仍悬而未决的空白。这项工作还将矩阵分解与“复谐整数”（split-complex numbers）理论联系起来，证实了某些类别的不可约复谐整数对应于该半群中的原子矩阵。