Grobner基理论及其应用.doc

Grobner基理论及其应用摘要: 本文介绍了运用Grobner基求整系数线性方程组的非负整数解的算法,并给出了一些求解Frobenius问题的例子.另外,本文还简要介绍了Hilbert基及其在求整系数线性方程组的非负整数解上的应用.最后,本文研究了源于符号动力系统理论的判断两个非负整数矩阵是否步转移等价问题,给出了算法及例子. 关键词: Grobner基;非负整数解;Hilbert基;转移等价Abstract: In this paper, we introduce an algorithm for computing the non-negative integer solutions to a linear system of equations over integers, and we also solve the Frobenius problem in some simple cases. In addition, we also briefly introduce Hilbert bases and its applications in computing the general nonnegative solutions to a linear system over integers. Finally, we study the problem of determining whether there is a shift equivalence of lag from one nonnegative matrix to another, which arises from the theory of symbolic dynamical systems, and present an algorithm and some examples.Key words: Grobner bases non-negative integer solution Hilbert bases shift equivalence引言对于环中理想的刻画是十分困难的,然而在实际中有大量问题都要求我们能够对环中理想有进一步的刻画,不只单纯回答与存在性相关的问题,更重要的是能够具体求解.Grobner基理论的本质是从多变元多项式环中任一理想的一组生成元出发,刻化和计算出一组具有好的性质的生成元,而具有好的性质的生成元,可帮助我们研究理想的结构和进行某些理想运算.求整系数方程组的非负整数解2.1 求整系数方程组的非负整数解对于,其中是整数环,求下列方程组(2-1)的解,其中是非负整数集合.为了使用Grobner基解这个问题,首先将它转换成多项式问题,然后用Grobner基的技巧解决相应的问题,最后再将多项式问题的解转换成方程组求解问题的解.分二步来求解.(1)设和,都是非负整数.判断方程组(2-1)是否有解,如果有解则求出一个解.首先,我们引进变元,并且考虑方程组,将这个式子的左边和右边分别相乘,我们得到(2-2)令是域上个变元的多项式环.考虑映射它由给出.于是方程组(2-1)有解当且仅当幂积是环中某个幂积的象.如果,则是方程组(2-1)的一个解.引理2.1.1 使用上边的记号.设所有的和都是非负整数.如果是的一个象,则它是环中某个幂积的象.现在我们给出判断(2-1)在条件(1)之下是否有解,如果有解,给出求解的算法1.(i)计算环中的理想的相对变元大于变元的消元序的Grobner基.(ii)计算幂积模的余多项式.(iii)如果,则方程组(2-1)没有非负整数解.如果,则是方程组(2-1)的非负整数解.(2)设和,是整数(不一定是非负的).判断方程组(2-1)是否有解,如果有解则求出一个解.首先需要处理负幂次.令是一个新的变元,是环中的理想.对于任何,存在非负整数和,使得.由于于是类似地,其中和都是非负整数,并且由式(2-2),有(2-3)考虑代数同态则方程组(2-1)有解当且仅当是环中幂积在之下的象.而且,如果,则是方程组(2-1)的整数解.与第一种情况相同,需要引理.引理2.1.2 使用上边的符号,如果是之下的象,则它是环中某个幂积的象.现在我们给出判断(2-1)在条件(2)之下是否有解和如果有解,给出求解的算法1.(i) 计算环中的理想(2-4)的相对变元大于变元的消元序的Grobner基.(ii) 计算幂积模的余多项式.(iii) 如果,则方程组(2-1)没有非负整数解.如果,则是方程组(2-1)的非负整数解.2.2 Frobenius问题考虑正整数,并且.什么数可以用的和来代替?换句话说,是否有正整数,使得有非负整数解?其中.命题2.2.1 假设是自然数.理想令是按的Grobner基.能被写成的和当且仅当模的余项是的形式.于是2.这个命题是2.1中第(1)种情况的特例.将上述算法用Maple10.0编程实现,对于一些简单的Froubenius问题进行求解,下面给出两个例子:1.用Maple计算,得到.2.计算,得到.2.3 Hilbert基Hilbert基是Grobner基的应用,是半群的最小生成元系.令是一个整数矩阵.令.是中一个含有零元的半群.那么是有限生成的.定义2.3.1 是一个顶点,如果,包括或.我们用表示的顶点集合.注记2.3.1 生成.注意是中在的自然半序下的最小的非空集合:.这说明是这个系统的Hilbert基.若,则若,;若如果,.我们称的顶点为中的元素.引理2.3.1(Dickson引理)设,令3那么.Dickson引理可推出是有限的.算法2.3.1 用半群理想求非负整数特解3.输入:方程组,其中是整数矩阵,.输出:如果存在,使得,输出向量.如果不存在使得,输出.1.如果取表示由的列向量生成的中子半群;计算的生成元集;如果存在二项式,输出,终止;否则,输出,终止.2.如果取表示由的列向量和生成的中子半群;计算的生成元集;如果存在二项式,其中不包括变元,输出,终止.否则,继续;如果不存在二项式,输出,终止.否则,选取一个以最后一个变元优先的项序,计算的Grobner基,;如果存在二项式,其中不包括变元,输出,终止;否则,输出,终止.下面给出满足命题2.3.1的算法.算法2.3.2 利用半群理想求顶点3.输入:方程组,其中是整数矩阵,.输出:,其中.1.如果,通过2.3.2求出并终止.2.如果,利用算法2.3.1,确定是否或.3.如果或,输入,终止.4.否则,取.5.对于,利用算法2.3.2递推算出.6.计算的.7.输出.若干类方程组求解3.1 某一类整系数齐次方程组求解假设、分别为阶和阶非负整数方阵,求满足矩阵方程的非负整数矩阵的一般表达式.设,则可写为按每一行展开,得到等价的另一种形式的方程组,共个方程.对该方程组进行化简,对每一个方程,把,(,)看成变元,合并同类项,得到如下形式的方程组(3-1)其中为上述化简得到的方阵.上述运算可通过软件Maple10.0实现.首先需要处理负幂次.为下文的描述更清晰,令令是一个新变元,是环中的理想.对于任何,存在非负整数和,使得由于于是由于,有(3-2)令考虑代数同态.则方程组(3-1)有解当且仅当是环中幂积在之下的象,而且,如果,则是方程组(3-1)的整数解.现在给出算法,判断(3-1)是否有解及在有解的情况下如何求解.(i) 计算环中的理想(3-3)的相对变元大于变元的消元序的Grobner基.(ii) 计算模的余多项式.(iii) 如果,则方程组(3-1)没有非负整数解.如果,则是方程组(3-1)的非负整数解.在编程过程中,使用Hilbert基软件包,直接求出形如(3-1)的整系数方程组的非负整数解的生成元,设为.则的非负整数解可写为:,其中为非负整数.现给出一个用软件实现的例子及结果:求的非负整数解,得到解的生成元为,于是,所有的非负整数解为,其中.3.2 某一类整系数齐次方程组求解假设为阶整数阵,为阶整数阵,求解整系数方程组(3-4)的非负整数解.按照2.1可求出(3-4)的非负整数解,但是对于某一给定的项序,至多只能求出一个特解,若想遍历所有的解,往往需要给出所有可能的项序排列,这样是一个极为耗时的做法,而且在用电脑实现的过程中,往往也加重了运算的负担,所以给出下面的一种解法.将转化成等价的形式(3-5)考虑矩阵方程组(3-6)利用Hilbert基软件包求出(3-6)的解的生成元.设有如下形式其中,且,为指标集.下面的命题给出解的一般表达形式.命题3.2.1 有非负整数解的充分必要条件是存在,使得,其中为非负整数.证明:充分性.,即为();,即为().则对,有.所以为的解.必要性.设为(3-4)的解,则必有,即有.而由于,即为和,即为.所以.用Hilbert软件包求得集合是的非负整数解的Hilbert基,易知是的解的Hilbert基.所以可由其线性表出,即存在,.证毕.现给出一个用软件实现的例子及结果:求的非负整数解.运算结果为:特解是,导出组的非负整数解的生成元为.所以该方程的通解为,其中.3.3 求解某一类矩阵方程组定义3.3.1 令和是非负整数矩阵.称到是一对非负整数矩阵的初等等价,如果满足和,记为:.称到是步强转移等价,是指存在一系列初等等价,记为(步).称是的强转移等价,如果存在,使得到步强转移等价.命题3.3.1 强转移等价是非负整数矩阵上的一个等价关系4.定义3.3.2 令和是非负整数矩阵,.称到是一对非负整数矩阵的步转移等价,如果满足,记为:.我们称是的转移等价,如果存在,使得是的步转移等价,记为.定理3.3.1 强转移等价是转移等价.更进一步,如果(步),那么(步)4.本节将研究在给定非负整数矩阵和正整数的情况下,判断到是否是步转移等价的算法,并给出了该算法的程序实现.判断到是否是步转移等价的,就等价于求矩阵方程组(3-7)的解,其中、分别为阶和阶非负整数方阵,为给定的一个正整数,、分别为阶和阶非负整数矩阵,若有解,则到是步转移等价的,若无解,则到不是步转移等价的.这是一个含有四个方程的方程组,在求解方程时,往往齐次的要比非齐次的方程更易求解,所以针对这一类方程,采取先求出(3-7)中的第一、二方程组的解,再从中选择满足第三、四方程组的解的办法.求解(3-7)中的第一、二方程组可归结于3.1,分别求出其非负整数解的极小生成元,设为,.则第一、二方程解组的非负整数解可分别表为,其中,为非负整数.于是(3-7)中的第三、四方程组转化为(3-8)现在的问题就转化为求(3-8)的非负整数解.即为(3-9)(3-10)其中.需要注意的,在及中,如果存在,对都有,则是无用的,它可以取任意值,于是我们称是自由的.同样地,如果存在,对都有,我们就称是自由的.对于自由的或,要将含它的项从中删掉,剩余就是不含自由项的.将看作一个整体进行求解,即求解(3-11)(3-12)其中.同3.2,分别求出(3-11),(3-12)的非负整数解的特解,再从中挑选出使(3-13)的秩为1的那些,然后比较,选出相同的生成元,这就是(3-7)的解.命题3.3.1 (3-11)中使(3-13)的秩为1的特解便是(3-9)的非负整数解.同样的,(3-12)中使(3-13)的秩为1的特解便是(3-10)的非负整数解.证明:只需对于(3-11)的情况证明便可.由(3-13)的秩为1,不妨设其中为既约分数,.若,由于中每个元素都是整数,所以,则,便是(3-9)的一组非负整数解.若,则其中,由中每个元素都是整数,知,必为整数,于是为的因子.这时,便是(3-9)的一组非负整数解.证毕.现给出一个用软件实现的例子及其运算结果:已知,对于某个给定的求的非负整数解是否存在,即求到经过多少步可以转移等价.通过上机实验得到,当时,均无解,时,得到解,及组成的矩阵或者.于是,取或就得到两组非负整数解或所以(3步).对已知求解时,发现在时均无解,但在时,运算了近2个小时,仍没有给出结果.由此可知,该算法可行,但效率不是很高,对于较大系数的方程组求解需要花费很长时间,有待改进.结论本文主要介绍了域上的Grobner基理论在求整系数方程组的非负整数解上的应用,并运用其中的理论,给出了一些求Frobeni