無相互作用的矩陣積

本文的閱讀等級:初級

考慮下列 3\times 3 矩陣:

A=\begin{bmatrix}    1&0&0\\    a&1&0\\    0&0&1    \end{bmatrix},~B=\begin{bmatrix}    1&0&0\\    0&1&0\\    b&0&1    \end{bmatrix},~C=\begin{bmatrix}    1&0&0\\    0&1&0\\    0&c&1    \end{bmatrix}

矩陣 A, B, C 共有 3! 種排列方式,因此產生 6 個矩陣積,即

ABC=\begin{bmatrix}    1&0&0\\    a&1&0\\    b&c&1    \end{bmatrix}, ~BAC=\begin{bmatrix}    1&0&0\\    a&1&0\\    b&c&1    \end{bmatrix},

ACB=\begin{bmatrix}    1&0&0\\    a&1&0\\    b&c&1    \end{bmatrix},~CAB=\begin{bmatrix}    1&0&0\\    a&1&0\\    b+ac&c&1    \end{bmatrix},

BCA=\begin{bmatrix}    1&0&0\\    a&1&0\\    b+ac&c&1    \end{bmatrix},~CBA=\begin{bmatrix}    1&0&0\\    a&1&0\\    b+ac&c&1    \end{bmatrix}

其中 ABC, BAC, ACB 未產生 ac 項,我們稱這些矩陣乘積無「相互作用」(interaction)。本文要探討的問題是:無相互作用的矩陣積必須滿足何種矩陣排列規則?

 
這個問題來自於 LU 分解。令 A 是一 n\times n 階矩陣,LU 分解式為 A=LU,其中下三角矩陣 L 記錄高斯消去法的化簡過程,上三角矩陣 U 則儲存化簡結果(詳見“LU 分解”)。我們用一個例子來說明 LU 分解的計算步驟,考慮

A=\left[\!\!\begin{array}{rrc}    3&-1&2\\    6&-1&5\\    -9&7&3    \end{array}\!\!\right]

令基本矩陣 E_{ij}i>j, 為列取代運算的矩陣表達(見“特殊矩陣 (10):基本矩陣”),在任一矩陣 X 左乘 E_{ij},即可消去 X(i,j) 元。運行高斯消去法的化簡過程可用一連串的基本矩陣乘法實現,如下:

E_{32}E_{31}E_{21}A=U

其中

E_{21}=\left[\!\!\begin{array}{rcc}    1&0&0\\    -2&1&0\\    0&0&1    \end{array}\!\!\right],~E_{31}=\begin{bmatrix}    1&0&0\\    0&1&0\\    3&0&1    \end{bmatrix},~E_{32}=\left[\!\!\begin{array}{crc}    1&0&0\\    0&1&0\\    0&-4&1    \end{array}\!\!\right]

乘開上式即得一上三角矩陣:

U=\left[\!\!\begin{array}{crc}    3&-1&2\\    0&1&1\\    0&0&5    \end{array}\!\!\right]

E=E_{32}E_{31}E_{21},計算發現矩陣積 E(3,1) 元存在相互作用:

E=E_{32}E_{31}E_{21}=\left[\!\!\begin{array}{crc}    1&0&0\\    0&1&0\\    0&-4&0    \end{array}\!\!\right]\begin{bmatrix}    1&0&0\\    0&1&0\\    3&0&1    \end{bmatrix}\left[\!\!\begin{array}{rcc}    1&0&0\\    -2&1&0\\    0&0&1    \end{array}\!\!\right]=\left[\!\!\begin{array}{rrc}    1&0&0\\    -2&1&0\\    11&-4&1    \end{array}\!\!\right]

基本矩陣 E_{ij} 皆可逆,改變 E_{ij}(i,j) 元的正負號即為其逆矩陣 E_{ij}^{-1},分別如下:

E_{21}^{-1}=\begin{bmatrix}    1&0&0\\    2&1&0\\    0&0&1    \end{bmatrix},~E_{31}^{-1}=\left[\!\!\begin{array}{rcc}    1&0&0\\    0&1&0\\    -3&0&1    \end{array}\!\!\right],~E_{32}^{-1}=\begin{bmatrix}    1&0&0\\    0&1&0\\    0&4&1    \end{bmatrix}

寫出 A=E^{-1}U,令 L=E^{-1}=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1},就得到 A 的 LU 分解,上例中,

L=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}=\begin{bmatrix}    1&0&0\\    2&1&0\\    0&0&1    \end{bmatrix}\left[\!\!\begin{array}{rcc}    1&0&0\\    0&1&0\\    -3&0&1    \end{array}\!\!\right]\begin{bmatrix}    1&0&0\\    0&1&0\\    0&4&1    \end{bmatrix}=\left[\!\!\begin{array}{rcc}    1&0&0\\    2&1&0\\    -3&4&1    \end{array}\!\!\right]

