【不周山之数据科学】基础知识 线性代数

本文主要介绍线性代数中与机器学习相关的重要概念,方便不懂的时候进行查阅。


更新历史

  • 2017.03.16: 并入【不周山之数据科学】系列
  • 2017.02.18: 完成初稿
  • 2017.02.08: 开始编写

写在前面

线性代数是是代数学的一个分支,主要处理线性关系问题,即数学对象之间的关系是以一次形式来表达的。线性关系问题简称线性问题,解线性方程组的问题是最简单的线性问题。

很多实际问题的处理,最后往往归结为线性问题,它比较容易处理。因此,线性代数在许多领域都有着广泛的应用,是一门基本且重要的学科。

向量 Vector

向量的可以用列的形式表示,但是为了书写和打印方便,一般会用圆括号括起来,转换为行的形式。如:$\mathbf{v}=(v_1,v_2)$。

若有向量 $\mathbf{v}=(v_1,v_2),\; \mathbf{w}=(w_1, w_2)$ 和常数 $c, d$,则

  • 向量相加 $\mathbf{v+w}=(v_1+w_1,v_2+w_2)$
  • 向量数乘 $c\mathbf{v}=(cv_1,cv_2)$
  • $c\mathbf{v}+d\mathbf{w}$ 是向量 $\mathbf{v}$ 和 $\mathbf{w}$ 的线性组合
  • $\mathbf{v\cdot w}$ 是向量 $\mathbf{v}$ 和 $\mathbf{w}$ 的内积(点积),值为 $\mathbf{v\cdot w}=\sum v_iw_i$,显然 $\mathbf{v\cdot w}=\mathbf{w\cdot v}$
  • $\Vert \mathbf{v} \Vert$ 是向量 $\mathbf{v}$ 的长度,$\Vert\mathbf{v}=\sqrt{\mathbf{v\cdot v}}\Vert$
  • 单位向量 $\mathbf{u}$ 的长度为1,$\mathbf{u}=\frac{\mathbf{v}}{\Vert\mathbf{v} \Vert}$ 是与 $\mathbf{v}$ 同方向的单位向量

如果 $\mathbf{v}$ 和 $\mathbf{w}$ 是非零向量,则有

$$\frac{\mathbf{v\cdot w}}{\Vert\mathbf{v} \Vert \Vert\mathbf{w} \Vert}=cos\;\theta$$

据此我们可以得到两个重要不等式:

  • $|\mathbf{v\cdot w}| \le \Vert\mathbf{v}\Vert \Vert\mathbf{w} \Vert$
  • $\Vert\mathbf{v+w}\Vert \le \Vert\mathbf{v}\Vert + \Vert\mathbf{w} \Vert$

有关向量的线性表示,下面的说法是等价的:

  • 向量 $b$ 能由向量组 $\mathbf{a_1,a_2,\cdots,a_m }$ 线性表示
  • 线性方程组 $x_1\mathbf{a_1}+x_2\mathbf{a_2}+\cdots+x_m\mathbf{a_m}=\mathbf{b}$ 有解
  • 秩相同 $R(\mathbf{a_1,a_2,\cdots,a_m }) = R(\mathbf{a_1,a_2,\cdots,a_m,b})$,因为 $\mathbf{b}$ 可以被向量组 $\mathbf{a_1,a_2,\cdots,a_m }$ 线性表示

如果向量组 $A: \mathbf{a_1,a_2,\cdots,a_m }(m \ge 2)$ 线性相关,下面说法等价:

  • 向量组 $A$ 至少存在一个向量是其余 $m-1$ 个向量的线性组合
  • 线性方程组 $x_1\mathbf{a_1}+x_2\mathbf{a_2}+\cdots+x_m\mathbf{a_m}=0$ 有非零解
  • $\mathbf{a_1,a_2,\cdots,a_m }$ 的秩小于向量的个数 $m$,即 $R(\mathbf{a_1,a_2,\cdots,a_m })<m$

如果向量组 $A: \mathbf{a_1,a_2,\cdots,a_m }(m \ge 2)$ 线性无关,下面说法等价:

  • 线性方程组 $x_1\mathbf{a_1}+x_2\mathbf{a_2}+\cdots+x_m\mathbf{a_m}=0$ 只有零解
  • $\mathbf{a_1,a_2,\cdots,a_m }$ 的秩等于向量的个数 $m$,即 $R(\mathbf{a_1,a_2,\cdots,a_m })=m$

