II_09_Diagonalization_and_Powers.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ This notebook is part of lecture 22 *Diagonalization and powers of A* 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, eye, Rational\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": [
    "# Diagonalizing a matrix\n",
    "# Powers of a matrix A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Definition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* If A is a *n*&#215;*n*, then a non-zero vector **x** in &#8477;<sup>n</sup> is called an *eigenvector* of the matrix A if A**x** is a scalar multiple of **x**\n",
    "* What this suggests is that if you consider the column vector **x** and multiply it by a scalar (here called &#955;) (which is then parallel to **x**, just of different length) it results in the same solution as multiplying the matrix A by **x**\n",
    "* Let's try another explanation: if a matrix A, multiplied with a (column) vector (**x**) results in a scalar multiple of that same (column) vector (and is thus parallel to that (column) vector) then this (column) vector is an eigenvector of the matrix A\n",
    "    * In essence this multiplication of a matrix with a (column) vector produces another vector on the same line as the original vector\n",
    "    * Depending on the value of this scalar the resulting vector might point in the opposite direction and be shorter or longer than the original\n",
    "* This scalar multiple is called the eigenvalue\n",
    "* Matrices can have more than one eigenvalue and eigenvector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Derivations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We need to insert an identity matrix of size *n* into the equation that describes the explanation above\n",
    "$$ {A}\\mathbf{x}={\\lambda}\\mathbf{x} \\\\ {A}\\mathbf{x}={\\lambda}{I}\\mathbf{x} \\\\ {A}\\mathbf{x}-{\\lambda}{I}\\mathbf{x}=\\mathbf{0} \\\\ \\left({A}-{\\lambda}{I}\\right)\\mathbf{x}=\\mathbf{0} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Look at this carefully and you'll notice that we are suggesting the nullspace (eigenspace) of the matrix (A-&#955;I)\n",
    "* This matrix has to be singular, i.e. have a determinant of 0\n",
    "$$ \\left|{A}-{\\lambda}{I}\\right|=0 $$\n",
    "* Solving this equation (called the characteristic equation) will give us the eigenvalues (&#955;<sup>'s</sup>)\n",
    "* It will always be a polynomial in &#955; (called the characteristic polynomial of A), with a leading coefficient of 1 and a degree of *n* corresponding to the size of A\n",
    "$$ {p}\\left({\\lambda}\\right)={\\lambda}^{n}+{c}_{1}{\\lambda}^{n-1}+\\dots+{c}_{n} $$\n",
    "* Substituting them back into...\n",
    "$$ \\left({A}\\mathbf{x}-{\\lambda}{I}\\right)\\mathbf{x}=\\mathbf{0} $$\n",
    "* ... allows us to calculate the eigenvector(s) **x**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Let's look at the following matrix A\n",
    "$$ A=\\begin{bmatrix} 0 & 0 & -2 \\\\ 1 & 2 & 1 \\\\ 1 & 0 & 3 \\end{bmatrix}\\\\ A-\\lambda I=\\begin{bmatrix} 0 & 0 & -2 \\\\ 1 & 2 & 1 \\\\ 1 & 0 & 3 \\end{bmatrix}-\\begin{bmatrix} \\lambda  & 0 & 0 \\\\ 0 & \\lambda  & 0 \\\\ 0 & 0 & \\lambda  \\end{bmatrix}=\\begin{bmatrix} -\\lambda  & 0 & -2 \\\\ 1 & 2-\\lambda  & 1 \\\\ 1 & 0 & 3-\\lambda  \\end{bmatrix}\\\\ \\begin{vmatrix} -\\lambda  & 0 & -2 \\\\ 1 & 2-\\lambda  & 1 \\\\ 1 & 0 & 3-\\lambda  \\end{vmatrix}=0\\\\ { \\lambda  }^{ 3 }-5{ \\lambda  }^{ 2 }+8\\lambda -4=0\\\\ { \\lambda  }_{ 1 }=1,\\quad { \\lambda  }_{ 2 }={ \\lambda  }_{ 3 }=2 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Let's start with the first eigenvalue, which is equal to 1 and replace it in A-&#955;I"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-1 & 0 & -2\\\\1 & 1 & 1\\\\1 & 0 & 2\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-1  0  -2⎤\n",
       "⎢         ⎥\n",
       "⎢1   1  1 ⎥\n",
       "⎢         ⎥\n",
       "⎣1   0  2 ⎦"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Matrix([[-1, 0 ,-2], [1, 1, 1], [1, 0, 2]])\n",
    "A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We now need the nullspace of this matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\left[\\begin{matrix}-2\\\\1\\\\1\\end{matrix}\\right]\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎡-2⎤⎤\n",
       "⎢⎢  ⎥⎥\n",
       "⎢⎢1 ⎥⎥\n",
       "⎢⎢  ⎥⎥\n",
       "⎣⎣1 ⎦⎦"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.nullspace()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We knew that this would be 1-dimensional after looking at the row-reduced form"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{pmatrix}\\left[\\begin{matrix}1 & 0 & 2\\\\0 & 1 & -1\\\\0 & 0 & 0\\end{matrix}\\right], & \\begin{bmatrix}0, & 1\\end{bmatrix}\\end{pmatrix}$$"
      ],
      "text/plain": [
       "⎛⎡1  0  2 ⎤, [0, 1]⎞\n",
       "⎜⎢        ⎥        ⎟\n",
       "⎜⎢0  1  -1⎥        ⎟\n",
       "⎜⎢        ⎥        ⎟\n",
       "⎝⎣0  0  0 ⎦        ⎠"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.rref()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* It has rank 2 (two pivot column and 1 free variable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Now for the other 2 eigenvalues, both equaling 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-2 & 0 & -2\\\\1 & 0 & 1\\\\1 & 0 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-2  0  -2⎤\n",
       "⎢         ⎥\n",
       "⎢1   0  1 ⎥\n",
       "⎢         ⎥\n",
       "⎣1   0  1 ⎦"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Matrix([[-2, 0, -2], [1, 0, 1], [1, 0, 1]])\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\left[\\begin{matrix}0\\\\1\\\\0\\end{matrix}\\right], & \\left[\\begin{matrix}-1\\\\0\\\\1\\end{matrix}\\right]\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎡0⎤, ⎡-1⎤⎤\n",
       "⎢⎢ ⎥  ⎢  ⎥⎥\n",
       "⎢⎢1⎥  ⎢0 ⎥⎥\n",
       "⎢⎢ ⎥  ⎢  ⎥⎥\n",
       "⎣⎣0⎦  ⎣1 ⎦⎦"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.nullspace()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{pmatrix}\\left[\\begin{matrix}1 & 0 & 1\\\\0 & 0 & 0\\\\0 & 0 & 0\\end{matrix}\\right], & \\begin{bmatrix}0\\end{bmatrix}\\end{pmatrix}$$"
      ],
      "text/plain": [
       "⎛⎡1  0  1⎤, [0]⎞\n",
       "⎜⎢       ⎥     ⎟\n",
       "⎜⎢0  0  0⎥     ⎟\n",
       "⎜⎢       ⎥     ⎟\n",
       "⎝⎣0  0  0⎦     ⎠"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.rref()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Only a single pivot column, therefor rank of 1 and two independent (free) variables"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Corresponding to the first eigenvalue we have a single eigenvector that is the basis for a 1-dimensional (line) eigenspace in &#8477;<sup>3</sup>\n",
    "* Corresponding to the second (and third) eigenvalues we have two basis vectors for a 2-dimensional plane in &#8477;<sup>3</sup>\n",
    "* Since we are talking about subspaces, we must note that the zero vector must be in both eigenspaces (type of nullspace), but isn't an eigenvector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The eigenvalues of triangular (upper and lower) and diagonal matrices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The eigenvalue of these type of matrices are exactly the entries along the main diagonal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Real and complex eigenvalues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* There will be characteristic polynomials resulting in complex roots\n",
    "* The consequences of real-valued eigenvalues for a square matrix A of size *n* are the following\n",
    "    * The system (A-&#955;I)**x**=**0** has non-trivial solutions\n",
    "    * There is a non-zero vector **x** in &#8477;<sup>n</sup> such that A**x**=&#955;**x**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The eigenvector matrix S and eigenvalue matrix &#923;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We need to create S from the (column) eigenvectors such that the following holds\n",
    "$$ {S}^{-1}{A}{S}=\\Lambda $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* As such, S should be square of size *n*&#215;*n* and invertible, so we need *n* independent eigenvectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Suppose we have *n* linearly independent eigenvectors of A\n",
    "* Put them in the columns of S and calculate AS\n",
    "$$ AS=A\\begin{bmatrix} \\vdots  & \\vdots  & \\vdots  & \\vdots  \\\\ \\vdots  & \\vdots  & \\vdots  & \\vdots  \\\\ { x }_{ 1 } & { x }_{ 2 } & \\dots  & { x }_{ n } \\\\ \\vdots  & \\vdots  & \\vdots  & \\vdots  \\end{bmatrix}=\\begin{bmatrix} \\vdots  & \\vdots  & \\vdots  & \\vdots  \\\\ \\vdots  & \\vdots  & \\vdots  & \\vdots  \\\\ { { \\lambda  }_{ 1 }x }_{ 1 } & { \\lambda  }_{ 2 }{ x }_{ 2 } & \\dots  & { \\lambda  }_{ n }{ x }_{ n } \\\\ \\vdots  & \\vdots  & \\vdots  & \\vdots  \\end{bmatrix}=\\begin{bmatrix} \\vdots  & \\vdots  & \\vdots  & \\vdots  \\\\ \\vdots  & \\vdots  & \\vdots  & \\vdots  \\\\ { x }_{ 1 } & { x }_{ 2 } & \\dots  & { x }_{ n } \\\\ \\vdots  & \\vdots  & \\vdots  & \\vdots  \\end{bmatrix}\\begin{bmatrix} { \\lambda  }_{ 1 } & 0 & 0 & 0 \\\\ 0 & { \\lambda  }_{ 2 } & 0 & 0 \\\\ \\vdots  & \\vdots  & { \\dots  } & \\vdots  \\\\ 0 & 0 & 0 & { \\lambda  }_{ n } \\end{bmatrix}\\\\ AS=S\\Lambda  $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* From this we have the following\n",
    "$$ AS=S\\Lambda \\\\ { S }^{ -1 }AS=\\Lambda \\\\ A=S\\Lambda { S }^{ -1 } $$\n",
    "* Later I will use the computer variable D for this diagonal matrix &#923;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The power of a matrix (only for *n* independent eigenvectors)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We saw in the example section of the last lecture that the following holds\n",
    "$$ {A}^{2}\\mathbf{x}={\\lambda}^{2}{x} $$\n",
    "* The eigenvectors are the same for A and A<sup>2</sup>\n",
    "* We can also see the following\n",
    "$$ { A }^{ 2 }=S\\Lambda { S }^{ -1 }S\\Lambda { S }^{ -1 }=S{ \\Lambda  }^{ 2 }{ S }^{ -1 } $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The power need not be 2, but any *k* which will have S<sup>-1</sup> appearing *k*-1 times"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We thus have the following theorems\n",
    "$$ { A }^{ k }\\rightarrow 0\\quad \\because \\quad k\\rightarrow \\infty ;\\quad \\left| { \\lambda  }_{ i } \\right| $$\n",
    "* ...and...\n",
    "* If *k* is a positive integer, &#955; is an eigenvalue of the matrix A, and **x** is a corresponding eigenvector, then &#955;<sup>k</sup> is an eigenvalue of A<sup>k</sup> and **x** is a corresponding eigenvector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What makes a matrix diagonalizable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* In discussing diagonalization we are concerned with finding a basis for &#8477;<sup>n</sup> that consists of eigenvectors of a given square matrix of size *n*\n",
    "* These bases can tell us about geometric properties of A and it can simplify numerical computations involving A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We need to answer two question (which are actually the same)\n",
    "    * Given a square matrix of size *n*, is there a basis for &#8477;<sup>n</sup> consisting of eigenvectors?\n",
    "    * Given a square matrix of size *n*, it there and invertible matrix S, such that S<sup>-1</sup>AS is a diagonal matrix? (It is the same matrix S referred to above)\n",
    "* If such a matrix S exists, it is said to diagonalize A (and we will call the resultant diagonal matrix D)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* In short the answer to the above question(s) is yes if A has *n* independent eigenvectors\n",
    "    * This happens if all &#955;<sup>'s</sup> are different (none are repeated) (not totally excluded if they are repeated though)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* If they are repeated, we still might have independent eigenvectors, i.e. any size identity matrix (because it is already diagonal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1 & 0 & 0 & 0 & 0\\\\0 & 1 & 0 & 0 & 0\\\\0 & 0 & 1 & 0 & 0\\\\0 & 0 & 0 & 1 & 0\\\\0 & 0 & 0 & 0 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1  0  0  0  0⎤\n",
       "⎢             ⎥\n",
       "⎢0  1  0  0  0⎥\n",
       "⎢             ⎥\n",
       "⎢0  0  1  0  0⎥\n",
       "⎢             ⎥\n",
       "⎢0  0  0  1  0⎥\n",
       "⎢             ⎥\n",
       "⎣0  0  0  0  1⎦"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = eye(5)\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{Bmatrix}1 : 5\\end{Bmatrix}$$"
      ],
      "text/plain": [
       "{1: 5}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.eigenvals()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\begin{pmatrix}1, & 5, & \\begin{bmatrix}\\left[\\begin{matrix}1\\\\0\\\\0\\\\0\\\\0\\end{matrix}\\right], & \\left[\\begin{matrix}0\\\\1\\\\0\\\\0\\\\0\\end{matrix}\\right], & \\left[\\begin{matrix}0\\\\0\\\\1\\\\0\\\\0\\end{matrix}\\right], & \\left[\\begin{matrix}0\\\\0\\\\0\\\\1\\\\0\\end{matrix}\\right], & \\left[\\begin{matrix}0\\\\0\\\\0\\\\0\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎛1, 5, ⎡⎡1⎤, ⎡0⎤, ⎡0⎤, ⎡0⎤, ⎡0⎤⎤⎞⎤\n",
       "⎢⎜      ⎢⎢ ⎥  ⎢ ⎥  ⎢ ⎥  ⎢ ⎥  ⎢ ⎥⎥⎟⎥\n",
       "⎢⎜      ⎢⎢0⎥  ⎢1⎥  ⎢0⎥  ⎢0⎥  ⎢0⎥⎥⎟⎥\n",
       "⎢⎜      ⎢⎢ ⎥  ⎢ ⎥  ⎢ ⎥  ⎢ ⎥  ⎢ ⎥⎥⎟⎥\n",
       "⎢⎜      ⎢⎢0⎥  ⎢0⎥  ⎢1⎥  ⎢0⎥  ⎢0⎥⎥⎟⎥\n",
       "⎢⎜      ⎢⎢ ⎥  ⎢ ⎥  ⎢ ⎥  ⎢ ⎥  ⎢ ⎥⎥⎟⎥\n",
       "⎢⎜      ⎢⎢0⎥  ⎢0⎥  ⎢0⎥  ⎢1⎥  ⎢0⎥⎥⎟⎥\n",
       "⎢⎜      ⎢⎢ ⎥  ⎢ ⎥  ⎢ ⎥  ⎢ ⎥  ⎢ ⎥⎥⎟⎥\n",
       "⎣⎝      ⎣⎣0⎦  ⎣0⎦  ⎣0⎦  ⎣0⎦  ⎣1⎦⎦⎠⎦"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.eigenvects()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Here we look at a triangular matrix, though"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{Bmatrix}2 : 2\\end{Bmatrix}$$"
      ],
      "text/plain": [
       "{2: 2}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Matrix([[2, 1], [0, 2]])\n",
    "A.eigenvals()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\begin{pmatrix}2, & 2, & \\begin{bmatrix}\\left[\\begin{matrix}1\\\\0\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎛2, 2, ⎡⎡1⎤⎤⎞⎤\n",
       "⎢⎜      ⎢⎢ ⎥⎥⎟⎥\n",
       "⎣⎝      ⎣⎣0⎦⎦⎠⎦"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.eigenvects()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We can use python™ code to calculate the diagonalized matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}3 & -2 & 4 & -2\\\\5 & 3 & -3 & -2\\\\5 & -2 & 2 & -2\\\\5 & -2 & -3 & 3\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡3  -2  4   -2⎤\n",
       "⎢             ⎥\n",
       "⎢5  3   -3  -2⎥\n",
       "⎢             ⎥\n",
       "⎢5  -2  2   -2⎥\n",
       "⎢             ⎥\n",
       "⎣5  -2  -3  3 ⎦"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Matrix([[3, -2,  4, -2], [5,  3, -3, -2], [5, -2,  2, -2], [5, -2, -3, 3]])\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "S, D = A.diagonalize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0 & 1 & 1 & 0\\\\1 & 1 & 1 & -1\\\\1 & 1 & 1 & 0\\\\1 & 1 & 0 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡0  1  1  0 ⎤\n",
       "⎢           ⎥\n",
       "⎢1  1  1  -1⎥\n",
       "⎢           ⎥\n",
       "⎢1  1  1  0 ⎥\n",
       "⎢           ⎥\n",
       "⎣1  1  0  1 ⎦"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S # S, such that A = S times D times the inverse of S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-2 & 0 & 0 & 0\\\\0 & 3 & 0 & 0\\\\0 & 0 & 5 & 0\\\\0 & 0 & 0 & 5\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-2  0  0  0⎤\n",
       "⎢           ⎥\n",
       "⎢0   3  0  0⎥\n",
       "⎢           ⎥\n",
       "⎢0   0  5  0⎥\n",
       "⎢           ⎥\n",
       "⎣0   0  0  5⎦"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D # The diagonal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S * D * S.inv() == A # Checking to see if our statement above is correct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S.inv() * A * S == D # Checking to see if our statement above is correct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{Bmatrix}-2 : 1, & 3 : 1, & 5 : 2\\end{Bmatrix}$$"
      ],
      "text/plain": [
       "{-2: 1, 3: 1, 5: 2}"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.eigenvals()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Remember &#923; from above?\n",
    "    * The eigenvalues are precisely the entries along the main diagonal of the diagonal matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* To produce the required diagonal matrix manually then will require computing *n* linearly independent eigenvectors for matrix A of size *n* (assuming that it is diagonalizable), creating a matrix with its columns equal to these eigenvectors (called matrix S) and performing the equation S<sup>-1</sup>AS to calculate the diagonal matrix D ( or &#923;)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Back to the topic of what makes a matrix diagonalizable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Suppose we have an equation that starts with some vector and every subsequent vector is a matrix A time the previous vector\n",
    "$$ \\mathbf{u}_{k+1}={A}\\mathbf{u}_{k} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* From this arises the following\n",
    "$$ { \\mathbf { u }  }_{ 1 }=A{ \\mathbf { u }  }_{ 0 }\\\\ { \\mathbf { u }  }_{ 2 }=A{ A\\mathbf { u }  }_{ 0 }={ A }^{ 2 }{ \\mathbf { u }  }_{ 0 }\\\\ { \\mathbf { u }  }_{ k }={ A }^{ k }{ \\mathbf { u }  }_{ 0 } $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* To really solve this problem, rewrite **u**<sub>0</sub> as follows (a certain scalar times an eigenvector)\n",
    "$$ { \\mathbf { u }  }_{ 0 }={ c }_{ 1 }\\mathbf{ x }_{ 1 }+{ c }_{ 2 }\\mathbf{ x }_{ 2 }+\\dots +{ c }_{ n }\\mathbf{ x }_{ n } = {S}\\mathbf{c} $$\n",
    "* Where the S**c** is a linear combination of the individual eigenvectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Now multiply both sides by A\n",
    "$$ A{ \\mathbf { u }  }_{ 0 }={ c }_{ 1 }{A}\\mathbf{ x }_{ 1 }+{ c }_{ 2 }{A}\\mathbf{ x }_{ 2 }+\\dots +{ c }_{ n }{A}\\mathbf{ x }_{ n } \\\\ A{ \\mathbf { u }  }_{ 0 }={ c }_{ 1 }{ \\lambda  }_{ 1 }\\mathbf{ x }_{ 1 }+{ c }_{ 2 }{ \\lambda  }_{ 2 }\\mathbf{ x }_{ 2 }+\\dots +{ c }_{ n }{ \\lambda  }_{ n }\\mathbf{ x }_{ n } $$\n",
    "* Taking a power of A now (i.e. *k*) would be akin to taking each eigenvalue to that power\n",
    "$$ {A}^{k}{ \\mathbf { u }  }_{ 0 }={ c }_{ 1 }{ \\lambda  }_{ 1 }^{k}\\mathbf{ x }_{ 1 }+{ c }_{ 2 }{ \\lambda  }_{ 2 }^{k}\\mathbf{ x }_{ 2 }+\\dots +{ c }_{ n }{ \\lambda  }_{ n }^{k}\\mathbf{ x }_{ n } $$\n",
    "* This can be written as\n",
    "$$ \\mathbf{u}_{k} = {A}^{k}\\mathbf{u}_{0}={\\Lambda}^{k}{S}\\mathbf{c} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "* As an example consider the Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, ...\n",
    "* What would the 100<sup>th</sup> number be?\n",
    "* Consider the following\n",
    "$$ {F}_{k+2}={F}_{k+1}+{F}_{k} $$\n",
    "* This is a (second-order) difference equation; think of this example as similar to a second-order differential equation (without derivatives)\n",
    "* By adding a second equation F<sub>k+1</sub>=F<sub>k+1</sub>, consider **u**<sub>k</sub> to be the following vector\n",
    "$$ \\mathbf{u}_{k}=\\begin{bmatrix} {F}_{k+1} \\\\ {F}_{k} \\end{bmatrix} $$\n",
    "* This means the following\n",
    "$$ \\mathbf{u}_{k+1}=\\begin{bmatrix} 1 & 1 \\\\ 1 & 0 \\end{bmatrix} \\begin{bmatrix} {F}_{k+1} \\\\ {F}_{k} \\end{bmatrix}=\\begin{bmatrix} {F}_{k+1}+{F}_{k} \\\\ {F}_{k+1} \\end{bmatrix} \\\\ \\mathbf{u}_{k+1}=\\begin{bmatrix} 1 & 1 \\\\ 1 & 0 \\end{bmatrix}\\mathbf{u}_{k} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1 & 1\\\\1 & 0\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1  1⎤\n",
       "⎢    ⎥\n",
       "⎣1  0⎦"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Matrix([[1, 1], [1, 0]])\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{Bmatrix}\\frac{1}{2} + \\frac{\\sqrt{5}}{2} : 1, & - \\frac{\\sqrt{5}}{2} + \\frac{1}{2} : 1\\end{Bmatrix}$$"
      ],
      "text/plain": [
       "⎧      ___         ___       ⎫\n",
       "⎪1   ╲╱ 5        ╲╱ 5    1   ⎪\n",
       "⎨─ + ─────: 1, - ───── + ─: 1⎬\n",
       "⎪2     2           2     2   ⎪\n",
       "⎩                            ⎭"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.eigenvals()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\begin{pmatrix}\\frac{1}{2} + \\frac{\\sqrt{5}}{2}, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}- \\frac{1}{- \\frac{\\sqrt{5}}{2} + \\frac{1}{2}}\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}, & \\begin{pmatrix}- \\frac{\\sqrt{5}}{2} + \\frac{1}{2}, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}- \\frac{1}{\\frac{1}{2} + \\frac{\\sqrt{5}}{2}}\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎛      ___                    ⎞  ⎛    ___                      ⎞⎤\n",
       "⎢⎜1   ╲╱ 5      ⎡⎡    -1     ⎤⎤⎟  ⎜  ╲╱ 5    1     ⎡⎡   -1    ⎤⎤⎟⎥\n",
       "⎢⎜─ + ─────, 1, ⎢⎢───────────⎥⎥⎟, ⎜- ───── + ─, 1, ⎢⎢─────────⎥⎥⎟⎥\n",
       "⎢⎜2     2       ⎢⎢    ___    ⎥⎥⎟  ⎜    2     2     ⎢⎢      ___⎥⎥⎟⎥\n",
       "⎢⎜              ⎢⎢  ╲╱ 5    1⎥⎥⎟  ⎜                ⎢⎢1   ╲╱ 5 ⎥⎥⎟⎥\n",
       "⎢⎜              ⎢⎢- ───── + ─⎥⎥⎟  ⎜                ⎢⎢─ + ─────⎥⎥⎟⎥\n",
       "⎢⎜              ⎢⎢    2     2⎥⎥⎟  ⎜                ⎢⎢2     2  ⎥⎥⎟⎥\n",
       "⎢⎜              ⎢⎢           ⎥⎥⎟  ⎜                ⎢⎢         ⎥⎥⎟⎥\n",
       "⎣⎝              ⎣⎣     1     ⎦⎦⎠  ⎝                ⎣⎣    1    ⎦⎦⎠⎦"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.eigenvects()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "S, D = A.diagonalize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}\\frac{1}{2} + \\frac{\\sqrt{5}}{2} & 0\\\\0 & - \\frac{\\sqrt{5}}{2} + \\frac{1}{2}\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡      ___             ⎤\n",
       "⎢1   ╲╱ 5              ⎥\n",
       "⎢─ + ─────       0     ⎥\n",
       "⎢2     2               ⎥\n",
       "⎢                      ⎥\n",
       "⎢               ___    ⎥\n",
       "⎢             ╲╱ 5    1⎥\n",
       "⎢    0      - ───── + ─⎥\n",
       "⎣               2     2⎦"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* From above we remember the following\n",
    "$$ \\mathbf{u}_{k} = {A}^{k}\\mathbf{u}_{0}={\\Lambda}^{k}{S}\\mathbf{c} $$\n",
    "* We have **u**<sub>0</sub> contains the first two values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}573147844013817084101\\\\354224848179261915075\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡573147844013817084101⎤\n",
       "⎢                     ⎥\n",
       "⎣354224848179261915075⎦"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "u_zero =  Matrix([1, 0])\n",
    "u_100 = A ** 100 * u_zero\n",
    "u_100 # The top value is the 100th Fibonacci number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}5\\\\3\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡5⎤\n",
       "⎢ ⎥\n",
       "⎣3⎦"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "u_four = A ** 4 * u_zero\n",
    "u_four # If the first number is 0 the the fourth number would be the top value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example problem 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Find an equation for C<sup>k</sup> where C is given by the following matrix\n",
    "$$  $$\n",
    "* Calculate C<sup>100</sup> when *a*=*b*=-1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "a, b, k = symbols('a b k')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}- a + 2 b & a - b\\\\- 2 a + 2 b & 2 a - b\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡ -a + 2⋅b    a - b ⎤\n",
       "⎢                   ⎥\n",
       "⎣-2⋅a + 2⋅b  2⋅a - b⎦"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C = Matrix([[2 * b - a, a - b], [2 * b - 2 * a, 2 * a - b]])\n",
    "C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We remember the following\n",
    "$$ {A}^{k}={S}{\\Lambda}^{k}{S}^{-1} $$\n",
    "* Where &#923; is denoted by the computer variable D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "S, D = C.diagonalize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}- \\frac{2 a - 2 b}{- 3 a + 3 b + \\sqrt{\\left(a - b\\right)^{2}}} & \\frac{2 a - 2 b}{3 a - 3 b + \\sqrt{\\left(a - b\\right)^{2}}}\\\\1 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡       -2⋅(a - b)                   2⋅(a - b)        ⎤\n",
       "⎢──────────────────────────  ─────────────────────────⎥\n",
       "⎢                __________                 __________⎥\n",
       "⎢               ╱        2                 ╱        2 ⎥\n",
       "⎢-3⋅a + 3⋅b + ╲╱  (a - b)    3⋅a - 3⋅b + ╲╱  (a - b)  ⎥\n",
       "⎢                                                     ⎥\n",
       "⎣            1                           1            ⎦"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Python™ is not always good at simplifying these\n",
    "* If you look at it carefully you will note the following"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1 & \\frac{1}{2}\\\\1 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1  1/2⎤\n",
       "⎢      ⎥\n",
       "⎣1   1 ⎦"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = Matrix([[1, Rational(1, 2)], [1, 1]])\n",
    "S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}\\frac{a}{2} + \\frac{b}{2} - \\frac{1}{2} \\sqrt{\\left(a - b\\right)^{2}} & 0\\\\0 & \\frac{a}{2} + \\frac{b}{2} + \\frac{1}{2} \\sqrt{\\left(a - b\\right)^{2}}\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡           __________                       ⎤\n",
       "⎢          ╱        2                        ⎥\n",
       "⎢a   b   ╲╱  (a - b)                         ⎥\n",
       "⎢─ + ─ - ─────────────            0          ⎥\n",
       "⎢2   2         2                             ⎥\n",
       "⎢                                            ⎥\n",
       "⎢                                  __________⎥\n",
       "⎢                                 ╱        2 ⎥\n",
       "⎢                       a   b   ╲╱  (a - b)  ⎥\n",
       "⎢          0            ─ + ─ + ─────────────⎥\n",
       "⎣                       2   2         2      ⎦"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}b & 0\\\\0 & a\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡b  0⎤\n",
       "⎢    ⎥\n",
       "⎣0  a⎦"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = Matrix([[b, 0], [0, a]])\n",
    "D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* For the values given, we have the following"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "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": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C = Matrix([[-1, 0],  [0, -1]])\n",
    "C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "S, D = C.diagonalize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "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": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "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": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D ** 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "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": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S * (D ** 100) * S.inv()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "* Doing the same, but with eigenvalues and eigenvectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}- a + 2 b & a - b\\\\- 2 a + 2 b & 2 a - b\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡ -a + 2⋅b    a - b ⎤\n",
       "⎢                   ⎥\n",
       "⎣-2⋅a + 2⋅b  2⋅a - b⎦"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C = Matrix([[2 * b - a, a - b], [2 * b - 2 * a, 2 * a - b]])\n",
    "C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{Bmatrix}\\frac{a}{2} + \\frac{b}{2} - \\frac{1}{2} \\sqrt{\\left(a - b\\right)^{2}} : 1, & \\frac{a}{2} + \\frac{b}{2} + \\frac{1}{2} \\sqrt{\\left(a - b\\right)^{2}} : 1\\end{Bmatrix}$$"
      ],
      "text/plain": [
       "⎧           __________                __________   ⎫\n",
       "⎪          ╱        2                ╱        2    ⎪\n",
       "⎨a   b   ╲╱  (a - b)       a   b   ╲╱  (a - b)     ⎬\n",
       "⎪─ + ─ - ─────────────: 1, ─ + ─ + ─────────────: 1⎪\n",
       "⎩2   2         2           2   2         2         ⎭"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C.eigenvals()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* This simplifies the &#955;<sub>1</sub> = *b* and &#955;<sub>2</sub> = *a*\n",
    "* That makes &#923; (or D) the following"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}b & 0\\\\0 & a\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡b  0⎤\n",
       "⎢    ⎥\n",
       "⎣0  a⎦"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = Matrix([[b, 0], [0, a]])\n",
    "D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\begin{pmatrix}\\frac{a}{2} + \\frac{b}{2} - \\frac{1}{2} \\sqrt{\\left(a - b\\right)^{2}}, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}- \\frac{a - b}{- \\frac{3 a}{2} + \\frac{3 b}{2} + \\frac{1}{2} \\sqrt{\\left(a - b\\right)^{2}}}\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}, & \\begin{pmatrix}\\frac{a}{2} + \\frac{b}{2} + \\frac{1}{2} \\sqrt{\\left(a - b\\right)^{2}}, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}- \\frac{a - b}{- \\frac{3 a}{2} + \\frac{3 b}{2} - \\frac{1}{2} \\sqrt{\\left(a - b\\right)^{2}}}\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎛           __________                                    ⎞  ⎛           ____\n",
       "⎢⎜          ╱        2                                     ⎟  ⎜          ╱    \n",
       "⎢⎜a   b   ╲╱  (a - b)       ⎡⎡         -(a - b)          ⎤⎤⎟  ⎜a   b   ╲╱  (a \n",
       "⎢⎜─ + ─ - ─────────────, 1, ⎢⎢───────────────────────────⎥⎥⎟, ⎜─ + ─ + ───────\n",
       "⎢⎜2   2         2           ⎢⎢                 __________⎥⎥⎟  ⎜2   2         2\n",
       "⎢⎜                          ⎢⎢                ╱        2 ⎥⎥⎟  ⎜               \n",
       "⎢⎜                          ⎢⎢  3⋅a   3⋅b   ╲╱  (a - b)  ⎥⎥⎟  ⎜               \n",
       "⎢⎜                          ⎢⎢- ─── + ─── + ─────────────⎥⎥⎟  ⎜               \n",
       "⎢⎜                          ⎢⎢   2     2          2      ⎥⎥⎟  ⎜               \n",
       "⎢⎜                          ⎢⎢                           ⎥⎥⎟  ⎜               \n",
       "⎣⎝                          ⎣⎣             1             ⎦⎦⎠  ⎝               \n",
       "\n",
       "______                                    ⎞⎤\n",
       "    2                                     ⎟⎥\n",
       "- b)       ⎡⎡         -(a - b)          ⎤⎤⎟⎥\n",
       "──────, 1, ⎢⎢───────────────────────────⎥⎥⎟⎥\n",
       "           ⎢⎢                 __________⎥⎥⎟⎥\n",
       "           ⎢⎢                ╱        2 ⎥⎥⎟⎥\n",
       "           ⎢⎢  3⋅a   3⋅b   ╲╱  (a - b)  ⎥⎥⎟⎥\n",
       "           ⎢⎢- ─── + ─── - ─────────────⎥⎥⎟⎥\n",
       "           ⎢⎢   2     2          2      ⎥⎥⎟⎥\n",
       "           ⎢⎢                           ⎥⎥⎟⎥\n",
       "           ⎣⎣             1             ⎦⎦⎠⎦"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C.eigenvects() # The solution is two tuples, with each being eigenvalue, eigenvector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* This simplifies to the following eigenvalue matrix S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1 & \\frac{1}{2}\\\\1 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1  1/2⎤\n",
       "⎢      ⎥\n",
       "⎣1   1 ⎦"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = Matrix([[1, Rational(1, 2)], [1, 1]])\n",
    "S"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We can see if we can get back to C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}- a + 2 b & a - b\\\\- 2 a + 2 b & 2 a - b\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡ -a + 2⋅b    a - b ⎤\n",
       "⎢                   ⎥\n",
       "⎣-2⋅a + 2⋅b  2⋅a - b⎦"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S * D * S.inv()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S * D * S.inv() == C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Python™ won't to D<sup>k</sup> for you, but it's easy to do yourself"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}b^{k} & 0\\\\0 & a^{k}\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡ k    ⎤\n",
       "⎢b   0 ⎥\n",
       "⎢      ⎥\n",
       "⎢     k⎥\n",
       "⎣0   a ⎦"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = Matrix([[b ** k, 0], [0, a ** k]])\n",
    "D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Now we can compute S&#923;S<sup>-1</sup>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}- a^{k} + 2 b^{k} & a^{k} - b^{k}\\\\- 2 a^{k} + 2 b^{k} & 2 a^{k} - b^{k}\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡    k      k     k    k ⎤\n",
       "⎢ - a  + 2⋅b     a  - b  ⎥\n",
       "⎢                        ⎥\n",
       "⎢     k      k     k    k⎥\n",
       "⎣- 2⋅a  + 2⋅b   2⋅a  - b ⎦"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S * D * S.inv()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Placing the given values into this equation will give you the same solution for C<sup>100</sup> as above"
   ]
  },
  {
   "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
}