《麻省理工公开课：线性代数》Lecture 1~3 笔记

决定写[WC 2011]XOR一题。

先学了高斯消元法。它和我以前想的解线性方程组的方法很相似。那时在学化学方程式的配平，我发现用待定系数法、根据元素守恒列方程就好了。为了表现自己“彻底”解决了这个问题，我写了个解线性方程组的程序。发现代入法不好实现，便决定采用加减消元法。又发现消元完毕后，会形成一个三角形（好神奇！），回代很方便。于是有了如下的大致思路：以第1个方程的未知数1为基准，消掉第2～n个方程中的未知数1；以第2个方程的未知数2为基准，消掉第3～n个方程中的未知数2……最后剩下第n个方程，只有一个未知数，而整个方程组形成了一个三角形，把第n个未知数代入第(n-1)个方程解出未知数(n-1)，把第n、(n-1)个未知数代入第(n-2)个方程解出未知数(n-2)……整个过程结束后，方程组就解完了。已经忘记一些细节是怎么处理的了，比如我不记得我有交换行的步骤，也许压根就没处理吧……

但是我并没懂得XOR和高斯消元法的联系——听说是经典应用？线性基——这是什么鬼？

经历了头痛欲裂的四五天（没有心情写作业或者睡觉或者研究其他题，听课质量低下），我释然了。是该学习一下线性代数，至少有个感性的认知。找了一套公开课http://open.163.com/special/opencourse/daishu.html，大概能在本年之内学完。

---

Lecture 1

2016.5.17

线性方程组可以横着看（row picture），可以竖着看（column picture）。横着看是我们熟知的解析几何，竖着看是向量的线性组合（linear combination）。

例子：

$$2x-y = 0\\-x+2y = 3$$
它们可以是平面上两条直线 2x-y = 0、-x+2y = 3，也可以是向量的线性组合：
$$x\begin{bmatrix}2 \\-1 \\\end{bmatrix}+y\begin{bmatrix}-1 \\2 \\\end{bmatrix}=\begin{bmatrix}0 \\3 \\\end{bmatrix}$$
解Ax = b是线性代数里的重要问题。Ax是A的列向量的线性组合。

Lecture 2

2016.5.19

高斯消元。初等形式已经会了，有趣的是可以用矩阵来表示。我还没有明白矩阵是什么，暂且理解为一些排列成矩形、用方括号括起来的数，它们可以看成一些行向量排成一行行，也可以看成一些列向量排成一列列。

以

$$x+2y+z=2\\3x+8y+z=12\\4y+z=2$$
为例。

它的系数矩阵是

$$\begin{bmatrix}1 & 2 & 1\\3 & 8 & 1\\0 & 4 & 1\\\end{bmatrix}$$

Step 1 以(1, 1)为主元，行2-3x行1：

$$\begin{bmatrix}1 & 0 & 0\\-3 & 1 & 0\\0 & 0 & 1\\\end{bmatrix}\times\begin{bmatrix}1 & 2 & 1\\3 & 8 & 1\\0 & 4 & 1\\\end{bmatrix}=\begin{bmatrix}1 & 2 & 1\\0 & 2 & -2\\0 & 4 & 1\\\end{bmatrix}$$

怎样一眼看出用什么去乘系数矩阵？将矩阵乘法看作对行的线性组合。Lecture 1中提及的是对列的线性组合。

例如：

$$\begin{bmatrix}1 & 2 & 7\\\end{bmatrix}\times\begin{bmatrix}11 & 12\\21 & 22\\31 & 32\\\end{bmatrix}=1\begin{bmatrix}11 & 12\\\end{bmatrix}+2\begin{bmatrix}21 & 22\\\end{bmatrix}+7\begin{bmatrix}31 & 32\\\end{bmatrix}$$

矩阵x矩阵，把第一个矩阵看成一个个行向量，所得的结果作为乘积对应位置的一行行即可。

所以，先前的用于消元的矩阵的含义为：第一行保持不变，用-3倍的第一行、1倍的第二行、0倍的第三行叠加（组合）得到新的第二行，第三行保持不变。

我想我明白单位矩阵为什么要那么定义了……

Step 2以(2, 2)为主元，行3-2x行2：

$$\begin{bmatrix}1 & 0 & 0\\0 & 1 & 0\\0 & -2 & 1\\\end{bmatrix}\times\begin{bmatrix}1 & 2 & 1\\0 & 2 & -2\\0 & 4 & 1\\\end{bmatrix}=\begin{bmatrix}1 & 2 & 1\\0 & 2 & -2\\0 & 0 & 5\\\end{bmatrix}$$

本例不涉及行的交换。原来排列矩阵有这个用途！

