{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第四讲：$A$ 的 $LU$ 分解\n",
    "\n",
    "$AB$的逆矩阵：\n",
    "$$\n",
    "\\begin{aligned}\n",
    "A \\cdot A^{-1} = I & = A^{-1} \\cdot A\\\\\n",
    "(AB) \\cdot (B^{-1}A^{-1}) & = I\\\\\n",
    "\\textrm{则} AB \\textrm{的逆矩阵为} & B^{-1}A^{-1}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "$A^{T}$的逆矩阵：\n",
    "$$\n",
    "\\begin{aligned}\n",
    "(A \\cdot A^{-1})^{T} & = I^{T}\\\\\n",
    "(A^{-1})^{T} \\cdot A^{T} & = I\\\\\n",
    "\\textrm{则} A^{T} \\textrm{的逆矩阵为} & (A^{-1})^{T}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "## 将一个 $n$ 阶方阵 $A$ 变换为 $LU$ 需要的计算量估计：\n",
    "\n",
    "1. 第一步，将$a_{11}$作为主元，需要的运算量约为$n^2$\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "a_{11} & a_{12} & \\cdots & a_{1n} \\\\\n",
    "a_{21} & a_{22} & \\cdots & a_{2n} \\\\\n",
    "\\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "a_{n1} & a_{n2} & \\cdots & a_{nn} \\\\\n",
    "\\end{bmatrix}\n",
    "\\underrightarrow{消元}\n",
    "\\begin{bmatrix}\n",
    "a_{11} & a_{12} & \\cdots & a_{1n} \\\\\n",
    "0      & a_{22} & \\cdots & a_{2n} \\\\\n",
    "0      & \\vdots & \\ddots & \\vdots \\\\\n",
    "0      & a_{n2} & \\cdots & a_{nn} \\\\\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "2. 以此类推，接下来每一步计算量约为$(n-1)^2、(n-2)^2、\\cdots、2^2、1^2$。\n",
    "\n",
    "3. 则将 $A$ 变换为 $LU$ 的总运算量应为$O(n^2+(n-1)^2+\\cdots+2^2+1^2)$，即$O(\\frac{n^3}{3})$。\n",
    "\n",
    "置换矩阵(Permutation Matrix)：\n",
    "\n",
    "3阶方阵的置换矩阵有6个：\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "1 & 0 & 0 \\\\\n",
    "0 & 1 & 0 \\\\\n",
    "0 & 0 & 1 \\\\\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "0 & 1 & 0 \\\\\n",
    "1 & 0 & 0 \\\\\n",
    "0 & 0 & 1 \\\\\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "0 & 0 & 1 \\\\\n",
    "0 & 1 & 0 \\\\\n",
    "1 & 0 & 0 \\\\\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "1 & 0 & 0 \\\\\n",
    "0 & 0 & 1 \\\\\n",
    "0 & 1 & 0 \\\\\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "0 & 1 & 0 \\\\\n",
    "0 & 0 & 1 \\\\\n",
    "1 & 0 & 0 \\\\\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "0 & 0 & 1 \\\\\n",
    "1 & 0 & 0 \\\\\n",
    "0 & 1 & 0 \\\\\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$n$阶方阵的置换矩阵有$\\binom{n}{1}=n!$个。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}