线性代数基础学习笔记（未完工）

· · 算法·理论

Part 0. 前言

wj 不知道为什么让我们看 jyy 的线代基础课。NOIP似乎从来没考过线代。。。

NOI大纲中关于线性代数的考试内容：

Part 1. 算术、代数与算法

从小学时我们就开始接触“算术”(Arithmetic):给定一个“表达式”和一系列“等价变换”的规则，求出表达式的值。例如：

753+672 = 1300+120+5=1425

中学时我们学习了“代数”(Algebra)：允许表达式中出现代表某个数值的“变量”，表达式仍然成立。例如：

\Rightarrow x \in \{-1,3\}

为什么我们会感觉“代数”比“算术”更难？因为算术的计算过程是确定的——表达式总是朝着“变简单”的方向走；而代数做什么变换“比较好”是困难的。比如看到 (3+4) \times 5 时一定会先算括号里的内容，然而看到 x^2-2x-3=0 时可能需要配方变成 x^2-2x+1-4=0，对未受训练的人来说就不显然了。因此，“算术”对应的是一种确定性(deterministic)，而“代数”对应的是一种不确定性(non-determinism)。

与算术和代数都不同，算法是一种解决问题的方法和步骤，是按照小步工作的自动计算过程。

Part 2. 线性算术

进入正题：什么是线性代数？

讲代数之前，肯定要讲算术。这里的线性算术与小学时的算术有很大区别。首先计算对象就不一样，线性算术是向量(vector)和向量的运算。

我们高一就会学习到向量。现在我们将向量定义为 n 维的“数组”，通常竖着书写。例如：

2 \\ -3 \end{bmatrix}\quad \vec{y}=\begin{bmatrix} 2.4 \\ 1 \\ -5 \end{bmatrix}

是不是突然感觉很熟悉？C++的STL里的vector就是这个意思。

向量的线性运算很简单，复习一下。加法是每个维度分别相加，数乘是每个维度分别乘同一个数字。例如：

\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}

这些就是线性算术！这似乎也……太简单了吧？

这样的线性算术的“公理”其实有很丰富的含义。现在问一个问题：什么是向量？一个数组？起点是原点的一个箭头？坐标系中的一个点？所谓向量，就是有方向的量。我们不妨画一个平面直角坐标系 xOy，然后把一些 2 维的向量直接画上去：

\vec{AB} = \begin{bmatrix}0\\1\end{bmatrix} \quad \vec{AC} = \begin{bmatrix}2\\0\end{bmatrix} \quad \vec{AD} = \begin{bmatrix}1\\1\end{bmatrix} \quad \vec{AE} = \begin{bmatrix}2\\1\end{bmatrix} \quad

此时我们发现，\vec{AE} 可以表示成两个向量的和：

\vec{AE} = \vec{AB}+\vec{AC} \begin{bmatrix}2\\1\end{bmatrix} = \begin{bmatrix}0\\1\end{bmatrix} + \begin{bmatrix}2\\0\end{bmatrix}

这与我们数组相加的定义是统一的。此时我们又可以进一步处理：

\begin{bmatrix}2\\1\end{bmatrix} = \begin{bmatrix}0\\1\end{bmatrix} + \begin{bmatrix}1\\0\end{bmatrix} + \begin{bmatrix}1\\0\end{bmatrix} \begin{bmatrix}2\\1\end{bmatrix} = \begin{bmatrix}0\\1\end{bmatrix} + 2\begin{bmatrix}1\\0\end{bmatrix}

若是扩展到任意 2 维向量上：

\begin{bmatrix}x\\y\end{bmatrix} = x\begin{bmatrix}1\\0\end{bmatrix} + y\begin{bmatrix}0\\1\end{bmatrix}

有趣！我们将任何的向量都“拆分”成了若干倍向量 \begin{bmatrix}1\\0\end{bmatrix} 和若干倍向量 \begin{bmatrix}0\\1\end{bmatrix} 的和。这里就体现了线性算术线性所在。

此时我希望根据上述两种运算定义出一种新的运算“\rightarrow”，把每一个向量变成另一个向量。

如果有以下变换规则：

\begin{bmatrix}0 \\ 0\end{bmatrix} \rightarrow \begin{bmatrix}0 \\ 0\end{bmatrix} \quad \begin{bmatrix}1 \\ 0\end{bmatrix} \rightarrow \begin{bmatrix}2 \\ 0\end{bmatrix} \quad \begin{bmatrix}2 \\ -1\end{bmatrix} \rightarrow \begin{bmatrix}4 \\ -2\end{bmatrix} \cdots

如果画在平面直角坐标系上，就会发现这实际上是一种“拉伸”操作，将一个向量的长度变成了原来的 2 倍。

我们不仅可以做这样简单的拉伸，还能做一些更复杂的事情。如果我们希望

\begin{bmatrix}1 \\ 0\end{bmatrix} \rightarrow \begin{bmatrix}3 \\ 4\end{bmatrix} \quad \begin{bmatrix}0 \\ 1\end{bmatrix} \rightarrow \begin{bmatrix}0 \\ 2\end{bmatrix}

就会出现

\begin{bmatrix}1\\1\end{bmatrix}=\begin{bmatrix}1 \\ 0\end{bmatrix}+\begin{bmatrix}0 \\ 1\end{bmatrix} \rightarrow \begin{bmatrix}3 \\ 4\end{bmatrix} + \begin{bmatrix}0 \\ 2\end{bmatrix} =\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} \rightarrow x\begin{bmatrix}3 \\ 4\end{bmatrix} + y\begin{bmatrix}0 \\ 2\end{bmatrix} =\begin{bmatrix}3x \\ 4x+2y\end{bmatrix}

如果画出一个多边形来，我们发现一个单位正方形通过这样的变换被拉伸并旋转成了一个平行四边形！

此时便可以定义出线性变换了。如果

\begin{bmatrix}1 \\ 0\end{bmatrix} \rightarrow \begin{bmatrix}a \\ b\end{bmatrix} \quad \begin{bmatrix}0 \\ 1\end{bmatrix} \rightarrow \begin{bmatrix}c \\ d\end{bmatrix}

那么

\begin{bmatrix}x \\ y\end{bmatrix} \rightarrow \begin{bmatrix}ax+cy \\ bx+dy\end{bmatrix}

要是把两个不同方向上的变换写在一起，就会变成大家熟悉的样子：

\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 & c \\ b & d\end{bmatrix} \begin{bmatrix}x&z \\ y&w\end{bmatrix}= \begin{bmatrix}ax+cy&az+cw \\ bx+dy&bz+dw\end{bmatrix}