筆記

Def：Graph 一個 Graph G = (V, E) 由 V 與 E 兩個集合所組成，其中 V 為有限集合，其元素稱為頂點 ( vertices )；而 E 之元素稱為連線 ( edges )，為相異的頂點所成之配對。 雖然我們稱 V 中元素為頂點，然而事實上 V 可為任意集合，不過是名字的差異。 我們稱 E 中元素為連線，然而事實上我們只定義了其元素為兩個相異頂點的 配對 ，通常我們使用數對來表示， 而既然表示的是配對，順序便不構成差別：(a, b) = (b, a)。 我們並未規定 E 包含了多少相異頂點之配對。 我們可使用圖形來表示一個 Graph ，使用點代表每一個頂點，使用兩點間之連線代表兩頂點之配對。 Graph 的圖形不會出現連回到同一點的線(loops)，那不是一個配對。 #### Def：adjacent、path、circuit、 connected  1. 在一個 Graph 中，若 E 中存在某兩頂點之配對，則我們說該兩頂點相鄰 ( adjacent )。 2. 一個 path 是一個由相異的  vertices  組成之數列，記為 P = x 1 -x 2 - ... -x n ，而其中任意 x i   與 x i+1  及 x i-1 必須相鄰。 3. 若是  x 1 -x 2 - ... -x n  中， x 1  與  x n  相鄰，則我們稱之為  circuit ，記做   x 1 -x 2 - ... -x 1   。 4. 若一個 Graph 中，任意兩頂點間，皆可找到一個 path 相連，我們稱這樣的 Graph connected。 Def：disconnect disconnect 一個 connected  Graph 所指的是，透過自 V 中 移除某些頂點 ，或自 E 中 移除某些配對 ，使得剩下的 Graph 不再是一個  connected Graph。 因為我們考慮 的是剩下的 "Graph" ，因此若有一個頂點被移除掉，則與之相關的配對也要跟著移除，否則無法構成一個 Graph。 而此剩餘的 Graph 被分解成數個互相不相連之區塊，而這些區塊有可能是一個 vertex，或是數個相連的 vertices。 值得注意的是：若一個 Gra

對角化問題 對於作用於有限維向量空間 V 上的線性變換 T ，我們想問： 既然我們可以透過改變基底，來改變線性變換矩陣，那麼，有沒有辦法為找到一組基底 b ，使得 [T] b  成為一個對角線矩陣呢？若是可以，又要如何找到 b 呢？ #### Def：可對角化(diagonalizable) 若一個作用於有限維向量空間 V 的線性變換 T ，可以找到一組 V 的  ordered basis b，使得  [T] b  為一個對角線矩陣，則說 T 為可對角化。若是一個方陣 A 所對應的線性變換 L A  可對角化，則說 A 為可對角化。 我們可以發現，若將向量對基底 b 分解，再經過 [T] b  這個線性變換，得到的結果仍然是一個由 b 所表達的向量，但是 [T] b  現在是一個對角線矩陣！也就是說，若該向量為該基底中的向量 vi，其線性變換時，只會乘上 [T] b   中的第 i 行第 i 列的項 ki，結果是自己的倍數。 即使我們以別組基底表示這個線性變換與向量，b 中的向量仍然具有線性變換後為自己倍數的性質，這是與 T 的表示法無關的，總而言之 ，b 是一組線性變換後，方向不會改變的向量！ 換句話說，若 T 可藉由 b 對角化，且b = {v1, v2, ... ,vn}，則： [T ] b  vi   =   kivi T(vi)   =   kivi 反過來看，若上述兩式子成立，找得到這麼一組向量當基底，T也理所當然可對角化。 總結來說，若找得到這樣的一組向量作為基底，就是一個可對角化的線性變換；而可對角化的線性變換也必定具有這樣一組基底。 Def：特徵值與特徵向量 對於線性變換 T ，向量空間 V ，若 v 屬於 V ，且 T(v) = kv ( k 為一常數) 則稱 v 為 eigenvector (特徵向量)、k 為 v 的 eigenvalue (特徵值)。 對應於對角化的討論，我們發現，特徵向量便是那些不被線性變換改變方向的向量，而特徵值則是該向量伸縮的倍數，同時也是對角線矩陣上的數，因此我們可以發現，每一個特徵向量都將會對應到一個特徵值，然而一個特徵值可能對應到一組或數組互為倍數關係的向量。 舉例： 若 C(R) 是由 R 到 R 的可無限次微分的函數所成之集合 (例如：多項式、三

