ps.dvi

Transcription

1 線性代數 1 問題集 周志成 這份問題集彙整自 29 年 3 月至 211 年 1 月刊登於 線代啟示錄 的 1 個每週問題 收錄的問題來源甚廣, 有我過去教學使用的演習題, 美國麻省理工學院的考題, 台灣多所大學的研究所入學試題, 以及參考書的練習題 這些問題大都具有解釋基本觀念或彰顯實用技巧的作用, 部分問題可能超越一般基礎線性代數水平, 但我相信演練略為艱深的問題不僅可以刺激思考活動, 鍛鍊推理解析力, 也有鞏固核心觀念的效果 為方便查閱, 本題集按 線性方程式與矩陣代數, 向量空間, 線性變換, 內積空間, 行列式, 特徵分析 與 二次型 編排, 但一些綜合問題不易切割, 此時便依解題過程所最需要聯繫的概念和方法歸類 由於時間倉促, 未及逐題校閱, 內容或有錯誤, 期待讀者提出批評與改進意見, 來日再版時將一併訂正 作者任教於國立交通大學電機工程系 見參考文獻 1

2 線性方程式與矩陣代數 Problem 1 In each part solve the matrix equation for X. (a) 1 1 X 1 1 = (b) AXB = C given that 1 4 A = 2 3, B = , C = (a) 因為未知矩陣 X 出現於係數矩陣的左邊, 我們可以將整個矩陣方程式轉置以便得出 如 Ax = b 的線性方程基本形式 : XT = 此矩陣方程式等價於二個係數矩陣相同的線性方程式, 將方程式等號右端的兩個常數 向量併入 3 3 階係數矩陣, 再以消去法將 3 5 階增廣矩陣化簡至最簡列梯形陣 式 (reduced row echelon form), 如此一來只需要進行一回計算程序便可解出二方 程式 消去法的化簡過程如下 :

3 最簡列梯形矩陣的右末二行即為 X T 的解, 取轉置可得 X = 6 1 (b) 首先判斷出 X 是 2 2 階矩陣, 直覺的做法是設 X 的 4 個未知元為 x,y,z,w, 進 行二次矩陣乘法運算將 AXB = C 乘開, 改寫成標準形式的線性方程式後再以消去 法求解 不過, 這樣做會產生 9 個一次方程式, 計算時很容易出錯 另一個方法是將求解程序分解成二個步驟, 令 Y = XB, 由方程式 AY = C 先解出 Y, 然後由方程式 XB = Y 解出 X 以下說明第二個做法 為求解 Y, 類似題 (a) 的做法, 我們可以一次解出三個方程式, 利用消去法化簡增廣矩陣 [ A C ], 得到 將最簡列梯形矩陣用分塊矩陣表示為 I 2 D, 並設 E 為消去法所執行過所有的 基本矩陣乘積, 由分塊矩陣乘法可得 [ ] [ ] E A C = EA EC = I 2 D 上式指出 EA = I 2, 因此 EC = EAY = I 2 Y = Y, 但上面的分塊 乘積顯示 EC = D, 這說明了分塊 D 即為 Y, 因此 Y =

4 Problem 2 接下來的工作是求解方程式 XB = Y 將方程式轉置可得 B T X T = Y T, 同樣以消 去法化簡增廣矩陣 [ B T Y T ], 過程如下 : 與前一個步驟的道理相同, 由得出的分塊可知 X T = X = , 所以 Let A = Determine the LU decomposition P A = LU, where P is the associated permutation matrix. 我們設計一個演算流程來紀錄高斯消去法的執行過程與結果, 包括下三角形矩陣 L = [l ij ] 所儲存的乘數 l ij, i > j, 排列矩陣 P 的列排序, 以及上三角形矩陣 U = [u ij ], i j 方法是在最右側加入一行代表列排序, 初始值設為 (1,2,3,4), 並於消去法產生的梯形矩陣零元位置填入取代運算所使用的乘數, 在該元底下加註一直線以利辨識 注意, 消去法的取代 4

5 和縮放運算不會計算代表列排序的最右行與儲存的乘數 ( 即加註底線的元 ), 詳細過程如下 : /3 5 4 所以得到 L = /3 1, U = , P = Problem 3 An n n matrix A is called idempotent if A 2 = A. (a) Show that if A is idempotent and invertible, then A = I. (b) Describe all 2 2 real idempotent matrices. (c) If A is idempotent, find the inverse of I ca (if possible) for some scalar c. 5

6 (a) 令 A A 2 = 左乘 A 1 便有 A 1 (A A 2 ) = A 1 A A 1 AA = I A =, 得出 A = I (b) 2 2 階矩陣的秩可能為 2, 1,, 以下分別考慮這三種狀況 若 ranka = 2, A 是可逆的, 由題 (a) 可知 A = I 若 ranka = 1, A 總是可寫成 A = uv T, 而且 A 2 = uv T uv T, 比較兩式得知 u, v 要滿足 v T u = 1, 例如, u = 2, v = 2, A = 若 ranka =, 顯然 A = (c) 由於 A 2 = A, 矩陣 A 的二次多項式總能變換為一次多項式, 可以嘗試計算 (I ca)(i da) = I ca da + cda 2 = I + (cd c d)a 若 cd c d =, 即 d = c c 1, 解出逆矩陣 (I ca) 1 = I c c 1 A 此式成立的條件為 c 1 Problem 4 Answer the following questions. (a) Show that if A and A + B are invertible, then I + BA 1 is also invertible. (b) If A, B, and A+B are invertible, express (A 1 +B 1 ) 1 in terms of A, B, and A + B. (c) Suppose that a square matrix A satisfies A 2 3A+I =. Find the inverse of A. (d) Suppose that I + A is invertible and B = (I + A) 1 (I A). Show that I + B is also invertible. 6

7 (a) 我們可以試探性地令矩陣 I +BA 1 與某些矩陣相乘, 以得出單位矩陣 依序右乘 A 及 (A + B) 1, 那麼 (I + BA 1 )A(A + B) 1 = (A + B)(A + B) 1 = I, 得到 (I + BA 1 ) 1 = A(A + B) 1 (b) 可設法將矩陣加法 A 1 +B 1 表示成數個可逆矩陣的乘積, 再運用逆矩陣性質 (XY Z) 1 = Z 1 Y 1 X 1 來完成計算 經過初步嘗試後發現 A 1 (A + B)B 1 = (I + A 1 B)B 1 = B 1 + A 1 應用上述逆矩陣乘積性質得 (A 1 + B 1 ) 1 = B(A + B) 1 A (c) 將單位矩陣 I 從給出的方程式 A 2 3A + I = 移至等號的一端, 另一端可提出公 因子 A, 即得 所以 A 1 = 3I A I = A 2 + 3A = A( A + 3I) (d) 首先要知道關鍵在於去除等式 B = (I + A) 1 (I A) 裡面的 (I + A) 1, 可直接 Problem 5 於上式左端通乘 I + A, 就得到 (I + A)B = I A, 整理為 AB + A + B = I, 接 著進行因式分解以分離出 I + B, 於是有 (I + A)(I + B) = 2I, 由此解出 (I + B) 1 = 1 (I + A) 2 Let x be a vector in R 3 satisfying x T x = 1. (a) Find a vector x such that (I 3 2xx T ) = 7

8 (b) If possible, find a vector x such that 1 1 (I 3 2xx T ) 3 = 2 Otherwise, give a reason why there is no such x. 我們使用符號運算來考慮一般的情況, 先將問題重述如下 : 已知 b,c R 3, 求單位向量 x ( x 2 = x T x = 1) 使滿足 (I 2xx T )b = c 乘開得到 (I 2xx T )b = b 2(x T b)x = c 方程式中出現了二個未知向量 x, 表面上似乎增加求解的困難度 由於 b, c 是已知的, 移項改寫為 2(x T b)x = b c, 可知 x 與 b c 共線, 因此設 x = k(b c), 再代回上面的方程式得到 2k 2 (b c) T b(b c) = b c 又因 x 不為零向量, 亦即 b c, 上式等價於 2k 2 (b c) T b = 1, 且若 (b c) T b >, 便有 1 k = ± 2(b c) T b 於是解出 1 x = ± (b c) 2(b c) T b 另外, 此題要求 x T x = 1, 因此 b, c 必須滿足 2(b c) T b = (b c) T (b c), 乘開整 理得到條件 b = c (a) 首先查驗 b = c = 1, 再將數值代入計算得到 k = ± 3 2, 因此 1 x = ± (b) 因為 b = 14, 而 c = 1, 這不符合解存在的必要條件, 故此題無解 8

9 Problem 6 Let B be a skew-symmetric matrix, B T = B. If A = (I + B)(I B) 1 prove that A is an orthogonal matrix. 利用已知 B T = B, 計算 A T = ( (I + B)(I B) 1) T = (I B T ) 1 (I + B T ) = (I + B) 1 (I B) 因為 (I B)(I + B) = (I + B)(I B), A T A = (I + B) 1 (I B)(I + B)(I B) 1 = (I + B) 1 (I + B)(I B)(I B) 1 = I 證得 A T = A 1 Problem 7 Suppose that A is an n n matrix such that for some k >, A k =. Such matrices are called nilpotent. (a) Show that A is not invertible. (b) Show that I A is invertible. (c) If the matrices A and B commute, show that I + AB is invertible. Note that B may not be nilpotent. 9