这里我们可以看到向量、方程组和矩阵问题实际上是可以相互转换的。但需要注意向量组等价,可得矩阵等价,但矩阵等价不能得到向量组等价

行列式 Determinant

线性代数中最重要的内容就是行列式和矩阵,虽然表面上看,行列式和矩阵不过是一种符号或速记,但从数学史上来看,优良的数学符号和生动的概念是数学思想产生的动力和钥匙。

行列式最初用于求解线性方程,行列式是否为零可用来判定一个线性方程是否有解。

行列式的三种变换:

  • 互换某两行(列),记为 $r_i \leftrightarrow r_j\;(c_i \leftrightarrow c_j)$
  • 提出某一行(列)的公因子,记为 $r_i \div k\;(c_i \div k)$
  • 把某一行(列)的 $k$ 倍加到另一行(列),记为 $r_i+kr_j\;(c_i+kc_j)$

计算行列式最常用的一种方法就是利用变换 $r_i+kr_j\;(c_i+kc_j)$ 和 $r_i \leftrightarrow r_j\;(c_i \leftrightarrow c_j)$,把行列式转化为上三角形行列式,从而算得行列式的值。

行列式为零,要么是两行(列)相同,要么是两行(列)成比例。

行列式按某行展开可以按任一行展开,而一行元素乘以另一行对应元素的代数余子式,其和为零。综合起来是:

$$a_{k1}A_{i1}+a_{k2}A_{i2}+ \cdots + a_{kn}A_{in}=\sum_{s=1}^n a_{ks}A_{is}=\begin{cases}D&, k=i\\ 0&,k\ne i\end{cases}$$

另外 $D^T=D$ 也是行列式的性质,这里提一下。

矩阵 Matrix

若有矩阵 $A$ 和矩阵 $B$,那么

  • 两个大小相同的矩阵才可以相加,记为 $A+B$,是对应位置的元素进行相加
  • 如果矩阵 $A$ 有 $n$ 列且矩阵 $B$ 有 $n$ 行,这两个矩阵可以相乘得到 $AB$

一个 $m \times n$ 的矩阵与一个 $n\times p$ 的矩阵相乘所需的乘法次数是 $mnp$ 次,一般我们会采用动态规划的方法来对乘法进行优化。

矩阵加法满足:

  • 交换率 $A+B=B+A$
  • 分配率 $c(A+B)=cA+cB$
  • 结合律 $A+(B+C)=(A+B)+C$

矩阵乘法满足:

  • 左分配率 $C(A+B)=CA+CB$
  • 右分配率 $(A+B)C=AC+BC$
  • 结合律 $A(BC)=(AB)C$

矩阵 $A$ 可逆当且仅当存在矩阵 $A^{-1}$,使得 $A^{-1}A=I$ 和 $AA^{-1}=I$,其中 $A^{-1}$ 称为 $A$ 的逆矩(inverse)阵。如果 $A$ 不可逆,称 $A$ 为奇异(singular)矩阵。

转置(transpose)是把一个矩阵行与列进行互换,如对于矩阵 $A$ 转置为 $(A^T)_{ij}=A_{ji}$。

对于矩阵 $A$ 和 $B$,$(A+B)^T=A^T+B^T,\;(AB)^T=B^TA^T,\;(A^{-1})^T=(A^T)^{-1}$

如果对于矩阵 $A$ 有 $a_{ij}=a_{ji}$,则称 $A$ 为对称矩阵。对称矩阵 $A$ 可分解为 $A=LDL^T$

对任意矩阵 $R$,$R^TR$ 和 $RR^T$ 都是对称矩阵且它们对角线上元素非负,大多数科学问题都是从一个矩阵 $R$ 开始,以 $R^TR$ 或 $RR^T$ 结束。

对于非零矩阵 $A$,$A^2$ 可以是零矩阵,但 $A^TA$ 不可能是零矩阵。

求解线性方程组是线性代数的核心问题。

求解 $A\mathbf{x}=\mathbf{b}$ 是寻找一个特定组合来产生 $\mathbf{b}$,其中 $\mathbf{A}$ 被称为系数矩阵。这个求解的过程,从另外一个角度来看是寻找多条线(平面或超平面)的交点。

每个超级计算机都会拿求解 $A\mathbf{x}=\mathbf{b}$ 来测试速度,计算机编程中应该直接进行消元或者置换,而不应该采用矩阵相乘来实现,因为矩阵相乘的方式带来更多冗余计算。

