1.md

矩阵计算

1. 符号介绍

略

2. 线性空间

2.1 定义

线性空间是指在一个集合 $S$ 上定义了加法和数乘运算, 且数乘满足下列线性规则, 即 $\forall \alpha, \beta\in P, \forall x,y\in S$ 均有

$$ \alpha(x+y) = \alpha x + \alpha y \\ (\alpha+\beta)x = \alpha x + \beta x \\ \alpha(\beta x) = (\alpha \beta) x \\ $$

*广义来说, 在一个地方内的元素经过可定义的操作, 新元素仍不会超过该地方, 则将其称为空间.

如何定义加法和乘法?

例如, 在 $\mathbb{R}^{n}$ 中, "加法" 运算定义为

$$ \cdots $$

点乘定义为 $\cdots $

思考: 在 $n$ 维实空间中, 两个向量连接的直线和线段分别怎么表示.

答案: $\lambda a + (1-\lambda)b, \lambda \in R, \lambda \in [0, 1]$

2.2 线性子空间

若 $S$ 和 $Q$ 同为线性空间, 且 $Q \subset S$, 则称 $Q$ 为 $S$ 的线性子空间.

例: 次数小于等于 $n$ ($n > 0$) 的实系数多项式的全体时线性空间. 次数等于 $n$ ($n > 0$) 的实系数多项式的全体不是线性空间 (因为 $0$ 不存在这个空间).

2.3 零空间与像空间

设 $A \in R^{m\times n}$ 为一个 $m\times n$ 矩阵, 其所对应的变换 $y = Ax$ ($x \in R^{n}$) 的值域 (像空间) 定义为

$$ R(A) = { y \in R^{m} | y = Ax, x\in R^{n} } $$

零空间 (核空间) 为 $Ax = 0$ 的所有解向量 $x \in R^{n}$ 组成的集合

$$ N(A) = { x \in R^{n} | Ax = 0, x\in R^{n} } $$

例: 给定 $A \in R^{m\times n}$, 求证 $R(A)$ 是 $R^{m}$ 的子空间, $N(A)$ 是 $R^{n}$ 的子空间.

要证明实空间 $S$ 是线性空间, 只需要证明

$\forall x, y \in S, \forall \alpha, \beta \in R$, 都有 $\alpha x + \beta y \in S$.

若有 $b \in R(A)$, 则一定存在 $x \in R^{n}$ 使得 $b = Ax$.

因此 $y = Ax$ 是否有解取决于是否 $y \in R(A)$.

2.4 向量系的生成空间

设有一组向量系 $x_1, x_2, \cdots , x_k$, 其中 $x_{i} \in R^{n}, i=1,2,\cdots ,k$, 则这一组向量系的所有线性组合的集合

$$ S = { y \in R^{n} | y = \alpha_1 x_1 + \alpha_2 x_2 + \cdots + \alpha_k x_k, \forall \alpha_1, \alpha_2, \cdots, \alpha_k } $$

容易证明 $S$ 是 $R^{n}$ 的一个子空间, 称为这一组向量系得生成空间.

因此所谓 $A$ 的像空间, 就是 $A$ 的列向量张成的空间.

即 $A = [x_1 \cdots x_k] \in R^{m \times n}$, 有 $S = R(A)$.

2.5 线性相关和线性无关

对于给定的一组向量系 $[x_1, x_2, \cdots, x_m], \forall x_i \in R^{n}$, 如果仅仅当 $\alpha_1, \alpha_2, \cdots, \alpha_m$ 都为零时, 其线性组合

$$ \alpha_1 x_1 + \alpha_2 x_2 + \cdots + \alpha_m x_m = 0 $$

则就称向量系 $[x_1, x_2, \cdots, x_m]$ 是线性无关的, 反之则是线性相关的.

如果在线性空间 $S$ 中存在有 $n$ 个向量线性无关, 而任何 $n+1$ 个向量均线性相关, 则称空间 $S$ 的维数为 $n$, 记作 $\operatorname{dim}(S) = n$.

若 $S$ 是定义在数域 $R$ 上的线性空间, 且 $S$ 中的向量系 $[x_1, x_2, \cdots, x_m]$ 满足以下两条:

