排列上三角矩陣的主對角元

本文的閱讀等級:中級

下面這則問題取自 2009 年台大電機工程研究所碩士班入學試題:

Let T be a linear operator from \mathbb{C}^n to itself and \lambda\in\mathbb{C}. Let N(T) denote the null space of T. Prove that for every basis of \mathbb{C}^n with respect to which T has an upper-triangular matrix, \lambda appears on the diagonal of the matrix T precisely \dim N((T-\lambda I)^n) times, or disprove it by giving a counter example.

這是原試題 PDF 檔,此題為第 11 題。

2009 台大電機研究所工程數學 (C)

 
為避免符號混淆,令矩陣 A 為線性變換 T 參考某一基底的表示矩陣,問題給出 An\times n 階複上三角矩陣。此題陳述若為真,我們要證明當 \lambda 出現於 A 的主對角線 (n-r) 次,亦即 A-\lambda I(n-r) 個零主對角元,(A-\lambda I)^n 的零空間維數為 (n-r),符號記作 \mathrm{dim}N((A-\lambda I)^n)=n-r,運用秩—零度定理可推論 (A-\lambda I)^n 的秩為

\mathrm{rank}(A-\lambda I)^n=n-\mathrm{dim}N((A-\lambda I)^n)=n-(n-r)=r

毫無疑問地,此題的切入點在於計算 \mathrm{rank}(A-\lambda I)^n,常用的運算方式是以相似轉換替換 A-\lambda I,如下:

A-\lambda I=MKM^{-1}

其中 MK 都是 n\times n 階,且 M 是可逆的,K 相似於 A-\lambda I,又有

(A-\lambda I)^n=(MKM^{-1}) (MKM^{-1})\cdots(MKM^{-1})=MK^nM^{-1}

推知 K^n 也相似於 (A-\lambda I)^n,因為兩相似矩陣有相同的秩,\mathrm{rank}(A-\lambda I)^n=\mathrm{rank}(K^n),原本的問題等價於計算相似矩陣 K^n 的秩。

 
矩陣 K 必須具備何種性質或形式方能簡化 \mathrm{rank}(K^n) 的計算?回答這個問題需要倚靠一點數學直覺,K 起碼要滿足兩個要求。第一,我們希望 K 也是一個上三角矩陣。上三角矩陣的主對角元即為其特徵值,而兩相似矩陣有相同的特徵值集合,如此 K 便保有與 A-\lambda I 相同的主對角元集合。第二,我們希望 K 重新排列 A-\lambda I 的零主對角元,使得零主對角元聚集於左上分塊,稍後我們會發現這麼做的理由是可以有效地簡化計算。例如,

A=\begin{bmatrix}  5&1&2\\  0&8&4\\  0&0&5  \end{bmatrix}

\lambda=5 出現於主對角線 2 次,那麼

A-5I=\begin{bmatrix}  0&1&2\\  0&3&4\\  0&0&0  \end{bmatrix}

矩陣 A-5I2 個零主對角元,我們期望得到的 K 矩陣有以下形式:

K=\begin{bmatrix}  0&\ast&\ast\\  0&0&\ast\\  0&0&3  \end{bmatrix}

上式中 \ast 表示該元可為任何值。

 
如果 K 具有上述兩個條件,便可用分塊矩陣表示為

K=\begin{bmatrix}  B&C\\  0&D  \end{bmatrix}

其中 B(n-r)\times(n-r) 階上三角矩陣,B 的主對角元全為零,B 是冪零分塊其特徵值全為零;Dr\times r 階上三角矩陣,D 有非零的主對角元 (\bullet\neq 0),D 包含非零特徵值:

B=\begin{bmatrix}  0&\ast&\cdots&\ast\\  0&0&\cdots&\ast\\  \vdots&\vdots&\ddots&\vdots\\  0&0&\cdots&0  \end{bmatrix},~D=\begin{bmatrix}  \bullet&\ast&\cdots&\ast\\  0&\bullet&\cdots&\ast\\  \vdots&\vdots&\ddots&\vdots\\  0&0&\cdots&\bullet  \end{bmatrix}

