用史密斯标准形解线性刁番矩阵方程 终极改版

1、用史密斯标准形解线性刁番矩阵方程作者：卫云龙 指导教师：孙广人摘要：凭借一个改进的史密斯标准形矩阵，我们将为整数矩阵方程AX=B得到一个整数解而给出充分必要条件，并且我们将为此解给出一个标准的公式。我们还将提供一个代数式用于推导出此解，并且最后还要利用Maple软件演示出此解得产生过程。关键字：矩阵方程 线性结构 史密斯标准形 刁番图方程 整数解。1 引言 解一个整系数线性方程组拥有理论性与实践性的双重重要性，这是为什么这个课题不仅被教授给数学专业的学生，而且商务与工程还有其他专业也要开设此课程。找到了解就等同于解出了矩阵方程AX=B。矩阵B通常是一个单列向量，但也不是必须如此。当未知数表示的

2、事物体的数量时，这个解就必须是一个非负整数矩阵。因此，找到所有整数解得主要问题是本质的理论问题。本人的主旨就是要解决这个主要难题。因此我们将为整数矩阵方程AX=B得到整数解给出充分必要条件，其中A，B，X，并且我们会给出一个明确的公式用于推导出此解。例1. 下面矩阵A的每一个列向量中的元素给出的事品牌分别为J,K,L,M的越南大肚猪饲料分别所含有的纤维，蛋白质，和脂肪的含量。饲养员想要知道究竟每种品牌的饲料应该使用多少量才能满足如下面矩阵B所示雄猪与雌猪分别对纤维，蛋白质，脂肪的需求量。矩阵B的第一列向量代表的事雄猪营养的需求，第二列向量是雌猪的需求。 A= B= 这个问题就是要找出所有AX=

3、B的非负整数解。这个矩阵方程可以由高斯乔丹法求解，但在一个欠定方程组中如例1，拥有两组未知列向量，具体是否存在整数解是未知的，如果它存在又是什么解。读者也许希望试图用高斯乔丹法找到例1的所有整数解。而我们的解法，不仅类似于Lazebnik【4】，Newman【5】，Ward【8】给出精确的解，而且为解给出了简明的公式。2 一个旧定理和一个新定理 这个步骤基于一个来自于Jacobsom（见【3】P79）改进的定理，它源自于Smith【7】论文。定理1.如果A任意整数矩阵，则存在可逆整数矩阵P和Q，它们的逆矩阵也同样是整数矩阵，使得PAQ=D其中D是一个整数对角阵具有下列属性D=1.有是的因数，且

4、i<j。2.若0，则ir。矩阵D就是我们所知道的矩阵A的史密斯标准形了，现在回到我们的问题中，给我们的矩阵A和B各自行列为mn和mp,令P和Q如定理1所设。假设此刻r<m和r<n，我们过会再考虑其中之一或两个不等式都不成立的情况。定义 且有整数矩阵 如下,矩阵式矩阵PB前r行组成的，结果我们将得出下面结论。定理2，AX=B整数矩阵方程X的解有，当且仅当a) U=0,为零矩阵。b) -1是一个整数矩阵。则解为矩阵形式X=其中矩阵Z为（n-r）p。证明假设AX=B的解X为整数矩阵由定理1得,和.令其中由前r行组成。又记和X是整数矩阵，所以和也是整数矩阵。然后将DY=PB写成如下形

5、式又有U=0和,所以等价于,它必定是一个整数矩阵。我们于是有如下结论进而有 其中和为整数矩阵。同时假设U=0,因此X是一个整数矩阵，由定理1得注1：注意定理2即使非零元素在史密斯标准形中不能相互整除的情况下依然是有效的。3Jacobson的算法 Jacobson的算法就是把矩阵A左乘和右乘整数初等矩阵（可逆且逆矩阵也为整数矩阵），其等价于1）交换两行或两列。2）将其中一行或一列乘以-1。3)将任意一行或一列的整数倍加到另一行或列。我们建议读者参阅Jacobson算法的详细内容。当我们进行矩阵运算时，我们会用一个常数除以矩阵的某一行来改进它。其结果是我们可能除去了这一行的公因数。更值得注意的是，

