Linear Algebra

发表于 | 更新于: | 分类于 | | 阅读数

3Blue1Brown & PCA

基础知识

行列式

  • 二阶行列式

  • $\begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{vmatrix} = a_{11}a_{22} - a_{12}a_{21} $

  • 三阶行列式

    • $\begin{vmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{vmatrix} = a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} -a_{13}a_{22}a_{31} - a_{23}a_{32}a_{11} - a_{33}a_{12}a_{21}$

  • 高阶行列式

    • 余子式$M_{ij}$

      • $n$阶行列式，把$a_{ij}$所在的行列删除，剩下的$n-1$阶行列式称记为$M_{ij}$

    • 代数余子式$A_{ij}$

      • $A_{ij} = (-1)^{i+j} M_{ij}$

    • $$
      |A| = \sum_{j = 1} ^ n a_{ij} A_{ij} \ \ (i = 1,2,…,n)
      \\
      |A| = \sum_{i = 1} ^ n a_{ij} A_{ij} \ \ (j = 1,2,…,n)
      $$

    • 逆序

      • 对于排列$i_1i_2…i_n$，若$(s,t)$并且$i_s > i_t , s>t$则称为一个逆序对，排列所有逆序对的数量称为逆序数，记作$\tau(i_1i_2…i_n)$。当逆序数为奇数则排列为奇排列，偶数则为偶排列

      • 行列式关于逆序数的求解公式：
        $$
        |A| = \sum_{j_1j_2…j_n} (-1)^{\tau(j_1j_2…j_n)}a_{1j_1} \cdot a_{2j_2}\cdot \cdot \cdot a_{nj_n}
        $$

  • 行列式性质

    • 行列互换，值不变，$|A| = |A^T|$
    • 行列式某行（列）元素全零，则行列式为零
    • 某行（列）有公因子$k$，可以提取至外部，$|A| = k|A’|$
    • 行列式某行（列）元素均是两个元素的和$a_{kj}+b_{kj} \ \ (j=1,…,n)$，可以拆成两个行列式的和，$|A| = |A’| + |A’’|$
    • 行列式两行（列）互换，值反号
    • 若某两行（列）对应值成比例，则行列式为零
    • 行列式某行（列）的$k$倍加到另一行（列），行列式值不变

  • 几个重要的行列式

    • 上（下）三角形行列式（主对角线行列式）利用逆序数求解行列式证明

      • $$
        \begin{vmatrix}
        a_{11} & a_{12}& … & a_{1n}\\
        0 & a_{22}& … & a_{2n} \\
        \vdots & \vdots& & \vdots\\
        0 & 0& … & a_{nn} \end{vmatrix} = \begin{vmatrix}
        a_{11} & 0 & … & 0\\
        a_{21} & a_{22}& … & 0 \\
        \vdots & \vdots& & \vdots\\
        a_{n1} & a_{n2} & … & a_{nn}
        \end{vmatrix} = \begin{vmatrix}
        a_{11} & 0& … & 0\\
        0 & a_{22}& … & 0 \\
        \vdots & \vdots& & \vdots\\
        0 & 0& … & a_{nn}
        \end{vmatrix} = \prod_{i=1}^n a_{ii}
        $$

    • 副对角线行列式逆序数行列式公式证明

      • $$
        \begin{vmatrix}
        a_{11} & a_{12} & … & a_{1,n-1} & a_{1n}\\
        a_{21} & a_{22} & … & a_{2,n-1} & 0\\
        \vdots & \vdots & & \vdots & \vdots \\
        a_{n1}& 0 & … & 0 & 0
        \end{vmatrix}=
        \begin{vmatrix}
        0 & … & 0 & a_{1n}\\
        0 & … & a_{2,n-1} & a_{2n}\\
        \vdots & & \vdots & \vdots \\
        a_{n1} & … & a_{n,n-1} & a_{nn}
        \end{vmatrix}=
        \begin{vmatrix}
        0 & … & 0 & a_{1n}\\
        0 & … & a_{2,n-1} & 0\\
        \vdots & & \vdots & \vdots \\
        a_{n1} & … & 0 & 0
        \end{vmatrix}= \\
        (-1)^\frac{n(n-1)}{2}a_{1n}\cdot a_{2,n-1} \cdot \cdot \cdot a_{n1}
        $$

    • 拉普拉斯展开式

      • $\mathbf{A}$为$m$阶矩阵，$\mathbf{B}$为$n$阶矩阵

      • $$
        \begin{vmatrix}
        \mathbf{A} & \mathbf{O}\\
        \mathbf{O} & \mathbf{B}
        \end{vmatrix}=
        \begin{vmatrix}
        \mathbf{A} & \mathbf{C}\\
        \mathbf{O} & \mathbf{B}
        \end{vmatrix}=
        \begin{vmatrix}
        \mathbf{A} & \mathbf{O}\\
        \mathbf{C} & \mathbf{B}
        \end{vmatrix}=
        |\mathbf{A}||\mathbf{B}|
        $$

      • $$
        \begin{vmatrix}
        \mathbf{O} & \mathbf{A}\\
        \mathbf{B} & \mathbf{O}
        \end{vmatrix}=
        \begin{vmatrix}
        \mathbf{C} & \mathbf{A}\\
        \mathbf{B} & \mathbf{O}
        \end{vmatrix}=
        \begin{vmatrix}
        \mathbf{O} & \mathbf{A}\\
        \mathbf{B} & \mathbf{C}
        \end{vmatrix}=
        (-1)^{mn}|\mathbf{A}||\mathbf{B}|
        $$

    • 范德蒙德行列式

      • $$
        \begin{vmatrix}
        1 & 1 & … & 1\\
        x_1 & x_2 & … & x_n\\
        x_1^2 & x_2^2 & … & x_n^2\\
        \vdots & \vdots & & \vdots\\
        x_1^{n-1} & x_2^{n-1} & … & x_n^{n-1}
        \end{vmatrix}=
        \prod_{1 \leq i < j \leq n} (x_j-x_i)
        $$

