Microsoft Word - Friedberg doc

Transcription

1 Liear Algebra- Chapter /9/ Chapter lemetary Matri Operatios ad Systems of Liear quatio - lemetary Matri Operatios ad lemetary Matrices I this sectio, we defie the elemetary operatios that are used throughout the chapter. I subsequet sectios, we use these operatios to obtai simple computatioal methods for determiig the rak of a liear trasformatio ad the solutio of a system of liear equatios. 何謂 基本矩陣運算 (lemetary matri operatio)? 基本矩陣(lemetary matri)? 以及基本矩陣運算可用於計算線性轉換的 Rak 與解線性方程組 There are two types of elemetary matri operatios row operatios ad colum operatios. DFINTION. lemetary operator Let A be a m matri. Ay oe of the followig three operatios o the rows [colums] of A is called a elemetary row [colum] operatio: 何謂 基本矩陣運算 (lemetary matri operatio)? 令 A 為一 m 的矩陣, 以下這三個運算可以稱為基本列或行運算 : () TYP : iterchagig ay two rows [colums] of A; 將 A 的任兩行或任兩列互換 () TYP : multiplyig ay row [colum] o A by a ozero scalar; 將非零常數乘至 A 中某一列 () TYP : addig ay scalar multiple of a row[colum] of A to aother row[colum]. 將 A 的某一列乘上任一常數後加到另外一列

2 Liear Algebra- Chapter /9/ XAMPL Let A 經過四種不同型態的運算 TYP : Iterchagig the secod row of A with the first row. The result matri is B TYP : Multiplyig the secod colum of A by C TYP : Addig times the third row of A to the first row 7 7 M TYP : Addig - times the third row of M to the first row of M A A Notice that if a matri Q ca be obtaied from matri P by meas of a elemetary row operatio, the P ca be obtaied from Q by a elemetary row operatio of the same type. 注意 : 若矩陣 Q 經過基本列運算後, 得到矩陣 P, 則矩陣 P 亦可由同一 TYP 的基本列運算得到矩陣 Q DFINITION. lemetary matri A elemetary matri is a matri obtaied by performig a elemetary operatio o I. The elemetart matri is said to be of type,, or accordig to whether the elemetary operatio performed o I is type,, or operatio, respectively. 基本矩陣 係指在 I 上實施某一基本運算後所得的矩陣 分別在 I 上實施 TYP 基本運算後所得基本矩陣稱為 TYP

