III_10_Final_exam_review.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ This notebook is part of *Final exam review* in the OCW MIT course 18.06 by Prof Gilbert Strang [1]\n",
    "+ Created by me, Dr Juan H Klopper\n",
    "    + Head of Acute Care Surgery\n",
    "    + Groote Schuur Hospital\n",
    "    + University Cape Town\n",
    "    + <a href=\"mailto:juan.klopper@uct.ac.za\">Email me with your thoughts, comments, suggestions and corrections</a> \n",
    "<a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc/4.0/\"><img alt=\"Creative Commons Licence\" style=\"border-width:0\" src=\"https://i.creativecommons.org/l/by-nc/4.0/88x31.png\" /></a><br /><span xmlns:dct=\"http://purl.org/dc/terms/\" href=\"http://purl.org/dc/dcmitype/InteractiveResource\" property=\"dct:title\" rel=\"dct:type\">Linear Algebra OCW MIT18.06</span> <span xmlns:cc=\"http://creativecommons.org/ns#\" property=\"cc:attributionName\">IPython notebook [2] study notes by Dr Juan H Klopper</span> is licensed under a <a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc/4.0/\">Creative Commons Attribution-NonCommercial 4.0 International License</a>.\n",
    "\n",
    "+ [1] <a href=\"http://ocw.mit.edu/courses/mathematics/18-06sc-linear-algebra-fall-2011/index.htm\">OCW MIT 18.06</a>\n",
    "+ [2] Fernando Pérez, Brian E. Granger, IPython: A System for Interactive Scientific Computing, Computing in Science and Engineering, vol. 9, no. 3, pp. 21-29, May/June 2007, doi:10.1109/MCSE.2007.53. URL: http://ipython.org"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<link href='http://fonts.googleapis.com/css?family=Alegreya+Sans:100,300,400,500,700,800,900,100italic,300italic,400italic,500italic,700italic,800italic,900italic' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=Arvo:400,700,400italic' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=PT+Mono' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=Shadows+Into+Light' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=Philosopher:400,700,400italic,700italic' rel='stylesheet' type='text/css'>\n",
       "\n",
       "<style>\n",
       "\n",
       "@font-face {\n",
       "    font-family: \"Computer Modern\";\n",
       "    src: url('http://mirrors.ctan.org/fonts/cm-unicode/fonts/otf/cmunss.otf');\n",
       "}\n",
       "\n",
       "#notebook_panel { /* main background */\n",
       "    background: #ddd;\n",
       "    color: #000000;\n",
       "}\n",
       "\n",
       "\n",
       "\n",
       "/* Formatting for header cells */\n",
       ".text_cell_render h1 {\n",
       "    font-family: 'Philosopher', sans-serif;\n",
       "    font-weight: 400;\n",
       "    font-size: 2.2em;\n",
       "    line-height: 100%;\n",
       "    color: rgb(0, 80, 120);\n",
       "    margin-bottom: 0.1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\t\n",
       ".text_cell_render h2 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "    font-weight: 400;\n",
       "    font-size: 1.9em;\n",
       "    line-height: 100%;\n",
       "    color: rgb(200,100,0);\n",
       "    margin-bottom: 0.1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\t\n",
       "\n",
       ".text_cell_render h3 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "    margin-top:12px;\n",
       "    margin-bottom: 3px;\n",
       "    font-style: italic;\n",
       "    color: rgb(94,127,192);\n",
       "}\n",
       "\n",
       ".text_cell_render h4 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "}\n",
       "\n",
       ".text_cell_render h5 {\n",
       "    font-family: 'Alegreya Sans', sans-serif;\n",
       "    font-weight: 300;\n",
       "    font-size: 16pt;\n",
       "    color: grey;\n",
       "    font-style: italic;\n",
       "    margin-bottom: .1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       ".text_cell_render h6 {\n",
       "    font-family: 'PT Mono', sans-serif;\n",
       "    font-weight: 300;\n",
       "    font-size: 10pt;\n",
       "    color: grey;\n",
       "    margin-bottom: 1px;\n",
       "    margin-top: 1px;\n",
       "}\n",
       "\n",
       ".CodeMirror{\n",
       "        font-family: \"PT Mono\";\n",
       "        font-size: 100%;\n",
       "}\n",
       "\n",
       "</style>\n",
       "\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.core.display import HTML, Image\n",
    "css_file = 'style.css'\n",
    "HTML(open(css_file, 'r').read())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sympy import init_printing, Matrix, symbols, sqrt, Rational\n",
    "from sympy.solvers import solve\n",
    "from numpy import matrix, transpose, sqrt, eye\n",
    "from numpy.linalg import pinv, inv, det, svd, norm, eig\n",
    "from scipy.linalg import pinv2\n",
    "from warnings import filterwarnings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "init_printing(use_latex = 'mathjax')\n",
    "filterwarnings('ignore')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Final examination review"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Previous examination questions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ If A is a *m* &times; *n* matrix of rank *r* and the following holds\n",
    "    + No solution\n",
    "    $$ Ax=\\begin{bmatrix}1\\\\0\\\\0\\end{bmatrix} $$\n",
    "    + One solution\n",
    "    $$ Ax=\\begin{bmatrix}0\\\\1\\\\0\\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ How many rows in this matrix?\n",
    "    + *m* = 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ What is the rank?\n",
    "    + If there are no solutions then *r* < *m*\n",
    "    + If there is only a single solution then the nullspace has only the zero vector as so *r* = *n*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ How many columns?\n",
    "    + For one solution (as above) *r* = *n* and with *m* = 3 and *r* < *m* we have *r* = *n* < 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Write down a matrix that fits the description above\n",
    "$$ A=\\begin{bmatrix}0&0\\\\1&0\\\\0&1\\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ True or False for the above\n",
    "    + Determinant of A<sup>T</sup>A is same as determinant of AA<sup>T</sup>\n",
    "        + False\n",
    "    + A<sup>T</sup>A is invertible\n",
    "        + If *r* = *n* (independent columns of A) then TRUE\n",
    "    + AA<sup>T</sup>A is positive definite\n",
    "        + False (it is going to be 3 &times; 3, but still with only rank 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0 & 0\\\\1 & 0\\\\0 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡0  0⎤\n",
       "⎢    ⎥\n",
       "⎢1  0⎥\n",
       "⎢    ⎥\n",
       "⎣0  1⎦"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Matrix([[0, 0], [1, 0], [0, 1]])\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1 & 0\\\\0 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1  0⎤\n",
       "⎢    ⎥\n",
       "⎣0  1⎦"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A.transpose() * A).inv()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A.transpose() * A).det() == (A * A.transpose())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0 & 0 & 0\\\\0 & 1 & 0\\\\0 & 0 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡0  0  0⎤\n",
       "⎢       ⎥\n",
       "⎢0  1  0⎥\n",
       "⎢       ⎥\n",
       "⎣0  0  1⎦"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A * A.transpose()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Prove that A<sup>T</sup>*y* = *c* has at least one solution for every *c* and in fact infinitely many solution for every *c*\n",
    "    + It has at least one solution because the new number of rows (*n*) is equal to *r*\n",
    "    + The dimension of the nullspace of A<sup>T</sup> is *m* - *r*, which in our example here would be > 0, thus infinitely many solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Suppose we have a matrix A with columns containing vectors *v*<sub>1</sub>, *v*<sub>2</sub>, and *v*<sub>3</sub>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Solve A**x** = *v*<sub>1</sub> - *v*<sub>2</sub> + *v*<sub>3</sub>\n",
    "    + This is simple multiplication by columns\n",
    "    $$ x=\\begin{bmatrix}1\\\\-1\\\\1\\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Suppose *v*<sub>1</sub> - *v*<sub>2</sub> + *v*<sub>3</sub> = 0\n",
    "    + Is the solution unique or are there more\n",
    "        + Uniqueness means nothing in the nullspace except the zero vector, so in this cane the solutions are not unique\n",
    "+ Suppose the columns are orthonormal (would be called *q*<sub>1</sub>, *q*<sub>2</sub>, *q*<sub>3</sub>)\n",
    "    + What combination of *v*<sub>1</sub> and *v*<sub>2</sub> are closet to *v*<sub>3</sub>?\n",
    "        + Zero for each *v*<sub>1</sub> and *v*<sub>2</sub>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Consider the Markov matrix\n",
    "$$ \\begin{bmatrix}0.2&0.4&0.3\\\\0.4&0.2&0.3\\\\0.4&0.4&0.4\\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Calculate the eigenvalues\n",
    "    + The matrix is singular (note how &frac12; of columns 1 plys &frac12; of column 2 equals columns 3) so one eigenvalue will be zero\n",
    "    + Another must be 1\n",
    "    + The trace adds to 0.8 and so must the sums of the eigenvalues, thus the last eigenvalue is -0.2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ If for the following the *u*(0) vector is as indicated, what would teh solution be after *k* steps?\n",
    "$$ {u}_{k}={A}^{k};\\quad u\\left({0}\\right)=\\begin{bmatrix}0\\\\10\\\\0\\end{bmatrix} $$\n",
    "    + The following will hold\n",
    "    $$ {u}_{k}={A}^{k};\\quad u\\left({0}\\right)={c}_{1}{\\lambda}_{1}^{k}{x}_{1}+{c}_{2}{\\lambda}_{2}^{k}{x}_{2}+{c}_{3}{\\lambda}_{3}^{k}{x}_{3} \\\\ {u}_{k}={A}^{k};\\quad u\\left({0}\\right)=0+{c}_{2}\\left({1}\\right){x}_{2}+{c}_{3}\\left({-0.2}\\right)^{k}{x}_{3} $$\n",
    "    + So at &infin; the only term that survives is *c*<sub>2</sub>*x*<sub>2</sub>\n",
    "    + Indeed, the key eigenvalue in any Markov matrix is 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "+ Consider the eigenvector and calculate *u* at &infin;\n",
    "    + We already know that we have to use the &lambda; = 1 eigenvalue\n",
    "    + The distribution at &infin; will be as follows (see python code below)\n",
    "    $$ u\\left({\\infty}\\right)=\\begin{bmatrix}3\\\\3\\\\4\\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0.2 & 0.4 & 0.3\\\\0.4 & 0.2 & 0.3\\\\0.4 & 0.4 & 0.4\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡0.2  0.4  0.3⎤\n",
       "⎢             ⎥\n",
       "⎢0.4  0.2  0.3⎥\n",
       "⎢             ⎥\n",
       "⎣0.4  0.4  0.4⎦"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Matrix([[0.2, 0.4, 0.3], [0.4, 0.2, 0.3], [0.4, 0.4, 0.4]])\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\begin{pmatrix}-0.2, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}-1.0\\\\1.0\\\\0\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}, & \\begin{pmatrix}0, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}-0.5\\\\-0.5\\\\1.0\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}, & \\begin{pmatrix}1.0, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}0.75\\\\0.75\\\\1.0\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎛-0.2, 1, ⎡⎡-1.0⎤⎤⎞, ⎛0, 1, ⎡⎡-0.5⎤⎤⎞, ⎛1.0, 1, ⎡⎡0.75⎤⎤⎞⎤\n",
       "⎢⎜         ⎢⎢    ⎥⎥⎟  ⎜      ⎢⎢    ⎥⎥⎟  ⎜        ⎢⎢    ⎥⎥⎟⎥\n",
       "⎢⎜         ⎢⎢1.0 ⎥⎥⎟  ⎜      ⎢⎢-0.5⎥⎥⎟  ⎜        ⎢⎢0.75⎥⎥⎟⎥\n",
       "⎢⎜         ⎢⎢    ⎥⎥⎟  ⎜      ⎢⎢    ⎥⎥⎟  ⎜        ⎢⎢    ⎥⎥⎟⎥\n",
       "⎣⎝         ⎣⎣ 0  ⎦⎦⎠  ⎝      ⎣⎣1.0 ⎦⎦⎠  ⎝        ⎣⎣1.0 ⎦⎦⎠⎦"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.eigenvects() # Looking for eigenvector of eigenvalue 1\n",
    "# Have to distribute the totals into 10 (were 10 total intiallly)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Calculate the projection onto the following line\n",
    "$$ a=\\begin{bmatrix}4\\\\-3\\end{bmatrix} $$\n",
    "    + The projection matrix is\n",
    "    $$ P=\\frac{{a}{a}^{T}}{{a}^{T}{a}} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 0.64, -0.48],\n",
       "        [-0.48,  0.36]])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = matrix([[4], [-3]]) # Using scipy\n",
    "(a * transpose(a)) / (transpose(a) * a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Consider the matrix with eigenvalues 0 and 3 and the following eigenvectors\n",
    "$$ 0,\\begin{bmatrix}1\\\\2\\end{bmatrix}\\quad 3,\\begin{bmatrix}2\\\\1\\end{bmatrix} $$\n",
    "    + We use the following decomposition\n",
    "    $$ A={S}{\\Lambda}{S}^{-1} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "S = matrix([[1, 2], [2, 1]])\n",
    "L = matrix([[0, 0], [0, 3]])\n",
    "S_inv = inv(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 4., -2.],\n",
       "        [ 2., -1.]])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = S * L * S_inv\n",
    "A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Give a 2 &times; 2 matrix A such that A &ne; B<sup>T</sup>B for any B\n",
    "    + B<sup>T</sup> is always symmetric, so A can be any non-symmetric matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ A matrix that has orthogonal eigenvectors, but is not symmetric\n",
    "    + Any skew-symmetric matrix (transpose = negative of matrix)\n",
    "    $$ \\begin{bmatrix}0&1\\\\-1&0\\end{bmatrix} $$\n",
    "    + Any orthogonal matrix\n",
    "    $$ \\begin{bmatrix}\\cos&-\\sin\\\\\\sin&\\cos\\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Consider the following system A**x**=**b**, with the least squares solution shown and calculate the projection of **b** onto the columnspace of A\n",
    "$$ \\begin{bmatrix} 1 & 0 \\\\ 1 & 1 \\\\ 1 & 2 \\end{bmatrix}=\\begin{bmatrix} c \\\\ d \\end{bmatrix}=\\begin{bmatrix} 3 \\\\ 4 \\\\ 1 \\end{bmatrix}, \\quad \\begin{bmatrix} \\hat { c }  \\\\ \\hat { d }  \\end{bmatrix}=\\begin{bmatrix} \\frac { 11 }{ 3 }  \\\\ -1 \\end{bmatrix} $$\n",
    "    + The least square solution is given, so simply multiply each entry by its column\n",
    "    $$ \\frac{ 11 }{ 3 } \\begin{bmatrix} 1 \\\\ 1 \\\\ 1 \\end{bmatrix}-1\\begin{bmatrix} 0 \\\\ 1 \\\\ 2 \\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Calculate a different vector **b** such that all the least square solutions are zero\n",
    "    + This requires **b** to be orthogonal to those columns, such as the following\n",
    "    $$ \\begin{bmatrix}1\\\\-2\\\\1\\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 6 (from recitation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Consider then 3 &times; 3 matrix A, with &lambda;<sub>1</sub>=1 and &lambda;<sub>2</sub>=2 and the first two pivots *d*<sub>1</sub>=*d*<sub>2</sub>=1\n",
    "$$ A=\\begin{bmatrix}1&0&1\\\\0&1&1\\\\1&1&0\\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Find &lambda;<sub>3</sub> and *d*<sub>3</sub>\n",
    "    + The sum of the eigenvalues must equal the trace, thus &lambda;<sub>3</sub>=-1\n",
    "    + Constant multiples of a row subtracted from another won't change the determinant leaving *d*<sub>1</sub>&times;*d*<sub>2</sub>&times;*d*<sub>3</sub>=|A| (just watching out for singular matrices which will have a zero on the main diagonal; here though we have three non-zero eigenvalues, so the matrix is not-singular), leaving *d*<sub>3</sub>=-2 (product of eigenvalues is also the determinant of A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Calculate the smallest *a*<sub>33</sub> entry that will make positive semi-definite\n",
    "    + For positive definite the eigenvalues must all be &ge; zero\n",
    "    + The determinant must also be &ge; 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1 & 0 & 1\\\\0 & 1 & 1\\\\1 & 1 & a_{33}\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1  0   1 ⎤\n",
       "⎢         ⎥\n",
       "⎢0  1   1 ⎥\n",
       "⎢         ⎥\n",
       "⎣1  1  a₃₃⎦"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a33 = symbols('a33')\n",
    "A = Matrix([[1, 0, 1], [0, 1, 1], [1, 1, a33]])\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$a_{33} - 2$$"
      ],
      "text/plain": [
       "a₃₃ - 2"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.det() # Thus a33 must be grteater tha or equal to 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Calculate the smallest values of *c* such that the following is still positive semi-definite\n",
    "$$ A-cI $$\n",
    "    + We can calculate the determinant using sympy (see below) or we can make use of the fact that adding a constant multiple of the identity matrix will only add that constant to each eigenvalue, leaving the eigenvectors intact\n",
    "       $$ 1+c,\\quad 2+c,\\quad -1+c $$\n",
    "   + Each must be &ge; 0, so the smallest value of *c* is 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}- 1.0 c + 1 & 0 & 1\\\\0 & - 1.0 c + 1 & 1\\\\1 & 1 & - 1.0 c\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-1.0⋅c + 1      0         1   ⎤\n",
       "⎢                              ⎥\n",
       "⎢    0       -1.0⋅c + 1    1   ⎥\n",
       "⎢                              ⎥\n",
       "⎣    1           1       -1.0⋅c⎦"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c = symbols('c')\n",
    "A = Matrix([[1, 0, 1], [0, 1, 1], [1, 1, 0]])\n",
    "(A - c * eye(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$- 1.0 c^{3} + 2.0 c^{2} + 1.0 c - 2$$"
      ],
      "text/plain": [
       "       3        2            \n",
       "- 1.0⋅c  + 2.0⋅c  + 1.0⋅c - 2"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A - c * eye(3)).det() # From here we can calulcate the smallest value of c such\n",
    "# that the determinant is still greater than or equal to zero"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$- c^{3} + 2 c^{2} + c - 2$$"
      ],
      "text/plain": [
       "   3      2        \n",
       "- c  + 2⋅c  + c - 2"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = -c ** 3 + 2 * c ** 2 + c - 2\n",
    "f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}-1, & 1, & 2\\end{bmatrix}$$"
      ],
      "text/plain": [
       "[-1, 1, 2]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve(f, c) # solve the equation f for the variable c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Consider now one of the starting vectors *u*<sub>0</sub> below and with *u*<sub>k+1</sub> = &frac12;A*u*<sub>k</sub> calculate the limiting behavior of *u*<sub>k</sub> as *k* approaches &infin;\n",
    "$$ {u}_{0}=\\begin{bmatrix}3\\\\0\\\\0\\end{bmatrix},\\quad\\begin{bmatrix}0\\\\3\\\\0\\end{bmatrix},\\quad\\begin{bmatrix}0\\\\0\\\\3\\end{bmatrix} $$\n",
    "    + Notice that &frac12; is a Markov matrix\n",
    "    + We cannot be sure that there will be a steady state as there are zero entries in &frac12;A\n",
    "    + Multiplying a matrix by a constant scalar will not change the eigenvectors, but will change the eigenvalues by the same scalar multiple and we will have &lambda;<sub>1</sub>=&frac12; and &lambda;<sub>2</sub>=1 and &lambda;<sub>3</sub>=-&frac12;\n",
    "    + We do have an eigenvalue of 1, so we will reach a steady-state\n",
    "    + The eigenvector of &lambda;<sub>2</sub>=1 is the following (see below)\n",
    "    $$ \\begin{bmatrix}1\\\\1\\\\1\\end{bmatrix} $$\n",
    "    + This already sums to 3, so will be *u*<sub>&infin;</sub>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}