高階緊密交替符號補矩陣的秩的算法

張 容,邵燕靈

(中北大學 理學院， 太原 030051)

高階緊密交替符號補矩陣的秩的算法

張 容,邵燕靈

(中北大學 理學院， 太原 030051)

定義了緊密交替符號矩陣的補矩陣，利用矩陣的初等變換，研究了該矩陣秩的求解過程。最后，當n≥5k時，提出了該矩陣的秩的計算算法，并給出了一個實例驗證了算法的可行性。

緊密交替符號矩陣；補矩陣；秩的算法

一個符號模式矩陣(符號矩陣)是一個元素取自于集合{+1,-1,0}的矩陣。

定義1 一個交替符號矩陣，是指一個沒有完全零行和零列的，其元素取自于集合{+1,-1,0}的方陣，并且滿足在任一行和任一列之中+1和-1交替出現，開始和最后出現的都是+1[1]。

定義2 一個矩陣被稱為緊密的(行緊密、列緊密)，是指在這個矩陣的每條線(行、列)上沒有零元素存在于2個非零元素間[2]。

1983年，Mill等在交替符號矩陣的猜想[3]引起了以Brualdi、Kim等學者在此方面的研究興趣[4-8]。文獻[1]研究了0-非0模式的n階交替符號矩陣，文獻[2]研究了緊密交替符號矩陣與完全幺模矩陣、組合矩陣和廣義互補基本矩陣的關系，文獻[7]得到了一個n階交替符號矩陣的最大譜半徑，文獻[8]得到了一類交替符號矩陣的逆和廣義逆。2015年，Fiedler等在文獻[9]中得到了緊密交替符號矩陣的秩的計算公式。

低階Bn,k的秩通常易得，而本文主要研究高階Bn,k的秩的算法。

1 預備知識

用Jn表示n階全1矩陣(在不引起混淆的情況下，簡記為J)，用An,k表示將En,k中的所有非零元素全替換為1后所產生的(0,1)矩陣，用Fn,k表示將An,k中的(1,k-1),(2,k-2),…,(k-1,1)元素全部替換為1后產生的矩陣，例如：

引理1[9]記(a,b) 代表整數a和整數b的最大公約數，r(M)及v(M)分別表示一個矩陣M的秩及零度，則

由秩-零化度定理可得：r(M)+v(M)=n。下面推論是顯然的:

引理1～3給出r(Bn,k)的一個估計。下面為計算r(Bn,k)方便，引入Cm、Dn,k。

若k=1，Bn,k為一個對角元為0其余元素均為1的矩陣，即Bn,1=Jn-In，則這樣的矩陣顯然是非奇異的，有r(Bn,k)=n。故以下討論默認k>1。

引理4 當n≥5k時，r(Bn,k)=3k-1+r(Dn-3k+1,k)。

證明 對Bn,k進行一系列初等變換后易得如下結果：

對Cm依次作如下初等變換：

1) 將Cm的第k-1-i列的-1倍加到Cm的第k-1+i列，i=1,2,…,k-2；

2) 將Cm的第k-1-i行的-1倍加到Cm的第k-1+i行，i=1,2,…,k-2；

3) 對Cm前k-2行進行初等行變換，化為反向負單位矩陣；

4) 將Cm的第k-1列的-1倍加到Cm的第2k-2+i列，i=1,2,…,n-4k+2。

2 高階r(Bn,k)算法

由于低階Bn,k的秩容易得到，認為n≥5k時n相對較大，下面對n≥5k時Bn,k的秩的算法進行研究。由引理4知r(Bn,k)=3k-1+r(Dn-3k+1,k)，故下面僅給出計算r(Dn-3k+1,k)的算法步驟：

步驟1 為計算方便，記p=n-3k+1，Dn-3k+1,k=Dp,k。首先對Dp,k進行判別，因p≥2k+1，故一定存在一個正整數α使得0≤p-α(2k-1)

1) 若α滿足0≤p-α(2k-1)

其中(α-1)I2k-1代表的是(α-1)個I2k-1矩陣塊。此時，r(Dp,k)=(α-1)·(2k-1)+(k-1)+r(αAp-(α-1)(2k-1)-(k-1),k+J)，接下來進行步驟2。