執行分塊矩陣乘法可得

K^n=\begin{bmatrix}  B^n&E\\  0&D^n  \end{bmatrix}

在此並不需要實際計算 (n-r)\times r 階分塊 E,我們真正在乎的是主對角分塊 B^nD^n。以歸納法可證明 B^n=0 (參閱“特殊矩陣 (1):冪零矩陣”),D^n 也是上三角矩陣,其主對角元為 (D^n)_{ii}=(d_{ii})^n\neq 0d_{ii}D 的主對角元,因此 \mathrm{rank}D^n=r,於是有下面的推論結果:

\mathrm{rank}K^n=\mathrm{rank}\begin{bmatrix}  0&E\\  0&D^n  \end{bmatrix}=r

上式等於宣告原題給出的陳述是正確的。

 
最後的棘手問題是如何得到滿足上述兩項要求的分解式 A-\lambda I=M^{-1}KM?亦即如何在不破壞上三角矩陣形式的情況下,排列上三角矩陣的主對角元?有兩個確定可行的方法。第一個方法是矩陣三角化,也稱為 Schur 定理,它說任何方陣 A 都相似於一個上三角矩陣:

T=U^{\ast}AU

其中 U 是么正矩陣 (unitary matrix),U^{\ast}=U^{-1}。計算程序參見“矩陣三角化的 Schur 定理”,以前述 3\times 3 階矩陣 A 為例,

T=\begin{bmatrix}  0&-0.4&2.2\\  0&0&4\\  0&0&3  \end{bmatrix},~ U=\begin{bmatrix}  1&0&0\\  0&0.8&0.6\\  0&-0.6&0.8  \end{bmatrix}

 
第二個方法是 Jordan 形式,任意方陣 A 相似於一 Jordan 形式:

J=M^{-1}AM

J 是具有所謂 Jordan 形式的上三角矩陣,詳細計算程序有些複雜,請見“Jordan 典型形式淺說 (下)”。同樣以上述 A 矩陣為例,JM 分別為

J=\begin{bmatrix}  0&1&0\\  0&0&0\\  0&0&3  \end{bmatrix},~ M=\begin{bmatrix}  1&0&1\\  0&-2&3\\  0&1.5&0  \end{bmatrix}

不論是矩陣三角化得到的 T 或 Jordan 形式 J,我們總是能令零主對角元集中於左上主對角分塊,因此證明了原題陳述。

 
近年大學理工科系多未將矩陣三角化和 Jordan 形式納入基礎線性代數課程內容,所以在我動手解答此題之初便理所當然地認為利用排列相似 (permutation similarity) 轉換就足以重新排列上三角型矩陣的主對角元,算式為 K=P^TAPP 是適當選擇的排列矩陣 (參見“矩陣視覺化”),P^T=P^{-1}。但舉例試了幾回之後才發現此路不通,譬如,我們想將 A 的第 2 個與第 3 個主對角元對調位置,可以執行

P^TAP=\begin{bmatrix}  1&0&0\\  0&0&1\\  0&1&0  \end{bmatrix}\begin{bmatrix}  0&1&2\\  0&3&4\\  0&0&0  \end{bmatrix}\begin{bmatrix}  1&0&0\\  0&0&1\\  0&1&0  \end{bmatrix}=\begin{bmatrix}  0&2&1\\  0&0&0\\  0&4&3  \end{bmatrix}

相似排列轉換雖然按原本預期重新排列了主對角元,但是轉換後的矩陣 P^TAP 無法保持上三角矩陣形式。

 
倘若我們不明瞭 Schur 定理,即矩陣可三角化,又沒學過 Jordan 形式,勢必要尋求其他證明方法。那麼是否還有更簡易的証明方法呢?到目前為止,坦白說,我仍然是一點頭緒也沒有。

 
誌謝 我要特別感謝交大電機系楊春美老師,在我仍然猶疑未定時,她清楚提點「以排列相似轉換排列上三角矩陣的主對角元,同時還要維持上三角矩陣形式──是不可能的事」。

This entry was posted in 線性代數專欄, 典型形式 and tagged , , , , , , , . Bookmark the permalink.