前言： 若 V 是一個 n 維的向量空間，W 是一個 m 維的向量空間，則我們可以在這兩個空間中建立一個由 V 至 W 的線性變換 T ，而我們又可以使用矩陣來表示線性變換，而線性代數研究的便是如何處理這些矩陣，然而矩陣的乘法頗為複雜，因此我們的目標是： 將矩陣簡化為對角線矩陣。 以基底的線性組合來表示向量 我們可以為 V 與 W 找一份基底，分別為 a = { v1, v2, ... ,vn } ，及 b = {w1, w2, ... ,wm} ，則 V 中的任意向量便可以表示為 a 的線性組合，例如 v = c1v1 + c2v2 + ... + cnvn ，我們又可以將係數抽離出來，成為一個向量， c = (c1, c2, ... ,cn) ，如此一來，我們再將 c 立起來，變成一個 column vector ，記為 [ v ] a = [ c ] ，此即 v 對應於基底 a 的 column vector 。 #### 線性變換矩陣 基底是一個向量空間的基礎，因此我們將基底 a 中的元素 vj 經過線性變換，變成了 T(vj) ，為 W 中的元素，既然是 W 中的向量，那就可以用 W 的基底 b 來表示，我們將每一個 T(vj) 對於 b 的 column vector 排排站好，變成一個 m x n 的矩陣，也就是 ( [T(v1)]  b  ,   [T(v2)]  b  , ... ,  [T(vn)]  b   )  ，我們稱這個矩陣為 A 。 這樣一來， A 這個矩陣，就是 a 這組基底裡每一個向量經過線性變換後，再由基底 b 將每一個 T(vj) 表示為 column vector 的結果。 如此一來，若是將 A 乘上  v  對應於基底 a 的 column vector ，即  A[ v ] a ，則剛好每一個係數 ci  都會剛好乘上其對應向量 vi 的線性變換 T(vi)，而其結果會是由 b 所表達的 T( v )，即：   A[  v  ] a   =    [ T( v)  ] b 這顯然是個非常好用的矩陣，如此一來，我們只要知道一個向量對 a 的分解，則透過這個矩陣，我們就可以知道他經過線性變換後對 b 的分解。  A = [T] a b 。

Matrix：   ( a11, a12, ...  , a1n  )                     ( a21, a22, ...  , a2n  )                     ( a31, a32, ...  , a3n  )                     (  ...  ,  ...  , ...   ,    ...  )                     ( am1, am2, ...  , amn  )                以上是一個 mxn 的矩陣向量空間，記做 M mxn (F) ，矩陣中的 a ij 稱為矩陣的【項】，為 F 中的元素。以下為一些矩陣的性質與專有名詞： #### 向量加法： 將對應位置的項相加 係數積： 將係數乘入矩陣中各個項 表示一個矩陣： 使用大寫英文字母，如：A、B 表示矩陣中一個項： 使用該矩陣的符號加下標，如：A ij row： 第一個下標相同的項，即同一橫條的項，組成一個 row column： 第二個下標相同的項，即同一直條的項，組成一個 column diagonal entries： 對角線項，兩個下標皆相同的項 trace： 矩陣對角線項的和，記為tr(M) 零矩陣： 矩陣中所有的項皆為零 方陣： 長度寬度一樣的矩陣， m = n 對角線矩陣： 對角線項以外的項皆為零的方陣 關於下標： 可以想像矩陣是一棟地底大樓，第一個編號是樓層的深度，第二個編號則是房間號碼，我們得先搭電梯到對的樓層，才能找到對的房間。  Transpose：轉置矩陣 轉置矩陣即將原本矩陣的 row 與 column 互換，因此若原本是 mxn 矩陣，轉置後會變成 nxm 矩陣，我們將 A 的轉置矩陣記為 A t  ，轉置矩陣的數學式表示如下 (A t ) ij = A ji Symmetric matrix：對稱矩陣 若一個矩陣與他的轉置矩陣相等 ，即  A =    A t ， 也就是說   A ij  = A ji， 我們就稱他為對稱矩陣 ，對稱矩陣必定是 方陣 ，且對稱與否與對角線項無關，因此 對角線矩陣 必定為對稱矩陣。 所有 nxn 的對稱矩陣，包含於所有 mxn 方陣這個向量空間之中，又因為零矩陣為對稱矩陣，且對稱矩

