algorithm - 非负整数矩阵的不可分解性

Question

我正在寻找一种算法来测试非负 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 a d x k 矩阵和 C a k x d 矩阵。这样我们就可以开始递归构造。我们用 B0 填充 B 的第一列，用 C0 填充 C 的第一行，这样 B0 * C0 <= A(这里我的意思是所有系数都较小)。然后找到大小分别为 d x (k-1) 和 (k-1) x d 的 B' 和 C'，使得 B' * C' = A - B0*C0 就足够了。这个算法比较慢!

与该问题相关的方程式是具有 2 个 d^2 变量的二次方程(A 为 d^2，B 为 d^2)，我想用非负整数求解它们。由于方程的形式非常特殊，我想可能有更好的方法来求解它们，或者至少可以使递归构造更有效。

Answer 1

好吧，我试着写下我看到的问题:

M = A x B

• M个已知非负整数输入矩阵NxN
• M的A,B未知输出分解，非单位，非负整数

矩阵乘法:

M[i][j] = sum(k=0,1,...,N-1)A[i][k]*B[k][j]

好的，为了清楚起见，现在让我写一个 3x3 的例子:

M[3][3]=A*B

  i  j    i  k    k  j    i  k    k  j    i  k    k  j
M[0][0]=A[0][0]*B[0][0]+A[0][1]*B[1][0]+A[0][2]*B[2][0]
M[0][1]=A[0][0]*B[0][1]+A[0][1]*B[1][1]+A[0][2]*B[2][1]
M[0][2]=A[0][0]*B[0][2]+A[0][1]*B[1][2]+A[0][2]*B[2][2]
M[1][0]=A[1][0]*B[0][0]+A[1][1]*B[1][0]+A[1][2]*B[2][0]
M[1][1]=A[1][0]*B[0][1]+A[1][1]*B[1][1]+A[1][2]*B[2][1]
M[1][2]=A[1][0]*B[0][2]+A[1][1]*B[1][2]+A[1][2]*B[2][2]
M[2][0]=A[2][0]*B[0][0]+A[2][1]*B[1][0]+A[2][2]*B[2][0]
M[2][1]=A[2][0]*B[0][1]+A[2][1]*B[1][1]+A[2][2]*B[2][1]
M[2][2]=A[2][0]*B[0][2]+A[2][1]*B[1][2]+A[2][2]*B[2][2]
// usage of B[i][j]
M[0][0]=A[0][0]*B[0][0]+...
M[1][0]=A[1][0]*B[0][0]+...
M[2][0]=A[2][0]*B[0][0]+...
M[?][j]=A[?][i]*B[i][j]+...
// usage of A[i][j]
M[0][0]=A[0][0]*B[0][0]+...
M[0][1]=A[0][0]*B[0][1]+...
M[0][2]=A[0][0]*B[0][2]+...
M[i][?]=A[i][j]*B[j][?]+...

当您仔细观察时，解决方案非常简单。找到所有:

A[i][j]=GCD(M[i][0],...,M[i][N-1])

然后从 M,A 或 B=M*inverse(A) 导出 B

如果至少有一个 A[i][j] > 1，则 M 是可分解的

您还可以将 B 作为 GCD 并从 M,B,... 导出 A

就这些，希望对你有帮助