6、这让我们得到了=1（i<r）的情况，所以定理中的矩阵，和矩阵变成了对角阵。结果P可能不必要是一个整数矩阵，介于P和Q有了这个性质，我们就有了下面推论。推论1.AX=B，X是整数矩阵当且仅当a） U=0，是零矩阵b） 是一个整数矩阵则方程解为形式为的所有矩阵，其中z为整数矩阵。 当推论条件a）和b）被满足则AX=B的所有整数解将由推论1（Z的元素都是整数）退出。在此例中，如果我们取矩阵为矩阵Q的前r列，矩阵为矩阵Q的后n-r列，则解X可以直接被写成,其中前一部分是原方程AX=B的特殊整数解。因为且P可逆，为同族方程的一个整数解。即，其中O的行列为。注2：注意推论1无论是否存在可逆矩阵P和Q

7、使得以及是整数矩阵推论1的结论都是正确的。4 其他情况我们现在回到以前我们忽略讨论的情况，读者可以自己证明下列结论。情况1：r=m=n.在此例中，不存在Z矩阵。推论1依然有效，但a）部分不再相关，b）部分的就是PB，c）部分简化成X=QPB。PAQ的行或列中的零矩阵将不会出现。情况2：r=m<n.在此例中，不存在U矩阵。推论1依然有效，但不存在a)部分，且在b）部分与c）部分中由PB替换。矩阵PAB中的行中没有零矩阵。情况3：r=n<m.在此例中，不存在Z矩阵。推论1依然有效，但c）部分简化为X=Q。矩阵PAB中的列将不存在零矩阵。5 改进算法 我们现在来表述Jacobson算法的

8、改进版本，而且我们将给出用新算法完成例1解答的全过程。 步骤1：由增广矩阵其中*为置空白步骤2：令K=1.步骤3：根据矩阵A的K行的元素对列向量进行重复的除法运算（如果K行的元素都是零，但下一行不是如此，则置换两行进行调整）。在每次运算中，当每一个元素与相对应于矩阵A的k行元素的最小非零数的元素做除法时，保留其余数。步骤4：继续步骤3，一直到产生出一个矩阵其中A的k行的每一个元素均为零，除了一个元素，即是这一行的最大公约数。步骤5：将增广矩阵的K行除以步骤4中所述的元素。步骤6：对矩阵A（包括其下面的矩阵）进行列交换，以产生一个此行中元素1在轴心位置上，而其他位置为0元素的一个矩阵。步骤7：利

9、用行变换将A矩阵K列的其它元素变换为0。步骤8：将K加1，并重复步骤3至步骤7.步骤9：继续步骤3至步骤8直到矩阵A被变换成如下形式其中在行中只有r<m时才会出现零矩阵，在列中只有r<n时才会出现零矩阵。行和列运算的次序等价于存在可逆矩阵P和Q且Q和都是整数矩阵。使得当将增广矩阵的一行除以此行中的最大公约数，这个数必须能被B原来行向量中的所有元素除尽。如果除不尽，则说明不存在整数解。在这种情况下B条件不被满足的列向量可以被除去，只需找到余下B的列向量的整数解。因为P是对应与行变换产生的矩阵，Q是对应于列变换产生的矩阵。增广矩阵在运算结束的时候将会表现出下面形式其中只有当r<m

10、时矩阵行里才会出现零矩阵，当r<n时矩阵列中才会出现零向量。现在马上就能清晰看出U是否是零矩阵，亦或者是否是一个整数矩阵。如果上述两种情况都未出现，则不存在整数解。如果条件都被满足了，整数解将可由推论中方程X的表达式精确求出。我们需要指出的是有很多种方法可以推导出上面的过程。由Jacobson得算法做出一个标准D矩阵然后再做除法将转换成或者将对角线元素变换成1都是没关系的。问题类似于是否该将行向量通过除以公因数进行简化一样无所谓。同样，人们可能在不同的正确运算步骤中，得到了不同的P与Q，却不用严格依照上述的运算程序，只要最终可将矩阵A变换成步骤9所示的形式就可以了。例1（进行正式求解）.

11、找出方程组AX=B的所有整数解。其中 和 我们做出增广矩阵由第一行开始。依据算法的步骤3，我们用矩阵列变换变换第一行的元素,.步骤4，我们将第一行其他元素变换为0，。步骤5就不用再做了，因为唯一剩下的第一行元素是1.继续步骤6，我们交换第1列和第2列。步骤7，我们进行列变换和从而得到此时无需继续严格的依照算法步骤，我们现在来变换第2行和第3行的数据，将第2行和第3行各自整除10和5.然后令K=2再为第二行做步骤3至步骤7的运算。首先做和，接着做和，最后再做和于是在第二行元素中就出现了1。完成步骤4只需做。步骤5可以省略（如果我们先前没有整除整行这个步骤就不能省略）。我们继续步骤6交换第一列和第

