小学的 “算术”
中学的 “代数”
为什么 “代数” 比 “算术” 更难?
“解决问题的方法与步骤。”
和 “算术” 和 “代数” 不同,算法是 “
线性算术
线性代数
线性代数中的算法
向量 (vector): 一个 $n$ 维的数组,通常
$$ \vec{x} = \begin{bmatrix} 3 \\ 4 \\ 1 \end{bmatrix}\qquad \vec{y} = \begin{bmatrix} 1.5 \\ -2 \end{bmatrix} $$
向量的算术:(加法) 每个维度分别相加;(数乘) 每个维度分别乘以同一个数字
$$ \begin{bmatrix} 3 \\ 4 \\ 1 \end{bmatrix} + \begin{bmatrix} -1 \\ 0 \\ 1.5 \end{bmatrix} = \begin{bmatrix} 2 \\ 4 \\ 2.5 \end{bmatrix}\qquad 3 \begin{bmatrix} 3 \\ 4 \\ 1 \end{bmatrix} = \begin{bmatrix} 9 \\ 12 \\ 3 \end{bmatrix} $$
这似乎也……太简单了吧?
“一个数组”
“起点是原点的箭头”
“坐标系中的一个点”
为什么是
什么运算 ($\rightarrow$) 可以把一个向量 (箭头) 变成另一个?
$$ \begin{bmatrix} 0 \\ 0 \end{bmatrix} \textcolor{blue}\rightarrow \begin{bmatrix} 0 \\ 0 \end{bmatrix} \qquad \begin{bmatrix} 1 \\ 0 \end{bmatrix} \textcolor{blue}\rightarrow \begin{bmatrix} 2 \\ 0 \end{bmatrix} \qquad \begin{bmatrix} 2 \\ -1 \end{bmatrix} \textcolor{blue}\rightarrow \begin{bmatrix} 4 \\ -2 \end{bmatrix} $$
$$ \begin{bmatrix} 1 \\ 0 \end{bmatrix} \textcolor{red}\rightarrow \begin{bmatrix} 3 \\ 4 \end{bmatrix} \qquad \begin{bmatrix} 0 \\ 1 \end{bmatrix} \textcolor{red}\rightarrow \begin{bmatrix} 0 \\ 2 \end{bmatrix} \qquad \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} + \begin{bmatrix} 0 \\ 1 \end{bmatrix} \textcolor{red}\rightarrow \begin{bmatrix} 3 \\ 6 \end{bmatrix} $$
$$ \begin{bmatrix} x \\ y \end{bmatrix} = x \begin{bmatrix} 1 \\ 0 \end{bmatrix} + y \begin{bmatrix} 0 \\ 1 \end{bmatrix} \textcolor{red}\rightarrow x \begin{bmatrix} 3 \\ 4 \end{bmatrix} + y \begin{bmatrix} 0 \\ 2 \end{bmatrix} $$
每个坐标轴分别做出的拉伸 + 旋转
$$ \begin{bmatrix} 1 \\ 0 \end{bmatrix} \textcolor{red}\to \begin{bmatrix} a \\ b \end{bmatrix} \qquad \begin{bmatrix} 0 \\ 1 \end{bmatrix} \textcolor{red}\to \begin{bmatrix} c \\ d \end{bmatrix} \qquad $$
$$ \left( \begin{bmatrix} x \\ y \end{bmatrix} = x \begin{bmatrix} 1 \\ 0 \end{bmatrix} + y \begin{bmatrix} 0 \\ 1 \end{bmatrix} \right) \textcolor{red}\rightarrow x \begin{bmatrix} a \\ b \end{bmatrix} + y \begin{bmatrix} c \\ d \end{bmatrix} $$
所以我们只要考虑 $(0,0)-(1,1)$ 的单位方格 “变成” 了什么
如何表示线性变换操作 “$\rightarrow$”?
$$ \begin{bmatrix} a & c \\ b & d \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} ax + cy \\ bx + dy \end{bmatrix} $$
$$ \begin{bmatrix} a & d & g \\ b & e & h \\ c & f & i \end{bmatrix} \begin{bmatrix} x \\ y \\ z \end{bmatrix} = \begin{bmatrix} ax + dy + gz \\ bx + ey + hz \\ cx + fy + iz \end{bmatrix} $$
$$ \begin{array}{rcl} & & \begin{bmatrix} a & d & g \\ b & e & h \\ c & f & i \end{bmatrix} \begin{bmatrix} x \\ y \\ z \end{bmatrix} \\ & = & \begin{bmatrix} a & d & g \\ b & e & h \\ c & f & i \end{bmatrix} \left( x \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} + y \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} + z \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} \right) \\ & = & x \left( \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} {\to} \begin{bmatrix} a \\ b \\ c \end{bmatrix} \right) + y \left( \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} {\to} \begin{bmatrix} d \\ e \\ f \end{bmatrix} \right) + z \left( \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} {\to} \begin{bmatrix} g \\ h \\ i \end{bmatrix} \right) \\ & = & \begin{bmatrix} ax + dy + gz \\ bx + ey + hz \\ cx + fy + iz \end{bmatrix} \end{array} $$
“压缩空间” 的变换
$$ \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} \qquad \qquad \begin{bmatrix} 1 & -1 \\ -2 & 2 \end{bmatrix} \qquad $$
“一一对应” 的变换:旋转 + 缩放
$$ \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \qquad \begin{bmatrix} 0 & -1 \\ -1 & 0 \end{bmatrix} \qquad \frac{1}{\sqrt2} \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix} \qquad \begin{bmatrix} 2 & 1 \\ 3 & 4 \end{bmatrix} $$
“一一对应的变换也有逆变换”
$$ \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \qquad \begin{bmatrix} 0 & -1 \\ -1 & 0 \end{bmatrix} \qquad \frac{1}{\sqrt2} \begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix} \qquad \frac{1}{5} \begin{bmatrix} 4 & -3 \\ -1 & 2 \end{bmatrix} $$
试一试 Visualizer 和一张图片
矩阵的乘法 = 线性变换的 “组合”
$$ \begin{bmatrix} 0 & -1 \\ -1 & 0 \end{bmatrix} \times \begin{bmatrix} 0 & -1 \\ -1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $$
$$ \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} $$
$$ \begin{bmatrix} 2 & 1 \\ 3 & 4 \end{bmatrix} \times \begin{bmatrix} 4 & -3 \\ -1 & 2 \end{bmatrix} = \begin{bmatrix} 5 & 0 \\ 0 & 5 \end{bmatrix} $$
先旋转、再拉伸 (从右向左计算)
$$ \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \left( \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} \right) = \begin{bmatrix} 1 & -1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} $$
$$ \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \left( \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} \right) = \begin{bmatrix} 1 & -1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} $$
矩阵乘法 = 线性变换的 “叠加” (从右向左)
$f_0 = 0, f_1 = 1, f_n = f_{n-1} + f_{n-2}$
矩阵乘法可以表示一组数字的任意 “线性” 运算
$$ \begin{array}{rcl} \begin{bmatrix} f_{n+1} \\ f_{n} \end{bmatrix} & = & \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f_{n} \\ f_{n-1} \end{bmatrix} \\ & = & \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} f_{1} \\ f_{0} \end{bmatrix} \end{array} $$
借助矩阵的特殊性,利用 “特征多项式” 可以实现 $O(k^2\log n)$ 甚至 $O(k \log k \log n)$ 的常系数线性递推关系求解
矩阵定义了线性变换
$$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$$
给定 “变换后” 的一个点,能否求出变换前的点?
$$ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 13 \\ 8\end{bmatrix} $$
这就是大家熟悉的 “方程组”!
$$A \vec x = \vec b \Rightarrow \vec x = A^{-1} b$$
任给两个不共线的向量,都可以去 “表示” 出平面上任意一个向量
$$ A = \begin{bmatrix} 2 & -1 \\ 3 & 1 \end{bmatrix} $$
$$ \begin{array}{rcl} \begin{bmatrix} x \\ y \end{bmatrix} & = & \displaystyle \frac{x+y}{5} \cdot \begin{bmatrix} 2 \\ 3 \\ \end{bmatrix} + \frac{-3x+2y}{5} \cdot \begin{bmatrix} -1 \\ 1 \\ \end{bmatrix} \\ & = & \displaystyle \frac{1}{5} \begin{bmatrix} 1 & 1 \\ -3 & 2 \\ \end{bmatrix} \begin{bmatrix} 2 & -1 \\ 3 & 1 \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix} \end{array} $$
$$ \left\{ \begin{matrix} x & + & y & = & 10 \\ 2x & + & 4y & = & 32 \\ \end{matrix} \right. $$
对方程组的 “等价变换”
$$ \left\{ \begin{matrix} 2x & + & 2y & = & 20 \\ 2x & + & 4y & = & 32 \\ \end{matrix} \right. \qquad \left\{ \begin{matrix} 2x & + & 2y & = & 20 \\ & + & 2y & = & 12 \\ \end{matrix} \right. $$
$$ \left\{ \begin{matrix} 2x & + & & = & 8 \\ & + & 2y & = & 12 \\ \end{matrix} \right. \qquad \left\{ \begin{matrix} x & + & & = & 4 \\ & + & y & = & 6 \\ \end{matrix} \right. $$
$$ \begin{bmatrix} 1 & 1 \\ 2 & 4 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 10 \\ 32 \end{bmatrix} $$
$$ \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 2 & 4 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 20 \\ 32 \end{bmatrix} $$
$$ \begin{bmatrix} 1 & 0 \\ -1 & 1 \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 2 & 4 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 20 \\ 12 \end{bmatrix} $$
$$ \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ -1 & 1 \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 2 & 4 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 8 \\ 12 \end{bmatrix} $$
$$ \color{red} \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 8 \\ 12 \end{bmatrix} $$
矩阵 = 线性变换 = 物理世界中的一个步骤
$$ \begin{bmatrix} f_{n+1} \\ f_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f_{n} \\ f_{n-1} \end{bmatrix} $$
线性代数与物理世界的联系
“贪心法”:每次都使我们离方程的解近一点
$$ \left\{ \begin{matrix} x & + & y & = & 10 \\ 2x & + & 4y & = & 32 \\ \end{matrix} \right. \qquad \left\{ \begin{matrix} x' = 10 - y \\ y' = 8 - x/2 \\ \end{matrix} \right. $$
$$ \begin{bmatrix} x' \\ y' \\ 1 \end{bmatrix} = \begin{bmatrix} 0 & -1 & 10 \\ -1/2 & 0 & 8 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix} $$
$$ \begin{bmatrix} 1 \\ 1 \end{bmatrix} {\to} \begin{bmatrix} 9 \\ 7.5 \end{bmatrix} {\to} \begin{bmatrix} 2.5 \\ 3.5 \end{bmatrix} {\to} \begin{bmatrix} 6.5 \\ 6.75 \end{bmatrix} {\to} \begin{bmatrix} 3.25 \\ 4.75 \end{bmatrix} {\to} \ldots \to \begin{bmatrix} 3.997 \\ 5.995 \end{bmatrix} $$
迭代法的成功不是偶然的
$$ \begin{bmatrix} 0 & -1 & 10 \\ -1/2 & 0 & 8 \\ 0 & 0 & 1 \end{bmatrix}^\infty = \begin{bmatrix} 0 & 0 & 4 \\ 0 & 0 & 6 \\ 0 & 0 & 1 \end{bmatrix} $$
有些线性变换可以表达成 “旋转” - “伸缩” - “逆旋转”
$$ \small \begin{bmatrix} 0 & -1 & 10 \\ -\frac12 & 0 & 8 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 4 & \sqrt2 & -\sqrt2 \\ 6 & 1 & 1 \\ 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & -\frac{1}{\sqrt2} & 0 \\ 0 & 0 & \frac{1}{\sqrt2} \end{bmatrix} \begin{bmatrix} 4 & \sqrt2 & -\sqrt2 \\ 6 & 1 & 1 \\ 1 & 0 & 0 \end{bmatrix}^{-1} $$
Google 成功的秘诀:为互联网上所有的页面重要性排序
$$ \small A = \begin{bmatrix} 0 & 0 & 1 & 1/2 \\ 1/3 & 0 & 0 & 0 \\ 1/3 & 1/2 & 0 & 1/2 \\ 1/3 & 1/2 & 0 & 0 \\ \end{bmatrix} \qquad x = \begin{bmatrix} 0.387 \\ 0.129 \\ 0.290 \\ 0.194 \end{bmatrix} $$
推荐系统:如何为你预测对商品的评分?
$$ \small \begin{matrix} & \text{Alice} & \text{Bob} & \text{Cathy} & \text{Dave} \\ \text{苹果} & 1 & ? & 1 & ? \\ \text{橙子} & ? & ? & ? & 3 \\ \text{香蕉} & 3 & ? & ? & ? \\ \text{西瓜} & 5 & 4 & ? & ? \\ \end{matrix} $$
矩阵分解:$M_{m\times n} = P_{m\times k} \times Q_{k\times n}$
物理世界中的很多过程都是线性 (或者可以线性近似) 的。
线性代数的应用
“加” 和 “乘” 的对象可以不是实数!
向量 (vector): 一个 $n$ 维的数组,通常竖着书写
说人话
设 $F$ 是一个域。$F$ 上的向量空间是集合 $V$ 上的两个运算:
且满足以下公理 (默认 $u,v,w\in V$, $a, b \in F$):
一个新的运算:$1 + 0 = 1, 1 + 1 = 0, 1 \cdot 1 = 1, 1 \cdot 0 = 0$
$$ \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} $$
$$ \begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} $$
给定 $n$ 个整数,从中取一部分,使取出数值的异或值最大
用一个变量 $x_i \in \{0,1\}$ 表示第 $i$ 个数字是否要取、$y_j$ 表示最终结果的第 $j$ 个 bit 是否为 1
“算术”、“代数” 和 “算法”
带着这个理解去重新理解你学过《线性代数》的全部