上式由左至右可讀出列運算的消元順序:(2,1), (3,1), (3,2),顯然此運算序不引發相互作用,故 L=[l_{ij}] 的主對角線下各元 l_{ij}(i>j) 完整地記錄列取代運算的乘數(即 2, -3, 4)。高斯消去法並未限定唯一的消元順序,產生 3\times 3L 矩陣的合法消元次序還有 (3,1), (2,1), (3,2)(2,1), (3,2), (3,1)(這個次序理論可行,但不符合簡單原則,請讀者自行嘗試),何以對應這些消元順序的矩陣積都沒有相互作用?

 
考慮一般 n\times n 階列取代基本矩陣。設 i\neq j,令 E_{ij}(a) 的主對角元為1,除 (i,j) 元等於 a,其他各元皆為0,故 E_{ij}(a) 可表示成

E_{ij}(a)=I+a\mathbf{e}_i\mathbf{e}_j^T

其中 \mathbf{e}_i 代表標準單位向量,第 i 元等於1,其餘各元為0。兩基本矩陣 E_{ij}(a)E_{kl}(b) 之積因此為

\begin{aligned}  E_{ij}(a)E_{kl}(b)&=(I+a\mathbf{e}_i\mathbf{e}_j^T)(I+b\mathbf{e}_k\mathbf{e}_l^T)\\  &=I+a\mathbf{e}_i\mathbf{e}_j^T+b\mathbf{e}_k\mathbf{e}_l^T+ab\mathbf{e}_i(\mathbf{e}_j^T\mathbf{e}_k)\mathbf{e}_l^T,  \end{aligned}

由上式可知是否發生相互作用的關鍵在於 \mathbf{e}_j^T\mathbf{e}_k:若 j=k\mathbf{e}_j^T\mathbf{e}_k=1ab 存在,故有相互作用;若 j\neq k\mathbf{e}_j^T\mathbf{e}_k=0,無相互作用。推廣至三基本矩陣乘積,如下:

\begin{aligned}  E_{ij}(a)E_{kl}(b)E_{st}(c)&=I+a\mathbf{e}_i\mathbf{e}_j^T+b\mathbf{e}_k\mathbf{e}_l^T+c\mathbf{e}_s\mathbf{e}_t^T\\  &+ab\mathbf{e}_i(\mathbf{e}_j^T\mathbf{e}_k)\mathbf{e}_l^T+ac\mathbf{e}_i(\mathbf{e}_j^T\mathbf{e}_s)\mathbf{e}_t^T+bc\mathbf{e}_k(\mathbf{e}_l^T\mathbf{e}_s)\mathbf{e}_t^T\\  &+abc\mathbf{e}_i(\mathbf{e}_j^T\mathbf{e}_k)(\mathbf{e}_l^T\mathbf{e}_s)\mathbf{e}_t^T,\end{aligned}

矩陣積 E_{ij}(a)E_{kl}(b)E_{st}(c) 無相互作用的條件是 j\neq kj\neq sl\neq s,換句話說,任意抽取兩矩陣,其「相鄰」指標必須相異,即左邊矩陣的行指標和右邊矩陣的列指標不同。

 
謎團終於煙消雲散。當我們對 A 執行基本列運算時,總是先消去 (1,1) 底下各個元,然後再消去 (2,2) 底下各個元,依此類推,構成 L 矩陣的基本矩陣排序為

(2,1),(3,1),(4,1),\ldots,(3,2),(4,2),\ldots,(4,3),(5,3),\ldots

對於任意兩矩陣,這個特殊的排列方式使得左矩陣的行指標小於右矩陣的列指標,所以無相互作用發生。另外,隨意排列相同行指標的矩陣序,如 (2,1), (3,1), (4,1),\ldots,並不會製造相互作用,這讓我們在對同一行消元時可以放心地自由決定執行順序。

廣告
本篇發表於 線性方程, 線性代數專欄 並標籤為 , , , 。將永久鏈結加入書籤。

2 Responses to 無相互作用的矩陣積

  1. 延伸寸 說道:

    遵守這種排列方式,在計算 L 時,只要用觀察法即可秒殺求得,不必逐一去做 E 矩陣的乘積。這是以前做 LU 分解習題的心得。原來後面有這一串道理。又:這種排列方式有沒有專屬名詞?

    • ccjou 說道:

      我沒有印象在哪一本教科書看過關於此問題的討論,不曉得此排列是否有專屬名稱,無相互作用是我自己訂的標題。在迴歸方程y=f(x1,x2,…),interaction是指f包含 x1*x2 此項。

發表迴響

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

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s