利用模算術判定可逆矩陣

本文的閱讀等級:初級

給定

A=\begin{bmatrix} 4563&2138&8978&1026\\ 7890&1237&8662&2048\\ 1140&3450&9975&7824\\ 2884&6782&3686&4589 \end{bmatrix}

若不實際計算矩陣秩或行列式,從矩陣型態如何判定 A 是可逆矩陣?如果我們能證明 \det A\neq 0,即知 A 是可逆矩陣。對於 n\times n 階矩陣 A=[a_{ij}],回想行列式的運算公式 (見“行列式的運算公式與性質”)

\displaystyle \det A=\sum_{(\alpha,\beta,\ldots,\zeta)}(a_{1\alpha}a_{2\beta}\cdots a_{n\zeta})\cdot\det P_{(\alpha,\beta,\ldots,\zeta)}

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

 
給定整數 m>1,任一整數可按照它除以 m 的餘數 0,1,2,\ldots,m-1 分為 m 個剩餘類。例如,若 m=6,所有的整數可分為6個子集,對應餘數 0,1,2,3,4,5。如果兩整數 ab 除以 m 的餘數相同,也就是說 a-bm 整除,則它們被歸為同一剩餘類,我們稱「ab 對於模 (modulo) m 同餘」,下列記法由高斯 (Carl Friedrich Gauss) 最先引用:

a\equiv b\pmod m

其中 \equiv 是同餘相等符號。例如,5\equiv 17\pmod 626\equiv -4\pmod 6。以下假設所有的模算術均針對整數。不難驗證下面三個性質:

  1. 反身性:a\equiv a\pmod m
  2. 對稱性:若 a\equiv b\pmod m,則 b\equiv a\pmod m
  3. 傳遞性:若 a\equiv b\pmod mb\equiv c\pmod m,則 a\equiv c\pmod m

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

 
下面介紹模算術遵守的兩個運算法則。若 a\equiv b\pmod mc\equiv d\pmod m,則

a+c\equiv b+d\pmod m

a\cdot c\equiv b\cdot d\pmod m

例如,從 17\equiv 5\pmod 626\equiv 2\pmod 6,可得

43=17+26\equiv 5+2=7\pmod 6

442=17\cdot 26\equiv 5\cdot 2=10\pmod 6

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

17\cdot 26-15\cdot 34\equiv 5\cdot 2-3\cdot 4=-2\equiv 4\pmod 6

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

\begin{vmatrix} 17&15\\ 34&26 \end{vmatrix}\equiv\begin{vmatrix} 5&3\\ 4&2 \end{vmatrix}\pmod 6

推廣至一般情況,令 A=[a_{ij}] 為一 n\times n 階矩陣且所有 a_{ij} 為整數,r_{ij} 代表 a_{ij} 除以 m 的餘數,即有 a_{ij}\equiv r_{ij}\pmod m,下式成立:

\det A=\begin{vmatrix} a_{11}&\cdots&a_{1n}\\ \vdots&\ddots&\vdots\\ a_{n1}&\cdots&a_{nn} \end{vmatrix}\equiv\begin{vmatrix} r_{11}&\cdots&r_{1n}\\ \vdots&\ddots&\vdots\\ r_{n1}&\cdots&r_{nn} \end{vmatrix}\pmod m

 
回到本文最初給的例子,用模算術來計算 \det A 除以 2 的餘數,過程如下:

\det A=\begin{vmatrix} 4563&2138&8978&1026\\ 7890&1237&8662&2048\\ 1140&3450&9975&7824\\ 2884&6782&3686&4589 \end{vmatrix}\equiv\begin{vmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{vmatrix}=1\pmod 2

可知 \det A\neq 0,因此 A 是可逆矩陣。再看一個例子,

B=\begin{bmatrix} 4809&1179&6391&2356\\ 1372&8563&9165&5489\\ 3559&1119&1224&7612\\ 1977&3308&5132&4437 \end{bmatrix}

同樣用模算術計算 \det B 除以 2 的餘數:

\det B=\begin{vmatrix} 4809&1179&6391&2356\\ 1372&8563&9165&5489\\ 3559&1119&1224&7612\\ 1977&3308&5132&4437 \end{vmatrix}\equiv\begin{vmatrix} 1&1&1&0\\ 0&1&1&1\\ 1&1&0&0\\ 1&0&0&1 \end{vmatrix}=-2\equiv 0\pmod 2

得知 \det B 是偶數,故無法判定 B 是否可逆。於是我們繼續計算 \det B 除以 3 的餘數:

\det B=\begin{vmatrix} 4809&1179&6391&2356\\ 1372&8563&9165&5489\\ 3559&1119&1224&7612\\ 1977&3308&5132&4437 \end{vmatrix}\equiv\begin{vmatrix} 0&0&1&1\\ 1&1&0&2\\ 1&0&0&1\\ 0&2&2&0 \end{vmatrix}=4\equiv 1\pmod 3

\det B 除以 3 的餘數是 1,這表明 \det B\neq 0,證得 B 是可逆矩陣。

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

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

繼續閱讀:
This entry was posted in 線性代數專欄, 行列式 and tagged , , , . Bookmark the permalink.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s