3

我正在寻找一种算法来测试非负 dxd 整数矩阵是否不可分解。我称矩阵不可分解如果它不能写成两个非负 dxd 整数矩阵的乘积，它们都不是置换矩阵（即在非负整数矩阵 SL_d(N) 的半环中不可逆）。我对行列式为 1 的 3x3 矩阵的情况最感兴趣。请注意，1x1 矩阵的情况对应于询问正整数是否为素数。对于行列式为 1 的 2x2 矩阵，众所周知，唯一不可分解的矩阵是置换矩阵和基本矩阵（这是因为基本矩阵生成整个 SL_2(N)）。在 SL_3(N) 中有无数个已知的不可分解矩阵的例子（J. Rivat “Undecomposable matrices in dimension 3” appendix in Pytheas Fogg “Substitutions in Dynamics, Arithmetics and Combinatorics”，Springer LNM）。

有一种简单的算法，它包括查看具有 B adxk 矩阵和 C akxd 矩阵的 BC = A 形式的更一般的因式分解。这样我们就可以开始递归构造了。我们用 B0 填充 B 的第一列，用 C0 填充 C 的第一行，这样 B0 * C0 <= A （这里我的意思是所有系数都更小）。然后找到大小分别为 dx (k-1) 和 (k-1) xd 的 B' 和 C' 就足够了，使得 B' * C' = A - B0*C0。这个算法比较慢！

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

4

1 回答 1

0

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

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

矩阵的乘法：

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

就这些了，希望对你有帮助...

于 2013-09-05T08:28:38.313 回答