{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 求解线性方程组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 逆矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "逆矩阵的几个属性:\n",
    "1. 若方阵 A 可逆，则 $A^{-1}A = I$，以及 $AA^{-1} = I$。\n",
    "2. 经过消除算法，A 不能存在全是 0 的行。pivots 不能有零。\n",
    "3. `det(A)` != 0\n",
    "4. $Ax = 0$: $x = 0$ 必须是唯一解。\n",
    "5. 若 A, B (同样行列) 都可逆，那么: $\\boxed{(AB)^{-1} = B^{-1}A^{-1}}$\n",
    "6. 一个 2x2 的矩阵，如果可逆，则 $ad - bc$ 不可为零。因为 \n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "a & b \\\\\n",
    "c & d\n",
    "\\end{bmatrix}^{-1} = \\frac{1}{ad - bc}\n",
    "\\begin{bmatrix}\n",
    "d & -b \\\\\n",
    "-c & a\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "7. 对角线矩阵(其余全为0):\n",
    "$$\n",
    "If \\quad A =\n",
    "\\begin{bmatrix}\n",
    "d_{1} \\\\\n",
    "& \\ddots \\\\\n",
    "& & d_{n}\n",
    "\\end{bmatrix}\n",
    "\\quad then \\quad\n",
    "A^{-1} = \n",
    "\\begin{bmatrix}\n",
    "1/d_{1} \\\\\n",
    "& \\ddots \\\\\n",
    "& & 1/d_{n}\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "8. 高斯消元法求逆矩阵，求矩阵的秩: \n",
    "$$ Multiply\\ \\begin{bmatrix} A & I \\end{bmatrix}\\ by \\ A^{-1}\\ to\\ get\\ \\begin{bmatrix} I & A^{-1} \\end{bmatrix}.$$\n",
    "9. 若 $K$ 沿主对角线对称，那么 $K^{-1}$ 也对称；求逆通常会让矩阵变得稠密；pivots 的乘积就是行列式的值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**消元法 = 因式分解**： $A = LU$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       " 1   3   1\n",
       " 1   1  -1\n",
       " 3  11   6"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = [1  3  1\n",
    "     1  1 -1\n",
    "     3 11  6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " -8.5   3.5   2.0\n",
       "  4.5  -1.5  -1.0\n",
       " -4.0   1.0   1.0"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iA = inv(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   2.22045e-16   1.11022e-16\n",
       " 0.0   1.0          -1.11022e-16\n",
       " 0.0  -3.55271e-15   1.0        "
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A * iA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0000000000000009"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "det(A * iA)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   0.0  0.0\n",
       " 1.0   1.0  0.0\n",
       " 3.0  -1.0  1.0"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L, U = lu(A, Val{false})\n",
    "L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   3.0   1.0\n",
       " 0.0  -2.0  -2.0\n",
       " 0.0   0.0   1.0"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   3.0   1.0\n",
       " 1.0   1.0  -1.0\n",
       " 3.0  11.0   6.0"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L * U"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 矩阵的转置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. $Ax$ 的转置是 $x^{T}A^{T}$, $AB$ 的转置是 $B^{T}A^{T}$, $A^{-1}$ 的转置是 $(A^{T})^{-1}$\n",
    "2. $x \\cdot y = x^{T}y$\n",
    "3. $Ax \\cdot y = x \\cdot A^{T}y$\n",
    "4. 对称矩阵的转置是其自身：$S^{T}=S$\n",
    "5. 正交矩阵的转置是其逆：$Q^{T} = Q^{-1}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×2 Array{Int64,2}:\n",
       " 1  4\n",
       " 2  5\n",
       " 3  6"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[1 2 3; 4 5 6]'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Q = [1/3 2/3 2/3; 2/3 1/3 -2/3; 2/3 -2/3 1/3]\n",
    "isapprox(inv(Q), Q')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 如何理解置换矩阵\n",
    "\n",
    "置换矩阵就是每一行每一列都有一个 1. 记为 $P$, 而 $P^{T}$ 依然是置换矩阵。单位矩阵 $I$ 是最简单的置换矩阵。通过交换 $I$ 的行，可以得到全部可能的置换矩阵。A permutation matrix $P$ has the rows of the identity $I$ in any order.\n",
    "\n",
    "本质上，置换矩阵是对行交换的顺序的一种描述。 $PA$ 的含义就是，对 $A$ 进行 $P$ 所描述的行交换。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 Array{Int64,2}:\n",
       "  4  -2  -7  -4  -8\n",
       "  9  -6  -6  -1  -5\n",
       " -2  -9   3  -5   2\n",
       "  9   7  -9   5  -8\n",
       " -1   6  -3   9   6"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "B = [4  -2  -7  -4  -8\n",
    "     9  -6  -6  -1  -5\n",
    "    -2  -9   3  -5   2\n",
    "     9   7  -9   5  -8\n",
    "    -1   6  -3   9   6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 Array{Float64,2}:\n",
       "  1.0        0.0        0.0       0.0        0.0\n",
       "  1.0        1.0        0.0       0.0        0.0\n",
       "  0.444444   0.0512821  1.0       0.0        0.0\n",
       " -0.111111   0.410256   0.582822  1.0        0.0\n",
       " -0.222222  -0.794872   0.171779  0.0242696  1.0"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L, U, p = lu(B)\n",
    "L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 Array{Float64,2}:\n",
       " 9.0  -6.0  -6.0      -1.0      -5.0     \n",
       " 0.0  13.0  -3.0       6.0      -3.0     \n",
       " 0.0   0.0  -4.17949  -3.86325  -5.62393 \n",
       " 0.0   0.0   0.0       8.67894   9.95297 \n",
       " 0.0   0.0   0.0       0.0      -0.771206"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5-element Array{Int64,1}:\n",
       " 2\n",
       " 4\n",
       " 1\n",
       " 5\n",
       " 3"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.6.1",
   "language": "julia",
   "name": "julia-0.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}