108 年 國立中山大學通訊工程研究所甲組《線性代數》
第 1 題8 分
Let matrix and . Please calculate , where is the identity matrix.
登入後即可作答並保存紀錄。
本題主要考驗矩陣的求逆、矩陣運算以及代數化簡的能力。
首先,我們需要計算矩陣 。
給定 ,
是 的單位矩陣 。
計算 :
計算 :
接下來,我們需要計算 。由於 是一個下三角矩陣,其逆矩陣也是下三角矩陣。
令 。
我們要求 。
(可以透過高斯消去法或觀察對角線元素的倒數得到)
現在計算 :
第 2 題8 分
Find the factorization for .
登入後即可作答並保存紀錄。
核心觀念
本題考查矩陣的 分解,其中:
- 為置換矩陣,負責交換列以取得非零主元。
- 為下三角矩陣,記錄消去過程中的乘數。
- 為對角矩陣,通常放置消去後的主元。
- 為對角線元素皆為 的上三角矩陣。
當消去過程中出現零主元時,必須先進行列交換,因此本題需要使用 。
解題方法
原矩陣為
第一個主元為 。為了處理第二欄的主元,先將第 、第 列交換:
因此
第一步消去第一欄
以第一列為主列:
得到
第二欄主元為 ,且第三列第二欄已經是 ,因此不需要再進行消去。
故可先寫成
其中下三角矩陣中的 ,分別來自消去時的乘數。
拆出對角矩陣
將上三角矩陣的主對角元素提出:
因此
且
第 3 題8 分
Let . Find a matrix such that .
登入後即可作答並保存紀錄。
本題主要考驗求解矩陣平方根的問題。
矩陣 是一個上三角矩陣,其特徵值是其對角線上的元素:, , 。
由於矩陣 的特徵值均為正且不重複,因此存在唯一的矩陣平方根 使得 。
如果 也是一個上三角矩陣,則 的特徵值必須是 的特徵值的平方根。
設 。
則 。
我們要求 。
比較對角線元素:
我們通常尋找主平方根,也就是特徵值取正的平方根。
令 , , 。
現在比較非對角線元素:
所以,一個可能的矩陣 是:
。
第 4 題8 分
Let . Please compute .
登入後即可作答並保存紀錄。
核心觀念
本題考查矩陣乘冪與最小多項式。若矩陣 滿足某個多項式關係,例如
即可將高次方 化為 與單位矩陣 的線性組合,大幅降低計算量。
解題方法
先直接計算 :
注意到
因此
也就是
因為
所以 的高次方皆可化為 與 的線性組合。設
由特徵值 與 代入相同的多項式關係:
當 時,
當 時,
第 5 題8 分
Find the best least square (error) sense by linear function to the model:
登入後即可作答並保存紀錄。
本題主要考驗最小平方法 (Least Squares Method) 的應用,目的是找到一條直線 最能擬合給定的數據點。
給定的數據點為 。
我們希望找到參數 和 ,使得誤差平方和 最小。
誤差平方和為:
為了使 最小,我們對 和 分別求偏導數,並令其為零:
計算 :
令上式為零,除以 :
(方程 1)
計算 :
令上式為零,除以 :
(方程 2)
現在我們需要解這個方程組:
從方程 1) 得到 , 所以 。
將 代入方程 2):
第 6 題8 分
Let . Find the QR-factorization of matrix A.
登入後即可作答並保存紀錄。
核心觀念
QR 分解是將矩陣 寫成
其中:
- 的欄向量為標準正交向量,滿足 ;
- 為上三角矩陣;
- 使用 Gram–Schmidt 正交化法,可由 的欄向量逐一建立 與 。
令
則
採用對角線元素皆為正的 QR 分解慣例。
解題方法:Gram–Schmidt 正交化
第一步:求
先將 單位化:
因此
同時,
第二步:求
先計算 在 方向上的投影係數:
將投影部分扣除,得到與 正交的向量:
由於
所以
其長度為
因此
且
第三步:求
先求 在 與 方向上的投影係數:
第 7 題8 分
Consider the set with the operations:
Is this a field? Why?
登入後即可作答並保存紀錄。
本題主要考驗對「體 (Field)」的定義的理解與判斷。一個體是一個集合,上面定義了兩種二元運算(通常稱為加法和乘法),這些運算必須滿足一系列公理。
我們需要檢查集合 和給定的運算 和 是否滿足體公理。
體公理如下:
-
是一個交換群 (Abelian group)。
a. 封閉性 (Closure):對於任意 , 。 (由加法表可見,所有結果都在 中)
b. 結合律 (Associativity):對於任意 , 。 (此處的加法是模 4 加法,滿足結合律)
c. 單位元 (Identity element):存在一個元素 使得對於任意 , 。 (由加法表知,0 是加法單位元)
d. 反元素 (Inverse element):對於任意 , 存在一個元素 使得 。
(所有元素都有加法反元素)
e. 交換律 (Commutativity):對於任意 , 。 (加法表是對稱的,滿足交換律) -
是一個交換群。
a. 封閉性 (Closure):對於任意 , 。 (這裡 )
檢查乘法表:
。
由於 ,乘法運算在 這個集合上不滿足封閉性。b. 結合律 (Associativity):對於任意 , 。 (此處的乘法是模 4 乘法,滿足結合律,但我們已經發現了問題)
c. 單位元 (Identity element):存在一個元素 使得對於任意 , 。 (由乘法表知,1 是乘法單位元)
d. 反元素 (Inverse element):對於任意 , 存在一個元素
第 8 題8 分
Let and be matrices with and . Please find
(a) (2%)
(b) (2%)
(c) (2%)
(d) (2%)
登入後即可作答並保存紀錄。
本題主要考驗矩陣行列式的基本性質。
給定 和 是 矩陣,且 , 。
(a)
行列式的性質之一是:兩個矩陣乘積的行列式等於它們各自行列式的乘積。
(b)
對於一個 矩陣 和一個純量 ,行列式的性質是:
在這裡, (因為 是 矩陣),。
(c)
這可以看作是 。
令 。則 也是一個 矩陣。
第 9 題8 分
Let , , be matrices with entries from the binary field with addition and multiplication defined in the following:
(a) (3%) Find the inverse matrix of in the binary field.
(b) (5%) Prove that the rows of span the null space of in the binary field.
登入後即可作答並保存紀錄。
核心觀念
本題在考兩個重點:
- 在二元體 中進行矩陣運算,其中
因此減法與加法相同。 - 利用秩—零度定理判斷矩陣的零空間:
若要證明若干向量張成 ,必須確認:
- 每個向量都屬於 ;
- 這些向量的線性獨立數量等於 。
(a)求
令
由矩陣乘法,在 中得到
由第四式,
第二式給出
第一式因此化為
第三式給出
再由 ,
所以
因此
在 中直接計算可得
(b)零空間張成關係的檢查
題目列出的矩陣為
因此
但 的每一個列向量屬於 。兩者所在的向量空間不同,所以依照題目目前的矩陣尺寸,無法成立「 的列向量張成 的零空間」。
而且, 的三列線性獨立。例如
其餘兩列無法由 互相倍乘得到,因此
由秩—零度定理,
第 10 題8 分
Assume that is a linear transmission system from to , where
Please find:
(a) (2%) the range of .
(b) (2%) the null space of .
(c) (2%) Is one-to-one? Explain why.
(d) (2%) Is onto? Explain why.
登入後即可作答並保存紀錄。
核心觀念
將線性映射寫成矩陣形式:
本題主要考查:
- 值域(range):所有可能輸出向量的集合。
- 零空間(null space):被映射至零向量的所有輸入向量。
- 一對一(one-to-one):不同輸入不會得到相同輸出;等價於零空間只有零向量。
- 映成(onto):值域等於整個陪域 。
- 秩-零化度定理:
解題方法
由題目中的第三個分量可得:
因此對任意輸入向量,輸出必定具有形式
其中
接著分別求值域與零空間。
(a)求 的值域
由上述關係,所有輸出向量均屬於集合
還需確認任意 都能產生。取
則
因此所有此形式的向量皆可由 產生,故
也可寫成張成空間:
所以
(b)求 的零空間
令輸出為零向量:
得到方程組:
第三式是第二式的負值,因此沒有提供新的限制。只需考慮:
令
則
所以任意零空間中的向量可表示為:
因此
第 11 題10 分
Let and denote two non-singular square matrices. Please prove that matrix has the same eigenvalues as matrix .
登入後即可作答並保存紀錄。
核心觀念
本題考查矩陣相似與特徵值的關係。
若存在可逆矩陣 ,使得
則稱 與 相似。相似矩陣具有相同的特徵多項式,因此必有相同的特徵值。
題目給定 、 為非奇異方陣,因此 可逆。
解題方法
觀察 與 的乘積順序,利用 的可逆性建立相似關係:
因此
這正符合相似矩陣的形式,表示 與 相似。
也可以直接比較特徵多項式:
\begin{align*}
\det(\lambda I-BA)
&=\det\left(A^{-1}(\lambda I-AB)A\right)\
第 12 題10 分
Let and , where are constants. Define as the matrix multiplication using 8 multiplication operators. Is it possible to reduce the number of multiplication operators to 7? Explain why.
登入後即可作答並保存紀錄。
本題主要考驗對矩陣乘法的理解,以及是否能找到更有效率的矩陣乘法演算法(例如 Strassen 演算法)。
題目中定義了一種特殊的「矩陣乘法」運算 ,其中 和 是 塊矩陣。
,
這個定義實際上就是標準的 塊矩陣乘法。
讓我們計算 (標準矩陣乘法):
。
這與題目中定義的 完全相同。
標準的 矩陣乘法,對於兩個 的矩陣,需要 次純量乘法。
例如,計算 。
需要 共 8 次純量乘法。
題目中的 和 是 塊矩陣。
塊矩陣 的元素是 。塊矩陣 的元素是 。
我們假設 是純量 (constants)。
那麼,計算 的結果矩陣的四個元素:
- : 需要 2 次純量乘法 () 和 1 次純量加法。
- : 需要 2 次純量乘法 () 和 1 次純量加法。
- : 需要 2 次純量乘法 () 和 1 次純量加法。
- : 需要 2 次純量乘法 () 和 1 次純量加法。
總共需要 次純量乘法。
總共需要 次純量加法。
問題問是否可以將純量乘法的數量減少到 7 次。
這涉及到 Strassen 演算法。Strassen 演算法是一種用於兩個 矩陣乘法(其中 是 2 的冪)的演算法,它比標準的 演算法更有效率。
對於 矩陣乘法,Strassen 演算法將乘法次數從 8 次減少到 7 次。
Strassen 演算法對於兩個 矩陣 和 的計算步驟如下:
計算 7 個中間值 :