3

非負の dxd 整数行列が分解できないかどうかをテストするアルゴリズムを探しています。私はマトリックスを非分解性と呼んでいます2 つの非負の dxd 整数行列の積として記述できない場合、置換行列ではありません (つまり、非負の整数行列 SL_d(N) の半環で可逆ではありません)。私は主に、行列式 1 を持つ 3x3 行列の場合に関心があります。1x1 行列の場合は、正の整数が素数であるかどうかを尋ねることに対応していることに注意してください。行列式 1 を持つ 2x2 行列の場合、分解できない行列は順列行列と基本行列だけであることがよく知られています (これは、基本行列が SL_2(N) 全体を生成するためです)。SL_3(N) には分解不可能な行列の例が無数に知られています (J. Rivat "Undecomposable matrixs in dimension 3" appendix in Pytheas Fogg "Substitutions in Dynamics, Arithmetics and Combinatorics", Springer LNM)。

B adxk 行列と C akxd 行列を使用して BC = A の形式のより一般的な因数分解を調べる単純なアルゴリズムがあります。そうすれば、再帰的な構築を開始できます。B の最初の列を B0 で埋め、C の最初の行を C0 で埋めて、B0 * C0 <= A となるようにします (ここでは、すべての係数が小さいことを意味します)。次に、B' * C' = A - B0*C0 となるようなサイズがそれぞれ dx (k-1) および (k-1) xd の B' および C' を見つければ十分です。このアルゴリズムは比較的遅いです!

問題に関連する方程式は、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 に答える