4つの対角要素すべてがゼロの4x4行列があります。他のすべての要素は非負の整数です。4行4列すべての合計は個別にわかります。行列の残りの12要素を決定することは可能ですか？例えば
0 1 1 0 sum=2
2 0 0 1 sum=3
4 1 0 0 sum=5
0 1 6 0 sum=7
sum=6 sum=3 sum=7 sum=1
どんなガイダンスも非常に役に立ちます。ありがとう
行列は
0 12 13 14 _ _
21 0 23 24 _ _
31 32 0 34 _ _
41 42 43 0 _ _ _
問題は一連の線形方程式を解くことです:
a 12 + a 13 + a 14 = c 1
a 21 + a 23 + a 24 = c 2
等々。12 個の変数と 8 個の方程式 (行に 4 つ、列に 4 つ) があります。12 変数の線形方程式系を解くには、通常 12 個の方程式が必要です。方程式の数が少ないため、システムには一意の解がありません。無限に多くの解があるかもしれません。
行列は
0 12 13 14 _ _
21 0 23 24 _ _
31 32 0 34 _ _
41 42 43 0 _ _ _
問題は一連の線形方程式を解くことです:
12 + 13 + 14 = r 1
a 21 + a 23 + a 24 = r 2
31 + 32 + 34 = r 3
41 + 43 + 44 = r 4
a 21 + a 31 + a 41 = c 1
a 12 + a 32 + a 42 = c 2
a 13 + a 23 + a 43 = c 3
a 14 + a 34 + a 44 = c 4
したがって、0 と 1 の係数のみで構成される A を使用して、Ax = b の形式の方程式を解く必要があります。ガウス消去法とユークリッド アルゴリズムを使用して、D が対角形式で SDT = A となるような整数行列 S、D、T を見つけます。方法がわからない場合は、ウェブでスミス標準形アルゴリズムを検索してください。
それで
SDTx = Ax = b
したがって
DTx = S -1 Ax = S -1 b
D は対角形式なので、解けるかどうかを確認できます
Dy = S -1 b
Yについて。また、(同種の) 解空間のベースも見つかります。次に、これを使用して、元の方程式の正の解を探す際の複雑さを軽減できます。