$$\begin{bmatrix}0 & 1\\1 & 0\\\end{bmatrix}\times\begin{bmatrix}a & b\\c & d\\\end{bmatrix}=\begin{bmatrix}c & d\\a & b\\\end{bmatrix}$$
$$\begin{bmatrix}a & b\\c & d\\\end{bmatrix}\times\begin{bmatrix}0 & 1\\1 & 0\\\end{bmatrix}=\begin{bmatrix}b & a\\d & c\\\end{bmatrix}$$
在矩阵左边乘上一些东西是对行的线性组合，在矩阵右边乘上一些东西是对列的线性组合。

Lecture 3

2016.5.24

Matrix multiplication (4 ways!)

以下设A是 $m \times n$ 的矩阵，B是 $n \times p$ 的矩阵，$C = A \times B$ 。只有A的列数等于B的行数，两者才能相乘。

单元素

$$c_{ij} = \sum_{k=1}^n a_{ik}b_{kj}$$
学了《数学：必修4》，有了看待它的新方式：A的第i行点乘B的第j列。

列

Columns of C are combinations of columns of A.

行

Rows of C are combinations of rows of B.

列x行

这个比较新颖。用A的第k列(i = 1, 2, …, n)叉乘B的第k行，把结果加起来即为所求。

这样做为什么是对的呢？

$$\begin{bmatrix}a_{1k}\\a_{2k}\\a_{3k}\\\end{bmatrix}\times\begin{bmatrix}b_{k1} & b_{k2}\\\end{bmatrix}=\begin{bmatrix}a_{1k}b_{k1} & a_{1k}b_{k2}\\a_{2k}b_{k1} & a_{2k}b_{k2}\\a_{3k}b_{k1} & a_{3k}b_{k2}\\\end{bmatrix}$$

用大白话讲出来是：第i行第j列 = 第一个矩阵的第i行点乘第二个矩阵的第j列 = $a_{ik}b_{kj}$ 。把k取遍1, 2, …, n，就是矩阵乘法的定义了。

其他：分块

矩阵乘法可以分成一块块来做，即把矩阵分成几部分，每部分当成一个元素，把单元素公式里的乘法换成矩阵乘法。Strassen算法便用到了这一点——这是一个玄妙的算法。
我不明白。

Inverses (Square matrices)

对于 $n \times n$ 的矩阵A。若存在 $A^{-1}A = I$ ，则称 $A^{-1}$ 是 $A$ 的逆。$AA^{-1}=I$ 。

没有逆的矩阵是不可逆的，或奇异（singular）的。如

$$\begin{bmatrix}1 & 3\\2 & 6\\\end{bmatrix}$$

对于奇异矩阵有3种解释：
1. 它的行/列向量不能通过线性组合得到单位矩阵。
2. 它的行列式等于0。
3. 存在向量$\mathbf x \neq \mathbf 0$，使$\mathbf A \mathbf x = \mathbf 0$ 。如果$\mathbf A^{-1}$存在，两边同乘它，得$\mathbf x = \mathbf 0$。

Gauss-Jordan (Solve many equations at once)

求矩阵的逆的算法。
例如，求

$$\begin{bmatrix}1 & 3\\2 & 7\\\end{bmatrix}$$
的逆，相当于解两个方程组。
$$\begin{bmatrix}1 & 3\\2 & 7\\\end{bmatrix}\begin{bmatrix}a\\b\\\end{bmatrix}=\begin{bmatrix}1\\0\\\end{bmatrix}\\\begin{bmatrix}1 & 3\\2 & 7\\\end{bmatrix}\begin{bmatrix}c\\d\\\end{bmatrix}=\begin{bmatrix}0\\1\\\end{bmatrix}$$
它们的系数矩阵是一样的，所以用高斯消元法消出来的矩阵是一样的。构造增广矩阵
$$\left[\begin{array}{cc|cc}1 & 3 & 1 & 0\\2 & 7 & 0 & 1\end{array}\right]$$
->
$$\left[\begin{array}{cc|cc}1 & 3 & 1 & 0\\0 & 1 & -2 & 1\end{array}\right]$$
->
$$\left[\begin{array}{cc|cc}1 & 0 & 7 & -3\\0 & 1 & -2 & 1\end{array}\right]$$
最后一步向上消元是Gauss-Jordan方法不同于Gauss方法的地方。可以看到 $\left[ \mathbf A | \mathbf I \right]$ 变成了 $\left[ \mathbf I | \mathbf A_{-1} \right]$ 。
可以用同时解两个方程组来理解，也可以用消元矩阵来理解： $\mathbf E\left[ \mathbf A | \mathbf I \right] = \left[ \mathbf I | \mathbf A^{-1} \right]$ ，因为 $\mathbf E\mathbf A = \mathbf I$ 告诉我们 $\mathbf E = \mathbf A^{-1}$ 。

---

模拟高考假还有2个小时结束。输入数学公式有些麻烦。