Grobner基理論及其應(yīng)用

《Grobner基理論及其應(yīng)用》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、Grobner基理論及其應(yīng)用摘要:本文介紹了運(yùn)用Grobner基求整系數(shù)線性方程組的非負(fù)整數(shù)解的算法,并給出了一些求解Frobenius問題的例子.另外,本文還簡要介紹了Hilbert基及其在求整系數(shù)線性方程組的非負(fù)整數(shù)解上的應(yīng)用.最后,本文研究了源于符號動力系統(tǒng)理論的判斷兩個非負(fù)整數(shù)矩陣是否步轉(zhuǎn)移等價問題,給出了算法及例子.關(guān)鍵詞:Grobner基;非負(fù)整數(shù)解;Hilbert基;轉(zhuǎn)移等價Abstract:Inthispaper,weintroduceanalgorithmforcomputingthenon-neg

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

3、problemofdeterminingwhetherthereisashiftequivalenceoflagfromonenonnegativematrixtoanother,whicharisesfromthetheoryofsymbolicdynamicalsystems,andpresentanalgorithmandsomeexamples.Keywords:Grobnerbasesnon-negativeintegersolutionHilbertbasesshiftequivalence引言對于環(huán)中理

4、想的刻畫是十分困難的,然而在實(shí)際中有大量問題都要求我們能夠?qū)Νh(huán)中理想有進(jìn)一步的刻畫,不只單純回答與存在性相關(guān)的問題,更重要的是能夠具體求解.Grobner基理論的本質(zhì)是從多變元多項式環(huán)中任一理想的一組生成元出發(fā),刻化和計算出一組具有"好的"性質(zhì)的生成元,而具有"好的"性質(zhì)的生成元,可幫助我們研究理想的結(jié)構(gòu)和進(jìn)行某些理想運(yùn)算.求整系數(shù)方程組的非負(fù)整數(shù)解2.1求整系數(shù)方程組的非負(fù)整數(shù)解對于,,,,其中是整數(shù)環(huán),求下列方程組(2-1)的解,其中是非負(fù)整數(shù)集合.為了使用Grobner基解這個問題,首先將它轉(zhuǎn)換成多項式問題,然

5、后用Grobner基的技巧解決相應(yīng)的問題,最后再將多項式問題的解轉(zhuǎn)換成方程組求解問題的解.分二步來求解.(1)設(shè)和,,都是非負(fù)整數(shù).判斷方程組(2-1)是否有解,如果有解則求出一個解.首先,我們引進(jìn)變元,并且考慮方程組,將這個式子的左邊和右邊分別相乘,我們得到(2-2)令是域上個變元的多項式環(huán).考慮映射它由給出.于是方程組(2-1)有解當(dāng)且僅當(dāng)冪積是環(huán)中某個冪積的象.如果,則是方程組(2-1)的一個解.引理2.1.1使用上邊的記號.設(shè)所有的和都是非負(fù)整數(shù).如果是的一個象,則它是環(huán)中某個冪積的象.現(xiàn)在我們給出判斷(2-

6、1)在條件(1)之下是否有解,如果有解,給出求解的算法[1].(i)計算環(huán)中的理想的相對變元大于變元的消元序的Grobner基.(ii)計算冪積模的余多項式.(iii)如果,則方程組(2-1)沒有非負(fù)整數(shù)解.如果,則是方程組(2-1)的非負(fù)整數(shù)解.(2)設(shè)和,,,是整數(shù)(不一定是非負(fù)的).判斷方程組(2-1)是否有解,如果有解則求出一個解.首先需要處理負(fù)冪次.令是一個新的變元,是環(huán)中的理想.對于任何,,存在非負(fù)整數(shù)和,使得.由于于是類似地,其中和都是非負(fù)整數(shù),并且由式(2-2),有(2-3)考慮代數(shù)同態(tài)則方程組(2-

7、1)有解當(dāng)且僅當(dāng)是環(huán)中冪積在之下的象.而且,如果,則是方程組(2-1)的整數(shù)解.與第一種情況相同,需要引理.引理2.1.2使用上邊的符號,如果是之下的象,則它是環(huán)中某個冪積的象.現(xiàn)在我們給出判斷(2-1)在條件(2)之下是否有解和如果有解,給出求解的算法[1].(i)計算環(huán)中的理想(2-4)的相對變元大于變元的消元序的Grobner基.(ii)計算冪積模的余多項式.(iii)如果,則方程組(2-1)沒有非負(fù)整數(shù)解.如果,,則是方程組(2-1)的非負(fù)整數(shù)解.2.2Frobenius問題考慮正整數(shù),并且.什么數(shù)可以用的和

8、來代替?換句話說,是否有正整數(shù),使得有非負(fù)整數(shù)解?其中.命題2.2.1假設(shè)是自然數(shù).理想令是按的Grobner基.能被寫成的和當(dāng)且僅當(dāng)模的余項是的形式.于是[2].這個命題是2.1中第(1)種情況的特例.將上述算法用Maple10.0編程實(shí)現(xiàn),對于一些簡單的Froubenius問題進(jìn)行求解,下面給出兩個例子:1.用Maple計算,得到.2.計算