III_02_Complex_matrices_FFT.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ This notebook is part of lecture 26 *Complex matrices and the fast Fourier transform* 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, I, sqrt, Rational\n",
    "from IPython.display import Image\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": [
    "# Complex vectors, matrices\n",
    "# Fast Fourier transform"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Complex vectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Consider the following vector with complex entries (from this point on I will not use the underscore to indicate a vector, so as not to create confusion with the bar, noting complex conjugate, instead, inferring from context)\n",
    "$$ {z} = \\begin{bmatrix} {z}_{1} \\\\ {z}_{2} \\\\ \\vdots \\\\ {z}_{n} \\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The length (actually length squared) of this vector is *no good*, since it should be positive\n",
    "$$ {z}^{T}{z} $$\n",
    "* Instead we consider the following\n",
    "$$ z\\bar { z } ={ \\left| { z } \\right|  }^{ 2 }\\\\ \\therefore \\quad \\bar { z } ^{ T }z\\\\ \\left[ { \\bar { z }  }_{ 1 },{ \\bar { z }  }_{ 2 },\\dots ,{ \\bar { z }  }_{ n } \\right] \\begin{bmatrix} { z }_{ 1 } \\\\ { z }_{ 2 } \\\\ \\vdots  \\\\ { z }_{ n } \\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1\\\\i\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1⎤\n",
       "⎢ ⎥\n",
       "⎣ⅈ⎦"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z = Matrix([1, I]) # I is the sympy symbol for the imaginary number i\n",
    "z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Let's calculate this manually"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\sqrt{2}$$"
      ],
      "text/plain": [
       "  ___\n",
       "╲╱ 2 "
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z.norm() # The length of a vector"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1\\\\- i\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1 ⎤\n",
       "⎢  ⎥\n",
       "⎣-ⅈ⎦"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z_cc = Matrix([1, -I])\n",
    "z_cc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left(\\left[\\begin{matrix}2\\end{matrix}\\right]\\right)^{\\frac{1}{2}}$$"
      ],
      "text/plain": [
       "     1/2\n",
       "([2])   "
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sqrt(z_cc.transpose() * z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Taking the transpose of the complex conjugate is called the Hermitian\n",
    "$$ {z}^{H}{z} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We can use the Hermitian for non-complex (or mixed complex) vectors **u** and **v** too\n",
    "$$ \\bar{y}^{T}{x} \\\\ {y}^{H}{x} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sympy.physics.quantum.dagger import Dagger # A fun way to quickly get the Hermitian"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1 & - i\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "[1  -ⅈ]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Dagger(z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left(\\left[\\begin{matrix}2\\end{matrix}\\right]\\right)^{\\frac{1}{2}}$$"
      ],
      "text/plain": [
       "     1/2\n",
       "([2])   "
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sqrt(Dagger(z) * z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Complex symmetric matrices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The transpose"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* If the symmetric matrix has complex entries then A<sup>T</sup>=A is *no good*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}2 & 3 + i\\\\3 - i & 5\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡  2    3 + ⅈ⎤\n",
       "⎢            ⎥\n",
       "⎣3 - ⅈ    5  ⎦"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Matrix([[2, 3 + I], [3 - I, 5]])\n",
    "A # A Hermitian matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.transpose() == A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}2 & 3 + i\\\\3 - i & 5\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡  2    3 + ⅈ⎤\n",
       "⎢            ⎥\n",
       "⎣3 - ⅈ    5  ⎦"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Dagger(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Dagger(A) == A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* This will work for real-values symmetric matrices as well"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}3 & 4\\\\4 & 2\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡3  4⎤\n",
       "⎢    ⎥\n",
       "⎣4  2⎦"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Matrix([[3, 4], [4, 2]])\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.transpose() == A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Dagger(A) == A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The eigenvalues and eigenvectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Back to the complex matrix A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}2 & 3 + i\\\\3 - i & 5\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡  2    3 + ⅈ⎤\n",
       "⎢            ⎥\n",
       "⎣3 - ⅈ    5  ⎦"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Matrix([[2, 3 + I], [3 - I, 5]])\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{Bmatrix}0 : 1, & 7 : 1\\end{Bmatrix}$$"
      ],
      "text/plain": [
       "{0: 1, 7: 1}"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.eigenvals()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ A=\\begin{bmatrix} 2 & 3+i \\\\ 3-i & 5 \\end{bmatrix}\\\\ A-\\lambda I=\\underline { 0 } \\\\ \\left| \\begin{bmatrix} 2 & 3+i \\\\ 3-i & 5 \\end{bmatrix}-\\begin{bmatrix} \\lambda  & 0 \\\\ 0 & \\lambda  \\end{bmatrix} \\right| =0\\\\ \\begin{vmatrix} 2-\\lambda  & 3+i \\\\ 3-i & 5-\\lambda  \\end{vmatrix}=0\\\\ \\left( 2-\\lambda  \\right) \\left( 5-\\lambda  \\right) -\\left( 3+i \\right) \\left( 3-i \\right) =0\\\\ 10-7\\lambda +{ \\lambda  }^{ 2 }-\\left( 9+1 \\right) =0\\\\ { \\lambda  }^{ 2 }-7\\lambda =0\\\\ { \\lambda  }_{ 1 }=0\\\\ { \\lambda  }_{ 2 }=7 $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{bmatrix}\\begin{pmatrix}0, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}- \\frac{3}{2} - \\frac{i}{2}\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}, & \\begin{pmatrix}7, & 1, & \\begin{bmatrix}\\left[\\begin{matrix}\\frac{3}{5} + \\frac{i}{5}\\\\1\\end{matrix}\\right]\\end{bmatrix}\\end{pmatrix}\\end{bmatrix}$$"
      ],
      "text/plain": [
       "⎡⎛      ⎡⎡  3   ⅈ⎤⎤⎞  ⎛      ⎡⎡3   ⅈ⎤⎤⎞⎤\n",
       "⎢⎜0, 1, ⎢⎢- ─ - ─⎥⎥⎟, ⎜7, 1, ⎢⎢─ + ─⎥⎥⎟⎥\n",
       "⎢⎜      ⎢⎢  2   2⎥⎥⎟  ⎜      ⎢⎢5   5⎥⎥⎟⎥\n",
       "⎢⎜      ⎢⎢       ⎥⎥⎟  ⎜      ⎢⎢     ⎥⎥⎟⎥\n",
       "⎣⎝      ⎣⎣   1   ⎦⎦⎠  ⎝      ⎣⎣  1  ⎦⎦⎠⎦"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.eigenvects()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "S, D = A.diagonalize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-3 - i & 3 + i\\\\2 & 5\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-3 - ⅈ  3 + ⅈ⎤\n",
       "⎢             ⎥\n",
       "⎣  2       5  ⎦"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0 & 0\\\\0 & 7\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡0  0⎤\n",
       "⎢    ⎥\n",
       "⎣0  7⎦"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* What about S now?\n",
    "* We have to use its transpose, but it is complex, so we have to take the Hermitian"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-3 + i & 2\\\\3 - i & 5\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-3 + ⅈ  2⎤\n",
       "⎢         ⎥\n",
       "⎣3 - ⅈ   5⎦"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Dagger(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S == Dagger(S) # Don't get confused here, S is not symmetric"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Remember that for a symmetric matrix the column vectors in S (usually called Q, the matrix of eigenvectors) are orthogonal, with Q<sup>T</sup>Q=I\n",
    "* With complex entries we have to consider the Hermitian here, not just the simple transpose\n",
    "* Here we call Q *unitary*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The fast Fourier transform"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Look at this special matrix (where we start counting rows and columns at zero)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ { F }_{ n }=\\begin{bmatrix} W^{ \\left( 0 \\right) \\left( 0 \\right)  } & { W }^{ \\left( 0 \\right) \\left( 1 \\right)  } & { W }^{ \\left( 0 \\right) \\left( 2 \\right)  } & \\dots  & { W }^{ \\left( 0 \\right) \\left( n-1 \\right)  } \\\\ W^{ \\left( 1 \\right) \\left( 0 \\right)  } & { W }^{ \\left( 1 \\right) \\left( 1 \\right)  } & { W }^{ \\left( 1 \\right) \\left( 2 \\right)  } & \\dots  & { W }^{ \\left( 1 \\right) \\left( n-1 \\right)  } \\\\ { W }^{ \\left( 2 \\right) \\left( 0 \\right)  } & { W }^{ \\left( 2 \\right) \\left( 1 \\right)  } & { W }^{ \\left( 2 \\right) \\left( 2 \\right)  } & \\dots  & { W }^{ \\left( 2 \\right) \\left( n-1 \\right)  } \\\\ \\vdots  & \\vdots  & \\vdots  & \\dots  & \\vdots  \\\\ { W }^{ \\left( n-1 \\right) \\left( 0 \\right)  } & { W }^{ \\left( n-1 \\right) \\left( 1 \\right)  } & { W }^{ \\left( n-1 \\right) \\left( 2 \\right)  } & \\dots  & { W }^{ \\left( n-1 \\right) \\left( n-1 \\right)  } \\end{bmatrix} \\\\ \\left({F}_{n}\\right)_{ij}={W}^{ij}; i,j=0,1,2,\\dots,n-1 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* W is a special number whose *n*<sup>th</sup> power equals 1\n",
    "$$ {W}^{n}=1 \\\\ W={ e }^{ \\frac { i2\\pi  }{ n }  }=\\cos { \\frac { 2\\pi  }{ n } +i\\sin { \\frac { 2\\pi  }{ n }  }  }  $$\n",
    "* It is in the complex plane of course (as written in *sin* and *cos* above)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Remember than *n* here refers to the size the matrix\n",
    "* Here it also refers to the *n*<sup>th</sup> *n* roots (if that makes any sense, else look at the image below)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": [
       "iVBORw0KGgoAAAANSUhEUgAAArwAAAFzCAYAAADc7Nq/AAAACXBIWXMAAAsTAAALEwEAmpwYAAAA\n",
       "GXRFWHRTb2Z0d2FyZQBBZG9iZSBJbWFnZVJlYWR5ccllPAAAWLFJREFUeNrsvU1sXF2a33eq3c54\n",
       "3N0jlabtxsBuSFNKLw2pUdrNQnwBygiyiNQLEp6V+CIAacQL8V0V4UVUQhCbHAR49S6MuLh5KRiB\n",
       "A3LRUhaBARJoysDsSLSUZBN0yJbSDuKZjEmp7XG70XZXzkM+R3x4eG/Vre/78fsBh6y6H+eee+6t\n",
       "c//nuc95Tq3b7ToAAAAAgLLyDaoAAAAAABC8AAAAAABVE7y1Wm3Xp+4AqenTvH4+ourHT9HrV8qt\n",
       "5Z/nagIAAMDMBW8fTvusb1D1E6VBuQEAAABGFLzdbveBTzWbzOrFeJ1Ph1Q3AAAAABRG8AIAAAAA\n",
       "IHgBAAAAAKoseHWQlQx+O9EBS+s+1Xts34q23x10gJPffln3CwOk5P+2T41ou4ZPnYTtmin5HoXB\n",
       "Ygnn1QnnJf9Nvid2XZTfiR63rgP+tk1ZJO/lIeq7b/1p/YTzrUfr6qYMyz2Os6DbbEd13rcee+Qn\n",
       "+xxo2Q/S7pVwbvrZ1ttJv+MmXHM5TotmAgAAoODIxBPjSpKdpvmU9fNmm47+P9EUlh8k7Cdi9EjX\n",
       "y38RUgdmn1aGstWjfY70e8i3brZdNtt1o/0Sj2fXmc8nUR72PLpRWeop+S1Hedg8t9Pqd5T6M+vi\n",
       "/MM12+1T16Ecu3osW9/2vBf63T/RPbOr6SRDvbUS6jn1/uxznN1x/k5IJBKJRCJNN81S8J5EwsYK\n",
       "u+UUAbYeLW8aUdLsU7YDIxqbsSBMKWMsBFsZxNpZOYMQ0/yuCN+Eda0e+XV6CPJWBsE7UP2pQD6x\n",
       "19LkfWLrK+N1Xog6HttJeaUI3nqKQN1NOae069C090BCh+Ak4Z6sm+O0aDBIJBKJRELwDip4k0TM\n",
       "dmxRE7HUy8pmRGinR7mWjcCqZxTG6ynr14N1MeXct3vs000Q2+tJ52etjX3KcdJL8A5bf2b5kQq/\n",
       "oyShn+E6L6dscxTXc7/7J+UYBwNch6ZZ30iwXLd67HNEg0EikUgkUjHTrHx4T/3B9xKW7+h/62e5\n",
       "oP83U/I6TNgn5lMe/rinvXw4TT5pxwvLG7Hfb3QOSWU8TQjP1q/8/cpRTynHSPXny7nh/+2p9XNX\n",
       "/+/45TsDXue044Z8Mvlgq//wvPrudlSQ96q3nQT3HTnXcP1tnS2n1ZHZp9HLvxwAAADyy6wEb5pw\n",
       "OE1YHwRNJ2kGN7UK9xO8zUjcpdEwQu04xef5OEU0xefQ77yyrEvLz0Xla2Q492Hqb0WPL+uO9fs4\n",
       "rrNTMd3vugWx21KL8K4K3eUM+51mKVPUWThJqaN6hnoGAACAnPLNApSxYcTq6RACp5/wKjKnGc5t\n",
       "lPprRGKvkaHTMKgYPu0jdjsqcEVwr7lzK/OpRls4GHPnq5/1+pgmAwAAAME7CURgibjZSHGDGCSP\n",
       "Zh9REwTNmZtAkpVXhVZ9igKoniIEGxnLMVT96ev7jhGCC/r93oCCPI2+Vnc9x+Bu8CDN6j4iNs+V\n",
       "Xi4vAAAAUEyKMPFEEESjxEMNIne5lx+mCqrjPscLAuxwQgIsZmHEcgxbfzIoTgSn+D0var1IXNv1\n",
       "QcR6jzjJ4bx6ifBGdG0S142CCtzDPnUNAAAACN6JIoOnRJTMJ00QIWSYxGDTXbz+3423j76vGXHc\n",
       "irZrGaG5NqXzX0gox7IRsBvjrj8Vqcu6XzjP4L/bGnCyj227vQ4+21bBeurSB9M5ZyzEUR4NFeTj\n",
       "vMeETtKEGjohBQPWAAAAELyTQS17iyp+xAJ3pDNhHYSZt/yyg16RCtSK98BdDMA6MHlc2l+jEASR\n",
       "t25m9joxImtlBPeKQdlLKEdwNVjrFzVh0PpTYbdt8j/VfPaMOO1kLLvse6ydjLNjOo3Lq+se9HIh\n",
       "0AgJ4fx2dbY2Gbh25C4s8adjuMfsNe+Yug71c+Sw/gIAACB4leMxbXccCRIRW7dVlMjnugpX+X+o\n",
       "y0/7iJpDk4d8DiHIjt2FBThsKxa/e2Z5011YI2+nhNo6HvG809ZtqFgPZQ4i+IGWc9z1t67L9xLO\n",
       "c03zbmSccldiHt8z+Yf63tB6POxXB+pOEa5Z03Q4Huj29cj6ejzMNUi55g1T3j2aCwAAgGJS0+D6\n",
       "kLcLcx4Oy6mw3StY2cX9YFeFZI2rCQAAALPkG1QBAAAAACB4AQAAAAAQvAAAAAAACF7IzjHnAAAA\n",
       "ADA6DFoDAAAAgFKDhRcAAAAAELwAAAAAAAheAAAAAAAELwAAAAAAghcAAAAAAMELAAAAAIDgBQAA\n",
       "AAAEL1UAAAAAAAheAAAAAAAELwBAcajVavs+dTXNUSMAAAheAAAAAAAELwAAAAAAghcAoADUarW6\n",
       "T0c+7easXNtarjr1DwCQjW9SBQAAiYigbOSwXE0tl5TvlPoHAEDwAgAMRbfbPa7VardzKCrviRiU\n",
       "8lH/AAAIXgCAkUVXDst0WhURWHZRDwDTAx9eAIAUNGTZUfS941PLpxNNLV234NNB2Ee+m/3qus+R\n",
       "rv+0X3S8uvroftpGj9c12xzZ7/3KFeW93qsMwWdWz8V+Pss/IT9ZfpByHq0+xwp11TTL5u2xEuq/\n",
       "rud5Eo5t9wcASAMLLwDAYIiQFQvrpk/zPomInNfPsmzPp2WfRLg+6Ha7e7qfCL4dn47Nfqd+/WYQ\n",
       "c/6fiMeG5nOq+dQHKJfTY1zJX/NZ7lUGRY6/7dOhJL9uR7aRff3/NbUwx8dLotXnWCt6viJu7+n5\n",
       "d3T7tZQ8O3rcTZMvLg8A0N+A4RsfagEAqtf41Wr7/t99/fqZbwv3E7aRBvLYr7ttvgv3/LJDFWkn\n",
       "uuyTuFUBLNEF9vyyBynHP9G87+n3dRWJiyIydZmIzzMLp19W02XyvRG+p5Qr7HcY8s9YhiMVvBt+\n",
       "2ZrZLpRtxQj0XRWcN4wIdlmPpcskz3UVuA0V5LYek+q/5zkBACSBSwMAwGCIADtUESpC71g/B0uu\n",
       "/dxIEH5NdXeQfe3r+LNlQexqPsch/wHLFfZrpojPtDIENqLvm6aMQYiL2N3pJ3Z7HcvvK8fZU9G7\n",
       "rEJ7r0d2sq6pbg24MgAAghcAIE8E/1p3/hp/O0EMN9yEX8+rD2+vMjgj5F0kvEVszqvYXYiE8DDn\n",
       "6xLy2OxzCovu3E1CxPGB+hjXubsAAMELAJADsevOrZgi6G6rO0JsyRRRWZ9gGcT/Vcqx0aMMvbBW\n",
       "3jPf2TRrbMbzDX7L6+7Cit3pVQAR4j6J6L2t5zGv+wMAIHgBAGbMggq2NRNqK7Z4iiCsR9Edmm58\n",
       "ky9IvuL2sNGjDL3EplhWw0C6edfbGpvlfJ2KVVm+ovmJBXk5Q1mOjY8xk1MAQF+I0gAAMHnO/Gkl\n",
       "5Jg7j36wkCDUNnS5RHewURrGxaEKyhAJYWEIsSjlapnPQ5+vDuyT89sUS7H/fuguojnsJcXg1UF1\n",
       "e+4iQoOww+0FAP3AwgsAMHlWVJgtqGDcU4EbXusHP9l77iKs2YLud+zG49tr/V8Ty5CBIC73+kwK\n",
       "0fN89Xjbel5rev6nul8ITxaL3boRz8EyvBaFVAMASISwZABQzcYvQ1iynJTzSjivGZal46LQYQAA\n",
       "RQALLwBAfsRtPfou1kxZtpeDsi2r2N1B7AJA0cCHFwAgP2JXpuIVMSmv7sNEDGFWt1mWLUwyIW4M\n",
       "K1wtACgaWHgBAPKD+L1KZAbxUV3Q7/f6+MtOAxHdG1oWpvIFgMKBhRcAIAeYQVt5LNsiVwgAigwW\n",
       "XgAAAABA8AIAAAAAIHgBAAAApkytVmvIJCc+dTVth4gnEkrPLE9KnSgvmfjkYEzl6uo022fTbcv3\n",
       "QfeDka/Bp3pH8AIAAECRkQgi4gP/wJ1PsCLfg5Dd0OR0fUjxuoAMED2csijbReBOHgatAQAAQGGJ\n",
       "Z9vz4lEinbR03bH/fqyf98w2Z+I2joAyo5n7RKAT23rCYOEFAACAsjFU+LzY9UC/n2hqJWy/ruu6\n",
       "aqmtD3i8cKx1zWNevzc1P1l2YPPV6bnDuiOzj833yLprqJvHQXxevc5Bj7sbHfeKu4V0MHTbruaz\n",
       "bM9PvtvyyIQ6+j2Ufzmt/k0eLfN53RxvN6qbZZO3nG8TwQsAlcA3etd9mouTX3XdbHY3YZtb1B5A\n",
       "IQkxrEdtO0RISkxsCRcorhKHKcJa1ombhEwW0xnwMMG9YlM/h2PM67JFzXfb7LOrx72t57mdILR3\n",
       "NI8wqc2CiuiGyX+vzzmc5WH2WTDLXcLxHmiZO2plD3R0/abOHrltzjdsvzxAncm2G3HdaB6dqCyf\n",
       "OgO4NABAUYXsnH4M/+8aEXt/wOy+TDmG/frep3f6+Y1PH/T7Wep2u++4KgAzbxdEoNbdVd/cUaj7\n",
       "33eigPbLN4yo3DOiMBPiZmHcK/ZMu7MZjmldNPSzpDUjNFt6XOuOIXm1VKzK9scqbMW6GoTgYp9z\n",
       "2HQXk+Bs6P+9BDeQwyDU1X2kpfkH8S7Tka/p+o5+D9dnz5xfVneSxLrR/5+OpesbYT2CFwDy/PC6\n",
       "5f/dUlEbPt+fUXFuakoU1PqQeqsC+I0mEcJvuJIAU2kvFlTcLI5jdkIVoyKe1lVIr8TC1xyzOebT\n",
       "OU35HI6zG4vyhLKfqvCcdxdW2TBFeBDFqecgk+H4dbLfciySozqQY3d0fZJLx2FU/p2E9QtjqJtG\n",
       "gmj+tB7BCwB5eVhdV2F71/y/NqbsXycsu+MuLMIiVD9E64c5/h1NDyMh/NqI4DeIYICxtx8ituTV\n",
       "9lqaNXZI0XsWyUF9WTtWrJljLqp4lFfq6xM+1SBWb2SY5nvPCN4gVFsqAndU0PY7h00V17LsNKVu\n",
       "g4vFPR0k2O1T/rhzYEX4JxGt5asPWDfNtI4AghcAZvWAuqXCNqSbA2YRRGrsXuBUVH7oc/x9d2Gp\n",
       "XfXb7/fZfk4/Xlcx7NyFO0U/q/N9u43P66P/tx8SAhhgLGJXBNuhGcR1mEEU9spXxFPDXVgJ47ya\n",
       "0eflIQ91Zon1xzu0kSRSBPieug2I325wC0hzudjRerHuErLvghHAPc/BHC/4zSYhdSRW2kYGX1zJ\n",
       "o6OD0A4TBHmwBos7xt6AdXrmgmHyblza358MiZTLpD1RGWV5ov8XovXy41zvta3+sJej/Q60tyo/\n",
       "sm6fNB8d7ySljPKlwXXreT1FKD7yaUuFaTdj2td92iowb42pPPvmGHNjOj8p35KWdV+FeJZzlO1e\n",
       "ivAe1/mRcnHPN1VwnGjaVnHitA060M+dPvdHp087ZI/TqWA9H/Vqv1X0dKN9uvGzwbTpXfP8ONFt\n",
       "D+I2Xq2H27r+SK9p11xj+dOK80045rI5Tt3ul7SvCrldc567KfmGvNbNsnU9Vj3LOdjjpz3jtJ7C\n",
       "NeiEfOI6iM73yBxzIeEahN/MutZ9Kym/hLppmbrcvXQ9aZRIOW7EdvWH1DAPhGbUyC302la/X/qh\n",
       "6vpl03B09UfR0JT449b9OlH5wg9ynmuWeA1vqYh7mVH4iaXzuYrGuxMu21gFb586eDSgCH6n9XCX\n",
       "e+hTh7LVQ1Re6aAmPGBThcEEyx5GjTe1g30meu06Izo+tTsmhbap3qMdmjcP9wU63qn3SCtBVDWp\n",
       "n8y/we3CnwcXk1SQH1w96i2f9Sgzbrvdy+oR9/RTrAF1fVg1o14kD5d0kfsmo/W2PUnBOWvBm3Ls\n",
       "u6Yj8AHx27OuOn2sWC1TV+sp22z3Wj/Fc1nvY+Xr9mmb4naoXlWrLmkq92vDGHYK/6wjDi8UlQWX\n",
       "fWaaHWdGgA45T/mC+kEdGsd/8UUa1Km+rD50Eut2yScRuT9352G+7iRsKqG9vvLpR2q1EqHZ7uc/\n",
       "WzbEZ9en5z498klcIX7o0zOXPLhOfJuf+PRTX7/vfHru090KVVf4nc+nrG+mfI5/v87lYzarU/3N\n",
       "tPoM7snSDgX/xDUTKxVgnM9Zua8ejCPqxaxB8EKRfnhBvIYH22HGbWW7+ogPhE8xDnVARN28ojyJ\n",
       "Z8KpkNB95NNLfYh/nSJyZXDZFz79oW80xT9VBoi97DeorIICWIT/nN5bn/v0yqePPcTvG59WNbpF\n",
       "FQSvS/kNn4lAvQeTZpyyIvgwB+3YzjjaIfNdzlteOR/Fs1wBjNgubfh023SwELwAExZVIgDkVeCm\n",
       "6WU2XBTGJG3baJ9hjt9wl+MYhgeojKiVmFO3VaR0KnI9bvnUFmuj//pjZ0JwpYjcu2rNfMfdnOkh\n",
       "88GnLWP9FWv4iwTxK50LsaTLW4YtE0WibPVxan7r8yli1ga+j0Vv+L43yoj9MfxuRpoQIaEdsm3a\n",
       "orZFYQR8k18SAIIXZi+YJHRJx8533cfFYFsfeGsZsh9k26yIxWQnfliG2VxUUF9ymyjpdZPpdrfc\n",
       "ucvCU3c1jNh7RO5EBJ9Yw5fcuW90sPzGPPbpJ2r1XSphNexFnc1YzH4SvAnbNKM8xvV7EJeEXbWq\n",
       "Hunn+ZRtZbm0cWsjvBpOaofquuxQ75WNpI4BACB4YfqiSRriI228j/UhJFaKdQ3sHW+/rQ+sxaih\n",
       "P3XRjC5p2xpXg1EeNPY1YrAkNaIHz2lJr9mSxqz9iQori1gdxfr4mborIHInJ3w/WX6lU+HOfX7f\n",
       "R5uJ1fdr9fVtl8jdIYuYTdtmrP672mEP4Zsamm9wp9iNO+8mRqy8Ht4c4dBxOxTqpZHQ1p3yi6nE\n",
       "8/QEaz6CF/L542xowy+NsTjBnyV37hJwNiOMfViogP0UkFofNPWUhr7Xtk0VDMdDlFnyPLXBwPWz\n",
       "HP/s1aFuE+YaL5vQFfEqvrnxxAoitMTaKCJ3qWqDznIgft+pz+8td+7yEFt9xfouVvggfG8V/JQ/\n",
       "WXgjX/kF/X0mWniNGLADvc7aiwGT9Yvd1rYn+DdKB/ue/35P27b1cNxoQoRNbZca42iHFGlzFqR8\n",
       "mm9Hy7BTpd+D1uu2vjHs6ue6ruuY5UmpY+8XEZFR3k3N78Rua9bL9T6Y4Lm19C1oV8/TlrHukqfy\n",
       "LcI1G2bQ5sgNJ4k07fBCrR6xNI9M2LGkEE27dsKHjNuuOxPSyF0NXJ0alkwfVq2U0Gch0PuRS4kR\n",
       "WtDrtOTSJ4aQAWpzJTnPfTejsGQTDAcn4cvSwpxtuQJPauEuAtXPR23GdsI2jShk2XbGiQrS0nrU\n",
       "1vQLkdbpNyGCuxowPzUsWVo7ZPYLk+7sugqGSnQX8Y6D8cHGO264i8kU5k3qBit9jxjHn663S4lx\n",
       "7Ew85QnFor8U6908R8O9deByEHJvyImlusThJZW1UQqNfT1l/Umv9SmxdpsZtj1xPSaGcFEAcmeC\n",
       "lGsjV6/I9ekldAstlqogeKMZ31Z7XEsRxdeL3mE24nI5Id7ucvR9YUxl6JmfEVIH45wcoUrt0CTi\n",
       "HbsCxjh2FzOiNZLuMXMOC4M8D6sseHFpgGm6MwROkl4tmVczjQxvJuS13Zo2Cj1fm7jzaAp7PfLa\n",
       "sK875XMY/CHzk89yZPeUrs0j47pgB6KJf67EzP1DdVt4x51cCHeHD+pLfUvdTmI/3yfG1aFIPr7h\n",
       "Nzof/d9L2KYZ/R/XgLWQXyelDduO3SoGuG6HZtDZpbapCu3QBBi0vnrFOJ5PCzsZv5rX7yeaWiku\n",
       "EOEZuJuUry5bDm5yffx0T829UU9wxwjuEJdC1umyZR1w2dFlC2Yw+VHC9q0e590N7h1J52aO1VUX\n",
       "kKn7Hn+T3wRMCftD7OdflsnXVh8OG6NuU+FOyJw7n+Us9s/9qFbA58TKLbz4Fcv8lkZuaJsOzTV3\n",
       "7uMrcXxXdbu8E0dqmFeBcpy0jXayG9rhHZdYbBhhfTpGsQXjZZh4x2kxjo/C88vfU2txpyRqU+fV\n",
       "CLPY4x441fVnHSdNiwkdq7qWYV3zlvv8gd57hzpw8tQc5zTlmDtqHJrXjtqhEfUdfT7uiNjVDtua\n",
       "HqOp27sBBluKQF7Rz+ua3wMVzuFYnwaqz6JBJJGmOTVwJpcF0sRfeYvA6f6dv/o73X90/bux68L1\n",
       "itTDviuhS8OQbitvilAHzvjxOuMrm+IatexSfBvd8D68wV9ynrYk1+4Ml1wBXB+XBhVgl55N7mJ8\n",
       "RuwP3kx7NW/uy+WMz0QRgSc9fMFbpnxSlt0Rpwm2ecb+7wfuqq+7CNajlLEvsQ/6pd+aM24lWvbt\n",
       "rNNs49IARbc0nZrXjQvUyMysumLle3ftG994/E9ufM/tf+/7buXb191//e1rEnIsuC5g1S23xVem\n",
       "JX7mLk9kIeHMJI7vy5xHdLBTe9vvSdv0Ckd2qJavrOk45fiQr/ZtQa/NyoBRedJiHNsJjPrGOFbX\n",
       "uTNXO3UhWEgqo77SP9Hj1nvkF1zrQqz3+QHrox4iTKjoTPutBKvyYcL6QaKKnKZ8biTkPfW3IAhe\n",
       "mCahwegkTX8ZhRKD8T4IZNIIseLJa+xr/+z3/8D9vb/+nU/r/+T632jgo1sZ0Ss+vtLxEWH7VbRa\n",
       "Zs07m7I4p8Xfi0THTr9tkvz3NZTYIGnTtGFnMXdVSDQSfmvERZ1NGxdCwInbwaDuDGkxjm2Iu0wx\n",
       "jtXv+obu30kpo9xHN1z6BEmHCffSMLHed3W/ezoTXy+OXfLELsdRGZI+uyHynvqzHsEL03zQ7pgf\n",
       "eEd7wAeaQg8U6+94HwLXfRJ/XLHg3gnL/4dfnvxltOnNk+//oE2NVU74irD9oU+vzSrx7/1SZ227\n",
       "m1PBe/YQTfHNPUzZfhx1Jg/u4J8pbdWRDsSx7djBMLF2YSxi9yxGug4ym89iQMkQ47il2/SNcayD\n",
       "xBbMjHvx/dmMPi+n3Gch1vu6nseCGy7We7gPGzq1dS8una9uP2+e2Xu6PpRneYBybEZ5Lw+4P4IX\n",
       "CvmQlR/VPf0BnOqPvqE9wI1xP6Aq/hCYc+e+mU+iVV/9y1//6m+7q5MVrHrRe52aq9xv8o1Pcq/I\n",
       "BBaxm8NP1Q0mL2U9dhcWpzThYQeU7UygDNJG3VYhIJ/r7mKQ0aEuZ9DadOlo/Z/NdmdSFmt7knU3\n",
       "GGhWdL21lJ72EZgds/2DBOG3o+K8E+7PFGH+QO+jXd12o9eAuRRWtEyhPMcuxbKqbzHs+YqoXTTW\n",
       "8hVTnlZSnfV57q/pfrtuRhM11dR5GADKI3RFtLYThO5bn8RHV0Sw8+L2lv/382ibFzd+8bOlitTT\n",
       "vruIUPEZs8Vlv3cACnZfi/Cdt4JRQ2yFiAF7hH2rwH2A4AUoVcM+584jLcTxdGUa2ufx9urG8DRa\n",
       "/EMvet9UoK4QvL3vI7lf7kSrnqn/LwBAocClAaA8IkWEyE8isSu+mXeTxK7y3F1+jR2WQYUR8e9T\n",
       "iOZgeSodhZxHcgAAQPAClFDo3jIRGCxfiG9mr+gLN37xMwlBFo/Iv3/y/R/MUbOg1tzP3OXZ2sQq\n",
       "LgPaHlFDAIDgBYBpiF0RHSJ27atn8bf8YQ+rbix6t3Qfyxa1Cyp699157F4bwkwiOfxYI4AAACB4\n",
       "AWBiYlfExo9VfAS+klfRQwwuiq28EqZslVoGFb0hhFkcyeGJhi8jugcAIHgBYKxC97oOuLIj6UWE\n",
       "/EhFycDc+MXPJL/X0eI2YcogEr4v3bm1174RkLcL73SgGwAAghcARha7IjbEenvfLBbxcVfFyCgs\n",
       "Rd/Fctym1iESve90QFvs4iBTEy9RQwCA4AWAUcSu+Ovuu8tRGF74NDeOaYFv/OJn79zVqWafaLxe\n",
       "gFj4ytuEz336+F/+7rfc3//22cuAr/19ukXtTLwtkNmqulGaH1PeyzJ7XAHO/0TPm1ntAMELUKIH\n",
       "nIiL2F/3cy86ZDKAD2M8VNtdDVOGgIE00bv131377sr/eON7v/3vr3/X/ZMb35PFjzV0Ge4wg//O\n",
       "WzpFcaKA1XUyE1ZD679m0rhmqZR8Nkc4h3Wd6GGShFnKbujsewAIXoASPARFcH5pFokglYkSxi5E\n",
       "NUxZO1pMmDJIRHy8/5vvXN/4du0bZ8+Sv/fXv+Nef+/7Z/eMT4jewX7nB+5iytZ7sYD162U61rpO\n",
       "ATvJTszxEFPYWuQcJi14RfAfMjsaIHgByvEAvK5i97FZLP66c5OcFcyLXon+8D5avMUVgQTkPrQu\n",
       "Nu5Pf/2r8DEMZrtbsd+tWGe3jatBK8M+LRVxt0XQ+nSYsJlYdnf65NPwadccW8pRN+Wa189nLhH2\n",
       "s+53Eq1rGovziYru+Bwb9tz1Y0fcIhLyXtDl3bA+oQzxunVzPh3jbtHR7RPPOe28TLlP1H3jIOt1\n",
       "AgQvAExA7KqYSBK705j2dyn6TpgyuIS/H7bc1amHX/3DD39hZ2cTF5z9qolej4jMGz6t+LSuoqyb\n",
       "ktZVzIq10orB2Eoq3/cSxHXXCM1dzUeOfU/36ZhdGtF/+1n2WwzfVShLfjviMqHnsm0EruS9aF0K\n",
       "dDthxX++nZD3oe5TU/G+HZVhT8t+qIJWRG9Lz0WWb2q+4RgPepxz4nl5jnXbHd1OrNkPwnXil43g\n",
       "BYDpi10rJl5ofN0P0ygDYcqgj9hdjTpjoUO2pLOzfZ4geqs0M5uIxFPjfjAf+dvatKZi7NAIu0Mj\n",
       "Bq2IvvQK3+aj4rChQvBUrcQi5hYylnklcqNo6jHXVVDH4nTNb78zRN4tza+l+dvz2VA3hT1TJ8d6\n",
       "7JZ+tm1llnO+dF5S33qMQ/2+Y9bP8+tG8ALAbMXu0gyKEx+TMGUgYleE65fRYvErf6Q+4E79y+0k\n",
       "FWFmtqUK/7Z7WXiDSD5WMbbjLlthJ04Pf9jbKYPj6kPkvRvydOcW4yz7SSdgU0XswRjPCxC8AJAj\n",
       "sftsRmKXMGWQJHbFNWErYdWc3i9WaEhc6Dl3OerH11UVvX0svCJwW+r6IEJXXBziqAsi3Jo98pft\n",
       "xQLaUR9W2TYMgvu0v7oqzGcob8gvuGTUxxB9IVhtT7OUQcva1EF0m3EnIMM5AyB4AQogdj/X18Oz\n",
       "pO0IUwbnYlfuURGx16JVn3ux+yZFNL2pqOg97vM9ZkW3OdIUllkO3WU/1CSCr+qJO7eG7vlrsGLW\n",
       "Lei6rGV9oPkd6X7rGc5pQwXodsI2a5rHSSRq08ogonhbXSCW9RzibdLO+XiIa0KIszI/Z/2NQS0A\n",
       "5FPs5kJYqr9m/Ar7M/XzLXK9S/nDjHWfTTLyRUkE7xt3dZDaV/4+WM1Q13f1Hr+Wx3u8IPeriL+O\n",
       "GbQFAAOAhRcAsdsTwpRBWkSGLGJXqLCld2zo6/tTwmcBIHgBELuTIxYmhCmrjthNjcgwoGBLE713\n",
       "qeXMdXhvxEkhABC8AIDYTYMwZZUVu30jMoxB9O4jegEAwQtQTrYisftFAfwZl6LvhCkrt9jNHJFh\n",
       "RNFb1ckpAADBC1BedLrgh2aRxNl9nvdyE6asUmJ34IgMYxC9L/XNBwAAgheg4GK37S77Q85qUolh\n",
       "aTvClFWBfZ9uRsskIsPYrrWKXusHLsfbL5vo1ckl5hOWL8sUwhnzaOp0w10N95Xn85VyLvdYX9fz\n",
       "WIj2OTDfW2a65JHqeYD95wc9Zs6vw1TOZ5D7OMs+/e4fBC9AMRogEbZPzaLXBRO7Tv0229Hi+yff\n",
       "/8EcV7gcjBqRYUDRK8ey0xDfKXoHSmZOS5igIWnWNIm6kHWChI5uL9MOb4yhPJNk012dNMNec5l0\n",
       "QuLdzgcBrPVjyyjrdoY49iiz0zWK/tuNrvW0zmeQ+/jKPtoB6mS9fxC8APlviMQ/8WuzSEa5Pyri\n",
       "uRCmrNRidywRGYYQvdZV5qH/vTwvcDW2XI8Z0cx5Hw8QcUHyOxSx6NPhJMozxuu5IeeWQfA0jbg9\n",
       "1XZy3iw75Bc5mXtvzNf7eNDIIdE+YulfHvD+QfAC5FTshogMgbNR7v5H/aHApxULIMKUFV/syjUd\n",
       "W0SGAR+Acu+8MIueFDFGr3mF3Ile2S747yf62r0VxF3YXl7vm/UHUZ5HJs+ufXUfXBz0f0MtfGGb\n",
       "To/yON1+12y/rda2ef0e1h2Z49XN8hPrlmDrwGzfSTonFbNNI+bDFMFNY6HcSaljWw+tPtscmHJ3\n",
       "4nPtcR2Xw3n0qY+0OrTXOeRV1+8Hep16XfMF48Jij9drn8Rrbc77ZIjr2DHH29XztfVxEt3HcV2t\n",
       "m3vSHj9sJ1bojjneuqn37cjNZV3zqJt7vqv1mUnkI3gBJo+I3WtGQMz5B/y7Ip8QYcpKJ3blDUSS\n",
       "VXWkiAwDIqL3rfn+vGiRG/zvuqYfVxJmRJPvMuXtuj7o7Stn8cvd0P3XojxvmzxD/nZfediH6XVF\n",
       "ZN1z564Pm33Ks+vOLas3dJ+mio+Qd3ChOAyiRMsZ9pFjbuu5xDRU3Czrea9F6/eC8HEX1twggs8s\n",
       "vj2sfDt6/Adal81IqCUdt6N539bUMOfkEvaXdQ90so9e9ZFWhzt6HmedHdPpqRuBn3rN9RiLum5H\n",
       "t+13n6Rd62Mt394Q17Gp5yX51aP749Tcdy66L3f0+rR02Q1d1rHb6TVeCeX3ac2s39QOUMhzWZdt\n",
       "a1lum+uRya8dwQswWYvPlrvsD7mqg3XKQGyBI0xZMcXudXd12l9hLBEZBhCLYkWec+WM3LCj7gjB\n",
       "13E+QQC21Jdx0Ne5az7fHX3wH+vDv9UrHxV1DRVHwU1iw4iz8Gr5VMvWMOWWbU5U7MXiOxZtpypy\n",
       "TqNrfazLmkYAHkbfe7Frjt/McNwFFYrHeuxL5xoRROVeVOZL9dGnDs8ErwrceSOAF1TM72W45mHg\n",
       "XksF3lD3yYjXMa4ze9+uxHVkjrlp1u3p8Q/dAH7Fur8cd1nruq6CN3SSjrT8y1nzRfACTE7siiC0\n",
       "/pBfFSDWbmYIU1ZqsTvWiAxDiN6ARG54Wfbr4M9brGFr+uA+SrG2pVHXPERU3FNRIGLmYELFXVFr\n",
       "XEhpokfKc1tFy27COe2pmAtiMQiyVMGreYhAs9brQY/rjIBMYk9F1iiDvkL5Oyr0wjX5NBivzzUP\n",
       "IjS8FRjHfTLMdaz3uGdPp9FR1HpbUOF8nFL2GoIXYHZiN35F/Fr9FMtG2xGmrMjIPTqViAwDiD+x\n",
       "Kn9hFt3XcH5lbi+CELKvdAfN4+x1uQ4G2uyVh7GeddQnsqnis99o+50gBs1+Pcvjzi2D9YTyHOry\n",
       "PS3ToTn3Hc0jLdrFXpLfaY/jSn4tLbd8X3YpPsK+HIvuwlLuhqlDY1E9s/bqtqfuwvrb75o33IWl\n",
       "en6c98mA13HB1FnLDRc5ox/HpjMTE+5je7029VpaP+pm1saFRCKNMXnEaiYP7a4msVpdL+v5/pu/\n",
       "/Z+v+tSN0lwBrtO+uUZzVbtP/TVqJ1y3Nz5dz8n12TLXpzDXyLOu5d3W7/Jn3qzvuovXsl0VZUfm\n",
       "PNcT8vyUR4/P4RV1V/NbSCqPybOpVuBw3I4unz+XBp+2+/Rdy7pt9tlNK2tUnk7Cdk1dt2yWSXmO\n",
       "9POyLYfZJhx/V/8v9DtuQrmTyhOf54nu06s+EuvQll8Emy23yT/1mqu4DOu2B7hP1s0+47iOu1E5\n",
       "6n3yjdfZ+7PXduE4ywm/F1l3EpWtY67xmdtHlt9mTXcGgPFZa+RBbV0ZPvO/s/0yn/PJ93/wzl2e\n",
       "qODtjV/87G7Or5Nck/tVuUbR9Vpyl8PkObXU353iILV+1ye4WwQLtITCu1vw6CaQ/fpvG4srTL/+\n",
       "RRyuGL/zwoNLA8B4G4lHkdh9VhEhtRR9v6OiCvIndpMiMpxFD8mL2FWh80Hvq+AyIx2qLa5gZRAr\n",
       "4CbVAAhegPyJ3evRA1n8dttVOPeUMGXPCVOWO7GbNkhtdZoRGQYQvVIm+xt6WMT4vDDUtb+RNiAO\n",
       "psZxmU4GwQswPl66y/F2q/Zgjs9X6oLJKPIvdp/NIiLDAMJHrNGvbEfKi95bXFGAif7uamXrcCB4\n",
       "AcaAfwCLsLtvxV/RJ5cYFH0d/iJa/JQwZbkhKSLDC3/d2gXpTNn4vFtcTgBA8AJMV+yKoLOi4ZUX\n",
       "uy8rWh2r7mqYsufcJbPFdzrk/nwcLX7rCmKBN/68gfvayQQAQPACTIktV21Xhk/c+MXPPiQI3Ide\n",
       "cM1xm8xM7Mr9+DRaHAapFSbigXYirWtDG9cGAEDwAkwBjcoQuzJUOmySviJ/Hy3GyjsbsdsrIkMR\n",
       "79Mld9m1gfsKABC8ABMWu3FUhiq7MsTEr5sJUzZ9sVuoiAxZSHBteKidTgAABC/AhGi7y64M+BQq\n",
       "XlCJ8CdMWf7Ebq4jMmQUvfG99Vw7nwAACF6AceIfsPKq+IkVv1WLypCBuANAmLLpUeSIDFlYcpcn\n",
       "pOC+AgAEL8CEBEXgrcYKBYO+NidM2ZQpekSGLGjn0v7mnjKADQAQvABjRGd6sgPVsC6lQ5iy6Ypd\n",
       "uTcLH5Eho+gVYf+e+woAELwAk6FtPr/wD959qiQZwpRNVeyWLSJDFpbsfeU7o9xXAIDgBRgV/0AV\n",
       "sXvTiIk2tdJX9EodEaZssmK3dBEZsqCdzdfcVwCA4AUYn9gVUWHdF54zUC0zhCmbvtgtfESGjNj7\n",
       "6I66HAEAIHgBRhBtNgwZ1qSMEKZsopQ9IkNPtNNpB0e2uSUAAMELMAQJ1t121WdUG7LDYCFM2YhU\n",
       "ISJDRqzIvYmVFwAQvADD8dxdWHffE4ZscAhTNnaxK6KuEhEZ+qFW3mcpAhgAAMEL0A+N7/mYh+lY\n",
       "IEzZeMRuFSMyZOmUfpqMAisvACB4AQbDPjjFurtFlQwHYcrGInYrGZGhH+pi9JyOKQAgeAEGJMl3\n",
       "l1oZWfRKHRKmbLxityoRGfqBlRcAELwAQ2AjM2DdHW+9WghTll3QVTYiQz/UyrtFBxUAELwAwwsz\n",
       "rJBjgjBlg0NEhoE6BQGx8j6iSgAAwQuQgr4OtXF3t6iViXUmnCNMWS+xK/ciERkykBCXl3sKABC8\n",
       "AD1om8/Pibs7XghTllnsEpFhtN/ufd95vUuVACB4ASDCPyDn/L+bZtEWtTIRCFPWW+wSkWEI1Mr7\n",
       "OrrPAADBCwAJQizwQh+gMGYIUzaU2CUiQzbsffVII64AAIIXAASdaOKhWYS4mKzobTvClCUh9x0R\n",
       "GYbEd1JfmvtKOg1L1AoAghcALrAPxrf+wblPlUwcwpQZ/Lk/jzpdZ/ei49X8MJ2GtHsMABC8AAhe\n",
       "BUvjFEgJU9auYpgyFfpPosUMUhtd8N5k8BoAghcAXOJgtZfUytSILXA3XcWschqR4WvE7nhQ3/tX\n",
       "Pe4xAEDwAlSSJfP5BaHIpkdKmLLVqoQp0/PcT+oIEJFhJLbMZyahAEDwAkD0QMS6O33a7nKYsmuu\n",
       "AtPDquvGS0dEhrGjg9fCPXVNJ5QBAAQvQDWJZlZ7rw9KmCJe3L1zV/2mH1cgTJmIWiIyTLZ+kzq1\n",
       "AIDgBagcWHfzgQjeOExZaYUfERmmLngfEpMXAMELUEn0AUjs3Rygg7NigXu/jGHKUiIyiNhnkNoY\n",
       "6Xa7b6JOFFZeAAQvQCWxD8D3+oCE2Yle6XCUOkxZj4gMjxC7E+ElghcAwQtQdeZSHowwO9rR99KE\n",
       "KesRkWGJiAwTY8t8fkh1ACB4AarIo5QHI8wIL/xEEJYuTFmPiAxf6AQcMAFit4ZarYaVFwDBC1Ad\n",
       "dLKJID4+4s6QK9qufGHKpEOVFJGBWf0mD24NAAhegMpCdIacUrYwZWkRGfx5LnG1p8K++TxHdQAg\n",
       "eKFg1Gq1pk/bPp1oks/1aJtlnxZkua4/0m13fWroNrJ+2eyz7tOBfu741O2ROtHxFsK+CWXs5Kj6\n",
       "5lIeiJAPShGmrFdEBi7xdIhia9/07dDdKbfTLWkTtQ2U/wsJ7fh6j7a9Y9rlZtxO+zTfp42WNB/l\n",
       "fZJSxm54LgAgeCFPSON36tMDnxZ9kkatYxoxabikIT3URSKGV3TbhtlW1ndMQ3ds9lnTJNw2KV4X\n",
       "EOG8o8eX8hyY427kpKNwy11+vYyFN2eUIUwZERlyxauUzu40mNe27562q9tWuMp30972ajePdVtn\n",
       "22kv6PeiNjm00Z/abd3mShutx9v1/1o+yTYP/LbH3C5QFmr+hqYWynhhz60ELX99a/pdBG3df1/M\n",
       "sK00pKf++0rCttJAdsK2ukxuohW/bDMS2EeiV3SRfN5JynPG9bRkhMhbX7673D25FY37InTNIrGO\n",
       "3h1WMPprb/P7zF/7/QmVWzpV4hceD1L7EYPUZvKbl0gfXwbx66/7oxmVQ0SsWFfXfBk21Nq77j/f\n",
       "NutT2015Q6f77iSsu9Qmp7TbIX8Rtodi2VWxew+hC2UEC2+5OTWfF2xPPqKuFoLAjm4fXm8N0yta\n",
       "0Ib6VK0IZxaHHL4imzOfER/5ph19z32YMiIy5BLbsclTeDJpM2Pra692c2/Edlr2PRaxq99F7IoF\n",
       "+TR2hwNA8EKe+SRwtfGSdBhZARpqVVhwl10MZLv6iOJUGutNUxYRvvJqLvgNL+dQ8O5z2+SXgoYp\n",
       "23JEZMgVGoXlo2kH52bYRjtjiGhGbXS/dvNQ9xnl+MECPK/PCPkvVufgY4zwBQQv5Bd1UagbEdvU\n",
       "hv7YbCMNm7zOCj5jO+aBELZrDHn8s8bT+IqFfBb1lZqUqxP5rs2inkQo3TTnjeDNP21XkDBlRGTI\n",
       "Nfa3PnU3JhWS0k5vRu2tfdPWr908HqGNbqi4tWL7TETrsW7rM6TDrQIIXphm49jSSAonGllh1460\n",
       "TRCb8mpqrZcflohRbdjuucuD1saBte46bTh3wqsz8VfT5fMzrlr7oHvNnZZ/ihKmjIgMhRK8I18T\n",
       "fVvW0fa5q9bRVo9dtlWwrvXYZpLt5rK7cDmzz4U1Y/T45NoGgOCFSQvdhg5MWFdRKhbTU23wduMG\n",
       "VcWuNKQbdgBZsBokvZ7SxvRSw2a2Ox6izHVnXpUFq4G1RJj8T2dcxfZBx2QTxSHXYcqIyFAtwWve\n",
       "li1rm7mn7d26Rj2It5c2Wiyqi5HgPFWRm7XdrI/Qhi4ntNEucmMbJX8ABC8MxLY2eCJgJZyMNJBi\n",
       "kb2nDdGnWIxG7Epju6liuWF6604b2RCPd163mXdXB7RdcYEYgLOBF9G+YplY0OMGa/KpSx9ENy3u\n",
       "pjwAIcfkOUyZ+hMn3UtLvtx0qnJCNJviNXVvGsoooe3uWUhIn+9ZcucuAdIWz1vDhIpdaXMXjVGj\n",
       "niRwM7SbDReNyxhAoJ/a8GT6OYSkbJrnwgZ3CyB4YaLoYLKmise1qLE+NA1RGMTQ0R75globzpJx\n",
       "fdhzF6/Cgm/Wkf6XBtSGvZl3l0cLD2o52InKG/KXdSGm5L34ddoMsCGuECPFEr1b7qobSlujIsxK\n",
       "7BKRoVi8Tun8DkJL27ONSEBK27Zm22gzQFi23zXt9LZpoxcGaDcXhmynY+tu4IEK6l19LmwYNwqA\n",
       "4usq4vDmVvBua4O2mBJncV4bpkO1+mYR0BKH8UaGbU/0uHsJ60SEz9uGUC0YexrLcTlyp8hr/coD\n",
       "7qf69aMv83XuumKhfrs/iRY/8+KynfEe2HdjjMPryyOiNh6k9oJBarltA8Q1JvhZP/PXvz1EHuEB\n",
       "eiOpA69taT1tfbRtiMt7z4QKS9u2qe3/7ZTjfmqT43ZbnwV7OTA4ACB44VNQ8Ya76tcV+LTcBhPv\n",
       "k+euNnQbPbZpacP4oOT1KyIk+Fm+9uc7x11XSNG75f89NovEV/auDm6bmuDViAzxIDWJyMBEJiVt\n",
       "A8zkOlnoK2IHaX+ztOUAcJlvUgW5JfhyHbreAwcy99KziFhtQKvQiOK/Ww7aPslMWcGNIIQpW5qi\n",
       "6F5yRGQoIm9S2oOsWENEv/EImcZDZG1/y26QAJhIJxcLb26tD+KzJa+hHiS5FsDI9SsiN1j3fuTr\n",
       "GB/LguIFpwjcp9Hiz3Siiqz3wFAWXo3I8NNosViZ5xikVoh2wD4AJXb4hwH2DS4Iwg1cBADyDYPW\n",
       "8oud7hHGj7XovKM6Cs1MwpQRkaEUvE1pE/qiAje008SrBUDwwpCczWnuzsPabCdN8zvrmcoKzjXz\n",
       "4EKcFJhZhCkjIkNpeDes4DXttNBJmi49CjsGAAheSLAeiM/Xoores1BjOovPgSZ5lXaQJIShN77O\n",
       "5szX99RIKUTvlksIUzbBQ8rx7kTLJCLDc65GobCd3YEjtWgEnTUjek+iNvrIYf0FQPBC38ZUfHdv\n",
       "a4Mqn8VS0NT/h7ocv7HBsQ+2d1RHaYgF7k317x0rGpEhDj/2lvBjhcT+/ueGbKfFyiuhITe1PZY2\n",
       "WgwRYrTYcMPHNAeAMUKUhvyL3lNtNAk/Mz6I0FBCZJCaF6Mv3OUwZasiUMc1pS8RGUoteIeOxa0h\n",
       "x1aoToD8goUXqsgtqqC0tKPv4mM7FjcDjcjwdbRYIjI8GpeghqljXRruUB0ACF6AsgrefaqjPOiE\n",
       "E8+ixY9VrI4qdpPuFSIyFJg4DFmtVmPGRQAEL0Bp4KFWbsSi+zFh2bBiV+6XLUdEhrIydGgyAEDw\n",
       "AuQZ++oS61zJUPeC1WixhCl7NGSWLx0RGcoM7igACF6AcjPIzEpQKNG75S5b7oSBBaoXyZLP/Wgx\n",
       "ERnKK3ix8AIgeAGKT61Wsw+0j9RIqYmtvAOFKdOIDI+jxURkKB8jxeIFAAQvQB65nvKgg5IhYcr8\n",
       "v1exCFaf3H5iV0QtERkAABC8AAC5J7by9g1TphEZkgajEZGhnODSAIDgBSgdvLKsEIOGKSMiQyXB\n",
       "pQEAwQtQOphlrXoMEqaMiAwAAAheAIBikRam7I+/9XvftQtSIjK8JiIDAACCFwCgCKJXxOylMGX/\n",
       "7e/9/u3w+Z9/9w/+C3c1IoNs/4jaAwBA8AIAFIVLVt6/+Vf+yl9r/d4N90e/87vu7/61b7WibcUF\n",
       "YomIDJXA+vDepzoAELwAAIUlKUzZP/jOdfc//f4fJG3+iIgM1YDJZwAQvAAAZeOSlfdbtW+473zj\n",
       "SjP4uYpjAAAoCTWf2lQDVIi5P/qd373/v/yNv0VNAMAn/uSXJ27DJ3c1jB1AmdnqdrvvqnCi3/Tp\n",
       "KdcbAADgDJ6JUCX2faqE4MWlAQAAAABKjVh4eX0DVWLOMRIbANLhmQhV4l1VTrTW7Xa53FAZarVa\n",
       "2128snzm7/82tVIdTr7/g1v+3897iZ0bv/gZ90T12oVPD0LfJtSoEYDygUsDAFSJLfvlP17t8K+q\n",
       "KAaA6naAjmwnaELH2Nbj1KlxBC8AwNjwQnbORe4sz//tB/fL3/7WLrrmiFxTNXFznVqAGdD0qeET\n",
       "ghfBCwAwVrbslz//T//pP/zjX/4b90//3ZV5Bx6rOIZqcNd8fk11wJS459Ptbrd7TFUgeAEAxoIX\n",
       "sDLhxE277IsPf/5/yn8RvP+h2/2zaJc2tQYAk8IL3VPELoIXAGCcYvd6goB9/S9+9Zdnpt2Pv/2t\n",
       "+5e//vdb0fr7fr8lag8gn4iPrU8dn5Z9OpHPuryuy090m12fGmY/Wb8e/HT1//wAx5X9Wz4d6P5d\n",
       "/TxvtgnrmmbZfCizfr/kJ5xQ7gO7PyB4AQbljfk8R3VUgufu3DfXcknM/vFf/L//wl19nd1WsQwA\n",
       "+UREpghIsZQe6wCwA12+4dOaO/eT3TWDw+T/sk97uo3T9YOIy5Yec03zaER5rOj/TyLclHMtJc+O\n",
       "lmtHtznVBGPim1QBVIwPVEF18IJV/DMfR4sl9Ng7/xSKN2/79BPzXVwgVh3uDWXnLu1DYRGhudLt\n",
       "djdVWK7rsnt+2aEuk/+7KiY31I3gRsjAr99RkbxshGoq4opg99c89vQYCz4dyrH9MhGtYkluaZkk\n",
       "PdD9kwj7hjJscHnHCxZeACgzz6PvHxOWneFF8L7/9yJa/JQwZaXHWvHfUB2F4jSIXUUsuyIom+rq\n",
       "sKxCM6yzIrWubghNI54HQlwlNI+wb9MIYxGsIoTXjdje65Hdnpa7gyvDZMDCC1XDWnDuUh3lxQvV\n",
       "R+7qrHqrXtj2suKJRVf2uxaJ5kfUKED+BG/0PQjFTh+hKiK0NexBVUi3MojkTSO0N/tsu+gu3BqW\n",
       "1Wq82MMiDAOChRcqhW88rAXnGjVSamJL7lsvdrd67aBiON7vIWHKSg0uDeUSwOIWUEtID1SsdlSs\n",
       "isvB7UFn1lMXBclDBKmEFruRlIf67YqwPs4iwjVqg4je2+7cnWFe9wcEL8DoEHS+nHiB2nZRGDJ3\n",
       "br3ti04t/L6PeIbygEtDeQhuAb2iLoiv7LG4HIg/r43gkJEFFajiOyzi+jTFBSH4E4tP7pmlVy3D\n",
       "ro/wlbKFgW0NLimCF2AU3prPuDWUT+zeShC3r9RHNyvx/ncIU1YJwQvFJkQ32FVf2JaGILNRGmQQ\n",
       "W0PXiyjdHfAYZxZbzbOlFuNLeajgFnG7qX67a7rfeprA1jBlocwhvx0uKYIXYBR4bVlu2u6yu8pH\n",
       "l9G6G/Di+KW7GqbsOWHKSskd8xkLb4HRCAz3VCiKJTYMGLN+sOI2sKfLF1SMigjOOsVvsNg23YUV\n",
       "dzHkocJ6W4+5puU61f1CeLJY7NZ1/wWT51o0IA9GRPxaqAWo1k1fq225i1BVz/xvoE2tlAP1tf1J\n",
       "tPiZuinE98G+uxjU9pm/D/ajvMT6/9Not698XqvUdGnagutWDA3qzwkAxQELL1SRd1RBaYmFrfji\n",
       "DuV/64WtWPu+ihY/IUxZqbAuTW+pDgAEL0CZYLa1EqI+tnEYsnafMGRZBPTHaNkWtV0abOcFVycA\n",
       "BC9AqfiQ8sCD4ord6+6qdfd1vzBk/VCxHOd7nzBlpRS8+1QHAIIXoDREvpo3qZFSsJpwLdvjyNiL\n",
       "XnGJiMOUbVHlpYAYvAAIXoBS8+k1da1WIzRZgVGf2qfR4hcDhiHrx1L0/aY/LoPXis8t85kIDQAI\n",
       "XoDS8SbloQfF43lCZ2asYlTFcxymrE2YssJDSDIABC9AZQQvFt6Cor60D2MBPOJAtTSWou/XHDOw\n",
       "FZbozc7HbreLSwMAgheg1IJ3juooLLHgfJ8Uc3cc+Hzf+X/PosWPNV4vFI+7Ke0BACB4AUopeBEs\n",
       "BUTDkN2JFk/ar1YE9sc+ohuKJ3j3qQ4ABC9A6eh2u1bwXqvVareolUKJ3esJQvO1Tgk8MdRVIhbV\n",
       "EqbsEVel0IIXCy8AghegtLxOefhB/mm7cx9ay1SiJmhs33hWrucMYCsc9xG8AAhegCqAH28B0TBk\n",
       "T6LFX+lUwNMiFtc3pyW4YXQSBqy9o1YAELwAZWXffMbCWxy2ou/iU9ueZgE0TNmrWASrGIf8M5fS\n",
       "DgAAghegdFiL4H2qI/9oGLL4WrUnFIasH6vu8gC2a9MW3oDgBQAEL0BP9DXmpylja7XaHLWSe7ai\n",
       "7+916t+po2HK4mM/VlEOxRG8+O8CIHgBSs9+ykMQcoYXkm137itrWZpxsZ7bTpPS5mrlF/XfvWY6\n",
       "vvvUCgCCF6BKgpfQUvkVuxIBIR4U9lp9aWeGulLEAve+xgiGfGI7tq+oDgAEL0DVBO+dWq1GaKl8\n",
       "IpbUOAxZLkSlhil7HZeXMGWFELz7VAcAgheg9Kgfr42pipU3Z+jUvY+jxc/UhzYvxNbna44wZXnl\n",
       "IYIXAMELUEXsQ2+O6sgd8cCwjy5n0/lqDOAX0eKnhCnLF7VazXZo30czLgIAgheg1NjpaLHw5gid\n",
       "sjcOQ7Y6ozBk/YjDlLm8CXPAnQEAwQtQUXSUdhAq16JZmGB2Yvd6gmB8qz6zuUNFeFzeh4QpyxWP\n",
       "Ujq6AIDgBagE9uG3RHXkArGY3kxYllu86G27q2HKsPLmAO3I3jQdXQQvAIIXoHLsm8+4NcwY9X2N\n",
       "xe2LWYchG0CoW+7482EA2+yxHVnCkQEgeAEqibX23MStYea03eUwZB9dQSZ08KJc7qU4TFmbMGUz\n",
       "B3cGAAQvQLXpdrvif2mtPkvUymxQn9c4DNnznIUh60d8/1xzzMA2M2J3BgQvAIIXoMoQrSEfxMJQ\n",
       "fGIL5Qer4vyraPETwpTlogPySju4AIDgBage/iG45S6iNdyMYnbCFNApeeMwZO2chiHLItzjMGVb\n",
       "XOWZC16suwAIXoDKg5V3dmI3KQzZ67yGIeuHivR2tPg+Ycqmi3Zcgz/4R+3YAgCCF6DS2IfhY/+w\n",
       "ZKDR9Fh1lweqhWWFxYteEfDve9xjMHmWUjq0AIDgBagmOgmFFShYeaeA+rY+jRa/0Cl7yyS4hJv+\n",
       "fNtc9cnjO6xyXz00i4iJDIDgBQBly3wmfup0iIXIx7LUvcYOjuO+rhKmbOqdjfe+Q/uGKgFA8ALA\n",
       "VcF7p1arzVElk0N9Wh/GArigA9XSiMX7NYe1cdqCl/oGQPACQKDb7b5zxOSdJrEQea9T9JYGDVP2\n",
       "LFr82It9JjiZEDpYLcTe/ejwnQZA8AJATxH2WH0BYczolLt3osWrJb6nPvYR+zA+7H30kti7AAhe\n",
       "AIhIGLy2RK2MXeyKD2s7Wvxap+YtHeqiEYt5CVPGwMgxox3U+3QsAADBC9AfK8ZWCVE2kfqNw5CV\n",
       "umOhMYXfRoufM4Btor/d1wxWAwAEL0AK0cxr1xxW3rGhYcieRIu/Ul/XshNbeW86ooGMDbXuPrYd\n",
       "CmoFABC8AL153kOowPBsRd+lY9GuwolrmLIXsQjWTgCMt0MhociYbAIAELwAGQRvsPLerNVqS1TJ\n",
       "aGgYsvvR4nbJwpD1o+0uD2C7VhXBP0nU7WgpqmcAAAQvQC90ZPdzHqBjZSv6/l6n4K0M6roRn/Nj\n",
       "7QzA8Njpqd+rWxIAAIIXYECBhpV3BHRK3ZvR4qrWpwje9wnLYAjUurtK5xQAELwAQ6ATUbzgQTqy\n",
       "2I0FifBKfVorh7pwxPfSHV9PdKiGA+suACB4AcbwMLW+vAxgG5zn7moYskrXo4Ypex3XE2HKBkMj\n",
       "MzylUwoACF6AEUjy5SUub3Z0Ct3H0eJnFQlDlqUzZbnmiAgyKFbgYt0FAAQvwAjYiA2IksHrzvLR\n",
       "4a96hhf9MilCHKbsKWHKspEQd7dNrQAAghdgSBKsvKv6sIUeqE9qHIZstWJhyPphXWbSOgmQzJb5\n",
       "/BbrLgAgeAFGF71tdzGyntip/cXu9YQ6equ+q6Co+I8F7kPClPXGdzjnos4Ub10AAMELMCasgHus\n",
       "D11IRgTIzYRlcFX02s5UgI5Bb2z9vPId0n2qBAAQvABjQF+Z2pH1vHpOQH1QY3H7oqphyDKyFH2/\n",
       "6euRDkICvqPZjjpT1BMAIHgBxox9uN4hTFkiIkhsGLKPDheQnmhnIA5T1iZM2RWxG3emnmm8bAAA\n",
       "BC/AuPAPVxlZ/5UVJQxgu0B9T+MwZM8JQ5aJpeg7vuJX2TKdKXED4S0LACB4ASaEiBAbpoyHrhG3\n",
       "0XdESUa0U/BVtPgJYcrO8R3LRy4aqKYRVAAAELwA40Yfsktm0UN9GFcaDUN2J1pMGLLhO1OBLcTu\n",
       "2WQvth5koNpLbhcAQPACTFb0ysPW+lxuVXkGNvU1jS25r73YRZQMgHYO2tHi+75+q96hErEbXBmk\n",
       "Q4DvPAAgeAGmxJK77NqwVeG6WHWXB6o5RMnQolc6Dm+jxZV1C9G3Jw/NojYD1QAAwQswJfSh2zaL\n",
       "KunaoD6mT6PFL3TqXBi+A2GRMGXtCord2JXhtf/d4RMOAAhegCmLXnn4xq4NtypWDbEA4ZXziGiY\n",
       "slexCK5gmDIRu9aVYYm7AwAQvACz4ZGrqGuDhiF7GAtgBqqNhbjTUKmIIBrj2t5bq7gyAACCF2BG\n",
       "JERtuK+zQVWBWNy/16lyYUQ0TNmzaPFj38m4WwGxK+do76NXOtMhAACCF2CGoleiEbwwi576h/Zc\n",
       "mc9Zp769GS1e4m4YK2LR/ZiwrMxiN/jt2gkmuK8AAMELkBNEANrR9S/LGqpMfUnb0eLX6nsKY0Jd\n",
       "Q2LXhvsa87jMIt/Gc15iggkAQPAC5ATj2mD9ecsah7btroYhW+IumIjo3XKXB0ae1X8ZB7Cp366d\n",
       "mvqZ/13RiQIABC9AzkSvhOKyFjnx5y3VK2gNQ/YkWvyV+pzC5DoYlpuuZJEw1G/3S7NIQpC1ufQA\n",
       "gOAFyKfo3XKX/Xmf+If5UolOcSv6/jFBkMEYUVeRF9HiVe18lEHsirV63ywSv91HXHkAQPAC5Fv0\n",
       "isC1/rzP1YJVaHSK2/vR4jZhyKZC210ewHatDB0NI3ZtvN1H+O0CAIIXoBjMucv+vPslmJQids94\n",
       "q1PhwoRRl5G4rh9rLOSi31N2kNqqugYBACB4AfKOWqisGDkbxFbUyA06tW0chowZ1aYvDt/36YQU\n",
       "BvVvt4PUviLeLgAgeAGKJ3rFUvW5WSSWrMJFbtCIALG4fUUYsumSEqbsThHDlKlfux38KJNL0IEC\n",
       "AAQvQEFF75a7PGOWRG7YKthpiCUuDkOGOJmN6JUOUxym7HmRwpSp2P3aLBJ/9yWuLgAgeAGKLXrb\n",
       "7vIo+8dFEb06le3jaPEzwpDNlLizca0oHRAdvGndMMRFY45BagCA4AUoh+hd8v9eRaK3CCIl9hH9\n",
       "6Eo+vW3e8Z2NN+5qmLKneQ9TpmJ33xGRAQAQvAClRkSvDVf2ZZ5j9KpvaByGbJUwZLlg1V0OUyZs\n",
       "FUzszhGRAQAQvAAlw0RusKL36zyKXvUJbUeLX+tUtzBjtNMRW9rv5zFMWYLYdYhdAEDwAiB684BY\n",
       "EOMwZG2uYK5Er1yPOExZrjokKWL3c8QuACB4ARC9M0V9QWP/4heEIcsl8T1z01+/XPiG9xC7W1w2\n",
       "AEDwAiB6Z00chkz8LdtctfyhnZA4TFl71mHKELsAgOAFgH6id2biUn1AH8YCmDBkuSbuJF2bZQcF\n",
       "sQsACF4AyCJ6n84wTm88EOq9IwxZrtHOyFfR4icaQ3naYvcRYhcAELwAkFX0Tn1yCg1DdidaTBiy\n",
       "YtB2V8OUTbWjou44P3aXQ4/9CLELAAheAOgnet/4NHF/TPX5jAXSa53KFnKOdkriwWoSpuzRlMSu\n",
       "CG47XXCIs8v9AwAIXgBIFL12Fi2xuO6rX+QkEbF0LWEZFEf0bkUdJuemYOXVNxFPE8QuoccAAMEL\n",
       "AMmiV6chThK9c5M4poYhexotfqFT2EKxiDspEqasPSGhe13eQPiPj81iEdy3ELsAgOAFgCzCV0Tv\n",
       "F2aRWF9/MqGwZVvR948O624h0TBlr2IRPO4wZfrG4Y277PMt4dHm9E0FAACCFwAyiV55Hf0jd3kw\n",
       "koQt2xqXX6+GIbsfLW4zUK3QxJ0V6SyNzbVBO10irO1MfC/8/YrYBQAELwAMJXpl0I+IUjuFrLxC\n",
       "FheHW2M4xFb0/b0Xu4QhKzAapuxZtPixdm5GFbtyb3ztroYdW6LmAQDBCwCjiF55dSyvkO2MWvIq\n",
       "+Y3GPR0KnYL2ZrQY4VIOnkedJKE9gtC9pf66T8xiefPwGWHHAADBCwDjEr0ymG3OXZ5gQKxsP1ar\n",
       "26Bi93qCAHqtPqBQcNQlJb6+9zXW8qBiVzpVsb9uGJzG/QIACF4AGLvwFats7Nf7ROP1DhK6rO2u\n",
       "hiFbooZLJXq33OW3AmfXPesANo3CIJ2pH0f3ylf+PryLvy4AIHgBYJKiV/x6RdzamKtiffupFyh9\n",
       "oyvolLNPosVfqe8nlIt29F1cWPreIxoCL8mF4Ufa6QIAQPACwMRF7zuxsrmrg5O+9GKl34C22AXi\n",
       "oxvBvxPyi7qovIgWr2rs5TSxK/fCT9xl/26xFN9l5jQAQPACwCyEr4iTz9zlAUoSZuxNkrVXp5qN\n",
       "w5CtEoas1LTdZReYxDBlYtX16Z27OgnJMw059o6qBAAELwDMSvTuu3MXh3hA25cJvr2x0Hmrvp5Q\n",
       "UtRVJb7uD0OYMuOrG1t1xWXmh9qpyj3+HFo+Hfh0ov8XovVNn9b184JP3SjN6/LlaD/Ja13Xd/uk\n",
       "+eh4JylllG0b3J0ACF4AGEz0flDfytjaG3x7n7/7W7fX3dUwZPhjVkP0tt3VMGXPNQKDCOLYp/uZ\n",
       "Dkwr0hTBIjY3fLrn06FP2yI6zfptXS6I2Dz26YFJh5o6kRiVZce+Lvb8/9u6bE0/39bPwm3dJiDC\n",
       "eceI3V3/r+WTbPPAb3vMnQkwWb5JFQCUVvjuq0W3bUXMtW9840nNr442f0UYskohnZsf287QH3/r\n",
       "9378z//yl3YbseouFUzohnv/gRGXayo4RQQfBmuv3yYI0LoRsZZTv+2OCtMV3WfFHOPYrz/bLghW\n",
       "//00rDPHl/wXVEifWXb9PxHf9xC6ANMDCy9AuUWvtfaeRXL4o9/5XVG7tQQBBBXBd25e/qbb/VO7\n",
       "7O/81f8sfBQf3y8KaNXNiohPK26DhTeJHd0+iNeuCtZBjyeCOliUZf8NFdR17kYABC9UnEH88KLl\n",
       "u/Jg0s/44Z0L3/0QyeF//dVffrz7r9+5//nf/9uzdX/yyxP3+//q/2qPaXpiyP/vSvx023/3z//V\n",
       "2eQR/8dvfu3+q//v/3H/8MNfyNdX7jwCQ5mmlF4w4lUQ6+phJHiX9Te8a3/zul19xN+2HH9T617y\n",
       "FpEr/6UtCW0bwhcAwQsVZhA/vPAwX9D97AMLP7wL4dv2/259/O1vX/yDkz9zP/zX790//XdnQRke\n",
       "+/Rzf05bIoi49UordpfceUzdp//bb3797bk/+4W779Of/vpXYv2XqYEflSkCgwpJ6RRvmt9nbNFd\n",
       "1N99cIPYDe1FtM8wx29oe2TF9lkb5POu6XGljB3uTgAEL1QU8cMTPzt96KwZEewS/PAC6868rtR9\n",
       "gx9eWLbi02b0QDvzw9PvvfzwgqXG+uGtJfj/5blexc1BhM9n//d//M1rL37tahG+78QCiPAtl9DV\n",
       "MGNfOzNY8X//za/FfeFzdV/YL8B5NHySDuyRWmQP+rgYbKu4XevxezjWtKfi1znjxjAiZ51kn/dp\n",
       "dMy1qH1a4C4FQPACJBH74Tnz4ItFMH54yQ96cXOYc+fTE9tR+xLG7KkK3+e4OpRP6LpzP12ZqOSW\n",
       "vwe2CnIu0tk9UhF5rL9/saCu69uWePtt7ZQuRoJTPvf7zZ6ajq5z6T6+WQTvpvl+GIS7WVYPxwMA\n",
       "BC9ATz88fTCJCE2y5OCH11v4vvRJRO3nCcJXojsEVweEbzGE4XW10CcJXeErFbptsfYX5Jzkt7ut\n",
       "wvCBvv0RF4TbKnznbSdWxa78PhfD/ub3eahC+azdUD/8prpLhWNcckEYxl1J24lT+/ZHPwc3q6Zu\n",
       "s6CdZwBA8ELFH+BZ/PDkYXec4OKAH1524buVInyF4OP7Umbh4q7M5e/klk4aIUL3aYLQlWmF/1Ci\n",
       "dhRF6Ea/b/mNbUQC8tR0cpe1HhZURMr2Yvk90rSt2+2ZDnT4be9qkvzuGYvwvIveJA1AbN0NPNDj\n",
       "7GqbIeeE4AWYMMThhVk8mBv6AJvXB45YPHZ6NPo9/fBMfiv6uR6Wj2kgWV8/PBOvs/DoK+4tHeDU\n",
       "joTTQ0l+3Xtd97KA4qlsvyeZMGJJr02MuC6ICN4q+GC0EGllM+F+PdT4t2dWXO301nrkJXmIG0RT\n",
       "XZQe9DnuojlWnO+auzxw9tC0UztJYlnbkUXuXAAEL5T74RysKU4fBiJIm/oAmrcB43X74Id3r4cf\n",
       "XrDWxBZWGdjywDyQRvHDW4wearGgLp0fXiR8Jd03q0UEy+ty8fF9qYJqnzt8ar+jW3pNltxVS64g\n",
       "HRK5fs+L3iGJXJFOdLKHNBqRAE26r091Mor1XmJXXSQOew1IjTvpKqAP9fMOdyoAgheq+ZC2fniL\n",
       "4UGiLgtnPnfykAkPkSQ/PHfuE3fqjB+ebr9hjiMCtROsMSGu5jj98Pzy4Ie3pmK3tH54RvjOqcB6\n",
       "bFZf0++P1eor1sSXZQptlaPfj0TNeKTpYcpmb1XkbpXo1K1vfD8ReZzxnt7o93vNsg0AFAd8eGGa\n",
       "TMoPLya2tOKHNx7hu6/hzP7QnY/wj/18xdL4pTv39X3j0yoD3cYidB/JoEF37pv7dYrYFf/cH2p4\n",
       "sa2SVYEVsRJScLFHItpBtX8rCzpRUassxzQTJB1xhUesS99AUAswrYYh3Gw3kh5MOotZPW19tK1s\n",
       "J9vfM6HC0raV7RbTXk1qQ7UX8tHR2uJesaHCe48HaboYc+n+owGxOooIy5Xl15d93124aXyWF5eM\n",
       "yJI7586t6L3qdavsftQSBcWduzZ9iqEN0OM+kbdyNxLWN8Y9QVC/Y45D8KphJcmHHBC8kMOGSNwP\n",
       "svZQ+4pYI1Sv+P0Oug2MVaSt+nSnx6ZiFRafXxGX+7MUankSvL4sd43AvZ+h/kTkvqnQ/SUdz/B2\n",
       "54rojdydoLrtkIhD8c3esD7UJuRcY9yiMe2YCF4EL1S3IZIG50C/9msUVnhwFfpa31LxttRH/Aqv\n",
       "jfjdn3I5ZyZ4VeDOmXQNkZupg7uuX6V9sOEG6w7rL5RQNCJ4EbxQvAYnuCAINxC0lRO/IuoeZtjl\n",
       "rQpgEXZvJinwpiV4tQ7uaprT/9f67IbITe84i199CGkYhK+4K22O+3U1IHgpe3lg0BpMBRNZQWDe\n",
       "+Opc93c+SdQAEb3S6ZFpjF+4qwPeAmIRltndZHDWT3Wwxr7O9Cazh83ldSCcznA2p9P5trXc4rLx\n",
       "c59+7M4ng7ifInYlXu4rn75w55ND3NIJIhC7l+8nCRMmltzb8vAXn0mfxAVqDbGba9F2pL/l+SRB\n",
       "lzQoSweCHYWOjkTt0XxO9HOzX146k55Y9bbNNt1BBoFJ1B+Zutqcw5Eev9Gn/GH5un5f133XB8k/\n",
       "Q/kk/nTH7H8wzUF7RYKwZDBNNrThkR+nww+vcmJFxN9LTcHyOWfSzZRd77sLS+xT3Vf+iTVY8nyj\n",
       "/99pEt6M2z/YzDAn/sp39fOcKeMgiMDddxfuHAhbKDONIbaRDnI9cmVxxmgi0REepAxGtnkdhrzM\n",
       "dyHLwGixrAZhfWzykuOvZDxHOQfJZ37E/JPKOFBc+8p3vHBpgCn39PHDg7R747q7eOUf/l8bU/av\n",
       "E5bdUfFqxbNl3Md/46bgqgGQw992EBpXBGraK3uzTzCWbOikISLoOirsxOJ/L0NeA7sFmOgLh/pc\n",
       "OrTGmfBGIcMxwyRJcg4yfuVYz2PU/OWZGcbFJMa192mNaasvwMILU0VDfckPM/jhNd1lP7w9aqmy\n",
       "98YlC7A23rf8v1sqgMPn+0Nk32+fO2M6DRHO74y4fYe4BRiJnTCNu7YTMpX0ioq95oRCjS2bZ9OD\n",
       "hGnlBzleiD2/Nub8Q1z7tTiuvU6IdKDPWQQvghdmKGzOerTUBGS4V96pgNxPeCjN6cfwXyyy1zMK\n",
       "3GF474zLhLvsRvGO2eUAJiN4k54h/vcfLKdi6Ry3/3YYZ7I5Jhe7jQnkvxzy6FE/4t9bx00QwQsA\n",
       "xRbDQQTv99pOXSXuJqySaZCDZfcLFbEWRCzA7EkTa/UJHjP41R6OI7MEwTlS/tGAthMd05BGY1zn\n",
       "geAFAMi3MP7gki3E1mf3TV5mWgOAmVPPef52/35x7YleguAFAACAKWDdD6YtLodBLKJNTTs5zN+K\n",
       "WCZqyghxeAEAAGDSAtK5i1f5lmnGZc8qDIMIXdaoB+NmpPyJa4/gBQAAgPyxZwTeWTxanRSiNSXB\n",
       "Fiyi9aTJLxLYdBdW6d14koukSS8GZBz5h4FwHY364KI8GhMS6wheAAAAgBSBF0SnCDyZZl6SxGRf\n",
       "m/TBNczXoTl+VyeDSNv+LFyYilIRnwc6k9mBlv0g60xok8rf57Fj6q6jM9AdmDyOHNZfBC8AAABM\n",
       "BxV49yLhK1bfBzoxwrG76m7Qb7DV8YDrRGDu6HFO++Wv4TNvq6iUzw0Vp8fuwkKbpTzHk8pf6+6e\n",
       "2b7pLsK0bTji2l+CmdYAoJqNX6227y7i9X5GlAYAgPKChRcAAAAAELwAAAAAAAheAAAAAAAELwAA\n",
       "AAAAghcAAAAAAMELAAAAAIDgBQAAAAAEL1UAAAAAAAheAAAAAAAELwAAAAAAghcAAAAAAMELAAAA\n",
       "AIDgBQAAgEpQq9UOfFr3qeNTt0fqRPst6L5Nn7Z9OtEkn+vUbHX4JlUAAAAAOefQp2OfdvT/uk+3\n",
       "zfojn9Z82oz2W9Z9mj6d+vTAJxG62z6JOF6kahG8AAAAADOn2+2uhM+1Wu1Ulx2bZfLv1C87Ncsa\n",
       "/t+8iFq7XNeJMG5Rs9UBlwYAAADINequMKhAXfBpJxa7hlNqFsELAAAAUGTEnWGzlximihC8AAAA\n",
       "AIWkVquJK0O92+3uJawT/1/x492gphC8AAAAAJMWpg2NvHCkbgsHQ7guJJFo3VUhLPmvWR9gKD8M\n",
       "WgMAAIBZiF0Rn7v6VSyxIkAlmoKEH5v3gvTBkPmK9VZcFm4nHE+iM2z4vDe5AgheAIAq8MZ8/kB1\n",
       "AExV7DZUfMrAscXgeqBiVZbPi6XXLx/G7UDE7l4UxSGIXTnOph7fYeWtDrg0AEAl8Q+6VZ/mNL2h\n",
       "RgCmirgVnPnRWj9bjaiwpl+Xh8w7xN61dPR4IoaPQlIhDFXoZPmbi1oAAACA6YmPWi2IjxtJYcNk\n",
       "NjQVqDcSYuiK28O8tf6q369YdQ/952VcFgDBCwAAALMUu+JOcJRx83siYqk1GBV8eAEAAGCa1M3n\n",
       "frFw8bGF8XS0sPACAADA1ITH+cC0E/16o8dMaABjg0FrAAAAMDVU4AY3hQVqBBC8AAAAUEbCgDOZ\n",
       "dOJKNAadkKJONcG4wKUBAAAApi9AziMrrOtXsfoGf10Z1CZid4VoC4DgBQAAgKKLXgkxJhbeeRW6\n",
       "QfieTRDBxBCA4AUAAAAAyAA+vAAAAACA4AUAAAAAQPACAAAAACB4AQAAAAAQvAAAAAAAY+P/F2AA\n",
       "dpneoblP1lsAAAAASUVORK5CYII=\n"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Image(filename = 'W.png')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* So for *n*=4 we will have the following\n",
    "$$ { F }_{ 4 }=\\begin{bmatrix} 1 & 1 & 1 & 1 \\\\ 1 & \\left( { e }^{ \\frac { 2\\pi i }{ 4 }  } \\right) ^{ 1 } & { \\left( { e }^{ \\frac { 2\\pi i }{ 4 }  } \\right) ^{ 2 } } & { \\left( { e }^{ \\frac { 2\\pi i }{ 4 }  } \\right) ^{ 3 } } \\\\ 1 & \\left( { e }^{ \\frac { 2\\pi i }{ 4 }  } \\right) ^{ 2 } & { \\left( { e }^{ \\frac { 2\\pi i }{ 4 }  } \\right) ^{ 4 } } & { \\left( { e }^{ \\frac { 2\\pi i }{ 4 }  } \\right) ^{ 6 } } \\\\ 1 & \\left( { e }^{ \\frac { 2\\pi i }{ 4 }  } \\right) ^{ 3 } & { \\left( { e }^{ \\frac { 2\\pi i }{ 4 }  } \\right) ^{ 6 } } & { \\left( { e }^{ \\frac { 2\\pi i }{ 4 }  } \\right) ^{ 9 } } \\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We note that a quarter of the way around is *i*\n",
    "$$ {e}^{\\frac{2\\pi{i}}{4}}={i} $$\n",
    "* We thus have the following\n",
    "$$ { F }_{ 4 }=\\begin{bmatrix} 1 & 1 & 1 & 1 \\\\ 1 & i & { i }^{ 2 } & { i }^{ 3 } \\\\ 1 & { i }^{ 2 } & { i }^{ 4 } & { i }^{ 6 } \\\\ 1 & { i }^{ 3 } & { i }^{ 6 } & { i }^{ 9 } \\end{bmatrix}\\\\ { F }_{ 4 }=\\begin{bmatrix} 1 & 1 & 1 & 1 \\\\ 1 & i & -1 & -i \\\\ 1 & -1 & 1 & -1 \\\\ 1 & -i & -1 & i \\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Note how the columns are orthogonal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1 & 1 & 1 & 1\\\\1 & i & -1 & - i\\\\1 & -1 & 1 & -1\\\\1 & - i & -1 & i\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1  1   1   1 ⎤\n",
       "⎢             ⎥\n",
       "⎢1  ⅈ   -1  -ⅈ⎥\n",
       "⎢             ⎥\n",
       "⎢1  -1  1   -1⎥\n",
       "⎢             ⎥\n",
       "⎣1  -ⅈ  -1  ⅈ ⎦"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F = Matrix([[1, 1, 1, 1], [1, I, -1, -I], [1, -1, 1, -1], [1, -I, -1, I]])\n",
    "F"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1\\\\1\\\\1\\\\1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1⎤\n",
       "⎢ ⎥\n",
       "⎢1⎥\n",
       "⎢ ⎥\n",
       "⎢1⎥\n",
       "⎢ ⎥\n",
       "⎣1⎦"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F.col(0) # Calling only the selected column (counting starts at 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The columns are supposed to be orthogonal, i.e. inner (dot) product should be zero\n",
    "* Clearly below it is not"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$4$$"
      ],
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F.col(1).dot(F.col(3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Remember, though, that this is a complex matrix and we have to use the Hermitian"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{pmatrix}\\left[\\begin{matrix}1\\\\i\\\\-1\\\\- i\\end{matrix}\\right], & \\left[\\begin{matrix}1\\\\- i\\\\-1\\\\i\\end{matrix}\\right]\\end{pmatrix}$$"
      ],
      "text/plain": [
       "⎛⎡1 ⎤, ⎡1 ⎤⎞\n",
       "⎜⎢  ⎥  ⎢  ⎥⎟\n",
       "⎜⎢ⅈ ⎥  ⎢-ⅈ⎥⎟\n",
       "⎜⎢  ⎥  ⎢  ⎥⎟\n",
       "⎜⎢-1⎥  ⎢-1⎥⎟\n",
       "⎜⎢  ⎥  ⎢  ⎥⎟\n",
       "⎝⎣-ⅈ⎦  ⎣ⅈ ⎦⎠"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "col1 = F.col(1)\n",
    "col3 = F.col(3)\n",
    "col1, col3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{pmatrix}\\left[\\begin{matrix}1 & i & -1 & - i\\end{matrix}\\right], & \\left[\\begin{matrix}1\\\\i\\\\-1\\\\- i\\end{matrix}\\right]\\end{pmatrix}$$"
      ],
      "text/plain": [
       "⎛[1  ⅈ  -1  -ⅈ], ⎡1 ⎤⎞\n",
       "⎜                ⎢  ⎥⎟\n",
       "⎜                ⎢ⅈ ⎥⎟\n",
       "⎜                ⎢  ⎥⎟\n",
       "⎜                ⎢-1⎥⎟\n",
       "⎜                ⎢  ⎥⎟\n",
       "⎝                ⎣-ⅈ⎦⎠"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Dagger(col3), col1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "[0]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Dagger(col3) * col1 # Another way to do the dot product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* So, these columns are all orthogonal, but they are not orthonormal\n",
    "* Note, though that the are all of length 2, so we can normalize each"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}\\frac{1}{2} & \\frac{1}{2} & \\frac{1}{2} & \\frac{1}{2}\\\\\\frac{1}{2} & \\frac{i}{2} & - \\frac{1}{2} & - \\frac{i}{2}\\\\\\frac{1}{2} & - \\frac{1}{2} & \\frac{1}{2} & - \\frac{1}{2}\\\\\\frac{1}{2} & - \\frac{i}{2} & - \\frac{1}{2} & \\frac{i}{2}\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1/2  1/2   1/2   1/2 ⎤\n",
       "⎢                     ⎥\n",
       "⎢      ⅈ          -ⅈ  ⎥\n",
       "⎢1/2   ─    -1/2  ─── ⎥\n",
       "⎢      2           2  ⎥\n",
       "⎢                     ⎥\n",
       "⎢1/2  -1/2  1/2   -1/2⎥\n",
       "⎢                     ⎥\n",
       "⎢     -ⅈ           ⅈ  ⎥\n",
       "⎢1/2  ───   -1/2   ─  ⎥\n",
       "⎣      2           2  ⎦"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Rational(1, 2) * F"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We also note the following\n",
    "$$ {F}_{n}^{H}{F}_{n}={I} $$\n",
    "* Just remember to normalize them"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}\\frac{1}{2} & \\frac{1}{2} & \\frac{1}{2} & \\frac{1}{2}\\\\\\frac{1}{2} & - \\frac{i}{2} & - \\frac{1}{2} & \\frac{i}{2}\\\\\\frac{1}{2} & - \\frac{1}{2} & \\frac{1}{2} & - \\frac{1}{2}\\\\\\frac{1}{2} & \\frac{i}{2} & - \\frac{1}{2} & - \\frac{i}{2}\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1/2  1/2   1/2   1/2 ⎤\n",
       "⎢                     ⎥\n",
       "⎢     -ⅈ           ⅈ  ⎥\n",
       "⎢1/2  ───   -1/2   ─  ⎥\n",
       "⎢      2           2  ⎥\n",
       "⎢                     ⎥\n",
       "⎢1/2  -1/2  1/2   -1/2⎥\n",
       "⎢                     ⎥\n",
       "⎢      ⅈ          -ⅈ  ⎥\n",
       "⎢1/2   ─    -1/2  ─── ⎥\n",
       "⎣      2           2  ⎦"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Dagger(Rational(1, 2) * F)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1 & 0 & 0 & 0\\\\0 & 1 & 0 & 0\\\\0 & 0 & 1 & 0\\\\0 & 0 & 0 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1  0  0  0⎤\n",
       "⎢          ⎥\n",
       "⎢0  1  0  0⎥\n",
       "⎢          ⎥\n",
       "⎢0  0  1  0⎥\n",
       "⎢          ⎥\n",
       "⎣0  0  0  1⎦"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Dagger(Rational(1, 2) * F) * ((Rational(1, 2) * F))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Now why do we call it *fast* Fourier transform\n",
    "* Note the following\n",
    "$$ { W }_{ n }={ e }^{ \\frac { 2\\pi i }{ n }  }\\\\ { \\left( { W }_{ n } \\right)  }^{ p }={ \\left( { e }^{ \\frac { 2\\pi i }{ n }  } \\right)  }^{ p }\\\\ { \\left( { W }_{ 64 } \\right)  }^{ 2 }={ \\left( { e }^{ \\frac { 2\\pi i }{ 64 }  } \\right)  }^{ 2 };\\quad n=64,\\quad p=2\\\\ \\therefore \\quad { \\left( { W }_{ 64 } \\right)  }^{ 2 }={ W }_{ 32 } $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Now we have the following connection between the two\n",
    "$$ \\left[ { F }_{ 64 } \\right] =\\begin{bmatrix} I & D \\\\ I & -D \\end{bmatrix}\\begin{bmatrix} { F }_{ 32 } & 0 \\\\ 0 & { F }_{ 32 } \\end{bmatrix}\\left[ P \\right] \\\\ D=\\begin{bmatrix} 1 & 0 & 0 & \\dots  & 0 \\\\ 0 & W & 0 & \\dots  & 0 \\\\ 0 & 0 & { W }^{ 2 } & \\dots  & 0 \\\\ \\vdots  & \\vdots  & \\vdots  & \\dots  & \\vdots  \\\\ 0 & 0 & 0 & \\dots  & { W }^{ 31 } \\end{bmatrix}$$\n",
    "* P is a permutation matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Going down to 16 will include the following\n",
    "$$ \\begin{bmatrix} I & D & 0 & 0 \\\\ I & -D & 0 & 0 \\\\ 0 & 0 & I & D \\\\ 0 & 0 & I & -D \\end{bmatrix}\\begin{bmatrix} { F }_{ 16 } & 0 & 0 & 0 \\\\ 0 & { F }_{ 16 } & 0 & 0 \\\\ 0 & 0 & { F }_{ 16 } & 0 \\\\ 0 & 0 & 0 & { F }_{ 16 } \\end{bmatrix}\\left[ P \\right]  $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The recursive work above leads to decreasing the work that is required for working with these problems"
   ]
  },
  {
   "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
}