管 濤 范興亞

(1.中國(guó)人民公安大學(xué)信息技術(shù)與網(wǎng)絡(luò)安全學(xué)院102600 2.北京市第四中學(xué)數(shù)學(xué)組 100037)

我們知道，利用矩陣可以求解斐波那契類型的遞推數(shù)列的通項(xiàng)公式. 事實(shí)上很多遞推問(wèn)題都可以利用矩陣解決. 我們來(lái)看下面這樣一個(gè)有趣的數(shù)學(xué)游戲：一個(gè)正方形，畫出它的中點(diǎn)正方形；再畫出新正方形的中點(diǎn)正方形，依此類推，會(huì)生成一個(gè)漂亮的圖案. 如果在原正方形的四個(gè)頂點(diǎn)處隨意各寫一個(gè)自然數(shù)，將相鄰頂點(diǎn)處的自然數(shù)相減(用較大的數(shù)減較小的數(shù)，若兩數(shù)相等，則差為0，稱這種運(yùn)算為相鄰做差運(yùn)算)，計(jì)算結(jié)果寫在每條邊的中點(diǎn)；依此類推.

例如：最先寫下2、12、15、8，運(yùn)算1次后得到10、3、7、6，運(yùn)算2次后得到7、4、1、4，運(yùn)算3次后得到3、3、3、3，運(yùn)算4次后得到0、0、0、0. 如下圖：

如果我們重復(fù)幾次這樣的游戲，就會(huì)發(fā)現(xiàn)不管開(kāi)始寫下什么數(shù)，似乎最后總會(huì)化為0. 因此可以猜想對(duì)于正方形進(jìn)行相鄰做差運(yùn)算，最終一定會(huì)化為四個(gè)數(shù)都是0的狀態(tài). 這一猜想是否正確？如果把正方形換成正n邊形，又會(huì)有什么樣的結(jié)論呢？

更一般的，我們可以借助向量序列的概念來(lái)描述這一問(wèn)題.

問(wèn)題1如下定義n維向量序列.α1=(a11,a12,…,a1n)中的元素都是自然數(shù)，當(dāng)i≥2時(shí)，向量αi=(ai1,ai2,…,ain)中的元素aij=|ai-1,j-ai-1,j+1|，其中規(guī)定ai-1,n+1=ai-1,1.在上述定義下，向量αi是否會(huì)收斂到零向量？

換句話說(shuō)，令max{ai1,ai2,…,ain}=Ai，數(shù)列{Ai}是否會(huì)在有限步之內(nèi)收斂到零？答案是否定的，但是我們可以得到如下的性質(zhì).

性質(zhì)1{Ai}極限一定存在，可設(shè)其為A，而且必定在有限步內(nèi)收斂到其極限值A(chǔ).

證明根據(jù)定義易知Ai≤Ai-1，也就是數(shù)列{Ai}單調(diào)減(非嚴(yán)格單調(diào)減)，又因?yàn)閧Ai}非負(fù)，根據(jù)單調(diào)有界準(zhǔn)則[1]，{Ai}必有極限值A(chǔ). 又因?yàn)槿我鈇ij都不大于A1，因此向量αi只有有限多種不同的形式，遲早會(huì)進(jìn)入周期循環(huán)狀態(tài)，那就是說(shuō){Ai}必定會(huì)在有限步之內(nèi)達(dá)到A并在之后保持恒定.即存在某個(gè)下標(biāo)k，當(dāng)i≥k時(shí)，Ai恒等于A. 證畢.

但是A并不一定等于零，它也有可能是一個(gè)正整數(shù). 例如當(dāng)n=3時(shí)，令α1=(a11,a12,a13)=(1,1,0)，那么α2=(a21,a22,a23)=(0,1,1)，可看作是(a11,a12,a13)中的元素做了一個(gè)3輪換，如果作為環(huán)排列寫在正三角形的三個(gè)頂點(diǎn)，則等同于(a11,a12,a13)，此后必然是一個(gè)周期為3的循環(huán)狀態(tài)，所以A=1. 那么很自然的會(huì)想到如下問(wèn)題.

問(wèn)題2當(dāng)n取何值時(shí)Ai必然收斂到零.

為解決問(wèn)題2，我們需要進(jìn)行較復(fù)雜的推理和分析. 我們已經(jīng)知道，存在下標(biāo)k，使得當(dāng)i≥k時(shí)Ai恒等于其下限也就是極限值A(chǔ). 接下來(lái)分析在此之后的向量αi中的元素可以取哪些自然數(shù)？

性質(zhì)2當(dāng)i≥k即Ai已經(jīng)達(dá)到其下極限A時(shí)，ai1,ai2,…,ain只能取0或A.

證明設(shè)當(dāng)i=k時(shí)，Ai已經(jīng)達(dá)到其下極限A. 那么在ak+n-1,1,ak+n-1,2,…,ak+n-1,n中存在至少一個(gè)元素等于A，不妨設(shè)ak+n-1,1=A. 逆推回去，ak+n-2,1和ak+n-2,2必然一個(gè)是0一個(gè)是A，再繼續(xù)逆推，ak+n-3,1、ak+n-3,2和ak+n-3,3也必須都取值0或A，并且至少有一個(gè)是A. 依此類推，ak1,ak2,…,akn全都要取0或A，因此對(duì)所有的i≥k以及有意義的j，aij都等于0或A. 證畢.

假定A為正數(shù)，那么不妨設(shè)A=1. 為解決問(wèn)題2，我們只需對(duì)n維的0-1向量進(jìn)行討論，搞清楚當(dāng)n取何值時(shí)，任意0-1向量一定會(huì)在有限步內(nèi)化為零向量.

