如何求MATLAB中構造的幻方的秩？

12-03

MATLAB中的magic函數，可以生成任意n大於等於3階的幻方。
其構造方法知乎上有人解答過了：
怎麼構造幻方，有什麼三階乃至四階及以上n階幻方的合成方法？ - 數學

同時，在說明文檔中提到了對於不同的階數n，矩陣的秩也不一樣：
For n odd, the rank of the magic square is n.
For n divisible by 4, the rank is 3.
For n even but not divisible by 4, the rank is n/2 + 2.

請問這個如何證明？

本答案中的證明以圖為主（多圖預警），公式為輔。

幻方的構造方法以及部分圖片取自這個回答：
怎麼構造幻方，有什麼三階乃至四階及以上n階幻方的合成方法？ - 知乎用戶的回答

第三種情況的證明已經補充完整。累死我了！

============ 1. n = 2k + 1 的情況 ============

幻方的構造方法為：從第一行正中央開始，向右上方逐個填充數字。若從上方出界，則轉移到下方；若從右邊出界，則轉移到左邊。若右上方已經填充了數字，則把新的數字填到下方的格子里。

例如，5階幻方是這樣的：

15階幻方畫成圖是這樣的：

我們的證明目標是：這樣的幻方是滿秩的。

為證明方便，我們把起始的格子由第一行正中央改為左上角。
這相當於把幻方的前 $k$ 列和後 $k+1$ 列交換，不改變幻方的秩。

上面的15階幻方，經過上述變換後是這樣的：

下面開始對此幻方進行行、列變換。
首先，讓每一行減去下一行，最後一行不變。幻方變成了這樣：

其中，除最後一行的部分，深藍色的值為 $-n-1$ ，淺藍色的值為 $-1$ ，紅色的值為 $n^2-n-1$ （請讀者自行驗證）。

然後，再讓各列都減去第一列：

顏色可能看不太清，我說明一下：第一列除左下角外，值均為 $-n-1$ ；去掉第一列及最後一行後的部分，大部分值（淺綠色）為 $0$ ，副對角線上的暗紅色值為 $n^2$ ，有兩排淺黃色的值為 $n$ 。

第一列除左下角外的值不為0，不爽。不過注意到，去掉第一列及最後一行後的部分，每行的和都是 $n^2 + n$ 。於是想到，把除第一列之外的所有列都加起來，除以 $n$ 後，加到第一列上去。結果為：

這樣，第一列就只有左下角元素非零了。

上面的行、列變換均不改變矩陣的秩，所以我們要證明上面這個矩陣滿秩。
由於第一列只有左下角元素非零，所以其實只要證明去掉第一列和最後一行後剩下的部分滿秩。
為了看得清楚，我把這部分單獨畫出來：

其中，深藍色的值為 $0$ ，淺藍色的值 $n$ ，暗紅色的值為 $n^2$ 。

記此矩陣為 $A$ ，設有行向量 $x$ 使得 $xA = 0$ 。
（我故意把 $x$ 放在 $A$ 左邊，下面敘述起來方便）
用 $x_i$ 表示 $x$ 的第 $i$ 個元素。
由 $x$ 與 $A$ 的最後一列相乘為零，得 $x_2 = -nx_1$ ；
由 $x$ 與 $A$ 的倒數第二列相乘為零，得 $x_4 = -nx_2$ ；
由 $x$ 與 $A$ 的倒數第四列相乘為零，得 $x_8 = -nx_4$ ……
如此遞推下去，下標會形成一個循環（儘管不一定經過每一個數字），於是有 $x_1 = (-n)^l x_1$ ， $l$ 為循環長度。這樣，必須有 $x_1 = 0$ 。
同理，從 $x$ 的任意一個元素開始遞推，都能形成循環，所以 $x$ 的所有元素都是0。
$xA = 0 Rightarrow x = 0$ ，故 $A$ 滿秩，證畢。

============ 2. n = 4k 的情況 ============

幻方的構造方法為：先畫兩個 n*n 的矩陣，在一個裡面依次填滿 $1 sim n^2$ 的數字，在另一個裡面依次填滿 $n^2 sim 1$ 的數字。然後從兩個矩陣中各取一部分數字，合成幻方。取數的標準為：把矩陣劃分成 4*4 的小矩陣，小矩陣兩條對角線上的數字取自第二個矩陣，其餘元素取自第一個矩陣。

例如，8階幻方是這樣的：

16階幻方畫成圖是這樣的：

我們的證明目標是：這樣的幻方的秩等於 3。

