管 濤 范興亞

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

我們知道，利用矩陣可以求解斐波那契類型的遞推數(shù)列的通項(xiàng)公式. 事實(shí)上很多遞推問題都可以利用矩陣解決. 我們來看下面這樣一個有趣的數(shù)學(xué)游戲：一個正方形，畫出它的中點(diǎn)正方形；再畫出新正方形的中點(diǎn)正方形，依此類推，會生成一個漂亮的圖案. 如果在原正方形的四個頂點(diǎn)處隨意各寫一個自然數(shù)，將相鄰頂點(diǎn)處的自然數(shù)相減(用較大的數(shù)減較小的數(shù)，若兩數(shù)相等，則差為0，稱這種運(yùn)算為相鄰做差運(yùn)算)，計算結(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ù)幾次這樣的游戲，就會發(fā)現(xiàn)不管開始寫下什么數(shù)，似乎最后總會化為0. 因此可以猜想對于正方形進(jìn)行相鄰做差運(yùn)算，最終一定會化為四個數(shù)都是0的狀態(tài). 這一猜想是否正確？如果把正方形換成正n邊形，又會有什么樣的結(jié)論呢？

更一般的，我們可以借助向量序列的概念來描述這一問題.

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

換句話說，令max{ai1,ai2,…,ain}=Ai，數(shù)列{Ai}是否會在有限步之內(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只有有限多種不同的形式，遲早會進(jìn)入周期循環(huán)狀態(tài)，那就是說{Ai}必定會在有限步之內(nèi)達(dá)到A并在之后保持恒定.即存在某個下標(biāo)k，當(dāng)i≥k時，Ai恒等于A. 證畢.

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

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

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

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

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

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

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

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

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

首先給出一個引理.

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

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

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

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

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

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

為了考慮n不是2的冪時的情況，我們需要借助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時，特征多項(xiàng)式可化為λn，由此也可得到前面定理1的結(jié)論. 當(dāng)n不是2的冪時，在f(λ)=(λ-1)n+(-1)n-1是一個至少含有兩項(xiàng)的n次多項(xiàng)式，并且其常數(shù)項(xiàng)為0.

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

證明在F2中考慮矩陣B的特征多項(xiàng)式g(λ)=|λI-B|=λn+(-1)n-1=λn+1，由引理2可知g(B)=0. 而對于任意次數(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的冪時，根據(jù)引理1可知，將f(λ)展開后除λn以外至少還有一項(xiàng)，即f(λ)不是單項(xiàng)式. 因此對任意正整數(shù)i，單項(xiàng)式λi都不能被f(λ)整除，這意味著λi不是A的零化多項(xiàng)式，所以A不冪零. 同時這也說明對任意的i，總能找到0-1向量γ使得Aiγ≠0. 證畢.

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

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

例如，在正六邊形的頂點(diǎn)寫下9、5、2、6、9、6，經(jīng)過一次相鄰做差運(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é)果相同，從此開始循環(huán)，循環(huán)周期為6.

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