特殊矩陣 (10)：基本矩陣

本文的閱讀等級：初級

數百年以來，化約主義 (reductionism) 主導科學和工程的研究方法論，基本思想是將複雜的系統或現象化解為各部分的組合，再透過分析各組件從而理解並描述原來的複雜系統或現象。化約主義經常見於線性代數，譬如，類似多項式的因式分解，高斯消去法把可逆矩陣分解為一組基本矩陣 (elementary matrix) 的乘積。本文介紹基本矩陣的一般形式與性質，特別的是基本矩陣是可逆的，且其逆矩陣也為基本矩陣。

令 $\mathbf{u}$ 與 $\mathbf{v}$ 為 $n$ 維實 (或複) 行向量 (column vector)。若 $\mathbf{v}^T\mathbf{u}\neq -1$ ，具有形式 $I_n+\mathbf{u}\mathbf{v}^T$ 的矩陣稱為基本矩陣^[1]，其中 $\mathbf{u}\mathbf{v}^T$ 是一個 $n\times n$ 階矩陣，稱為 $\mathbf{u}$ 和 $\mathbf{v}$ 的外積(outer product)。若 $\mathbf{u}$ 和 $\mathbf{v}$ 不為零向量，則 $\mathbf{u}\mathbf{v}^T$ 為秩─1 (rank-one) 矩陣，即 $\hbox{rank}(\mathbf{u}\mathbf{v}^T)=1$ ^[2]。請注意， $\mathbf{v}^T\mathbf{u}$ 是一個純量。見下例，若 $\mathbf{u}=\begin{bmatrix} 1\\ 2 \end{bmatrix}$ 且 $\mathbf{v}=\begin{bmatrix} 0\\ 1 \end{bmatrix}$ ，則

$\mathbf{v}^T\mathbf{u}=\begin{bmatrix} 0&1 \end{bmatrix}\begin{bmatrix} 1\\ 2\end{bmatrix}=2, ~~ \mathbf{u}\mathbf{v}^T=\begin{bmatrix} 1\\ 2\end{bmatrix}\begin{bmatrix} 0&1 \end{bmatrix}=\begin{bmatrix} 0&1\\ 0&2 \end{bmatrix}$ ，

且 $I_2+\mathbf{u}\mathbf{v}^T=\begin{bmatrix} 1&1\\ 0&3 \end{bmatrix}$ 是一個基本矩陣。

因為 $(I_n+\mathbf{u}\mathbf{v}^T)^T=I_n+\mathbf{v}\mathbf{u}^T$ 且 $\mathbf{u}^T\mathbf{v}=\mathbf{v}^T\mathbf{u}\neq -1$ ，基本矩陣的轉置也是一個基本矩陣。所有的基本矩陣都是可逆的，下面展示一個直接的論證。我們猜測基本矩陣的逆矩陣也是一個基本矩陣，設

$(I+\mathbf{u}\mathbf{v}^T)^{-1}=I+k\mathbf{u}\mathbf{v}^T$ ，

其中 $k$ 是一個未知數。計算

$\begin{aligned} (I+\mathbf{u}\mathbf{v}^T)\left(I+k\mathbf{u}\mathbf{v}^T\right)&=I+\mathbf{u}\mathbf{v}^T+k\mathbf{u}\mathbf{v}^T+k\mathbf{u}(\mathbf{v}^T\mathbf{u})\mathbf{v}^T\\ &=I+\left(1+k+k\mathbf{v}^T\mathbf{u}\right)\mathbf{u}\mathbf{v}^T.\end{aligned}$

令上式等於 $I$ ，解得 $k=-(1+\mathbf{v}^T\mathbf{u})^{-1}$ 。因此，基本矩陣 $I+\mathbf{u}\mathbf{v}^T$ 的逆矩陣為

$\displaystyle (I+\mathbf{u}\mathbf{v}^T)^{-1}=I-\frac{1}{1+\mathbf{v}^T\mathbf{u}}\mathbf{u}\mathbf{v}^T$ 。

基本矩陣的逆矩陣公式解釋了為何我們要求 $\mathbf{v}^T\mathbf{u}\neq -1$ 。

使用矩陣行列式引理 (matrix determinant lemma) 可導出基本矩陣的行列式公式 (見“矩陣和之行列式 (上)”)，如下：