• $[x_1, x_2, \cdots, x_m]$ 线性无关;
• $\forall x \in S$, $x$ 都可以表示成 $x = \alpha_1 x_1 + \alpha_2 x_2 + \cdots + \alpha_n x_n$;

则称向量系 $x_1, x_2, \cdots, x_n$ 是空间 $S$ 的一组基底.

基底上的向量表示唯一, 可以通过线性无关定义证明.

2.6 线性空间的四种运算

• $T \cap V = { x | x \in T \land x \in V }$
• $T \cup V = { x | x \in T \lor x \in V }$
• $T + V = { x | x = y + z, y \in T, z \in V }$
• $T \oplus V = { x | x = y + z, y \in T, z \in V, T \cap V = { 0 } }$

$T \cup V$ 不一定是线性子空间.

3. 矩阵

3.1 矩阵与线性方程组

$A x = b$

$A$: 系数矩阵, $x$: 未知向量, $b$: 右端项 (观察项, 输出项)

$a_1x_1 + a_2x_2 + \cdots + a_n x_n = b$

$A = \begin{bmatrix} a_1, a_2, \cdots, a_n \end{bmatrix}$

---

对于线性方程组的系数矩阵 $A$ 常有三种形式：

1. $m > n$ 时常称矩阵 $A$ 是 "高矩阵", 相应的线性方程组为超定方程组 (overdetermined systems);
2. $m = n$ 时矩阵 $A$ 称为正方矩阵 (square matrix);
3. $m < n$ 时矩阵 $A$ 常称为 "宽矩阵", 相应的线性方程组为亚定方程组 (underdetermined systems). 但方程组 $Ax=b$ 中矩阵的上面三种形式, 仅仅是形式上的差别, 并不是影响其解 (有解、无解等) 的本质差别.

3.2

性质:

• $AB \neq BA$
• $(AB)C = A(BC)$

思考:

• $AB \neq BA$ (什么时候等于)

3.3 行列式

$\det(A) = |\lambda_1| \cdots |\lambda_m|$

性能指标	性能
二次型	矩阵的正定性和负定性
行列式	矩阵的奇异性
特征值	矩阵的奇异性, 正定性, 对角线元素结构
迹	矩阵对角线元素和
秩	-

• 特征值、特征向量
• 谱分析
• 为什么要研究矩阵特征值和特征向量:
  • 矩阵和矩阵的比较是很难的, 我们要研究一个矩阵为什么是好的, 关键就在于谱.
  • 一个矩阵会产生很多特征值, 如果这些特征值的分布较好, 例如矩阵的大部分特征值集中, 少部分分散, 则可以忽略掉分散的那部分特征值.
  • 大部分的特征值的能量应该要接近, 差别不能过大.
  • 标记传播, 随机游走, 马尔可夫过程等等方法中的矩阵计算, 其本质都是谱的分析, 都是对矩阵特征值的分析.
  • 关键在于如何快速地计算矩阵的特征值.
  • 特征分解, 矩阵分解的关键在于将特征值与特征向量分解出来. 无论是为了存储, 还是计算, 都是十分重要的.
  • 还有矩阵求导, 特征值求导. $A \to \dot{A}$, 特征值如何 $\mu_c \to \dot{\mu}_c$ ?
  • 矩阵压缩也是一样的, 可以去掉特征值较小的那部分.
  • 计算和压缩是需要权衡的, 傅里叶变换的计算开销大, 但是可以压缩得更小; 余弦变换的计算开销小, 但是压缩的结果较大.
• 矩阵计算 (矩阵分解) => 特征值, 特征向量, 距离度量 => 人工智能 (聚类分类, 计算机视觉)

3.4 矩阵二次型

• $A$ 是实对称矩阵或复共轭矩阵.

若遇到 $x^{\mathrm{H}}Bx, B = A^{\mathrm{H}}A$, 我们称 $B = A^{\mathrm{H}}A$ 为 Hermitian 矩阵, 我们要尽量将其转为 $A = Q^{\mathrm{T}}Q$ 的形式.

• 正定矩阵: $\forall x \neq 0, x^{\mathrm{H}}Ax > 0$, 记作 $A \succ 0$
  • 关键在于特征值大于零, $x^{\mathrm{H}}Ax = (Qx)^{\mathrm{T}}\Lambda (Qx) > 0$
  • 谱分析是完全二部图

