附录 D 矩阵 (Matrices)
核心结论
-
矩阵与向量基础：矩阵 \(A = (a_{ij})\) 是 \(m \times n\) 实数阵列；向量是 \(n \times 1\) 列阵；转置 \(A^T\) 交换行列；零矩阵、单位矩阵、单位向量。
-
特殊矩阵：对角、三对角、上/下三角、单位三角、置换矩阵（行/列置换）、对称矩阵 (\(A = A^T\))——各自有特殊运算性质。
-
基本运算：加法（逐元素）、标量乘法、矩阵乘法（式 D.2，\(n \times n\) 时 \(\Theta(n^3)\))；分配律、结合律；矩阵乘法 不交换；内积、outer product、范数（式 D.2）。
-
逆、秩、行列式：逆矩阵唯一（存在时）、秩 = 最大线性无关列数 = 最大线性无关行数、行列式（递推定义，式 D.1）；非奇异 \(\Leftrightarrow\) 满秩 \(\Leftrightarrow\) det ≠ 0。
-
正定矩阵：\(A\) 正定若 \(x^T A x > 0\) for all non-zero \(x\)；满列秩矩阵的 \(A^T A\) 必正定（Theorem D.6）——广泛用于优化、统计。
-
常用性质：\((AB)^T = B^T A^T\)；可逆 ⟺ 满秩；对称矩阵的逆仍对称；置换矩阵的逆 = 转置。
|
附录主旨
本附录是第 4 章 Strassen 矩阵乘法、第 28 章矩阵运算与线性规划、第 28.3 节最小二乘逼近等内容的数学基础。矩阵是线性代数的核心对象；算法分析中常用到「矩阵乘法的代价」「矩阵求逆」「正定性」等性质。理解这些概念后，第 28 章线性规划单纯形法、内点法的分析才会自然。 |
一、核心概念
本附录围绕 5 个核心概念展开：基本定义、特殊矩阵、矩阵运算、逆与秩、行列式、正定性。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
矩阵与向量基础 |
矩阵 \(A \in \mathbb{R}^{m \times n}\)；向量 \(x \in \mathbb{R}^n\)；转置 \(A^T\)；零矩阵、单位矩阵。 |
§D.1；列向量是标准形式，行向量 = 转置。 |
特殊矩阵 |
对角、三对角、上/下三角、单位三角、置换矩阵、对称。 |
§D.1；各自运算特性不同（如三角矩阵的逆仍三角）。 |
矩阵运算 |
加法（逐元素）、标量乘法、矩阵乘法（式 D.2）；分配律、结合律；不交换。 |
§D.1；内积 = 行向量 × 列向量；外积 = 列 × 行；范数。 |
逆、秩、行列式 |
逆：\(AA^{-1} = I\)；秩 = 行列线性无关数；行列式（递推）；非奇异 ⟺ 满秩 ⟺ det ≠ 0。 |
§D.2；Theorem D.1, D.5。 |
正定矩阵 |
\(x^T A x > 0\) for all non-zero \(x\)；满列秩 \(A\) 的 \(A^T A\) 正定。 |
§D.2；Theorem D.6；最小二乘、Newton 法、二次规划中广泛出现。 |
二、详细笔记
2.1 矩阵与向量
What：矩阵是二维数表；向量是一维数表；两者都是线性代数的核心对象。
Why：很多算法问题（线性方程组、最小二乘、图邻接矩阵）都自然表示为矩阵；矩阵运算的代价决定了算法的效率。
How：
| 概念 | 记号 |
|---|---|
矩阵 |
\(A \in \mathbb{R}^{m \times n}\)，元素 \(a_{ij}\) |
向量 |
\(x \in \mathbb{R}^n\)（列向量）；行向量 = \(x^T\) |
转置 |
\((A^T)_{ij} = A_{ji}\) |
零矩阵 |
所有元素 = 0；记为 0 |
单位矩阵 |
\(I_n = \text{diag}(1, \ldots, 1)\)；第 i 列为单位向量 \(e_i\) |
范数 |
\(|x| = (x_1^2 + \cdots + x_n^2)^{1/2} = (x^T x)^{1/2}\) |
When：所有矩阵运算的预备知识。
Example：\(A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}\) 是 2×3 矩阵；\(A^T = \begin{pmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{pmatrix}\) 是 3×2 矩阵。
2.2 特殊矩阵
What：六类常用特殊矩阵，各自有独特的结构和运算性质。
Why：特殊矩阵（三角、对角、对称等）的运算效率高；算法设计中识别矩阵的特殊结构可大幅加速。
How：
| 类型 | 结构 |
|---|---|
性质 |
对角 |
\(a_{ij} = 0\) if \(i \neq j\) |
乘法逐元素，可逆 ⟺ 所有对角元非零 |
三对角 |
仅主对角 + 上下次对角非零 |
线性方程组高效解法（追赶法） |
上三角 |
\(u_{ij} = 0\) if \(i > j\) |
与下三角乘积保持三角性 |
下三角 |
\(l_{ij} = 0\) if \(i < j\) |
三角分解中常见 |
置换 |
每行每列恰一个 1 |
乘以向量置换元素；逆 = 转置 |
对称 |
\(A = A^T\) |
特征值为实数；可对角化（谱定理） |
单位三角 |
三角矩阵 + 对角元全 1 |
用于 LU 分解 |
When：建模与算法设计中识别特殊矩阵以选择高效子程序。
Example：置换矩阵 \(P\) 左乘向量置换其元素；右乘矩阵置换其列。
2.3 矩阵运算
What：矩阵加法（逐元素）、标量乘法（数乘每元素）、矩阵乘法（行 × 列求和）。
Why：矩阵乘法的复杂度 \(\Theta(n^3)\)（naive）是很多数值算法的瓶颈；理解其性质（不交换、结合、分配）是分析的前提。
How：
| 性质 | 公式 |
|---|---|
加法（逐元素） |
\((A + B)_{ij} = a_{ij} + b_{ij}\) |
标量乘法 |
\((cA)_{ij} = c a_{ij}\) |
矩阵乘法 |
\((AB)_{ij} = \sum_k a_{ik} b_{kj}\)（式 D.2） |
结合律 |
\(A(BC) = (AB)C\) |
分配律 |
\(A(B + C) = AB + AC\) |
不交换 |
一般 \(AB \neq BA\) |
单位矩阵 |
\(I A = A I = A\) |
转置 |
\((AB)^T = B^T A^T\) |
内积 |
\(x^T y = \sum_i x_i y_i\) |
外积 |
\((xy^T)_{ij} = x_i y_j\) |
范数 |
\(|x| = \sqrt{x^T x}\) |
When：所有线性代数计算；第 4 章 Strassen 改进至 \(O(n^{\lg 7})\)，第 28 章单纯形法的核心运算。
Example：naive 矩阵乘法 \(\Theta(n^3)\)；Strassen \(\Theta(n^{\lg 7}) \approx \Theta(n^{2.81})\)；Coppersmith-Winograd 进一步降至 \(O(n^{2.373})\)。
2.4 逆、秩、线性无关
What：本节讨论三个紧密相关的概念——逆（可否还原）、线性无关（最少表示）、秩（有效维度）。
-
逆：\(AA^{-1} = I_n = A^{-1} A\)，存在时唯一。
-
线性无关：向量 \(x_1, \ldots, x_n\) 线性无关若 \(c_1 x_1 + \cdots + c_n x_n = 0\) 蕴含所有 \(c_i = 0\)。
-
秩：列秩 = 最大线性无关列数 = 行秩（Theorem D.1）。
Why：可逆性是「能否解线性方程组」「矩阵是否退化」的核心；秩给矩阵「有效维度」。
How：
| 概念 | 定义 |
|---|---|
逆 |
\(A A^{-1} = I_n\)；存在 ⟺ 满秩 ⟺ 非奇异 |
满秩 |
\(n \times n\) 矩阵 rank = \(n\) |
列秩 |
最大线性无关列数 |
行秩 |
最大线性无关行数 |
null vector |
非零 \(x\) 使 \(Ax = 0\)；存在 ⟺ 不满列秩 |
唯一逆 |
若 \(B, C\) 都是 \(A\) 的逆，则 \(B = C\)（练习 D.2-1） |
逆的逆 |
\((A^{-1})^{-1} = A\) |
逆与转置 |
\((A^{-1})^T = (A^T)^{-1}\) |
逆与乘积 |
\((AB)^{-1} = B^{-1} A^{-1}\) |
Theorem D.2：\(A\) 有满列秩 ⟺ 无 null vector。
When：解线性方程组（满秩 ⟺ 唯一解）；矩阵分解的前提条件。
Example：\(A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\) 的逆是 \(\begin{pmatrix} 0 & 1 \\ 1 & -1 \end{pmatrix}\)（Fibonacci 矩阵）。
2.5 行列式
What：行列式是 \(n \times n\) 矩阵的标量值，递推定义为：
Why：行列式判断矩阵是否可逆（det = 0 ⟺ 奇异）；是特征多项式的常数项；与体积、特征值等几何对象关联。
How：
| 性质 | 描述 |
|---|---|
零行列 |
任意行或列为零 ⟹ det = 0 |
数乘一行 |
整行数乘 c ⟹ det 乘 c |
行加法不变 |
某行加到另一行 det 不变 |
转置不变 |
\(\det(A^T) = \det(A)\) |
行交换变号 |
交换两行 ⟹ det 乘 -1 |
乘积 |
\(\det(AB) = \det(A) \det(B)\) |
Theorem D.5 |
\(A\) 奇异 ⟺ det = 0 |
三角矩阵 |
det = 对角元之积 |
When：判断可逆性；计算特征多项式；几何上 = 体积缩放因子。
Example：\(\det\begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad - bc\)。
2.6 正定矩阵
What：\(n \times n\) 实对称矩阵 \(A\) 正定若对所有非零 \(x\)，\(x^T A x > 0\)；半正定若 \(\geq 0\)。
Why：正定矩阵在二次规划、Newton 法、最小二乘、高斯过程等广泛应用；保证优化问题的凸性、算法的稳定性。
How：
| 性质 | 描述 |
|---|---|
单位矩阵 |
\(I_n\) 正定（\(x^T I x = |x|^2 > 0\)） |
对角矩阵 |
所有对角元 > 0 ⟺ 正定 |
特征值 |
所有特征值 > 0 ⟺ 正定 |
Cholesky 分解 |
正定 ⟺ 可分解为 \(A = LL^T\) |
满列秩 + Theorem D.6 |
\(A^T A\) 正定（\(x^T A^T A x = |Ax|^2 > 0\)） |
加法 |
两正定之和正定 |
逆 |
正定的逆仍正定 |
Theorem D.6 证明：\(x^T (A^T A) x = (Ax)^T (Ax) = \|Ax\|^2 \geq 0\)；若 = 0 则 \(Ax = 0\)，满列秩 ⟹ \(x = 0\)，矛盾。
When：二次目标函数 \(\frac{1}{2} x^T Q x + c^T x\) 的 Hessian 正定 ⟺ 严格凸 ⟺ 唯一全局最小；最小二乘问题自动正定。
Example：\(\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}\) 正定（特征值 3, 1 均 > 0）；\(\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\) 不正定（特征值 ±1）。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((附录 D 矩阵))
基础定义
矩阵向量
转置
零与单位
特殊矩阵
对角三角
置换对称
三对角
矩阵运算
加法标量乘
矩阵乘法
分配结合
不交换
逆与秩
逆矩阵
线性无关
秩行列无关数
行列式
递推定义
乘积性
判可逆
正定矩阵
二次型
特征值正
A转置A构造五、重点与易错点
-
矩阵乘法不交换：对 \(n > 1\)，一般 \(AB \neq BA\)；这是与标量乘法的关键区别。
-
转置反转乘法顺序：\((AB)^T = B^T A^T\)；常被忽略导致错误。
-
逆矩阵存在 ⟺ 行列式 ≠ 0 ⟺ 满秩 ⟺ 零空间只有零向量（Theorem D.1, D.5, D.2 联合）。
-
「非奇异」「可逆」「满秩」三词同义——描述同一性质的不同侧面；不要被术语混淆。
-
零矩阵的逆不存在（det = 0）；单位矩阵的逆是自身。
-
正定 ⟹ 对称：定义本身只要求对称矩阵正定；非对称矩阵的「正定性」需另行定义（如 Cholesky 分解要求对称）。
-
正定的等价条件：所有特征值 > 0；所有顺序主子式 > 0（Silvester 准则）；可 Cholesky 分解。
-
最小二乘自动正定：求解 latexmath[\min \|Ax - b\|^2] 时法方程 \(A^T A x = A^T b\) 中 \(A^T A\) 满列秩时正定，故可解。
-
矩阵乘法的 Strassen 算法：分治 + 7 次子乘法（而非 8 次）⟹ \(O(n^{\lg 7}) \approx O(n^{2.81})\)；第 4 章。
-
置换矩阵的逆 = 转置：因 \(P^T P = I\)；这是置换「一一对应」的代数表达。
-
行列式几何意义：二维 = 平行四边形有向面积；三维 = 平行六面体有向体积；n 维 = 平行体的 n 维体积缩放因子。
-
可逆性与双射：\(A: \mathbb{R}^n \to \mathbb{R}^n\) 可逆 ⟺ 作为线性映射是双射 ⟺ 无非零零空间元素。