chapter02.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第二讲：矩阵消元\n",
    "\n",
    "`消元法`最早由高斯提出，我们以前解方程组的时候都会使用，现在来看如何使用矩阵实现消元法。\n",
    "\n",
    "## 消元法\n",
    "\n",
    "有三元方程组\n",
    "\n",
    "$$\\begin{cases}x&+2y&+z&=2\\\\3x&+8y&+z&=12\\\\&4y&+z&=2\\end{cases}$$\n",
    "\n",
    "对应的矩阵形式$A\\boldsymbol{x}=\\boldsymbol{b}$为\n",
    "\n",
    "$$\\begin{bmatrix}1&2&1\\\\3&8&1\\\\0&4&1\\end{bmatrix}\\begin{bmatrix}x\\\\y\\\\z\\end{bmatrix}=\\begin{bmatrix}2\\\\12\\\\2\\end{bmatrix}$$\n",
    "\n",
    "按照我们以前做消元法的思路：\n",
    "\n",
    "**第一步**\n",
    "\n",
    "我们希望在第二个方程中消去$x$项，来操作系数矩阵（如果第三个方程有$x$，也需要消去）\n",
    "\n",
    "$$A=\\begin{bmatrix}\\underline{1}&2&1\\\\3&8&1\\\\0&4&1\\end{bmatrix}$$\n",
    "\n",
    "下划线的元素为第一步的主元（pivot）：\n",
    "\n",
    "$$\\begin{bmatrix}\\underline{1}&2&1\\\\3&8&1\\\\0&4&1\\end{bmatrix}\\xrightarrow{row_2-3row_1}\\begin{bmatrix}\\underline{1}&2&1\\\\0&2&-2\\\\0&4&1\\end{bmatrix}$$\n",
    "\n",
    "这里我们先不管$\\boldsymbol{b}$向量，等做完$\\boldsymbol{A}$的消元可以再做$b$的消元。（这是MATLAB等工具经常使用的算法。）\n",
    "\n",
    "**第二步**\n",
    "\n",
    "我们希望在第三个方程中消去$y$项，现在第二行第一个非零元素成为了第二个主元\n",
    "\n",
    "$$\\begin{bmatrix}\\underline{1}&2&1\\\\0&\\underline{2}&-2\\\\0&4&1\\end{bmatrix}\\xrightarrow{row_3-2row_2}\\begin{bmatrix}\\underline{1}&2&1\\\\0&\\underline{2}&-2\\\\0&0&\\underline{5}\\end{bmatrix}$$\n",
    "    \n",
    "注意到第三行消元过后仅剩一个非零元素，所以它就成为第三个主元。做到这里就算消元完成了。\n",
    "\n",
    "再来讨论一下消元失效的情形：首先，主元不能为零；其次，在消元时遇到主元位置为零，则需要交换行，使主元不为零；最后提一下，如果我们把第三个方程$z$前的系数成$-4$，会导致第二步消元时最后一行全部为零，则第三个主元就不存在了，至此消元不能继续进行了，这就是下一讲中涉及的**不可逆情况**。\n",
    "\n",
    "**第三步**\n",
    "\n",
    "接下来就该回代（back substitution）了，这时我们在$A$矩阵后面加上$b$向量写成增广矩阵（augmented matrix）的形式：\n",
    "\n",
    "$$\\left[\\begin{array}{c|c}A&b\\end{array}\\right]=\\left[\\begin{array}{ccc|c}1&2&1&2\\\\3&8&1&12\\\\0&4&1&2\\end{array}\\right]\\to\\left[\\begin{array}{ccc|c}1&2&1&2\\\\0&2&-2&6\\\\0&4&1&2\\end{array}\\right]\\to\\left[\\begin{array}{ccc|c}1&2&1&2\\\\0&2&-2&6\\\\0&0&5&-10\\end{array}\\right]$$\n",
    "\n",
    "不难看出，$z$的解已经出现了，此时方程组变为\n",
    "\n",
    "$$\\begin{cases}x&+2y&+z&=2\\\\&2y&-2z&=6\\\\&&5z&=-10\\end{cases}$$\n",
    "\n",
    "从第三更方程求出$z=-2$，代入第二个方程求出$y=1$，在代入第一个方程求出$x=2$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 消元矩阵\n",
    "\n",
    "虽然前面消元时用到了矩阵，但是消元过程其实并没有用到矩阵的运算。接着教授引入**消元矩阵**来做消元。也就是说通过引入矩阵，然后做矩阵运算得到和前面行变换一样的结果。具体怎么做呢？开始之前，回顾上一讲的矩阵乘以向量的方法，有三个列向量的矩阵乘以另一个向量，按**矩阵列的线性组合**可以写作为：\n",
    "\n",
    "$$\\Bigg[v_1\\ v_2\\ v_3\\Bigg]\\begin{bmatrix}3\\\\4\\\\5\\end{bmatrix}=3v_1+4v_2+5v_3$$\n",
    "\n",
    "现在我们不用列的形式，而是**行的形式**（为什么？因为消元其实是矩阵行的变换）。左侧的一个行向量乘以右侧的一个矩阵，那么可以看作**矩阵行向量的线性组合**，如下：\n",
    "\n",
    "$$\\begin{bmatrix}1&2&7\\end{bmatrix}\\begin{bmatrix}&row_1&\\\\&row_2&\\\\&row_3&\\end{bmatrix}=1row_1+2row_2+7row_3$$\n",
    "\n",
    "为什么可以表示成这样，教授解释等讲到矩阵乘法的求法之后，就会明白了。教授强调分别用行和列来进行矩阵操作，这就是线性代数的核心概念。下面我们利用矩阵行向量线性组合这一思想，来将消元法所做的行操作写成矩阵乘以矩阵的形式。\n",
    "\n",
    "**第一步**\n",
    "\n",
    "消元法操作为将第二行改成$row_2-3row_1$，其余两行不变。用矩阵操作来说，就是我们需要一个矩阵，使其满足下面的等式：\n",
    "\n",
    "$$\\Bigg[\\quad ?\\quad\\Bigg]\\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}$$\n",
    "\n",
    "（教授提示）这将是一个很简单的矩阵，毕竟这里只需要改变第二行。那么左边矩阵的第一行是什么呢？嗯，教授给出答案为 $\\begin{bmatrix}1&0&0\\end{bmatrix}$。因为这等价于取1倍系数矩阵的第一行，而不取其他行，这样就得到了右边矩阵的第一行。左边矩阵的最后一行是什么呢？答案是 $\\begin{bmatrix}0&0&1\\end{bmatrix}$，取1个系数矩阵的第三行，而不取其他行，就得到了右边矩阵的第三行。左边矩阵的第二行稍微复杂点，是 $\\begin{bmatrix}-3&1&0\\end{bmatrix}$，相当于-3倍行一加上1倍行二。于是，就求得了下面的结果，我们称左侧矩阵为消元矩阵，记作$E_{21}$，用它可以将第二行第一个元素变为零）：\n",
    "\n",
    "$$\\begin{bmatrix}1&0&0\\\\-3&1&0\\\\0&0&1\\end{bmatrix}\\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}$$\n",
    "\n",
    "（另外，如果三行都不变，消元矩阵就是单位矩阵$I=\\begin{bmatrix}1&0&0\\\\0&1&0\\\\0&0&1\\end{bmatrix}$，$I$之于矩阵运算相当于$1$之于四则运算。）\n",
    "\n",
    "**第二步**\n",
    "\n",
    "接下来我们需要另一个矩阵，用来将第三行第二个元素变为零，也就是求$E_{32}$消元矩阵。\n",
    "\n",
    "$$\\begin{bmatrix}1&0&0\\\\0&1&0\\\\0&-2&1\\end{bmatrix}\\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}$$\n",
    "\n",
    "这就是消元所用的两个初等矩阵（elementary matrix）。\n",
    "\n",
    "**第三步**\n",
    "\n",
    "最后，我们将这两步综合起来，即$E_{32}(E_{12}A)=U$，也就是说如果我们想从$A$矩阵直接得到$U$矩阵（上三角矩阵的缩写）的话，只需要$(E_{32}E_{21})A$即可。注意，矩阵乘法虽然不能随意变动相乘次序，但是可以变动括号位置，也就是满足结合律（associative law），而结合律在矩阵运算中非常重要，很多定理的证明都需要巧妙的使用结合律。\n",
    "\n",
    "既然提到了消元用的初等矩阵，那我们再介绍一种用于置换两行的矩阵，置换矩阵（permutation matrix），例如：\n",
    "\n",
    "$$\\begin{bmatrix}0&1\\\\1&0\\end{bmatrix}\\begin{bmatrix}a&b\\\\c&d\\end{bmatrix}=\\begin{bmatrix}c&d\\\\a&b\\end{bmatrix}$$\n",
    "\n",
    "置换矩阵将原矩阵的两行做了互换。顺便提一下，如果我们希望交换两列，则有\n",
    "\n",
    "$$\\begin{bmatrix}a&b\\\\c&d\\end{bmatrix}\\begin{bmatrix}0&1\\\\1&0\\end{bmatrix}=\\begin{bmatrix}b&a\\\\d&c\\end{bmatrix}$$\n",
    "\n",
    "我们现在能够将$A$通过矩阵运算写成$U$，那么如何从$U$在变回$A$，也就是求消元的逆运算。注意对某些“坏”矩阵，并没有逆，而本讲的例子都是“好”矩阵。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 逆\n",
    "\n",
    "现在，我们以$E_{21}$为例，\n",
    "\n",
    "$$\\Bigg[\\quad ?\\quad \\Bigg]\\begin{bmatrix}1&0&0\\\\-3&1&0\\\\0&0&1\\end{bmatrix}=\\begin{bmatrix}1&0&0\\\\0&1&0\\\\0&0&1\\end{bmatrix}$$\n",
    "\n",
    "什么矩阵可以取消这次行变换？这次变换是从第二行中减去三倍的第一行，那么其逆变换就是给第二行加上三倍的第一行，所以逆矩阵就是$\\begin{bmatrix}1&0&0\\\\3&1&0\\\\0&0&1\\end{bmatrix}$。\n",
    "\n",
    "我们把矩阵$E$的逆记作$E^{-1}$，所以有$E^{-1}E=I$。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}