3.5 矩阵特征值

矩阵特征值是 $n$ 阶矩阵的最重要的数值特征之一, 也是一个有重要应用背景的数值特征.

线性变换 $T$ 的输出向量与输入向量只相差一个比例因子 $\lambda$, 也就是

$$ Tu = \lambda u, u \neq 0 $$

则称标量 $\lambda$ 和向量 $u$ 分别是线性变换 $T$ 的 特征值 和 特征向量.

特征向量不是唯一的.

由定义可得

$$ (A - \lambda I)u = 0 $$

实际上即变为求解行列式

$$ \det(A - \lambda I) = 0 $$

同理, 由这个式子也可以看出, 只要有一个特征值是 $0$, 则 $A$ 为奇异矩阵.

---

$A = \begin{bmatrix} 1 & 2 & 0 \ -1 & 2 & -1 \ 0 & 1 & 1 \\end{bmatrix}$

$A^T = \begin{bmatrix}1 & -1 & 0\2 & 2 & 1\0 & -1 & 1\end{bmatrix}$

$A^TA = \begin{bmatrix}2 & 0 & 1\0 & 9 & -1\1 & -1 & 2\end{bmatrix}$

$\det(A^TA - \lambda I) = \begin{vmatrix}2 - \lambda & 0 & 1\0 & 9 - \lambda & -1\1 & -1 & 2 - \lambda\end{vmatrix} = - \lambda^{3} + 13 \lambda^{2} - 38 \lambda + 25 = 0$

$[ \lambda_1 = \frac{13}{3} + (- \frac{1}{2} - \frac{\sqrt{3} i}{2}) \sqrt[3]{\frac{623}{54} + \frac{\sqrt{30819} i}{18}} + \frac{55}{9 (- \frac{1}{2} - \frac{\sqrt{3} i}{2}) \sqrt[3]{\frac{623}{54} + \frac{\sqrt{30819} i}{18}}}, \ \lambda_2 = \frac{13}{3} + \frac{55}{9 (- \frac{1}{2} + \frac{\sqrt{3} i}{2}) \sqrt[3]{\frac{623}{54} + \frac{\sqrt{30819} i}{18}}} + (- \frac{1}{2} + \frac{\sqrt{3} i}{2}) \sqrt[3]{\frac{623}{54} + \frac{\sqrt{30819} i}{18}}, \ \lambda_2 = \frac{13}{3} + \frac{55}{9 \sqrt[3]{\frac{623}{54} + \frac{\sqrt{30819} i}{18}}} + \sqrt[3]{\frac{623}{54} + \frac{\sqrt{30819} i}{18}}]$

$[ \lambda_1 = 2.92112493807244, \ \lambda_2 = 0.936075017171059, \ \lambda_3 = 9.1428000447565]$

求解 $(\lambda_i I - A^TA)u = 0$ 的非零解, 即

$\lambda_1 I - A^TA = \begin{bmatrix}\lambda_1 & 0 & 0\0 & \lambda_1 & 0\0 & 0 & \lambda_1\end{bmatrix} - \begin{bmatrix}2 & 0 & 1\0 & 9 & -1\1 & -1 & 2\end{bmatrix} = \begin{bmatrix}0.92112493807244 & 0 & -1.0\0 & -6.07887506192756 & 1.0\-1.0 & 1.0 & 0.92112493807244\end{bmatrix}$

---

• 若 $A, B$ 均为 $n \times n$ 矩阵, 则矩阵乘积特征值 $\operatorname{eig}(AB) = \operatorname{eig}(BA)$
• 若 $A$ 为 $m \times n$ 矩阵, $B$ 为 $n \times m$ 矩阵, 那么 $\operatorname{eig}(AB)$ 和 $\operatorname{eig}(BA)$ 具有相同的非零特征值, 所不同的是零特征值的重数不一样
• 逆矩阵的特征值 $\operatorname{eig}(A^{-1}) = 1 / \operatorname{eig}(A)$
• 设 $I_n$ 为 $n \times n$ 单位矩阵, $c$ 为标量, 则
  • $\operatorname{eig}(I_n + cA) = 1 + c \cdot \operatorname{eig}(A)$
  • $\operatorname{eig}(A + c I_n) = \operatorname{eig}(A) + c$
  • 很重要的一点: 怎么求逆才能比较稳定.
  • 也就是说, 只要在对角线上加一个小常数, 就能变得稳定.