10 (a) 可以用反證法證明 假設 A 是可逆的, 則有 AA 1 = I, 那麼 A k (A 1 ) k = (A A) (A 1 A 1 ) }{{}}{{} k k = } A {{ A} (AA 1 )A} 1 {{ A 1 } k 1 k 1 = A k 1 (A 1 ) k 1 重複上述步驟可歸納得 A k (A 1 ) k = AA 1 = I 但已知 A k =, 因此 (A 1 ) k 不可能存在, 出現了矛盾的結果, 顯然最初的假設是錯的 另一個做法是運用行列式性質直接證明 計算 A k 的行列式值 det(a k ) = det(a) det(a) = det(a) k }{{} k 由於 det(a k ) = det() =, 可知 det(a) =, 證得 A 不是可逆的 (b) 直接求出 I A 的逆矩陣便可以證明此命題成立 問題的重心在於存在 k >, 使 A k =, 我們於是產生了聯繫 A k 與 I A 的想法 注意以下的因式分解公式 : 1 x k = (1 x)(1 + x + x x k 1 ) 對應的矩陣多項式則為 I A k = (I A)(I + A + A A k 1 ) 從已知條件 A k = 推得 (I A)(I + A + A A k 1 ) = I, 這表明 I A 是可逆的, 而且 (I A) 1 = I + A + A A k 1 (c) 可以運用題 (b) 的方法 當 k 是奇數時, 考慮下面的因式分解公式 : 1 + x k = (1 + x)(1 x + x 2 + x k 1 ) 1

11 應用於矩陣的情況, 也就有 I + (AB) k = (I + AB)(I AB + (AB) 2 + (AB) k 1 ) 剩下的工作是計算 (AB) k 因為問題給出 BA = AB, 就有 (AB) k = AB(AB) k 1 = A(BA)B(AB) k 2 = A(AB)B(AB) k 2 = A 2 B 2 (AB) k 2 繼續重複上述步驟可歸納出 (AB) k = A k B k, 但 A k =, 所以 (AB) k =, 故推知 I + AB 是可逆的 如果滿足 A k = 的 k 是偶數, 可令 m = k + 1, 則 (AB) m = (AB) k (AB) =, 將上述論證的 k 改為 m, 再分解 I + (AB) m 為因式, 仍然可以證明原命題成立 Problem 8 Let A be an n n matrix. If A 2 =, show that I A is nonsingular. 最直接的方法是求出 I A 的逆矩陣, 利用已知條件可得 (I A)(I + A) = I A 2 = I 因此, (I A) 1 = I + A 第二個做法是從子空間著手, 如果能證得 I A 的零空間僅包含零向量, 即證出所求 設 (I A)x =, 亦即 x = Ax, 等號兩邊同乘 A, 就有 Ax = A 2 x =, 推知 x = 此外, 還可以利用特徵值來證明 : 若 I A 不包含零特徵值, 則 I A 是可逆的 設 Ax = λx, 則 A 2 x = λ 2 x =, 因為 x, 得知 λ =, A 的所有特徵值為, 稱為冪零矩陣 計算 (I A)x = x λx = x, 可知 I A 有重複 n 次的特徵值 1, 因此為可逆矩陣 Problem 9 Let A be an n by n real symmetric matrix, and s(a) be the sum of all entries of A. Prove that s(a 2 ) (s(a))2 s(i n ) 11

12 展開 A 2 並將所有元加總, s(a 2 ) = n n n a ik a kj i=1 j=1 k=1 已知 A 是對稱矩陣, 對於任意 i, k, a ik = a ki, 交換加總順序就得到 n n n s(a 2 ) = a ki a kj = = = k=1 ( n n k=1 i=1 j=1 i=1 a ki ) ( n n ) 2 a ki k=1 n k=1 ρ 2 k i=1 n j=1 a kj 上式中我們令 ρ k = n i=1 a ki 利用 Cauchy-Schwarz 不等式, ( n n ) 2 ρ 2 k 1 ρ k = (s(a))2 n s(i n ) k=1 k=1 另外也可以使用精簡的符號推導, 令 1 = (1,1,...,1), 則 利用 Cauchy-Schwarz 不等式, s(a 2 ) = 1 T A 2 1 = 1 T A T A1 = (A1) T (A1) = A1 2 (s(a)) 2 = (1 T A1) A1 2 = n A1 2 合併上面兩式即證得所求 Problem 1 Let A and B be n n matrices. Prove that if AB =, then for every positive integer k, trace(a + B) k = tracea k + traceb k 12

13 考慮展開式 (A + B) k = A k + ka k 1 B + + kab k 1 + B k 注意, (A+B) k 包含四種不同類型的項, 即 A k, B k, A m B k m, 以及 B m A k m, m 1 因為 AB =, 可知 A m B k m = A m 1 (AB)B k m 1 = 利用跡數性質 trace(xy ) = trace(y X), 其中 XY 和 Y X 為方陣, 就有 trace(b m A k m ) = trace(a k m B m ) = trace = 對上面展開式等號兩邊取跡數可得 trace(a + B) k = trace(a k + B k ) = tracea k + traceb k 最後一個步驟使用了矩陣加法的跡數性質, trace(x + Y ) = tracex + tracey, X 和 Y 為方陣 Problem 11 For n n matrices A and B, the commutator of A and B is defined by [A,B] AB BA. Show that (a) [A,B] T = [B T,A T ] (b) [A,[B,C]] + [B,[C,A]] + [C,[A,B]] = (c) trace[a,b] = (d) [A,B] is never similar to the identity matrix. (e) If the diagonal entries of A are all equal to zero, then there exists matrices U and V such that A = [U,V ]. (a) 代入計算並展開 [A,B] T = (AB BA) T = B T A T A T B T = [B T,A T ] 13

14 (b) 直接計算 [A,[B,C]] + [B,[C,A]] + [C,[A,B]] = A(BC CB) (BC CB)A + B(CA AC) (CA AC)B + C(AB BA) (AB BA)C = (c) 利用跡數性質計算 trace[a,b] = trace(ab BA) = trace(ab) trace(ba) = trace(ba) trace(ba) = (d) 利用題 (c) 結果, trace[a,b] =, 但 tracei = n, 推知 [A,B] 和 I 的特徵值不相同, 故 [A,B] 不相似於 I (e) 如不加入限制直接解方程式 A = [U,V ] = UV V U, 可以想像其過程十分繁雜 先選擇一種特殊形式的 U 矩陣, 例如下面的主對角矩陣 1 2 U =... n 以元為計算單位展開 A = [U,V ] = UV V U, 比較等號兩邊得到 a ij = iv ij v ij j = (i j)v ij 因此若 i j, 可設 v ij = a ij /(i j), 若 i = j, 則 v ij =, Problem 12 Suppose A is m m, U is m n, V is n m, and D is n n. The following questions relate to the inverse of the block matrix A U. V D 14

15 (a) Suppose A is invertible. Find W, X, Y, and Z satisfying W A U = I m Y X I n V D Z (b) Suppose Z is invertible. Find the inverse of I m Y. Z (c) Use the results of (a) and (b) to compute the inverse of A U. To have V D this result, what assumptions of the matrix invertibility should be made? (d) An alternative way to derive the inverse of a block matrix is to start with I m X A U = Z W V D Y I n Follow the steps described in (a), (b), (c) and then derive a new formula for the inverse of the block matrix A U. By equating the (1,1) entry V D of the obtained inverse and that obtained in (c), show that (A UD 1 V ) 1 = A 1 + A 1 U(D V A 1 U) 1 V A 1 (e) By the formula in (d), derive a formula for (A + uv T ) 1. (f) By the formula in (d), show that (A + UBV ) 1 = A 1 A 1 U(I + BV A 1 U) 1 BV A 1 15

16 (a) 給出的矩陣方程式其用意在於將分塊矩陣轉換為上三角形矩陣, 因此不難解出其中的 未知分塊 以分塊矩陣乘法展開, 得到以下四式 : WA = I m XA + I n V = WU = Y XU + I n D = Z 已知 A 是可逆矩陣, 可依序解出 W = A 1 X = V A 1 Y = A 1 U Z = D V A 1 U (b) 類似一般矩陣性質, 分塊上三角矩陣的逆矩陣仍為分塊上三角矩陣, 故考慮 I m Y I m P = I m Z Q I n 展開後, 由分塊矩陣的第二行取出等式 : I m P + Y Q = ZQ = I n 因 Z 是可逆的, 便有 Q = Z 1, P = Y Q = Y Z 1, 所求的逆矩陣為 1 I m Y = I m Y Z 1 Z Z 1 (c) 由題 (a) 可知以下關係式 : A 1 V A 1 I n A U = I m A 1 U V D D V A 1 U 16

17 利用題 (b) 求得之上三角形分塊矩陣的逆矩陣公式, 將上式同時左乘等號右端矩陣之 逆矩陣, 便得到 A U 1 = I m A 1 1 U A 1 V D D V A 1 U V A 1 I n = I m A 1 U(D V A 1 U) 1 A 1 (D V A 1 U) 1 V A 1 I n = A 1 + A 1 U(D V A 1 U) 1 V A 1 A 1 U(D V A 1 U) 1 (D V A 1 U) 1 V A 1 (D V A 1 U) 1 此式成立的條件是 A 和 D V A 1 U 都是可逆的 (d) 設 D 是可逆的, 重複前題的步驟可得另一分塊逆矩陣, 如下 : A U V D 1 = (A UD 1 V ) 1 (A UD 1 V ) 1 UD 1 D 1 V (A UD 1 V ) 1 D 1 V (A UD 1 V ) 1 UD 1 + D 1 此式與題 (c) 的逆矩陣相等, 比較 (1,1) 元即可得所求公式 (e) 設 D = 1, U = u, V = v T, 代入題 (d) 給出的公式, 可知 (A + uv T ) 1 = A 1 + A 1 u( 1 v T A 1 u) 1 v T A 1 = A 1 A 1 uv T A v T A 1 u 上式成立的要件是純量 1 + v T A 1 u 不得為零 (f) 設 B = D 1, 亦即 D = B 1, 再代入題 (d) 的公式, 便有 (A + UBV ) 1 = A 1 A 1 U(B 1 + V A 1 U) 1 V A 1 由等式 B(B 1 + V A 1 U) = I + BV A 1 U, 可得 (B 1 + V A 1 U) 1 = (I + BV A 1 U) 1 B, 故 (A + UBV ) 1 = A 1 A 1 U(I + BV A 1 U) 1 BV A 1 注意, 此公式假設 A 和 I + BV A 1 U 是可逆矩陣 17

18 Problem 13 Suppose A and B are n n matrices, and B is not nilpotent. If AB + BA =, then AX + XA = B has no solution. Note that an n n matrix A is called nilpotent if A k = for some positive integer k. 令 k 為任意正整數, 重複使用 2k 1 次 AB = BA, 可得 AB 2k 1 = (AB)B 2k 2 = BAB 2k 2 = B 2 AB 2k 3 = = B 2k 1 A 接者使用反證法, 如果 B = AX + XA, 利用上式就有 B 2k = (AX + XA)B 2k 1 = AXB 2k 1 + XAB 2k 1 = AXB 2k 1 XB 2k 1 A 計算 traceb 2k = trace(axb 2k 1 XB 2k 1 A) = trace(axb 2k 1 ) trace(xb 2k 1 A) = trace(axb 2k 1 ) trace(axb 2k 1 ) = 令 B 的特徵值為 λ i, i = 1,2,...,n, 根據跡數 (trace) 與特徵值關係, 就有 traceb 2k = n i=1 λ 2k i = 因為 k 是任意正整數, 這說明 λ i =, i = 1,2,...,n, 換句話說, B 為冪零矩陣, 這與原 命題矛盾 18

19 向量空間 Problem 14 Let S = 1 1 2, 1 2 Find an extension vector set T from R 4 so that S T form a basis for R 4. 使用嘗試錯誤法並不難求出一組基底, 但問題在於如何以系統化方式計算擴展向量集 T 想法是藉助列梯形矩陣分辨線性獨立向量的能力, 將標準基底向量 e 1,...,e 4 併入給定的向量集 S 構成一增廣矩陣 A, 再將 A 化簡至列梯形矩陣, 如下 : 此結果顯示 A 的第 1, 2, 4, 5 行是線性獨立的, 故擴展向量集可為 T = 1, 1 19

20 Problem 15 Suppose A is a 3 4 matrix. The block matrix [ A I 3 ] is reduced by row operations to (a) Find a basis for the row space of A. (b) Find a basis for the nullspace of A. (c) Find a basis for the left nullspace of A. (d) Find a basis for the column space of A. 為方便推理, 我們考慮一般的情況 設 A 為 m n 階矩陣, 又設 m m 階矩陣 E 代表 消去法所執行的基本矩陣乘積, 因此有 [ ] [ ] [ ] E A I m = EA EI m = R E 其中 m n 階矩陣 R = EA 為 A 的最簡列梯形矩陣 當 A 的秩等於 r 時, 記為 ranka = r, 在不失一般性原則下, 以分塊形式將 R 表示如下 : R = I r F r (n r) 階分塊 F 由對應非軸行的係數所構成 令 E = E 2 為 (m r) m 階, 化簡後的分塊矩陣可以進一步分解為 [ ] R E = I r F E 1 E 2 E 1 E 2, E 1 為 r m 階, 以此題給出的數值為例, ranka = 2, F = 2 1, E 1 = 2 1 [ ], E 2 =

21 注意, 分塊 F 和 E 2 為描述矩陣 A 的四個基本子空間提供的充分的資訊 (a) 列運算不改變矩陣的列空間, 因此 C(A T ) = C(R T ), 由於 R 的非零列是線性獨立 的, 因此可以作為 A 的列空間基底向量, 亦即分塊 [ I r [1,2,1,] T, [,,,1] T F ] 的列 故此題答案為 (b) 列運算不改變矩陣的零空間, 齊次方程式 Ax = 和 Rx = 有相同的解集合, 故 其零空間相同 N(A) = N(R) 由已知的 R 矩陣, 可確定零空間矩陣 (nullspace matrix) 為 N = F I n r 滿足 RN = 由於 N 的行向量是線性獨立的, A 的零空間基底可為 N 的行向量 由給出的 R 可知 N = 1 所以 A 的零空間基底包含向量 [ 2,1,,] T, [ 1,,1,] T (c) 矩陣 A 其左零空間中的向量 y 滿足 A T y = 或 y T A = T 因為 EA = E 1 A = I r F = R E 2 便有 E 2 A =, 這說明了 E 2 的各列都屬於 A T 的零空間, 又由於基本矩陣乘積 E 是可逆的, 故包含線性獨立的列, E 2 的列便可組成 A T 的零空間基底 此題答案為 [1, 2,1] T (d) 列運算改變了矩陣的行空間, C(A) C(R), 由最簡列梯形矩陣 R 不可能推論出 A 的行空間, 但從題 (c) 得到的左零空間 N(A T ) 仍提供足夠的資訊以描述 C(A) 設矩 陣 B 其各列為 A T 的零空間基底向量, 由題 (c) 得知 B = E 2, 也就有 C(B T ) = N(A T ), 利用子空間的正交互補關係, C(A) = N(A T ) 和 C(B T ) = N(B), 可推知 C(A) = N(B), 表明了 A 的行空間其實就是 B 的零空間 由前題結果, 21

22 B = [ ], B 已經為最簡列梯形陣式, 其零空間由 [2,1,] T 和 [ 1,,1] T 所擴張而成, 此即為 A 的行空間基底向量 另一個做法是直接求矩陣 A, 不過這個方法的計算量稍大 由式 EA = R, 同時左乘 E 1 得到 A = E 1 R, 如下 : A = = 最簡列梯形矩陣 R 的第 1, 4 行為軸行, 可知 A 的第 1, 4 行可為行空間基底 : [1,1,1] T 和 [1,2,3] T Problem 16 Consider the following matrices: A = , B = Determine if A and B have the same column space, row space, nullspace, or left nullspace. 若 A 列等價於 B, 則 A 和 B 有相同的最簡列梯形矩陣 (reduced row echelon form), 因此有相同的列空間與零空間 同樣道理, 若 A T 列等價於 B T, 則 A T 和 B T 有相同的最 簡列梯形矩陣, 也有相同的行空間與左零空間 分別以基本列運算化簡 A, B 得到 A B

23 A 和 B 的最簡列梯形矩陣不同, 推知 C(A T ) C(B T ), N(A) N(B) 再計算化簡 A T, B T : A T B T A T 和 B T 的最簡列梯形矩陣相同, 推知 C(A) = C(B), N(A T ) = N(B T ) Problem 17 If possible construct a 3 3 real matrix A with the following properties: (a) A is a symmetric matrix. Its row space is spanned by the vector [1,1,2] T and its column space is spanned by the vector [1,2,3] T. (b) All three of these equations have no solution but A : Ax = e 1, Ax = e 2, Ax = e 3 where e 1 = [1,,] T, e 2 = [,1,] T, e 3 = [,,1] T. (c) The vector [1,1,1] T is in the row space of A but the vector [1, 1,] T is not in the nullspace of A. (a) 矩陣 A 的列空間以及行空間僅由一個向量擴張而成, 表示 ranka = 1 任意秩為 1 的矩陣可表為 A = uv T, 由給出的向量可知 A = k 2 [ ] = k 其中 k, 所以不存在滿足此條件的對稱矩陣 23

24 (b) 只要設法使 e 1, e 2, e 3 都不在 A 的行空間內即可, 例如, A = (c) 矩陣的零空間和列空間正交, 但因為 [1,1,1] T 正交於 [1, 1,] T, 列空間不能僅由 [1,1,1] T 擴張而成, 否則 [1, 1,] T 便於零空間內, 這與題意不符 克服此障礙的方式是讓列空間再增加一個不與 [1, 1,] T 正交的基底向量, 例如, A = 1 1 此矩陣的零空間由向量 [, 1,1] T 所擴張, 不包含 [1, 1,] T Problem 18 Suppose that U and W are two subspaces in R 4. The subspace U is spanned by u 1 = [1,1,,] T and u 2 = [1,,1,] T, and the subspace W is spanned by w 1 = [,1,,1] T and w 2 = [,,1,1] T. (a) Find a basis for the sum U + W. (b) Find a basis for the intersection U W. (c) Explain why the following relation is correct. dimu + dimw = dim(u + W) + dim(u W) (a) 令矩陣 A 的行向量依序為 u 1,u 2,w 1,w 2, 則子空間之和 U +W = span(u W) 即為 A 的行空間 以下使用標準程序找尋 A 的行空間基底, 以消去法化簡得到梯形 24

25 陣式 : A = 得知 U + W 的基底向量為 A 的軸行, 即 1, 2, 3 行 : 1 1, 1 1, 1 1 (b) 最簡單計算子空間交集 U W 的做法是求題 (a) 的 A 之零空間 N(A) 任何 x N(A) 滿足 Ax =, 或寫成向量方程式 x 1 u 1 + x 2 u 2 + x 3 w 1 + x 4 w 2 = 進一步將 u i 和 w i 分離 : x 1 u 1 + x 2 u 2 = x 3 w 1 x 4 w 2 等號左邊的向量屬於 U, 而等號右邊的向量屬於 W, 所以此向量屬於 U W 由題 (a) 結果, 可繼續化簡 A 至最簡列梯形矩陣, 如下 : 由最簡列梯形矩陣得知 A 的零空間由 [1, 1, 1,1] T 擴張, 子空間交集 U W 的基底向量也就是 1 u 1 + ( 1) u 2 = =

26 (c) 題 (a) 與題 (b) 結果提供了 U + W 和 U W 的維度, ranka = dim(u + W), dimn(a) = dim(u W) A 的行向量總數為 dimu + dimw, 從秩 零度定理推知 dimn(a) + rank(a) = dimu + dimw, 因此證得 dimu + dimw = dim(u + W) + dim(u W) Problem 19 Let W 1 and W 2 be two subspaces in vector space V. Show that the following two statements are equivalent. (a) W 1 W 2 = {}. (b) dim(w 1 + W 2 ) = dimw 1 + dimw 2 (a) (b) 若 (a) 成立, 設 {x 1,...,x m } 為 W 1 的一組基底, {y 1,...,y n } 為 W 2 的一組基底, 因為 W 1 W 2 = {}, 向量集 {x 1,...,x m,y 1,...,y n } 構成 W 1 + W 2 的一組基底, 所以 dim(w 1 + W 2 ) = m + n = dimw 1 + dimw 2 (b) (a) 利用反證法, 若 (b) 成立且假設 W 1 W 2 {} 設 {z 1,...,z k } 為 W 1 W 2 的一組基底, 將向量集 {z 1,...,z k } 擴增成 W 1 和 W 2 的基底, 分別為 {z 1,...,z k,x 1,...,x m } 和 {z 1,...,z k,y 1,...,y n }, 因此 dimw 1 = k+m, dimw 2 = k+n, 而 dim(w 1 +W 2 ) = k + n + m 當 k >, 就有 dim(w 1 + W 2 ) < dimw 1 + dimw 2 這與 (b) 矛盾, 因此必定有 k =, 這指出 W 1 W 2 = {} Problem 2 Prove that the intersection of three 6-dimensional subspaces in R 8 is not the single point {}. 26

27 想法是先限制二個子空間交集的維度, 然後延伸推論出三個子空間交集維度的範圍 令 U, V, W 為 R 8 內的子空間, 且 dimu = dimv = dimw = 6 因為 U + V 仍屬於 R 8, 便有 dim(u + V ) 8, 再由關係式 dim(u + V ) = dimu + dimv dim(u V ) 得知 6+6 dim(u V ) 8, 所以 dim(u V ) 4, 同理可以得到 dim(v W) 4 再次引用前述性質 dim((u V ) + (U W)) = dim(u V ) + dim(u W) dim(u V W) 但是 (U V ) + (U W) U, 故 dim((u V ) + (U W)) 6, 因此 dim(u V ) + dim(u W) dim(u V W) 6 引用 dim(u V ) 4, dim(v W) 4, 上面不等式就為 dim(u V W) dim(u V ) + dim(u W) = 2 從而得知 U, V, W 的交集不可能為零向量 Problem 21 Let A = 2 2, B = (a) Find the intersection of the nullspace of A and the nullspace of B. (b) Find the intersection of the column space of A and the column space of B. 27

28 (a) 設 x N(A) N(B), 因此有 Ax = 與 Bx =, 合併二式成為 A x = B, 零空間交集 N(A) N(B) 即為分塊矩陣 A 的零空間 以消去法化簡 B 分塊矩陣至最簡列梯形矩陣, 如下 : 分塊矩陣的秩與其行數相等, 這說明 A 的零空間與 B 的零空間交集為 {} (b) 行空間的交集較為困難求得, 原因是行空間可以由許多不同的基底擴張而成, 因此最 直覺的解法是將行空間改以零空間形式表示 先將矩陣 A, B 的行空間轉換為矩陣 D, E 的零空間, 再按題 (a) 方式求其交集 以 N(A T ) 的基底向量設為 D 的列, 便 有 C(D T ) = N(A T ), 利用子空間的正交互補關係 C(A) = N(A T ), 故 C(A) = C(D T ) = N(D) 同理, 以 N(B T ) 的基底向量設為 E 的列, 則有 C(B) = N(E) 以下分別將 A T 與 B T 的零空間找出 : A T = B T =

29 取整數可設 D = [ ], E = [ ] 下一步是計算分塊矩陣 D E 的零空間, 以消去法進行化簡, 可得 D 與 E 的零空間交集由向量 [, 2,1] T 所擴張, 這便是 A 和 B 行空間其交集的 基底向量 Problem 22 Suppose A is m by n, and ranka = r. Let E = E 1 be a nonsingular matrix such that EA = B E 2 where B is r by n, and B is in row echelon form. Prove that C(A) = N(E 2 ), where C(A) is the column space of A, and N(E 2 ) is the nullspace of E 2. 欲證明 C(A) = N(E 2 ), 我們可以分別證明 C(A) N(E 2 ) 和 N(E 2 ) C(A) 由 E 1 A = B, 得知 E 2 A =, A 的行向量屬於 E 2 的零空間, 故 C(A) N(E 2 ) E 2 設 b N(E 2 ), 就有 Eb = E 1 b = E 1b = c E 2 E 2 b [ ] 其中 c = E 1 b 是 r- 維向量 考慮增廣矩陣 A b, 則 [ ] [ ] E A b = EA Eb = B c [ ] 上式給出 rank A b = ranka = r, 故方程式 Ax = b 是一致的, 因此 b C(A), 這 證明了 N(E 2 ) C(A) 29

30 Problem 23 Let A be an n by n nilpotent matrix of index k, i.e., k is the smallest positive integer such that A k =. If x is a vector such that A k 1 x, show that the set {x,ax,a 2 x,...,a k 1 x} is linearly independent. 考慮向量集的線性組合 c 1 x + c 2 Ax + + c k A k 1 x = 將上式左乘 A k 1, 利用性質 A j =, j k, 就有 c 1 A k 1 x + c 2 A k x + + c k A 2k 2 x = c 1 A k 1 x = 由已知 A k 1 x 斷定 c 1 =, 因此 c 2 Ax + c 3 A 2 x + + c k A k 1 x = 再將上式左乘 A k 2, 同樣可以推論 c 2 =, 就得到 c 3 A 2 x + + c k A k 1 x = 重複進行上述步驟可以證得 c i =, i = 1,...,k Problem 24 Let {v 1,...,v n } be a basis for a vector space V and n 2. Is the set {v 1 + v 2,v 2 + v 3,...,v n 1 + v n,v n + v 1 } also a basis for V? 設 c 1 (v 1 + v 2 ) + c 2 (v 2 + v 3 ) + + c n (v n + v 1 ) = 3

31 展開整理成 (c 1 + c n )v 1 + (c 1 + c 2 )v (c n 1 + c n )v n = 於是有以下齊次線性方程組 : c 1 + c n =, c 1 + c 2 =,..., c n 1 + c n =, c i 存在非平凡解的充要條件為 = 1 + ( 1) n+1 = 若 n 為偶數, c i 有不全為零解, 給出的向量集不可作為 V 的基底 ; 若 n 為奇數, c i =, i = 1,...,n, 向量集可為 V 的基底 Problem 25 Vandermonde matrices are descirbed by V = 1 x 1 x 2 1 x n x 2 x 2 2 x n x m x 2 m xn 1 m in which x i x j, for all i j. Show that if n m, the columns of V are linearly independent. 考慮齊次方程 1 x 1 x 2 1 x n x 2 x 2 2 x n x m x 2 m x n 1 m c c 1 c 2. c n 1 =. 31

32 對於 i = 1,2,...,m, 也就有 c + c 1 x i + c 2 x 2 i + + c n 1x n 1 i = 這指出多項式 p(x) = c + c 1 x + c 2 x c n 1 x n 1 有 m 個相異根, x i, i = 1,2,...,m 根據代數學基本定理, (n 1) 階多項式 p(x) 至多存在 (n 1) 個相異根, 但已知 n m, 上述齊次方程成立的條件必須是 c = c 1 = = c n 1 =, 因此證得 V 的行向量是線性獨立的 Problem 26 If A is an m n matrix and B is an n p matrix, prove that ranka + rankb n rankab This is called Sylvester s inequality. 我們從秩 零度定理下手, 即 dim N(A) = n ranka 如果能夠證明 rankb rankab dim N(A) 等於證得給出的命題為真 關鍵想法是要聯繫 rankb 和 rankab, 考慮這個情境 : 設線 性轉換 T : C(B) C m, 也就是說 T 的定義域為 C(B), 對於 x C(B), 其像為 T(x) = Ax, 也可以說 T(y) = ABy, 但 y C p 秩 零度定理的線性轉換語言陳述為 dim ima(t) + dim ker(t) = dim C(B) 但是 dim ima(t) = dim C(AB) = rankab, 且 dim C(B) = rankb, 可推知 dim ker(t) = rankb rankab 然而 C(B) C n, 轉換 T 的核僅為 A 其零空間 N(A) 的部分集合 ( 子空間 ), 故 dim ker(t) dimn(a), 因此得證 32

33 Problem 27 Suppose A is an m n matrix. (a) Prove that there exist an m m invertible matrix P and an n n invertible matrix Q such that where r is the rank of A. PAQ = I r (b) Suppose that A with rank r can be factorized as A = U I r V where U is an m m invertible matrix and V is an n n invertible matrix. Decribe the column space of A and the row space of A in terms of U and V. (a) 對矩陣 A 執行消去法化簡至最簡列梯形矩陣, 設 m m 階可逆矩陣 P 為所執行過 所有基本矩陣的乘積, 再於化簡所得矩陣右乘一排列矩陣使其軸行全部移動至最左邊, 因為 ranka = r, 故得到 PAS = I r F = R 其中 S 是 n n 階排列矩陣, 注意 P 和 S 都是可逆的 接著再對 n m 階矩 陣 R T 進行列運算化簡, 設 n n 階可逆矩陣 T T 表示執行過的基本矩陣乘積, 因 rankr T = r, 就有 T T R T = T T I r F T = I r = J T 上式結果 J T 為 n m 階矩陣, 由 J = RT, 再將 R = PAS 代入得到 PAST = J, 令 Q = ST, 故 PAQ = J, 此即為所求 33

34 (b) 將 U 和 V 矩陣切割為適當分塊便可以清楚地描述 A 的行空間和列空間, 如下 : [ ] U = U 1 U 2, V = V 1 V 2 分塊 U 1 包含 U 的前 r 個行向量, V 1 包含 V 的前 r 個列向量 因此 A 即為 [ ] A = U 1 U 2 I r V 1 考慮矩陣 A 的第一種形式 : [ ] A = U 1 U 2 I r [ V = U 1 因 V 是可逆的, C(V ) = C n, 所以 A 的行空間基底由 U 1 的行向量構成 從第二種 形式 : A = U I r V 2 V 1 = U V 1 V 2 ] V 因 U 是可逆矩陣, C(U) = C m, 故 A 的列空間基底由 V 1 的列形成 Problem 28 Let A be an n n matrix. Prove that there is an invertible matrix B such that BA is a projection. 設 A 的行空間 C(A) 維度為 r, 則零空間 N(A) 維度為 n r 令 {x 1,...,x r } 為 A 的行空間基底, 將此基底擴充為 C n 的基底 : {x 1,...,x r,x r+1,...,x n } 因為任一 i = 1,...,r, x i C(A), 我們可以找到 y i 使得 Ay i = x i 再設 {y r+1,...,y n } 為零空間 N(A) 基底, 下面我們證明 {y 1,...,y n } 為線性獨立集, 故可為 C n 基底 考慮 c 1 y c n y n =, 因為 y i N(A), i = r + 1,...,n, 就有 ( n ) r r A c i y i = c i Ay i = c i x i = i=1 i=1 i=1 34

35 但 x 1,...,x r 為 C(A) 的基底向量, 因此是線性獨立集, 推知 c 1 = = c r =, 也就有 c r+1 y r c n y n =, 又因為 y r+1,...,y n 為 N(A) 的基底, 可斷定 c r+1 = = c n = 現在我們有兩組 C n 基底 : {x 1,...,x n } 和 {y 1,...,y n } 令可 逆矩陣 B 滿足 Bx i = y i, i = 1,...,n 對於 i = 1,...,r, BAy i = Bx i = y i, 對於 i = r + 1,...,n, BAy i = B =, 證得 BA 為一投影矩陣 Problem 29 Let A and B be n by n matrices. If AB =, show that the dimension of the nullspace of BA is at least n/2. ] 令 B = [b 1 b n, b j C n, 已知條件可寫為 ] ] AB = A [b 1 b n = [Ab 1 Ab n = 得知 b j N(A), j = 1,...,n, 亦即 C(B) N(A), 就有 rankb dimn(a) 由秩 零度定理, ranka + dimn(a) = n, 可推出 rankb n ranka, 又因為 rank(ba) min{ranka,rankb}, 就有 rank(ba) min{ranka, n ranka} 上式指出 rank(ba) n/2, 再使用秩 零度定理, 可得 Problem 3 dimn(ba) = n rank(ba) n/2 Let A be an n by n matrix of the form A = P D P 1 where P and D are n n and r r, r n, nonsingular matrices, respectively. Prove the following statements. 35

36 (a) There exists a nonsingular matrix B such that A 2 = BA. (b) ranka = ranka 2 (c) The column space of A and the nullspace of A are disjoint, i.e., C(A) N(A) = {}. (a) 設計以下的分塊乘法 A 2 = P D2 P 1 = P D P 1 P D P 1 = BA D 上式中 B = P D P 1 是可逆的 D (b) 證明 (a) (b) 因為可逆矩陣不改變矩陣秩, ranka 2 = rank(ba) = ranka (c) 證明 (b) (c) 設 ranka = ranka 2, 由秩 - 零度定理可知 dimn(a) = dimn(a 2 ) 又因為 N(A) N(A 2 ), 故 N(A) = N(A 2 ) 設 x C(A) N(A), 就有 Ax = 且存在 y 使得 x = Ay, 則 Ax = A(Ay) = A 2 y = 推論 y N(A 2 ) = N(A), Ay =, 所以 x = Problem 31 Let A and B be nonsingular n n matrices. Prove that rank(a B) = rank(a 1 B 1 ) 關鍵在於聯繫 A B 和 A 1 B 1, 觀察後不難得到下式 : B 1 A 1 = B 1 (A B)A 1 36

37 已知 A 1 和 B 1 是可逆的, 就有 rank(b 1 A 1 ) = rank(a B), 矩陣與非零常數相乘不改變矩陣秩, 故 rank(a 1 B 1 ) = rank(b 1 A 1 ), 證得原命題 補充解釋為何與可逆矩陣相乘不改變原矩陣的秩 設 A 為 m m 階可逆矩陣, B 為 m n, 有這個事實 : AB 和 B 的零空間相同, N(AB) = N(B) 證明如下 : 若 Bx =, 顯然 ABx = 反之, 若 ABx =, 同時左乘 A 1, 就有 A 1 ABx = Bx = 再來利用秩 零度定理可得 rank(ab) = n dimn(ab), rankb = n dimn(b), 故 rank(ab) = rankb 另一方面, 若 BA 是合法運算, 且 A 是可逆的, 則利用上述結果以及 ranka T = ranka, 就有 rank(ba) = rank(ba) T = rank(a T B T ) = rankb T = rankb Problem 32 Suppose A and B are n n matrices and A is nonsingular. Let B = A UQV, where U is n p, Q is p m, and V is m n. Show that if B is nonsingular then I V A 1 UQ is nonsingular, and vice versa. 若 B 是可逆的, 利用反證法, 假設 y 且 (I V A 1 UQ)y = 令 x = A 1 UQy, 則 V x = y, 這指出 x 將上式左乘 A, 就有 Ax = UQy, 因此 Bx = Ax UQV x = Ax UQy = 這與原假設 B 是可逆矩陣矛盾, 可知 I V A 1 UQ 的零空間不含非零向量, 故 I V A 1 UQ 是可逆的 若 I V A 1 UQ 是可逆的, 仍使用反證法, 假設有 x 使得 Bx =, 就有 Ax = UQV x 左乘 A 1, 可得 x = A 1 UQV x = A 1 UQy 將上面結果代入以下算式 (I V A 1 UQ)y = y V x = 因為 I V A 1 UQ 是可逆的, 必定有 y =, 也就有 V x =, 這又使 Ax = Bx + UQV x =, 與 A 是可逆矩陣矛盾, 推知 B 的零空間不含非零向量, B 是可逆的 Problem 33 Suppose A is an m n real matrix. 37

38 (a) If A T Ax =, show that Ax =. (b) Show that A and A T A have the same nullspace. (c) Show that A and A T A have the same row space, and thus ranka = ranka T A. (a) 左乘 x T 於 A T Ax =, 即得 x T A T Ax = (Ax) T Ax = Ax 2 =, 推知 Ax = 另一個做法是利用子空間的交集關係, 由 A T (Ax) = 可知 Ax N(A T ), 但是 Ax 屬於行空間 C(A), 再利用子空間互補關係 N(A T ) C(A) = {} 可確定 Ax = (b) 若 x N(A), 即 Ax =, 也就有 A T Ax = A T =, 這指出 x N(A T A), 因此 N(A) N(A T A) 題 (a) 已說明 N(A T A) N(A), 故推論得 N(A) = N(A T A) (c) 矩陣的列空間為其零空間的正交互補, 即 C(A T ) = N(A), C(A T A) = N(A T A) 利用題 (b) 結論 N(A) = N(A T A), 可得 C(A T ) = C(A T A), 也因此 ranka = dimc(a T ) = dimc(a T A) = ranka T A Problem 34 (a) Suppose A is an n by n matrix of rank r. Show that A may be written as a sum of rank-one matrices: A = x 1 y T x ry T r where x i and y i, i = 1,...,r, are n-dimensional vectors. (b) Suppose B is an n by n matrix of the form B = x 1 y T x r y T r If n-dimensional vectors x 1,...,x r are independent, what conditions of y i s must be satisfied so that the rank of B is r? 38

39 (c) Suppose X is a 3 2 matrix, and Y is a 2 5 matrix. How many possible dimensions of the nullspace of XY are there? (a) 矩陣 A 的行空間基底向量數是 r, 令 A 的行空間基底為線性獨立向量集合 {x 1,...,x r }, 則 A 的每一行 a j 都可用唯一方式表示為此基底向量的線性組合 對於 j = 1,...,n, 便有唯一確定的 y ij s 使 a j = y 1j x y rj x r 以行作為計算單位來實現矩陣乘法, 表現形式如下 : y [ ] [ ] 11 y 1n A = a 1 a n =. x 1 x r.... y r1 y rn 將上式右邊的權重矩陣以其列向量表示, 再以行 - 列相乘展開, 可得 [ ] A = x 1 x r y T 1. y T r = x 1y T x r y T r (b) 將基底向量 {x 1,...,x r } 擴充為 n- 維向量空間的基底 : {x 1,...,x r,x r+1,...,x n }, B 於是可寫為. [ ] B = x 1 x r x r+1... x n Ṭ. y T 1 y T r T = XY n n 階矩陣 X 由 n 個基底向量構成, 因此是可逆的 任意矩陣 Y 與可逆矩陣 X 相乘並不改變其秩, 故 rankb = ranky 為滿足條件 rankb = r, 矩陣 Y 的前 r 個列 ( 亦即非零列 ) 必須是線性獨立的, 即 y 1,...,y r 為一組線性獨立向量 39

40 (c) 將矩陣 XY 的各行視為 X 的行向量之線性組合, 3 2 階矩陣 X 僅有 2 行, 因此不論任何 Y, 總有 rankxy 2 矩陣 XY 為 3 5 階, 利用秩 - 零度定理推得 dimn(xy ) = 5 rankxy, 故 dimn(xy ) 可能為 3, 4, 5 Problem 35 Suppose A is an m n real matrix with full row rank, i.e., ranka = m. Which of the following equations always have a solution (possibly infinitely many) for any legal b? (a) Ax = b (b) A T x = b (c) A T Ax = b (d) AA T x = b (e) A T Ax = A T b (f) AA T x = Ab (a) Ax = b 總是有解, 因為 dimc(a) = ranka = m, 所以 C(A) = R m (b) A T x = b 可能沒有解, 因為 dimc(a T ) = ranka = m, 但 b 可以是 R n 中的任意向量 當 n > m 時, A T 的行空間 ( 維度為 m) 未能充滿整個 R n 空間 (c) A T Ax = b 可能無解, 推論如下 : 因為 N(A) = N(A T A), 其互補空間亦相等, 即 N(A) = N(A T A), 也就是 C(A T ) = C(A T A) 由題 (b), dimc(a T A) = dimc(a T ) = m, 因此得知 n n 階矩陣 A T A 的行空間是 R n 空間內維度為 m 的子空間 (d) AA T x = b 恆有唯一解, AA T 是 m m 階矩陣, 由題 (c) 可知 C(AA T ) = C(A), 即 dimc(aa T ) = dimc(a) = m, AA T 是滿秩, 故為可逆矩陣 4

41 (e) A T Ax = A T b 總是有解的, 利用題 (a) 結果, 任何 Ax = b 的解也必為 A T Ax = A T b 的解 (f) AA T x = Ab 有唯一解, 直接利用題 (d), 矩陣 AA T 是可逆的 41

42 線性變換 Problem 36 Let V be the vector space of polynomials of degree at most 3 with real coefficients. Let T be the map defined by for all f(x) V. T(f(x)) = d2 f dx df dx (a) Show that T is a linear transformation. (b) Find the matrix [T] B and [T] C representing T with respect to the bases B = {1,x,x 2,x 3 } and C = {1,1+x,1+x+x 2,1+x+x 2 +x 3 }, respectively. (c) Find the matrix M representing the change of bases from B to C. (a) 設 f(x),g(x) V, 則 ( T(f(x) + g(x)) = d2 (f + g) d(f + g) d 2 f dx = dx dx df ) ( d 2 ) g + dx dx 2 + 2dg dx = T(f(x)) + T(g(x)) ( T(cf(x)) = d2 cf d 2 dx 2 + 2dcf dx = c f dx df ) = ct(f(x)) dx 這證明了 T 為線性轉換 (b) B 的基底向量經轉換後為 T(1) = T(x) = 2 T(x 2 ) = 2 + 4x T(x 3 ) = 6x + 6x 2 42

43 因此 T(a + bx + cx 2 + dx 3 ) 可表示為矩陣乘法, 如下 : 2 2 a 4 6 b [T(x)] B = [T] B [x] B = 6 c d C 的基底向量經轉換後為 T(1) = T(1 + x) = 2 T(1 + x + x 2 ) = 4 + 4x = 4(1 + x) T(1 + x + x 2 + x 3 ) = 4 + 1x + 6x 2 = 6 + 4(1 + x) + 6(1 + x + x 2 ) 因此 T(s + t(1 + x) + u(1 + x + x 2 ) + v(1 + x + x 2 + x 3 )) 可表示為 2 6 s 4 4 t [T(x)] C = [T] C [x] C = 6 u v (c) 令 M 表示基底 B 至基底 C 的轉換矩陣, 而 M 1 即為基底 C 至基底 B 的轉換矩陣 因為 B 為標準基底, 所以 M = 解得其逆矩陣為 M =

44 利用 M[x] B = [x] C 和 M[T(x)] B = [T(x)] C, 可聯繫題 (b) 的兩個轉換 : M[T] B [x] B = [T] C M[x] B, 即 M[T] B = [T] C M, 或 [T] C = M[T] B M 1 驗證如下 : = Problem 37 Let A be an m n matrix. Prove or disprove the following statements. (a) If the vectors v 1, v 2,...,v k in C n are linearly independent, so are Av 1, Av 2,...,Av k. (b) If the vectors Av 1, Av 2,...,Av k in C m are linearly independent, so are v 1, v 2,...,v k. (a) 考慮極端情況 A =, 可知此題陳述不為真 延伸討論, 矩陣 A 要滿足什麼條件方能維持 Av 1, Av 2,...,Av k 的獨立性? 由線性獨立定義, 方程式 c 1 Av 1 + c 2 Av c k Av k = A(c 1 v 1 + c 2 v c k v k ) = 僅有解 c 1 = c 2 = = c k =, 矩陣 A 的零空間和向量 v 1,,v k 的擴張僅交集於零向量, 或者說 v 1,,v k 不屬於 A 的零空間 (b) 利用反證法, 先假設 v 1, v 2,...,v k 是線性相依, 則必定存在不全為零的權重 c 1, c 2,...,c k 使得 c 1 v 1 + c 2 v c k v k = 等號兩邊左乘 A, c 1 Av 1 + c 2 Av c k Av k = 這指出 Av 1, Av 2,...,Av k 為線性相依, 與已知條件矛盾, 故得證 44

45 Problem 38 Suppose [T] E = 1 1 is the transformation matrix for a linear transformation T with respect to the standard basis, and [T] B = is the transformation matrix with respect to B basis. Find a set of basis vectors of 4 11 B. 設基底 B 包含 2- 維基底向量集 {b 1,b 2 }, 令 B = [ b 1 b 2 ], B 的兩行向量是線性獨立, 故 B 是可逆的 因轉換矩陣 [T] E 滿足 T(x) = [T] E x, 而參考基底 B 的座標向量 [x] B 又 滿足 [T(x)] B = [T] B [x] B 因為 [x] B = B 1 x 且 [T(x)] B = B 1 T(x) = B 1 [T] E x, 則 [T] B B 1 = B 1 [T] E, 或 B[T] B = [T] E B 設線性轉換 L(B) = B[T] B [T] E B, 問題即為求轉換 L 的核 (kernel), 即 L(B) = 令 B = a b, 代入 L(B) 並展開, c d 可得 1a + 4b c 25a + 1b d L(B) = 1c + 4d 25c + 1d 再將此轉換改為矩陣乘法形式, 如下 : a a b b L = c 1 4 c d 25 1 d 以消去法化簡至最簡列梯形矩陣 :

46 零空間即為 [ 2 5,1,,]T 和 [ 1 25,, 2 5,1] 的擴張, 寫回 2 2 階矩陣, 滿足 L(B) = 的 矩陣可表示為 其中的兩行向量就是 B 的基底向量 : 又因為 B 是可逆矩陣, det(b) = 還要再加上條件 β Problem α 1 25 β α 2 5 β β 2 5 α 1 25 β 2 5 β, 2 5 α 1 25 β α 2 5 β β Consider the following linear transformation α β T(X) = AX XA = 1 25 β2 where X is a 2 2 matrix. If A is diagonalizable, prove that T is also diagonalizable. 設 Ax i = λ i x i, i = 1,2, 因為 A 可對角化, {x 1,x 2 } 為線性獨立向量集 令 2 2 階矩 陣 B ij 的第 j 行等於 x i, 其餘各行為零, 則 B = {B 11,B 12,B 21,B 22 } 為所有 2 2 階 矩陣形成的向量空間的有序基底 計算各基底向量 B ij 的像 T(B ij ) = AB ij B ij A, 如 下 : T(B 11 ) = AB 11 B 11 A [ ] [ ] = A x 1 x 1 a 11 a 12 = [ ] λ 1 x 1 a 21 a 21 ] [a 11 x 1 a 12 x 1 = λ 1 B 11 a 11 B 11 a 12 B 12 46

47 以同樣方式可以得到 T(B 12 ) = AB 12 B 12 A = λ 1 B 12 a 21 B 11 a 22 B 12 T(B 21 ) = AB 21 B 21 A = λ 2 B 21 a 11 B 21 a 12 B 22 T(B 22 ) = AB 22 B 22 A = λ 2 B 22 a 21 B 21 a 22 B 22 所以 T 參考有序基底 B 的表示矩陣為 [T] B = [[T(B 11 )] B [T(B 12 )] B [T(B 21 )] B ] [T(B 22 )] B λ 1 a 11 a 21 a = 12 λ 1 a 22 = λ 1I A T λ 2 a 11 a 21 λ 2 I A T a 12 λ 2 a 22 設 A 可對角化為 A = SΛS 1, 則 ci A T = (S T ) 1 (ci Λ)S T 也為可對角化矩陣, 因此證得所求 Problem 4 If {u 1,...,u n } and {v 1,...,v n } are bases of R n, and if Au j = Bv j = n c ij u i i=1 n c ij v i i=1 what is the relation between the matrices A and B? 令 C, U, V 為 n n 階矩陣, C = [c ij ], U 的行向量為 u j, V 的行向量為 v j, j = 1,2,...,n 給出的第一個方程式可寫為矩陣乘積 : c [ ] [ ] 11 c 1n A u 1 u n =. u 1 u n.... c n1 c nn 47

48 亦即 AU = UC, 同理由第二個方程式可得 BV = V C 因為 U, V 的行向量都是完整基底, U 和 V 同是可逆矩陣, 故 A 和 C 可表示為 A = UCU 1 和 C = V 1 BV, 也就有 A = UV 1 BV U 1 設 P = UV 1, 得到 A = PBP 1, A 相似於 B 另外一個做法是利用線性變換觀念, 關鍵想法是聯繫這二組基底向量, 設矩陣 P 表示線性變換滿足 Pv j = u j, j = 1,...,n, 則 Au j = APv j 且 Au j = n c ij u i = i=1 ( n n ) c ij Pv i = P c ij v i = PBv j i=1 i=1 因此對於任意 j, APv j = PBv j, 或 (AP PB)v j, j = 1,2,...,n, 推知 AP PB 的零空間維度等於 n, 即 rank(ap PB) =, 所以 AP = PB 矩陣 A, B 其實是參 考不同基底的線性變換表示矩陣, 而 P 則是這兩組基底的變換矩陣 48

49 內積空間 Problem 41 Suppose W is a subspace of an inner product space V and W is the orthogonal complement of W in V. For any x V, show that y W is the orthogonal projection of x onto W, i.e., x = y + y, for some y W, if and only if for every z W, x y x z. 設 y W, 且 x = y + y, 其中 y W, 可知 x y W 對於任意 z W, 就有 y z W, 故 x y,y z =, 所以 x z 2 = (x y) + (y z) 2 = x y 2 + y z 2 證得 x y x z 欲證明相反方向陳述, 設 w 為 x 至 W 的正交投影且 w y 考慮 x = w + w, 其中 w W, 因為 y,w W, 可得 x y 2 = (x w) (w y) 2 = x w 2 + w y 2 x w 2 這造成矛盾, 因此證得原命題 Problem 42 Let {v 1,...,v n } be an orthonormal basis for an inner product space V over C. If x V, show that (a) x = n i=1 x,v i v i (b) x,x k i=1 x,v i 2,1 k n. Note that x,y denotes the inner product of x and y. 49

50 (a) 將 x 表示為 x = c 1 v c n v n 令等號兩邊與 v i 計算內積, 因為 v i,v j = 1 若 i = j, v i,v j = 若 i j, 就有 c i = x,v i,i = 1,...,n (b) 將題 (a) 公式代入計算 x,x = = = n c i v i, i=1 n i=1 j=1 n c i 2 i=1 n c j v j j=1 n c i v i,c j v j k c i 2 (k = 1,...,n) i=1 Problem 43 Suppose x and y are vectors in an inner product space V. Show that x y x y This is called the backward triangle inequality. 利用三角不等式 x + y x + y 改寫 x, 如下 : x = x y + y x y + y 5

51 得到 x y x y 再考慮 y = x y + x x y + x 也就有 ( x y ) x y 合併上面二式即證得所求 Problem 44 Suppose x 1, x 2, x 3 are three vectors in R n, and x T i x j <, for i,j = 1,2,3, i j. Prove that x 1, x 2, x 3 are linearly independent. 利用反證法, 假設 x, x 2, x 3 是線性相依 在不失一般性下, 設 x i, i = 1,2,3, 為單位向量, 且 x 3 = c 1 x 1 + c 2 x 2 計算內積並使用已知條件, x T 1 x 3 = x T 1 (c 1 x 1 + c 2 x 2 ) = c 1 + c 2 x T 1 x 2 < x T 2 x 3 = x T 2 (c 1 x 1 + c 2 x 2 ) = c 1 x T 2 x 1 + c 2 < 已知 x T 1 x 2 <, 第一式乘以 x T 1 x 2 可得 c 1 (x T 1 x 2) < c 2 (x T 1 x 2) 2, 再合併第二式可得 c 2 < c 1 x T 2 x 1 < c 2 (x T 1 x 2 ) 2 所以 (x T 1 x 2) 2 > 1, 這與最初假設 x 1, x 2 為單位向量矛盾, 證得 x 1, x 2, x 3 為線性獨立 Problem 45 Let x 1,...,x n be vectors in R m, and let A = [a ij ], where a ij = x T i x j i,j = 1,...,n. Show that x 1,...,x n are linearly independent if and only if A is nonsingular. 51

52 考慮 c 1 x c n x n = 計算 x T i, i = 1,2,...,n, 與上式乘積, 利用給出條件可得 x T i (c 1 x c n x n ) = c 1 x T i x c n x T i x n = c 1 a i1 + + c n a in = 將這 n 個式子以矩陣乘法表示, 如下 : a 11 a 1n c 1 Ac = =. a n1 a nn c n 若向量集 x 1,...,x n 是線性獨立的, 必定有 c 1 = = c n =, 這說明 Ac = 存在平 凡解, 故 ranka = n, A 為可逆矩陣 相反方向的陳述也成立 ] 另一個做法運用 QR 分解 設 X = [x 1 x n, 令其 QR 分解式為 X = QR, 因為 Q T Q = I n, A = X T X = (QR) T (QR) = R T Q T QR = R T R 若 X 有線性獨立的行向量, 則 R 為可逆矩陣 又因為 ranka = rank(r T R) = rankr, 所以 A 也是可逆的 顯然反向陳述亦真 Problem 46 Let A be an n by n real matrix satisfying (Ax) T (Ay) = x T y for every x, y in R n. Show that A is an orthogonal matrix. 從給出條件 (Ax) T (Ax) = x T A T Ax = x T x 得到 x T (A T A I)x = 52

53 令 B = A T A I, B 為對稱矩陣, 接著我們證明 : 對於對稱矩陣 B, 任意向量 x 都滿足 x T Bx =, 則 B = 考慮 (x + y) T B(x + y) 的展開式, 將它寫為 (x + y) T B(x + y) x T Bx y T By = x T By + y T Bx 由已知條件, 上式等號左邊為零, 右邊等於 2x T By, 亦即 x T By = 設 x = By 再代回左式, 就有 By 2 =, 因此 By =, 但 y 是任意向量, 所以必定有 B =, 推知 A T A = I, 即 A T = A 1, A 為正交矩陣 Problem 47 Suppose Q is a 4 3 real matrix with orthonormal columns q 1, q 2, q 3. (a) Suppose v is not in the column space of Q. Use Gram-Schmidt process to obtain the fourth orthonormal vector q 4. (b) Describe the nullspaces of Q, Q T, Q T Q and QQ T. (c) Suppose b = q 1 + 2q 2 + 3q 3 + 4q 4. Find the least-squares solution to Qx = b. What is the projection p of this b onto the column space of Q? (a) 將向量 v 投影至 q i, i = 1,2,3, 的分量去除即可 : p 4 = v (v T q 1 )q 1 (v T q 2 )q 2 (v T q 3 )q 3 再正規化向量 : q 4 = p 4 / p 4 (b) 因 Q = [ q 1 q 2 q 3 ] 有線性獨立的 3 個行, Q 的零空間僅含零向量 Q T 的零空間即為 C(Q) 的正交互補空間, 故 N(Q T ) 由題 (a) 的 q 4 向量所擴張成 ( 因 q 4 與 q 1, q 2, q 3 正交 ) 因為 Q T Q = I 3, 故其零空間為 {}, 而 4 4 階矩陣 QQ T 的零空間由 q 4 所擴張, 這是由於 QQ T q 4 = Q = 53

54 (c) 因為 Q T Q = I, 正規方程式 (normal equation) Q T Qˆx = Q T b 等價於 ˆx = Q T b, 所以 Problem 48 ˆx = q T 1 q T 2 q T 3 1 (q 1 + 2q 2 + 3q 3 + 4q 4 ) = 2 3 投影向量 p 即為 p = Qˆx = q 1 + 2q 2 + 3q 3 Suppose C is an n n real symmetric positive-definite matrix. (a) Suppose C = B T B for some m n matrix B. Which of the following (if any) must be properties of B: full column rank, full row rank? (b) Suppose A has linear independent columns, and C = B T B as in (a). In terms of B, A, and b, write down an explicit formula for the x that minimize (Ax b) T C(Ax b). (c) Suppose that C was only positive semi-definite. Is there still a minimum value of (Ax b) T C(Ax b)? Is there still a unique solution x? (a) 因為 C 是正定矩陣, 對於任意 x, x T Cx = x T B T Bx = Bx 2 >, 1 故 N(B) = {}, B 是滿行秩 但 B 未必是滿列秩, 例如, B = 1, 則 C = B T B = 1 1 (b) 整理算式 : (Ax b) T C(Ax b) = (Ax b) T B T B(Ax b) = (BAx Bb) T (BAx Bb) = BAx Bb 2 54

55 最小平方解滿足正規方程式 (BA) T (BA)ˆx = (BA) T Bb 由已知以及題 (a), A 和 B 都是滿行秩, 因此 BA 也是滿行秩, 理由是 N(A) = {} 且 N(B) = {}, 若 BAx =, 則 Ax =, 又 x =, 故 N(BA) = {} BA 有線性獨立的行, 推知 (BA) T (BA) 是可逆的, 所以最小平方解為 ˆx = (A T B T BA) 1 A T B T Bb = (A T CA) 1 A T Cb (c) 倘若 C 僅為半正定, 仍有 C = B T B, 且 (Ax b) T C(Ax b) 仍有最小值, 但 B 未必為滿行秩, 也因此最小平方解並不唯一存在 例如, 若 C =, 則任何 x 都可使 (Ax b) T C(Ax b) 最小化 Problem 49 Suppose A is an n n real matrix. (a) Show that A T A may be written as A T A = LL T, where L is a real lower triangular matrix with nonnegative diagonal entries. (b) Show that the factorization A T A = LL T, L with positive diagonal entries, is unique if A is nonsingular. This is called the Cholesky factorization of A T A; every positive definite matrix may be factored in this way. [ ] (a) 將矩陣 A 以 QR 形式分解為 A = QR, Q = q 1 q n 是 n n 階正交 正規矩陣, R 是 n n 階上三角形矩陣 因為 Q 1 = Q T, R = Q 1 A = Q T A = q T 1. q T n [ ] a 1 a n 矩陣 R 的主對角元為 (R) ii = q T i a i, 進行 QR 分解時可以選擇 q i 的正負符號使 (R) ii 令 L = R T, 所以 A T A = (QR) T (QR) = R T Q T QR = R T R = LL T 下三角形矩陣 L 的主對角元皆不為負 55

56 (b) 當 A 是可逆時, A 的零空間僅含零向量, 對於 x, x T A T Ax = (Ax) T (Ax) = Ax 2 >, 這指出 A T A 是對稱正定矩陣 A T A 的主對角之元皆為正值, 因為 (A T A) ii = a T i a i = e T i AT Ae i > 設 B = A T A, 將 B = LL T 以如下的分塊矩 陣表示 B = b 11 b T 21 b 21 B 22 T = l l T 21 = l 21 L 22 L T 22 l2 11 l 11 l T 21 l 11 l 21 l 21 l T 21 + L 22 L T 22 注意 b 11 >, 由第 1 列可解出 l 11 = b 11, l 21 = 1 b11 b 21, 由 (2,2) 元得到 L 22 L T 22 = B 22 l 21 l T 21 = B 22 1 b 11 b 21 b T 21 由於 B 是正定的, 對於任意不都為零的 x, y 就有 [ ] x y T b 11 b T 21 x b 21 B 22 y Problem 5 = b 11 x 2 + 2x(b T 21y) + y T B 22 y ( = b 11 x 1 ) 2 b T 21 b y + y T B 22y 1 (b T b y)2 11 ( = b 11 x 1 ) 2 ( b T 21 b y + y T B 22 1 ) b 21 b T 21 y > 11 b 11 這說明 B 22 1 b 11 b 21 b T 21 亦為對稱正定矩陣 利用歸納法, 必定可以解出唯一的 L 22 滿足 B 22 1 b 22 b 21 b T 21 = L 22 L T 22 Suppse u and v are linear independent vectors in R n. (a) Find a nonzero vector w in R n as a linear combination of u and v so that w is perpendicular to u. (b) Suppose u and v are two columns of A, i.e., A = [ u v ], find Q and R so that A = QR, where Q has orthonormal columns and R is a 2 by 2 upper triangular matrix. (c) Let P be the orthogonal projection matrix onto the subspace spanned by u and v. Express P in terms of Q only. 56

57 (a) 運用 Gram-Schmidt 正交化程序將 v 中的 u 分量去除即可 令 w = v cu, 按 題意 w 和 u 正交, 故 w T u = v T u cu T u =, 所以 c = (v T u)/(u T u), 則 w = v vt u u T u u (b) 由題 (a) 已知 w 和 u 正交, 再將他們正規化, 令 q 1 = u/ u, q 2 = w/ w, 此 即為 Q 的兩行, Q = [ q 1 q 2 ] 接著設法將矩陣 A 的兩行表示為 q 1 和 q 2 的線 性組合, 設矩陣 R 的兩行為 r 1 和 r 2, 以行為計算單位展開 A = QR: [ ] u = Qr 1 = [ q 1 q 2 ]r 1 = u w r u w 1 [ ] v = Qr 2 = [ q 1 q 2 ]r 2 = u w r u w 2 分別可解出 r 1 = u, r 2 = c u, 其中 c = (v T u)/(u T u) w (c) 投影矩陣 P 將向量投影至 A 的行空間, 利用題 (b) 的 QR 分解及性質 Q T Q = I, 就有 Problem 51 P = A(A T A) 1 A T = (QR)(R T Q T QR) 1 (R T Q T ) = (QR)(R T R) 1 (R T Q T ) = Q(RR 1 (R T ) 1 R T )Q T = QQ T Suppoes A, B and Q are n n real matrices, and B = Q T AQ, where Q is an orthogonal matrix. Denote the (i,j) entry of A to be a ij. Show that n i=1 j=1 n a 2 ij = n n i=1 j=1 b 2 ij 57

58 執行矩陣乘法運算可得出 n n a 2 ij = tr(a T A) i=1 j=1 因此問題變成證明 tr(a T A) = tr(b T B) 因為 B = Q T AQ, 且正交矩陣滿足 Q T = Q 1, 便有 tr(b T B) = tr(q T A T QQ T AQ) = tr(q T A T AQ) = tr(a T AQQ T ) = tr(a T A), 最後步驟利用了跡數的一個實用性質 : 若 CD 和 DC 都是方陣, 但尺寸未必相同, tr(cd) = tr(dc) Problem 52 Suppose u 1, u 2, u 3 form an orthonormal basis for R 3 and v 1, v 2 form an orthonormal basis for R 2. Let A = u 1 v T 1 + u 2v T 2. (a) Show that AA T is an orthogonal projection matrix. (b) Find the eigenvalues and corresponding eigenvectors of AA T. (c) Show that A T A is the identity matrix. (a) 因為 v T 1 v 2 = 且 v T i v i = 1, 計算 AA T = (u 1 v T 1 + u 2 v T 2 )(v 1 u T 1 + v 2 u T 2 ) = u 1 u T 1 + u 2 u T 2 AA T 是對稱的, 而且 (AA T ) 2 = AA T, 這是由於 (AA T ) 2 = (u 1 u T 1 + u 2 u T 2 )(u 1 u T 1 + u 2 u T 2 ) = u 1 u T 1 + u 2 u T 2 同樣利用了 u T 1 u 2 = 且 u T i u i = 1 任何滿足條件 P T = P 及 P 2 = P 的矩陣便是正交投影矩陣 (b) 投影矩陣 AA T 將 R 3 空間的向量投影至 AA T 的行空間, 我們從題 (a) 知道 AA T 的行空間基底可為 {u 1, u 2 }, 因此投影矩陣 AA T 不改變 u 1 和 u 2, 驗證如下 : AA T u 1 = (u 1 u T 1 + u 2u T 2 )u 1 = u 1 AA T u 2 = (u 1 u T 1 + u 2u T 2 )u 2 = u 2 58

59 AA T 有特徵值 1, 1, 以及對應的特徵向量 u 1, u 2 又由於 AA T 是實數對稱矩陣, 必定可選擇一組正交特徵向量, 因而推論 u 3 也是特徵向量, 但 u 3 與 AA T 的行空間正交, 故 u 3 屬於左零空間 N((AA T ) T ), 亦即 (AA T ) T u 3 = AA T u 3 = 綜合上面的討論, AA T 的特徵值為 1,1,, 而對應的特徵向量分別是 u 1, u 2, u 3 (c) 重複利用正交正規向量的基本關係, 得出 A T A = (v 1 u T 1 + v 2u T 2 )(u 1v T 1 + u 2v T 2 ) = v 1v T 1 + v 2v T 2 注意 A T Av 1 = (v 1 v T 1 + v 2v T 2 )v 1 = v 1 且 A T Av 2 = (v 1 v T 1 +v 2v T 2 )v 2 = v 2, 因為 v 1, v 2 是 R 2 的基底向量, 對於任意 x R 2 總有唯一表示式 x = c 1 v 1 +c 2 v 2, 計算 A T Ax = A T A(c 1 v 1 + c 2 v 2 ) = c 1 A T Av 1 + c 2 A T Av 2 = c 1 v 1 + c 2 v 2 = x 這指出對於任意 x R 2, 恆有 A T Ax = x, 由此可推論 A T A = I 2 Problem 53 Suppose we are given the following measurements: y = 2 at t = 1, y = at t =, y = 3 at t = 1, and y = 5 at t = 2. (a) Find the best straight line fit to the above measurements. (b) Suppose that instead of a straight line, we fit the data by a parabola: y = c + c 1 t + c 2 t 2. Without actually solving the best parabola fit, will it be possible to determine whether the best parabola fit has less fitting error than that generated by the best line fit? Explain the reason. (a) 令配適的直線為 y = c + dt, 假設給出的四組測量值滿足直線方程式, 就有 c d = 2 c = c + d = 3 c + 2d = 5 59

60 表示為矩陣形式 Ax = b, 其中 x = [c,d] T, 且 A =, b = 由於此方程式並不一致, 我們改以最小平方法求解 因為 A 的二行向量是線性獨立 的, 可順利得出最小平方解, 詳細過程如下 : A T A = 4 2, A T b = 正規方程式 A T Aˆx = A T b 即為 ˆx = 6 15 解出 ˆx = [.3, 2.4] T, 故最佳配適直線是 y =.3 2.4t (b) 由題 (a) 的最佳配適可以計算出誤差向量為 e = b Ax =.3.3 = 若以二次曲線配適, 則有以下不一致的方程式 A x = b: x = 注意由直線配適得到的誤差向量 e 與矩陣 A 的第三個行向量正交 : 1 [ ] = 1 4 6

61 這表示誤差 e 已經與 A 的行空間正交, 也就是說二次曲線配適與一次曲線配適得出 Problem 54 的誤差相等 The trace of an n by n matrix A is defined to be the sum of its diagonal entries, denoted by tr(a). (a) Suppose A is an m n matrix and B is an n m matrix. Show by direct calculation that tr(ab) = tr(ba). (b) If A and B are 2 2 matrix such that show that a + d =. AB BA = a b c d (c) Suppose m n matrix A has linear independent columns, P is the projection matrix onto the column space of A, and Q is the projection matrix onto the left nullspace of A. Show that tr(p) = n and tr(q) = m n. (a) 對於矩陣 C, 設 (C) ij 為其第 (i,j) 元 由跡數 (trace) 的定義得知 tr(ab) = tr(ba) = m (AB) ii = i=1 n (BA) jj = j=1 比較以上二式證得 tr(ab) = tr(ba) (b) 對原式等號兩端計算跡數 : m i=1 j=1 n j=1 i=1 n (A) ij (B) ji m (B) ji (A) ij tr(ab BA) = tr(ab) tr(ba) = = a + d 61

62 (c) 投影至 C(A) 的矩陣是 P = A(A T A) 1 A T, 利用題 (a) 的性質, tr(p) = tr(a(a T A) 1 A T ) = tr((a T A) 1 A T A) = tr(i n ) = n 因為 Q = I m P, 就有 tr(q) = tr(i m P) = tr(i m ) tr(p) = m n Problem 55 Suppose A is an m n real matrix. Given some b R m, it is known that the equation Ax = b is solvable. (a) Show that there is a unique vector y in the row space of A such that Ay = b. (b) Show that among all possible solutions of Ax = b, the one in the row space has the minimum length. (c) Suppose A has independent rows and y is in the row space of A so that Ay = b. Express y in terms of A and b. (a) 設 x R n 滿足方程式 Ax = b, 因列空間 C(A T ) 與零空間 N(A) 為正交互補, x 可唯一分解為 x = y + z, 其中 y C(A T ), z N(A) 代入方程式 Ax = A(y + z) = Ay + Az = Ay = b, 所以 y 亦為方程式的解 假設 y,y C(A T ) 皆為方程式的解, 即 Ay = b, Ay = b, 將兩式相減可得 A(y y ) =, 由此知 y y N(A), 但是 y 和 y 的線性組合仍於列空間中, 因此 y y C(A T ), 故 y y N(A) C(A T ) = {}, 必有 y = y, 證得列空間內的解是唯一的 (b) 承題 (a), 方程式有解 x = y +z, 其中 y C(A T ), z N(A), 且 y 是唯一存在 因 y 和 z 是正交的, 解的長度為 x 2 = (y+z) T (y+z) = y 2 + z 2 y 2, 等號發生於 z = (c) 因為 A 有線性獨立的列, 列空間的任何向量 y 可以用唯一方式表示為 A 的列空列向量之線性組合 : y = A T c, c 為權重向量 考慮方程式 Ay = AA T c = b 的求解問 62

63 題, 因 rankaa T = ranka T = m, AA T 是滿秩, 於是有唯一解 c = (AA T ) 1 b, 亦即 y = A T (AA T ) 1 b 滿足 Ay = b Problem 56 Let W = span{1,x} P 2, where P 2 is a vector space of polynomials of degree at most 2 has the standard inner product for p,q P 2 as follows: p,q = 1 p(x)q(x)dx Compute the orthogonal complement W. 設 p(x) = a + a 1 x + a 2 x 2 W, 必定有 p(x) 1 和 p(x) x, 亦即 = p,1 = = p,x = 1 1 積分後可得下列線性方程 (a + a 1 x + a 2 x 2 )1dx = a 1dx + a 1 xdx + a 2 x 2 dx (a + a 1 x + a 2 x 2 )xdx = a xdx + a 1 x 2 dx + a 2 x 3 dx a a a 2 = 1 2 a a a 2 = 解出 a = 1 6 α, a 1 = α, a 2 = α, 其中 α 是自由變數, 得到 ( ) 1 p(x) = α 6 x + x2 所以, W = span { 1 6 x + x2} 63

64 行列式 Problem 57 Explain why the following determinant is equal to zero: a 14 a 15 a 24 a 25 a 34 a 35 a 41 a 42 a 43 a 44 a 45 a 51 a 52 a 53 a 54 a 55 For an n by n matrix A = [a ij ], what is the smallest m m zero principal submatrix, a ij =, i,j = 1,...,m, making det A =? 行列式的前三個行向量為線性相關, 所以行列式等於零 ; 也就是說, 如果零主子陣 太大, 將 使行列式為零 當零主子陣為 m m 階時, 有 m 個 n- 維向量擠在維度是 n m 的子空 間中, 這 m 個向量要為獨立的條件是必須有足夠的活動空間, 亦即 n m m; 反過來 說, 如果 m > n m, 則此 m 個向量必定是線性相關, 因此使行列式為零的最小 m 值為 n+1 2 Problem 58 Let A n be the tridiagonal n n matrix with 2 s on the main diagonal, 1 s immediately above the main diagonal, 3 s immediately below the main diagonal, and s everywhere else: A n =

65 (a) Explicitly calculate deta n, for n = 1,2,3,4, and express deta n in terms of deta n 1 and deta n 2. (b) Derive the formula for deta n. (a) 前面幾個低階行列式可以很容易求出 deta 1 = det[2] = deta 2 = 3 2 = deta 3 = = = 2detA 2 3detA 1 = = deta 4 = = 由此可歸納得到 deta n 的遞迴公式 = 2detA 3 3detA 2 = 2 ( 4) 3 (1) = 11 deta n = 2detA n 1 3detA n 2 (b) 將題 (a) 的遞迴公式寫成矩陣形式 : deta k+2 = 2 3 deta k+1 deta k+1 1 deta k 令 u k = deta k+1, A 為上式的係數矩陣, 便有差分方程式 u k+1 = Au k, 初 deta k 始值為 u 1 = [1,2] T 將矩陣 A 正交化為 A = SΛS 1, S 和 Λ 分別為特徵向量矩 65

66 陣和特徵值矩陣 : A = = λ 1 λ λ i 1 λ 2 1 λ 1 其中 λ 1 = 1 + 2i, λ 2 = 1 2i 差分方程式的解為 u n = A n 1 u 1, 計算 矩陣的冪 Problem 59 A n 1 = λ 1 λ = 1 2 2i λn 1 1 λ n i 1 λ 2 1 λ 1 λn 1 λn 2 λ n 1 λ 2 + λ 1 λ n 2 λ1 n 1 λ2 n 1 λ1 n 1 λ 2 + λ 1 λ2 n 1 再將初始值 u 1 和得到的 A n 1 代入 u n = A n 1 u 1 可得出解 deta n = 1 2 2i (λn 1 1 λ2 n 1 2λ1 n 1 λ 2 + 2λ 1 λ2 n 1 ) Calculate the determinant of the following 6 6 matrix: A =

67 觀察發現給出的矩陣每一列及每一行僅含一零元, 於是將 A 改寫為排列矩陣 P 和矩陣 B 的乘積, 而 B 的主對角元皆為零, 如下 : A = PB = 排列矩陣 P 其列次序為 , 經過 3 次列交換可轉換為單位矩陣, 因此 detp = 1 將矩陣 B 改寫成 B = uu T I, 其中 u = [1,1,1,1,1,1] T, 而 6 6 階方陣 uu T 的每一個元皆為 1 因 uu T 為對稱矩陣, 必可找出互為正交的完整特徵向量集合 計算 (uu T )u = (u T u)u = 6u, 令 v Span{u}, 則 u T v =, 因此有 (uu T )v = (u T v)u = 因為 dimspan{u} = 5, 矩陣 uu T 的特徵值為 6,,,,,, 得知 B 的特徵值則為 5, 1, 1, 1, 1, 1, 故 detb = 5, 所以 deta = (detp)(detb) = ( 1)( 5) = 5 Problem 6 Let P = A B C D where A,B,C,D are n n matrices. If D is invertible and CD = DC, show that detp = det(ad BC) 分塊矩陣的行列式有一個有效而實用的性質 : 三角形分塊矩陣的行列式等於主對角分塊行列式的乘積 因此, 若三角形分塊矩陣的主對角分塊都是單位矩陣 ( 其階數未必相同 ), 則行列式值為 1 為利用上述性質, 我們設計一個矩陣乘法運算 : 令 P 和一個主對角為單位矩陣的 67

68 三角形分塊矩陣相乘, 並使其乘積亦為三角形分塊矩陣, 下為一例 : A B I n = A BD 1 C B C D D 1 C I n D 三角形分塊其 (2,1) 元設為 D 1 C 的目的是使矩陣乘積也為三角形分塊矩陣 剩下來的 工作是計算矩陣的行列式, 利用前述性質, 等號左邊的行列式為 A B C D I n D 1 C I n = detp deti n deti n = detp 等號右邊的行列式則為 A BD 1 C B D = det(a BD 1 C) detd = det(ad BD 1 CD) = det(ad BD 1 DC) = det(ad BC) 我們使用了已知條件 CD = DC 上面左右兩端的兩行列式相等, 於是得證 Problem 61 LetA andb be m m and n n matrices, respectively. Derive a formula for det A. B C 考慮下面的分塊矩陣乘法 A I n = A B C I m C B 計算等號兩邊行列式, 利用矩陣乘積行列式可乘性質, 可得 A I n B C I m = A C B 68

69 執行 m + n 次列交換運算, 每次列交換改變行列式正負符號, 因此 I n I m = I ( 1)m+n m I n = ( 1)m+n 因為下三角形分塊矩陣的行列式等於主對角分塊行列式乘積, 也就有 A C B = (deta)(detb) 所以 Problem 62 A B C = ( 1)m+n (deta)(detb) Let A and B be n by n matrices over C. Prove that A B = det(a + B) det(a B) B A 設 (A + B)x = λx, (A B)y = µy, 則 A B x = λ x, A B y = µ y B A x x B A y y 上兩式指出方陣 A B 包含 A + B 的特徵值 λ 和 A B 的特徵值 µ, 因此存在以下 B A 特徵多項式關係 : A ti n B B A ti n = det((a + B) ti n) det((a B) ti n ) 代入 t = 即證得所求 69

70 Problem 63 Suppose A and B are n n real matrices. Let C = A B B A Show that detc. 設計分塊矩陣乘法 I ii I A B B A I ii I = A ib B A + ib 其中 i = 1 等號兩邊同時計算行列式, 因為 I ii I = 1, I ii I = 1 就有 A B B A = A ib B A + ib = det(a + ib)det(a + ib) = det(a + ib)det(a + ib) Problem 64 Suppose A, B, C and D are n n matrices. If rank A B = n, show that C D A B C D = 7

71 分開兩個情況討論 若 A 是可逆的, 則 ranka = n, 考慮 I A B = A B CA 1 I C D D CA 1 B 所以 D CA 1 B =, 亦即 D = CA 1 B 等號兩邊取行列式, 可得 detd = (detc)(deta 1 )(detb), 也就有 A D = B C 若 A 不可逆, 只要證明 detb = 或 detc = 即可 若 B 為可逆矩陣, rankb = n, 就有 I A B A B = DB 1 I C D C DB 1 A 推知 C = DB 1 A, 故 detc = (detd)(detb 1 )(deta) = Problem 65 Suppose A and B are n by n orthogonal matrices such that deta + detb = Prove that det(a + B) =. 利用行列式性質 det(a + B) = det(a + B) T = det(a T + B T ) 等號兩邊分別左乘 deta 和 detb, 使用行列式可乘公式和正交矩陣關係, 可得 (deta)det(a + B) = (deta)det(a T + B T ) = det(aa T + AB T ) = det(i + AB T ) 且 (detb)det(a + B) = det(ba T + BB T ) = det(ba T + I) T = det(i + AB T ) 將兩式相減, 就有 (deta detb)det(a + B) = 若 det(a + B), 則 deta = detb 由已知 deta + detb = 可推得 deta =, 這與 A 是正交矩陣矛盾, 所以必定有 det(a + B) = 71