logo标签列表

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

algorithmmatrix
3
我正在寻找一种算法，用于测试一个非负的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），而我想用非负整数来解决它们。由于方程式具有非常特殊的形式，我猜测可能有更好的方法来解决它们，或者至少使递归构造更有效率。
2
你能把你的问题更加正式化一些吗？对于给定的矩阵M，你想知道是否存在矩阵A和B，使得M = A x B？总是存在一个平凡解A = Identity，B = M，因此没有矩阵是不可分解的... - catchmeifyoutry
@catchmeifyoutry 对的！我的意思是非平凡解（就像你为整数分解所做的那样）。谢谢。 - V. Delecroix
2
对于 d > 1，您总是可以编写 M = P*(P^(-1)*M)，其中 P 是非平凡置换矩阵，即每行和每列恰好有一个 1 的矩阵，在其他地方为 0。置换矩阵的逆矩阵仍然是置换矩阵，因此，如果我没有误解您的要求，唯一不可分解的将是 1×1 素数矩阵。您可能还想排除置换矩阵。 - Daniel Fischer
@DanielFischer：你是正确的！ - V. Delecroix
1
我建议你在mathoverflow上发布这个问题。同时，请明确你是否想要一个因式分解（如果存在），或者你只是想知道矩阵是否不可分解的答案。对于1x1，可以在多项式时间内进行素性测试（使用一些相当重的数论，因此你的问题可以说是一个数学问题），但实际上产生非质数的因式分解被认为是困难的（可能是NP完全的，或者介于NP完全和P之间）。另外，如果你愿意假设矩阵条目的界限（以加快计算速度），也请说明。 - user2566092
显示剩余6条评论
1个回答
0

好的，我尝试根据我的理解来描述这个问题：

M = A x B
  • 给定一个非负整数矩阵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，或者将B推导为B=M*inverse(A)

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

同时你也可以从M，B等推导出A的最大公约数....

就这些，希望能有所帮助...

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接