• 相异特征值对应的特征向量是线性无关的.
• 若 $A$ 是 $n \times n$ 的实对称矩阵, 则所有特征值都是实数, 其 $n$ 个特征向量可以构成一个完备系, 即一定存在 $n$ 个互相正交的特征向量可以构成 $n$ 维空间的基底.

---

二次型本质定义:

• 正定矩阵: 所有特征值大于零
• 半正定矩阵: 所有特征值为非负实数
• 负定矩阵: 所有特征值小于零
• 半负定矩阵
• 不定矩阵

矩阵特征值是刻画矩阵特性 (奇异性, 正定性等) 的重要特征.

3.6 矩阵的迹

对角线元素的和成为迹 $\operatorname{tr}(A) = a_{11} + a_{22} + \cdots + a_{nn}$

我们有 $\operatorname{tr}(A) = \sum_{i} \lambda_i$

因为我们将 $|\lambda I - A| = 0$ 展开有 $\lambda^{n} + a_1 \lambda^{n-1} + \cdots + a_n = 0$

则由韦达定理有 $-a_1 = \sum_{i} \lambda_i$

迹是特征值的和, 也就是 1-范数, 而 1-范数是 0-范数的最小凸包.

性质:

• $\operatorname{tr}(\alpha A + \beta B) = \alpha \operatorname{tr}(A) + \beta \operatorname{tr}(B)$
• $A \in R^{m \times n}, B \in R^{n \times m}$, 则 $\operatorname{tr}(AB) = \operatorname{tr}(BA)$
  • $\operatorname{tr}(AB) = \sum_{i = 1}^{n}(AB){ii} = \sum{i = 1}^{n}(\sum_{j=1}^{n}a_{ij}b_{ji})$
  • $\operatorname{tr}(BA) = \sum_{j = 1}^{n}(BA){jj} = \sum{j = 1}^{n}(\sum_{i=1}^{n}b_{ji}a_{ij})$
• $\operatorname{tr}(A^{\mathrm{H}}A) = 0$, 则 $A = 0_{m \times n}$
  • $A = (\alpha_1, \alpha_2, \cdots, \alpha_n)$
  • $\operatorname{tr}(A^{\mathrm{H}}A) = \sum_{i=1}^{n}|\alpha_{i}|^{2} = 0$
• $\operatorname{tr}(xy^{\mathrm{T}}) = y^{\mathrm{T}}x$, $x^{\mathrm{T}}Ax = \operatorname{tr}(Axx^{\mathrm{T}})$

3.7 矩阵的秩

线性无关:

一组 $m$ 维 $n$ 个向量组成的向量系 $u_1, u_2, \cdots, u_n$ 线性无关, 是指只有当 $n$ 个系数 $\alpha_1, \cdots, \alpha_n$ 全为零时,

$$ \alpha_1 u_1 + \alpha_2 u_2 + \cdots + \alpha_n u_n = 0 $$

才成立.

秩:

设 $A$ 是一个 $n \times n$ 矩阵, 列向量系的极大线性无关组所含向量数是 $r (\le \min(m, n))$, 则称矩阵 $A$ 的秩为 $r$. 记作

$$ \operatorname{rank}(A) = r $$

性质:

• 秩等于非零特征值的个数.
• $\operatorname{rank}(A)$ 是正整数.
• $\operatorname{rank}(A) \le \min(m, n)$
• $\operatorname{rank}(A) = \operatorname{rank}(A^{\mathrm{T}})$
• 常数/标量 (scalar) $c \neq 0$, 则 $\operatorname{rank}(cA) = \operatorname{rank}(A)$
• $A \in R^{m \times n}, B \in R^{m \times m}, C \in R^{n \times n}$ 非奇异矩阵, 则 $\operatorname{rank}(BA) = \operatorname{rank}(AC) = \operatorname{rank}(BAC) = \operatorname{rank}(A)$
  • $\operatorname{rank}(BA) \le \min(\operatorname{rank}(B), \operatorname{rank}(A)) \le \operatorname{rank}(A)$
  • $\operatorname{rank}(A) = \operatorname{rank}(B^{-1}BA) \le \operatorname{rank}(BA)$