$\det(I+\mathbf{u}\mathbf{v}^T)=\det I+\mathbf{v}^T(\mathrm{adj}I)\mathbf{u}$ 。

因為 $\det I=1$ 且 $\mathrm{adj}I=I$ ，基本矩陣的行列式可簡化為

$\det(I+\mathbf{u}\mathbf{v}^T)=1+\mathbf{v}^T\mathbf{u}$ 。

在高斯消去法中，每一個基本列運算 (elementary row operation) 對應一個基本矩陣。基本列運算可分為三類 (見“高斯消去法”)：

交換：列 $i$ 與列 $j$ 互換位置；
伸縮：列 $i$ 通乘一個非零常數 $c$ ；
取代：列 $j$ 通乘一個非零常數 $c$ 的結果加進列 $i$ ， $i\neq j$ 。

你對單位矩陣 $I$ 執行基本列運算，其結果即為對應的基本矩陣。以 $3\times 3$ 階矩陣為例，

$E_1=\begin{bmatrix} 0&1&0\\ 1&0&0\\ 0&0&1 \end{bmatrix},~ E_2=\begin{bmatrix} 1&0&0\\ 0&c&0\\ 0&0&1 \end{bmatrix},~ E_3=\begin{bmatrix} 1&0&0\\ c&1&0\\ 0&0&1 \end{bmatrix}$ ，

其中 $E_1$ 代表交換列 1 與列 2， $E_2$ 由列 2 乘以常數 $c$ 而得， $E_3$ 則為列 1 乘以常數 $c$ 再加進列 2 的結果。計算矩陣乘法即可驗證左乘一個基本矩陣等同於執行一次對應的基本列運算：

$\begin{aligned} E_1A&=\begin{bmatrix} 0&1&0\\ 1&0&0\\ 0&0&1 \end{bmatrix}\begin{bmatrix} a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33} \end{bmatrix}=\begin{bmatrix} a_{21}&a_{22}&a_{23}\\ a_{11}&a_{12}&a_{13}\\ a_{31}&a_{32}&a_{33} \end{bmatrix},\\ E_2A&=\begin{bmatrix} 1&0&0\\ 0&c&0\\ 0&0&1 \end{bmatrix}\begin{bmatrix} a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33} \end{bmatrix}=\begin{bmatrix} a_{11}&a_{12}&a_{13}\\ ca_{21}&ca_{22}&ca_{23}\\ a_{31}&a_{32}&a_{33} \end{bmatrix},\\ E_3A&=\begin{bmatrix} 1&0&0\\ c&1&0\\ 0&0&1 \end{bmatrix}\begin{bmatrix} a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33} \end{bmatrix}=\begin{bmatrix} a_{11}&a_{12}&a_{13}\\ ca_{11}+a_{21}&ca_{12}+a_{22}&ca_{13}+a_{23}\\ a_{31}&a_{32}&a_{33} \end{bmatrix}.\end{aligned}$

從上面三個基本矩陣 $E_1,E_2,E_3$ 反推可以歸納出基本矩陣的型態為 $I+\mathbf{u}\mathbf{v}^T$ ，如下：

$\begin{aligned} E_1&=\begin{bmatrix} 0&1&0\\ 1&0&0\\ 0&0&1 \end{bmatrix}=I+\left[\!\!\begin{array}{rrc} -1&1&0\\ 1&-1&0\\ 0&0&0 \end{array}\!\!\right]=I+\left[\!\!\begin{array}{r} 1\\ -1\\ 0 \end{array}\!\!\right]\begin{bmatrix} -1&1&0 \end{bmatrix}=I+(\mathbf{e}_1-\mathbf{e}_2)(\mathbf{e}_2-\mathbf{e}_1)^T,\\ E_2&=\begin{bmatrix} 1&0&0\\ 0&c&0\\ 0&0&1 \end{bmatrix}=I+\left[\!\!\begin{array}{ccc} 0&0&0\\ 0&c-1&0\\ 0&0&0 \end{array}\!\!\right]=I+(c-1)\begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix}\begin{bmatrix} 0&1&0 \end{bmatrix}=I+(c-1)\mathbf{e}_2\mathbf{e}_2^T,\\ E_3&=\begin{bmatrix} 1&0&0\\ c&1&0\\ 0&0&1 \end{bmatrix}=I+\begin{bmatrix} 0&0&0\\ c&0&0\\ 0&0&0 \end{bmatrix}=I+c\begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix}\begin{bmatrix} 1&0&0 \end{bmatrix}=I+c\,\mathbf{e}_2\mathbf{e}_1^T,\end{aligned}$