Def： subspaces 子向量空間 若 W 為向量空間 V(F) 的子集合，且其運算方式與 V 相同，若 W 也是一個向量空間，則我們稱 W 為 V 的子空間。 (ps. V(F) 表示V定義在 Field F上。) 因此要證明 W 是一個子空間，就必須證明他是一個向量空間，但因為 W 已經是 V 的子集合，因此顯然有許多性質不需再被檢驗，例如交換律、結合律等對 V 中所有向量皆適用的性質。 因此若已知【 W 為 V 的子集合】，且【運算的定義相同】，要證明 W 為 V 的子空間，只需檢驗以下性質即可： (a) 向量加法封閉性 (b) 係數積封閉性 (c) 加法單位元素：零向量 存在 (d) 每一個向量的加法反元素存在 #### 其中 (c) 可以利用消去律證明該零向量與 V 中的零向量是同一個。 且其中 (d) 其實是可以省略的，這是因為係數積封閉性的緣故。因為係數來自一個 Field ，而 Field 必定包含 1 這個係數 (乘法單位元素)，且同時包含 1 的反元素 -1，這麼一來，根據係數積封閉性，若 x 為 W 中的一個向量，則 -x 也必定會存在於 W 之中。 問：既然如此，為什麼在向量空間的定義中不也省略反元素這一項？ 若是不在向量空間的定義中定義反元素，將會造成許多問題。雖然每個 x 可以經由係數積的封閉性造出 -x ，然而 x + (-x) = 0x 卻是未被定義的！回頭看看 向量空間 的定理， 0x = 0 是由消去律所證出來的，然而消去律卻是由反元素性質所證明！ 也就是說，若是不去定義反元素，我們可能無法僅僅由其他定義證出消去律，而隨著消去律而來的許多有用性質也會跟著付之一炬。 其實在向量空間的條件中定義反元素時，不僅是讓每一個向量都對應到一個反元素，也同時在每一個向量與零向量之間形成連結，在定義了反元素之後，零向量才有其用武之處，零向量與反元素其實是一體兩面啊！ 回過頭來看子空間的情形，可以發現上述的問題不會發生，因為子空間包含於向量空間之內，而在向量空間之中是可以使用消去律及其他定理的，因此 x + (-x) = 0x 不會陷入未定義的窘境。 Thm： 在同一個向量空間中，任意子空間的交集都會是一個子空間。 這個定理可以輕易獲得證明，若現在有兩個子空間 V 、W，兩子空間皆包含零向量，因此其交集也必包含零向量

