我正在寻找一种算法,用于测试一个非负的dxd整数矩阵是否是不可分解的。如果一个矩阵无法被写成两个非负的dxd整数矩阵的乘积,其中没有一个是排列矩阵(即在非负整数矩阵半环SL_d(N)中不可逆),那么我称它为不可分解的。我主要关注行列式为1的3x3矩阵的情况。请注意,1x1矩阵的情况对应于询问正整数是否为质数。对于行列式为1的2x2矩阵,已知的唯一的不可分解矩阵是排列矩阵和初等矩阵(这是因为初等矩阵生成了整个SL_2(N))。在SL_3(N)中有无数个已知的不可分解矩阵(J. Rivat“Undecomposable matrices in dimension 3”在Pytheas Fogg的“Substitutions in Dynamics,Arithmetics and Combinatorics”,Springer LNM附录中有介绍)。
有一个朴素的算法,它包括查看形式为BC = A的更一般的分解,其中B是一个d x k矩阵,而C是一个k x d矩阵。这样我们可以开始递归构造。我们通过B0填充B的第一列,并通过C0填充C的第一行,以使B0 * C0 <= A(这里我指所有系数都更小)。然后只需要找到B'和C',它们分别是d x(k-1)和(k-1)x d的大小,使得B' * C' = A - B0 * C0。这个算法相对较慢!
与问题相关的方程式是二次的,有2 d ^ 2个变量(d ^ 2用于A,d ^ 2用于B),而我想用非负整数来解决它们。由于方程式具有非常特殊的形式,我猜测可能有更好的方法来解决它们,或者至少使递归构造更有效率。
有一个朴素的算法,它包括查看形式为BC = A的更一般的分解,其中B是一个d x k矩阵,而C是一个k x d矩阵。这样我们可以开始递归构造。我们通过B0填充B的第一列,并通过C0填充C的第一行,以使B0 * C0 <= A(这里我指所有系数都更小)。然后只需要找到B'和C',它们分别是d x(k-1)和(k-1)x d的大小,使得B' * C' = A - B0 * C0。这个算法相对较慢!
与问题相关的方程式是二次的,有2 d ^ 2个变量(d ^ 2用于A,d ^ 2用于B),而我想用非负整数来解决它们。由于方程式具有非常特殊的形式,我猜测可能有更好的方法来解决它们,或者至少使递归构造更有效率。
d > 1
,您总是可以编写M = P*(P^(-1)*M)
,其中P
是非平凡置换矩阵,即每行和每列恰好有一个1
的矩阵,在其他地方为0
。置换矩阵的逆矩阵仍然是置换矩阵,因此,如果我没有误解您的要求,唯一不可分解的将是 1×1 素数矩阵。您可能还想排除置换矩阵。 - Daniel Fischer