$n$ 阶矩阵 $A$,可以认为下列说法是等价的:

  1. $\mathbf{A}$ 是满秩矩阵
  2. $\mathbf{A}$ 的标准形是 $E$
  3. $\mathbf{A}$ 可以表达为有限个初等矩阵的乘积
  4. 齐次线性方程组 $Ax=0$ 只有零解
  5. 非齐次线性方程组 $Ax=b$ 有唯一解

对称矩阵

对称矩阵是线性代数中(无论理论还是实践)最重要的矩阵。

  • 实对称矩阵的特征向量一定可以选为相互正交(不同特征值对应的特征向量相互正交),而特征值一定是实数,同时特征值的符号与主元符号相符
  • 所有实对称矩阵都可以对角化,对角化变为 $A=Q\Lambda Q^T$,其中 $Q$ 是正交矩阵
  • 每个方阵都可以分解为 $A=QTQ^{-1}$,如果A的特征值是实数则存在实数矩阵 $Q$ 和 $T$

正定矩阵 Positive Definite Matrix

  • 对任何非零向量 $\mathbf{x}$ 都有 $\mathbf{x}^TA\mathbf{x}>0$ 时,我们称 $A$ 为正定矩阵
  • 矩阵 $A$ 正定当且仅当它的特征值或主元都为正数,正定矩阵的对角线上不会出现零
  • 如果 $A$ 与 $B$ 都对称正定,则 $A+B$ 也对称正定
  • 如果 $R$ 的列向量线性无关,则 $A=R^TR$ 不但是对称矩阵,而且正定
  • 椭圆 $\mathbf{x}^TA\mathbf{x}=1$ 的轴沿着 $A$ 的特征向量方向,轴长为 $\frac{1}{\sqrt \lambda}$

相似矩阵 Similar Matrix

  • 如果存在任一矩阵 $M$ 使得 $B=M^{-1}AM$,则 $B$ 与 $A$ 相似,从定义上就可以看出相似是可逆的
  • 没有被 $M$ 改变的有:特征值、迹、行列式、秩和无关特征向量个数
  • 被 $M$ 改变的有:特征向量、NULL空间、列空间、行空间、左NULL空间和奇异值;
  • 如果 $A$ 有 n 个线性无关的特征向量,则 $A$ 与 $\Lambda$ 相似且 $M=S$,这里 $S$ 为特征向量矩阵,并且$AS=SA,\;S^{-1}AS=\Lambda$(其实这也就是对角化的过程)

向量空间和子空间

空间 $R^n$ 包含任何含有 $n$ 个实数元素的列向量 $\mathbf{v}$,我们可以把 $R^n$ 中任意向量加在一起,也可以为任何向量乘上一个数字 $c$,得到的结果都在这个空间中。

  • 对于一个集合,如果集合中元素对加法和数乘(即向量乘以一个常数)是封闭的,那么这个集合构成一个空间。
  • 只包含一个零向量的空间称为空间 $Z$

一个向量空间的子空间(Subspace)满足如下条件:如果 $\mathbf{v}$ 和 $\mathbf{w}$ 都在这个子空间中,则 $\mathbf{v+w}$ 与 $c\mathbf{v}$ 也在这个子空间中,而他们的线性组合 $c\mathbf{v}+d\mathbf{w}$ 也在子空间中。

  • 矩阵 $A$ 列向量的线性组合构成它的列空间,一般记为 $C(A)$,当 $\mathbf{b}$ 在 $C(A)$ 时 $A\mathbf{x}=\mathbf{b}$ 有解。
  • 矩阵 $A$ 的 NULL 空间包括满足 $A\mathbf{x}=0$ 的所有 $\mathbf{x}$,记为 $N(A)$
  • 一个矩阵的行空间和它的 NULL 空间相互正交
  • 矩阵的秩是矩阵主元的数量,可以记为 $r$,它不但是行向量的维度还是列向量的维度,而且 NULL 空间的维度是列空间的维度减去 $r$
  • 对于矩阵 $A$ 和 $B$,存在结论 $rank(AB) \le min(rank(A),rank(B))$