思考题:

• $\operatorname{rank}(AB) \le \min(\operatorname{rank}(A), \operatorname{rank}(B))$

证明:

不妨设 $A \in R^{n \times k}, B \in R^{k \times m}$

令 $\bm{C} = \bm{A}\bm{B} = \bm{A}\begin{bmatrix} \bm{b_1}, \bm{b_2}, \cdots, \bm{b_m} \end{bmatrix} = \begin{bmatrix} \bm{A}\bm{b_1}, \bm{A}\bm{b_2}, \cdots, \bm{A}\bm{b_m} \end{bmatrix} = \begin{bmatrix} \bm{c}_1, \bm{c}_2, \cdots, \bm{c}_m \end{bmatrix}$

则 $\bm{c}j = \bm{A}\bm{b}j = \sum{i=1}^{k}b{ij}\bm{a}_{j}$

即 $\bm{A}\bm{B}$ 的列向量可以由 $\bm{A}$ 的列向量线性表出, 因此有

$\operatorname{rank}(AB) \le \operatorname{rank}(A)$

同理有 $\operatorname{rank}(AB) \le \operatorname{rank}(B)$

因此 $\operatorname{rank}(AB) \le \min(\operatorname{rank}(A), \operatorname{rank}(B))$

---

根据 $A \in R^{m \times n}$ 的秩的大小, 线性方程组可以分为三种类别:

• 适定线性方程组: 若 $m = n$ 且 $\operatorname{rank}(A) = n$, 即 $A$ 为非奇异矩阵.
• 欠定线性方程组: $\operatorname{rank}(A) = m < n$, 方程组无唯一解.
• 超定线性方程组: $\operatorname{rank}(A) = m > n$, 方程组无解.

3.8 内积和范数

• 定义范数函数 $\rho(x)$
  • $\rho(x) \ge 0$, 且 $\rho(x) = 0$ 当且仅当 $x = 0$
  • $\rho(\alpha x) = |\alpha|\rho(x)$
  • $\rho(x + y) \le \rho(x) + \rho(y)$
• 定义了范数之后, 就能定义夹角余弦
• 任何的距离都定义在范数上.

Lp 范数:

• $\left| x \right|{p} = (\sum{i = 1}^{n}(x_i)^{p})^{\frac{1}{p}}$
• $\left| x \right|_{0} \triangleq$ 非零元素个数. 非凸范数.
• $\left| x \right|_{1} \triangleq |x_1| + |x_2| + \cdots + |x_n|$
• $\left| x \right|_{2} \triangleq (|x_1|^{2} + |x_2|^{2} + \cdots + |x_n|^{2})^{\frac{1}{2}}$
• $\left| x \right|_{\infty} \triangleq \max{ |x_1|, |x_2|, \cdots, |x_n| }$

函数空间的内积与范数:

若 $x(t)$ 和 $y(t)$ 都是闭区间 $[a,b]$ 上的连续函数, 则它们的内积

$$ \left<x(t), y(t)\right> \triangleq \int_{a}^{b}x(t)y(t)\mathrm{d}t $$

正交:

若向量内积等于零, 即 $\left&lt;x, y \right&gt; = 0$, 则称这两个向量正交.

• 几何意义: 向量垂直.
• 物理意义: 两个向量不会包含对方任何成分, 即不会互相交融, 也不会互相干扰.

正交向量系:

给定一组 $n$ 维向量 $x_1, x_2, \cdots, x_m$, 其中 $m \le n$, 如果两两正交满足

$$ \left<x_i, x_j\right> = \begin{cases} a_i > 0, & i = j \ 0, & i \neq j \end{cases} \quad i, j = 1, 2, \cdots, m $$

则称 $x_1, x_2, \cdots, x_m$ 是一组正交向量系, 若还有 $\left| x_i \right| = 1$, 则称为标准正交向量系.

3.9 矩阵范数

• $L_1$ 范数 ($p = 1$)
• Frobenius 范数 ($p = 2$)