CP220_2024_Quiz2_Q.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "view-in-github"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/AshrithSagar/CP220-M4RAS-2024/blob/main/CP220_2024_Quiz2_Q.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Jq34pkM7-BOX"
      },
      "source": [
        "---\n",
        "**CP220-2024 Quiz2**\n",
        "\n",
        "Copy this notebook into your directory\n",
        "\n",
        "Please write the final answer using the form\n",
        "\n",
        "Also paste the link to your answer notebook using the same form\n",
        "\n",
        "The text cells for answers are optional - but might be useful for you to work through your solution\n",
        "\n",
        "(you can also write on paper and take a photo and upload your work)\n",
        "\n",
        "This could be useful in case there is a case for partial grading.\n",
        "\n",
        "The code cells are also optional but higly recommended as it will allow you to calculate the answers easily.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "GMcDWDZUILlp"
      },
      "outputs": [],
      "source": [
        "import numpy as np"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HgBXroJNITnn"
      },
      "source": [
        "---\n",
        "**Q1 (1pt)** <br>\n",
        "\n",
        "Let $A=\\begin{bmatrix} 1 & 1 \\\\ 0 & 2 \\end{bmatrix}$\n",
        "\n",
        "The singular values of $A$ in decreasing order are (include only one digit after decimal point):\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 22,
      "metadata": {
        "id": "ggbQ0PZfYg-B"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Eigenvalues of (A^T)(A) are [5.23606798 0.76393202]\n"
          ]
        }
      ],
      "source": [
        "#Ans\n",
        "A = np.array([[1,1],\n",
        "              [0,2]])\n",
        "ATA = np.dot(A.T,A)\n",
        "L, X = np.linalg.eig(ATA)\n",
        "L = L[::-1]\n",
        "print(f\"Eigenvalues of (A^T)(A) are {L}\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Therefore, the singular values of $A$ in decreasing order are $\\sigma_1=5.2$ and $\\sigma_2=0.8$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wImoHlUhmCez"
      },
      "source": [
        "---\n",
        "\n",
        "**Q2 (2pt)**\n",
        "\n",
        "Consider a unit square (vertices at (0.5,-0.5), (0.5,0.5),(-0.5,0.5), (-0.5,-0.5))\n",
        "\n",
        "It undergoes an arbitrary rotation and  the vertices end up as\n",
        "\n",
        "B = np.array(\n",
        "    [[-0.18,0.68,0.18,0.18],\n",
        " [-0.68,-0.18,0.68,0.68]]\n",
        ")\n",
        "\n",
        "Let R be the rotation matrix which results in this rotation.\n",
        "\n",
        "Then the elements of R[0,0], R[0,1], R[1,0], R[1,1] with upto 1 decimal precision after are:\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-KkOZ857pJAH"
      },
      "source": [
        "---\n",
        "\n",
        "Ans (explanation - optional):\n",
        "\n",
        "$ R = \\begin{bmatrix} \\cos(\\theta) & -\\sin(\\theta) \\\\ \\sin(\\theta) & \\cos(\\theta) \\end{bmatrix} $\n",
        "\n",
        "$ R = \\begin{bmatrix} -0.8 & 0.6 \\\\ -0.6 & -0.8 \\end{bmatrix} $"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 69,
      "metadata": {
        "id": "gMYB2I8xm55J"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "RA = [-0.7 -0.7]\n"
          ]
        }
      ],
      "source": [
        "A = np.array([[0.5,-0.5],[0.5,0.5],[-0.5,0.5],[-0.5,0.5]]).T\n",
        "\n",
        "B = np.array(\n",
        "    [[-0.18,0.68,0.18,0.18],\n",
        " [-0.68,-0.18,0.68,0.68]]\n",
        ")\n",
        "\n",
        "R = np.array([[-0.8,0.6],[-0.6,0.8]])\n",
        "RA = np.dot(R,A)\n",
        "RB = np.dot(R,B)\n",
        "\n",
        "a = [0.5, -0.5]\n",
        "print(f\"RA = {np.dot(R,a)}\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 70,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "R[0,0]: 0.5\n",
            "R[0,1]: 0.9\n",
            "R[1,0]: -0.9\n",
            "R[1,1]: 0.5\n"
          ]
        }
      ],
      "source": [
        "import numpy as np\n",
        "\n",
        "# Original vertices of the unit square\n",
        "original_vertices = np.array([\n",
        "    [0.5, -0.5],\n",
        "    [0.5, 0.5],\n",
        "    [-0.5, 0.5],\n",
        "    [-0.5, -0.5]\n",
        "])\n",
        "\n",
        "# Transformed vertices\n",
        "B = np.array([\n",
        "    [-0.18, 0.68, 0.18, 0.18],\n",
        "    [-0.68, -0.18, 0.68, 0.68]\n",
        "])\n",
        "\n",
        "# Calculate the rotation matrix using two pairs of points\n",
        "# Let's take the first original vertex and its transformed counterpart\n",
        "original_point = original_vertices[0]  # (0.5, 0.5)\n",
        "transformed_point = B[:, 0]            # (-0.18, -0.68)\n",
        "\n",
        "# Calculate the rotation angle\n",
        "theta = np.arctan2(transformed_point[1], transformed_point[0]) - np.arctan2(original_point[1], original_point[0])\n",
        "\n",
        "# Construct the rotation matrix\n",
        "R = np.array([\n",
        "    [np.cos(theta), -np.sin(theta)],\n",
        "    [np.sin(theta),  np.cos(theta)]\n",
        "])\n",
        "\n",
        "# Round the elements to 1 decimal precision\n",
        "R_rounded = np.round(R, 1)\n",
        "\n",
        "# Output the relevant elements\n",
        "elements = R_rounded.flatten()\n",
        "print(\"R[0,0]:\", elements[0])\n",
        "print(\"R[0,1]:\", elements[1])\n",
        "print(\"R[1,0]:\", elements[2])\n",
        "print(\"R[1,1]:\", elements[3])\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ew6eDcXexEw5"
      },
      "source": [
        "---\n",
        "**Q3(2pt)**\n",
        "\n",
        "Find the geometric multiplicity for the eigen value of 3 for a matrix under the following conditions:\n",
        "\n",
        "a)  $A$ is  similar to  $\\begin{bmatrix} 3 & 0 & 0 &0 \\\\ 0 & 3 & 1 & 0  \\\\ 0 & 0 & 3 & 1 \\\\ 0 & 0 & 0 & 3 \\end{bmatrix}$\n",
        "\n",
        "b)  $A$ is  similar to  $\\begin{bmatrix} 3 & 1 & 0 &0 \\\\ 0 & 3 & 1 & 0  \\\\ 0 & 0 & 3 & 1 \\\\ 0 & 0 & 0 & 3 \\end{bmatrix}$\n",
        "\n",
        "c)  $A$ is  similar to  $\\begin{bmatrix} 3 & 1 & 0 &0 \\\\ 0 & 3 & 0 & 0  \\\\ 0 & 0 & 3 & 1 \\\\ 0 & 0 & 0 & 3 \\end{bmatrix}$\n",
        "\n",
        "d)  $A$ is  similar to  $\\begin{bmatrix} 3 & 0 & 0 &0 \\\\ 0 & 3 & 0 & 0  \\\\ 0 & 0 & 3 & 1 \\\\ 0 & 0 & 0 & 3 \\end{bmatrix}$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "q6Bl_0BFz_Zf"
      },
      "source": [
        "---\n",
        "\n",
        "Ans (explanation optional):\n",
        "\n",
        "Since all of them are triangular matrices in some sense, we have that all the eigenvalues for each of the matrices above is 3.\n",
        "That is, algbraic multiplicity of the eigenvalue 3 is 4 for all the matrices above.\n",
        "\n",
        "For geometric multiplicity, we count the number of jordan blocks.\n",
        "\n",
        "(a). GM = 1 + 1 = 2\n",
        "\n",
        "(b). GM = 1\n",
        "\n",
        "(c). GM = 1 + 1 = 2\n",
        "\n",
        "(d). GM = 1 + 1 + 1 = 3\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 38,
      "metadata": {
        "id": "lVC5aA2C0PW8"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Geometric multiplicity for eigenvalue 3 in matrix a: 2\n",
            "Geometric multiplicity for eigenvalue 3 in matrix b: 1\n",
            "Geometric multiplicity for eigenvalue 3 in matrix c: 2\n",
            "Geometric multiplicity for eigenvalue 3 in matrix d: 3\n"
          ]
        }
      ],
      "source": [
        "def geometric_multiplicity(matrix, eigenvalue):\n",
        "    I = np.eye(matrix.shape[0])\n",
        "    matrix_lI = matrix - eigenvalue * I\n",
        "    u, s, vh = np.linalg.svd(matrix_lI)\n",
        "    rank = np.sum(s > 1e-10)  # tolerance\n",
        "    nullity = matrix_lI.shape[0] - rank\n",
        "    return nullity\n",
        "\n",
        "matrices = {\n",
        "    'a': np.array([[3, 0, 0, 0],\n",
        "                   [0, 3, 1, 0],\n",
        "                   [0, 0, 3, 1],\n",
        "                   [0, 0, 0, 3]]),\n",
        "    \n",
        "    'b': np.array([[3, 1, 0, 0],\n",
        "                   [0, 3, 1, 0],\n",
        "                   [0, 0, 3, 1],\n",
        "                   [0, 0, 0, 3]]),\n",
        "    \n",
        "    'c': np.array([[3, 1, 0, 0],\n",
        "                   [0, 3, 0, 0],\n",
        "                   [0, 0, 3, 1],\n",
        "                   [0, 0, 0, 3]]),\n",
        "    \n",
        "    'd': np.array([[3, 0, 0, 0],\n",
        "                   [0, 3, 0, 0],\n",
        "                   [0, 0, 3, 1],\n",
        "                   [0, 0, 0, 3]])\n",
        "}\n",
        "\n",
        "eigenvalue = 3\n",
        "for key, matrix in matrices.items():\n",
        "    g_mult = geometric_multiplicity(matrix, eigenvalue)\n",
        "    print(f\"Geometric multiplicity for eigenvalue {eigenvalue} in matrix {key}: {g_mult}\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nQd35ITvgiqF"
      },
      "source": [
        "---\n",
        "**Q4 (1.5 pts)**\n",
        "\n",
        "*Google's page rank algorithm*\n",
        "\n",
        "Let pages 1, 2, 3 be three web pages, with an outgoing hyperlink from page 1 to page 2, and page 2 to page 3 and and one link each to pages 1 and 2 from page 3. We can model this connectivity as a graph G of Vertices (V) and Edges (E) as follows:\n",
        "\n",
        "$V = \\{ 1, 2, 3\\}$\n",
        "\n",
        "$E \\in V \\times V = \\{(1,2), (2,3), (3,1), (3,2)\\}$\n",
        "\n",
        "The ajacency matrix representation of this graph is:\n",
        "\n",
        "$A = \\begin{bmatrix} 0 & 0 & 1\\\\ 1 & 0 & 1 \\\\ 0 & 1 & 0 \\end{bmatrix}$\n",
        "\n",
        "with the interpretation that rows and columns correspond to vertices 1,2,3 and $a_{ij}=1$ if there is an edge from node $j$ to node $i$ (i.e $(j,i) \\in E$)\n",
        "\n",
        "\n",
        "The weight of each outgoing edge from a vertex is just the 1 over the total number of outgoing edges from that vertex.\n",
        "\n",
        "$W_{ik} = \\frac{1}{\\sum_{k=1}^{k=3} I((k,i)\\in E)}$\n",
        "\n",
        "Here $I(cond) = 1$ if and only if $cond$ is True, otherwise it is 0.\n",
        "\n",
        "The weight adjacency matrix for the above web of pages can then be written as:\n",
        "\n",
        "$G=\\begin{bmatrix} 0 & 0 & 1/2 \\\\ 1 & 0 & 1/2 \\\\ 0 & 1 & 0 \\end{bmatrix}$ (i.e. columns are normalized to sum to 1)\n",
        "\n",
        "A person browsing the web, and looking at page $i$, will go out with equal chance through one of the hyperlinks of the page. For example, a person on web page 3, at the next time step, could land up in pages 1 and 2 with equal chance. Similarly, a person on web page 1, will go to page 2 and a person on page 2, will go to page 3.\n",
        "\n",
        "Let the initial chances of being in pages 1, 2, 3 be $\\pi_0 = \\begin{bmatrix} \\frac{1}{4} \\\\ \\frac{1}{4} \\\\ \\frac{1}{2} \\end{bmatrix}$,\n",
        "\n",
        "if $\\pi_t$ is the vector indicating the probabilities of being in different pages at time $t$ then the same at $t+1$ is:\n",
        "\n",
        "$\\pi_{t+1} = G \\pi_t$\n",
        "\n",
        "Given the initial vector $\\pi_0$ as above, what is $\\pi_∞$? (write answer in decmial notation with 1 digit precision after decimal point and first component being positive)\n",
        "\n",
        "\n",
        "(As an side, the values of $\\pi_∞$ give the page rank of web pages, which is then used to sort the pages and present to you on a web search)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pjCfFwFlgzbf"
      },
      "source": [
        "Ans (explanation optional):\n",
        "\n",
        "Seems like a markov chain.\n",
        "And we need to calulate the steady state."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 49,
      "metadata": {
        "id": "SSDTC6nJhsPi"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Evolved Distribution after 100 iterations: [0.35 0.35 0.35]\n",
            "Steady-State Distribution: [0.33333333 0.33333333 0.33333333]\n"
          ]
        }
      ],
      "source": [
        "G = np.array([[0,0,0.5],[1,0,0.5],[0,1,0]])\n",
        "p_0 = np.array([1/4,1/4,1/2])\n",
        "\n",
        "num_iterations = 100\n",
        "p = p_0\n",
        "\n",
        "for _ in range(num_iterations):\n",
        "    p = p @ G\n",
        "\n",
        "print(\"Evolved Distribution after 100 iterations:\", p)\n",
        "\n",
        "A = np.append(G.T - np.eye(G.shape[0]), np.ones((1, G.shape[0])), axis=0)\n",
        "b = np.zeros(G.shape[0] + 1)\n",
        "b[-1] = 1\n",
        "\n",
        "steady_state = np.linalg.lstsq(A, b, rcond=None)[0]\n",
        "print(\"Steady-State Distribution:\", steady_state)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1cAkvldTijCY"
      },
      "source": [
        "**Q5 (3.5pt)**\n",
        "\n",
        "Let $A=\\begin{bmatrix} 1 & 0 & 0 \\\\ 0 & 1 & 0 \\\\ 1 &\n",
        " 1 & 0 \\end{bmatrix}$.\n",
        "\n",
        "and $b=\\begin{bmatrix} 2 \\\\ 2 \\\\ 2 \\end{bmatrix}$\n",
        "\n",
        "Then if $x_s = min_x ||Ax-b||$,\n",
        "the number of solutions which achieve minima is ________<br>\n",
        "and the minimim norm solution is: [\\__,\\__,\\__]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GgAcePGAW2Ix"
      },
      "source": [
        "---\n",
        "\n",
        "Ans (explanation optional):\n",
        "\n",
        "We can use the matrix pseudoinverse to solve this.\n",
        "\n",
        "The pseudoinverse of a matrix $A$ is given by $A^+ = (A^TA)^{-1}A^T$\n",
        "\n",
        "Then the minimum norm solution is given by $x_s = A^+b$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 50,
      "metadata": {
        "id": "5SWwRZ__h19L"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Number of solutions which achieve minima: unique\n",
            "Minimum norm solution: [0.44444444 0.88888889 0.44444444]\n"
          ]
        }
      ],
      "source": [
        "A = np.array([\n",
        "    [1,1,0],\n",
        "    [0,1,1],\n",
        "    [1,2,1]\n",
        "])\n",
        "b = np.array([2, 2, 2])\n",
        "A_pseudo_inv = np.linalg.pinv(A)\n",
        "\n",
        "x_s = A_pseudo_inv @ b # Minimum norm solution\n",
        "\n",
        "rank_A = np.linalg.matrix_rank(A)\n",
        "rank_Ab = np.linalg.matrix_rank(np.column_stack((A, b)))\n",
        "\n",
        "if rank_A == rank_Ab:\n",
        "    num_solutions = 'infinite'\n",
        "else:\n",
        "    num_solutions = 'unique'\n",
        "\n",
        "print(\"Number of solutions which achieve minima:\", num_solutions)\n",
        "print(\"Minimum norm solution:\", x_s)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xr8TLYPBZH8j"
      },
      "source": [
        "---\n",
        "**Q6 (1.5pts)**\n",
        "\n",
        "Let $F$ be a subspace spanned by $\\{\\begin{bmatrix} 1 \\\\ 0 \\\\ 1 \\end{bmatrix}, \\begin{bmatrix} 0 \\\\ 1 \\\\ 1 \\end{bmatrix}\\}$.\n",
        "\n",
        "Let $G$ be a subspace spanned by $\\{\\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\end{bmatrix}, \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\end{bmatrix}, \\begin{bmatrix} 0 \\\\ 0 \\\\ 2 \\end{bmatrix}\\}$\n",
        "\n",
        "The unit vector in G which is orthogoal  to F is given by: _______\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lijd4TFjarh1"
      },
      "source": [
        "---\n",
        "Ans (explanation optional)\n",
        "\n",
        "So, G is essentially the 3D space and F is a plane in this space.\n",
        "\n",
        "We can just take cross product and find the unit vector.\n",
        "\n",
        "$\\implies \\frac{1}{\\sqrt{3}}\\begin{bmatrix} -1 \\\\ -1 \\\\ 1 \\end{bmatrix}$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 58,
      "metadata": {
        "id": "d78WCmeZQmpT"
      },
      "outputs": [],
      "source": [
        "F_basis = np.array([[1, 0, 1], [0, 1, 1]])\n",
        "G_basis = np.array([[1, 0, 0], [0, 1, 0], [0, 0, 2]])\n"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "include_colab_link": true,
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "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.9.19"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}