$A\mathbf{x}=\mathbf{b}$ 的全部解

  • 求解 $A\mathbf{x}=\mathbf{b}$ 可以看做求以 $A$ 列向量为坐标轴时 $\mathbf{b}$ 的坐标值 $\mathbf{x}$
  • $A\mathbf{x}=\mathbf{b}$ 可解当且仅当最后 $m-r$ 个等式变成 $0=0$
  • $A\mathbf{x}=\mathbf{b}$ 的所有解是满足 $A\mathbf{x}=\mathbf{b}$ 的一个特解 $x_p$ 加上 $A\mathbf{x}=0$
  • 根据秩 $r$ 的取值,线性方程组有如下四种可能(其中 $m,n$ 为行数、列数)
    • $r=m,r=n$,方阵且可逆,$A\mathbf{x}=\mathbf{b}$ 有且只有一个解
    • $r=m,r<n$,矮又宽型,$A\mathbf{x}=\mathbf{b}$ 有无穷多解
    • $r<m,r=n$,高又瘦型,$A\mathbf{x}=\mathbf{b}$ 有一个解或无解
    • $r<m,r<n$,行和列都不满秩,$A\mathbf{x}=\mathbf{b}$ 有无穷多解或无解

一组向量 $\mathbf{v_1,\cdots,v_n}$ 线性无关,当且仅当 $x_1\mathbf{v_1}+x_2\mathbf{v_2}+\cdots+x_n\mathbf{v_n}=\mathbf{0}$ 中的 $x$ 全为零。

  • 一组向量的线性组合所构成的空间是这组向量所张成的空间,空间中线性无关且能张成这一空间的一组向量可以作为这一空间的基。
  • 所有基包含向量个数相同,我们把这个数称为该空间的维度,矩阵 $A$ 列向量所张成空间的维度等于矩阵的秩
  • 空间中每个向量表示为一组基线性组合是唯一的
  • 空间 $Z$ 只包含零向量,这一空间的维度为 0,空集构成此空间的一组基
  • 对于空间 $V$ 和 $W$ 有 $dim(V)+dim(W)=dim(V\cap W)+dim(V\cup W)$

最小二乘法

求解$A\mathbf{x}=\mathbf{b}$时经常会遇到无解的情况,这个时候我们就需要近似找到一个最小二乘解(也就是让误差最小的解),一般来说可以直接对 $\Vert A\mathbf{x-b}\Vert ^2$ 求导并令其等于 0 就可以求的最小二乘解(有最小的平方误差)

注:一般这里的 $A$ 的列向量需要线性无关,这样才能保证 $A^TA$ 是可逆的,否则有多个解。

特征值与特征向量

矩阵乘以向量,在功能上相当于把一个向量变换为另一个向量。一个矩阵的特征向量是这样一种特定的向量,它经过这种变换后方向不变(或正好相反),只发生长度上的伸缩,特征值则反映了特征向量的伸缩倍数(及方向)。

用公式表示为:

$$\mathbf{Ax}=\lambda \mathbf{x}$$

  • 满足上式的向量 $\mathbf{x}$ 称为矩阵 $\mathbf{A}$ 的特征向量
  • 数 $\lambda$ 反应了伸缩的倍数及方向,称为与 $\mathbf{x}$ 对应的特征值

一些重要性质

设 $\lambda_1,\lambda_2,\cdots,\lambda_n$ 是 n 阶矩阵 $\mathbf{A}$ 的 $n$ 个特征值,则:

  • $\lambda_1,\lambda_2,\cdots,\lambda_n=a_{11}+a_{22}+\cdots+a_{nn}$
  • $\lambda_1\lambda_2\cdots\lambda_n=|\mathbf{A}|$
  • 当对 $A$ 平方时特征向量不会发生改变,而特征值会被平方,另外拥有特殊性质的矩阵会有特殊的特征值与特征向量
  • 对一个矩阵进行消元或者行变换都会改变这个矩阵的特征值
  • n 个特征值的乘积等于矩阵的行列式的值,n 个特征值的和等于矩阵的迹,矩阵的迹是矩阵对角线元素之和

特征向量之间的关系:

  • 矩阵 $\mathbf{A}$ 的属于不同特征值的特征向量是线性无关的
  • 设 $\lambda_1,\lambda_2,\cdots,\lambda_n$ 是矩阵 $\mathbf{A}$ 的 $m$ 个互异特征值,对应于 $\lambda_i\;(i=1,2,\cdots,m)$ 的线性无关的特征向量有 $r_i$ 个,则→所有这些特征向量构成的向量组是线性无关的
  • 对称矩阵 $\mathbf{A}$ 的属于不同特征值的特征向量是两两相交的

特征值所对应的特征向量的个数:

  • 每个特征值都对应着至少一个特征向量
  • $k$ 重特征值对应的线性无关的特征向量的个数不超过 $k$
  • 若 $A$ 为对称矩阵,则 $A$ 的每个特征值对应的线性无关特征向量的个数恰好等于该特征值的重数

