Tag Archives: 排列矩陣

每週問題 March 23, 2015

證明排列矩陣 (permutation matrix) 的轉置即為其逆矩陣。 A permutation matrix is a matrix that has exactly one 1 in each row and each column, and all entries elsewhere are 0. Show that any permutation matrix is invertible and its inverse is equal to … Continue reading

Posted in pow 線性方程與矩陣代數, 每週問題 | Tagged | 4 Comments

有向無環圖與 (0,1) 矩陣的特徵值

本文的閱讀等級:中級 若一個矩陣 的每一元 為 或 ,我們稱之為 (0,1) 矩陣。2003年任職 Wolfram 研究中心的韋斯坦 (Eric W. Weisstein) 在計算 階 (0,1) 矩陣,,的特徵值時,發現所有特徵值皆為正實數[1]的 (0,1) 矩陣總數為下列序列: 在圖論中,若一個有向圖無法從某個頂點出發經過若干條邊回到該點,則稱之為有向無環圖 (directed acyclic graph,簡稱DAG)。韋斯坦得到的序列恰巧與包含 個標記頂點的有向無環圖數的前五項相等[2]: 自然地,韋斯坦猜想這兩個數列完全相同。圖一顯示 的所有標記有向無環圖。2004年麥凱 (Brendan D. McKay) 等人證明了韋斯坦猜想:包含 個標記頂點的有向無環圖與特徵值皆為正實數的 階 矩陣存在一對一的關係[3]。底下介紹一個精巧的證明。

Posted in 線性代數專欄, 圖論, 應用之道 | Tagged , , , , , , , , | 7 Comments

半正定矩陣的判別方法

本文的閱讀等級:中級 令 為一個 階實對稱矩陣。若任一非零向量 使得二次型 ,我們稱 是正定 (positive definite) 矩陣 (見“特殊矩陣 (6):正定矩陣”)。若任一 皆滿足 ,則 稱為半正定 (positive semidefinite) 矩陣。本文介紹半正定矩陣的一些判別方法。如欲將本文內容推廣至 Hermitian 複矩陣,僅須將實數系 替換為複數系 ,並且將轉置 替換為共軛轉置 即可。

Posted in 線性代數專欄, 二次型 | Tagged , , , , , , , | 2 Comments

矩陣乘積行列式公式的代數證法

本文的閱讀等級:初級 令 和 為 階矩陣。矩陣乘積 的行列式定理,或稱「可乘公式」,如下所示: 。 過去我們曾經討論了三種證明方法:第一種方式最常見於教科書,將 表示成基本矩陣乘積,透過 得證,其中 是任意基本矩陣。第二種方式是基於分塊矩陣運算的簡明證法 (以上兩種證法請見“利用分塊矩陣證明 det(AB)=(det A)(det B)”)。第三種方式則建立於函數 之上 (見“行列式的運算公式與性質”)。本文再介紹一個直接計算矩陣乘積的代數證法,包含三個步驟:先乘開 ,再化簡,最後整理成行列式的乘積。從表面上看,直接計算矩陣乘積及其行列式似乎涉及一定程度的蠻力,至於是否果真如此,請讀者閱畢全文後再自行評斷。

Posted in 線性代數專欄, 行列式 | Tagged , | 3 Comments

PA=LU 分解

本文的閱讀等級:中級 令 是一個 階可逆矩陣。LU 分解 是高斯消去法的一種表達形式,下三角矩陣 記錄消元過程使用的乘數,上三角矩陣 儲存約化結果,其中 和 的主對角元分別滿足 和 (見“LU 分解”)。不過,並非每一可逆矩陣都存在 LU 分解。在執行高斯消去法的化簡程序中,若 出現在軸元 (pivot) 位置,即 元,列取代運算便無法消去軸元底下各元,這時標準 LU 分解不復存在。可逆矩陣 的軸元總數 (即 ) 等於 ,透過列交換運算必能獲得一個 (非零) 軸元,所以仍可繼續下一階段的化簡步驟。從實際面來看,縱使未發生「零軸元」的情況 (軸元所在位置為零),為了避免因不當使用消去法而引發災難,部分軸元法 (partial pivoting) 也會適時地交換列 (見“特殊矩陣 (12):對角佔優矩陣”)。見下例 (取自[1]): 。 從 同時包含數值很小和很大的主對角元可知 不具數值穩定性,也就是說,標準 LU … Continue reading