矩阵

由若干个行（列）向量拼成的

  • 矩阵的秩

    • 最高阶非零子式的阶数称为矩阵的秩，$k$阶子式为从左上角$a_{11}$到右下角$a_{kk}$所产生的矩阵
    • 本质就是组成该矩阵的线性无关向量的个数

  • 加减乘

    • 同形矩阵加减
    • 数乘$k\mathbf{A} = \mathbf{A}k$
    • 矩阵相乘，$c_{ij} = \sum_{k=1}^s a_{ik}b_{kj}$。 $s \times n$得到的结果是$m \times n$的矩阵，矩阵的乘法本质是左边矩阵通过右边矩阵变换成为一个新的矩阵。

  • 伴随矩阵

    • 代数余子式的转置称为伴随矩阵，只有方阵才有伴随矩阵，记为$A^*$
    • $AA^* = A^*A = |A|E$
    • $A^{−1}=\frac{1}{|A|} A^*$，若存在$A^{-1}$
    • $(A ^ *)^{-1}=(A^{-1})^ *=\frac{1}{|A|}A$
    • $|A^*|=|A|^{n-1}$
    • $(kA) ^ *=k^{n-1}A ^ *$

  • 矩阵的逆

    • $A$为$n$阶方阵，$\mathbf{AB} = \mathbf{BA} = \mathbf{E} $，$\mathbf{B}$为$\mathbf{A}$的逆矩阵，记作$\mathbf{A^{-1}}$
    • 充要条件：$|A| \neq 0$
    • 若A，B同阶可逆
      • $(AB)^{-1} = B^{-1}A^{-1}$
      • $(A^{T})^{-1} = (A^{-1})^{T}$
    • A，B均是可逆方阵
      • $\begin{bmatrix}
        A & O\\
        O & B
        \end{bmatrix}^{-1} =
        \begin{bmatrix}
        A^{-1} & O\\
        O & B^{-1}
        \end{bmatrix}$
      • $\begin{bmatrix}
        O & A\\
        B & O
        \end{bmatrix}^{-1}=
        \begin{bmatrix}
        O & B^{-1}\\
        A^{-1} & O
        \end{bmatrix}$
    • 对于矩阵$\begin{bmatrix}
      a & b\\
      c & d
      \end{bmatrix}$，逆矩阵为$\frac{1}{ad-bc}\begin{bmatrix}
      d & -b\\
      -c & a
      \end{bmatrix}$

线性代数

向量

在计算机中，向量往往是对于数据的抽象表示。

  • 向量的加法可以理解成向量的移动，向量的数乘可以理解为向量的缩放
  • 正交向量内积为0，$(\alpha, \beta ) = \alpha ^ T \beta = 0$
  • 向量组$\alpha _1, \alpha _2, … \alpha _s$满足自内积为1，反之内积为0，则称为标准或单位正交向量
  • 施密特正交化
    • 线性无关向量组$\alpha_1, \alpha_2$
    • $\beta_1 = \alpha_1$
    • $\beta_2 = \alpha_2 - \frac{(\alpha_2, \beta_1)}{(\beta_1, \beta_1)} \beta_1$
    • 单位化：$\eta_1 = \frac{\beta_1}{|\beta_1|}, \eta_2 = \frac{\beta_2}{|\beta_2|}$

向量的线性变换

向量按照矩阵的坐标变换变成了另一种样式，这里的坐标变换改变x轴y轴，原点不变，所有网格线仍然等距且平行，对于更高维度的坐标系也成立。