奇异值分解 Singular Value Decomposition

奇异值分解在线性代数中非常重要,它可以对角化任意矩阵,有很多实际用途,如降维等。把秩为 $r$ 的 $A$ 通过 SVD 分解为 $U\Sigma V^T$,$\Sigma$ 对角线上是奇异值 $\sigma_1 \ge \sigma_2 \ge \cdots \sigma_r > 0$:

  • $\sigma_1^2,\cdots,\sigma_r^2$ 是 $AA^T$ 或 $A^TA$ 特征值(两者特征值相同)
  • $U$ 是 $AA^T$ 的特征向量,前 $r$ 列来源于 $A$ 的列空间,后 $m−r$ 列来源于 $N(A^T)$
  • $V$ 是 $A^TA$ 的特征向量,$r$ 列是 $A$ 的行空间,后$n−r$ 列来源于 $N(A)$
  • $\Sigma$ 对角线上奇异值从小到大排列,奇异值越大对整个矩阵的重要性也越大
  • $U$ 和 $V$ 的列向量分别是输出空间和输入空间的坐标轴

对任意实数方阵 $A$ 根据 SVG 且 $V^TV$ 分解有

$$A=U\Sigma V^T=UV^TV\Sigma V^T=(UV^T)(V\Sigma V^T)=(Q)(H)$$

其中 $Q$ 是正交阵,$H$ 是对称半正定的,如果 $A$ 可逆则 $H$ 是对称正定的。这个过程便是极分解,它把线性变换中旋转(在 $Q$ 中)与伸展(在 $H$ 中)分开

行列式 Determinant

方阵 $A$ 主元的乘积称为这个方阵的行列式,它包含大量关于 $A$ 的信息,一般记为 $det\;A$ 或 $|A|$,我们需要了解关于行列式的十个性质:

  1. $n\times n$ 单位阵的行列式为 1
  2. 当两行交换时行列式符号会改变
  3. 行列式是分别关于每一行的线性函数
  4. 如果矩阵中两行相等则行列式等于 0
  5. 从一行中减去另外一行的若干倍整个行列式不变
  6. 如果矩阵中有一行都等于零则行列式等于 0
  7. 如果矩阵是对焦矩阵则行列式等于对角元素的乘积
  8. 如果矩阵奇异则行列式等于 0,非奇异时行列式不为 0
  9. $|AB|=|A|\;|B|$
  10. $|A^T|=|A|$

行列式是分别关于每一行的线性函数。例如:在其他行不变的情况下,当第一行数乘t时行列式数乘t,当第一行相加是行列式相加。

应用

  • 工程问题常常产生对称矩阵 $K$,它通常是正定的,一般来源于 $K=A^TA$ 或 $K=A^TCT$,矩阵 $C$ 往往是对角的,包含一些正的物理常数
  • 图关联矩阵告诉我们 $m$ 条边与 $n$ 个结点的连接情况,通常情况下 $m>n$,关联矩阵的元素是 -1、0 或者 1。对关联矩阵进行消元就是把对应的图变成树(树是没有闭环的图)
  • 如果一个矩阵 $A$ 每个元素都是非负的且每一列的和都为 1,则它是一个马尔科夫矩阵
    • 如果 $A$ 是一个正马尔科夫矩阵($a_{ij}>0$),则 $\lambda_1=1$ 比其它特征值都大,与之对应的特征向量 $x_1=1$ 是稳态
    • 马尔科夫矩阵 $A$ 的第二大特征值的绝对值 $|\lambda_2|$ 控制收敛到稳态的收敛速度,非正马尔科夫矩阵中可能有 $|\lambda_2|=1$,则不存在稳态
  • 假设现在有一代价向量 $\mathbf{c}$,线性规划是在满足 $A\mathbf{x}=\mathbf{b}$ 与 $\mathbf{x} \ge 0$ 的情况下,使得 $\mathbf{c \cdot x}$最小;上述问题的对偶问题是在满足 $A^T\mathbf{y} \le \mathbf{c}$情况下,使得 $\mathbf{b \cdot y}$最大,令代价 $\mathbf{c \cdot x^*}$ 最小等价于 $\mathbf{b \cdot y^*}$ 最大
  • 校正矩阵(Correct Matrix)、均值(Mean)、方差(Variance)、协方差矩阵(Covariance Matrix)、主成分分析(Principal Component Analysis)

参考链接

捧个钱场?