Grobner基理论及其应用

《Grobner基理论及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Grobner基理论及其应用摘要:本文介绍了运用Grobner基求整系数线性方程组的非负整数解的算法,并给出了一些求解Frobenius问题的例子.另外,本文还简要介绍了Hilbert基及其在求整系数线性方程组的非负整数解上的应用.最后,本文研究了源于符号动力系统理论的判断两个非负整数矩阵是否步转移等价问题,给出了算法及例子.关键词:Grobner基;非负整数解;Hilbert基;转移等价Abstract:Inthispaper,weintroduceanalgorithmforcomputingthenon-neg

2、ativeintegersolutionstoalinearsystemofequationsoverintegers,andwealsosolvetheFrobeniusprobleminsomesimplecases.Inaddition,wealsobrieflyintroduceHilbertbasesanditsapplicationsincomputingthegeneralnonnegativesolutionstoalinearsystemoverintegers.Finally,westudythe

3、problemofdeterminingwhetherthereisashiftequivalenceoflagfromonenonnegativematrixtoanother,whicharisesfromthetheoryofsymbolicdynamicalsystems,andpresentanalgorithmandsomeexamples.Keywords:Grobnerbasesnon-negativeintegersolutionHilbertbasesshiftequivalence引言对于环中理

4、想的刻画是十分困难的,然而在实际中有大量问题都要求我们能够对环中理想有进一步的刻画,不只单纯回答与存在性相关的问题,更重要的是能够具体求解.Grobner基理论的本质是从多变元多项式环中任一理想的一组生成元出发,刻化和计算出一组具有"好的"性质的生成元,而具有"好的"性质的生成元,可帮助我们研究理想的结构和进行某些理想运算.求整系数方程组的非负整数解2.1求整系数方程组的非负整数解对于,,,,其中是整数环,求下列方程组(2-1)的解,其中是非负整数集合.为了使用Grobner基解这个问题,首先将它转换成多项式问题,然

5、后用Grobner基的技巧解决相应的问题,最后再将多项式问题的解转换成方程组求解问题的解.分二步来求解.(1)设和,,都是非负整数.判断方程组(2-1)是否有解,如果有解则求出一个解.首先,我们引进变元,并且考虑方程组,将这个式子的左边和右边分别相乘,我们得到(2-2)令是域上个变元的多项式环.考虑映射它由给出.于是方程组(2-1)有解当且仅当幂积是环中某个幂积的象.如果,则是方程组(2-1)的一个解.引理2.1.1使用上边的记号.设所有的和都是非负整数.如果是的一个象,则它是环中某个幂积的象.现在我们给出判断(2-

6、1)在条件(1)之下是否有解,如果有解,给出求解的算法[1].(i)计算环中的理想的相对变元大于变元的消元序的Grobner基.(ii)计算幂积模的余多项式.(iii)如果,则方程组(2-1)没有非负整数解.如果,则是方程组(2-1)的非负整数解.(2)设和,,,是整数(不一定是非负的).判断方程组(2-1)是否有解,如果有解则求出一个解.首先需要处理负幂次.令是一个新的变元,是环中的理想.对于任何,,存在非负整数和,使得.由于于是类似地,其中和都是非负整数,并且由式(2-2),有(2-3)考虑代数同态则方程组(2-

7、1)有解当且仅当是环中幂积在之下的象.而且,如果,则是方程组(2-1)的整数解.与第一种情况相同,需要引理.引理2.1.2使用上边的符号,如果是之下的象,则它是环中某个幂积的象.现在我们给出判断(2-1)在条件(2)之下是否有解和如果有解,给出求解的算法[1].(i)计算环中的理想(2-4)的相对变元大于变元的消元序的Grobner基.(ii)计算幂积模的余多项式.(iii)如果,则方程组(2-1)没有非负整数解.如果,,则是方程组(2-1)的非负整数解.2.2Frobenius问题考虑正整数,并且.什么数可以用的和

8、来代替?换句话说,是否有正整数,使得有非负整数解?其中.命题2.2.1假设是自然数.理想令是按的Grobner基.能被写成的和当且仅当模的余项是的形式.于是[2].这个命题是2.1中第(1)种情况的特例.将上述算法用Maple10.0编程实现,对于一些简单的Froubenius问题进行求解,下面给出两个例子:1.用Maple计算,得到.2.计算