可以利用基向量来描述线性变换

通过记录两个基向量$\hat{i}, \hat{j}$，就可以得到变换后的其他向量。

已知向量$\overrightarrow v = \begin{bmatrix} -1 \\ 2\end{bmatrix}$

变换之前的$\hat{i},\hat{j}$分别为：

$\hat{i} = \begin{bmatrix} 1 \\ 0\end{bmatrix} \ \ \ \hat{j} = \begin{bmatrix} 0 \\ 1 \end{bmatrix} \ \ \ \overrightarrow{v} = -1 \hat{i} + 2 \hat{j}$

假设变换之后的$\hat{i}, \hat{j}$如下，则

$\begin{aligned}
\hat{i} = \begin{bmatrix}
1 \\
-2
\end{bmatrix} \\
\hat{j} = \begin{bmatrix}
3 \\
0
\end{bmatrix} \\
\vec{v} = -1\hat{i} + 2 \hat{j} &= \begin{bmatrix}
5 \\
2
\end{bmatrix} \\
&= -1\begin{bmatrix}
1 \\
-2
\end{bmatrix} + 2 \begin{bmatrix}
3 \\
0
\end{bmatrix} \\
&= \begin{bmatrix}
1 & 3 \\
-2 & 0
\end{bmatrix} \begin{bmatrix}
-1 \\
2
\end{bmatrix} \\
&= \begin{bmatrix}
5 \\
2
\end{bmatrix} \\
\end{aligned}
$

写成矩阵形式则为$\begin{bmatrix}
1 & 3 \\
-2 & 0
\end{bmatrix} \begin{bmatrix}
-1 \\
2
\end{bmatrix}$

alt

alt

如果变换后的$\hat{i}, \hat{j}$是线性相关的，说明变换后的坐标为一维空间，相当于两个基向量重合了

线性变换的复合与矩阵乘法

alt

两个矩阵的乘积需要从右向左读，类似函数的复合。

alt

这样两个矩阵的乘积就对应了一个复合的线性变换，最终得到对应变换后的$\hat{i}, \hat{j}$

alt

alt

更一般的情形

alt

复合乘积的顺序会影响结果，即$\mathbf{M_1 M_2} \neq \mathbf{M_2 M_1}$

满足结合律(Associativity)：$(AB)C = A(BC)$因为变换都是从右至左的，添加括号完全没有影响变换

三维空间的线性变换

与二维的变换类似，三维考虑$\hat{i} , \hat{j}, \hat{k}$三组基向量的变换过程。由此引申为$n$维矩阵变换。

行列式的本质

  • 行列式的本质是计算线性变化对空间的缩放比例，具体一点就是，测量一个给定区域面积增大或减小的比例。

  • 单位面积的变换代表任意区域的面积变换比例。

alt

alt

alt

  • 行列式的值表示缩放比例
  • 当行列式值为零，说明围成得面积（体积）为零，导致了降维
  • 对于行列式值为负数的解释

alt

  • 三维空间的行列式类似，它的单位是一个单位1的立方体。

  • 三位空间的线性变换，可以使用右手定则判断三维空间的定向。如果变换前后都可以通过右手定则得到，那么他的行列式就是正值，否则为负值。

alt

alt

  • $det(M_1 M_2) = det(M_1)det(M_2)$ 复合缩放比例等于两个分比例的积

逆矩阵

矩阵变换的逆过程

当矩阵对应行列式为0说明已经降维，此时逆变换无效，即无逆变换

秩

表示变换空间后的维度（对应线性无关向量数），满秩列空间维数和空间维数相等。

核

对于所有矩阵变换来说，如果变换后落到零向量$\vec{v} = [0, …, 0]$中，我们把变换前的该向量组称为零空间（Null space）或核（Kernel），即$A \vec{x} = [0, … ,0]$的解集合$\vec{x}$，很明显此时矩阵$A$将空间进行了降维。

点积

对于两个维度相同的向量，他们的点积计算为：$\begin{bmatrix}1 \\ 2\end{bmatrix} ^ T\cdot\begin{bmatrix} 3 \\ 4\end{bmatrix}=1\cdot3+2\cdot4=11$

点积的几何解释是将一个向量向一个向量投影，然后两个长度相乘，如果为负数则表示反向。

要证明点积的上述计算原理，需要了解$L(\vec{v} + \vec{w}) = L(\vec{v}) + L(\vec{w}) \\ L(c \vec{v} ) = c L(\vec{v})$其中L函数为线性变换

重新认识一下这种运算，在二维空间中沿着某方向放置一条数轴，数轴的基向量设为$\hat{u}$。我们将空间中的向量投影到这条直线上，可表明这个操作是线性的，因为它满足等距分布的点在投影之后仍是等距分布。

