GAMES001课程笔记01-线性代数基础

这个系列是GAMES001-图形学中的数学(GAMES 001: Mathematics in Computer Graphics)的同步课程笔记。课程旨在总结归纳图形学学习过程中重要的数学概念、理论和方法，并将以索引的形式在每一章节中穿插讲解该数学专题在图形学中的应用。本课程既可以作为GAMES系列其它课程学习的基础或「手册」，也可以作为站在不一样的视角复习图形学知识的平台。本节主要介绍线性代数的相关内容。

向量

向量(vector)是图形学中最基本的研究对象之一，像是空间中点的位置或是物体表面的法向都可以用向量来表示。实际上，早在中学阶段我们就接触过向量的概念。当时我们把向量定义为既有大小又有方向的量，一般用一个箭头来表示，同时向量之间的运算需要满足平行四边形法则。

向量空间

关于向量更加严格的定义需要引入向量空间(vector space)的概念。具体来说，数域 $F$ 上具有加法和标量乘法的非空集合 $V$ 即为 $F$ 上的向量空间，其中的元素则称为向量。一个向量空间需要满足一系列的性质，包括加法封闭性、标量乘法封闭性、加法交换律、加法结合律、标量乘法结合律、分配律等。一般来说图形学相关的研究中数域 $F$ 大多是取为实数域 $R$ ，但有些时候也会取复数域 $C$ 或其他合适的数域。

线性组合

在向量空间的基础上我们可以引入线性组合(linear combination)的概念。简单来说，线性组合就是把一组向量 ${u_{1}, u_{2}, . . ., u_{n}}$ 通过系数 $a_{1}$ , $a_{2}$ , …, $a_{n}$ 加起来。如果存在不全为0的一组系数能够使得 $a_{1} u_{1} + a_{2} u_{2} + . . . + a_{n} u_{n} = 0$ ，则称向量集合 ${u_{1}, u_{2}, . . ., u_{n}}$ 是线性相关的；反之则称这一组向量是线性无关的。

线性组合的一个重要应用是用来定义向量空间的维度(dimension)。我们把向量空间中能够找出的一组线性无关向量的个数的最大值称为向量空间的维度，记为 $\dim V$ 。同时， $\dim V$ 个线性无关的向量可以构成向量空间中的一组基矢(basis vectors)。容易证明，空间中的任意一个向量都可以唯一地表示为这组基矢的线性组合，而线性组合的系数则称为该向量在这组基下的坐标(coordinates)。

在图形学的研究中我们往往会接触到各种低维或高维的向量空间。

矩阵

线性映射

两个向量空间 $V$ 和 $W$ 可以通过线性映射(linear mapping) $f : V \to W$ 进行联系，它需要满足如下定义：

$f (u + v) = f (u) + f (v)$
$f (α v) = α f (v)$

在低维空间中的缩放和旋转都是线性映射，但是需要注意平移不是线性映射。

矩阵

在线性映射的基础上我们可以定义矩阵(matrix)。尽管它最常见的形式是一个二维的数组，但它更合理的理解方式则是对线性映射的一种表示方法。实际上矩阵乘法的意义是给出原始空间 $V$ 中的基矢在新空间 $W$ 基矢下的坐标。在这种观点下，矩阵的乘法可以理解为线性映射的复合，即对空间多次相继变换的合成。

矩阵单目运算

特征值

如果向量 $u$ 满足方程 $A u = λ u$ ，则称向量 $u$ 为矩阵 $A$ 的特征向量(eigenvector)， $λ$ 称为对应的特征值(eigenvalue)。从线性映射的角度来看，特征值的意义在于它说明了对于某些向量，线性映射的作用等价于用特征值进行数乘运算。

矩阵特征值的一个重要应用是用于计算矩阵多项式的特征值。对于矩阵 $A$ ，我们定义它的矩阵多项式为 $f (A) = c_{k} A^{k} + c_{k - 1} A^{k - 1} + . . . + c_{1} A + c_{0} E$ ，则我们有如下结论：

若 $λ$ 是矩阵 $A$ 的特征值，则 $f (λ)$ 必为 $f (A)$ 的特征值
设矩阵 $A$ 的特征值为 ${λ_{1}, λ_{2}, . . ., λ_{n}}$ ；则 $f (A)$ 的全部特征值由 $f (λ_{1})$ , $f (λ_{2})$ , …, $f (λ_{n})$ 给出

