非负整数矩阵的不可分解性
我正在寻找一个算法来测试一个非负的dxd整数矩阵是否是不可分解的。如果一个矩阵不能写成两个非负的dxd整数矩阵的乘积，则称为不可分解的矩阵，它们中没有一个是置换矩阵(即非负整数矩阵SL_d(N)的半环不可可逆)。我最感兴趣的是行列式为1的3x3矩阵。注意，1x1矩阵的情况对应于问一个正整数是否是素数。对于行列式为1的2x2矩阵，众所周知，唯一不可分解的矩阵是置换矩阵和初等矩阵(这是因为初等矩阵生成整个SL_2(N))。SL_3(N)中的不可分解矩阵有很多已知的例子(J. Rivat第3维不可分解矩阵“Pytheas中的替换，算法和组合中的替换”，Springer )。
有一个朴素的算法，它包含了一个更一般的分解形式BC =A与B，a，d，k矩阵和C，a，k，d矩阵。这样我们就可以开始递归构造了。我们用B0填充B的第一列，用C0填充C的第一行，使得B0 * C0 <= A(这里的意思是所有系数都较小)。然后求出B‘和C’的大小分别为d (k-1)和(k-1) x，使得B‘* C’=A-B0*C0。这个算法比较慢！
与此问题相关的方程是二次型的，变量为2d^2(A为d^2，B为d^2 )，我想用非负整数来求解它们。由于方程是非常特殊的形式，我想可能有更好的方法来解决它们，或者至少使递归构造更有效。
回答 1
Stack Overflow用户
发布于 2013-09-05 08:28:38
好的，我试着写问题，因为我看到它：
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或as B=M*inverse(A)导出B。
如果至少有单个Ai >1，则M是可分解的。
你也可以得到B作为GCD和衍生的A从M，B，.
仅此而已，希望能帮上忙..。
https://stackoverflow.com/questions/17629733
复制相似问题
腾讯云开发者
