DM/HW4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Theory :\n",
    "https://twlab.tistory.com/25\n",
    "\n",
    "# Doc: \n",
    "https://docs.sympy.org/0.7.5/tutorial/matrices.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sympy import *\n",
    "init_printing(use_unicode = True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exercise 5.1.1\n",
    "> no random jump case "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0.333333333333333 & 0.5 & 0\\\\0.333333333333333 & 0 & 0.5\\\\0.333333333333333 & 0.5 & 0.5\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡0.333333333333333  0.5   0 ⎤\n",
       "⎢                           ⎥\n",
       "⎢0.333333333333333   0   0.5⎥\n",
       "⎢                           ⎥\n",
       "⎣0.333333333333333  0.5  0.5⎦"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M = Matrix([[1/3, 1/2, 0], [1/3, 0, 1/2], [1/3, 1/2, 1/2]])\n",
    "M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-0.666666666666667 & 0.5 & 0 & 0\\\\0.333333333333333 & -1 & 0.5 & 0\\\\0.333333333333333 & 0.5 & -0.5 & 0\\\\1 & 1 & 1 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-0.666666666666667  0.5   0    0⎤\n",
       "⎢                                ⎥\n",
       "⎢0.333333333333333   -1   0.5   0⎥\n",
       "⎢                                ⎥\n",
       "⎢0.333333333333333   0.5  -0.5  0⎥\n",
       "⎢                                ⎥\n",
       "⎣        1            1    1    1⎦"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#temp = M - eye(3)\n",
    "temp = Matrix([[-2/3, 1/2, 0], [1/3, -1, 1/2], [1/3, 1/2, -1/2]])\n",
    "temp = temp.col_insert(3, Matrix([0,0,0]))\n",
    "A = temp.row_insert(4,Matrix([[1,1,1,1]]))\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left ( \\left[\\begin{matrix}1 & 0 & 0 & 0.230769230769231\\\\0 & 1 & 0 & 0.307692307692308\\\\0 & 0 & 1 & 0.461538461538462\\\\0 & 0 & 0 & 0\\end{matrix}\\right], \\quad \\left ( 0, \\quad 1, \\quad 2\\right )\\right )$$"
      ],
      "text/plain": [
       "⎛⎡1  0  0  0.230769230769231⎤           ⎞\n",
       "⎜⎢                          ⎥           ⎟\n",
       "⎜⎢0  1  0  0.307692307692308⎥           ⎟\n",
       "⎜⎢                          ⎥, (0, 1, 2)⎟\n",
       "⎜⎢0  0  1  0.461538461538462⎥           ⎟\n",
       "⎜⎢                          ⎥           ⎟\n",
       "⎝⎣0  0  0          0        ⎦           ⎠"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.rref()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAwEAAAAVCAYAAAAesOIFAAAABHNCSVQICAgIfAhkiAAADBJJREFUeJztnXvQFlUdxz/Qq4mJt0iYylFBDIEGpCS7mC+UlBUOXf9oMqlsqnFSZ7qYTA0P3VAjzZGsMTM0m/6wQgW7SMYbStpVptBAVB7TUSJQBAGVF57++J2dZ5999+zuOXt99fedeWbfd885u7/9nN/57e2cs6BSqVQqlUqlUqlesuoHOqHfhlqtUalUKpVKpVKpVHk0ht7r+06QMDIm8x+BRcDSmLTXAtcDTwDPA23ge8BRDsa8EjgPWA48BOwFngHuBj5lsQngMuBO4DFT5ingPmCh2aZNLjbPZyio6G+/ZT+nA78EnjT7eRK4A3hPTN4RwCeBe4FdwB5zLBcAL4vJ78Os6bwgO7MqeEH5zObjz+u9CJvHjW2PADcDb06wqw4VESMC+dSH+m8z/RfKi5FN5QXuzFzzN0FFtvmwzqF7zOel5M3qWx8CrgbuAnaabd+Usu029rrYYinj61t54nwZvMCdWZvhwQuyMyuTF/gxc7FtD3Jdvwh4NFx4ROjvfmC1ydSK2dEE4E/AMcCtyJuCmcAsYCPwVmB7irEAnwV+YAxdDfwHGAt8ADjCHMyHCd2pGL0A/AN4ANgKvAI4DXgjEnxOQxwoj83TgXkWu08HZgO3A++LpH0V+AawDVhpjm0McIo5xi9H8t+ION9WYAWwG3gnMNly/D7MmswL3JhVwQvKZ+bL6zLDYztwC8LsROBsoA/4OOlBpgoVFSMCudaH+m8z/RfKjZFN5QXuzPIwrkNFt/lAxwL/Qm74DgM+DVxnyeviW+uAacCzyIXjJOBnwMcSbGkDRyI3NlE9CyyJWe/jW3nifFm8wJ1Zm+bzguzMyuYFfsx8bAMYAM6g9/of6HYHall29juT/vnI+ivM+h9aykU1G5jL0Kcz45Dg3QE+GFPuEMv2vmXKXBOTVpTNAPeYMmdH1gcnl1XA6JhyB0X+n2fyP4JUVjjfcpM2P1LGh1lTeYEbs6p4Qb3MbLzGIU/+tiAn2rBm0WXTBBXpP+BeH+q/8arTf6H8GDkceUEysyLyV6Gi2zzIxcnvgYeB75D8lNbVt2YBE80++sn+lLadanWvXH0rT5wvk1ewfxdmbZrNC7Izq4IX+DHzsQ3kJiD6QARIvgkYb9I2MzTQjkbuVHYjd295tMDs52qHMtPoggirSJunmm09Tu+r6JGIo+0GXpXR3hvNts5P2M/fM24L3JnVyQvcmdXNC8pnlsTrTSbtVkvZnUh3ibpVVYyA+PpQ/7WrTv+tO0Y2kRckMysifxUqq81fCBwA3o5cj9gu0Hx8K6x+yrtAs8nmW3nifFW8oLybAJvK4AXZmFXFC9yZ5bFtgNBNgK2vZFSzzfIOBFxYu4C1wKHIK5s82meWgw5l5prlPyPri7T5M2b5Y3r7Y74FOAH4NfA00j/tYsTBbH3Sxpll3F1qsG4G8mooi1yZ1ckL3JnVzQvKZ5bEaxPyqnQmvU9FQQLYaOSJRt2qKkZAfH2o/9pVp//WHSObyAuSmRWRvwqV0eZPBi4FrgLWpOT18S1fvRzpzrHAbH8WfjdjNt/yjfPKy/28mJVZlbzAjVlhtvVlzPc6s3zQkr4JmAOchAzu8FHQhwvgtwn5voj03zoC6S/2NsRBLo3kK8rmUUjFHGBof7FTzfK/SH+210fS1yCDRP4XWrfNLE+I2df40N+TkEFxScrCrEm8wJ1Z1bygWmZpvJ5CGvcVSH/JW5A+kBOQbgGr6F4g1KkyY0SW+lD/7apJ/ltnjGwiL0hnljd/VSq6zfcBP0W6cC3IkN/Ht3w1ztgW1mbgE8hkKjZl9S2fOK+83M+LLsyq5AVuzEqxrR97d6BrSe5nFvTbusRlhxEtMdu4PSXfFrqjpjvAb5BBYFEVZfO5Jt/KmLTFJm0QCXjvQBx4CnLS6SCvXsL6qFn/EHB0aH0fMoAtOK6zUuyCbMyaxAvcmVXNC6pllsYr0Dwk8IXt2oTwaYLKjBFZ6kP9t6sm+W+dMbKJvCB7m/fNX5WKbvNfR95yhJ9kthL24eNbYfWTravGQuStx1jkzcZUZKzDAWTWlWkJZbP6ViCXOF81L8jGrKm8wI1ZVbzAnVke2wYIdQeKM7YVk5bW2L9t0r9iSU/TBab8v+kN+kkaC7wfmYHgCeT1cFhF2bzW5Jsbk3a5SdvP0EoahYxm79DrcCORVzgdxOGvRUaEr0emuHrQpM1JscuVWRN4gTuzunhBNczSeIGM8B9EnnqMR4LEDLqD8i5POoiKVHaMgOT6UP8dqib4b10xsqm8IFubz5O/KhXZ5mciMS4ay1oJ+/DxrbD6yXaBZlNwk7k8Q9403wK3OF8HL8jHrE5e4M6sbl5gZ5bHtgE8bgKC0dNfsBi61KR/zpKepPNN2fvp9gV10XHI3KjrI+uLsHmyyfMY8X2zLqF75xmn60z6hZH1fcaudchJbSdy9/YGujNATE+wKw+zOnmBH7M6eUF5zLLw6jd5fhWTdigyUHA/vd0k6lCZMSKquPpQ/7WrTv+tI0Y2lRdkY5Ynf5Uqqs33IRd7DyD9osNqYb+o9fWtQP3ku0A70ZR3mQLV5luBLVnifF28wnb6MKuLF/gxq5sX2JnlsW2A0E1A1oHBG83yJEv6RLO09Q206SIkUKxHBkGkfRQhTo8iFTuF3gEiRdicNhgr2McOS/mnzXJUZP0g8F3kJDYKOBx4N3Ic05GT3v2WbeZlViev8H5cmNXJC8pjloVXMB/46pi0PcBfkHZ8iqV8VSorRsQprj7Uf+2q03+rjpFN5gUvjgHBgYpq84eZbZwMPIdcoAS/hSbPj8z/4XnUfX2rKG01S5fZj2y+5RLnlZf7edGHWd28wM6sMNuyDgwOQM9BwIZnAhiNfBBkL+kD28K6GBnssQ44k+5gMB+92izDQTKvzYcgH6s5gATgOK1BTlYTgYOR0ephTTXLdqL1XZ1j9nsD3VktwiqKWV28oFhmVfGC4pll5RU8tbBNAxasj3KsWmXEiCRF60P9N1l1+W+VMbLJvCA7M9/8VauoNv889uObgVzI3Y1c+NwTSivat1wVdLVw/U5LnG+5xHnl5X5e9GFWNy+wMyvFtn7s3YHA76MgE5AZHKIfLfiaKfM3svXXnET8a92RdAcfrS3I5kDB56RXpNh2k8n3zcj6M5GguIOhU9kdHrOdU5EBLruI79rhwqzJvMCdWdm8oHpmWXl9hG7f6NdE0s5CeO1l6KfVl5ly81O2X6SKjBE+9aH+O1R1+y9UEyObzgvcmLnmX0b17R2KbfNxamHv3gJ+vhWon/SuGlOI96fjkK4YHYbOMuPjW75xPqoW5fGCdGbDjRckMyubF/gxy2PbAKHuQHHGtiyGTkCmI+og0zEtBv5g/t9IPOy2ST8+tO5cs24QuNLsL/qbH9nORchTnzuRwUiLgeuRr711kE8lTy7I5kB3mXxpg7GOoVtRa5CBHDeb49uHfNUtqj8jFbHU2HSbyb8beFdMfldmTeYF7szK5gXVM8vKayQy3VkH6Rd9A/K59NuQhm7r9xd8cCnpU+VFq6gYAX71of7bPP+F8mPkcOAFbsxc89fR3qHYNh+nFskXta6+NQ+5YVpGdxaVh0PrlsTs/zlklpprkNj7C+QCs4PMPHVwpIyPb/nG+ahaFMsL3Ji1GF68ApttzMrmFezflZmvbZDjJgDgWOAnSKW8gPTXugr7k5c2Qxt7y6xL+g1EtjMV+D7ymncbcpDPAH8120t68uNqM0i/sQ7ZB2MdjTz52Gz2sR35kp3tIylfQr54uQN5TbUZeWJyvCV/CzdmTecFbszK5gXVMnPldRASKO9FAt4g0ldwJfYZUu4zeY/KsP0iVUSMAP/6UP9tnv9CuTGyRbN5gTsz1/x1tXcors3HqUXyRS24+VawPduvHcl/BvBzYAPii/uQuddXId+gGBGzD1/f8onztuMrild4m1mYDTde4eOzMSuTF/gx87UNct4EqFSq5utIpP9kE6YOValU5Urbu0qlyqoBUm4Cgt+GykxSqVRFai7yetFnekSVSjW8pO1dpVIlaQxD30gAvbMDtYFFof/zzKygUqnq0wpkZhGVSvXil7Z3lUqVpD30Xt+rVCqVSqVSqVQqlUqlUqlUKpVKpXpJ6P8kmar2kmwBXwAAAABJRU5ErkJggg==\n",
      "text/latex": [
       "$$\\left [ 0.23076923076923078, \\quad 0.3076923076923077, \\quad 0.46153846153846156\\right ]$$"
      ],
      "text/plain": [
       "[0.23076923076923078, 0.3076923076923077, 0.46153846153846156]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[3/13,4/13,6/13]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exercise 5.1.2\n",
    "> random jump with probability delta = 0.8\n",
    "> the prevention for dead end, spyder trap "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-0.666666666666667 & 0.466666666666667 & 0.0666666666666667 & 0\\\\0.333333333333333 & -0.933333333333333 & 0.466666666666667 & 0\\\\0.333333333333333 & 0.466666666666667 & -0.533333333333333 & 0\\\\1 & 1 & 1 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-0.666666666666667  0.466666666666667   0.0666666666666667  0⎤\n",
       "⎢                                                             ⎥\n",
       "⎢0.333333333333333   -0.933333333333333  0.466666666666667   0⎥\n",
       "⎢                                                             ⎥\n",
       "⎢0.333333333333333   0.466666666666667   -0.533333333333333  0⎥\n",
       "⎢                                                             ⎥\n",
       "⎣        1                   1                   1           1⎦"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "delta = 0.8\n",
    "N = 3\n",
    "M = Matrix([[1/3, 1/2, 0], [1/3, 0, 1/2], [1/3, 1/2, 1/2]])\n",
    "S = Matrix([[1/N, 1/N, 1/N], [1/N, 1/N, 1/N], [1/N, 1/N, 1/N]])\n",
    "temp = delta*M + (1- delta)*S - eye(3)\n",
    "temp = temp.col_insert(3, Matrix([0,0,0]))\n",
    "A = temp.row_insert(4,Matrix([[1,1,1,1]]))\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left ( \\left[\\begin{matrix}1 & 0 & 0 & 0.259259259259259\\\\0 & 1 & 0 & 0.308641975308642\\\\0 & 0 & 1 & 0.432098765432099\\\\0 & 0 & 0 & 0\\end{matrix}\\right], \\quad \\left ( 0, \\quad 1, \\quad 2\\right )\\right )$$"
      ],
      "text/plain": [
       "⎛⎡1  0  0  0.259259259259259⎤           ⎞\n",
       "⎜⎢                          ⎥           ⎟\n",
       "⎜⎢0  1  0  0.308641975308642⎥           ⎟\n",
       "⎜⎢                          ⎥, (0, 1, 2)⎟\n",
       "⎜⎢0  0  1  0.432098765432099⎥           ⎟\n",
       "⎜⎢                          ⎥           ⎟\n",
       "⎝⎣0  0  0          0        ⎦           ⎠"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.rref()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> S matrix can be transfered into S vector because ∑|R| = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-0.733333333333333 & 0.4 & 0 & -0.0666666666666667\\\\0.266666666666667 & -1 & 0.4 & -0.0666666666666667\\\\0.266666666666667 & 0.4 & -0.6 & -0.0666666666666667\\\\1 & 1 & 1 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-0.733333333333333  0.4   0    -0.0666666666666667⎤\n",
       "⎢                                                  ⎥\n",
       "⎢0.266666666666667   -1   0.4   -0.0666666666666667⎥\n",
       "⎢                                                  ⎥\n",
       "⎢0.266666666666667   0.4  -0.6  -0.0666666666666667⎥\n",
       "⎢                                                  ⎥\n",
       "⎣        1            1    1             1         ⎦"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "delta = 0.8\n",
    "M = Matrix([[1/3, 1/2, 0], [1/3, 0, 1/2], [1/3, 1/2, 1/2]])\n",
    "# S = Matrix([[1/N, 1/N, 1/N], [0, 0, 0], [0, 0, 0]])\n",
    "# temp = delta*M + (1- delta)*S - eye(3)\n",
    "temp = delta*M - eye(3)\n",
    "Svector =  -(1- delta)*Matrix([1/N,1/N,1/N])\n",
    "temp = temp.col_insert(3, Svector)\n",
    "A = temp.row_insert(4,Matrix([[1,1,1,1]]))\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left ( \\left[\\begin{matrix}1 & 0 & 0 & 0.259259259259259\\\\0 & 1 & 0 & 0.308641975308642\\\\0 & 0 & 1 & 0.432098765432099\\\\0 & 0 & 0 & 0\\end{matrix}\\right], \\quad \\left ( 0, \\quad 1, \\quad 2\\right )\\right )$$"
      ],
      "text/plain": [
       "⎛⎡1  0  0  0.259259259259259⎤           ⎞\n",
       "⎜⎢                          ⎥           ⎟\n",
       "⎜⎢0  1  0  0.308641975308642⎥           ⎟\n",
       "⎜⎢                          ⎥, (0, 1, 2)⎟\n",
       "⎜⎢0  0  1  0.432098765432099⎥           ⎟\n",
       "⎜⎢                          ⎥           ⎟\n",
       "⎝⎣0  0  0          0        ⎦           ⎠"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.rref()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### power iteration method "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration 0 ...\n",
      "distance =  0.10886621079036359\n",
      "iteration 1 ...\n",
      "distance =  0.03840438948740428\n",
      "iteration 2 ...\n",
      "distance =  0.006978181649210422\n",
      "iteration 3 ...\n",
      "distance =  0.002694155040223752\n",
      "iteration 4 ...\n",
      "distance =  0.000690717723326753\n",
      "iteration 5 ...\n",
      "distance =  0.00023252459842663494\n",
      "iteration 6 ...\n",
      "distance =  6.747656831871295e-05\n",
      "iteration 7 ...\n",
      "distance =  2.136482502025899e-05\n",
      "iteration 8 ...\n",
      "distance =  6.443969268831849e-06\n",
      "iteration 9 ...\n",
      "distance =  1.998329919632112e-06\n",
      "iteration 10 ...\n",
      "distance =  6.100863484933637e-07\n",
      "iteration 11 ...\n",
      "distance =  1.8792241082335177e-07\n",
      "iteration 12 ...\n",
      "distance =  5.759209807890141e-08\n",
      "iteration 13 ...\n",
      "distance =  1.770416244714274e-08\n",
      "iteration 14 ...\n",
      "distance =  5.432463853003383e-09\n"
     ]
    }
   ],
   "source": [
    "# PageRank Algorithm\n",
    "M = np.array(M, dtype='f')\n",
    "N = 3\n",
    "delta = 0.8\n",
    "elipslion = 1e-8\n",
    "R = np.ones((N,1))*(1/N)\n",
    "#R = np.ones((N,1))\n",
    "K = np.ones((N,1))*((1- delta)/N)\n",
    "# R = delta * np.matmul(M,prevR) + K\n",
    "iteration = 0\n",
    "distance = 100\n",
    "\n",
    "while distance > elipslion:\n",
    "    print(\"iteration\", iteration, \"...\")\n",
    "    prevR = R\n",
    "    R = delta * np.matmul(M,R) + K\n",
    "    iteration = iteration + 1\n",
    "    distance = np.linalg.norm(R-prevR)\n",
    "    print(\"distance = \",np.linalg.norm(R-prevR))\n",
    "    #print(R)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.25925927],\n",
       "       [0.30864198],\n",
       "       [0.43209878]])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q1: exercise 5.1.3\n",
    "> dead end eixist => compensate the score (Transition Matrx shoule always be stochastic matrix during iteration)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = Symbol('n')\n",
    "#dn = Symbol('1/n')\n",
    "delta = Symbol('\\u03B4') # unicode delta : \\u03B4\n",
    "N = 5\n",
    "M = (1/n)*Matrix([[0,1,1,1, 0], [1,0,1,1, 0], [1,1,0,1,0],[1,1,1,0,0],[1,1,1,0,0]])\n",
    "temp = delta*M - eye(N)\n",
    "\n",
    "S = (1/(n+1))*Matrix([[1, 1, 1,1 , 1/(1-delta)], [1, 1 ,1, 1, 1/(1-delta)], [1, 1 , 1, 1, 1/(1-delta)], [1, 1,1, 1, 1/(1-delta)], [1, 1,1, 1, 1/(1-delta)]])\n",
    "\n",
    "temp = delta*M + (1- delta)*S - eye(N)\n",
    "temp = temp.col_insert(N, zeros(N,1))\n",
    "A = temp.row_insert(N,ones(1,N+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0 & \\frac{1}{n} & \\frac{1}{n} & \\frac{1}{n} & 0\\\\\\frac{1}{n} & 0 & \\frac{1}{n} & \\frac{1}{n} & 0\\\\\\frac{1}{n} & \\frac{1}{n} & 0 & \\frac{1}{n} & 0\\\\\\frac{1}{n} & \\frac{1}{n} & \\frac{1}{n} & 0 & 0\\\\\\frac{1}{n} & \\frac{1}{n} & \\frac{1}{n} & 0 & 0\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡   1  1  1   ⎤\n",
       "⎢0  ─  ─  ─  0⎥\n",
       "⎢   n  n  n   ⎥\n",
       "⎢             ⎥\n",
       "⎢1     1  1   ⎥\n",
       "⎢─  0  ─  ─  0⎥\n",
       "⎢n     n  n   ⎥\n",
       "⎢             ⎥\n",
       "⎢1  1     1   ⎥\n",
       "⎢─  ─  0  ─  0⎥\n",
       "⎢n  n     n   ⎥\n",
       "⎢             ⎥\n",
       "⎢1  1  1      ⎥\n",
       "⎢─  ─  ─  0  0⎥\n",
       "⎢n  n  n      ⎥\n",
       "⎢             ⎥\n",
       "⎢1  1  1      ⎥\n",
       "⎢─  ─  ─  0  0⎥\n",
       "⎣n  n  n      ⎦"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}\\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{\\left(n + 1\\right) \\left(- δ + 1\\right)}\\\\\\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{\\left(n + 1\\right) \\left(- δ + 1\\right)}\\\\\\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{\\left(n + 1\\right) \\left(- δ + 1\\right)}\\\\\\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{\\left(n + 1\\right) \\left(- δ + 1\\right)}\\\\\\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{n + 1} & \\frac{1}{\\left(n + 1\\right) \\left(- δ + 1\\right)}\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡  1      1      1      1           1        ⎤\n",
       "⎢─────  ─────  ─────  ─────  ────────────────⎥\n",
       "⎢n + 1  n + 1  n + 1  n + 1  (n + 1)⋅(-δ + 1)⎥\n",
       "⎢                                            ⎥\n",
       "⎢  1      1      1      1           1        ⎥\n",
       "⎢─────  ─────  ─────  ─────  ────────────────⎥\n",
       "⎢n + 1  n + 1  n + 1  n + 1  (n + 1)⋅(-δ + 1)⎥\n",
       "⎢                                            ⎥\n",
       "⎢  1      1      1      1           1        ⎥\n",
       "⎢─────  ─────  ─────  ─────  ────────────────⎥\n",
       "⎢n + 1  n + 1  n + 1  n + 1  (n + 1)⋅(-δ + 1)⎥\n",
       "⎢                                            ⎥\n",
       "⎢  1      1      1      1           1        ⎥\n",
       "⎢─────  ─────  ─────  ─────  ────────────────⎥\n",
       "⎢n + 1  n + 1  n + 1  n + 1  (n + 1)⋅(-δ + 1)⎥\n",
       "⎢                                            ⎥\n",
       "⎢  1      1      1      1           1        ⎥\n",
       "⎢─────  ─────  ─────  ─────  ────────────────⎥\n",
       "⎣n + 1  n + 1  n + 1  n + 1  (n + 1)⋅(-δ + 1)⎦"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-1 + \\frac{- δ + 1}{n + 1} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{1}{n + 1} & 0\\\\\\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & -1 + \\frac{- δ + 1}{n + 1} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{1}{n + 1} & 0\\\\\\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & -1 + \\frac{- δ + 1}{n + 1} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{1}{n + 1} & 0\\\\\\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & -1 + \\frac{- δ + 1}{n + 1} & \\frac{1}{n + 1} & 0\\\\\\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} & -1 + \\frac{1}{n + 1} & 0\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡     -δ + 1  -δ + 1   δ   -δ + 1   δ   -δ + 1   δ       1        ⎤\n",
       "⎢-1 + ──────  ────── + ─   ────── + ─   ────── + ─     ─────     0⎥\n",
       "⎢     n + 1   n + 1    n   n + 1    n   n + 1    n     n + 1      ⎥\n",
       "⎢                                                                 ⎥\n",
       "⎢-δ + 1   δ        -δ + 1  -δ + 1   δ   -δ + 1   δ       1        ⎥\n",
       "⎢────── + ─   -1 + ──────  ────── + ─   ────── + ─     ─────     0⎥\n",
       "⎢n + 1    n        n + 1   n + 1    n   n + 1    n     n + 1      ⎥\n",
       "⎢                                                                 ⎥\n",
       "⎢-δ + 1   δ   -δ + 1   δ        -δ + 1  -δ + 1   δ       1        ⎥\n",
       "⎢────── + ─   ────── + ─   -1 + ──────  ────── + ─     ─────     0⎥\n",
       "⎢n + 1    n   n + 1    n        n + 1   n + 1    n     n + 1      ⎥\n",
       "⎢                                                                 ⎥\n",
       "⎢-δ + 1   δ   -δ + 1   δ   -δ + 1   δ        -δ + 1      1        ⎥\n",
       "⎢────── + ─   ────── + ─   ────── + ─   -1 + ──────    ─────     0⎥\n",
       "⎢n + 1    n   n + 1    n   n + 1    n        n + 1     n + 1      ⎥\n",
       "⎢                                                                 ⎥\n",
       "⎢-δ + 1   δ   -δ + 1   δ   -δ + 1   δ     -δ + 1            1     ⎥\n",
       "⎢────── + ─   ────── + ─   ────── + ─     ──────     -1 + ─────  0⎥\n",
       "⎣n + 1    n   n + 1    n   n + 1    n     n + 1           n + 1   ⎦"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-1 + \\frac{- δ + 1}{n + 1} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{1}{n + 1} & 0\\\\\\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & -1 + \\frac{- δ + 1}{n + 1} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{1}{n + 1} & 0\\\\\\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & -1 + \\frac{- δ + 1}{n + 1} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{1}{n + 1} & 0\\\\\\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & -1 + \\frac{- δ + 1}{n + 1} & \\frac{1}{n + 1} & 0\\\\\\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} + \\frac{δ}{n} & \\frac{- δ + 1}{n + 1} & -1 + \\frac{1}{n + 1} & 0\\\\1 & 1 & 1 & 1 & 1 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡     -δ + 1  -δ + 1   δ   -δ + 1   δ   -δ + 1   δ       1        ⎤\n",
       "⎢-1 + ──────  ────── + ─   ────── + ─   ────── + ─     ─────     0⎥\n",
       "⎢     n + 1   n + 1    n   n + 1    n   n + 1    n     n + 1      ⎥\n",
       "⎢                                                                 ⎥\n",
       "⎢-δ + 1   δ        -δ + 1  -δ + 1   δ   -δ + 1   δ       1        ⎥\n",
       "⎢────── + ─   -1 + ──────  ────── + ─   ────── + ─     ─────     0⎥\n",
       "⎢n + 1    n        n + 1   n + 1    n   n + 1    n     n + 1      ⎥\n",
       "⎢                                                                 ⎥\n",
       "⎢-δ + 1   δ   -δ + 1   δ        -δ + 1  -δ + 1   δ       1        ⎥\n",
       "⎢────── + ─   ────── + ─   -1 + ──────  ────── + ─     ─────     0⎥\n",
       "⎢n + 1    n   n + 1    n        n + 1   n + 1    n     n + 1      ⎥\n",
       "⎢                                                                 ⎥\n",
       "⎢-δ + 1   δ   -δ + 1   δ   -δ + 1   δ        -δ + 1      1        ⎥\n",
       "⎢────── + ─   ────── + ─   ────── + ─   -1 + ──────    ─────     0⎥\n",
       "⎢n + 1    n   n + 1    n   n + 1    n        n + 1     n + 1      ⎥\n",
       "⎢                                                                 ⎥\n",
       "⎢-δ + 1   δ   -δ + 1   δ   -δ + 1   δ     -δ + 1            1     ⎥\n",
       "⎢────── + ─   ────── + ─   ────── + ─     ──────     -1 + ─────  0⎥\n",
       "⎢n + 1    n   n + 1    n   n + 1    n     n + 1           n + 1   ⎥\n",
       "⎢                                                                 ⎥\n",
       "⎣     1            1            1            1           1       1⎦"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left ( \\left[\\begin{matrix}1 & 0 & 0 & 0 & 0 & 0\\\\0 & 1 & 0 & 0 & 0 & 0\\\\0 & 0 & 1 & 0 & 0 & 0\\\\0 & 0 & 0 & 1 & 0 & 0\\\\0 & 0 & 0 & 0 & 1 & 0\\end{matrix}\\right], \\quad \\left ( 0, \\quad 1, \\quad 2, \\quad 3, \\quad 4\\right )\\right )$$"
      ],
      "text/plain": [
       "⎛⎡1  0  0  0  0  0⎤                 ⎞\n",
       "⎜⎢                ⎥                 ⎟\n",
       "⎜⎢0  1  0  0  0  0⎥                 ⎟\n",
       "⎜⎢                ⎥                 ⎟\n",
       "⎜⎢0  0  1  0  0  0⎥, (0, 1, 2, 3, 4)⎟\n",
       "⎜⎢                ⎥                 ⎟\n",
       "⎜⎢0  0  0  1  0  0⎥                 ⎟\n",
       "⎜⎢                ⎥                 ⎟\n",
       "⎝⎣0  0  0  0  1  0⎦                 ⎠"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "temp.rref()\n",
    "# temp.eigenvects()\n",
    "# temp.nullspace()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left ( \\left[\\begin{matrix}1 & 0 & 0 & 0 & 0 & 0\\\\0 & 1 & 0 & 0 & 0 & 0\\\\0 & 0 & 1 & 0 & 0 & 0\\\\0 & 0 & 0 & 1 & 0 & 0\\\\0 & 0 & 0 & 0 & 1 & 0\\\\0 & 0 & 0 & 0 & 0 & 1\\end{matrix}\\right], \\quad \\left ( 0, \\quad 1, \\quad 2, \\quad 3, \\quad 4, \\quad 5\\right )\\right )$$"
      ],
      "text/plain": [
       "⎛⎡1  0  0  0  0  0⎤                    ⎞\n",
       "⎜⎢                ⎥                    ⎟\n",
       "⎜⎢0  1  0  0  0  0⎥                    ⎟\n",
       "⎜⎢                ⎥                    ⎟\n",
       "⎜⎢0  0  1  0  0  0⎥                    ⎟\n",
       "⎜⎢                ⎥, (0, 1, 2, 3, 4, 5)⎟\n",
       "⎜⎢0  0  0  1  0  0⎥                    ⎟\n",
       "⎜⎢                ⎥                    ⎟\n",
       "⎜⎢0  0  0  0  1  0⎥                    ⎟\n",
       "⎜⎢                ⎥                    ⎟\n",
       "⎝⎣0  0  0  0  0  1⎦                    ⎠"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.rref()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## I don't know why this formula cannot find solution!!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-1 & \\frac{δ}{n} & \\frac{δ}{n} & 0 & \\frac{δ - 1}{n + 1}\\\\\\frac{δ}{n} & -1 & \\frac{δ}{n} & 0 & \\frac{δ - 1}{n + 1}\\\\\\frac{δ}{n} & \\frac{δ}{n} & -1 & 0 & \\frac{δ - 1}{n + 1}\\\\\\frac{δ}{n} & \\frac{δ}{n} & \\frac{δ}{n} & -1 & \\frac{δ - 1}{\\left(n + 1\\right) \\left(- δ + 1\\right)}\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡    δ   δ            δ - 1      ⎤\n",
       "⎢-1  ─   ─   0        ─────      ⎥\n",
       "⎢    n   n            n + 1      ⎥\n",
       "⎢                                ⎥\n",
       "⎢δ       δ            δ - 1      ⎥\n",
       "⎢─   -1  ─   0        ─────      ⎥\n",
       "⎢n       n            n + 1      ⎥\n",
       "⎢                                ⎥\n",
       "⎢δ   δ                δ - 1      ⎥\n",
       "⎢─   ─   -1  0        ─────      ⎥\n",
       "⎢n   n                n + 1      ⎥\n",
       "⎢                                ⎥\n",
       "⎢δ   δ   δ            δ - 1      ⎥\n",
       "⎢─   ─   ─   -1  ────────────────⎥\n",
       "⎣n   n   n       (n + 1)⋅(-δ + 1)⎦"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = Symbol('n')\n",
    "#dn = Symbol('1/n')\n",
    "delta = Symbol('\\u03B4') # unicode delta : \\u03B4\n",
    "N = 4\n",
    "M = (1/n)*Matrix([[0,1,1, 0], [1,0,1,0], [1,1,0,0],[1,1,1,0]])\n",
    "temp = delta*M - eye(N)\n",
    "\n",
    "# S = (1/(n+1))*Matrix([[1, 1, 1, 1/(1-delta)], [1, 1, 1, 1/(1-delta)], [1, 1, 1, 1/(1-delta)], [1, 1, 1, 1]])\n",
    "Svector =  -(1- delta)*(1/(n+1))*Matrix([1,1,1,1/(1-delta)])\n",
    "# temp = temp.col_insert(N, Svector)\n",
    "# A = temp.row_insert(N,Matrix([[1,1,1,1]]))\n",
    "temp = temp.col_insert(N, Svector)\n",
    "temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}\\frac{- \\left(\\left(1 - \\frac{δ^{2}}{n^{2}}\\right) \\left(- \\frac{δ - 1}{n + 1} - \\frac{δ \\left(δ - 1\\right)}{n \\left(n + 1\\right)}\\right) - \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right) \\left(- \\frac{δ - 1}{n + 1} - \\frac{δ \\left(δ - 1\\right)}{n \\left(n + 1\\right)}\\right)\\right) \\left(\\frac{δ \\left(1 - \\frac{δ^{2}}{n^{2}}\\right)}{n} - \\frac{δ \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right)}{n}\\right) + \\left(\\frac{\\left(1 - \\frac{δ^{2}}{n^{2}}\\right) \\left(δ - 1\\right)}{n + 1} - \\frac{δ \\left(- \\frac{δ - 1}{n + 1} - \\frac{δ \\left(δ - 1\\right)}{n \\left(n + 1\\right)}\\right)}{n}\\right) \\left(\\left(1 - \\frac{δ^{2}}{n^{2}}\\right)^{2} - \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right)^{2}\\right)}{\\left(-1 + \\frac{δ^{2}}{n^{2}}\\right) \\left(\\left(1 - \\frac{δ^{2}}{n^{2}}\\right)^{2} - \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right)^{2}\\right)}\\\\\\frac{- \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right) \\left(\\left(1 - \\frac{δ^{2}}{n^{2}}\\right) \\left(- \\frac{δ - 1}{n + 1} - \\frac{δ \\left(δ - 1\\right)}{n \\left(n + 1\\right)}\\right) - \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right) \\left(- \\frac{δ - 1}{n + 1} - \\frac{δ \\left(δ - 1\\right)}{n \\left(n + 1\\right)}\\right)\\right) + \\left(- \\frac{δ - 1}{n + 1} - \\frac{δ \\left(δ - 1\\right)}{n \\left(n + 1\\right)}\\right) \\left(\\left(1 - \\frac{δ^{2}}{n^{2}}\\right)^{2} - \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right)^{2}\\right)}{\\left(1 - \\frac{δ^{2}}{n^{2}}\\right) \\left(\\left(1 - \\frac{δ^{2}}{n^{2}}\\right)^{2} - \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right)^{2}\\right)}\\\\\\frac{\\left(1 - \\frac{δ^{2}}{n^{2}}\\right) \\left(- \\frac{δ - 1}{n + 1} - \\frac{δ \\left(δ - 1\\right)}{n \\left(n + 1\\right)}\\right) - \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right) \\left(- \\frac{δ - 1}{n + 1} - \\frac{δ \\left(δ - 1\\right)}{n \\left(n + 1\\right)}\\right)}{\\left(1 - \\frac{δ^{2}}{n^{2}}\\right)^{2} - \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right)^{2}}\\\\\\frac{- \\left(\\left(1 - \\frac{δ^{2}}{n^{2}}\\right) \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right) - \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right)^{2}\\right) \\left(\\left(1 - \\frac{δ^{2}}{n^{2}}\\right) \\left(- \\frac{δ - 1}{n + 1} - \\frac{δ \\left(δ - 1\\right)}{n \\left(n + 1\\right)}\\right) - \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right) \\left(- \\frac{δ - 1}{n + 1} - \\frac{δ \\left(δ - 1\\right)}{n \\left(n + 1\\right)}\\right)\\right) + \\left(\\left(1 - \\frac{δ^{2}}{n^{2}}\\right) \\left(- \\frac{δ - 1}{\\left(n + 1\\right) \\left(- δ + 1\\right)} - \\frac{δ \\left(δ - 1\\right)}{n \\left(n + 1\\right)}\\right) - \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right) \\left(- \\frac{δ - 1}{n + 1} - \\frac{δ \\left(δ - 1\\right)}{n \\left(n + 1\\right)}\\right)\\right) \\left(\\left(1 - \\frac{δ^{2}}{n^{2}}\\right)^{2} - \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right)^{2}\\right)}{\\left(1 - \\frac{δ^{2}}{n^{2}}\\right) \\left(\\left(1 - \\frac{δ^{2}}{n^{2}}\\right)^{2} - \\left(- \\frac{δ}{n} - \\frac{δ^{2}}{n^{2}}\\right)^{2}\\right)}\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                       ⎛⎛     2⎞                         ⎛       2⎞          \n",
       "⎢                       ⎜⎜    δ ⎟ ⎛  δ - 1   δ⋅(δ - 1)⎞   ⎜  δ   δ ⎟ ⎛  δ - 1 \n",
       "⎢                     - ⎜⎜1 - ──⎟⋅⎜- ───── - ─────────⎟ - ⎜- ─ - ──⎟⋅⎜- ───── \n",
       "⎢                       ⎜⎜     2⎟ ⎝  n + 1   n⋅(n + 1)⎠   ⎜  n    2⎟ ⎝  n + 1 \n",
       "⎢                       ⎝⎝    n ⎠                         ⎝      n ⎠          \n",
       "⎢                     ────────────────────────────────────────────────────────\n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                           ⎛       2⎞ ⎛⎛     2⎞              \n",
       "⎢                                           ⎜  δ   δ ⎟ ⎜⎜    δ ⎟ ⎛  δ - 1   δ⋅\n",
       "⎢                                         - ⎜- ─ - ──⎟⋅⎜⎜1 - ──⎟⋅⎜- ───── - ──\n",
       "⎢                                           ⎜  n    2⎟ ⎜⎜     2⎟ ⎝  n + 1   n⋅\n",
       "⎢                                           ⎝      n ⎠ ⎝⎝    n ⎠              \n",
       "⎢                                         ────────────────────────────────────\n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                         ⎛   \n",
       "⎢                                                                         ⎜   \n",
       "⎢                                                                         ⎜1 -\n",
       "⎢                                                                         ⎜   \n",
       "⎢                                                                         ⎝   \n",
       "⎢                                                                         ────\n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢  ⎛                                2⎞                                        \n",
       "⎢  ⎜⎛     2⎞ ⎛       2⎞   ⎛       2⎞ ⎟ ⎛⎛     2⎞                         ⎛    \n",
       "⎢  ⎜⎜    δ ⎟ ⎜  δ   δ ⎟   ⎜  δ   δ ⎟ ⎟ ⎜⎜    δ ⎟ ⎛  δ - 1   δ⋅(δ - 1)⎞   ⎜  δ \n",
       "⎢- ⎜⎜1 - ──⎟⋅⎜- ─ - ──⎟ - ⎜- ─ - ──⎟ ⎟⋅⎜⎜1 - ──⎟⋅⎜- ───── - ─────────⎟ - ⎜- ─ \n",
       "⎢  ⎜⎜     2⎟ ⎜  n    2⎟   ⎜  n    2⎟ ⎟ ⎜⎜     2⎟ ⎝  n + 1   n⋅(n + 1)⎠   ⎜  n \n",
       "⎢  ⎝⎝    n ⎠ ⎝      n ⎠   ⎝      n ⎠ ⎠ ⎝⎝    n ⎠                         ⎝    \n",
       "⎢─────────────────────────────────────────────────────────────────────────────\n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎢                                                                             \n",
       "⎣                                                                             \n",
       "\n",
       "              ⎛  ⎛     2⎞     ⎛       2⎞⎞   ⎛⎛     2⎞                         \n",
       "              ⎜  ⎜    δ ⎟     ⎜  δ   δ ⎟⎟   ⎜⎜    δ ⎟                         \n",
       "              ⎜δ⋅⎜1 - ──⎟   δ⋅⎜- ─ - ──⎟⎟   ⎜⎜1 - ──⎟⋅(δ - 1)     ⎛  δ - 1   δ\n",
       "            ⎞ ⎜  ⎜     2⎟     ⎜  n    2⎟⎟   ⎜⎜     2⎟           δ⋅⎜- ───── - ─\n",
       "  δ⋅(δ - 1)⎞⎟ ⎜  ⎝    n ⎠     ⎝      n ⎠⎟   ⎜⎝    n ⎠             ⎝  n + 1   n\n",
       "- ─────────⎟⎟⋅⎜────────── - ────────────⎟ + ⎜──────────────── - ──────────────\n",
       "  n⋅(n + 1)⎠⎟ ⎝    n             n      ⎠   ⎝     n + 1                    n  \n",
       "            ⎠                                                                 \n",
       "──────────────────────────────────────────────────────────────────────────────\n",
       "                     ⎛        2             2⎞                                \n",
       "           ⎛      2⎞ ⎜⎛     2⎞    ⎛       2⎞ ⎟                                \n",
       "           ⎜     δ ⎟ ⎜⎜    δ ⎟    ⎜  δ   δ ⎟ ⎟                                \n",
       "           ⎜-1 + ──⎟⋅⎜⎜1 - ──⎟  - ⎜- ─ - ──⎟ ⎟                                \n",
       "           ⎜      2⎟ ⎜⎜     2⎟    ⎜  n    2⎟ ⎟                                \n",
       "           ⎝     n ⎠ ⎝⎝    n ⎠    ⎝      n ⎠ ⎠                                \n",
       "                                                                              \n",
       "                                                                     ⎛        \n",
       "           ⎛       2⎞                      ⎞                         ⎜⎛     2⎞\n",
       "(δ - 1)⎞   ⎜  δ   δ ⎟ ⎛  δ - 1   δ⋅(δ - 1)⎞⎟   ⎛  δ - 1   δ⋅(δ - 1)⎞ ⎜⎜    δ ⎟\n",
       "───────⎟ - ⎜- ─ - ──⎟⋅⎜- ───── - ─────────⎟⎟ + ⎜- ───── - ─────────⎟⋅⎜⎜1 - ──⎟\n",
       "(n + 1)⎠   ⎜  n    2⎟ ⎝  n + 1   n⋅(n + 1)⎠⎟   ⎝  n + 1   n⋅(n + 1)⎠ ⎜⎜     2⎟\n",
       "           ⎝      n ⎠                      ⎠                         ⎝⎝    n ⎠\n",
       "──────────────────────────────────────────────────────────────────────────────\n",
       "                     ⎛        2             2⎞                                \n",
       "            ⎛     2⎞ ⎜⎛     2⎞    ⎛       2⎞ ⎟                                \n",
       "            ⎜    δ ⎟ ⎜⎜    δ ⎟    ⎜  δ   δ ⎟ ⎟                                \n",
       "            ⎜1 - ──⎟⋅⎜⎜1 - ──⎟  - ⎜- ─ - ──⎟ ⎟                                \n",
       "            ⎜     2⎟ ⎜⎜     2⎟    ⎜  n    2⎟ ⎟                                \n",
       "            ⎝    n ⎠ ⎝⎝    n ⎠    ⎝      n ⎠ ⎠                                \n",
       "                                                                              \n",
       "  2⎞                         ⎛       2⎞                                       \n",
       " δ ⎟ ⎛  δ - 1   δ⋅(δ - 1)⎞   ⎜  δ   δ ⎟ ⎛  δ - 1   δ⋅(δ - 1)⎞                 \n",
       " ──⎟⋅⎜- ───── - ─────────⎟ - ⎜- ─ - ──⎟⋅⎜- ───── - ─────────⎟                 \n",
       "  2⎟ ⎝  n + 1   n⋅(n + 1)⎠   ⎜  n    2⎟ ⎝  n + 1   n⋅(n + 1)⎠                 \n",
       " n ⎠                         ⎝      n ⎠                                       \n",
       "─────────────────────────────────────────────────────────────                 \n",
       "                         2             2                                      \n",
       "                 ⎛     2⎞    ⎛       2⎞                                       \n",
       "                 ⎜    δ ⎟    ⎜  δ   δ ⎟                                       \n",
       "                 ⎜1 - ──⎟  - ⎜- ─ - ──⎟                                       \n",
       "                 ⎜     2⎟    ⎜  n    2⎟                                       \n",
       "                 ⎝    n ⎠    ⎝      n ⎠                                       \n",
       "                                                                              \n",
       "                                                                              \n",
       "   2⎞                      ⎞   ⎛⎛     2⎞                                    ⎛ \n",
       "  δ ⎟ ⎛  δ - 1   δ⋅(δ - 1)⎞⎟   ⎜⎜    δ ⎟ ⎛       δ - 1         δ⋅(δ - 1)⎞   ⎜ \n",
       "- ──⎟⋅⎜- ───── - ─────────⎟⎟ + ⎜⎜1 - ──⎟⋅⎜- ──────────────── - ─────────⎟ - ⎜-\n",
       "   2⎟ ⎝  n + 1   n⋅(n + 1)⎠⎟   ⎜⎜     2⎟ ⎝  (n + 1)⋅(-δ + 1)   n⋅(n + 1)⎠   ⎜ \n",
       "  n ⎠                      ⎠   ⎝⎝    n ⎠                                    ⎝ \n",
       "──────────────────────────────────────────────────────────────────────────────\n",
       "                     ⎛        2             2⎞                                \n",
       "            ⎛     2⎞ ⎜⎛     2⎞    ⎛       2⎞ ⎟                                \n",
       "            ⎜    δ ⎟ ⎜⎜    δ ⎟    ⎜  δ   δ ⎟ ⎟                                \n",
       "            ⎜1 - ──⎟⋅⎜⎜1 - ──⎟  - ⎜- ─ - ──⎟ ⎟                                \n",
       "            ⎜     2⎟ ⎜⎜     2⎟    ⎜  n    2⎟ ⎟                                \n",
       "            ⎝    n ⎠ ⎝⎝    n ⎠    ⎝      n ⎠ ⎠                                \n",
       "\n",
       "         ⎞                                               ⎤\n",
       "         ⎟                                               ⎥\n",
       "⋅(δ - 1)⎞⎟ ⎛        2             2⎞                     ⎥\n",
       "────────⎟⎟ ⎜⎛     2⎞    ⎛       2⎞ ⎟                     ⎥\n",
       "⋅(n + 1)⎠⎟ ⎜⎜    δ ⎟    ⎜  δ   δ ⎟ ⎟                     ⎥\n",
       "─────────⎟⋅⎜⎜1 - ──⎟  - ⎜- ─ - ──⎟ ⎟                     ⎥\n",
       "         ⎠ ⎜⎜     2⎟    ⎜  n    2⎟ ⎟                     ⎥\n",
       "           ⎝⎝    n ⎠    ⎝      n ⎠ ⎠                     ⎥\n",
       "────────────────────────────────────                     ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "2             2⎞                                         ⎥\n",
       "    ⎛       2⎞ ⎟                                         ⎥\n",
       "    ⎜  δ   δ ⎟ ⎟                                         ⎥\n",
       "  - ⎜- ─ - ──⎟ ⎟                                         ⎥\n",
       "    ⎜  n    2⎟ ⎟                                         ⎥\n",
       "    ⎝      n ⎠ ⎠                                         ⎥\n",
       "────────────────                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                ⎛        2             2⎞⎥\n",
       "      2⎞                      ⎞ ⎜⎛     2⎞    ⎛       2⎞ ⎟⎥\n",
       " δ   δ ⎟ ⎛  δ - 1   δ⋅(δ - 1)⎞⎟ ⎜⎜    δ ⎟    ⎜  δ   δ ⎟ ⎟⎥\n",
       " ─ - ──⎟⋅⎜- ───── - ─────────⎟⎟⋅⎜⎜1 - ──⎟  - ⎜- ─ - ──⎟ ⎟⎥\n",
       " n    2⎟ ⎝  n + 1   n⋅(n + 1)⎠⎟ ⎜⎜     2⎟    ⎜  n    2⎟ ⎟⎥\n",
       "     n ⎠                      ⎠ ⎝⎝    n ⎠    ⎝      n ⎠ ⎠⎥\n",
       "─────────────────────────────────────────────────────────⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎥\n",
       "                                                         ⎦"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# temp.rref()\n",
    "result = temp.rref()\n",
    "result[0].col(-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2: Random Walk with Restart"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> (a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0 & 0 & 0 & 0.5 & 0\\\\0 & 0 & 0 & 0 & 1\\\\0.333333333333333 & 1 & 0 & 0.5 & 0\\\\0.333333333333333 & 0 & 0 & 0 & 0\\\\0.333333333333333 & 0 & 1 & 0 & 0\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡        0          0  0  0.5  0⎤\n",
       "⎢                               ⎥\n",
       "⎢        0          0  0   0   1⎥\n",
       "⎢                               ⎥\n",
       "⎢0.333333333333333  1  0  0.5  0⎥\n",
       "⎢                               ⎥\n",
       "⎢0.333333333333333  0  0   0   0⎥\n",
       "⎢                               ⎥\n",
       "⎣0.333333333333333  0  1   0   0⎦"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "delta = 0.8\n",
    "N = 5\n",
    "M = Matrix([[0,0,0,1/2,0], [0,0,0,0,1], [1/3,1,0,1/2,0], [1/3,0,0,0,0], [1/3,0,1,0,0]])\n",
    "# S = Matrix([[1/N, 1/N, 1/N], [0, 0, 0], [0, 0, 0]])\n",
    "# temp = delta*M + (1- delta)*S - eye(3)\n",
    "M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-1 & 0 & 0 & 0.4 & 0 & -0.2\\\\0 & -1 & 0 & 0 & 0.8 & 0\\\\0.266666666666667 & 0.8 & -1 & 0.4 & 0 & 0\\\\0.266666666666667 & 0 & 0 & -1 & 0 & 0\\\\0.266666666666667 & 0 & 0.8 & 0 & -1 & 0\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡       -1           0    0   0.4   0   -0.2⎤\n",
       "⎢                                           ⎥\n",
       "⎢        0          -1    0    0   0.8   0  ⎥\n",
       "⎢                                           ⎥\n",
       "⎢0.266666666666667  0.8  -1   0.4   0    0  ⎥\n",
       "⎢                                           ⎥\n",
       "⎢0.266666666666667   0    0   -1    0    0  ⎥\n",
       "⎢                                           ⎥\n",
       "⎣0.266666666666667   0   0.8   0   -1    0  ⎦"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "temp = delta*M - eye(N)\n",
    "Svector =  -(1- delta)*Matrix([1,0,0,0,0])\n",
    "A = temp.col_insert(N, Svector)\n",
    "# A = A.row_insert(N,Matrix([[1,1,1,1,1,1]]))\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left ( \\left[\\begin{matrix}1 & 0 & 0 & 0 & 0 & 0.223880597014925\\\\0 & 1 & 0 & 0 & 0 & 0.207487154391975\\\\0 & 0 & 1 & 0 & 0 & 0.249571813065818\\\\0 & 0 & 0 & 1 & 0 & 0.0597014925373134\\\\0 & 0 & 0 & 0 & 1 & 0.259358942989968\\end{matrix}\\right], \\quad \\left ( 0, \\quad 1, \\quad 2, \\quad 3, \\quad 4\\right )\\right )$$"
      ],
      "text/plain": [
       "⎛⎡1  0  0  0  0  0.223880597014925 ⎤                 ⎞\n",
       "⎜⎢                                 ⎥                 ⎟\n",
       "⎜⎢0  1  0  0  0  0.207487154391975 ⎥                 ⎟\n",
       "⎜⎢                                 ⎥                 ⎟\n",
       "⎜⎢0  0  1  0  0  0.249571813065818 ⎥, (0, 1, 2, 3, 4)⎟\n",
       "⎜⎢                                 ⎥                 ⎟\n",
       "⎜⎢0  0  0  1  0  0.0597014925373134⎥                 ⎟\n",
       "⎜⎢                                 ⎥                 ⎟\n",
       "⎝⎣0  0  0  0  1  0.259358942989968 ⎦                 ⎠"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.rref()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0.223880597014925\\\\0.207487154391975\\\\0.249571813065818\\\\0.0597014925373134\\\\0.259358942989968\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡0.223880597014925 ⎤\n",
       "⎢                  ⎥\n",
       "⎢0.207487154391975 ⎥\n",
       "⎢                  ⎥\n",
       "⎢0.249571813065818 ⎥\n",
       "⎢                  ⎥\n",
       "⎢0.0597014925373134⎥\n",
       "⎢                  ⎥\n",
       "⎣0.259358942989968 ⎦"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result = A.rref()\n",
    "result[0].col(-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration 0 ...\n",
      "distance =  0.1959591790982077\n",
      "[[0.28      ]\n",
      " [0.16      ]\n",
      " [0.29333333]\n",
      " [0.05333333]\n",
      " [0.21333333]]\n",
      "iteration 1 ...\n",
      "distance =  0.13428990262607193\n",
      "[[0.22133333]\n",
      " [0.17066667]\n",
      " [0.224     ]\n",
      " [0.07466667]\n",
      " [0.30933334]]\n",
      "iteration 2 ...\n",
      "distance =  0.1061820107530088\n",
      "[[0.22986667]\n",
      " [0.24746667]\n",
      " [0.22542223]\n",
      " [0.05902222]\n",
      " [0.23822223]]\n",
      "iteration 3 ...\n",
      "distance =  0.08120179044462032\n",
      "[[0.22360889]\n",
      " [0.19057778]\n",
      " [0.28288001]\n",
      " [0.06129778]\n",
      " [0.24163556]]\n",
      "iteration 4 ...\n",
      "distance =  0.06414214898940802\n",
      "[[0.22451911]\n",
      " [0.19330845]\n",
      " [0.23661038]\n",
      " [0.05962904]\n",
      " [0.28593304]]\n",
      "iteration 5 ...\n",
      "distance =  0.05110483292183438\n",
      "[[0.22385162]\n",
      " [0.22874643]\n",
      " [0.23837014]\n",
      " [0.05987176]\n",
      " [0.24916007]]\n",
      "iteration 6 ...\n",
      "distance =  0.040818601722857284\n",
      "[[0.22394871]\n",
      " [0.19932805]\n",
      " [0.26663962]\n",
      " [0.05969377]\n",
      " [0.25038988]]\n",
      "iteration 7 ...\n",
      "distance =  0.03270515495237641\n",
      "[[0.22387751]\n",
      " [0.2003119 ]\n",
      " [0.24305961]\n",
      " [0.05971966]\n",
      " [0.27303135]]\n",
      "iteration 8 ...\n",
      "distance =  0.02617749705553816\n",
      "[[0.22388786]\n",
      " [0.21842508]\n",
      " [0.24383805]\n",
      " [0.05970067]\n",
      " [0.25414835]]\n",
      "iteration 9 ...\n",
      "distance =  0.020938730573909485\n",
      "[[0.22388027]\n",
      " [0.20331868]\n",
      " [0.25832377]\n",
      " [0.05970343]\n",
      " [0.25477388]]\n",
      "iteration 10 ...\n",
      "distance =  0.016750246561777392\n",
      "[[0.22388137]\n",
      " [0.2038191 ]\n",
      " [0.24623773]\n",
      " [0.05970141]\n",
      " [0.26636042]]\n",
      "iteration 11 ...\n",
      "distance =  0.013399969208182917\n",
      "[[0.22388056]\n",
      " [0.21308834]\n",
      " [0.24663754]\n",
      " [0.0597017 ]\n",
      " [0.25669188]]\n",
      "iteration 12 ...\n",
      "distance =  0.01071990098028898\n",
      "[[0.22388068]\n",
      " [0.20535351]\n",
      " [0.25405283]\n",
      " [0.05970149]\n",
      " [0.25701152]]\n",
      "iteration 13 ...\n",
      "distance =  0.008575982194037114\n",
      "[[0.22388059]\n",
      " [0.20560922]\n",
      " [0.24786492]\n",
      " [0.05970152]\n",
      " [0.26294378]]\n",
      "iteration 14 ...\n",
      "distance =  0.006860802068822044\n",
      "[[0.22388061]\n",
      " [0.21035503]\n",
      " [0.24806947]\n",
      " [0.05970149]\n",
      " [0.25799343]]\n",
      "iteration 15 ...\n",
      "distance =  0.005488637697694913\n",
      "[[0.2238806 ]\n",
      " [0.20639474]\n",
      " [0.25186612]\n",
      " [0.0597015 ]\n",
      " [0.25815708]]\n",
      "iteration 16 ...\n",
      "distance =  0.004390909264086185\n",
      "[[0.2238806 ]\n",
      " [0.20652566]\n",
      " [0.24869789]\n",
      " [0.05970149]\n",
      " [0.26119439]]\n",
      "iteration 17 ...\n",
      "distance =  0.0035127271346550456\n",
      "[[0.2238806 ]\n",
      " [0.20895551]\n",
      " [0.24880262]\n",
      " [0.05970149]\n",
      " [0.2586598 ]]\n",
      "iteration 18 ...\n",
      "distance =  0.00281018161747374\n",
      "[[0.2238806 ]\n",
      " [0.20692784]\n",
      " [0.2507465 ]\n",
      " [0.05970149]\n",
      " [0.25874359]]\n",
      "iteration 19 ...\n",
      "distance =  0.0022481453685100094\n",
      "[[0.2238806 ]\n",
      " [0.20699487]\n",
      " [0.24912437]\n",
      " [0.05970149]\n",
      " [0.26029869]]\n",
      "iteration 20 ...\n",
      "distance =  0.0017985163146071528\n",
      "[[0.2238806 ]\n",
      " [0.20823896]\n",
      " [0.24917799]\n",
      " [0.05970149]\n",
      " [0.25900099]]\n",
      "iteration 21 ...\n",
      "distance =  0.0014388130468829686\n",
      "[[0.2238806 ]\n",
      " [0.20720079]\n",
      " [0.25017326]\n",
      " [0.05970149]\n",
      " [0.25904389]]\n",
      "iteration 22 ...\n",
      "distance =  0.0011510504364213873\n",
      "[[0.2238806 ]\n",
      " [0.20723511]\n",
      " [0.24934272]\n",
      " [0.05970149]\n",
      " [0.2598401 ]]\n",
      "iteration 23 ...\n",
      "distance =  0.0009208403488014078\n",
      "[[0.2238806 ]\n",
      " [0.20787208]\n",
      " [0.24937018]\n",
      " [0.05970149]\n",
      " [0.25917567]]\n",
      "iteration 24 ...\n",
      "distance =  0.0007366722789315902\n",
      "[[0.2238806 ]\n",
      " [0.20734054]\n",
      " [0.24987976]\n",
      " [0.05970149]\n",
      " [0.25919764]]\n",
      "iteration 25 ...\n",
      "distance =  0.0005893378232357625\n",
      "[[0.2238806 ]\n",
      " [0.20735811]\n",
      " [0.24945452]\n",
      " [0.05970149]\n",
      " [0.2596053 ]]\n",
      "iteration 26 ...\n",
      "distance =  0.0004714702586126442\n",
      "[[0.2238806 ]\n",
      " [0.20768424]\n",
      " [0.24946858]\n",
      " [0.05970149]\n",
      " [0.25926511]]\n",
      "iteration 27 ...\n",
      "distance =  0.00037717620688426147\n",
      "[[0.2238806 ]\n",
      " [0.20741209]\n",
      " [0.24972948]\n",
      " [0.05970149]\n",
      " [0.25927636]]\n",
      "iteration 28 ...\n",
      "distance =  0.00030174096550604826\n",
      "[[0.2238806 ]\n",
      " [0.20742109]\n",
      " [0.24951177]\n",
      " [0.05970149]\n",
      " [0.25948508]]\n",
      "iteration 29 ...\n",
      "distance =  0.00024139277240441126\n",
      "[[0.2238806 ]\n",
      " [0.20758807]\n",
      " [0.24951896]\n",
      " [0.05970149]\n",
      " [0.25931091]]\n",
      "iteration 30 ...\n",
      "distance =  0.00019311421792340643\n",
      "[[0.2238806 ]\n",
      " [0.20744873]\n",
      " [0.24965254]\n",
      " [0.05970149]\n",
      " [0.25931666]]\n",
      "iteration 31 ...\n",
      "distance =  0.00015449137433883546\n",
      "[[0.2238806 ]\n",
      " [0.20745333]\n",
      " [0.24954107]\n",
      " [0.05970149]\n",
      " [0.25942353]]\n",
      "iteration 32 ...\n",
      "distance =  0.00012359309947112778\n",
      "[[0.2238806 ]\n",
      " [0.20753882]\n",
      " [0.24954476]\n",
      " [0.05970149]\n",
      " [0.25933435]]\n",
      "iteration 33 ...\n",
      "distance =  9.887447957688835e-05\n",
      "[[0.2238806 ]\n",
      " [0.20746748]\n",
      " [0.24961315]\n",
      " [0.05970149]\n",
      " [0.2593373 ]]\n",
      "iteration 34 ...\n",
      "distance =  7.909958366146411e-05\n",
      "[[0.2238806 ]\n",
      " [0.20746984]\n",
      " [0.24955608]\n",
      " [0.05970149]\n",
      " [0.25939202]]\n",
      "iteration 35 ...\n",
      "distance =  6.327966692913825e-05\n",
      "[[0.2238806 ]\n",
      " [0.20751361]\n",
      " [0.24955796]\n",
      " [0.05970149]\n",
      " [0.25934636]]\n",
      "iteration 36 ...\n",
      "distance =  5.062373354332146e-05\n",
      "[[0.2238806 ]\n",
      " [0.20747709]\n",
      " [0.24959298]\n",
      " [0.05970149]\n",
      " [0.25934787]]\n",
      "iteration 37 ...\n",
      "distance =  4.0498986834669513e-05\n",
      "[[0.2238806 ]\n",
      " [0.20747829]\n",
      " [0.24956376]\n",
      " [0.05970149]\n",
      " [0.25937588]]\n",
      "iteration 38 ...\n",
      "distance =  3.2399189467720084e-05\n",
      "[[0.2238806 ]\n",
      " [0.2075007 ]\n",
      " [0.24956473]\n",
      " [0.05970149]\n",
      " [0.2593525 ]]\n",
      "iteration 39 ...\n",
      "distance =  2.5919351574168223e-05\n",
      "[[0.2238806 ]\n",
      " [0.207482  ]\n",
      " [0.24958266]\n",
      " [0.05970149]\n",
      " [0.25935328]]\n",
      "iteration 40 ...\n",
      "distance =  2.073548125931088e-05\n",
      "[[0.2238806 ]\n",
      " [0.20748262]\n",
      " [0.24956769]\n",
      " [0.05970149]\n",
      " [0.25936762]]\n",
      "iteration 41 ...\n",
      "distance =  1.6588385007449036e-05\n",
      "[[0.2238806 ]\n",
      " [0.2074941 ]\n",
      " [0.24956819]\n",
      " [0.05970149]\n",
      " [0.25935565]]\n",
      "iteration 42 ...\n",
      "distance =  1.3270708005947542e-05\n",
      "[[0.2238806 ]\n",
      " [0.20748452]\n",
      " [0.24957737]\n",
      " [0.05970149]\n",
      " [0.25935605]]\n",
      "iteration 43 ...\n",
      "distance =  1.061656640478574e-05\n",
      "[[0.2238806 ]\n",
      " [0.20748484]\n",
      " [0.24956971]\n",
      " [0.05970149]\n",
      " [0.25936339]]\n",
      "iteration 44 ...\n",
      "distance =  8.493253123808565e-06\n",
      "[[0.2238806 ]\n",
      " [0.20749071]\n",
      " [0.24956996]\n",
      " [0.05970149]\n",
      " [0.25935726]]\n",
      "iteration 45 ...\n",
      "distance =  6.7946024990642305e-06\n",
      "[[0.2238806 ]\n",
      " [0.20748581]\n",
      " [0.24957466]\n",
      " [0.05970149]\n",
      " [0.25935746]]\n",
      "iteration 46 ...\n",
      "distance =  5.435681999263401e-06\n",
      "[[0.2238806 ]\n",
      " [0.20748597]\n",
      " [0.24957074]\n",
      " [0.05970149]\n",
      " [0.25936122]]\n",
      "iteration 47 ...\n",
      "distance =  4.348545599379174e-06\n",
      "[[0.2238806 ]\n",
      " [0.20748898]\n",
      " [0.24957087]\n",
      " [0.05970149]\n",
      " [0.25935809]]\n",
      "iteration 48 ...\n",
      "distance =  3.478836479494501e-06\n",
      "[[0.2238806 ]\n",
      " [0.20748647]\n",
      " [0.24957328]\n",
      " [0.05970149]\n",
      " [0.25935819]]\n",
      "iteration 49 ...\n",
      "distance =  2.783069183606458e-06\n",
      "[[0.2238806 ]\n",
      " [0.20748655]\n",
      " [0.24957127]\n",
      " [0.05970149]\n",
      " [0.25936011]]\n",
      "iteration 50 ...\n",
      "distance =  2.2264553468966862e-06\n",
      "[[0.2238806 ]\n",
      " [0.20748809]\n",
      " [0.24957133]\n",
      " [0.05970149]\n",
      " [0.25935851]]\n",
      "iteration 51 ...\n",
      "distance =  1.781164277533536e-06\n",
      "[[0.2238806 ]\n",
      " [0.20748681]\n",
      " [0.24957257]\n",
      " [0.05970149]\n",
      " [0.25935856]]\n",
      "iteration 52 ...\n",
      "distance =  1.4249314220582098e-06\n",
      "[[0.2238806 ]\n",
      " [0.20748685]\n",
      " [0.24957154]\n",
      " [0.05970149]\n",
      " [0.25935955]]\n",
      "iteration 53 ...\n",
      "distance =  1.139945137666429e-06\n",
      "[[0.2238806 ]\n",
      " [0.20748764]\n",
      " [0.24957157]\n",
      " [0.05970149]\n",
      " [0.25935872]]\n",
      "iteration 54 ...\n",
      "distance =  9.119561101523425e-07\n",
      "[[0.2238806 ]\n",
      " [0.20748698]\n",
      " [0.2495722 ]\n",
      " [0.05970149]\n",
      " [0.25935875]]\n",
      "iteration 55 ...\n",
      "distance =  7.295648881145254e-07\n",
      "[[0.2238806 ]\n",
      " [0.207487  ]\n",
      " [0.24957168]\n",
      " [0.05970149]\n",
      " [0.25935926]]\n",
      "iteration 56 ...\n",
      "distance =  5.836519104876149e-07\n",
      "[[0.2238806 ]\n",
      " [0.20748741]\n",
      " [0.24957169]\n",
      " [0.05970149]\n",
      " [0.25935884]]\n",
      "iteration 57 ...\n",
      "distance =  4.6692152837072714e-07\n",
      "[[0.2238806 ]\n",
      " [0.20748707]\n",
      " [0.24957202]\n",
      " [0.05970149]\n",
      " [0.25935885]]\n",
      "iteration 58 ...\n",
      "distance =  3.735372226847311e-07\n",
      "[[0.2238806 ]\n",
      " [0.20748708]\n",
      " [0.24957175]\n",
      " [0.05970149]\n",
      " [0.25935911]]\n",
      "iteration 59 ...\n",
      "distance =  2.9882977815212127e-07\n",
      "[[0.2238806 ]\n",
      " [0.20748729]\n",
      " [0.24957176]\n",
      " [0.05970149]\n",
      " [0.25935889]]\n",
      "iteration 60 ...\n",
      "distance =  2.390638225230211e-07\n",
      "[[0.2238806 ]\n",
      " [0.20748711]\n",
      " [0.24957192]\n",
      " [0.05970149]\n",
      " [0.2593589 ]]\n",
      "iteration 61 ...\n",
      "distance =  1.9125105799120687e-07\n",
      "[[0.2238806 ]\n",
      " [0.20748712]\n",
      " [0.24957178]\n",
      " [0.05970149]\n",
      " [0.25935903]]\n",
      "iteration 62 ...\n",
      "distance =  1.5300084640014867e-07\n",
      "[[0.2238806 ]\n",
      " [0.20748723]\n",
      " [0.24957179]\n",
      " [0.05970149]\n",
      " [0.25935892]]\n",
      "iteration 63 ...\n",
      "distance =  1.2240067712044994e-07\n",
      "[[0.2238806 ]\n",
      " [0.20748714]\n",
      " [0.24957187]\n",
      " [0.05970149]\n",
      " [0.25935892]]\n",
      "iteration 64 ...\n",
      "distance =  9.792054170721749e-08\n",
      "[[0.2238806 ]\n",
      " [0.20748714]\n",
      " [0.2495718 ]\n",
      " [0.05970149]\n",
      " [0.25935899]]\n",
      "iteration 65 ...\n",
      "distance =  7.833643339798246e-08\n",
      "[[0.2238806 ]\n",
      " [0.20748719]\n",
      " [0.2495718 ]\n",
      " [0.05970149]\n",
      " [0.25935894]]\n",
      "iteration 66 ...\n",
      "distance =  6.266914670752844e-08\n",
      "[[0.2238806 ]\n",
      " [0.20748715]\n",
      " [0.24957185]\n",
      " [0.05970149]\n",
      " [0.25935894]]\n",
      "iteration 67 ...\n",
      "distance =  5.0135317322956766e-08\n",
      "[[0.2238806 ]\n",
      " [0.20748715]\n",
      " [0.24957181]\n",
      " [0.05970149]\n",
      " [0.25935897]]\n",
      "iteration 68 ...\n",
      "distance =  4.010825385018916e-08\n",
      "[[0.2238806 ]\n",
      " [0.20748718]\n",
      " [0.24957181]\n",
      " [0.05970149]\n",
      " [0.25935894]]\n",
      "iteration 69 ...\n",
      "distance =  3.2086603068631755e-08\n",
      "[[0.2238806 ]\n",
      " [0.20748715]\n",
      " [0.24957183]\n",
      " [0.05970149]\n",
      " [0.25935894]]\n",
      "iteration 70 ...\n",
      "distance =  2.566928246241961e-08\n",
      "[[0.2238806 ]\n",
      " [0.20748716]\n",
      " [0.24957182]\n",
      " [0.05970149]\n",
      " [0.25935896]]\n",
      "iteration 71 ...\n",
      "distance =  2.05354259537487e-08\n",
      "[[0.2238806 ]\n",
      " [0.20748717]\n",
      " [0.24957182]\n",
      " [0.05970149]\n",
      " [0.25935895]]\n",
      "iteration 72 ...\n",
      "distance =  1.6428340749824276e-08\n",
      "[[0.2238806 ]\n",
      " [0.20748716]\n",
      " [0.24957183]\n",
      " [0.05970149]\n",
      " [0.25935895]]\n",
      "iteration 73 ...\n",
      "distance =  1.3142672623064079e-08\n",
      "[[0.2238806 ]\n",
      " [0.20748716]\n",
      " [0.24957182]\n",
      " [0.05970149]\n",
      " [0.25935896]]\n",
      "iteration 74 ...\n",
      "distance =  1.0514138091930125e-08\n",
      "[[0.2238806 ]\n",
      " [0.20748717]\n",
      " [0.24957182]\n",
      " [0.05970149]\n",
      " [0.25935895]]\n",
      "iteration 75 ...\n",
      "distance =  8.411310457026091e-09\n",
      "[[0.2238806 ]\n",
      " [0.20748716]\n",
      " [0.24957182]\n",
      " [0.05970149]\n",
      " [0.25935895]]\n"
     ]
    }
   ],
   "source": [
    "# PageRank Algorithm\n",
    "M = np.array(M, dtype='f')\n",
    "N = 5\n",
    "delta = 0.8\n",
    "elipslion = 1e-8\n",
    "R = np.ones((N,1))*(1/N)\n",
    "#R = np.ones((N,1))\n",
    "# K = np.ones((N,1))*((1- delta)/N)\n",
    "K = np.zeros((N,1))\n",
    "K[0] = ((1- delta))\n",
    "# R = delta * np.matmul(M,prevR) + K\n",
    "iteration = 0\n",
    "distance = 100\n",
    "\n",
    "while distance > elipslion:\n",
    "    print(\"iteration\", iteration, \"...\")\n",
    "    prevR = R\n",
    "    R = delta * np.matmul(M,R) + K\n",
    "    iteration = iteration + 1\n",
    "    distance = np.linalg.norm(R-prevR)\n",
    "    print(\"distance = \",np.linalg.norm(R-prevR))\n",
    "    print(R)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.2238806 ],\n",
       "       [0.20748716],\n",
       "       [0.24957182],\n",
       "       [0.05970149],\n",
       "       [0.25935895]])"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-1 & 0 & 0 & 0.4 & 0 & 0\\\\0 & -1 & 0 & 0 & 0.8 & 0\\\\0.266666666666667 & 0.8 & -1 & 0.4 & 0 & 0\\\\0.266666666666667 & 0 & 0 & -1 & 0 & -0.2\\\\0.266666666666667 & 0 & 0.8 & 0 & -1 & 0\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡       -1           0    0   0.4   0    0  ⎤\n",
       "⎢                                           ⎥\n",
       "⎢        0          -1    0    0   0.8   0  ⎥\n",
       "⎢                                           ⎥\n",
       "⎢0.266666666666667  0.8  -1   0.4   0    0  ⎥\n",
       "⎢                                           ⎥\n",
       "⎢0.266666666666667   0    0   -1    0   -0.2⎥\n",
       "⎢                                           ⎥\n",
       "⎣0.266666666666667   0   0.8   0   -1    0  ⎦"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "delta = 0.8\n",
    "N = 5\n",
    "M = Matrix([[0,0,0,1/2,0], [0,0,0,0,1], [1/3,1,0,1/2,0], [1/3,0,0,0,0], [1/3,0,1,0,0]])\n",
    "temp = delta*M - eye(N)\n",
    "Svector =  -(1- delta)*Matrix([0,0,0,1,0])\n",
    "A = temp.col_insert(N, Svector)\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left ( \\left[\\begin{matrix}1 & 0 & 0 & 0 & 0 & 0.0895522388059701\\\\0 & 1 & 0 & 0 & 0 & 0.187912894543675\\\\0 & 0 & 1 & 0 & 0 & 0.263763151455836\\\\0 & 0 & 0 & 1 & 0 & 0.223880597014925\\\\0 & 0 & 0 & 0 & 1 & 0.234891118179594\\end{matrix}\\right], \\quad \\left ( 0, \\quad 1, \\quad 2, \\quad 3, \\quad 4\\right )\\right )$$"
      ],
      "text/plain": [
       "⎛⎡1  0  0  0  0  0.0895522388059701⎤                 ⎞\n",
       "⎜⎢                                 ⎥                 ⎟\n",
       "⎜⎢0  1  0  0  0  0.187912894543675 ⎥                 ⎟\n",
       "⎜⎢                                 ⎥                 ⎟\n",
       "⎜⎢0  0  1  0  0  0.263763151455836 ⎥, (0, 1, 2, 3, 4)⎟\n",
       "⎜⎢                                 ⎥                 ⎟\n",
       "⎜⎢0  0  0  1  0  0.223880597014925 ⎥                 ⎟\n",
       "⎜⎢                                 ⎥                 ⎟\n",
       "⎝⎣0  0  0  0  1  0.234891118179594 ⎦                 ⎠"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.rref()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0.0895522388059701\\\\0.187912894543675\\\\0.263763151455836\\\\0.223880597014925\\\\0.234891118179594\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡0.0895522388059701⎤\n",
       "⎢                  ⎥\n",
       "⎢0.187912894543675 ⎥\n",
       "⎢                  ⎥\n",
       "⎢0.263763151455836 ⎥\n",
       "⎢                  ⎥\n",
       "⎢0.223880597014925 ⎥\n",
       "⎢                  ⎥\n",
       "⎣0.234891118179594 ⎦"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result = A.rref()\n",
    "result[0].col(-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result = A.rref()\n",
    "result = np.array(result[0].col(-1), dtype='f')\n",
    "result.sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration 0 ...\n",
      "distance =  0.1665332814843917\n",
      "[[0.08      ]\n",
      " [0.16      ]\n",
      " [0.29333333]\n",
      " [0.25333333]\n",
      " [0.21333333]]\n",
      "iteration 1 ...\n",
      "distance =  0.07234485432509959\n",
      "[[0.10133333]\n",
      " [0.17066667]\n",
      " [0.25066667]\n",
      " [0.22133333]\n",
      " [0.256     ]]\n",
      "iteration 2 ...\n",
      "distance =  0.04660898052920942\n",
      "[[0.08853333]\n",
      " [0.2048    ]\n",
      " [0.25208889]\n",
      " [0.22702222]\n",
      " [0.22755556]]\n",
      "iteration 3 ...\n",
      "distance =  0.034994759726755295\n",
      "[[0.09080889]\n",
      " [0.18204445]\n",
      " [0.27825778]\n",
      " [0.22360889]\n",
      " [0.22528   ]]\n",
      "iteration 4 ...\n",
      "distance =  0.028795744804246303\n",
      "[[0.08944356]\n",
      " [0.180224  ]\n",
      " [0.25929482]\n",
      " [0.2242157 ]\n",
      " [0.24682193]]\n",
      "iteration 5 ...\n",
      "distance =  0.023259299795727877\n",
      "[[0.08968628]\n",
      " [0.19745754]\n",
      " [0.2577171 ]\n",
      " [0.22385162]\n",
      " [0.23128747]]\n",
      "iteration 6 ...\n",
      "distance =  0.018540659804773187\n",
      "[[0.08954065]\n",
      " [0.18502998]\n",
      " [0.27142302]\n",
      " [0.22391634]\n",
      " [0.23009002]]\n",
      "iteration 7 ...\n",
      "distance =  0.014812063729907244\n",
      "[[0.08956654]\n",
      " [0.18407202]\n",
      " [0.26146802]\n",
      " [0.22387751]\n",
      " [0.24101592]]\n",
      "iteration 8 ...\n",
      "distance =  0.011845526708128903\n",
      "[[0.089551  ]\n",
      " [0.19281274]\n",
      " [0.26069303]\n",
      " [0.22388441]\n",
      " [0.23305883]]\n",
      "iteration 9 ...\n",
      "distance =  0.009475666005505251\n",
      "[[0.08955376]\n",
      " [0.18644706]\n",
      " [0.26768422]\n",
      " [0.22388027]\n",
      " [0.23243469]]\n",
      "iteration 10 ...\n",
      "distance =  0.00758169375863584\n",
      "[[0.08955211]\n",
      " [0.18594775]\n",
      " [0.26259076]\n",
      " [0.223881  ]\n",
      " [0.23802838]]\n",
      "iteration 11 ...\n",
      "distance =  0.006065661419303839\n",
      "[[0.0895524 ]\n",
      " [0.19042271]\n",
      " [0.26219117]\n",
      " [0.22388056]\n",
      " [0.23395317]]\n",
      "iteration 12 ...\n",
      "distance =  0.0048524515044426125\n",
      "[[0.08955223]\n",
      " [0.18716254]\n",
      " [0.26577103]\n",
      " [0.22388064]\n",
      " [0.23363357]]\n",
      "iteration 13 ...\n",
      "distance =  0.003881936984790919\n",
      "[[0.08955226]\n",
      " [0.18690686]\n",
      " [0.26316288]\n",
      " [0.22388059]\n",
      " [0.23649742]]\n",
      "iteration 14 ...\n",
      "distance =  0.0031055446477636244\n",
      "[[0.08955224]\n",
      " [0.18919794]\n",
      " [0.26295833]\n",
      " [0.2238806 ]\n",
      " [0.23441091]]\n",
      "iteration 15 ...\n",
      "distance =  0.002484434812993571\n",
      "[[0.08955224]\n",
      " [0.18752873]\n",
      " [0.26479119]\n",
      " [0.2238806 ]\n",
      " [0.23424726]]\n",
      "iteration 16 ...\n",
      "distance =  0.0019875492603849175\n",
      "[[0.08955224]\n",
      " [0.18739781]\n",
      " [0.26345582]\n",
      " [0.2238806 ]\n",
      " [0.23571355]]\n",
      "iteration 17 ...\n",
      "distance =  0.0015900397803807651\n",
      "[[0.08955224]\n",
      " [0.18857084]\n",
      " [0.26335108]\n",
      " [0.2238806 ]\n",
      " [0.23464525]]\n",
      "iteration 18 ...\n",
      "distance =  0.0012720317301086\n",
      "[[0.08955224]\n",
      " [0.1877162 ]\n",
      " [0.26428951]\n",
      " [0.2238806 ]\n",
      " [0.23456146]]\n",
      "iteration 19 ...\n",
      "distance =  0.0010176253546977487\n",
      "[[0.08955224]\n",
      " [0.18764917]\n",
      " [0.2636058 ]\n",
      " [0.2238806 ]\n",
      " [0.2353122 ]]\n",
      "iteration 20 ...\n",
      "distance =  0.0008141002777631446\n",
      "[[0.08955224]\n",
      " [0.18824976]\n",
      " [0.26355217]\n",
      " [0.2238806 ]\n",
      " [0.23476524]]\n",
      "iteration 21 ...\n",
      "distance =  0.0006512802211119351\n",
      "[[0.08955224]\n",
      " [0.18781219]\n",
      " [0.26403265]\n",
      " [0.2238806 ]\n",
      " [0.23472234]]\n",
      "iteration 22 ...\n",
      "distance =  0.0005210241786007086\n",
      "[[0.08955224]\n",
      " [0.18777787]\n",
      " [0.26368259]\n",
      " [0.2238806 ]\n",
      " [0.23510672]]\n",
      "iteration 23 ...\n",
      "distance =  0.00041681934333212073\n",
      "[[0.08955224]\n",
      " [0.18808537]\n",
      " [0.26365513]\n",
      " [0.2238806 ]\n",
      " [0.23482667]]\n",
      "iteration 24 ...\n",
      "distance =  0.00033345547455136513\n",
      "[[0.08955224]\n",
      " [0.18786133]\n",
      " [0.26390114]\n",
      " [0.2238806 ]\n",
      " [0.2348047 ]]\n",
      "iteration 25 ...\n",
      "distance =  0.0002667643796054009\n",
      "[[0.08955224]\n",
      " [0.18784376]\n",
      " [0.2637219 ]\n",
      " [0.2238806 ]\n",
      " [0.23500151]]\n",
      "iteration 26 ...\n",
      "distance =  0.00021341150367705703\n",
      "[[0.08955224]\n",
      " [0.1880012 ]\n",
      " [0.26370785]\n",
      " [0.2238806 ]\n",
      " [0.23485812]]\n",
      "iteration 27 ...\n",
      "distance =  0.00017072920294033148\n",
      "[[0.08955224]\n",
      " [0.1878865 ]\n",
      " [0.2638338 ]\n",
      " [0.2238806 ]\n",
      " [0.23484688]]\n",
      "iteration 28 ...\n",
      "distance =  0.00013658336235435165\n",
      "[[0.08955224]\n",
      " [0.1878775 ]\n",
      " [0.26374203]\n",
      " [0.2238806 ]\n",
      " [0.23494764]]\n",
      "iteration 29 ...\n",
      "distance =  0.00010926668988405188\n",
      "[[0.08955224]\n",
      " [0.18795811]\n",
      " [0.26373484]\n",
      " [0.2238806 ]\n",
      " [0.23487423]]\n",
      "iteration 30 ...\n",
      "distance =  8.7413351907146e-05\n",
      "[[0.08955224]\n",
      " [0.18789938]\n",
      " [0.26379933]\n",
      " [0.2238806 ]\n",
      " [0.23486847]]\n",
      "iteration 31 ...\n",
      "distance =  6.993068152568813e-05\n",
      "[[0.08955224]\n",
      " [0.18789477]\n",
      " [0.26375234]\n",
      " [0.2238806 ]\n",
      " [0.23492006]]\n",
      "iteration 32 ...\n",
      "distance =  5.5944545220550496e-05\n",
      "[[0.08955224]\n",
      " [0.18793605]\n",
      " [0.26374866]\n",
      " [0.2238806 ]\n",
      " [0.23488247]]\n",
      "iteration 33 ...\n",
      "distance =  4.475563617641729e-05\n",
      "[[0.08955224]\n",
      " [0.18790598]\n",
      " [0.26378167]\n",
      " [0.2238806 ]\n",
      " [0.23487952]]\n",
      "iteration 34 ...\n",
      "distance =  3.580450894114802e-05\n",
      "[[0.08955224]\n",
      " [0.18790362]\n",
      " [0.26375762]\n",
      " [0.2238806 ]\n",
      " [0.23490594]]\n",
      "iteration 35 ...\n",
      "distance =  2.8643607152896112e-05\n",
      "[[0.08955224]\n",
      " [0.18792475]\n",
      " [0.26375573]\n",
      " [0.2238806 ]\n",
      " [0.23488669]]\n",
      "iteration 36 ...\n",
      "distance =  2.2914885722264017e-05\n",
      "[[0.08955224]\n",
      " [0.18790935]\n",
      " [0.26377264]\n",
      " [0.2238806 ]\n",
      " [0.23488518]]\n",
      "iteration 37 ...\n",
      "distance =  1.8331908577822402e-05\n",
      "[[0.08955224]\n",
      " [0.18790815]\n",
      " [0.26376032]\n",
      " [0.2238806 ]\n",
      " [0.23489871]]\n",
      "iteration 38 ...\n",
      "distance =  1.4665526862244246e-05\n",
      "[[0.08955224]\n",
      " [0.18791897]\n",
      " [0.26375935]\n",
      " [0.2238806 ]\n",
      " [0.23488885]]\n",
      "iteration 39 ...\n",
      "distance =  1.173242148975035e-05\n",
      "[[0.08955224]\n",
      " [0.18791108]\n",
      " [0.26376801]\n",
      " [0.2238806 ]\n",
      " [0.23488808]]\n",
      "iteration 40 ...\n",
      "distance =  9.385937191761887e-06\n",
      "[[0.08955224]\n",
      " [0.18791046]\n",
      " [0.2637617 ]\n",
      " [0.2238806 ]\n",
      " [0.23489501]]\n",
      "iteration 41 ...\n",
      "distance =  7.508749753403146e-06\n",
      "[[0.08955224]\n",
      " [0.187916  ]\n",
      " [0.26376121]\n",
      " [0.2238806 ]\n",
      " [0.23488996]]\n",
      "iteration 42 ...\n",
      "distance =  6.0069998027232486e-06\n",
      "[[0.08955224]\n",
      " [0.18791197]\n",
      " [0.26376564]\n",
      " [0.2238806 ]\n",
      " [0.23488956]]\n",
      "iteration 43 ...\n",
      "distance =  4.8055998421603165e-06\n",
      "[[0.08955224]\n",
      " [0.18791165]\n",
      " [0.26376241]\n",
      " [0.2238806 ]\n",
      " [0.23489311]]\n",
      "iteration 44 ...\n",
      "distance =  3.8444798737326415e-06\n",
      "[[0.08955224]\n",
      " [0.18791449]\n",
      " [0.26376216]\n",
      " [0.2238806 ]\n",
      " [0.23489053]]\n",
      "iteration 45 ...\n",
      "distance =  3.075583899009953e-06\n",
      "[[0.08955224]\n",
      " [0.18791242]\n",
      " [0.26376443]\n",
      " [0.2238806 ]\n",
      " [0.23489032]]\n",
      "iteration 46 ...\n",
      "distance =  2.460467119210961e-06\n",
      "[[0.08955224]\n",
      " [0.18791226]\n",
      " [0.26376277]\n",
      " [0.2238806 ]\n",
      " [0.23489214]]\n",
      "iteration 47 ...\n",
      "distance =  1.968373695378056e-06\n",
      "[[0.08955224]\n",
      " [0.18791371]\n",
      " [0.26376264]\n",
      " [0.2238806 ]\n",
      " [0.23489082]]\n",
      "iteration 48 ...\n",
      "distance =  1.5746989563463958e-06\n",
      "[[0.08955224]\n",
      " [0.18791265]\n",
      " [0.26376381]\n",
      " [0.2238806 ]\n",
      " [0.23489071]]\n",
      "iteration 49 ...\n",
      "distance =  1.2597591651024927e-06\n",
      "[[0.08955224]\n",
      " [0.18791257]\n",
      " [0.26376296]\n",
      " [0.2238806 ]\n",
      " [0.23489164]]\n",
      "iteration 50 ...\n",
      "distance =  1.0078073320686114e-06\n",
      "[[0.08955224]\n",
      " [0.18791331]\n",
      " [0.26376289]\n",
      " [0.2238806 ]\n",
      " [0.23489097]]\n",
      "iteration 51 ...\n",
      "distance =  8.062458656556205e-07\n",
      "[[0.08955224]\n",
      " [0.18791277]\n",
      " [0.26376349]\n",
      " [0.2238806 ]\n",
      " [0.23489091]]\n",
      "iteration 52 ...\n",
      "distance =  6.449966925110404e-07\n",
      "[[0.08955224]\n",
      " [0.18791273]\n",
      " [0.26376306]\n",
      " [0.2238806 ]\n",
      " [0.23489139]]\n",
      "iteration 53 ...\n",
      "distance =  5.159973540274073e-07\n",
      "[[0.08955224]\n",
      " [0.18791311]\n",
      " [0.26376302]\n",
      " [0.2238806 ]\n",
      " [0.23489104]]\n",
      "iteration 54 ...\n",
      "distance =  4.1279788319289337e-07\n",
      "[[0.08955224]\n",
      " [0.18791283]\n",
      " [0.26376333]\n",
      " [0.2238806 ]\n",
      " [0.23489101]]\n",
      "iteration 55 ...\n",
      "distance =  3.3023830654648985e-07\n",
      "[[0.08955224]\n",
      " [0.18791281]\n",
      " [0.2637631 ]\n",
      " [0.2238806 ]\n",
      " [0.23489126]]\n",
      "iteration 56 ...\n",
      "distance =  2.641906452287088e-07\n",
      "[[0.08955224]\n",
      " [0.18791301]\n",
      " [0.26376309]\n",
      " [0.2238806 ]\n",
      " [0.23489108]]\n",
      "iteration 57 ...\n",
      "distance =  2.113525161226351e-07\n",
      "[[0.08955224]\n",
      " [0.18791286]\n",
      " [0.26376324]\n",
      " [0.2238806 ]\n",
      " [0.23489107]]\n",
      "iteration 58 ...\n",
      "distance =  1.6908201286154323e-07\n",
      "[[0.08955224]\n",
      " [0.18791285]\n",
      " [0.26376313]\n",
      " [0.2238806 ]\n",
      " [0.23489119]]\n",
      "iteration 59 ...\n",
      "distance =  1.352656102914285e-07\n",
      "[[0.08955224]\n",
      " [0.18791295]\n",
      " [0.26376312]\n",
      " [0.2238806 ]\n",
      " [0.2348911 ]]\n",
      "iteration 60 ...\n",
      "distance =  1.0821248824952382e-07\n",
      "[[0.08955224]\n",
      " [0.18791288]\n",
      " [0.2637632 ]\n",
      " [0.2238806 ]\n",
      " [0.23489109]]\n",
      "iteration 61 ...\n",
      "distance =  8.656999059888775e-08\n",
      "[[0.08955224]\n",
      " [0.18791287]\n",
      " [0.26376314]\n",
      " [0.2238806 ]\n",
      " [0.23489116]]\n",
      "iteration 62 ...\n",
      "distance =  6.925599245307605e-08\n",
      "[[0.08955224]\n",
      " [0.18791293]\n",
      " [0.26376314]\n",
      " [0.2238806 ]\n",
      " [0.23489111]]\n",
      "iteration 63 ...\n",
      "distance =  5.540479393898622e-08\n",
      "[[0.08955224]\n",
      " [0.18791289]\n",
      " [0.26376318]\n",
      " [0.2238806 ]\n",
      " [0.23489111]]\n",
      "iteration 64 ...\n",
      "distance =  4.432383517656497e-08\n",
      "[[0.08955224]\n",
      " [0.18791289]\n",
      " [0.26376315]\n",
      " [0.2238806 ]\n",
      " [0.23489114]]\n",
      "iteration 65 ...\n",
      "distance =  3.5459068147614253e-08\n",
      "[[0.08955224]\n",
      " [0.18791291]\n",
      " [0.26376315]\n",
      " [0.2238806 ]\n",
      " [0.23489112]]\n",
      "iteration 66 ...\n",
      "distance =  2.836725452964589e-08\n",
      "[[0.08955224]\n",
      " [0.18791289]\n",
      " [0.26376317]\n",
      " [0.2238806 ]\n",
      " [0.23489111]]\n",
      "iteration 67 ...\n",
      "distance =  2.269380365501621e-08\n",
      "[[0.08955224]\n",
      " [0.18791289]\n",
      " [0.26376315]\n",
      " [0.2238806 ]\n",
      " [0.23489113]]\n",
      "iteration 68 ...\n",
      "distance =  1.8155042920722133e-08\n",
      "[[0.08955224]\n",
      " [0.1879129 ]\n",
      " [0.26376315]\n",
      " [0.2238806 ]\n",
      " [0.23489112]]\n",
      "iteration 69 ...\n",
      "distance =  1.4524034321293607e-08\n",
      "[[0.08955224]\n",
      " [0.1879129 ]\n",
      " [0.26376316]\n",
      " [0.2238806 ]\n",
      " [0.23489112]]\n",
      "iteration 70 ...\n",
      "distance =  1.1619227494331016e-08\n",
      "[[0.08955224]\n",
      " [0.18791289]\n",
      " [0.26376315]\n",
      " [0.2238806 ]\n",
      " [0.23489113]]\n",
      "iteration 71 ...\n",
      "distance =  9.295381986250477e-09\n",
      "[[0.08955224]\n",
      " [0.1879129 ]\n",
      " [0.26376315]\n",
      " [0.2238806 ]\n",
      " [0.23489112]]\n"
     ]
    }
   ],
   "source": [
    "# PageRank Algorithm\n",
    "M = np.array(M, dtype='f')\n",
    "N = 5\n",
    "delta = 0.8\n",
    "elipslion = 1e-8\n",
    "R = np.ones((N,1))*(1/N)\n",
    "#R = np.ones((N,1))\n",
    "# K = np.ones((N,1))*((1- delta)/N)\n",
    "K = np.zeros((N,1))\n",
    "K[3] = ((1- delta))\n",
    "# R = delta * np.matmul(M,prevR) + K\n",
    "iteration = 0\n",
    "distance = 100\n",
    "\n",
    "while distance > elipslion:\n",
    "    print(\"iteration\", iteration, \"...\")\n",
    "    prevR = R\n",
    "    R = delta * np.matmul(M,R) + K\n",
    "    iteration = iteration + 1\n",
    "    distance = np.linalg.norm(R-prevR)\n",
    "    print(\"distance = \",np.linalg.norm(R-prevR))\n",
    "    print(R)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.08955224],\n",
       "       [0.1879129 ],\n",
       "       [0.26376315],\n",
       "       [0.2238806 ],\n",
       "       [0.23489112]])"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q3: topic sensitive PageRank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-1 & 0.4 & 0.8 & 0 & -0.2\\\\0.266666666666667 & -1 & 0 & 0.4 & 0\\\\0.266666666666667 & 0 & -1 & 0.4 & 0\\\\0.266666666666667 & 0.4 & 0 & -1 & 0\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡       -1          0.4  0.8   0   -0.2⎤\n",
       "⎢                                      ⎥\n",
       "⎢0.266666666666667  -1    0   0.4   0  ⎥\n",
       "⎢                                      ⎥\n",
       "⎢0.266666666666667   0   -1   0.4   0  ⎥\n",
       "⎢                                      ⎥\n",
       "⎣0.266666666666667  0.4   0   -1    0  ⎦"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "delta = 0.8\n",
    "N = 4\n",
    "M = Matrix([[0,1/2,1,0], [1/3,0,0,1/2], [1/3,0,0,1/2], [1/3,1/2,0,0]])\n",
    "temp = delta*M - eye(N)\n",
    "Svector =  -(1- delta)*Matrix([1,0,0,0])\n",
    "A = temp.col_insert(N, Svector)\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0.428571428571429\\\\0.19047619047619\\\\0.19047619047619\\\\0.19047619047619\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡0.428571428571429⎤\n",
       "⎢                 ⎥\n",
       "⎢0.19047619047619 ⎥\n",
       "⎢                 ⎥\n",
       "⎢0.19047619047619 ⎥\n",
       "⎢                 ⎥\n",
       "⎣0.19047619047619 ⎦"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result = A.rref()\n",
    "result[0].col(-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0.385714285714286\\\\0.171428571428571\\\\0.271428571428571\\\\0.171428571428571\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡0.385714285714286⎤\n",
       "⎢                 ⎥\n",
       "⎢0.171428571428571⎥\n",
       "⎢                 ⎥\n",
       "⎢0.271428571428571⎥\n",
       "⎢                 ⎥\n",
       "⎣0.171428571428571⎦"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "delta = 0.8\n",
    "N = 4\n",
    "M = Matrix([[0,1/2,1,0], [1/3,0,0,1/2], [1/3,0,0,1/2], [1/3,1/2,0,0]])\n",
    "temp = delta*M - eye(N)\n",
    "Svector =  -(1- delta)*Matrix([1/2,0,1/2,0])\n",
    "A = temp.col_insert(N, Svector)\n",
    "result = A.rref()\n",
    "result[0].col(-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q4. HIT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}1 & 0 & 0 & 1 & 1\\\\0 & 1 & 0 & 1 & 1\\\\0 & 0 & 1 & 1 & 1\\\\0 & 0 & 0 & 1 & 0\\\\0 & 0 & 0 & 0 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1  0  0  1  1⎤\n",
       "⎢             ⎥\n",
       "⎢0  1  0  1  1⎥\n",
       "⎢             ⎥\n",
       "⎢0  0  1  1  1⎥\n",
       "⎢             ⎥\n",
       "⎢0  0  0  1  0⎥\n",
       "⎢             ⎥\n",
       "⎣0  0  0  0  1⎦"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L = Matrix([[1,0,0,1,1], [0,1,0,1,1], [0,0,1,1,1], [0,0,0,1,0],[0,0,0,0,1]])\n",
    "L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0.333333333333333 & 0 & 0 & 0 & 0\\\\0 & 0.333333333333333 & 0 & 0 & 0\\\\0 & 0 & 0.333333333333333 & 0 & 0\\\\0.333333333333333 & 0.333333333333333 & 0.333333333333333 & 1 & 0\\\\0.333333333333333 & 0.333333333333333 & 0.333333333333333 & 0 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡0.333333333333333          0                  0          0  0⎤\n",
       "⎢                                                             ⎥\n",
       "⎢        0          0.333333333333333          0          0  0⎥\n",
       "⎢                                                             ⎥\n",
       "⎢        0                  0          0.333333333333333  0  0⎥\n",
       "⎢                                                             ⎥\n",
       "⎢0.333333333333333  0.333333333333333  0.333333333333333  1  0⎥\n",
       "⎢                                                             ⎥\n",
       "⎣0.333333333333333  0.333333333333333  0.333333333333333  0  1⎦"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "delta = 1\n",
    "N = 5\n",
    "M = Matrix([[1/3,0,0,0,0], [0,1/3,0,0,0], [0,0,1/3,0,0], [1/3,1/3,1/3,1,0],[1/3,1/3,1/3,0,1]])\n",
    "M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-0.666666666666667 & 0 & 0 & 0 & 0 & 0\\\\0 & -0.666666666666667 & 0 & 0 & 0 & 0\\\\0 & 0 & -0.666666666666667 & 0 & 0 & 0\\\\0.333333333333333 & 0.333333333333333 & 0.333333333333333 & 0 & 0 & 0\\\\0.333333333333333 & 0.333333333333333 & 0.333333333333333 & 0 & 0 & 0\\\\1 & 1 & 1 & 1 & 1 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-0.666666666666667          0                   0           0  0  0⎤\n",
       "⎢                                                                   ⎥\n",
       "⎢        0           -0.666666666666667          0           0  0  0⎥\n",
       "⎢                                                                   ⎥\n",
       "⎢        0                   0           -0.666666666666667  0  0  0⎥\n",
       "⎢                                                                   ⎥\n",
       "⎢0.333333333333333   0.333333333333333   0.333333333333333   0  0  0⎥\n",
       "⎢                                                                   ⎥\n",
       "⎢0.333333333333333   0.333333333333333   0.333333333333333   0  0  0⎥\n",
       "⎢                                                                   ⎥\n",
       "⎣        1                   1                   1           1  1  1⎦"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "temp = delta*M - eye(N)\n",
    "Svector =  -(1- delta)*Matrix([1/N,1/N,1/N,1/N,1/N])\n",
    "A = temp.col_insert(N, Svector)\n",
    "A = A.row_insert(N,ones(1,N+1))\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left ( \\left[\\begin{matrix}1 & 0 & 0 & 0 & 0 & 0\\\\0 & 1 & 0 & 0 & 0 & 0\\\\0 & 0 & 1 & 0 & 0 & 0\\\\0 & 0 & 0 & 1 & 1.0 & 1.0\\\\0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0\\end{matrix}\\right], \\quad \\left ( 0, \\quad 1, \\quad 2, \\quad 3\\right )\\right )$$"
      ],
      "text/plain": [
       "⎛⎡1  0  0  0   0    0 ⎤              ⎞\n",
       "⎜⎢                    ⎥              ⎟\n",
       "⎜⎢0  1  0  0   0    0 ⎥              ⎟\n",
       "⎜⎢                    ⎥              ⎟\n",
       "⎜⎢0  0  1  0   0    0 ⎥              ⎟\n",
       "⎜⎢                    ⎥, (0, 1, 2, 3)⎟\n",
       "⎜⎢0  0  0  1  1.0  1.0⎥              ⎟\n",
       "⎜⎢                    ⎥              ⎟\n",
       "⎜⎢0  0  0  0   0    0 ⎥              ⎟\n",
       "⎜⎢                    ⎥              ⎟\n",
       "⎝⎣0  0  0  0   0    0 ⎦              ⎠"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result = A.rref()\n",
    "result\n",
    "# result[0].col(-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A.nullspace()\n",
    "# A.eigenvects()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration 0 ...\n",
      "iteration 1 ...\n",
      "iteration 2 ...\n",
      "iteration 3 ...\n",
      "iteration 4 ...\n",
      "iteration 5 ...\n",
      "iteration 6 ...\n",
      "iteration 7 ...\n",
      "iteration 8 ...\n",
      "iteration 9 ...\n",
      "iteration 10 ...\n",
      "iteration 11 ...\n",
      "iteration 12 ...\n",
      "iteration 13 ...\n"
     ]
    }
   ],
   "source": [
    "# PageRank Algorithm\n",
    "M = np.array(M, dtype='f')\n",
    "N = 5\n",
    "delta = 0.8\n",
    "elipslion = 1e-8\n",
    "R = np.ones((N,1))*(1/N)\n",
    "#R = np.ones((N,1))\n",
    "# K = np.ones((N,1))*((1- delta)/N)\n",
    "K = np.zeros((N,1))\n",
    "K[0] = ((1- delta))\n",
    "# R = delta * np.matmul(M,prevR) + K\n",
    "iteration = 0\n",
    "distance = 100\n",
    "\n",
    "while distance > elipslion:\n",
    "    print(\"iteration\", iteration, \"...\")\n",
    "    prevR = R\n",
    "    R = delta * np.matmul(M,R) + K\n",
    "    iteration = iteration + 1\n",
    "    distance = np.linalg.norm(R-prevR)\n",
    "#     print(\"distance = \",np.linalg.norm(R-prevR))\n",
    "#     print(\"Rank = \")\n",
    "#     print(R)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[2.72727275e-01],\n",
       "       [1.83904531e-09],\n",
       "       [1.83904531e-09],\n",
       "       [3.63636377e-01],\n",
       "       [3.63636377e-01]])"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}0.333333333333333 & 0 & 0 & 0.5 & 0\\\\0 & 0.333333333333333 & 0 & 0 & 0\\\\0 & 0 & 0.333333333333333 & 0 & 0\\\\0.333333333333333 & 0.333333333333333 & 0.333333333333333 & 0.5 & 0\\\\0.333333333333333 & 0.333333333333333 & 0.333333333333333 & 0 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡0.333333333333333          0                  0          0.5  0⎤\n",
       "⎢                                                               ⎥\n",
       "⎢        0          0.333333333333333          0           0   0⎥\n",
       "⎢                                                               ⎥\n",
       "⎢        0                  0          0.333333333333333   0   0⎥\n",
       "⎢                                                               ⎥\n",
       "⎢0.333333333333333  0.333333333333333  0.333333333333333  0.5  0⎥\n",
       "⎢                                                               ⎥\n",
       "⎣0.333333333333333  0.333333333333333  0.333333333333333   0   1⎦"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "delta = 1\n",
    "N = 5\n",
    "M = Matrix([[1/3,0,0,1/2,0], [0,1/3,0,0,0], [0,0,1/3,0,0], [1/3,1/3,1/3,1/2,0],[1/3,1/3,1/3,0,1]])\n",
    "M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left[\\begin{matrix}-0.666666666666667 & 0 & 0 & 0.5 & 0 & 0\\\\0 & -0.666666666666667 & 0 & 0 & 0 & 0\\\\0 & 0 & -0.666666666666667 & 0 & 0 & 0\\\\0.333333333333333 & 0.333333333333333 & 0.333333333333333 & -0.5 & 0 & 0\\\\0.333333333333333 & 0.333333333333333 & 0.333333333333333 & 0 & 0 & 0\\\\1 & 1 & 1 & 1 & 1 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-0.666666666666667          0                   0           0.5   0  0⎤\n",
       "⎢                                                                      ⎥\n",
       "⎢        0           -0.666666666666667          0            0    0  0⎥\n",
       "⎢                                                                      ⎥\n",
       "⎢        0                   0           -0.666666666666667   0    0  0⎥\n",
       "⎢                                                                      ⎥\n",
       "⎢0.333333333333333   0.333333333333333   0.333333333333333   -0.5  0  0⎥\n",
       "⎢                                                                      ⎥\n",
       "⎢0.333333333333333   0.333333333333333   0.333333333333333    0    0  0⎥\n",
       "⎢                                                                      ⎥\n",
       "⎣        1                   1                   1            1    1  1⎦"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "temp = delta*M - eye(N)\n",
    "Svector =  -(1- delta)*Matrix([1/N,1/N,1/N,1/N,1/N])\n",
    "A = temp.col_insert(N, Svector)\n",
    "A = A.row_insert(N,ones(1,N+1))\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left ( \\left[\\begin{matrix}1 & 0 & 0 & 0 & 0 & 0\\\\0 & 1 & 0 & 0 & 0 & 0\\\\0 & 0 & 1 & 0 & 0 & 0\\\\0 & 0 & 0 & 1 & 0 & 0\\\\0 & 0 & 0 & 0 & 1 & 1.0\\\\0 & 0 & 0 & 0 & 0 & 0\\end{matrix}\\right], \\quad \\left ( 0, \\quad 1, \\quad 2, \\quad 3, \\quad 4\\right )\\right )$$"
      ],
      "text/plain": [
       "⎛⎡1  0  0  0  0   0 ⎤                 ⎞\n",
       "⎜⎢                  ⎥                 ⎟\n",
       "⎜⎢0  1  0  0  0   0 ⎥                 ⎟\n",
       "⎜⎢                  ⎥                 ⎟\n",
       "⎜⎢0  0  1  0  0   0 ⎥                 ⎟\n",
       "⎜⎢                  ⎥, (0, 1, 2, 3, 4)⎟\n",
       "⎜⎢0  0  0  1  0   0 ⎥                 ⎟\n",
       "⎜⎢                  ⎥                 ⎟\n",
       "⎜⎢0  0  0  0  1  1.0⎥                 ⎟\n",
       "⎜⎢                  ⎥                 ⎟\n",
       "⎝⎣0  0  0  0  0   0 ⎦                 ⎠"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result = A.rref()\n",
    "result"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}