上述性质表明矩阵多项式的特征值可以由矩阵的特征值来完全确定，这样我们就可以通过分析矩阵的特征值来理解矩阵多项式的行为。

度量空间

需要注意的是向量空间中的元素本身是不能进行比较的。如果要比较不同的元素则还需要定义一个度量函数 $d : V \times V \to R$ ，它需要满足非负性、同一性、对称性以及三角不等式等性质。定义了度量函数的集合 $V$ 称为度量空间(metric space)，其中度量函数 $d$ 描述了空间中元素之间的「距离」。

当我们在向量空间上引入度量函数就得到了赋范向量空间(normed vector space)，其度量函数 $d$ 一般也被称为「范数」，记为 $‖ \cdot ‖$ 。

内积空间

在赋范向量空间的基础上我们还可以进一步定义内积空间(inner product space)，其中内积函数 $< \cdot, \cdot >: V \times V \to R$ 给出了向量之间的夹角。

通过内积我们可以计算任意两个向量之间的夹角，当两个向量的内积为0时称这两个向量相互正交(orthogonal)。对于向量空间中的一组基，如果任意两个基矢都是相互正交的单位向量，则称这组基是向量空间中的一组单位正交基。事实上，我们可以通过施密特正交化以及向量规范化的技术将向量空间中的任意一组基转换为单位正交基。单位正交基有很多非常方便的性质。由于基矢都是相互正交的单位向量，使用单位正交基表达的向量进行内积时只需要对相应的坐标进行乘法和求和运算。我们熟悉的笛卡尔坐标系(Cartesian coordinates)就是 $R^{n}$ 中一组单位正交基加上原点构成的坐标系。

不改变向量内积的变换称为单位正交变换。在单位正交变换下，单位正交基会被变换为空间中的另一组单位正交基。使用矩阵进行表示时，变换矩阵 $R$ 需要满足 $R^{T} = R^{- 1}$ 。这样的矩阵对应空间中的旋转变换以及镜像空间中的旋转变换。

幺正空间与幺正变换

定义了内积的复数域 $C$ 的线性空间称为幺正空间(unitary space)，其内积通过Hermite函数给出。很多实数域上内积空间的定义和性质都可以直观地推广到幺正空间中。

应用

接下来我们介绍向量和矩阵在图形学中的各种应用。

低维变换矩阵

以二维空间为例，平面上点的位置坐标可以表示为一个二维向量，而坐标的线性变换则表示为一个矩阵。不难发现，各种二维线性变换(缩放、剪切、旋转等)的矩阵具有相应的形式。

三维空间与二维的情况类似，不过需要说明的是三维空间的旋转要比二维复杂很多，相关的内容我们会在后面的课程进行介绍。

齐次坐标

进行坐标变换的一个技巧在于引入齐次坐标(homogeneous coordinate)，即在n维空间中使用n+1维向量来表示。在齐次坐标的意义下，对向量进行等比例缩放不影响其n维坐标的意义。

(\begin{matrix} x, y, z, w \end{matrix}) \leftrightarrow (\begin{matrix} \frac{x}{w}, \frac{y}{w}, \frac{z}{w}, 1 \end{matrix})

利用齐次坐标我们可以把整个坐标变换都使用一个矩阵来进行表示。根据矩阵运算的规则，这样表示的坐标变换等价于按照缩放、旋转、平移的顺序进行处理。

矩阵变换

既然矩阵可以理解为线性变换，那么对矩阵进行的变换实际上就是对线性变换进行的「变换」。在这样的认识下，矩阵的相似变换和合同变换都可以理解为某些情况下特殊的线性变换。

二次型

关于n个变量的二次多项式可以利用矩阵表示为一个二次型(quadratic form) $x^{T} A x$ ，其中矩阵 $A$ 包含了多项式的系数。我们在中学阶段接触过的圆锥曲线可以通过二次型来得到一个规范的表达。

从二次型的角度来理解合同变换，不难发现变换后的系数矩阵 $C^{T} A C$ 实际上对应着坐标变换后的二次型系数。这种表示揭示了合同变换对于二次型的影响: 它实际上是在原始二次型中进行了坐标变换，从而改变了二次型的系数矩阵。

正定矩阵与对称矩阵

我们定义对于任意非0向量 $x$ 满足 $x^{T} A x > 0$ 的矩阵为正定(positive definite)矩阵，这样一个正定矩阵就对应着一个恒取正值的二次多项式。在很多实际应用中，我们往往会要求可微函数 $f$ 的二阶微分系数矩阵为正定矩阵，满足这样条件的函数具有很多优异的性质方便我们进行处理。

