利用模算術判定可逆矩陣

本文的閱讀等級：初級

給定

，

若不實際計算矩陣秩或行列式，從矩陣型態如何判定 是可逆矩陣？如果我們能證明 ，即知 是可逆矩陣。對於 階矩陣 ，回想行列式的運算公式 (見“行列式的運算公式與性質”)

，

其中 代表對應列置換 的排列矩陣。觀察發現上例 的主對角元都是奇數，非主隊角元都是偶數。根據行列式的運算公式， 僅有一項 是奇數，其餘各項皆為偶數，推論 是奇數，故必不為零，即證明 是可逆矩陣。一整數 是偶數或奇數取決於 除以 的餘數是 或 ，這種表述方式可以加以推廣為模算術 (modular arithmetic)。本文介紹模算術的基礎知識，並解說如何利用模算術來判定可逆矩陣。

 
給定整數 ，任一整數可按照它除以 的餘數 分為 個剩餘類。例如，若 ，所有的整數可分為6個子集，對應餘數 。如果兩整數 和 除以 的餘數相同，也就是說 被 整除，則它們被歸為同一剩餘類，我們稱「 和 對於模 (modulo) 同餘」，下列記法由高斯 (Carl Friedrich Gauss) 最先引用：

，

其中 是同餘相等符號。例如，，。以下假設所有的模算術均針對整數。不難驗證下面三個性質：

1. 反身性：
2. 對稱性：若 ，則 。
3. 傳遞性：若 且 ，則 。

因此，同餘是一種等價關係 (見“矩陣的等價關係”)。這表示同餘和等式具有同樣的特性，我們可以將同餘看成某種等式。

 
下面介紹模算術遵守的兩個運算法則。若 且 ，則

，

。

例如，從 ，，可得

，

。

同餘保持加法和乘法等價性質允許我們僅對模 的餘數採行算術運算。下例說明如何用模算術快速得到一算式除以 的餘數：

。

此結果可立刻應用於計算行列式除以 的餘數：

。

推廣至一般情況，令 為一 階矩陣且所有 為整數， 代表 除以 的餘數，即有 ，下式成立：

。

 
回到本文最初給的例子，用模算術來計算 除以 的餘數，過程如下：

，

可知 ，因此 是可逆矩陣。再看一個例子，

。

同樣用模算術計算 除以 的餘數：

，

得知 是偶數，故無法判定 是否可逆。於是我們繼續計算 除以 的餘數：

。

除以 的餘數是 ，這表明 ，證得 是可逆矩陣。

 
至此我們不禁要問：萬一給定的矩陣 不可逆，那將如何？因為 除以任何 總是得到餘數 ，上述程序必須從 持續至 大於所有的 ，我們方能確知 的行列式等於零。這不啻宣告模算術僅適用於判定可逆矩陣，對於不可逆矩陣反而是徒勞無功之舉。即便模算術並非萬無一失且僅適用判定包含整數元的可逆矩陣，但模算術自有一個特別的線性代數應用──希爾密碼 (Hill cipher)。日後我們將詳細探討這個有趣的主題。

 
補註：
讀者是否曾經疑問：為甚麼不可逆矩陣也稱為「奇異」(singular) 矩陣？這裡「奇異」是指「異於一般所見的特殊情況」，與「奇異值分解」(singular value decomposition) 無關。如果一 階矩陣的元皆隨機產生，則該矩陣是可逆矩陣的機率非常之大。舉例來說， 階矩陣是可逆的，若唯一元不為零； 階矩陣是可逆的，若兩個列 (行) 向量所表示的平面上兩點不在穿越原點的同一直線上。 階矩陣是可逆的，若三個列 (行) 向量所表示的空間中三點不在穿越原點的同一平面上。所以說，如果一矩陣來自摻入雜音的實驗測量或調查數據，那麼我們幾乎可以肯定它是可逆矩陣。在這種情況下，利用模算術判定可逆矩陣可以視為一種保險措施。

繼續閱讀：

• 希爾密碼

Advertisement