其中 $\mathbf{e}_i$ 是第 $i$ 個標準單位向量 (第 $i$ 元為 $1$ ，其餘元為 $0$ )。推廣至 $n\times n$ 階矩陣，如下：

交換列 $i$ 和列 $j$ ：

$E_1=I_n+(\mathbf{e}_i-\mathbf{e}_j)(\mathbf{e}_j-\mathbf{e}_i)^T$ ；

列 $i$ 通乘一個非零常數 $c$ ：

$E_2(c)=I_n+(c-1)\mathbf{e}_i\mathbf{e}_i^T$ ；

將列 $j$ 通乘一個非零常數 $c$ 的結果加進列 $i$ ：

$E_3(c)=I_n+c\mathbf{e}_i\mathbf{e}_j^T$ 。

接下來，我們寫出上述三種基本矩陣的行列式與逆矩陣。

令 $\mathbf{u}=\mathbf{e}_i-\mathbf{e}_j$ 且 $\mathbf{v}=\mathbf{e}_j-\mathbf{e}_i$ 。計算可得 $\mathbf{v}^T\mathbf{u}=-2$ ，故 $\det E_1=-1$ ，逆矩陣則為

$E_1^{-1}=I_n+\mathbf{u}\mathbf{v}^T=E_1$ 。

基本矩陣 $E_1$ 交換兩個列，改變矩陣行列式的正負號； $E_1$ 的逆矩陣為其自身，因為連續交換兩次列 $i$ 與列 $j$ 等於什麼事也沒做。
令 $\mathbf{u}=(c-1)\mathbf{e}_i$ 且 $\mathbf{v}=\mathbf{e}_i$ 。計算可得 $\mathbf{v}^T\mathbf{u}=c-1$ ，故 $\det E_2(c)=c$ 且

$E_2(c)^{-1}=I_n+\left(\frac{1}{c}-1\right)\mathbf{e}_i\mathbf{e}_i^T=E_2\left(\frac{1}{c}\right)$ 。

對應 $E_2(c)^{-1}$ 的基本列運算將列 $i$ 通乘 $\frac{1}{c}$ 。
令 $\mathbf{u}=c\,\mathbf{e}_i$ 且 $\mathbf{v}=\mathbf{e}_j$ 。計算可得 $\mathbf{v}^T\mathbf{u}=0$ ，故 $\det E_3(c)=1$ 且

$E_3(c)^{-1}=I_n+(-c)\mathbf{e}_i\mathbf{e}_j^T=E_3(-c)$ 。

對應 $E_3(c)^{-1}$ 的基本列運算是將列 $j$ 通乘非零常數 $-c$ 的結果加進列 $i$ 。

最後我們解釋何以任何一個非奇異 (nonsingular) 矩陣，即可逆矩陣，可以分解為數個基本矩陣之積。

定理. 方陣 $A$ 是非奇異的一個充要條件是 $A$ 為基本矩陣之積。

假設 $A$ 是一個非奇異矩陣。在高斯─約當法，我們對 $A$ 執行基本列運算直至得到單位矩陣 $I$ (見“高斯─約當法”)。假設 $E_1,E_2,\ldots,E_k$ 表示對應列運算的基本矩陣，則

$E_k\cdots E_2E_1A=I$ 。

因此， $A=E_1^{-1}E_2^{-1}\cdots E_k^{-1}$ ，其中所有的 $E_i^{-1}$ 都是基本矩陣。相反的，假設 $A=F_1F_2\cdots F_k$ ，其中 $F_i$ 是基本矩陣。因為所有的 $F_i$ 是非奇異矩陣，其積必定也是一個非奇異矩陣。

註解
[1] 在中國大陸，基本矩陣稱為「初等矩陣」，基本列運算稱為「初等行變換」。
[2] 若 $\mathbf{u}$ 或 $\mathbf{v}$ 為零向量，則 $\mathbf{u}\mathbf{v}^T=0$ ，基本矩陣 $I_n+\mathbf{u}\mathbf{v}^T$ 退化為單位矩陣。

繼續閱讀：

9 Responses to 特殊矩陣 (10)：基本矩陣