正定矩阵有很多重要的数学性质，比如说它的所有特征值都是正数。但是需要注意，这个命题的逆命题不成立。而对于实对称矩阵，只要它的特征值都是正数那么它就是正定矩阵。

矩阵分解

矩阵分解(matrix decomposition)在图形学中有着广泛的应用。矩阵的PLU分解指出一个方阵 $A$ 可以表示成3个矩阵的乘积:

A = P L U

其中 $P$ 为初等变换矩阵， $L$ 为下三角矩阵， $U$ 为上三角矩阵。当 $P$ 矩阵取单位阵时，PLU分解即为更加常见的LU分解。在求解线性方程组时常用的高斯消元法就可以理解为对矩阵进行PLU分解。

另一种常用的矩阵分解是Cholesky分解，它指出正定矩阵 $A$ 可以分解为

A = L L^{H}

其中 $L$ 为下三角矩阵。和LU分解相比，Cholesky分解一般具有 $O (n^{2})$ 而不是 $O (n^{3})$ 的复杂度，因此Cholesky分解在求解大规模稀疏矩阵方程中有着重要的应用。

除了上面介绍的两类矩阵分解外，QR分解以及奇异值分解(SVD)在物理仿真等领域中也都有着大量的应用。

向量和矩阵的范数

向量的范数(norm)可以用来描述向量的「长度」。常用的向量范数可以通过 $L_{p}$ 范数的规则来进行定义：

‖ x ‖_{p} = (| x_{1} |^{p} + | x_{2} |^{p} + \dots + | x_{n} |^{p})^{\frac{1}{p}}

需要注意的是 $L_{0}$ 范数不满足正定性、正齐次性以及三角不等式，因此严格来说 $L_{0}$ 范数并不是真正意义上的范数。

向量范数的概念可以推广到矩阵上，用来描述不同矩阵元素的「大小」。其中，矩阵的诱导范数(induced norm)定义为把矩阵 $A$ 作用在单位向量 $x$ 上所能得到的最大范数：

‖ A ‖ = max {‖ A x ‖ : x \in R^{n}, ‖ x ‖ = 1} = max {\frac{‖ A x ‖}{‖ x ‖} : x \in R^{n}, ‖ x ‖ \neq 0}

这样我们可以基于向量的 $L_{p}$ 范数得到矩阵的诱导 $L_{p}$ 范数：

‖ A ‖_{p} = max {\frac{‖ A x ‖_{p}}{‖ x ‖_{p}} : x \in R^{n}, ‖ x ‖ \neq 0}

从几何角度上看，矩阵的诱导 $L_{p}$ 范数实际上描述了矩阵 $A$ 作为线性变换对向量模长所能产生的最大放大倍数。

同时能够证明诱导范数的相容律：

‖ A x ‖ \leq ‖ A ‖ ‖ x ‖

利用诱导范数的相容律可以方便计算矩阵的各种诱导 $L_{p}$ 范数。

除了诱导范数外，我们还可以基于其它方式来定义矩阵范数。其中，矩阵的元素形式范数(entrywise norm)是先将矩阵降维成向量，然后对降维后向量求 $L_{p}$ 范数得到的矩阵范数。另一种常用的矩阵范数是Schatten范数，它的特点是范数不随幺正变换而发生变化。

矩阵求导

矩阵求导是一类非常实用的计算技术，在很多问题中我们都会遇到标量对一个矩阵进行求导的运算。在进行求导时我们需要考虑矩阵变元的布局，切记在计算时保证每一步所采用的布局是一致的。

首先考虑标量函数 $f (x)$ 对向量 $x$ 的求导，此时求导的结果是一个列向量：

\frac{\partial f (x)}{\partial x_{n \times 1}} = (\frac{\partial f}{\partial x_{1}}, \frac{\partial f}{\partial x_{2}}, \dots, \frac{\partial f}{\partial x_{n}})^{T}

一些常用的求导公式可以参考下方课件。

对于定义在矩阵上的标量函数 $f (X)$ ，其求导结果为一个矩阵：

\frac{\partial f (X)}{\partial X_{m \times n}} = (\begin{matrix} \frac{\partial f}{\partial x_{11}} & \dots & \frac{\partial f}{\partial x_{1 n}} \\ ⋮ & ⋱ & ⋮ \\ \frac{\partial f}{\partial x_{m 1}} & \dots & \frac{\partial f}{\partial x_{m n}} \end{matrix})