6 則回應給 排列上三角矩陣的主對角元

  1. foremap 說:

    A-\lambda I 是一個上三角形矩陣 我們可以表示為 D+U
    D為對角軸矩陣
    U為上三角矩陣,對角軸皆為0
    \therefore (A-\lambda I)^{n}=(D+U)^{n}=D^{n}+\sum_{x+y=n}^{ }D^{x}U^{y}+U^{n}
    但是 D^{x}U^{y} 必為上三角形矩陣且對角軸為0
    \therefore (D+U)^{n}=D^{n}+U{}' , U{}'也為上三角矩陣,對角軸為0
    因此只要我們知道 rank(A-\lambda I)=n-r , A-\lambda I 是上三角形矩陣
    rank(A-\lambda I)^{n}=n-r 一定會成立
    \therefore N((A-\lambda I)^{n}) 的rank 為r

    所以我們可以得到一個結論
    上三角形乘以n次方 所得的矩陣一定還是上三角形 而且特徵值會是原來的n次方

  2. ccjou 說:

    這麼簡單計算就行?!哈!
    這是你之前寫的解答嗎?為什麼當初我看不懂?誤以為你胡亂寫。
    你寫的展開算式有個錯誤,DUUD 不可交換,所以不存在你寫的簡單形式,但是這不並影響最後結論…
    還有你說 \mathrm{rank}(A-\lambda I)=n-r,而我是假設 \mathrm{rank}(A-\lambda I)=r
    有人在交流區提問 Rayleigh quotient 的問題,找人上去回覆好吧?

  3. foremap 說:

    這不是我之前寫的解答
    我之前誤以為 n次方的結果會只剩一個對角矩陣…(慚愧)

  4. ccjou 說:

    看不懂你說的用高斯消去法,要不然你寫一篇詳細說明上面的解法和其他以相似矩陣的做法, 放入觀點中…

  5. foremap 說:

    剛剛那個我還沒寫完啦XD
    因為寫到一半覺得錯了

  6. foremap 說:

    喔 對了 如果要用相似矩陣做法 也有方法可循
    首先 我門必須用到高斯消去的運算方法
    我們先定義 P這個矩陣 ex:P_{23} 就是第3列加到第2列…等
    P的對角軸為1

    分兩部份 如果A 為一個可逆矩陣 且是上三角形矩陣
    透過高斯消去法 最後一定可以得到一對角矩陣D
    P^{m}P^{m-1}...P^{1}A=D
    先令 P^{m}P^{m-1}...P^{1} = M
    而且rank(A)=rank(D)=rank(MA) (高斯消去不會改變rank)
    A的特徵值 也會和 D相同 (因為是上三角形矩陣)

    OK 知道這件事有什麼用呢? 我們目的是要將對角軸做排序的動作
    原本是希望證明 rank(A^{n})=r , 因為 rank(A) = rank(MA)
    我們如果證明 rank((MA)^{n})=r 那就簡單多了
    如果我們將對角矩陣MA做排序
    P(MA)P^{-1} 這樣我們可以將對角元素任意排列 ps: 此P 為排列矩陣
    令K = P(MA)P^{-1}
    rank((MA)^{n})=rank(K^{n})=rank\begin{bmatrix} 0 & E\\ 0 & D{}'^{n} \end{bmatrix}=r

    如果A 不為一個可逆矩陣
    那 MA 的結果不一定是 對角矩陣D
    但是下面兩個性質能成立
    rank(A)=rank(MA) (高斯消去不會改變rank)
    A的特徵值 也會和MA相同 (因為是上三角形矩陣 又不改變對角軸元素)

    但仍然可以透過 P(MA)P^{-1} 將對角元素任意排列嗎?
    有限制 但一定可以將相同對角元素排在一起 You can try it!
    原因是因為 高斯消去法將很多上三角的元素都變成0了
    所以同理:
    令K = P(MA)P^{-1}
    rank((MA)^{n})=rank(K^{n})=rank\begin{bmatrix} 0 & E\\ 0 & D{}'^{n} \end{bmatrix}=r

    其實我不確定這樣對不對 所以還事先不要放觀點XD

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s