2) 若α滿足k≤p-(α-1)(2k-1)<2k-1，則說明Dp,k通過一系列初等變化，可得到：

此時r(Dp,k)=(α-1)·(2k-1)+r(αFp-(α-1)(2k-1),k+V)，接下來則跳過步驟2，直接進行步驟3。

步驟2 首先，將αAp-(α-1)(2k-1)-(k-1),k+J這種形式重新看成αAq,u+J(q,u∈Z+)來計算。

步驟3 將αFn-(α-1)(2k-1),k+V這種形式看成αFq,u+V(q,u∈Z+)來計算。

2) 若u

通過上述步驟，由步驟1判別后進行步驟2和步驟3的相互迭代即可求得相應的r(Dn-3k+1,k)，由引理4可求得r(Bn,k)。

3 算法實例

計算B77,11的秩。

4 結束語

本文定義了緊密交替符號模式補矩陣Bn,k，當n≥5k時，提出了秩的計算算法。同時，由于Bn,k和Bn,n-k+1通過列的逆序排列可相互得到，有r(Bn,k)=r(Bn,n-k+1)，故解決了Bn,k對應低階時的秩。

[1] BRUALDI R A,KIERNAN K P,MEYER S A,et al.Patterns of alternating sign matrices[J].Linear Algebra & Its Applications,2013,438(10):3967-3990.

[2] FIEDLER M,HALL F J,STROEV M.Dense alternating sign matrices and extensions[J].Linear Algebra & Its Applications,2014,444:219-226.

[3] MILLS W H,ROBBINS D P,JR H R.Alternating sign matrices and descending plane partitions[J].Journal of Combinatorial Theory,1983,34(3):340-359.

[4] BRUALDI R A,KIM H K.Completions of Alternating Sign Matrices[J].Graphs & Combinatorics,2015,31(3):507-522.

[5] BRUALDI R A,KIM H K.A Generalization of Alternating Sign Matrices[J].Journal of Combinatorial Designs,2015,23(5):204-215.

[6] BRUALDI R A,KIM H K.Symmetric alternating sign matrices[J].2014,60(3):333-345.

[7] BRUALDI R A,COOPER J.Note on the spectral radius of alternating sign matrices[J].Linear Algebra & Its Applications,2014,442(442):99-105.

[8] CATRAL M,LIN M,OLESKY D D,et al.Inverses and eigenvalues of diamondalternating sign matrices[J].Special Matrices,2014,2(1):78-84.

[9] FIEDLER M,GAO W,HALL F J,et al.Ranks of dense alternating sign matrices and their sign patterns[J].Linear Algebra & Its Applications,2015,471:109-121.

[10]HORN R A,JOHNSON C R.Matrix Analysis(Second Edition)[M].Beijing:China Machine press,2014.

(責任編輯 陳 艷)

Algorithm for Rank of High Order Dense Alternating Sign Complement Matrices

ZHANG Rong, SHAO Yan-ling

(School of Science, North University of China, Taiyuan 030051, China)

The defination of dense alternating sign complement matrices was proposed and the solving process of the rank of this matrices was researched by elementary operation. Finally，whenn≥5k，we give a calculation algorithm for rank and provide a practical example to verify the feasibility of the algorithm.

dense alternating sign matrices; complement matrix; algorithm for rank

2016-10-28 基金項目：國家自然科學基金資助項目(11071227)；山西省回國留學人員科研資助項目(12-070)

張容(1992—)，女，碩士碩士生，主要從事組合數學研究，E-mail:rena345@163.com ；通訊作者 邵燕靈，女，博士，教授，主要從事組合數學研究。

張容,邵燕靈.高階緊密交替符號補矩陣的秩的算法[J].重慶理工大學學報(自然科學)，2017(3):175-180.

format：ZHANG Rong, SHAO Yan-ling.Algorithm for Rank of High Order Dense Alternating Sign Complement Matrices[J].Journal of Chongqing University of Technology(Natural Science)，2017(3):175-180.

10.3969/j.issn.1674-8425(z).2017.03.027

O157

A

1674-8425(2017)03-0175-06