常用的矩阵求导公式可以参考下方课件。

对于更复杂情况下的矩阵求导问题，我们则可以借助矩阵的微分来进行处理。首先我们定义标量函数对向量以及矩阵的微分为：

d f (x) = (\frac{\partial f}{\partial x_{1}}, \frac{\partial f}{\partial x_{2}}, \dots, \frac{\partial f}{\partial x_{n}}) (\begin{matrix} d x_{1} \\ d x_{2} \\ ⋮ \\ d x_{n} \end{matrix}) = tr [\begin{matrix} (\frac{\partial f}{\partial x_{1}}, \frac{\partial f}{\partial x_{2}}, \dots, \frac{\partial f}{\partial x_{n}}) (\begin{matrix} d x_{1} \\ d x_{2} \\ ⋮ \\ d x_{n} \end{matrix}) \end{matrix}]

d f (X) = tr [\begin{matrix} {(\begin{matrix} \frac{\partial f}{\partial x_{11}} & \dots & \frac{\partial f}{\partial x_{m 1}} \\ ⋮ & ⋱ & ⋮ \\ \frac{\partial f}{\partial x_{1 n}} & \dots & \frac{\partial f}{\partial x_{m n}} \end{matrix})}_{n \times m} {(\begin{matrix} d x_{11} & \dots & d x_{1 n} \\ ⋮ & ⋱ & ⋮ \\ d x_{m 1} & \dots & d x_{m n} \end{matrix})}_{m \times n} \end{matrix}]

实际上我们可以把函数的微分 $d f$ 理解为自变量的变化趋于0时，函数差分 $Δ f$ 的一种极限情况。容易验证，上面的两个定义是符合这样的认知的。

接下来我们引入矩阵函数 $F (X)$ 的微分：

d F_{p \times q} (X) = {(\begin{matrix} d f_{11} (X) & \dots & d f_{1 q} (X) \\ ⋮ & ⋱ & ⋮ \\ d f_{p 1} (X) & \dots & d f_{p q} (X) \end{matrix})}_{p \times q}

不难发现 $d F$ 是一个 $p \times q$ 维的矩阵，其中每个元素都是标量函数 $f_{i j}$ 对矩阵 $X$ 的微分。这样我们可以把微分符号 $d$ 视为一个算子，它作用在不同类型的函数上时具有相应的定义。同时，微分算子还满足相应的运算规则。

利用矩阵的微分算子可以计算比较复杂的矩阵函数的导数。首先对于标量函数 $f (X_{m \times n})$ 我们有微分表达式：

d X_{m \times n} = {(\begin{matrix} d x_{11} & \dots & d x_{1 n} \\ ⋮ & ⋱ & ⋮ \\ d x_{m 1} & \dots & d x_{m n} \end{matrix})}_{m \times n}

\frac{\partial f (X)}{\partial X_{m \times n}^{T}} = {(\begin{matrix} \frac{\partial f}{\partial x_{11}} & \dots & \frac{\partial f}{\partial x_{m 1}} \\ ⋮ & ⋱ & ⋮ \\ \frac{\partial f}{\partial x_{1 n}} & \dots & \frac{\partial f}{\partial x_{m n}} \end{matrix})}_{n \times m}

结合 $d f (X)$ 的表达式不难发现

d f (X) = tr [\frac{\partial f (X)}{\partial X^{T}} d X]

因此我们只需要把微分 $d f$ 凑成类似上式的形式就可以得到相应的偏导数矩阵。

张量

内积、外积、向量积

在介绍张量相关的内容前我们需要先回顾一下向量的各种乘法。向量的内积(inner product)也称为标量积，它把两个向量映射为一个标量，其大小等于向量模长之积乘以它们夹角的余弦：

a \cdot b = ⟨ a, b ⟩ = ‖ a ‖ ‖ b ‖ \cos θ

向量的叉积(cross product)也称为向量积，它把两个向量映射为一个垂直于它们的新的向量，其方向由右手螺旋法则确定，大小等于向量模长之积乘以它们夹角的正弦：

a \times b = ‖ a ‖ ‖ b ‖ \sin θ

对于二维和三维向量的叉积，我们有相对简单的计算公式：

(a_{x}, a_{y}) \times (b_{x}, b_{y}) = a_{x} b_{y} - b_{x} a_{y}