同樣進行各種行、列變換。首先，讓每一列減去前一列，第1列不變。結果如下：

注意第 3、5、7、……、n-1 列，看起來彷彿都變成了0。其實，第3、7、11……列的內容是 $[+1, -1, -1, +1, cdots]$ ，第5、9、13……列的內容是 $[-1, +1, +1, -1, ldots]$ （請讀者自行驗證），這些列拿出來，秩為1。

剩下的各列里，第 2、6、10……列看起來比較像，第4、8、12……列看起來也比較像。
那麼，就讓第6、10……列減去第2列，第8、12……列減去第4列，結果如下：

相減的結果很小，圖上看不出來了。我告訴你結果：第6、10、14……列的內容是 $[+8,-8,-8,+8,ldots]$ ，第8、12、16……列的內容是 $[-8,+8,+8,-8,ldots]$ （同樣請讀者自行驗證）。這樣，矩陣中除去第1、2、4列，剩下的部分秩為1。若要考慮整個矩陣的秩，只看前4列就行了。

巧的是，第2列和第4列的和，恰好是 $[-4, +4, +4, -4, ldots]$ ，是第3列的-4倍。於是，整個矩陣的秩，只看前3列就行了。

我們要證明這部分的秩等於3。那就拿出開頭3行好了，它們是：
$left[ egin{array}{ccc} n^2 quad -n^2+2 quad 1 \ n+1 quad n^2-2n-2 quad -1 \ 2n+1 quad n^2-4n-2 quad -1 end{array} ight]$
容易驗證這部分的秩為3（過程略），證畢。

============ 3. n = 4k + 2 的情況 ============

首先指出，Matlab（我用的是R2010a版本）里，這類幻方的構造方法與開頭引用的那篇答案略有不同。還是一圖勝千言吧。Matlab 作出的 18 階幻方如下圖所示：

作法為：

先按左上、右下、右上、左下的順序，用奇數階幻方的構造方法，構造四個 $n/2$ 階幻方；
交換左上、左下兩部分的前 $k$ 列，但中間那一行的第一個元素不交換，中央元素交換；
交換右上、右下兩部分的後 $k-1$ 列。

我們的證明目標為：這樣的幻方的秩為 $2k+3$ 。

首先注意到，如果把幻方的上下兩半相減，那麼各行相減的結果都相同，除了最中間那一行。
於是，我們可以用這兩種相減的結果代替原矩陣的下半部分，得到一個 $(2k+3) imes n$ 的矩陣：

這裡，倒數第2行是原來的第1行減去第 $2k+2$ 行，最後一行是原來的第2行減去第 $2k+3$ 行。

然後，讓最後一行減去倒數第2行；再讓第 $k+1$ 行（即上半部分的特殊行）減去新的最後一行的一半，就可以讓特殊行不再特殊（請讀者自行驗證）：

注意，此時的最後一行中，僅有兩個元素非零。

回憶一下證明目標，是要證明這個 $(2k+3) imes n$ 矩陣的秩為 $2k+3$ 。
矩陣一共只有 $2k+3$ 行，所以只要挑出 $2k+3$ 列，證明這些列構成的子陣滿秩就行了。
挑哪些列呢？不妨就挑第1列和後 $2k+2$ 列：

注意挑出來的這個子陣中，最後一行僅有第一個元素非零，於是僅需證明右上角的 $2k+2$ 階方陣滿秩。

去掉第一列和最後一行，並讓第 $1 sim 2k$ 行依次減去下一行：

與第一種情況類似，圖中還有兩排顏色與背景相近的元素看不清。

注意到首、末兩列，除了最後兩個元素之外都是相等的。於是讓第一列減去最後一列。
另外把第 $2 sim k+1$ 列拿到最右邊，這樣上半部分的排列就跟第一種情況的證明過程類似了。

最左一列的倒數第二個元素非零，我們想把它弄成零。
事實上，此時左下角的 2x2 子陣的值為： $frac{n^2}{4} left[ egin{array}{cc} -1 3 \ -2 1 end{array} ight]$
讓倒數第二行減去倒數第一行的一半，就可以把倒數第二行的第一個元素弄成零，此時倒數第二行的第二個元素仍非零。此時最左一列僅有最末元素非零了，於是只需證明右上角的 $2k+1$ 階方陣滿秩。
這一點的證明方法與第一種情況（即 n 為奇數的情況）相同。

Mathworks公司的創始人之一 Cleve Moler 寫過博客解釋原因:
Magic Squares, Part 3, Linear Algebra