Tag Archives: 排列相似

有向無環圖與 (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

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

本文的閱讀等級:中級 設 為一 階排列矩陣, 的每一行和每一列恰有一個元為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

每週問題 December 27, 2010

這是關於排列相似的基本練習問題。 Pow-Dec-27-10 參考解答 PowSol-Dec-27-10

Posted in pow 特徵分析, 每週問題 | Tagged | Leave a comment

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

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

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

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

本文的閱讀等級:中級 下面這則問題取自 2009 年台大電機工程研究所碩士班入學試題: Let be a linear operator from to itself and . Let denote the null space of . Prove that for every basis of with respect to which has an upper-triangular matrix, appears on the diagonal of … Continue reading

Posted in 線性代數專欄, 典型形式 | Tagged , , , , , , , | 6 Comments

矩陣視覺化

本文的閱讀等級:初級 矩陣通常以其儲存的數字陣列形式呈現,除非是天賦異稟的奇才,一般人很難洞察大尺寸矩陣的內部構造。矩陣視覺化是指利用色彩表示元的數值,雖然並不十分精確,但適合觀察矩陣的分塊結構,具有「見林不見樹」的效果。

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