12、二列。步骤7只需.结果为现在和其中Z1，Z2 ，Z3 ，和Z4是任意整数 这个过程又是推导出的最后答案中的数字会不必要的大。不过这可以通过多种变换得到纠正。考虑第一个元素，因为12705/121059.于是我们可以将Z2 替换成- Z2-1059（Z2符号式为了使我们在寻找非负解时新的Z2为非负。同样的理由我们也将Z1替换成- Z1）。类似的，第二列的数字可以通过将Z4替换成- Z4-891而减小，并且我们将Z3替换成- Z3，从而Z3非负值。结果为Z即为方程组的整数解。正如我们推论后所提到的，此解也可以写成其中第一部分是原方程AX=B的特殊整数解，第二部分是Q2Z形式，其中Q2是同族方程的整

13、数解。 找到矩阵方程的所有整数解得主要问题我们已经解决了，而在实际应用中是要找出每种品牌饲料应该使用的分量，我们需要进一步求解出所有的非负整数解，这等同于去为整数规划问题找到可行区域。特别的，我们必须找到所有整数使得解矩阵X的所有元素都是非负的。在这种情况下，我们要求的解不难从构造的4个不等式中发现。第一个列向量有3组解：第一个是Z1=306，Z2=178从而我们计算出J、K、L、M品牌饲料的使用分量分别是3、26、16、0.其它两组解分别是Z1=308、Z2=179和Z1=310、Z2=180，从而求解出其相对应的饲料使用量分别是5、16、11、12和7、6、8、24。第二列向量有两组解Z3

14、=259，Z4=151和Z3=261，Z4=152，从而求解出各品牌饲料的各自使用量分别是4、14、10、9和6、4、5、21。6 使用maple软件 除了通过以上算法手算完成推论1中给出的方程解的形式，我们还可以利用Maple的命令找出一个矩阵的史密斯标准形，还有对应的P和Q矩阵，然后应用于定理2。利用例1中的A矩阵，命令如下（D,P,Q）:=SmithForm(A,method=integer,output=S,U,V)给出结果.(事实上，因为D是Maple软件的保留字符，必须使用其它名字代替。也要注意Maple给出的矩阵D不是方形的。)检验整数解是否存在，计算注意到D和PB都有两行非零行

15、，所以根据定理2，确定存在整数解，完整的解得表达式如下如前面一样，我们可以将Z2替换成-Z2-482，Z4替换成- Z4-406，结果为取值（Z1,Z2）=(3,2),(5,3)，（7，4）将为列向量1求出三组解（前面已给出）取值（Z3,Z4）=(4,3),(6,4)将为列向量求出两组解（前面已给出）7 其它问题 解线性刁番矩阵方程的问题已被Contejean and Devie【1】，Domenjoud【2】和Pottier【6】解决过，而且他们的方法也被其他人不断完善。而我们的方法是不同于他们的，因为他给出了解得明确表达式，而且它可以允许B包含多个列向量。 我们的方法，当然也适用于形如XA

16、=B的矩阵方程。因为这是等价于方程的，我们的方法也可以找出方程AX=B的所有整数解，其中A和B是拥有合理元素的矩阵。 一个我们所希望解决却又未能解决的问题：为这个解法会对这个体系产生什么样的影响给出一个直观上的回答。众所周知，高斯乔丹的行变换转换的解决方案，使他们的超平面平行于坐标轴。我们想在我们描述列向量变换过程中提出一个类似的见解，但我们却没有做到。我们在这里邀请其他此方面的学者前来探索这个问题。参考文献1E.Contejean and H.Devie,“An effcient incremental algorithm for solvingsystems of linear Dioph

17、antine equations," Information and Computation113 (1994) 143-172.2 E. Domenjoud, “Solving systems of linear Diophantine equations: an algebraic approach," Mathematical Foundations of Computer Science 1991,A. Tarlecki, ed., Vol. 520 of Lecture Notes in Computer Science, Springer,1991.3 N. J

18、acobson, Lectures in Abstract Algebra, Vol. 2: Linear Algebra, VanNostrand, 1953.4 F. Lazebnik, “On systems of linear Diophantine equations," The Mathe-matics Magazine 69 (1996) 261-266.5 M. Newman, Integral Matrices, Academic Press, 1972.6 L. Pottier, “Minimal solutions of linear diophantine systems: bounds and algorithms," Rewriting Techniques and Applications, R. V. Book, ed., Vol.488 of Lecture Notes in Computer Science, Springer, 1991.7 H. J. S. Smith, “On systems of linear indeterminate equations and con-gruences," Philosophical Transactions of the Royal Society of