向量空間： 向量空間由 兩個集合：V、F ， 兩種運算方式：【向量加法】、【係數積】 構成。   V ：該空間中所有向量的集合  F ：可作用於向量上之係數所形成之 Field   向量加法 ：由 V 中兩個元素對應至 V 中另一元素的運算   係數積 ：由 F 中一元素與 V 中一元素對應至 V 中一元素之運算 向量空間中的向量加法與係數積，與一般算術之加法與乘法不一樣， 向量加法牽涉到方向的相加 ( 牽涉到順序 )，而係數積則是一個外在的係數乘以向量，並非兩個向量相乘，因此在向量空間中需要另外一個由係數構成的集合 F。 #### Def： vector space (  向量空間 ) 一個定義在Field  F 、向量加法及係數積之上的向量空間 V 具有以下性質： ( 其中 a, b, c 屬於 F ， x, y, z 屬於 V ) 1. 加法封閉性：向量 x + y 屬於V 2. 加法單位元素：V 裡頭存在 0 向量，使得 x + 0 = x 3. 加法反元素：對任意向量 x 都可以找到一個 y ，使得 x + y = 0 4. 加法交換律：x + y = x + y 5. 加法結合律：x + (y + z) = (x + y) + z 6. 係數積封閉性：向量 ax 屬於V 7. 係數積單位元素：對於任意 x， 1x = x 8. 係數積結合律：(ab)x = a(bx) 9. 係數積分配律：a(x + y) = ax + ay 10.係數運算的分配律：(a + b) x = ax +bx 為什麼沒有係數積反元素？ 加法反元素之結構為，一個向量，加上反元素(向量)之後，變成加法單位元素 0 向量。對應至係數積，我們期待係數積反元素之結構為：一個係數，與係數積反元素做運算後，變成係數積單位元素 1。 然而這並沒有意義，因為這樣的結構已經包含在 F 這個 Field 之中了，也就是說， 定義向量空間時，其實已同時為係數的集合內定了一個結構，因此係數本身即具有加法與乘法，及其他 Field 之性質 ，然而這與整個向量空間的關係不大，我們只需要保證這些係數在與向量們作用時不會出問題就好，因此我們有 8. 10. 項，確保係數間的運算，在係數積的運算中能保持一致。 n-tuple： (a1, a2, ... ,an)

Def：Field 一個 Field  F 定義在一個集合與兩種運算方式之下，兩種運算分別為加法 ( + ) 與乘法( * )。若 a, b, c 為 F 中的元素，則具有以下性質： 1. 乘法與加法封閉性與唯一性：a + b 與 a * b 唯一且皆屬於 F 2. 乘法與加法單位元素：0、1 屬於 F ，使得 a + 0 = a 且 a * 1 = a 3. 乘法與加法反元素：任意 a 皆存在 b、c ，使得 a + b = 0 、 a * c = 1，(只有 0 沒有乘法反元素) 4. 乘法與加法交換律：a + b = b + a  、  a * b = b * a 5. 乘法與加法結合律：(a + b) + c = a + (b + c) 、 (a * b) * c = a * (b * c) 6. 乘法對加法的分配律：a * (b + c) = ab + ac R 是一個 Field 、有理數也是一個 Field、Z2：{0, 1}，其中1 + 1 = 0，其餘運算與與正常運算相同，這也是一個 Field 。 經由加法與乘法反元素，可以定義減法與除法為與反元素相加或相乘。 #### Thm：消去律 對任意 a, b, c 屬於 F (1) 若 a + b = c + b ，則 a = c (2) 若 a * b = c * b，且 b 不等於 0，則 a = c 由反元素、結合律即可證出 corollary：由此定理可證出加法及乘法單位元素唯一。 Thm  若 a, b 為 Field F 中的元素，則具有以下性質： (1) a * 0 = 0 (2) (-a) * b = a * (-b) = -(a * b) (3) (-a) * (-b) = a * b 其中(1)可利用 0 + 0 = 0 與消去律證得，(2)則是各自檢驗前兩項符合 a * b的反元素，(3)可由(2)證得。 Characteristic 在上方 Z2 的例子中，可以發現有一些 Field 具有循環的特質。即其乘法單位元素 1 ，在連加 p 次之後，其總和會是 0 ，對於一個 Field ，我們把最小的 p 稱為這個 Field 的 Characteristic ，而若是沒有任何正整數 p 可以符合，則稱這個 Field 的