alt

根据这个投影，我们定义了一个从二维向量到数的线性变换（需要强调的是，尽管这条数轴放置在二维空间中，但是这个变换是一个从二维向量到数的函数，输出的是一个数，而向量$\hat{u}$是一个二维向量，只是恰好落在数轴的方向），下一步就是得到其对应的1x2矩阵（投影矩阵），矩阵的列向量应该是向量$\hat{i}$和$\hat{j}$经过线性变换后得到的数值。

注意向量$\hat{u}$和向量$\hat{i}$都是单位向量，从对称性可知向量$\hat{i}$向$\hat{u}$投影的长度，等于向量$\hat{u}$在向量$\hat{i}$方向上的投影长度，而$\hat{u}$向$\hat{i}$方向的投影就是$\hat{u}$的横坐标，也就等于向量$\hat{i}$在数轴上投影得到的数。同样的过程也可对$\hat{j}$进行操作。以此得到投影矩阵的两个元素就是向量$\hat{u}$的两个坐标，即线性变换为$[\hat{u} _x, \hat{u}_y]$ 。对偶向量为$\hat{u} = \begin{bmatrix} \hat{u}_x \\ \hat{u}_y \end{bmatrix}$

叉积

$\vec{v} \times \vec{w} = \vec{ p}$ 的数值上等于平行四边形面积，当$\vec{v}$在$\vec{w}$右侧，数值为正数，$\hat{i} \times \vec{j} = +$

真正的叉积是通过两个三维向量$\vec{v}$和$\vec{w}$，生成一个新的三维向量$\vec{u}$，这个向量垂直于向量$\vec{v} \vec{w}$所围成的平面，长度等于他们的面积。

在数值和几何角度理解参阅click this

基变换

  • 不同空间网格定义相同向量有不同的表示方法，这也就是前文所讲的线性变换的原理

  • 线性变换数值上是变换后网格的声明的向量到直角坐标系的向量的改变，逆变换相反

特征向量和特征值

  • 当一个矩阵变换时，如果有一些向量位置不变（可能不存在），只是长度改变成原来的若干倍，即$A \vec{v} = \lambda \vec{v}$时，将$\vec{v}$称为特征向量；$\lambda$称为特征值。
  • $\begin{aligned} A \vec{v} = \lambda I \vec{v} \\ ( A - \lambda I ) \vec{v} = \vec{0} \end{aligned} $ ，由之前的核理论，此时应该有$det(A - \lambda I) = 0 $
  • 相似
    • 对于$A,B$两个n阶方阵，如果有$P^{-1} A P = B$，则称为A相似于B（$A \sim B$）
    • 实质上就是就是线性变换$A$，在$P$的作用下到了另一个坐标系的变换，再通过$P^{-1}$回到直角坐标系和在直角坐标系的$B$变换一致。也就是说两者只是在不同空间系下的相同变换
    • 相似对角化
      • $P^{-1} A P = \Lambda$，其中$\Lambda$为对角矩阵，说明在$P$空间变换是只在变更基向量的长度
      • $P$为将上述$\lambda$的解代入$(A - \lambda I) \vec{v} = \vec{0}$所得到所有特征向量$\vec{v}$，再组建成一个矩阵$P$，称为对角化
      • $A^n = P \Lambda P^{-1} P \Lambda P^{-1} … P \Lambda P^{-1} = P \Lambda ^ {n} P^{-1} $

PCA降维

详细推导click this

假设一组数据$X = \begin{pmatrix}
a_1 & a_2 & a_3 & … & a_m \\
b_1 & b_2 & b_3 & … & b_m
\end{pmatrix}$，均值处理为0（即将每个字段减去字段的平均值，几何上就是将坐标轴移动到$(\bar{a}, \bar{b})$），$cov(a,b) = \frac{1}{m} \sum_{i=1}^m a_i b_i $，将之变成一个矩阵上来，构造$\frac{1}{m} X X^{T}$

需要一个线性变换使得$\frac{1}{m} X X^{T}$变成对角矩阵，方差最大，协方差最小为0，此时就是求出$P$

此时的$P$就是$\frac{1}{m} X X^T$特征向量组成的矩阵，之后用$P$的第一列乘$X$便得到一组一唯向量

PCA代码如下：

1
2
3
4
5
6
7
8
9
10
import numpy as np

if __name__  == "__main__":
    X = np.array([[-1, -2], [-1, 0], [0, 0], [2, 1], [0, 1]], dtype= float)
    m, n = X.shape
    Cov = X.T.dot(X) / m
    lam, c = np.linalg.eig(Cov)
    P = c.T
    PCA = P[0].dot(X.T)
    print(PCA)
thanks!