vtriplev says:

12/16/2010 at 11:51 pm

uv’ 按照https://ccjou.wordpress.com/2011/01/10/%E5%9F%BA%E6%9C%AC%E7%9F%A9%E9%99%A3%E7%9A%84%E5%B9%BE%E4%BD%95%E6%84%8F%E7%BE%A9/
是1種projection
所以
E1,E2,E3的表達法,都帶有1種幾何意義
E1的表達法,其實就是I+2uu’

VtripleV says:

12/17/2010 at 12:51 pm

好像打太快了
E1的表達法應該就是Household矩陣
https://ccjou.wordpress.com/2009/09/14/%E7%89%B9%E6%AE%8A%E7%9F%A9%E9%99%A3-%E5%9B%9B%EF%BC%9Ahouseholder-%E7%9F%A9%E9%99%A3/

VtripleV says:

12/17/2010 at 2:19 pm

類似(I-AB)invertible => I-BA invertible
在交大林琦焜教授的開放課程第47分鐘有一些用等比級數思路的介紹
http://140.113.8.88/pub/pubdrm/fa962/192k/970304.wmv
順著這個思路依樣畫葫蘆
利用前面求(I-AB)inverse的技巧
在(A+UBV)^(-1)的求解上
A+UBV=A[I+A^-1*UBV]
(A+UBV)^-1=[I+A^-1*UBV]A^-1
最後也得到類似的答案了

ccjou says:

12/18/2010 at 9:04 am

目前我只知道使用分塊矩陣推導矩陣和的逆矩陣，有空時再來研究你說的方法。

vtriplev says:

12/19/2010 at 11:19 am

林教授的思路方法,是可以幫忙推導公式,但是不rigorus
不過用來不rigorus推導,還挺方便的.我去討論區用站內的數學公式輸入法來寫1下

ccjou says:

12/20/2010 at 11:33 am

$(I-A)^{-1}=I+A+A^2+\cdots$
的成立條件是 $A$ 的特徵值滿足 $\vert\lambda\vert<1$ 。不嚴格(rigorous)是指這個吧！？房子是不能建在沙灘上的。

在路上 says:

04/21/2014 at 1:49 pm

三种初等矩阵本身是很好理解的，看到一个初等矩阵，马上可以知道它对一个与之相乘矩阵或向量的作用是什么，其逆也可以顺手写出。但是是出于什么样的想法把一个初等矩阵变成了I+u*v’这种不直观的形式？从I+u*v’貌似一眼看不出它对另一个矩阵干了什么事！写成这种形式到底有什么好处呢？

- ccjou says:
  
  04/21/2014 at 4:17 pm
  
  數學家們可能不會承認，但他們確實常用歸納法來解決問題。如果你眼前有單位矩陣 $I$ ，初等行變換所乘的矩陣
  $E_1=\begin{bmatrix} 0&1&0\\ 1&0&0\\ 0&0&1 \end{bmatrix},E_2=\begin{bmatrix} 1&0&0\\ 0&3&0\\ 0&0&1 \end{bmatrix},E_3=\begin{bmatrix} 1&0&0\\ 4&1&0\\ 0&0&1 \end{bmatrix}$ ，正交投影至XY平面的矩陣 $P=\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&0&0 \end{bmatrix}$ ，以及以Y軸鏡射的矩陣 $H=\begin{bmatrix} 1&0&0\\ 0&-1&0\\ 0&0&1 \end{bmatrix}$ ，我們不免好奇：這些矩陣是否具有相同的表達形式？將它們減去 $I$ ，你會得到rank-one矩陣，即 $uv^T$ 。這樣做有甚麼好處呢？我想到的一個理由是簡化矩陣的設計，見
  https://ccjou.wordpress.com/2011/01/10/%E5%9F%BA%E6%9C%AC%E7%9F%A9%E9%99%A3%E7%9A%84%E5%B9%BE%E4%BD%95%E6%84%8F%E7%BE%A9/
  
  https://ccjou.wordpress.com/2011/03/22/%E8%AE%8A%E6%8F%9B%E7%9F%A9%E9%99%A3%E7%9A%84%E8%A8%AD%E8%A8%88/
  
Pingback: 线性代数 — 线性代数中的一些特殊矩阵（被广泛用于高斯消元法的消元矩阵E）（个人笔记扫描版） – 源码巴士

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