Tag Archives: 排列矩陣

每週問題 March 23, 2015

Posted on 03/23/2015 by ccjou

證明排列矩陣 (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) 矩陣的特徵值

Posted on 10/25/2013 by ccjou

本文的閱讀等級：中級 若一個矩陣 的每一元 為 或 ，我們稱之為 (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

半正定矩陣的判別方法

Posted on 01/10/2013 by ccjou

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

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

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

Posted on 06/08/2012 by ccjou

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

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

PA=LU 分解

Posted on 04/13/2012 by ccjou

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

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

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

Posted on 03/26/2012 by ccjou

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

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

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

Posted on 03/23/2012 by ccjou

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

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

優超關係與雙隨機矩陣

Posted on 05/27/2011 by ccjou

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

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

證明或反駁

Posted on 04/04/2011 by ccjou

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

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

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

Posted on 12/20/2010 by ccjou

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

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