III_05_Singular_value_decomposition.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ This notebook is part of lecture 29 *Singular value decomposition* 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": false
   },
   "outputs": [],
   "source": [
    "from sympy import init_printing, Matrix, symbols, sqrt, 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": [
    "+ This chapter starts with explanations using sympy\n",
    "+ A proper method using numpy and sympy is described in the example problem at the end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Singular value decomposition (SVD)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Derivation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* This is the final form of matrix factorization\n",
    "* The factors are an orthogonal matrix A, a diagonal matrix &Sigma;, and an orthogonal matrix V\n",
    "$$ {A}={U}{\\Sigma}{V}^{T} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ In case the matrix A is symmetric positive definite, the decomposition is akin to the following\n",
    "$$  {A}={Q}{\\Lambda}{Q}^{T} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Consider a vector *v*<sub>1</sub> in &#8477;<sup>n</sup> row space, transformed into a vector *u*<sub>1</sub> in &#8477;<sup>m</sup> column space by the matrix A\n",
    "$$ {u}_{1}={A}{v}_{1} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* What we are looking for is an orthogonal basis in &#8477;<sup>n</sup> row space, transformed into an orthogonal basis in &#8477;<sup>m</sup> column space\n",
    "$$ {u}_{1}={A}{v}_{1} \\\\ { v }_{ 1 }\\bot { v }_{ 2 };{ u }_{ 1 }\\bot { u }_{ 2 }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* It's easy to calculate an orthogonal basis in the row space using Gram-Schmidt\n",
    "* Now, though, we need something special in A that would ensure that the basis *u*<sub>i</sub> in in &#8477;<sup>m</sup> column space is also orthogonal (and at the same time make it orthonormal, so that *v*<sub>i</sub> ends up as &sigma;<sub>i</sub>*u*<sub>i</sub>)\n",
    "* The two nullspaces are not required\n",
    "* So, we are looking for the following\n",
    "$$ A\\begin{bmatrix} \\vdots  & \\vdots  & \\vdots  & \\vdots  \\\\ { v }_{ 1 } & { v }_{ 2 } & \\cdots  & { v }_{ r } \\\\ \\vdots  & \\vdots  & \\vdots  & \\vdots  \\end{bmatrix}=\\begin{bmatrix} \\vdots  & \\vdots  & \\vdots  & \\vdots  \\\\ { u }_{ 1 } & u_{ 2 } & \\cdots  & { u }_{ r } \\\\ \\vdots  & \\vdots  & \\vdots  & \\vdots  \\end{bmatrix}\\begin{bmatrix} { \\sigma  }_{ 1 } & \\quad  & \\quad  & \\quad  & \\quad  \\\\ \\quad  & { \\sigma  }_{ 2 } & \\quad  & \\quad  & \\quad  \\\\ \\quad  & \\quad  & \\quad \\ddots  & \\quad  & \\quad  \\\\ \\quad  & \\quad  & \\quad  & { \\sigma  }_{ r }\\quad  & \\quad  \\\\ \\quad  & \\quad  & \\quad  & \\quad  & \\left( 0 \\right)  \\end{bmatrix} \\\\ {A}{V}={U}{\\Sigma}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ In the case that we are not changing spaces V and U would be the same matrix Q (and then Q<sup>-1</sup>)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example problem explaining the derivation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Look at the next matrix A that is square and invertible (i.e. rank 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}4 & 4\\\\-3 & 3\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡4   4⎤\n",
       "⎢     ⎥\n",
       "⎣-3  3⎦"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Matrix([[4, 4], [-3, 3]])\n",
    "A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We are looking for *v*<sub>1</sub> and *v*<sub>2</sub> in the &#8477;<sup>2</sup> rowspace and *u*<sub>1</sub> and *u*<sub>2</sub> in the &#8477;<sup>2</sup> columnspace, as well as the scaling factors *&sigma;*<sub>1</sub>>0 and *&sigma;*<sub>2</sub>>0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Just to be complete, we extend V until *v*<sub>n</sub> with zero columns and U with zero columns until *u*<sub>m</sub>, as well as zeros for &Sigma; to include the nullspaces"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Now A is not symmetric so that their eigenvectors are not orthogonal (Q), so we can't go that route"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ From above we have the following and because V is square and orthogonal we have\n",
    "$$ {A}={U}{\\Sigma}{V}^{-1} \\\\ {A}={U}{\\Sigma}{V}^{T} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Multiplying both sides by A<sup>T</sup> we will have a left-hand side that is square and definte (semi)definte\n",
    "$$ A=U\\Sigma { V }^{ T }\\\\ { A }^{ T }A=V{ \\Sigma  }^{ T }{ U }^{ T }U\\Sigma { V }^{ T }\\\\ \\because \\quad { U }^{ T }U=I\\\\ \\because \\quad { \\Sigma  }^{ T }\\Sigma =\\dots { \\sigma  }_{ i }^{ 2 }\\dots \\\\ { A }^{ T }A=V{ \\Sigma  }^{ T }\\Sigma { V }^{ T } $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Because A<sup>T</sup>A is now definite (semi)positive, we have a perfect situation akin to being able to use Q&Lambda;Q<sup>T</sup>\n",
    "+ The eigenvalues are the squares of the &sigma;<sub>i</sub> values\n",
    "+ To get U we use AA<sup>T</sup> and use its eigenvalues and eigenvectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* All of this is easy to accomplish with the mpmath submodule of sympy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sympy.mpmath import svd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "U, S, V = svd(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1.0 & 3.33066907387547 \\cdot 10^{-16}\\\\1.11022302462516 \\cdot 10^{-16} & -1.0\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡        1.0           3.33066907387547e-16⎤\n",
       "⎢                                          ⎥\n",
       "⎣1.11022302462516e-16          -1.0        ⎦"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U # The numbers round to zero!!! Please see it as zero"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix(\n",
       "[['5.65685424949238'],\n",
       " ['4.24264068711928']])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S # Not the final Sigma matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix(\n",
       "[['0.707106781186547', '0.707106781186548'],\n",
       " ['0.707106781186548', '-0.707106781186547']])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ There are square roots, so the values are given instead of symbols"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Now let's do it step-by-step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}25 & 7\\\\7 & 25\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡25  7 ⎤\n",
       "⎢      ⎥\n",
       "⎣7   25⎦"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.transpose() * A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{Bmatrix}18 : 1, & 32 : 1\\end{Bmatrix}$$"
      ],
      "text/plain": [
       "{18: 1, 32: 1}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A.transpose() * A).eigenvals()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\begin{pmatrix}18, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}-1\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}, & \\begin{pmatrix}32, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}1\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎛18, 1, ⎡⎡-1⎤⎤⎞, ⎛32, 1, ⎡⎡1⎤⎤⎞⎤\n",
       "⎢⎜       ⎢⎢  ⎥⎥⎟  ⎜       ⎢⎢ ⎥⎥⎟⎥\n",
       "⎣⎝       ⎣⎣1 ⎦⎦⎠  ⎝       ⎣⎣1⎦⎦⎠⎦"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A.transpose() * A).eigenvects()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* These are not normalized, though\n",
    "* Also remember to take the square roots of the eigenvalues\n",
    "* ... and to add zeros to incorporate the correct size for *m* and *n*\n",
    "* ... and to take the transpose"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Now let's tackle U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}32 & 0\\\\0 & 18\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡32  0 ⎤\n",
       "⎢      ⎥\n",
       "⎣0   18⎦"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A * A.transpose()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{Bmatrix}18 : 1, & 32 : 1\\end{Bmatrix}$$"
      ],
      "text/plain": [
       "{18: 1, 32: 1}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A * A.transpose()).eigenvals()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The eigenvalues are always the same"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\begin{pmatrix}18, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}0\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}, & \\begin{pmatrix}32, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}1\\\\0\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎛18, 1, ⎡⎡0⎤⎤⎞, ⎛32, 1, ⎡⎡1⎤⎤⎞⎤\n",
       "⎢⎜       ⎢⎢ ⎥⎥⎟  ⎜       ⎢⎢ ⎥⎥⎟⎥\n",
       "⎣⎝       ⎣⎣1⎦⎦⎠  ⎝       ⎣⎣0⎦⎦⎠⎦"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A * A.transpose()).eigenvects()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Also remember to normalize (see example problem below)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We now have U, &Sigma; and V<sup>T</sup> (although &Sigma; must still be constructed; see below)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example problem to explain the derivation for dependent rows, columns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Let's consider this rank=1, 2&times;2 singular matrix\n",
    "+ The rowspace is just a line (the second row is a constant multiple of the first)\n",
    "+ The nullspace of this row picture is a line perpendicular to this\n",
    "+ The columnspace is also on a line, with the nullspace of A<sup>T</sup> being a line perpendicular to this"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}4 & 3\\\\8 & 6\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡4  3⎤\n",
       "⎢    ⎥\n",
       "⎣8  6⎦"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Matrix([[4, 3], [8, 6]])\n",
    "A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Let's use *svd*() first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "U, S, V = svd(A, full_matrices = True, compute_uv = True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* This is likely to be different to the value you calculate for U\n",
    "* We are talking unit basis vectors, though, which can be in a different direction depending on your choice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-0.447213595499958 & -0.894427190999916\\\\-0.894427190999916 & 0.447213595499958\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-0.447213595499958  -0.894427190999916⎤\n",
       "⎢                                      ⎥\n",
       "⎣-0.894427190999916  0.447213595499958 ⎦"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix(\n",
       "[['11.1803398874989'],\n",
       " ['0.0']])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Note that the size of our &Sigma; matrix is wrong\n",
    "+ It has to be 2&times;2 and we have to create it from this info\n",
    "+ Since A has rank = 1 and all off-diagonal entries must be zero, we will only have a value in the first row, first column position\n",
    "+ Below I show you how to correct this"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix(\n",
       "[['-0.8', '-0.6'],\n",
       " ['-0.6', '0.8']])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}80 & 60\\\\60 & 45\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡80  60⎤\n",
       "⎢      ⎥\n",
       "⎣60  45⎦"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.transpose() * A # Which will be symmetric positive definite and of rank = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{Bmatrix}0 : 1, & 125 : 1\\end{Bmatrix}$$"
      ],
      "text/plain": [
       "{0: 1, 125: 1}"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A.transpose() * A).eigenvals() # One eigenvalue will be zero and the other must then be the trace"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\begin{pmatrix}0, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}- \\frac{3}{4}\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}, & \\begin{pmatrix}125, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}\\frac{4}{3}\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎛0, 1, ⎡⎡-3/4⎤⎤⎞, ⎛125, 1, ⎡⎡4/3⎤⎤⎞⎤\n",
       "⎢⎜      ⎢⎢    ⎥⎥⎟  ⎜        ⎢⎢   ⎥⎥⎟⎥\n",
       "⎣⎝      ⎣⎣ 1  ⎦⎦⎠  ⎝        ⎣⎣ 1 ⎦⎦⎠⎦"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A.transpose() * A).eigenvects()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}25 & 50\\\\50 & 100\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡25  50 ⎤\n",
       "⎢       ⎥\n",
       "⎣50  100⎦"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A * A.transpose()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{Bmatrix}0 : 1, & 125 : 1\\end{Bmatrix}$$"
      ],
      "text/plain": [
       "{0: 1, 125: 1}"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A * A.transpose()).eigenvals()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\begin{pmatrix}0, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}-2\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}, & \\begin{pmatrix}125, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}\\frac{1}{2}\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎛0, 1, ⎡⎡-2⎤⎤⎞, ⎛125, 1, ⎡⎡1/2⎤⎤⎞⎤\n",
       "⎢⎜      ⎢⎢  ⎥⎥⎟  ⎜        ⎢⎢   ⎥⎥⎟⎥\n",
       "⎣⎝      ⎣⎣1 ⎦⎦⎠  ⎝        ⎣⎣ 1 ⎦⎦⎠⎦"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A * A.transpose()).eigenvects()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Inserted below is the three resultant matrices from our calculations above (normalized, etc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{pmatrix}\\left[\\begin{matrix}\\frac{\\sqrt{5}}{5} & \\frac{2 \\sqrt{5}}{5}\\\\\\frac{2 \\sqrt{5}}{5} & \\frac{\\sqrt{5}}{5}\\end{matrix}\\right], & \\left[\\begin{matrix}5 \\sqrt{5} & 0\\\\0 & 0\\end{matrix}\\right], & \\left[\\begin{matrix}0.8 & 0.6\\\\0.6 & -0.8\\end{matrix}\\right]\\end{pmatrix}$$"
      ],
      "text/plain": [
       "⎛⎡   ___       ___⎤                           ⎞\n",
       "⎜⎢ ╲╱ 5    2⋅╲╱ 5 ⎥  ⎡    ___   ⎤             ⎟\n",
       "⎜⎢ ─────   ───────⎥, ⎢5⋅╲╱ 5   0⎥, ⎡0.8  0.6 ⎤⎟\n",
       "⎜⎢   5        5   ⎥  ⎢          ⎥  ⎢         ⎥⎟\n",
       "⎜⎢                ⎥  ⎣   0     0⎦  ⎣0.6  -0.8⎦⎟\n",
       "⎜⎢    ___     ___ ⎥                           ⎟\n",
       "⎜⎢2⋅╲╱ 5    ╲╱ 5  ⎥                           ⎟\n",
       "⎜⎢───────   ───── ⎥                           ⎟\n",
       "⎝⎣   5        5   ⎦                           ⎠"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Matrix([[1 / sqrt(5), 2 / sqrt(5)], [2 / sqrt(5), 1 / sqrt(5)]]), Matrix([[sqrt(125), 0], [0, 0]]), Matrix([[0.8, 0.6], [0.6, -0.8]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Now let me show you how to correct the *svd*() solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-0.447213595499958 & -0.894427190999916\\\\-0.894427190999916 & 0.447213595499958\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-0.447213595499958  -0.894427190999916⎤\n",
       "⎢                                      ⎥\n",
       "⎣-0.894427190999916  0.447213595499958 ⎦"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix(\n",
       "[['11.1803398874989'],\n",
       " ['0.0']])"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}11.1803398874989 & 0\\\\0 & 0\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡11.1803398874989  0⎤\n",
       "⎢                   ⎥\n",
       "⎣       0          0⎦"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = Matrix([[11.1803398874989, 0], [0, 0]])\n",
    "S # Composed by hand (proper method further below)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix(\n",
       "[['-0.8', '-0.6'],\n",
       " ['-0.6', '0.8']])"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-0.8 & -0.6\\\\-0.6 & 0.8\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-0.8  -0.6⎤\n",
       "⎢          ⎥\n",
       "⎣-0.6  0.8 ⎦"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V = Matrix([[-0.8, -0.6], [-0.6, 0.8]])\n",
    "V # Remember that this is actually V transpose"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Let's calculate A&Sigma;V<sup>T</sup>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}3.99999999999998 & 2.99999999999999\\\\7.99999999999996 & 5.99999999999997\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡3.99999999999998  2.99999999999999⎤\n",
       "⎢                                  ⎥\n",
       "⎣7.99999999999996  5.99999999999997⎦"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U * S * V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Compensating for rounding, this is the original matrix A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ The orthonormal basis for the rowspace is\n",
    "$$ {v}_{1},{v}_{2},\\dots,{v}_{r} $$\n",
    "+ The orthonormal basis for the columnspace is\n",
    "$$ {u}_{1},{u}_{2},\\dots,{u}_{r} $$\n",
    "+ The orthonormal basis for the nullspace is\n",
    "$$ {v}_{r+1},{v}_{r+2},\\dots,{v}_{n} $$\n",
    "+ The orthonormal basis for the nullspace of A<sup>T</sup>\n",
    "$$ {u}_{r+1},{u}_{r+2},\\dots,{u}_{m} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example problem 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Find the singular value decomposition of the matrix\n",
    "$$ \\begin{bmatrix}5&5\\\\-1&7\\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ First off, I'll show you how to make proper use of numpy and scipy (as opposed to sympy) to solve singular value decomposition problems"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from numpy import matrix, transpose # Importing the matrix object and the \n",
    "# transpose object from numerical python (numpy)\n",
    "from numpy.linalg import svd, det # Importing the svd and determinant\n",
    "# methods from the linalg submodule \n",
    "from scipy.linalg import diagsvd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "function"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(transpose) # Type tells us what 'something' is (sometimes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 5,  5],\n",
       "        [-1,  7]])"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C = matrix([[5, 5], [-1, 7]]) # Using the numpy matrix object\n",
    "C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We can see from the determinant that the rows and columns are independent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$40.0$$"
      ],
      "text/plain": [
       "40.0"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "det(C) # Notice the difference in syntax"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Let's calculate U by looking at A<sup>T</sup>A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[26, 18],\n",
       "        [18, 74]])"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transpose(C) *C # Notice the difference in synmtax"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ This is symmetric, positive definite\n",
    "+ One eigenvalue will be 0 and the other, the trace (since they (the eigenvalues) must sum to the trace)\n",
    "+ Remember that the eigenvalues are the squares of the *&sigma;*<sub>i</sub> values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Now let's put numpy and sympy to good use"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "U, S, VT = svd(C) # I use the computer variable VT to remind us that\n",
    "# this is the transpose of V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ S will only indicate the eigenvalues and must be converted to the correct sized matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{pmatrix}2, & 2\\end{pmatrix}$$"
      ],
      "text/plain": [
       "(2, 2)"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M, N = C.shape # Shape returns a tuple (two values), indicating\n",
    "# row and column size\n",
    "M, N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 8.94427191,  0.        ],\n",
       "       [ 0.        ,  4.47213595]])"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sig = diagsvd(S, M, N) # Creating a m times n matrix from S\n",
    "Sig"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 0.31622777,  0.9486833 ],\n",
       "        [ 0.9486833 , -0.31622777]])"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "VT"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Let's check if it worked!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 5.,  5.],\n",
       "        [-1.,  7.]])"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U * Sig * VT"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's use good old sympy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}5 & 5\\\\-1 & 7\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡5   5⎤\n",
       "⎢     ⎥\n",
       "⎣-1  7⎦"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C = Matrix([[5, 5], [-1, 7]])\n",
    "C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ We need to work with a positive (semi)definite matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{pmatrix}\\left[\\begin{matrix}26 & 18\\\\18 & 74\\end{matrix}\\right], & 1600\\end{pmatrix}$$"
      ],
      "text/plain": [
       "⎛⎡26  18⎤, 1600⎞\n",
       "⎜⎢      ⎥      ⎟\n",
       "⎝⎣18  74⎦      ⎠"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CTC = C.transpose() * C # Using the computer variable CTC to remind that\n",
    "# it is C transpose times C\n",
    "CTC, CTC.det()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Let's look at the eigenvalues"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{Bmatrix}20 : 1, & 80 : 1\\end{Bmatrix}$$"
      ],
      "text/plain": [
       "{20: 1, 80: 1}"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CTC.eigenvals()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ &Sigma; will contain along its main diagonal the square root of these eigenvalues"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}2 \\sqrt{5} & 0\\\\0 & 4 \\sqrt{5}\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡    ___         ⎤\n",
       "⎢2⋅╲╱ 5      0   ⎥\n",
       "⎢                ⎥\n",
       "⎢             ___⎥\n",
       "⎣   0     4⋅╲╱ 5 ⎦"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sig = Matrix([[sqrt(20), 0], [0, sqrt(80)]])\n",
    "Sig"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ For V we require the eigenvectors of C<sup>T</sup>C\n",
    "+ We need to remember to normalize each vector (dividing each component by the length (norm) of that vector"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\begin{pmatrix}20, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}-3\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}, & \\begin{pmatrix}80, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}\\frac{1}{3}\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎛20, 1, ⎡⎡-3⎤⎤⎞, ⎛80, 1, ⎡⎡1/3⎤⎤⎞⎤\n",
       "⎢⎜       ⎢⎢  ⎥⎥⎟  ⎜       ⎢⎢   ⎥⎥⎟⎥\n",
       "⎣⎝       ⎣⎣1 ⎦⎦⎠  ⎝       ⎣⎣ 1 ⎦⎦⎠⎦"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CTC.eigenvects()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Let's normalize each *v*<sub>i</sub> by calculating the length (norm) of each"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\sqrt{10}$$"
      ],
      "text/plain": [
       "  ____\n",
       "╲╱ 10 "
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v1 = Matrix([-3, 1])\n",
    "v1.norm()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\frac{\\sqrt{10}}{3}$$"
      ],
      "text/plain": [
       "  ____\n",
       "╲╱ 10 \n",
       "──────\n",
       "  3   "
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v2 = Matrix([Rational(1, 3), 1])\n",
    "v2.norm()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ We'll get each element of V by dividing by these norms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{pmatrix}- \\frac{3 \\sqrt{10}}{10}, & \\frac{\\sqrt{10}}{10}\\end{pmatrix}$$"
      ],
      "text/plain": [
       "⎛     ____     ____⎞\n",
       "⎜-3⋅╲╱ 10    ╲╱ 10 ⎟\n",
       "⎜──────────, ──────⎟\n",
       "⎝    10        10  ⎠"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "-3 / v1.norm(), 1 / v1.norm()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{pmatrix}\\frac{\\sqrt{10}}{10}, & \\frac{3 \\sqrt{10}}{10}\\end{pmatrix}$$"
      ],
      "text/plain": [
       "⎛  ____      ____⎞\n",
       "⎜╲╱ 10   3⋅╲╱ 10 ⎟\n",
       "⎜──────, ────────⎟\n",
       "⎝  10       10   ⎠"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Rational(1, 3) / v2.norm(), 1 / v2.norm()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}- \\frac{3 \\sqrt{10}}{10} & \\frac{\\sqrt{10}}{10}\\\\\\frac{\\sqrt{10}}{10} & \\frac{3 \\sqrt{10}}{10}\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡     ____      ____ ⎤\n",
       "⎢-3⋅╲╱ 10     ╲╱ 10  ⎥\n",
       "⎢──────────   ────── ⎥\n",
       "⎢    10         10   ⎥\n",
       "⎢                    ⎥\n",
       "⎢    ____        ____⎥\n",
       "⎢  ╲╱ 10     3⋅╲╱ 10 ⎥\n",
       "⎢  ──────    ────────⎥\n",
       "⎣    10         10   ⎦"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V = Matrix([[-3 / sqrt(10), 1 / sqrt(10)], [1 / sqrt(10), 3 / sqrt(10)]])\n",
    "# Just remember to put the elements of V in the correct place\n",
    "V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Remember that it is equal to the transpose of V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V == V.transpose()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Now for U using CC<sup>T</sup>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}50 & 30\\\\30 & 50\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡50  30⎤\n",
       "⎢      ⎥\n",
       "⎣30  50⎦"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CCT = C * C.transpose() # Using the computer variable CCT\n",
    "CCT"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ The eigenvalues will be the same"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{Bmatrix}20 : 1, & 80 : 1\\end{Bmatrix}$$"
      ],
      "text/plain": [
       "{20: 1, 80: 1}"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CCT.eigenvals()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\begin{pmatrix}20, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}-1\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}, & \\begin{pmatrix}80, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}1\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎛20, 1, ⎡⎡-1⎤⎤⎞, ⎛80, 1, ⎡⎡1⎤⎤⎞⎤\n",
       "⎢⎜       ⎢⎢  ⎥⎥⎟  ⎜       ⎢⎢ ⎥⎥⎟⎥\n",
       "⎣⎝       ⎣⎣1 ⎦⎦⎠  ⎝       ⎣⎣1⎦⎦⎠⎦"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CCT.eigenvects()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "u1 = Matrix([-1, 1])\n",
    "u2 = Matrix([1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{pmatrix}- \\frac{\\sqrt{2}}{2}, & \\frac{\\sqrt{2}}{2}\\end{pmatrix}$$"
      ],
      "text/plain": [
       "⎛   ___     ___⎞\n",
       "⎜-╲╱ 2    ╲╱ 2 ⎟\n",
       "⎜───────, ─────⎟\n",
       "⎝   2       2  ⎠"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "-1 / u1.norm(), 1 / u1.norm()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{pmatrix}\\frac{\\sqrt{2}}{2}, & \\frac{\\sqrt{2}}{2}\\end{pmatrix}$$"
      ],
      "text/plain": [
       "⎛  ___    ___⎞\n",
       "⎜╲╱ 2   ╲╱ 2 ⎟\n",
       "⎜─────, ─────⎟\n",
       "⎝  2      2  ⎠"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 / u2.norm(), 1 / u2.norm()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}- \\frac{\\sqrt{2}}{2} & \\frac{\\sqrt{2}}{2}\\\\\\frac{\\sqrt{2}}{2} & \\frac{\\sqrt{2}}{2}\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡   ___     ___⎤\n",
       "⎢-╲╱ 2    ╲╱ 2 ⎥\n",
       "⎢───────  ─────⎥\n",
       "⎢   2       2  ⎥\n",
       "⎢              ⎥\n",
       "⎢   ___     ___⎥\n",
       "⎢ ╲╱ 2    ╲╱ 2 ⎥\n",
       "⎢ ─────   ─────⎥\n",
       "⎣   2       2  ⎦"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U = Matrix([[-sqrt(2) / 2, sqrt(2) / 2], [sqrt(2) / 2, sqrt(2) / 2]])\n",
    "# Just remember to put the elements of U in the correct place\n",
    "U"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Let's see if it worked!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}5 & 5\\\\-1 & 7\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡5   5⎤\n",
       "⎢     ⎥\n",
       "⎣-1  7⎦"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U * Sig * V"
   ]
  },
  {
   "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
}