由于向量中的元素只取0和1，問(wèn)題1中的遞推公式也可以等價(jià)的描述為問(wèn)題3.

問(wèn)題3如下構(gòu)造定義在2元域F2={0,1}[2]上的n維向量序列.首先任給α1=(a11,a12,…,a1n)，當(dāng)i≥2時(shí)，令向量αi=(ai1,ai2,…,ain)中的元素aij=ai-1,j+ai-1,j+1，其中規(guī)定ai-1,n+1=ai-1,1. 當(dāng)維數(shù)n取何值時(shí)，一定存在某個(gè)下標(biāo)k使得αk=0.

問(wèn)題3也可以用2元域F2上的矩陣進(jìn)行表述，設(shè)n階方陣

首先給出一個(gè)引理.

證略. 讀者可自行閱讀參考文獻(xiàn)[3]中75頁(yè)習(xí)題31的解答.

借助引理1能得到下述結(jié)論.

定理1當(dāng)n=2m時(shí)，A作為2元域F2上的矩陣是冪零的，An=0.

所有元素均為偶數(shù)，因此在A是2元域F2上的冪零矩陣. 證畢.

由定理1容易推出，當(dāng)n=2m時(shí)，按上述定義的任意n維0-1向量，至多經(jīng)過(guò)n次相鄰做差運(yùn)算就可以得到零向量. 再進(jìn)一步得到下面的性質(zhì)3.

性質(zhì)3當(dāng)n=2m時(shí)，在正n邊形的每個(gè)頂點(diǎn)上隨意寫一個(gè)整數(shù)，進(jìn)行相鄰做差運(yùn)算，經(jīng)過(guò)有限步后一定會(huì)化為都是0的形式. 文章最初正方形的問(wèn)題作為性質(zhì)3的一個(gè)特例也隨之解決.

為了考慮n不是2的冪時(shí)的情況，我們需要借助Hamilton-Cayley定理.

引理2(Hamilton-Cayley定理)數(shù)域F上，方陣的特征多項(xiàng)式一定是零化多項(xiàng)式.

證略.

在F2中考慮A的特征多項(xiàng)式f(λ)=|λI-A|=(λ-1)n+(-1)n-1. 當(dāng)n=2m時(shí)，特征多項(xiàng)式可化為λn，由此也可得到前面定理1的結(jié)論. 當(dāng)n不是2的冪時(shí)，在f(λ)=(λ-1)n+(-1)n-1是一個(gè)至少含有兩項(xiàng)的n次多項(xiàng)式，并且其常數(shù)項(xiàng)為0.

定理2當(dāng)n不是2的冪時(shí)，A作為2元域F2上的矩陣不是冪零的.

證明在F2中考慮矩陣B的特征多項(xiàng)式g(λ)=|λI-B|=λn+(-1)n-1=λn+1，由引理2可知g(B)=0. 而對(duì)于任意次數(shù)小于n的m次多項(xiàng)式h(λ)，h(B)中第1行第m+1列的元素非零，因此g(λ)也是矩陣B的極小多項(xiàng)式.

下面考慮矩陣A的極小多項(xiàng)式，由于B=A-I，因此A的特征多項(xiàng)式

f(λ)=g(λ-1)=(λ-1)n+1=(λ+1)n+1

也就是A的極小多項(xiàng)式.

當(dāng)n不是2的冪時(shí)，根據(jù)引理1可知，將f(λ)展開(kāi)后除λn以外至少還有一項(xiàng)，即f(λ)不是單項(xiàng)式. 因此對(duì)任意正整數(shù)i，單項(xiàng)式λi都不能被f(λ)整除，這意味著λi不是A的零化多項(xiàng)式，所以A不冪零. 同時(shí)這也說(shuō)明對(duì)任意的i，總能找到0-1向量γ使得Aiγ≠0. 證畢.

在定理2的證明中，我們已經(jīng)得到了如下性質(zhì)，

性質(zhì)4當(dāng)n不是2的冪時(shí)，在正n邊形的每個(gè)頂點(diǎn)上隨意寫一個(gè)整數(shù)，進(jìn)行相鄰做差運(yùn)算，有可能無(wú)法化為都是0的形式，而是陷入循環(huán)，這個(gè)循環(huán)中只出現(xiàn)0和某個(gè)正數(shù)A.

例如，在正六邊形的頂點(diǎn)寫下9、5、2、6、9、6，經(jīng)過(guò)一次相鄰做差運(yùn)算后變?yōu)?、3、4、3、3、3，繼續(xù)做下去，得到的結(jié)果如下表

原始數(shù)據(jù)952696第1次運(yùn)算后434333第2次運(yùn)算后111001第3次運(yùn)算后001010第4次運(yùn)算后011110第5次運(yùn)算后100010第6次運(yùn)算后100111第7次運(yùn)算后101000第8次運(yùn)算后111001

第8次運(yùn)算結(jié)果和第2次運(yùn)算結(jié)果相同，從此開(kāi)始循環(huán)，循環(huán)周期為6.

這樣我們完全搞清楚了正n邊形上的相鄰做差運(yùn)算產(chǎn)生的向量序列的收斂性問(wèn)題. 當(dāng)然其中還有很多定量計(jì)算的東西值得進(jìn)一步探討. 例如任給一個(gè)2m維的向量，能否計(jì)算出它收斂到0所需要的步數(shù)；再比如，當(dāng)維數(shù)不是2的冪時(shí)，循環(huán)的最小正周期是多少. 希望本文能起到拋磚引玉的作用，讓各位讀者進(jìn)一步思考并解決這些問(wèn)題.