Posted in 線性方程, 線性代數專欄 | Tagged , , , , | 9 Comments

排列相似的益智遊戲──尋找排列矩陣

本文的閱讀等級:中級 設 為一 階排列矩陣, 的每一行和每一列恰有一個元為1,其餘元為0。排列矩陣是可逆矩陣,且 。一 階矩陣 相似於 ,因為 和 透過排列變換建立相似關係,故稱為排列相似(permutation similar)。明顯地, 僅將 的各個元置換行列並不改變其值。本文要探討的問題是排列相似的益智遊戲:若 排列相似於 ,尋找一排列矩陣 使得 ,如下例(取自2006年台大電機所碩士班入學試題): 。

Posted in 特徵分析, 線性代數專欄 | Tagged , , , | Leave a comment

特殊矩陣 (16):排列矩陣

本文的閱讀等級:中級 一 階矩陣 稱為排列矩陣 (或稱置換矩陣,permutation matrix),若 的每一行和每一列恰有一個元為 ,其餘元為 ,例如: , 明顯地, 也是一排列矩陣。設 ,,則 , 。 左乘排列矩陣和右乘排列矩陣有不同的效果: 將 的列按 2, 4, 1, 3 排序, 則將 的行按 3, 1, 4, 2 排序。寫出 ,配合轉置運算,右乘排列矩陣 可表示為左乘排列矩陣 ,以下限定排列矩陣總是以左乘方式執行。既然每一 階排列矩陣 代表 個元素的一種特別排列,可知冪矩陣 表示連續執行 次排列,所以 也是一排列矩陣。考慮這個問題:試求一 階排列矩陣 … Continue reading

Posted in 特殊矩陣, 線性代數專欄 | Tagged , , , , | 13 Comments

優超關係與雙隨機矩陣

本文的閱讀等級:高級 設 為一 階 Hermitian 矩陣,令 代表 的特徵值。Hermitian 矩陣 的特徵值 皆是實數,所有主對角元 也是實數(見“特殊矩陣(9):Hermitian 矩陣”)。我們知道矩陣跡數等於特徵值之和,也就是說,主對角元之和等於特徵值之和,即 除此之外,特徵值 和主對角元 還具有某種不易察覺的關係,稱為優超(majorization),它不但是研究許多不等式的重要理論,也是探討矩陣不等式的一個強力武器[1,2]。

Posted in 線性代數專欄, 二次型 | Tagged , , , | 3 Comments

證明或反駁

本文的閱讀等級:初級 不論是線性代數或其他數學科目,形式向來凌駕實質內容,學習教材無一不是經過刻意選取裁剪,原因是教學使命在於有效地傳遞知識,而不是訓練如何處理不定情況。然而,證明或反駁命題卻需要多元靈活的思索過程,判斷命題真偽不僅要重組因果邏輯,還必須聯想相關的基本概念,難怪常常我們看得懂書本內容,但就是不曉得如何證明或反駁。看下面這個命題 (取自台大數研所 2011 年碩士班入學試題): 令 和 為 階實矩陣且 ,則 和 至少有一不為可逆矩陣。 請分別就 和 二種情況,證明或反駁此命題。

Posted in 線性代數專欄, 證明細解 | Tagged , , | 1 Comment

利用基本相似變換證明 Jordan 形式定理

本文的閱讀等級:高級 Jordan 典型形式定理是線性代數理論中最艱深的定理之一,它說:任意方陣 都相似於基本 Jordan 分塊直和所構成的 Jordan 矩陣 (見“Jordan 形式大解讀 (上)”)。設 有特徵值 ,我們曾經在“Jordan 形式大解讀 (下)”發展了一個以計算矩陣秩 為基礎的 Jordan 矩陣演算法,並確定 的 Jordan 形式唯一存在(若不考慮 Jordan 分塊的排序變化)。本文介紹一個採用一連串基本相似變換的證明法,它的優點是能夠讓我們清楚看見從矩陣 至其 Jordan 形式 的相似型態演變過程。這個證法雖然已有悠久的歷史,但幾乎不曾出現於教科書中;此法講究靈活運用基本相似變換,整個證明過程類似在解「俄羅斯方塊」,堪稱是線性代數中罕見的一個「益智遊戲」。

Posted in 線性代數專欄, 典型形式 | Tagged , , , , , | Leave a comment