(a_{x}, a_{y}, a_{z}) \times (b_{x}, b_{y}, b_{z}) = | \begin{matrix} e_{x} & e_{y} & e_{z} \\ a_{x} & a_{y} & a_{z} \\ b_{x} & b_{y} & b_{z} \end{matrix} |

除了上面介绍的两个常用公式外，三维向量的叉积还可以表达为一个反对称矩阵和向量的乘法：

a \times b = (\begin{matrix} 0 & - a_{z} & a_{y} \\ a_{z} & 0 & a_{x} \\ - a_{y} & a_{x} & 0 \end{matrix}) (\begin{matrix} b_{x} \\ b_{y} \\ b_{z} \end{matrix})

这样矩阵乘法表示的叉积在一些推导以及编程中有一定的优势。

向量的外积(outer product)也称为张量积，它将两个向量映射为一个矩阵：

a \otimes b = A = a b^{H}

在三维实数域上，上面的公式等价于：

(\begin{matrix} a_{x} \\ a_{y} \\ a_{z} \end{matrix}) (\begin{matrix} b_{x} & b_{y} & b_{z} \end{matrix}) = (\begin{matrix} a_{x} b_{x} & a_{x} b_{y} & a_{x} b_{z} \\ a_{y} b_{x} & a_{y} b_{y} & a_{y} b_{z} \\ a_{z} b_{x} & a_{z} b_{y} & a_{z} b_{z} \end{matrix})

同时不难发现外积的迹等于内积：

tr (a \otimes b) = a \cdot b

张量

张量(tensor)是对向量以及矩阵更本质的表达。在使用张量时我们需要区分张量的协变与逆变分量。简单来说，我们把使用上标的分量称为逆变(contravariant)分量，而把使用下标的分量称为协变(covariant)分量。以三维空间中的位移矢量为例，当我们给定一组基底 ${e_{1}, e_{2}, e_{3}}$ 时，位移矢量可以表示为：

x = x^{1} e_{1} + x^{2} e_{2} + x^{3} e_{3}

这里每个基底的分量都是逆变的，它暗示当基底的长度发生变化时分量会按照逆变换的规律进行变换。如果这组基底不是单位正交的，那么可以构造另一组基底 ${e^{1}, e^{2}, e^{3}}$ 使得它们满足Kronecker性质：

e_{i} \cdot e^{j} = δ_{i}^{j}

这组基底称为原来基底的逆变基，原来的基底相应称为协变基。显然位移矢量也可以使用逆变基来进行表示：

x = x_{1} e^{1} + x_{2} e^{2} + x_{3} e^{3}

利用Einstein求和约定，位移矢量在协变基和逆变基下的表示为

x = x^{i} e_{i} = x_{i} e^{j}

同时，不难发现

x \cdot e_{i} = (x_{1} e^{1} + x_{2} e^{2} + x_{3} e^{3}) \cdot e_{i} = x_{i}

x \cdot e^{i} = (x^{1} e_{1} + x^{2} e_{2} + x^{3} e_{3}) \cdot e^{i} = x^{i}

即协变分量 $x_{i}$ 由 $x$ 和协变基通过内积计算得到，逆变分量通过 $x$ 和逆变基通过内积计算得到。

除此之外，我们有

x_{i} = (x^{j} e_{j}) \cdot e_{i} = x^{j} (e_{i} \cdot e_{j}) = x^{j} g_{i j}

我们把 $g_{i j} = e_{i} \cdot e_{j}$ 称为度规张量(metric tensor)。

实际上协变/逆变分量的概念是随着基底的选取而产生的。每当我们选取了一直协变基底就对应着一组逆变基底，它们互为对偶基，且满足Kronecker性质。对于标量我们可以把它认为是0阶张量，也无所谓协变/逆变；矢量可以认为是1阶张量，在使用时需要指明是在哪个基底；而更高阶的张量同样需要指明哪些是协变哪些是逆变。

张量的运算

张量的并乘是最基本的运算之一。对于一个(m,n)阶张量和(p,q)阶张量，它们的并乘会得到一个(m+p, n+q)阶张量。

与并乘相对应的张量运算是缩并。缩并在一对协变/逆变基矢上进行运算，利用Kronecker符号使得运算后的张量阶数降低2。

利用并乘和缩并运算，我们可以定义张量的点积。对于两个张量 $T$ 和 $S$ ，它们的点积等于先进行并乘再进行缩并。

利用Levi-Civita符号我们还可以定义张量的叉积。

向量