3 Liear Algebra- Chapter /9/ For eample, iterchagig the first rows of I produces the elemetary matri 為基本矩陣 (lemetary matri), 係由 I 的前二行互調或前兩列 互調取得 Note that ca be obtaied by iterchagig the first two colums of I. I fact, ay elemetary matri ca be obtaied i at least two ways either by performig a elemetary row operatio o I or by performig a elemetary colum operatio o I. Similarly, 也是基本矩陣 (lemetary matri), 此矩陣可由兩種管道取得 is a elemetary matri sice it ca be obtaied from I by a elemetary colum operatio of type (addig - times the first colum of I to the third colum). Theorem. Let A M m (F), ad suppose that B is obtaied from A by performig a elemetary row [colum] operatio. The there eists a m m [ ] elemetary matri such that B A [B A]. IN fact, is obtaied from I m [I ] by performig the same elemetary row [colum[ operatio as that which was performed o A to obtai B. Coversely, if is a m m [ ] elemetary matri, the A [A] is the matri obtaied from A by performig the same elemetary row [colum] operatio as that which produces from I m [I ]. 令 A M m (F) 並假設 B 是由 A 經實施某一基本列 或行 運算後所得到的矩陣, 則存在一個 m m 或 基本矩陣, 使得 B A 或 B A 矩陣是由 I m 或 I 經實施與 由 A 得到 B 相同的基本列 或行 運算後所得到的矩陣 反之, 若 是一個 m m 或 的基本矩陣, 則 A 或 A 是由 A 經過與 由 I m 或 I 得到 相同的基本列 或行 運算後所得到的矩陣 A lemetary row [colum] operatios B I m lemetary row [colum] operatios B A [ A]

4 Liear Algebra- Chapter /9/ XAMPL Cosider the matrices A ad B i ample. I this case, B is obtaied from A by iterchagig the secod row of A with the first row. Performig this same operatio o I, we obtai the elemetary matri 範例 :A 經過基本列運算 (Iterchagig the secod row of A with the first row) B I m 經過基本列運算 (Iterchagig the secod row of A with the first row) 則 B 亦可由 B A 取得 A A B Cosider the matrices A ad C i ample. I this case, C is obtaied from A by multiplyig the secod colum of A by. Performig this same operatio o I, we obtai the elemetary matri 範例 :A 經過基本行運算 (Multiplyig the secod colum of A by ) C I 經過基本行運算 (Multiplyig the secod colum of A by ) 則 C 亦可由 C A 取得 A C A Theorem. lemetary matrices are ivertible, ad the iverse of a elemetary matri is a elemetary matri of the same type. 基本矩陣為可逆矩陣, 且基本矩陣的反矩陣亦是同一型的基本矩陣 Proof Let be a elemetary matri. The ca be obtaied by a elemetary row

5 Liear Algebra- Chapter /9/ [colum] operatio o I. By reversig the steps used to trasform I ito, we ca trasform back ito I. The result is that I ca be obtaied from by a elemetary row [colum] operatio of the same type. By Theorem., there is a elemetary matri such that I. Therefore, is ivertible ad. 令 是 的基本矩陣, 可由 I 經實施一基本列或行運算取得, 若把用來實施 I 的運算對 實施, 亦可得到 I 依據 Theorem. 可知 : 存在一基本矩陣 使得 I, 因此 為可逆且 lemetary Matrices lemetary Matrices / / A elemetary matri is oe that ca be obtaied from the idetity matri I through a sigle elemetary row operatio. I R R R R R R R R Operatio T Operatio T lemetary Matrices lemetary Matrices / / i h g f e d c b a A A A f e d i h g c b a R R A A i h g f e d c b a R A A i h g c f b e a d c b a R R lemetary Matrices lemetary Matrices / / ach elemetary matri is ivertible. I R R I I, R R I i.e., R R I lemetary Matrices lemetary Matrices / / If A ad B are row equivalet matrices ad A is ivertible, the B is ivertible. Sice A ad B are row equivalet there eits a sequece of row operatios T, T such that BT T A. Let the elemetary matrices of these operatios be,. Thus B A The matri A,,, are all ivertible. ( ) ( )... A B B... A A... A - The Rak of a Matri ad Matri Iverse I this sectio, we defie the rak of a matri. We the use elemetary operatios to compute the rak of a matri ad a liear trasformatio. The sectio cocludes with a procedure for computig the iverse of a ivertible matri. 何謂 矩陣的秩 (Rak)? 利用基本行列運算來計算矩陣與線性轉換的秩 本節還包括介紹如何計算可逆矩陣的反矩陣

6 Liear Algebra- Chapter /9/ DFINITION. Rak of a Matri If A M m (F), we defie the rak of A, deoted rak(a), to be the rak of the liear trasformatio L A : F F m. 若 A M m (F), 則矩陣 A 的秩為線性轉換 L A : F F m 的秩, 註記為 rak(a) A matri is ivertible if ad oly if its rak is. 一個 的矩陣為可逆的 若且唯若 條件為該矩陣的 Rak 為 very matri A is the matri represetatio of the liear trasformatio L A with respect to the appropriate stadard ordered bases. Thus the rak of the liear trasformatio L A is the same as the rak of oe of its matri represetatio, amely, A. 每一個矩陣 A 是線性轉換 L A 對於某個標準有序基底的矩陣表示式, 因此該線性轉換 L A 的 Rak 就等於矩陣表示式 A 的 Rak 即 rak(l A ) rak(a) DFINITION.9 Let V ad W be vector spaces, ad let T: V W be liear. If N(T) ad R(T) are fiitedimesioal, the we defie the ullity of T, deoted ullity(t), ad the rak of T, deoted rak(t), to be the dimesios of N(T) ad R(T), respectively. V 與 W 為向量空間, 且 T: V W 為線性轉換 定義 T 的核次數 (Nullity):ullity(T) dimesios of N(T) 定義 T 的秩 (Rak):rak(T) dimesio of R(T) 核次數 (Nullity) 與秩 (Rak) 分別代表 N(T) 與 R(T) 的維度 DFINITION. Let {u, u,, u } be a ordered basis for a fiite-dimesioal vectors space V. For V, let a, a,, a be the uique scalars such that 令 {u, u,, u } 為有限向量空間 V 的有序基底, 則存在唯一的一組純量 a, a,, a, 使得 V 內任意向量, 均可表達成該組基底的線性組合 : i a i u i we defie the coordiate vector of relative to, deoted [], by

7 Liear Algebra- Chapter /9/ [] a a : a. 稱為 相對於有序基底 的座標向量 DFINITION. Suppose that V ad W are fiite-dimesioal vector spaces with ordered bases {v, v,, v } ad γ {w, w,, w }, respectively. Let T: V W be liear. The for each j, j, there eist uique scalars a ij F, i m, such that m T( v ) a w for j j i ij i We call the m matri A defied by A ij a ij the matri represetatio of T i the ordered bases ad γ ad write γ A [T]. If V W ad γ, the we write A [T]. 設 V 與 W 分別為有限維度的向量空間, {v, v,, v } 與 γ {w, w,, w } 分別為 V 與 W 的有序基底, 且 T: V W 為 V 映至 W 的線性轉換 對每一個 j( j ) 而言, 存在唯一的純量 a ij F( i m), 使得 m T( v ) a w j i ij i 將 m 的矩陣 A 定義為 A ij a ij, 並稱呼 A 為線性轉換 T 的矩陣表達方式 在 γ V 與 W 分別以 與 γ 作為有序基底下,A 可註記為 A [T] 若 V W 且 γ, 則 A [T] m 提示 : T( v ) a w 為 將 v j 的像 T(v j ) 表達成有序基底 γ 的線性組合 j i ij i DFINITION.7 Let A be a m matri with etries from a field F. We deote by L A the mappig L A : F F m defied by L A () A (the matri product A ad ) for each colum vector F. We call L A a left-multiplicatio trasformatio. 令 A 是 m 的矩陣, 所有元素均來自 F L A 為 F 映至 F m 的線性轉換並定義為 L A () A, 其中 為行向量 (Colum vector) 且 F L A 被稱為左乘法轉換 7

8 Liear Algebra- Chapter /9/ The et theorem eteds this fact to ay matri represetatio of ay liear trasformatio defied o fiite-dimesioal vector spaces. Theorem. Let T: V W be a liear trasformatio betwee fiite dimesioal vector spaces, ad let ad γ be ordered bases for V ad W, respective. The rak(t) rak( [T] ). 令 T: V W, 且 與 γ 分別為有限維度向量空間 V 與 W 的有序基底, 則 rak(t) rak( [T] ) γ 改寫 Defiitio. Suppose that F ad F m are fiite-dimesioal vector spaces with ordered bases {v,v,,v } ad γ {w,w,,w }, respectively. Let L A : F F m be liear ad defied by L A () A. The for each j, j, there eist uique scalars a ij F, i m, such that L A (v ) j m i a ij w i for j. We call the m matri A defied by A ij a ij the matri γ represetatio of L A i the ordered bases ad γ ad write A [LA ]. γ Now that the problem of fidig the rak of a liear trasformatio has bee reduced to the problem of fidig the rak of a matri, we eed a result that allows us to perform rakpreservig operatios o matrices. The et theorem ad its corollary tell us how to do this. 線性轉換的 Rak 可以被簡化為找矩陣的 Rak 如何找矩陣的 Rak? Theorem. Let A be a m matri. If P ad Q are ivertible m m ad matrices, respectively, the 令 A 為 m 的矩陣, 若 P 與 Q 分別為可逆的 m m 與 矩陣, 則 (a) rak(aq) rak(a), (b) rak(pa) rak(a), (c) rak(paq) rak(a) Proof R(L AQ ) R(L A L Q ) L A L Q (F ) L A (L Q (F )) L A (F ) R(L A ) Sice L Q is oto, rak(aq) dim(r(l AQ )) dim(r(l A )) rak(a).

9 Liear Algebra- Chapter /9/ : rak(paq) rak(pa) rak(a). 註 :Theorem. 是為後續 Reduced Row chelo Form of Matri 做準備 : 一個矩陣經過基本行運算, 或基本列運算, 或基本行與列運算後, 並不會改變 RANK Corollary lemetary row ad colum operatios o a matri are rak-preservig. 矩陣的基本列與行運算不會改變矩陣的 Rak 此推論結果是計算反矩陣 解線性方程組的重要依據 Theorem. The rak of ay matri equals the maimum umber of its liearly idepedet colums; that is, the rak of a matri is the dimesio of the subspace geerated by its colum. 任一矩陣的 Rak 等於其最大線性獨立行向量數目 ; 即矩陣的 Rak 是由矩陣的行向量生成的子空間的維度 L A : F F m Proof For ay A M m (F), rak(a) rak(l A ) dim(r(l A )). Let be the stadard basis of F. The spas F ad hece, by Theorem., R(L A ) spa(l A ()) spa({l A (e ), L A (e ),, L A (e )}) But, for ay j, we have see i Theorem.(b) that L A (e j ) Ae j a j, where a j is the jth colum of A. Hece R(L A ) spa({a, a,..., a }) Thus rak(a) rak(l A ) dim(spa({a, a,..., a })). 對任意矩陣 A,rak(A) rak(l A ) dim(r(l A )). 令 為 F 的標準基底且生成 F 依據 Theorem. L A 的值域 Rage 可由 L A () 來生成 R(L A ) spa(l A ()) spa({l A (e ), L A (e ),, L A (e )}) 對任意 j 而言, 由 Theorem.(b) 可知 L A (e j ) Ae j a j 其中,a j 為 A 的第 j 個行 (a j 相當於 Theorem.(b) 的 v j 或 Theorem. 的 T(v j )), 因此 R(L A ) 9

10 Liear Algebra- Chapter /9/ spa({a, a,..., a }) 所以 rak(a) rak(l A ) dimesio of R(L A ) dim(spa({a,a,...,a })). Theorem. 令 V 與 W 為向量空間, 且 T: V W 為線性轉換 若 {v, v,, v } 是定義域 (Domai)V 的基底, 則 T 的值域 Rage R(T) 可由 T() 來生成 意即 R(T) spa(t()) spa({t(v ), T(v ),, T(v )}) Theorem. A 為 m 的矩陣與 B 為 p 的矩陣,u j 與 v j 分別為 AB 與 B 的第 j 行 ( j p ) 則 (a) u j A v j. (b) v j B e j, where e j is the j th stadard vector of F p. XAMPL Let A Observe that the first ad secod colums of A are liearly idepedet ad that the third colum is a liear combiatio of the first two. Thus A 的第一行與第二行是線性獨立, 第三行則是前兩行的線性組合 於是 rak(a) dim,, spa A 的第 行 :a 第 行 :a 第 行 :a I order to compute the rak of a matri A, it is frequetly useful to postpoe the use of Theorem. util A has bee suitable modified by meas of appropriate elemetary row ad colum operatios so that the umber of liearly idepedet colums is obvious. 為了利用 Theorem. 求矩陣 A 的 Rak( 等於最大線性獨立行向量數目 ),A 可先經過基本列或行運算, 使其線性獨立的行數變得比較明顯 XAMPL Let

11 Liear Algebra- Chapter /9/ A If we subtract the first row of A from rows ad (type elemetary row operatios), the result is If we ow substract twice the first colum from the secod ad substract the first colum from the third (type elemetary colum operatios), we obtai ( 後二行線性相依, 最大線性獨立行數為 ) It is ow obvious that the maimum umber of liearly idepedet colum of this matri is. Hece the rak of A is. Theorem. Let A be a m matri of rak r. The r m, r, ad, by meas of a fiite umber of elemetary row ad colum operatios, A ca be trasformed ito the matri Ir O D, where O, O, ad O are zero matrices. Thus D ii for i r ad O O D ij otherwise. 令 A 為 Rak 等於 r 的 m 矩陣, 則 r m 且 r 經過有限次數的基本行與列 Ir O 運算, 讓 A 化成 D 其中,I r 為對角元素為 的對角矩陣 即 A 可經 O O 過有限次數的基本行及列運算, 取得沿對角線前 r 個位置皆為, 其餘各處皆為 的 矩陣 D Proof If A is the zero matri, r. I this case, the coclusio follows with D A. 若 A 為零矩陣, 則 r 且 D A Now suppose that A O ad r rak(a); the r >. The proof is by mathematical iductio o m, the umber of rows of A. 若 A 非零矩陣且 r rak(a), 則 r >

12 Liear Algebra- Chapter /9/ 採用數學歸納法 Suppose that m A ca be trasformed ito the matri (,,.). So rak(d) rak(a) by Corollary to Theorem. ad Theorem.. Thus the theorem is established for m. 設 m, 則 A 可以化成 (,,.) 依據 Corollary to Theorem. 及 Theorem., rak(d) rak(a), 故本定理對 m 的矩陣是成立的 Net assume that the theorem holds for ay matri with at most m - row (for some m >). We must prove that the theorem holds for ay matri with m rows. 其次, 假設本定理對至多含 m - 列的矩陣皆成立 (m > ) 至於含 m 列的矩陣是否成立? If, Theorem. ca be established i a maer aalogous to that for m. 若, 則可按 m 的方式證明本定理對於 的矩陣成立 We ow suppose that >. Sice A O, A ij for some i, j. By meas of at most oe elemetary row ad at most oe elemetary colum operatio (each of type ). We ca move the ozero etry to the, positio. By meas of of at most oe additioal type operatio, we ca assure a i the, positio. By meas of at most m type row operatios ad at most type colum operatios, we ca elimiate all ozero etries i the first row ad the first colum with the eceptio of the i the, postio. Thus, with a fiite umber of elemetary operatio, A ca be trasformed ito a matri 經過有限次數的基本行及列運算, 可將 A 轉換成.. B where B is a (m-) (-) matri : B' B has rak oe less tha B. B 的 Rak 比 B 少 Sice rak(a) rak(b) r, rak(b ) r. Therefore r m ad r

13 Liear Algebra- Chapter /9/ by the iductio hypothesis. Hece r m ad r. 由於 rak(a) rak(b) r, 故 rak(b ) r 依數學歸納法 r m 且 r 因此 r m 且 r Also by the iductio hypothesis, B ca be trasformed by a fiite umber of elemetary row ad colum operatios ito the (m-) (-) matri D such that 同樣地, 依據數學歸納法,B 可經過有限次數的基本行與列運算轉換成 (m- ) (-) 的矩陣 D, 使得 Let I r O D where O, O, ad O are zero matrices. O O That is, D cosists of all zeros ecept for its first r- diagoal etries, which are oes... D : D' We see that the theorem ow follows oce we show that D ca be obtaied from B by meas of a fiite umber of elemetary row ad colum operatios. D 可由 B 經過有限次基本行及列運算而取得 Thus, sice A ca be trasformed ito B ad B ca be trasformed ito D, each by a fiite umber of elemetary operatios, A ca be trasformed ito D by a fiite umber of elemetary operatios. 經過有限次基本行及列運算 :A B D Fially, sice D cotais oes as its first r diagoal etries, D cotais oes as its first r diagoal etries ad zeros elsewhere. 最後,D 沿對角線前 r- 個位置皆為, 故 D 沿對角線前 r 個位置皆為, 其餘 各處皆為 XAMPL Cosider the matri A. 9

14 Liear Algebra- Chapter /9/ By meas of a successio of elemetary row ad colum operatios, we ca trasform A ito a matri D as i Theorem.. 透過一系列的基本行與列運算, 將 A 轉換成 D A... D 9 By the corollary to Theorem., rak(a) rak(d). Clearly, however, rak(d) ; so rak(a). Corollary Let A be a m matri of rak r. The there eist ivertible matrices B ad C of sizes m m ad, respectively, such that D BAC, where D i which O, O, ad O are zero matrices. Ir O O is the m matri O 令 A 為 m 的矩陣,Rak 為 r 存在可逆的 m m 矩陣 B 與 矩陣 C, 使得 D BAC; 其中,D Proof Ir O O 為 m 的矩陣,O O 及 O 為零矩陣 O By Theorem., A ca be trasformed by meas of a fiite umber of elemetary row ad colum operatios ito the matri D. We ca appeal to Theorem. each time we perform a elemetary operatio. Thus there eist elemetary m m matrices,,, p ad elemetary matrices G, G,,G q such that D p p- AG G G q. By Theorem., each j ad G j is ivertible. Let B p p- ad C G G G q. The B ad C are ivertible, ad D BAC. 依據 Theorem.,A 可經過有限次的基本列與行運算化成 D 引用 Theorem., 每一次皆實施某一個基本列運算, 於是存在基本的 m m 矩陣,,, p 與基本的 矩陣 G, G,, G q, 使得 D p p- AG G G q 依據 Theorem. 每一個基本矩陣 j 與 G j 皆為可逆, 令 B p p- 與 C G G G q, 於是 B 與 C 皆為可逆, 且 D p p- AG G G q BAC

15 Liear Algebra- Chapter /9/ Theorem. 令 A M m (F) 並假設 B 是由 A 經實施某一基本列 或行 運算後所得到的矩陣, 則存在一個 m m 或 基本矩陣, 使得 B A 或 B A 矩陣是由 I m 或 I 經實施與 由 A 得到 B 相同的基本列 或行 運算後所得到的矩陣 反之, 若 是一個 m m 或 的基本矩陣, 則 A 或 A 是由 A 經過與 由 I m 或 I 得到 相同的基本列 或行 運算後所得到的矩陣 Theorem. 基本矩陣為可逆矩陣, 且基本矩陣的反矩陣亦是同一型的基本矩陣 Theorem. 令 A 為 Rak 等於 r 的 m 矩陣, 則 r m 且 r 經過有限次數的基 Ir O 本行與列運算, 讓 A 化成 D 其中,I r 為對角元素為 的對角矩陣 O O Corollary Let A be a m matri. The (a) rak(a t ) rak(a). 矩陣轉置後的 RANK 不變 (b) The rak of ay matri equals the maimum umber of its liearly idepedet rows; that is, the rak of a matri is the dimesio of the subspace geerated by rows. 任一矩陣的 Rak 等於最大線性獨立列向量的數目, 即矩陣的 Rak 等於由該矩陣列向量所生成的子空間的維度 (c) The rows ad colums of ay matri geerate subspaces of the same dimesio, umerically equal to the rak of the matri. 任一矩陣的列向量與行向量生成的子空間的維度相同, 維度等於該矩陣的 Rak Proof By Corollary, there eist ivertible matrices B ad C such that D BAC, where D satisfies the stated coditios of the corollary. Takig trasposes, we have D t (BAC) t C t A t B t Sice B ad C are ivertible, so are B t ad C t. Hece by Theorem., rak(a t ) rak(c t A t B t ) rak(d t ). Suppose that r rak(a). The D t is a m matri with the form of the matri D i Corollary, ad hece

16 Liear Algebra- Chapter /9/ rak(d t ) r by Theorem.. Thus rak(a t ) rak(d t ) r rak(a) 依據 Corollary, 存在可逆矩陣 B 與 C, 使得 D BAC 取其轉置可得 :D t (BAC) t C t A t B t 由於 B 與 C 為可逆, 故 B t 與 C t 亦為可逆 依據 Theorem., 得知 rak(a t ) rak(c t A t B t ) rak(d t ) 設 r rak(a) 則 D t 為一 m 的矩陣, 型式與 D 相同 ( 參考 Corollary ) 且依據 Theorem. 得知 rak(d t ) r 於是 rak(a t ) rak(d t ) r rak(a) Theorem. Let A be a m matri. If P ad Q are ivertible m m ad matrices, respectively, the 令 A 為 m 的矩陣, 若 P 與 Q 分別為可逆的 m m 與 矩陣, 則 (a) rak(aq) rak(a), (b) rak(pa) rak(a), (c) rak(paq) rak(a) Theorem. The rak of ay matri equals the maimum umber of its liearly idepedet colums; that is, the rak of a matri is the dimesio of the subspace geerated by its colum. 任一矩陣的 Rak 等於其最大線性獨立行向量數目 ; 即矩陣的 Rak 是由矩陣的行向量生成的子空間的維度 L A : F F m Corollary very ivertible matri is a product of elemetary matrices. 每一可逆矩陣均可為基本矩陣的乘積 Proof If A is a ivertible matri, the rak(a). Hece the matri D i Corollary equals I, ad there eist ivertible matrices B ad C such that I BAC. As i the proof of Corollary, ote that B p p- ad C G G G q, where the i s ad G i s are elemetary matrices. Thus A B - I C - B - C -, so that A p G - q G - q- G -.

17 Liear Algebra- Chapter /9/ The iverses of elemetary matrices are elemetary matrices, however, ad hece A is the product of elemetary matrices. 若 A 為可逆的 矩陣, 則 rak(a) 因此 Corollary 中的矩陣 D 為 I, 且存在可逆的 B 與 C 矩陣, 使得 I BAC 如同 Corollary 的證明一樣,B p p- 且 C G G G q 其中, i s 與 G i s 皆為基本矩陣 於是,A B - I C - B - C - 即 A p G - q G - q- G - 基本矩陣的反矩陣亦為基本矩陣,A 是基本矩陣的乘積 Theorem.7 Let T: V W ad U: W Z be liear trasformatios o fiite-dimesioal vector spaces V, W, ad Z, ad let A ad B be matrices such that the product AB is defied. The 令 V W 與 Z 為有限維度的向量空間,T: V W 與 U: W Z 為線性轉換, 且 A 與 B 為滿足乘積 AB 定義的矩陣 則 (a) rak(ut) rak(u). (b) rak(ut) rak(t). (c) rak(ab) rak(a). (d) rak(ab) rak(b). Proof (a) Clearly, R(T) W. Hece R(UT) UT(V) U(R(T)) U(W) R(U). Thus rak(ut) dim(r(ut)) dim (R(U)) rak(u). (c) By (a) rak(ab) rak(l AB ) rak (L A L B ) rak(l A ) rak(a). (d) By (c) ad Corollary to Theorem. rak(ab) rak((ab) t ) rak(b t A t ) rak(b t ) rak (B). (b) Let α, ad γ be ordered bases for V, W, ad Z, respectively, ad let A γ [ U] ad B [ T] α. The A B γ [ UT] α by Theorem.. Hece, by Theorem. ad (d) rak(ut) rak(a B ) rak(b ) rak (T). Theorem. Let V, W, ad Z be fiite-dimesioal vector space with ordered bases α,, ad γ, respectively. Let T: V W ad U: W Z be liear trasformatio. The 7

18 Liear Algebra- Chapter /9/ [UT] γ α [U] [T] γ α. 令 V W 與 Z 是有限維度的向量空間,α 與 γ 分別為 V W 與 Z 的有序基底 令 T: V W ( 先 α ) 且 U: W Z ( 後 γ ), 則 [UT] γ [U] γ [T] α α Theorem. Let T: V W be a liear trasformatio betwee fiite dimesioal vector spaces, ad let ad γ be ordered bases for V ad W, respective. The rak(t) rak( [T] ). 令 T: V W, 且 與 γ 分別為有限維度向量空間 V 與 W 的有序基底, γ 則 rak(t) rak( [T] ) γ XAMPL (a) Let A ( 第一列與第二列是 LI) rak(a). (b) Let A ( 第三列與第一 二列是 LD)rak(A) (c) Let A ( 三列為 LI) rak(a) The iverse of a Matri We have remarked that a matri is ivertible if ad oly if its rak is. Sice we kow how to compute the rak of ay matri, we ca always test a matri to determie whether it is ivertible. We ow provide a simple techique for computig the iverse of a matri that utilizes elemetary row operatios. 已知 矩陣為可逆的 若且唯若 條件為該矩陣的 Rak 等於 DFINITION. Augmeted Matri Let A ad B be m ad m p matrices, respectively. By the augmeted matri ( A B), we mea that the m (p) matri ( A B) ; that is, the matri whose first colums are the colums of A ad whose last p colums are the colums of B. 設 A 與 B 分別為 m 與 m p 的矩陣, 則增廣矩陣 (Augmeted matri) (A B)

19 Liear Algebra- Chapter /9/ 為一 m (p) 的矩陣 ( A B), 該矩陣的前 行 (Colum) 為 A 的所有的行, 後 p 行為 B 的所有行 Let A be a ivertible matri, ad cosider the augmeted matri C ( A I ). C ( A I ) A C (A A A I ) (I A ). By Corollary to Theorem., A - is the product of elemetary matrices, say A p p-. (A - 是多個基本矩陣的乘積 ) Thus A C (A A A I ) (I A )... (A I ) A C (I A ). p p We have the followig result: If A is a ivertible ivertible matri, the it is possible to trasform the matri (A I ) ito the matri (I A - ) by meas of a fiite umber of elemetary row operatios. 若 A 為一可逆的 矩陣, 則可經過有限次數的基本列運算將矩陣 (A I ) 化成 (I A - ) Coversely, suppose that A is ivertible ad that, for some matri B, the matri (A I ) ca be trasformed ito the matri (I B) by a fiite umber of elemetary row operatios. Let,,, p be the elemetary matrices associated with these elemetary row operatios as i Theorem.; the 反之, 假設 A 是可逆且矩陣 (A I ) 可經有限次數的基本列運算轉換成矩陣 (I B), 並令,,, p 分別為 Theorem. 所稱的基本矩陣, 則... (A I p p ) (I B) Let M p p-, we have 令 M p p- p p...(a I ) (I B) ( MA M) M(A I ) (I B) 9

20 Liear Algebra- Chapter /9/ Hece MA I ad M B. It follows that M A -. So B A -. 可由 MA I 及 M B 得知 :M 就是 A -, 故 B 就是 A - Thus we have the follow results:if A is a ivertible matri, ad the matri (A I ) is trasformed i a matri of the form (I B) by meas of a fiite umber of elemetary row operatios, the BA -. 若 A 為一可逆的 矩陣, 且矩陣 (A I ) 可經有限次數的基本列運算化成 (I B), 則 BA - If, o the other had, A is a matri that is ot ivertible, the rak(a) <. Hece ay attempt to trasform (A I ) ito a matri of the form (I B) by meas of elemetary row operatios must fail. 反之, 若 A 是一不可逆的 矩陣, 則 rak(a) < 因此任何想利用基本列運算要將矩陣 (A I ) 化成 (I B) 的努力必定失敗 Thus we have the follow results: If A is a otivertible matri, the ay attempt to trasform (A I ) ito a matri of the form (I B) produce a row whose first etries are zeros. 若 A 是一不可逆的 矩陣, 任何想將矩陣 (A I ) 化成 (I B) 的努力, 最後會產生一前 個元素均為 的列 XAMPL We determie whether the matri A is ivertible, ad if it is, we compute its iverse. A 是否為可逆矩陣? We attempt to use elemetary row operatios to trasfer

21 Liear Algebra- Chapter /9/ A I) ( ito a matri of the form (I B) 看看能否利用基本行與列運算將矩陣 (A I ) 化成 (I B)? Iterchagig rows ad : Multiplyig the first row by /: Addig - times row to row : Multiplyig row by / to obtai i the, positio: Addig - times row to row ad times row to row : Multiplyig row by /: Addig appropriate multiply of row to row ad completes the process: 目標達成! Thus A is ivertible, ad A

22 Liear Algebra- Chapter /9/ XAMPL We determie whether the matri A is ivertible, ad if it is, we compute its iverse. A 是否為可逆矩陣? We attempt to use elemetary row operatios to trasfer A I) ( ito a matri of the form (I B) 看看能否利用基本行與列運算將矩陣 (A I ) 化成 (I B)? Addig - times row to row ad - times row to row, the addig row to row : is a matri with row whose first etries are zeros. Therefore A is ot ivertible. 最後一列前 個元素均為 XAMPL 7 Let T: P (R) P (R) be defied by T(f()) f()f ()f (), where f () ad f () deote the first ad secod derivatives of f(). We use Corollary to Theorem. to test T for ivertibility ad compute the iverse if T is ivertible. Takig {,, } to be the stadard ordered basis of P (R), we have 令 T: P (R) P (R) 為線性轉換且定義為 T(f()) f()f ()f () 利用 Corollary to Theorem. 來測試 T 是否可逆? 並計算其逆轉換 取 {,, } 為 P (R) 的標準有序基底 T() T()

23 Liear Algebra- Chapter /9/ T( ) [T] 稱為 T 相對有序基底 的座標向量 [T 依據 Corollary to Theorem., T 可逆 若且唯若 - ] ([T] ) [T] 可逆且 Usig the method of amples ad, we ca show that [T] is ivertible with iverse ([T] ) Thus T is is ivertible, ad ([T] [T (a a a )] ) [T ] a a a. Hece by Theorem., we have a a a a a Therefore T - (a a a ) (a -a )(a -a )a. Corollary to Theorem. Let V be fiite-dimesioal vector space with a ordered basis, ad let T: V V be liear. The T is ivertible if ad oly if [T] is ivertible. - Furthermore, [T ] ([T] ). V 為有限維度的向量空間, 是 V 的有序基底, 令 T: V V 為線性轉換 T 為可逆的 若且唯若 條件為 [T] 可逆 再者, [T - ] ([T] ) Theorem. Let V ad W be fiite-dimesioal vector spaces havig ordered bases ad γ, respectively, ad let T: V W be liear. The, for each u V, we have [T(u)] [T] γ [u]. γ V 與 W 為有限維度的向量空間, 與 γ 分別 V 與 W 的有序基底 令 T: V W 為線 性轉換, 則 V 中的 u 映至 W 的結果 T(u) 相對於有序基底 γ 的座標向量為 [T(u)] [T] [u] γ γ Ivertible ad Iverse of MATRIX Let A be a matri. If a matri B ca be foud such that AB BA I, the A is

24 Liear Algebra- Chapter /9/ said to be ivertible ad B is called the iverse of A. (deote B A -, ad A -k (A - ) k ) If such a matri B does ot eist, the A has o iverse. XAMPL A ad B AB I BA I Thus AB BA I, provig that the matri A has iverse B. Theorem The iverse of a ivertible matri is uique. Let B ad C be iverse of A. Thus AB BA I, ad AC CA I. Multiply both sides of the equatio AB I by C. C(AB) CI (CA)B C I B C B C Thus a ivertible matri has oly oe iverse.. How to fid A - Based o the Gauss-Jorda algorithm. Let A be a ivertible matri. The AA - I Let the colums of A - be X, X,, X, ad the colums of I be C,C,,C Let A X X L X, I C C L C [ ] [ ] Fid A - by fidig X, X,, X. Write the equatio AA - I i the form [ X L X] [ C C L C] [ A X AX L AX ] [ C C L C] AX C, AX C, L,AX A X Thus C How to fid A - Solvig these systems by usig Gauss-Jorda elimiatio o the large augmeted matri [A:C C.C ] augmeted matri : [ A : C C L C] L [ I ] Thus, whe A - : X X L X eits. [ A : I ] L [ I : A ] [ I : B] where B A If the reduced echelo form of [A:I[ ] is computed ad the first part is ot of the form I the A has o iverse.

25 Liear Algebra- Chapter /9/ ample / Determie the iverse of A [ A : I ] R ( ) R R R ( )R ample / R R R ( )R R R R ( )R A. ample Determie the iverse of [ A: I] 7 A R ( )R R ( )R R ( )R R R 7 There is o eed to proceed further. The reduced echelo form caot have a oe i the (, ) locatio. The reduced echelo form caot be of the form [I : B]. Thus A does ot eist. Color Models / A color model i the cotet of graphics is a method of implemetig colors. The commo used models iclude RGB model ad YIQ model. The RGB model is used i computer moitors, ad the YIQ model is used i televisio screes. A RGB computer sigal ca be coverted to a YIQ televisio sigal usig the matri trasformatio Y R I.9.7. G YIQ>RGB Q... B Properties of Matri Iverse Let A ad B be ivertible matrices ad c a ozero scalar. The. ( A ) A. ( ca) A c. ( AB) B A Color Models /. ( A ) ) ( A. ( A ) t t ) ( A A sigal is coverted from a televisio scree to a computer moitor usig iverse of the above matri. R Y G.9.7. I B... Q R.9. Y G.7.7 I B..7 Q Cryptography 密碼學 / Cryptography 密碼學 / Cryptography is the process of codig ad decodig messages. The techique ca be traced back to the aciet Greeks. Today govermets use sophisticated methods of codig ad decodig messages. Oe type of code that is etremely difficult to break makes use of a large matri to ecode a message. The receiver of the message decodes it usig the iverse of the matri. The first matri is called the ecodig matri, ad its iverse is called the decodig matri. Message A A - codig Matri Trasmissio Decodig Matri Decoded Message

26 Liear Algebra- Chapter /9/ ample / Let the message be BUY IBM STOCK Ad the ecodig matri be B U Y - I B M - S T O C K codig ample / Let the message be BUY IBM STOCK Ad the decodig matri be B U Y - I B M - S T O C K Decodig Systems of Liear quatios Theoretical Aspects The system of equatios a a a... m a a a m... a... a... a were a ij ad b i ( i m ad j ) are scalars i a field F ad,,, are variables takig values i F, is called a system of m liear equatios i ukows over the field F. 上式稱為佈於 Field F 含有 個未知數 m 個線性方程式的系統或方程組 (system of m liear equatios i ukows) m b b b m (S) a a.. a a a.. a The m matri A is called the coefficiet matri of the : : : a m a m.. a m b b system (S)( 係數矩陣 ). If we let : ad b. The the system (S) may : bm be rewritte as a sigle matri equatio A b.( 單一矩陣方程式 ) To eploit the results that we have developed, we ofte cosider a system of liear equatios as a sigle matri equatio.

27 Liear Algebra- Chapter /9/ 7 A solutio to the system (S) is a -tuple F s : s s s such that As b. The set of all solutios to the system (S) is called the solutio set of the system( 解集合 ). System (S) is called cosistet ( 相容 )if its solutio set is oempty; otherwise it is called icosistet( 不相容 ). 方程組 (S) 的解為一 序組, 該序組可以使 As b 方程組的所有解所成的集合稱為該方程組的解集合 (Solutio set) 方程組的解集合非空集合者, 稱為 相容 ; 解集合空集合者, 稱為 不相容 XAMPL Cosider ; that is, ( 以矩陣表示 ) This system has may solutios, such as 7 s ad s Cosider ; that is, 顯然地, 方程組無解 We begi our study of system of liear equatios by eamiig the class of homogeeous system of liear equatios. 先討論齊次方程組 DFINITION. Homogeeous & Nohomogeeous A system Ab of m liear equatios i ukows is said to be homogeeous if b. Otherwise the system is said to be ohomogeeous. 方程組 A b:b 稱為齊次方程組, 否則稱為非齊次方程組 Ay homogeeous system has at least oe solutio, amely, the zero vector. The et result gives further iformatio about the set of solutios to a homogeeous system.

28 Liear Algebra- Chapter /9/ 齊次方程組至少有一個解, 那就是 零向量 Theorem. Let A be a homogeeous system of m liear equatios i ukows over a field F. Let K deote the set of all solutios to A. The K N(L A ); hece K is a subspace of F of dimesio - rak(l A ) - rak(a). 令 A 代表一佈於 Field 含有 個未知數 m 個線性方程式的方程組 若令 K 代表該方程組的解集合 (Solutio set), 則 K N(L A ) K 為 F 內的子空間且其維 度為 rak (L A ) - rak(a) Proof Clearly, K {s F : As } N(L A ). The secod part ow follows from the dimesio theorem. Nullity(T)rak(T) dim(v) Nullity (L A ) dim (F ) rak (L A ) rak (A) DFINTION.7 Let V ad W be vector space, ad let T: V W be liear. We defie the ull space (or kerel) N(T) of T to be the set of all vectors i V such that T() ; that is, N(T) { V: T() }. V 與 W 為向量空間, 且 T: V W 為線性轉換 定義 線性轉換 T 的 Null space 為 V 內所有滿足 T() 的向量 所形成的集合, 註記為 N(T) Null space 的元素 經線性轉換 T 轉換後所對應的 像 為, 意即 T() Null space 內的元素的 像 皆為 DFINITION.7 Let A be a m matri with etries from a field F. We deote by L A the mappig L A : F F m defied by L A () A (the matri product A ad ) for each colum vector F. We call L A a left-multiplicatio trasformatio. 令 A 是 m 的矩陣, 所有元素均來自 F L A 為 F 映至 F m 的線性轉換並定義為 L A () A, 其中 為行向量 (Colum vector) 且 F L A 被稱為左乘法轉換 Theorem. (Dimesio Theorem) Let V ad W be vector spaces, ad let T: V W be liear. If V is fiite-dimesioal, the Nullity(T) rak(t) dim(v). T 的核次數 (Nullity) 與秩 (Rak) 的和, 等於定義域的維度 dim(v) Corollary Let A be a homogeeous system of m liear equatios i ukows over a field

29 Liear Algebra- Chapter /9/ 9 F. If m <, the system A has a ozero solutio. 令 A 代表一佈於 Field 含有 個未知數 m 個線性方程式的方程組 若 m <, 則該方程組具有一非零解 Proof Suppose that m <. The rak(a) rak (L A ) m. Hece dim(k) - rak(l A ) m >, where K N(L A ). Sice dim(k) >, K {}. Thus there eists a ozero vector s K; so s is a ozero solutio to A. 設 m <, 則 rak(a) rak (L A ) m 依據 Theorem.,K {s F : As } N(L A ) dim(k) - rak(l A ) m >, 表示 dim(k) >,K {}, 故存在非零向量 s, 使得 A XAMPL Cosider Let A be the coefficiet matri of this system. It is clear that rak(a). If K is the solutio set of this system, the dim(k) -. Thus ay ozero solutio costitutes a basis for K. 若 K 是方程組的解所組成的集合 ( 簡稱為解集合 ), 依 Theorem. 得知 dim(k) -, 因此任一非零解將形成 K 的基底 For eample, sice is a solutio to the give system, is a basis for K. Thus ay vector i K is of the form t t t t where t R. 例如, 因 是方程組的一個解, 故 為 K 的基底,K 內的任一向量均具有如下形式 : t t t t

30 Liear Algebra- Chapter /9/ We ow tur to the study of ohomogeeous systems. Our et result shows that the solutio set of a ohomogeeous system A b ca be described i terms of the solutio of the homogeeous system A. We refer to the equatio A as the homogeeous system correspodig to A b. 以下將進一步探討 非齊次方程組 非齊次方程組 A b 的解集合可利用齊次方程組 A 的解來加以說明 因此我們可將 A 視為 A b 的齊次方程組 Theorem.9 Let K be the solutio set of a system of liear equatios A b, ad let K H be the solutio set of the correspodig homogeeous system A. The for ay solutio s to A b, K {s} K H {sk: k K H }. 設 K 為線性方程組 A b 的解集合, 且 K H 為對應的齊次方程組的解集合, 則對 A b 的任一個解 s 而言,K {s} K H {sk: k K H } Proof Let s be ay solutio to A b. We must show that K {s} K H. If w K, the Aw b. Hece A(w - s) Aw As b b. So w - s K H. Thus there eists k K H such that w - s k. It follows that w s k {s} K H, ad therefore K {s} K H. Coversely, suppose that w {s} K H ; the w s k for some k K H. But the Aw A(s k) As Ak b b; so w K. Therefore {s} K H K, ad thus K{s} K H. 令 s 為 A b 的任一個解, 我們必須證明 K {s} K H 若 w K, 則 Aw b( 即 w 為 A b 的解 ) 於是 A(w - s) Aw As b b 所以 w - s K H ( 即 w-s 為 A 的解 ) w - s 既然是 K H 的元素, 表示有一元素 k K H, 使得 w - s k,w s k w s k {s} K H

31 Liear Algebra- Chapter /9/ 因此 K {s} K H 反之, 假設 w {s} K H, 則 K H 中存在一元素 k(k K H ), 使得 w s k 因 Aw A(s k) As Ak b b 故 w K 是 A b 的解 因此 {s} K H K 總結 :K{s} K H XAMPL Cosider 7 The correspodig homogeeous system is the system i ample. It is easily verified that s is a solutio to the preceedig ohomogeeous system. So the solutio set of the system is R t : t K by Theorem.9. s 是非齊次方程組 A b 的解, 是齊次方程組的解 依據 Theorem.9 得知線性方程組 A b 的解集合 R t : t K The followig theorem will provide us with a meas of computig solutios to certai system of liear equatios. Theorem.~. 提供計算線性方程組的解的方法 Theorem. Let A b be a system of liear equatios i ukows. If A is ivertible, the the

32 Liear Algebra- Chapter /9/ system has eactly oe solutio, amely, A - b. Coversely, if the system has eactly oe solutio, the A is ivertible. 令 A b 為含 個未知數 個線性方程式的方程組, 若 A 為可逆, 則方程組恰有一個解, 解為 A - b 反之, 若該方程組恰有一個解, 則 A 為可逆 Proof Suppose that A is ivertible. Substitutig A - b ito system, we have A(A - b)( AA - )b b. Thus A - b is a solutio. If s is a arbitrary solutio, the As b. Multiplyig both sides by A - gives s A - b. Thus the system has oe ad oly oe solutio, amely, A - b. 假設 A 為可逆, 將 A - b 代入方程組可得 A(A - b)( AA - )b b 故 A - b 確為方程組的解 若 s 為方程組的任意解, 則 As b 兩邊乘上 A -, 可得 s A - b 因此, 方程組僅有唯一的解 A - b Coversely, suppose that the system has eactly oe solutio s. Let K H deot the solutio set for the correspodig homogeeous system A. By Theorem.9, {s} {s} K H. But it is so oly if K H {}. Thus N(L A ) {}, ad hece A is ivertible. 反之, 假設方程組恰有一個解 s 令 K H 為相對應齊次方程組 A 的解集合 依據 Theorem.9, 要能 {s} {s} K H, 唯有 K H {} K H {}, 即表示 N(L A ) {}, 故 A 為可逆 XAMPL Cosider the followig system of three liear equatios i three ukows: I ample of Sectio., we compute the iverse of the coefficiet matri A of this system. Thus the system has eactly oe solutio, amely,

33 Liear Algebra- Chapter /9/ A A A b 7 Theorem. Let A b be a system of liear equatios. The the system is cosistet ( 相容 )if ad oly if rak(a) rak (A b). Matri (A b) is called the augmeted matri of the system A b. 令 A b 為線性方程式方程組, 則此方程組至少有一個解的 若且唯若 條件為 rak(a) rak (A b) 矩陣 (A b) 稱為方程組 A b 的增廣矩陣 Proof To say that A b has a solutio is equivalet to sayig that b R(L A ). I the proof of Theorem., we saw that R(L A ) spa({a, a,..., a }), the spa of the colum of A. Thus A b has a solutio if ad oly if b spa({a, a,..., a }). But b spa({a, a,..., a }) if ad oly if spa({a, a,..., a }) spa({a, a,..., a, b}). This last statemet is equivalet to dim (spa({a,a,...,a })) dim (spa({a,a,...,a, b})). So by Theorem., the preceedig equatio reduces to rak(a) rak (A b). A b 有一解, 相當於 b R(L A ), 即 b 屬於線性轉換 L A 的 Rage 在 Theorem. 的證明中提到 R(L A ) spa({a,a,...,a }),a j 為 A 的第 j 個行 (Colum), 即線性轉換 L A 的 Rage 係由矩陣 A 的行 (Colum) 所生成 因此 A b 要有一個解的 若且唯若 條件為 b spa({a, a,..., a }) 至於 b spa({a, a,..., a }) 之條件? b spa({a,a,...,a }) 的 若且唯若 條件為 spa({a,a,...,a }) spa({a,a,...,a, b}) 其條件相當於 :

34 Liear Algebra- Chapter /9/ dim (spa({a,a,...,a })) dim (spa({a,a,...,a, b})) 依據 Theorem., 該條件可簡化為 rak(a) rak (A b) Theorem. The rak of ay matri equals the maimum umber of its liearly idepedet colums; that is, the rak of a matri is the dimesio of the subspace geerated by its colum. 任一矩陣的 Rak 等於其最大線性獨立行向量數目 ; 即矩陣的 Rak 是由矩陣的行向量生成的子空間的維度 L A : F F m XAMPL Recall the system of equatios Sice A ad ( A b) rak(a) ad rak (A b). Because the two raks are uequal, the system has o solutios. 矩陣 A 與增廣矩陣 (A b) 的 Rak 不同, 故方程組沒有解 XAMPL We ca use Theorem. to determie whether (,, ) is i the rage of the liear trasformatio T: R R defied by T(a, a, a ) (a a a, a -a a, a a ). 利用 Theorem. 來判斷 (,, ) 是否在線性轉換 T 的 Rage 中? 其中,T: R R 定義為 T(a, a, a ) (a a a, a -a a, a a ) Now (,, ) R(T) if ad oly if there eists a vector s {,, } i R such that T(s)(,, ). Such a vector s must be a solutio to the system Sice the raks of the coefficiet matri ad the augmeted matri of this system are ad, respectively, it follows that this system has o solutios. Hece (,, ) R(T). (,, ) R(T) 的 若且唯若 的條件為存在一向量 s {,, } R, 使得 T(s)(,, )

35 Liear Algebra- Chapter /9/ 向量 s 必須是 因係數矩陣 的解 的 Rak 為, 增廣矩陣 的 Rak 為 兩 者不相等, 故方程組無解,(,, ) R(T) Theorem. Let A b be a system of liear equatios. The the system is cosistet ( 相容 )if ad oly if rak(a) rak (A b). Matri (A b) is called the augmeted matri of the system A b. 令 A b 為線性方程式方程組, 則此方程組至少有一個 解的 若且唯若 條件為 rak(a) rak (A b) 矩陣 (A b) 稱為方程組 A b 的 增廣矩陣 Applicatio I 97, Wassily Leotief wo the Nobel prize i ecoomics for his work i developig a mathematical model that ca be used to describe various ecoomic pheomea. 97 年,Wassily Leotief 因研究一數學模式來描述各種經濟現象而獲頒諾貝爾經濟獎 CLOSD MODL We begi by cosiderig a simple society composed of three peoples (idustries) a farmer who gows all the food, a tailor who makes all the clothig, ad a carpeter who builds all the housig. We assume that each perso sells to ad buy from a cetral pool ad that everythig produced is cosumed. Sice o commodities either eter or leave the system, this case is referred to as the CLOS MODL. 考慮一個單純社會的三種人 : 生產食物的農夫 製衣的裁縫師與蓋住屋的木匠 並假設採取集中聯營買賣, 且每一件產品皆付諸消費, 由於過程中沒有任何成品進入或脫離這個系統, 所以稱為 封閉模式 ach of these three idividual cosumes all three of the commodities produced i the

36 Liear Algebra- Chapter /9/ society. Suppose that the proportio of each of the commodities cosumed by each perso is give i the followig table. 社會中每一位皆消費所生產的三種成品, 且每一種產品也都被三位所消費, 其消費比例如下 : 食物 Food 衣物 Clothig 住屋 Housig 農夫 Farmer... 裁縫師 Tailor..7. 木匠 Carpeter... Let p, p, ad p deote the icomes of the farmer, tailor, ad carpeter, respectively. To esure that this society survives, we require that the cosumptio of each idividual equals his or her icome. 令 p p 與 p 分別表示農夫 裁縫師與木匠的收入, 並為確保這個封閉社會可以存活, 假設每一位的收入等於消費 Note that the farmer cosumes % of the clothig. Because the total cost of all clothig is p, the tailor s icome, the amout spet by the farmer o clothig is. p. Moreover, the amout spet by the farmer o food, clothig, ad housig must equal the farmer s icome, ad so we obtai the equatio. p. p. p p. 對農夫而言, 農夫的衣物消費佔 %, 然因所有衣物的消費總額 p 等於裁縫師的 收入, 所以農夫在衣物上的消費為. p, 且農夫在食物 衣物與住屋的總消費要等 於農夫的收入 p, 所以農夫的收入與消費關係式 :. p. p. p p Similary equatios describig the epeditures of the tailor ad carpeter produce the followig system of liear equatios: 同理, 分別對裁縫師與木匠進行討論, 可獲得下列方程組 :

37 Liear Algebra- Chapter /9/. p. p. p p. p.7 p. p p. p. p. p p This system ca be writte as Ap p. p 其中, p p p. 且 A (Iput-output (or cosumptio) matri).. 稱為輸入 - 輸出 ( 或消費 ) 矩陣. Ap p 稱為均衡條件 (quilibrium coditio) 能否利用不等式 p p 來替代等式? At first, it may seem reasoable to replace the equilibrium coditio by the iequality Ap p, that is, the requiremet that cosumptio ot eceed productio? But, i fact, Ap p implies that Ap p i the closed model. For otherwise, there eists a k for which p k > A kjp j. j Hece, sice the colums of A sum to. i > Aijp j... i p p, which is a cotradictio. ( 出現矛盾 ) i j 答案是在封閉系統中,Ap p Ap p j j Oe solutio to the homogeeous system (I A), which is equivalet to the. equilibrium coditio, is p.. 7

38 Liear Algebra- Chapter /9/ 齊次方程組 (I A) 或均衡條件的一個解為. p.. We may iterpret this to mea that the society survives if the farmer, taior, ad carpeter have icomes i the proportios ::.. p. 可以解釋為 : 若農夫 裁縫師與木匠收入比例為 ::, 則社會將. 能生存下去 Theorem. B C Let A be a iput-output matri havig the form A, where D is a (- D ) positive vector ad C is a (-) positive vector. The (I-A) has a oedimesioal solutio set that is geerated by a oegative vector. B C 設 A 為 輸入 - 輸出矩陣, A ; 其中,D 為 (-) 正向量,C 為 D (-) 正向量, 則 (I-A) 具有一維解集合, 且該解集合係由一非負向量所生成 Ay iput-output matri with all positive etries satisfies the hypothesis of this theorem. 任何輸入 - 輸出矩陣滿足 Theorem. 的基本假設條件 例如 :.7 A OPN MODL I the OPN MODL, we assume that there is a outside demad for each of the commodities produced. Returig to our simple society, let,, ad be the moetary values of food, clothig, ad housig produced with respective outside demads d, d, ad d. Let A be the matri such that A ij represets the amout of commodity i required to

39 Liear Algebra- Chapter /9/ produce oe moetary uit of commodity j. The the value of the surplus of food i the society is (A A A ), that is, the value of food produced mius the value of food cosumed while producig the three commodities. The assumptio that everythig produced is cosumed gives us a similar equilibrium coditio for the ope model, amely, that the surplus of each of the three commodities must equal the correspodig outside demads. Hece i A ij j d j i for j,,. 在 開放模式 中, 我們假設每一產品皆有外來的需求, 在前述的單純社會裡, 令 與 分別代表食物 衣物與住屋的貨幣價值,d d 與 d 為食物 衣物與住屋的外來需求價值 令 A 為 矩陣,A ij 表示生產 一個貨幣單位 的產品 j 所需要的產品 i 的價值 於是此社會中食物的盈餘價值為 (A A A ), 即食物的價值減去生產食物 衣物與住屋所需消耗的食物的價值, 意即生產出來的食物價值扣掉用去生產食物 衣物與住屋所消耗掉的價值 ) (A A A 為生產一個貨幣單位的食物 衣物 與住屋 所需消耗的食物 數量 A 表示生產貨幣價值為 的衣物所需要的食物價值 ) 對每一種產品而言, 其盈餘價值等於外來的需求價值, 於是 i A ij j d j i for j,, Suppose that cets worth of food, cets worth of clothig, ad cets worth of housig are required for the productio of $ worth of food. Similar, suppose that cets worth of food, cets worth of clothig, ad cets worth of housig are required for the productio of $ worth of clothig. Fially, suppose that cets worth of food, cets worth of clothig, ad cets worth of housig are required for the productio of $ worth of housig. The the iput-output matri is. A 假設生產價值 元的食物需要價值 分的食物 (A.) 價值 分的衣物 (A.) 及價值 分的住屋 (A.), 生產價值 元的衣物需要價值 分的 食物 (A.) 價值 分的衣物 (A.) 及價值 分的住屋 (A.), 生 9

40 Liear Algebra- Chapter /9/ 產價值 元的住屋需要價值 分的食物 (A.) 價值 分的衣物 (A.) 及價值 分的住屋 (A.), 於是輸入輸出矩陣 A 為. A 若食物的外來需求值為 億元 衣物為 億元 住屋值為 百億元, 則 (I A). d 表示 : 要滿足外來需求, 必須生產的食物價值為 9 億元 衣物價值為 7 億元 住屋價值為 7 億元 Theorem Let AX Y be a system of liear equatios i variables. If A eists, the solutio is uique ad is give by X A Y. Proof Substitute X A Y ito the matri equatio. AX A(A Y) (AA )Y I Y Y. The solutio is uique. Let X be ay solutio, thus AX Y. Multiplyig both sides of this equatio by A gives A AX A Y I X A Y X A Y.

41 Liear Algebra- Chapter /9/ ample / Solve the system of equatios This system ca be writte i the followig matri form: If the matri of coefficiets is ivertible, the uique solutio is The Leotief I/O Model i coomics / The Leotief iput-output model is used to aalyze the iterdepedece of ecoomics. Wassily Leotief received a Nobel Prize i 97 for his work i thie field. The practical applicatios of this model have proliferated util it has ow become a stadard tool for ivestigatig ecoomic structures ragig from cities ad corporatio to states ad coutries. Cosider a ecoomics situatio that ivolves iterdepedet idustries. The output of ay oe idustry is eeded as iput by other idustries, ad eve possibly by the idustry itself. ample / A The uique solutio is,, The Leotief I/O Model i coomics / How a mathematical model ivolvig a system of liear equatios ca be costructed to aalyze such a situatio? Assume that each idustry produces oe commodity. Let a ij deote the amout of iput of a certai commodity i to produce uit output of commodity j. I our model let the amouts of iput ad output be measured i dollars. Thus, for eample, a. meas that cets worth of commodity is required to produce oe dollar s worth of commodity.. The Leotief I/O Model i coomics / a ij amout of commodity i i oe dollar of commodity j. a ij 生產一元價值的 j 產品需要耗用的 i 產品價值 The elemets a ij, called iput coefficiets, defie a matri A, called the iput-output matri, which describes the iterdepedece of the idustries. tedig the model to iclude a ope sector (all oproducig sectors). The product of idustries may go ot oly ito other producig idustries, but also ito other o-producig sectors of the ecoomy such as cosumers ad govermets. The Leotief I/O Model i coomics / Applyig the model to the ecoomy of a coutry, X represets the total output of each of the producig sectors of the ecoomy ad AX describes the cotributios made by the various sectors to fulfillig the itersectioal iput requiremets of the ecoomy. D D is equal to (X-AX), the differece betwee total output X ad idustry trasactio AX. D is thus the gross atioal product of the ecoomy. The Leotief I/O Model i coomics / d i demad of the ope sectors from idustry i. i total output of idustry I ecessary to meet demads of all idustries ad the ope sector. a a a i total output of idustry i i demad of idustry total output Output matri ample / i demad of idustry X AX iteridustry portio of output i demad of idustry D d i demad of ope sector ope sector portio of output Demad matri Cosider a ecoomy cosistig of three idustries havig the followig iput-output matri A.. Determie the output levels required of the idustries to meet the demads of the other idustries ad of the ope sector i each case. 9, 9, ad i tur A D The uit of D are millios of dollars.

42 Liear Algebra- Chapter /9/ ample / We wish to compute the output levels X that correspod to the various ope sector demads D, X is give by the equatio X AX D. Rewritte as follows. X AX D (I A)X D X (I A) D We get I A ample / By usig Gauss-Jorda elimiatio ( I A) of D 9 X ( I A) D ( I A) various values correspod ig output ample / The output levels ecessary to meet the demads 9 9 7, 9, ad are 99,, ad. The uits are milliod of dollars. Computig (I-A) - m (I A)(I A A L A ) m I(I A A L A ) A(I A A m I A ( I A)( I A A L A ) m L A I m ) ( I A) I A A L m A NOT: A m Populatio Movemet / I, millio of people live i cities ad millio of people live i the surroudig suburbs. Represet this iformatio by the t matri X The probability of a perso stayig i the city was.9. Thus the t probability of movig to the suburbs was.. The probability of a perso movig to the city was.; the probability of remaiig i suburbia was.99. (from ) (to) P city suburb city suburb Populatio Movemet / City populatio i people who remaied from people who moved i from the suburbs (.9 ) (. ) 7. millio Suburba populatio i people who moved i from the city people who stayed from (. ) (.99 ).9 millio Ca arrive at these umbers usig matri multiplicatio.9 PX. X Populatio Movemet / Assume that the populatio flow represeted by the matri P is uchaged over the years. The populatio distributio X after years is give by X P X P X. I geeral, X P X i i P is called the -step trasitio matri. The (i,j)th elemet of P gives the probability of goig from state j to state i i steps. For eample: (from) city suburb.. P..9 (to) city suburb The probability of livig i the city i ad beig i the suburbs years later is. Markov Chais The probabilities i the above model deped oly o the curret state of a perso whether the perso is livig i the city or i suburbia. This type of model, i which the probability of goig from oe state to aother depeds oly o the curret state rather tha o a more complete historical descriptio, is called a Markov chai. Markov chais are useful tools for scietists i may fields such as geetics.

43 Liear Algebra- Chapter /9/ Geetics / Geetics is the brach of biology that deals with heredity ( 遺傳 ).). It is the study of uits called gees, which determie the characteristics livig thigs iherit from their parets. The iheritace ( 遺傳 )of) such traits( ( 特徵 )as) se, height, eye color, ad hair color of huma beigs, ad such traits as petal( ( 花瓣 ) color ad leaf shape of plats, are govered by gees. I medicie, agriculture.. Geetics / The traits of guiea pigs( ( 天竺鼠 )are) log hair ad short hair. The legth of hair is govered by a pair of gee which we deote A ad a. A guiea pig may have ay oe of the combiatio of AA, Aa,, or aa. ach of these classes is called a geotype( ( 基因型 ).) The AA type guiea pig is idistiguishable i appearace from the t Aa type both have log hair whereas the aa type has short hair. The A gee is said to domiate the a gee. A aimal is called domiat ( 顯性 )if) it has AA gees, hybrid ( 混種 ) with Aa gees, ad recessive ( 隱性 )with) aa gees. Geetics / Whe two guiea pigs are crossed, the offsprig iherits oe gee from each paret i radom maer. Give the geotype of the parets, we ca determie the probabilities of the geotype of the offsprig: AAAA probabilities of AA, Aa,, ad aa are,,ad. AaAA probabilities of AA, Aa,, ad aa are ½, ½,, ad. aaaa probabilities of AA, Aa,, ad aa are,, ad. This series of eperimets is a Markov chai havig trasitio matri AA Aa aa / AA P / Aa aa Geetics / Assume a iitial populatio of guiea pigs made up of a equal umber of each geotype. X / / / The fractios of followig geeratios are / / 7 / / /,X /,X /,X / X AA Aa aa - Systems of Liear quatios Computatioal Aspects DFINITION. quivalet Two systems of liear equatios are called equivalet if they have the same solutio set. 兩個線性方程組稱為等價, 意指兩者具有相同的解集合 lemetary Trasformatios Trasformatio called elemetary trasformatios ca be used to chage a system of liear equatios ito aother system of liear equatios that have the same solutio. These trasformatios are used to solve system of liear equatios by elimiatig variables. The equivalet trasformatios used i terms of matri are called LMNTARY ROW OPRATION.

