106 交大資工所數學考點分析

題型與配分

科目「線性代數與離散數學（1102）」，系所班別資訊聯招，考試日期 106 年 2 月 10 日第 2 節，全卷 3 頁、13 題、100 分，不可使用計算機。

作答規定（106–107 年皆有）：「First you need to write down your answers clearly and then explain how to compute the answers. You also need to answer the questions in order. Do not jump around.」

離散數學考點（1–6）

• 第 1 題（15%）｜(a) 10% 把兩個關於質數的敘述翻譯成邏輯式（可用 IsPrime(x) 述詞）：「每個大小為 10⁸ 的區間都有質數」與「有無限多對相差不超過 10⁸ 的相鄰質數」 (b) 5% 這兩個敘述邏輯上等價嗎？哪一個必定為假？為什麼
• 第 2 題（10%）｜n = 2^k 時兩個 n×n 矩陣相乘：(a) 5% 描述一個漸進更快的乘法方法（Strassen） (b) 5% 用遞迴關係式分析複雜度
• 第 3 題（10%）｜每個人從 {1,…,n} 中任選 n_i 個相異整數：(a) 5% 兩人各選 k 個時，保證至少有一個共同整數的最大 k（鴿籠原理） (b) 5% 給定具體人數與選數，求「恰好共有一個共同整數」的組合數
• 第 4 題（5%）｜給一個有向圖表示的關係 L，定義 i ~ j 若且唯若 i 與 j 之間沒有任何 L 關係，問 ~ 的 0-1 矩陣中有幾個 1
• 第 5 題（5%）｜判斷兩個圖是否同構，要給出同構映射或嚴謹論證不存在
• 第 6 題（5%）｜解遞迴式 a_n = 4a_n−1 − 4a_n−2（a₀ = 4、a₁ = 4）。重根 λ = 2，解含 n·2ⁿ 項

線性代數考點（7–13）

• 第 7 題（4%）｜A 為非對稱方陣時，判斷 B = A − A^T（必為 skew-symmetric）與 C = (I+A)(I−A^T) 各屬於對稱／反對稱／皆非
• 第 8 題（10%）｜(a) 5% A 為 4×5、B 為 5×7 且 AB = 0，若 rank(B) = 2，求 rank(A) 的最大可能值（3，因為 C(B) ⊆ N(A)） (b) 5% A = uv^T + vw^T + wu^T，若 x₁u + x₂v + x₃w = 0 有非零解，求 rank(A) 的最大值
• 第 9 題（6%）｜把向量 x 分解成 x_r ∈ C(A^T)（列空間） 與 x_n ∈ N(A)（零空間） 兩部分
• 第 10 題（5%）｜給三個點，用最小平方法配一條直線 b = C + Dt，求誤差平方和 ‖e‖²
• 第 11 題（10%，10 個是非題）｜線代判斷：線性算子是否必為單射、正交矩陣是否必有特徵值 1（假）、馬可夫矩陣是否必有特徵值 1（真）、投影矩陣的特徵空間、奇異矩陣是否永不可對角化（假）、實對稱矩陣的特徵值與特徵向量、主元乘積是否等於特徵值乘積（假，只有行列式相等）、對稱矩陣能否與非對稱矩陣相似、AA^T = A^TA 時 A 與 A^T 是否有相同特徵值、奇異值是否皆為非負實數
• 第 12 題（5%）｜證明 det([[A,B],[C,D]]) = det(A)·det(D − CA⁻¹B)（Schur complement）
• 第 13 題（10%）｜三個政黨的世代轉移機率，求長期穩定狀態（steady state）。這是馬可夫鏈求主特徵向量

這份考卷的難點

1. 第 1(b) 題要判斷「哪一個必定為假」：第一個敘述（每個大小 10⁸ 的區間都有質數）是假的（質數間隙可以任意大），第二個（有無限多對間距 ≤ 10⁸ 的質數）已被張益唐等人證明為真。這需要數論常識。
2. 第 12 題的 Schur complement 證明要用分塊矩陣的 LU 分解，是線代的進階技巧。
3. 第 11 題的 10 個是非題涵蓋線代幾乎所有迷思，其中「主元乘積 = 特徵值乘積」是常見錯誤（兩者都等於行列式，但主元乘積 ≠ 特徵值，除非 A 對稱正定）。
4. 必須依序作答且先寫答案再解釋，跳題作答可能影響閱卷。

準備建議

• 交大的數學科目全名是「線性代數與離散數學」，兩科各半，且第 2 節考（軟體在第 1 節）
• 馬可夫鏈的穩定狀態（106 第 13 題）是交大偏好的應用題，要會求轉移矩陣的主特徵向量
• Strassen 演算法與遞迴式分析（106 第 2 題）橫跨數學與演算法兩科，是交大的特色
• 線代的是非判斷題（106 第 11 題 10 分）在交大 106、107 都出現，建議整理成「命題＋反例」的對照表