44 Liear Algebra- Chapter /9/ quivalet System Systems of equatios that are related through elemetary trasformatios are called equivalet systems. Matrices that are related through elemetary row operatios are called row equivalet matrices. The symbol is used to idicate equivalece i both cases. Theorem. Let A b be a system of m liear equatios i ukows, ad let C be a ivertible m m matri. The the system (CA) Cb is equivalet to A b. 設 A b 為含 個未知數 m 個線性方程式的方程組, 若 C 為可逆的 m m 矩陣, 則 (CA) Cb 等價於 A b Proof Let K be the solutio set for A b ad K the solutio set for (CA) Cb. If w K, the Aw b. So (CA)w Cb, ad hece w K. Thus K K. Coversely, if w K, the (CA)w Cb. Hece Aw C - (CA)w C - (Cb) b; so w K. Thus K K, ad therefore, KK. 設 K 為 A b 的解集合且 K 為 (CA) Cb 的解集合 若 w K, 則 Aw b (CA)w Cb, 故 w K, 於是 K K 反之, 若 w K, 則 (CA)w Cb Aw C - (CA)w C - (Cb) b, 故 w K, 於是 K K 因此,KK Corollary Let A b be a system of m liear equatios i ukows. If (A b ) is obtaied from from (A b) by a fiite umber of elemetary row operatios, the the system A b is equivalet to the origial system. 設 A b 為含 個未知數 m 個線性方程式的方程組 若 (A b ) 是由 (A b) 經過有限次數的基本列運算而得, 則 A b 等價於 A b, 即兩者具有相同的解 集合 Proof Suppose that (A b ) is obtaied from (A b) by elemetary row operatios. These