practicals/Maths_For_ML_English_Prac.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "m2s4kN_QPQVe"
      },
      "source": [
        "# **The Mathematical Basics of Machine Learning: A Beginner's Adventure**\n",
        "\n",
        "<!-- I've hosted the image on my own google drive, this embed link is possibly a bit brittle. The image is here: https://drive.google.com/file/d/15S_hS_3Hil_zuJQwWqquOa0RwfXNSBDM/ and the embedding code comes from here\n",
        "https://www.labnol.org/embed/google/drive/\n",
        "-->\n",
        "<img src=\n",
        "\"https://lh3.googleusercontent.com/drive-viewer/AITFw-x2E9J_9vDgyiiiVWaqbF5eVDc2ULDTdHSfx9ggmhnHwBokyFI6M4H5H3wfoOogWtmOPKvB0LfFP_mapLkDFRVPltg5=s2560\"\n",
        "width=\"60%\" />\n",
        "\n",
        "### *Before you start*\n",
        "Use this link to access the practical, then save a personal copy before starting work.\n",
        "\n",
        "<a href=\"https://colab.research.google.com/github/deep-learning-indaba/indaba-pracs-2023/blob/main/practicals/Maths_For_ML_English_Prac.ipynb\" target=\"_parent\">\n",
        "<img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/>\n",
        "</a>\n",
        "\n",
        "© Deep Learning Indaba 2023. Apache License 2.0.\n",
        "\n",
        "**Authors:** Geraud nangue Tasse, Bryn Elesedy, Tejumade Afonja, Ruan de Kock\n",
        "\n",
        "**Reviewers:** Marianne Monteiro, James Allingham, Abdel Mfougouon Njupoun, Kale-Ab Tessera\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4XVoSIi0YHVm"
      },
      "source": [
        "\n",
        "# Introduction\n",
        "\n",
        ">\"Machine learning is the latest in a long line of attempts to distill human\n",
        "knowledge and reasoning into a form that is suitable for constructing machines and engineering automated systems. As machine learning becomes\n",
        "more ubiquitous and its software packages become easier to use, it is natural and desirable that the low-level technical details are abstracted away\n",
        "and hidden from the practitioner. However, this brings with it the danger\n",
        "that a practitioner becomes unaware of the design decisions and, hence,\n",
        "the limits of machine learning algorithms.\" - Forward from the Mathematics of Machine Learning Book\n",
        "\n",
        "<!-- When embarking on a journey into the world of machine learning, it's crucial to grasp the fundamental mathematical underpinnings that form the bedrock of this exciting field. Imagine these mathematical concepts as the building blocks at the heart of the image displayed above. While not an exhaustive list, it provides a solid glimpse into the essential concepts that empower machine learning endeavors.  -->\n",
        "\n",
        "In this tutorial, our focus will be on several pivotal foundations: `linear algebra`, `analytical geometry`, `matrix decomposition`, and `vector calculus`. Although we won't delve into probabilities & distributions and optimization, it is important to note that they play a vital role in the more advanced applications of the examples we'll explore.\n",
        "\n",
        "Further, it is important to recognize the interconnectedness of these mathematical fields within the realm of machine learning. For instance, the optimization process intertwines seamlessly with vector calculus, a relationship evident when training neural networks through techniques like gradient descent.\n",
        "\n",
        "The figure above showcases the four pillars of machine learning, representing the primary model categories: `regression`, `classification`, `dimensionality reduction`, and `density estimation`. While you might be familiar with <font color='green'>`Regression`</font> and <font color='orange'>`Dimensionality Reduction`</font>, all four of these pillars are integral to the broader landscape of data science. Join us in unraveling the mathematical essence that drives machine learning forward."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Qgx1eK2ZbUqe"
      },
      "source": [
        "# Motivation\n",
        "\n",
        "**Why is the underlying mathematics important to you?**\n",
        "> \"Machine learning builds upon the language of mathematics to express\n",
        "concepts that seem intuitively obvious but that are surprisingly difficult\n",
        "to formalize. Once formalized properly, we can gain insights into the task\n",
        "we want to solve.\" - Foreword from the Mathematics of Machine Learning book\n",
        "\n",
        "In the modern era there are plethora of tools and libraries that do the heavy lifting for you. However,\n",
        "\n",
        "- A tool in and of itself, does not tell you:\n",
        " - Why a technique worked or did not;\n",
        " - What the technique actually does;\n",
        " - If a technique is likely to be efective for your problem instance;\n",
        " - The underlying assumptions that the technique uses;\n",
        "- Most off the shelf approaches are not state of the art\n",
        " - If you want to truly push the boundaries of a field, you need to innovate --  but without really understanding the foundational components, this is nearly impossible.\n",
        "\n",
        "\n",
        "Our tutorial aim to equip you with the foundational knowledge of mathematics for machine learning."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "W4DFxTC7bWpS"
      },
      "source": [
        "# How this Tutorial is Organized\n",
        "\n",
        "## Linear Algebra I <font color='green'>`Beginner`</font>\n",
        "\n",
        "### Overview\n",
        "This track gives a very basic introduction to linear algebra.\n",
        "We cover the basics of vectors and matrices (what they are and how to compute with them) along with dot products and the vector\n",
        "magnitude.\n",
        "We highlight the use of these topics in machine learning\n",
        "in the example of ridge regression. [Take me there!!](#scrollTo=dTbUZzMpogjx)\n",
        "\n",
        "#### Sections\n",
        "In this track you will cover the following topics:\n",
        "- [ ] Vectors\n",
        "- [ ] Matrices\n",
        "- [ ] The Dot Product\n",
        "- [ ] The Magnitude of a Vector\n",
        "- [ ] Example: Ridge Regression\n",
        "\n",
        "#### Prerequisites\n",
        "This track has almost no prerequisites apart from\n",
        "basic (high school) math.\n",
        "For the ridge regression example it will be helpful to know\n",
        "a little vector calculus, but it's not necessary.\n",
        "\n",
        "> <font color='red'>`Tip`</font> to track your progress, make sure to check the boxes as you finish with each topic by editing this cell and changing\n",
        "- [ ] ...\n",
        "- [x] ...\n",
        "\n",
        "## Linear Algebra II <font color='orange'>`Intermediate`</font>\n",
        "\n",
        "### Overview\n",
        "This track assume that you've got the basics covered and takes you through more advanced topics. [Take me there!!](#scrollTo=VxAke0QRa3zl)\n",
        "\n",
        "#### Sections\n",
        " - [ ] Orthonormal bases and orthogonal projections\n",
        " - [ ] Determinant, trace\n",
        " - [ ] Eigenvectors and eigenvalues\n",
        " - [ ] Eigendecomposition and diagonalisation\n",
        " - [ ] Principal component analysis (PCA)\n",
        "\n",
        "#### Prerequisites\n",
        "Be very comfortable with Linear Algebra I <font color='green'>`Beginner`</font>.\n",
        "\n",
        "<!-- We will cover the minimal mathematics for\n",
        "- <font color='green'>`Regression`</font>:\n",
        "<font color='green'>`Beginner`</font> `Section 1`\n",
        " - What is a vector, basic vector operations `Linear Algebra`\n",
        " - What is a matrix, basic matrix operations `Linear Algebra`\n",
        " - Norms and Inner products `Analytic Geometry`\n",
        " - Univariate differentiation `vector calculus`\n",
        " - Differentiating a multivariate function `vector calculus`\n",
        " - Taking a gradient and some basic gradient operations `vector calculus`\n",
        " - Linear regression `Example`\n",
        "\n",
        "- <font color='orange'>`Dimensionality Reduction`</font>: <font color='orange'>`Intermediate`</font> `Section 2`\n",
        " - Orthonormal bases and orthogonal projections `Analytic Geometry`\n",
        " - Determinant, trace `Matrix Decomposition`\n",
        " - Eigenvectors and eigenvalues `Matrix Decomposition`\n",
        " - Eigendecomposition and diagonalisation `Matrix Decomposition`\n",
        " - Principal component analysis (PCA) `Example` -->\n",
        "\n",
        "\n",
        "\n",
        "**Note**\n",
        "\n",
        "This practical has lots of hands-on exercises.\n",
        "Don't worry if you get stuck on something, it's all part of the\n",
        "learning process!\n",
        "If you feel that an exercise is taking you too long please\n",
        "feel free to return to it later or ask a tutor for help."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RXdF3bj33RWu"
      },
      "source": [
        "# Additional Resources\n",
        "\n",
        "For other practicals from the Deep Learning Indaba, please visit [here](https://github.com/deep-learning-indaba/indaba-pracs-2023).\n",
        "\n",
        "The material for this practical is based on the book\n",
        "[Mathematics for Machine Learning](https://mml-book.github.io).\n",
        "We recommend that you consult the book for more details and a deeper dive on each topic.\n",
        "For the Linear Algebra I and Linear Algebra II tracks, see\n",
        "chapters 2, 3 and 4.\n",
        "For a background in vector calculus, see chapter 5.\n",
        "\n",
        "Throughout the sections we will highlight additional resources.\n",
        "Often we will recommend videos or lessons from\n",
        "3Blue1Brown as these can be good for intuition.\n",
        "These videos follow a different order to our tracks, so\n",
        "you might run into concepts that we've\n",
        "not introduced yet.\n",
        "When that happens either read ahead in this practical or see the relevant 3Blue1Brown lesson\n",
        "[here](https://www.3blue1brown.com/topics/linear-algebra) (e.g. basis vectors are mentioned in Chapter 2 but don't appear in Linear Algebra I).\n",
        "\n",
        "\n",
        "\n",
        "More generally, there are many good resources for linear algebra:\n",
        "\n",
        "- The [3Blue1Brown Course](https://www.3blue1brown.com/topics/linear-algebra)\n",
        "- Gilbert Strang (famous for teaching Linear Algebra)\n",
        "  - [Videos of Gilbert Strang's Lectures](https://www.youtube.com/playlist?list=PL49CF3715CB9EF31D)\n",
        "  - [Introduction to Linear Algebra (book), Gilbert Strang](https://math.mit.edu/~gs/linearalgebra/)\n",
        "- For anything you could ever want to know about matrices, try the book _Matrix Analysis by Johnson and Horn_. (A great reference).\n",
        "- For a more mathematical viewpoint you can use course notes,\n",
        "such as [these ones from the Cambridge maths tripos](https://dec41.user.srcf.net/notes). Relevant courses are _Vectors and Matrices_ and _Linear Algebra_.\n",
        "  \n",
        "Videos can be nice for intuition, but if you want to deeply understand something you'll need to use the lecture courses or the books as well. In particular you'll need to work out examples and do the associated exercises.\n",
        "In comparision with the videos, the lecture notes and books will be more self-contained and more useful in the long run, but probably more challenging and may offer less intuition.\n",
        "As always, you get out what you put in.\n",
        "\n",
        "<!-- # # @title **Paths to follow:** What is your level of experience in the topics presented in this notebook? (Run Cell)\n",
        "# experience = \"beginner\" #@param [\"beginner\", \"intermediate\", \"advanced\"]\n",
        "\n",
        "# sections_to_follow=\"\"\n",
        "\n",
        "# if experience == \"beginner\":\n",
        "#   sections_to_follow=\"Introduction -> 1.1 Subsection -> 2.1 Subsection -> Conclusion -> Feedback\"\n",
        "# elif experience == \"intermediate\":\n",
        "#   sections_to_follow=\"Introduction -> 1.2 Subsection -> 2.2 Subsection -> Conclusion -> Feedback\"\n",
        "# elif experience == \"advanced\":\n",
        "#   sections_to_follow=\"Introduction -> 1.3 Subsection -> 2.3 Subsection -> Conclusion -> Feedback\"\n",
        "\n",
        "# print(f\"Based on your experience, it is advised you follow these -- {sections_to_follow} sections. Note this is just a guideline.\") -->"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eISLDyPq8rWB"
      },
      "source": [
        "# Install and import required packages. (Run Me)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "OshUoD5Y8hk7"
      },
      "outputs": [],
      "source": [
        "# Install and import anything required. Capture hides the output from the cell.\n",
        "import jax\n",
        "import jax.numpy as jnp\n",
        "\n",
        "import matplotlib.pyplot as plt\n",
        "import numpy as np\n",
        "\n",
        "import timeit\n",
        "import matplotlib as mpl\n",
        "mpl.use('Agg')\n",
        "plt.style.use('fivethirtyeight')\n",
        "from ipywidgets import interact\n",
        "import sklearn.datasets\n",
        "from sklearn.datasets import load_digits\n",
        "from sklearn.datasets import fetch_openml"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dTbUZzMpogjx"
      },
      "source": [
        "# Linear Algebra I <font color='green'>`Beginner`</font>\n",
        "\n",
        "What you will learn in this section: Vectors, Basics of Matrices, The Dot Product, The Magnitude of a Vector, and a Ridge Regression example.\n",
        "\n",
        "> <font color='red'>`Tip`</font> you can hide the sections that you are not currently studying by toggling the collapse button from $\\blacktriangledown$ to $\\blacktriangleright$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "alEg193g3RWw"
      },
      "source": [
        "## Vectors\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5pM9PjlJhEDs"
      },
      "source": [
        "Numerical arrays are the fundamental data structure in most machine learning code.\n",
        "Intuitively, a vector is a column array of numbers\n",
        "that comes with algebraic operations\n",
        "such as addition and subtraction (with other arrays of the same shape)\n",
        "and multiplication by a scalar (multiplying all the elements in the array\n",
        "by the same number).\n",
        "\n",
        "Vectors appear very regularly in both theoretical and applied machine learning.\n",
        "The subject of linear algebra, which concerns special collections of vectors called vector spaces and transformations between them, is foundational not\n",
        "only to machine learning, but also mathematics and the physical sciences.\n",
        "\n",
        "Vectors are used in machine learning to represent and manipulate data.\n",
        "Vectors are commonly used as a collection of input features for a model, such\n",
        "as\n",
        "`(square footage, number of bathrooms, age of property, ...)`\n",
        "in a house price regression task.\n",
        "Vectors are also used to contain data representations, such as in modern language models or the classic `Word2Vec`.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F_MV7s_fsJ65"
      },
      "source": [
        "### Vectors as Computational Arrays"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ww6ebdJUYQy1"
      },
      "source": [
        "The simplest working definition of a vector is a column (1-d) array of numbers such as\n",
        "$$\\begin{pmatrix} 1\\\\4\\\\2\\end{pmatrix}\n",
        "\\quad \\text{ or } \\quad\n",
        "\\begin{pmatrix} 0.5\\\\6\\\\7\\\\4.9\\\\2.1\\end{pmatrix}$$\n",
        "\n",
        "The _dimension_ of the vector is simply the length of the array.\n",
        "So above, the vectors have dimensions 3 and 5 respectively.\n",
        "We will write vectors with a boldface font, so\n",
        "$\\mathbf{a}, \\mathbf{b}, \\mathbf{c},$ etc.\n",
        "\n",
        "The elements of the array are called the _components_ of the vector.\n",
        "We write $\\mathbf{a}_i$ for the i<sup>th</sup> component of the vector\n",
        "$\\mathbf{a}$. So $\\mathbf{a}_2$ is the number in the 2<sup>nd</sup> position\n",
        "(from the top) in the array. This is 4 (in the first example) and 6 (in the second example above).\n",
        "By convention indexing starts from 1 in math but starts from 0 in Python (sorry!)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "R9epJ1dtYTLs"
      },
      "source": [
        "\n",
        "In this practical we will specifically consider real vectors, which are arrays whose elements are real numbers.\n",
        "Any two real vectors of the same dimension can be added to or subtracted from one another by adding or subtracting the corresponding elements, just like arrays.\n",
        "For instance,\n",
        "$$\n",
        "\\begin{pmatrix} 1\\\\4\\\\2\\end{pmatrix} +\n",
        "\\begin{pmatrix} 3\\\\1\\\\6\\end{pmatrix}\n",
        "=\n",
        "\\begin{pmatrix} 4\\\\5\\\\8\\end{pmatrix}\n",
        "$$\n",
        "and\n",
        "$$\n",
        "\\begin{pmatrix} 3\\\\1\\\\6\\end{pmatrix}\n",
        "-\n",
        "\\begin{pmatrix} 1\\\\4\\\\2\\end{pmatrix}\n",
        "=\n",
        "\\begin{pmatrix} 2\\\\-3\\\\4\\end{pmatrix}\n",
        "$$\n",
        "However, the dimensions must match. The following expression makes no sense mathematically\n",
        "$$\n",
        "\\begin{pmatrix} 1\\\\3\\\\2\\end{pmatrix} +\n",
        "\\begin{pmatrix} 3\\\\1\\\\6\\\\4\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "Also, any real vector can be multiplied by a real number to get another real vector, where the multiplication happens element-wise. For instance\n",
        "$$\n",
        "2 \\times \\begin{pmatrix} 1\\\\4\\\\2\\end{pmatrix}\n",
        "=\n",
        "\\begin{pmatrix} 2\\\\8\\\\4\\end{pmatrix}\n",
        "$$\n",
        ">In the context of linear algebra, numbers are often called _scalars_ and the above calculation is called _scalar multiplication_.\n",
        "\n",
        "The set of all real vectors of dimension $n$ is written $\\mathbb{R}^{n}$, i.e., the set of all $n$-tuples of real numbers.\n",
        "\n",
        "**Note**:\n",
        "From now on, unless stated otherwise, the word _vector_ will refer specifically to real vectors."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iWzKh_lcYfEy"
      },
      "source": [
        "#### Examples in Code\n",
        "In jax we can represent vectors using `jnp.array`. The following represents the\n",
        "vector\n",
        "$$\\mathbf{a} = \\begin{pmatrix} 1\\\\4\\\\2\\end{pmatrix}$$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DIAljWZxdAJo",
        "outputId": "cb04af9e-1a2f-4750-eabb-62d7ba7c85c0"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([1, 4, 2], dtype=int32)"
            ]
          },
          "execution_count": 20,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "a = jnp.array([1, 4, 2])\n",
        "a"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "l1Kg-mwVND4W"
      },
      "source": [
        "Elements of the vectors can be accessed using square brackets.\n",
        "Recall that indexing vector entries in math typically starts from 1, but indexing arrays\n",
        "in Python starts from 0, so be careful!"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "iDJ6hXrWNDDG",
        "outputId": "e60600f5-8cdd-4703-9522-95fbfd603209"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "1\n"
          ]
        }
      ],
      "source": [
        "# Print the first component of a. In math this component would be written a_1\n",
        "print(a[0])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8wp0rMj1cfzp"
      },
      "source": [
        "Their dimension can be calculated using `len` or `.shape`"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XTLHHVOecmL6",
        "outputId": "4d1a3897-08b0-473c-8362-b6878c0cb1f4"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "3\n",
            "(3,)\n"
          ]
        }
      ],
      "source": [
        "print(len(a))\n",
        "print(a.shape)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mFmHDsfJdkS-"
      },
      "source": [
        "Addition, subtraction and scalar multiplication can all be done via standard python operations."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "33dnrs8JdjuA",
        "outputId": "420e19f0-b8c3-463c-f6ac-ed9e845275c4"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([4, 5, 8], dtype=int32)"
            ]
          },
          "execution_count": 23,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "a = jnp.array([1, 4, 2])\n",
        "b = jnp.array([3, 1, 6])\n",
        "a + b"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "G_-WtsJwebG3",
        "outputId": "be53c85d-0225-4df7-f235-5cfe5958ec74"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([2, 8, 4], dtype=int32)"
            ]
          },
          "execution_count": 24,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "2 * a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ZdCx7RQTeT9i",
        "outputId": "366490c4-cb25-41dd-b34a-d2b10e8d0113"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([ 2, -3,  4], dtype=int32)"
            ]
          },
          "execution_count": 25,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "b - a"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Cbxhdrjbekhk"
      },
      "source": [
        ">If the dimensions don't match then jax will throw an error, but this touches on a computaional topic known as _broadcasting_ which is beyond the scope of this practical."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sNeAWDXPfKvo"
      },
      "source": [
        "#### Exercise\n",
        "\n",
        "Let\n",
        "$$\n",
        "\\mathbf{a} = \\begin{pmatrix} 1\\\\1\\\\0.9\\\\0.6\\end{pmatrix}\n",
        "\\quad\\text{ and }\\quad\n",
        "\\mathbf{b}\n",
        "=\n",
        "\\begin{pmatrix} 0\\\\1\\\\3\\\\ 2.718\\end{pmatrix}\n",
        "$$\n",
        "Use jax to calculate $3\\mathbf{a} - \\mathbf{b}$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "LeNcOU7ZfFq_"
      },
      "outputs": [],
      "source": [
        "# Place your answer here"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1UxBl5KcwrfD"
      },
      "source": [
        "#### Solution"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rtxiu2kywt7D",
        "outputId": "5ca79e4f-a7ce-4dbf-aeb8-06c3996b5c2d"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([ 3.        ,  2.        , -0.3000002 , -0.91799986], dtype=float32)"
            ]
          },
          "execution_count": 6,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "a = jnp.array([1., 1., 0.9, 0.6])\n",
        "b = jnp.array([0., 1., 3., 2.718])\n",
        "\n",
        "answer = 3 * a - b\n",
        "answer"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Krg2R2KgcuSN"
      },
      "source": [
        "### Vectors as Geometrical Objects [Optional]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6ueJCQa7kKuF"
      },
      "source": [
        "In school, you may have been introduced to vectors as geometrical objects representing a directed line from the origin to a position in space.\n",
        "These geometrical vectors can be represented as arrays by expressing\n",
        "their components relative to a co-ordinate system. For instance,\n",
        "$$\\begin{pmatrix} 1\\\\4\\\\2\\end{pmatrix}$$\n",
        "represents a directed ray from the origin to the point with co-ordinates $x=1,y=4,z=2$.\n",
        "The vector operations of addition, subtraction and scalar multiplication\n",
        "have the geometrical meaning shown in the figure below.\n",
        "\n",
        "<img src=\n",
        "\"https://lh3.googleusercontent.com/drive-viewer/AITFw-zIgBFg0YE3LHIMjTbnv-gXsY9wHuKggmrJ3wl9exGr4xE5Z7bo__3gypuiuSvZJw4lrRgNGMWiiNyez-A8YUivC1ns=s1600\"\n",
        "width=\"30%\" />\n",
        "\n",
        "Not all vectors can be thought of this way, but almost all of the cases you cover in machine learning are amenable to this interpretation."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rKOQH-S7sUyC"
      },
      "source": [
        "### Mathematical Definition: Vector Spaces [Optional]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fC2KoTPUWdh8"
      },
      "source": [
        "Mathematically, a vector is defined to be any element of a _vector space_.\n",
        "A (real) vector space $V$ is a set of objects with two operations, vector addition and scalar multiplication.\n",
        "\n",
        "Vector addition must satisfy, for all $\\mathbf{a}, \\mathbf{b}, \\mathbf{c} \\in V$\n",
        "- closure: $\\mathbf{a} + \\mathbf{b} \\in V$\n",
        "- commutativity: $\\mathbf{a} + \\mathbf{b} = \\mathbf{b} + \\mathbf{a}$\n",
        "- associativity: $\\mathbf{a} + (\\mathbf{b} + \\mathbf{c}) = (\\mathbf{a} + \\mathbf{b}) + \\mathbf{c}$\n",
        "- identity: There is a zero-vector $\\mathbf{0}$ such that for all $\\mathbf{a}\\in V$,\n",
        "$\\mathbf{a} + \\mathbf{0} = \\mathbf{a}$.\n",
        "- inverse: For all $\\mathbf{a}\\in V$ there's a vector $\\mathbf{-a} \\in V$\n",
        "such that $\\mathbf{a} + \\mathbf{-a} = \\mathbf{0}$.\n",
        "\n",
        "Scalar multiplication must satisfy, for all $\\mathbf{a}, \\mathbf{b} \\in V$\n",
        "and for all $\\lambda, \\mu \\in \\mathbb{R}$\n",
        "- $\\lambda(\\mathbf{a}+\\mathbf{b}) = \\lambda \\mathbf{a} + \\lambda \\mathbf{b}$\n",
        "- $(\\lambda+ \\mu)\\mathbf{a} = \\lambda \\mathbf{a} + \\mu \\mathbf{a}$\n",
        "- $\\lambda(\\mu \\mathbf{a}) = (\\lambda \\mu)\\mathbf{a}$\n",
        "- $1 \\mathbf{a} = \\mathbf{a}$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YEWAi5p9snZO"
      },
      "source": [
        "#### Examples of Vector Spaces"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "er_anGbkYs63"
      },
      "source": [
        "\n",
        "- The set of all $n$-tuples of real numbers $\\mathbb{R}^n$ with element-wise addition and multiplication by real scalars.\n",
        "- The set of all degree $n$ polynomials with real coefficients\n",
        "$$f(x) = a_0 + a_1 x + a_2 x^2 + \\cdots + a_n x^n$$\n",
        "is a vector space. The polynomial $f$ can be represented by\n",
        "$$\n",
        "\\begin{pmatrix}\n",
        "a_0\\\\\n",
        "a_1\\\\\n",
        "a_2\\\\\n",
        "\\vdots\\\\\n",
        "a_n\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "- The set of all functions $f: \\mathcal{X}\\to \\mathbb{R}$ for any finite set $\\mathcal{X}$.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QcXA-_e6sy-V"
      },
      "source": [
        "#### Limitations of the Array Intuition\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_KyO8VbeUPdw"
      },
      "source": [
        "\n",
        "_If this section is confusing to you, please ignore it._\n",
        "\n",
        "_It's only here to make you aware that,\n",
        "although the array-based understanding of vectors we use is useful,\n",
        "it has it's limits._"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PfFrXosRYuFE"
      },
      "source": [
        "The definition of a vector as a column array of numbers is sufficient\n",
        "for most of modern machine learning.\n",
        "The geometric intuition as an arrow from the origin is also useful.\n",
        "Indeed, these notions are probably what many\n",
        "scientists have in mind when they think of the word 'vector'.\n",
        "\n",
        ">However, the mathematical definition of a vector allows for\n",
        "vectors that _cannot_ be written as column arrays of numbers.\n",
        "A vector space in which every vector can be represented as a column\n",
        "array of numbers is called a _finite dimensional vector space_.\n",
        "A vector space where you cannot do this is called an\n",
        "_infinite dimensional vector space_.\n",
        "\n",
        "We won't cover infinite dimensional vector spaces in this practical as they require\n",
        "more advanced math, but they are of fundamental importance in mathematics, physics and even machine learning.\n",
        "In particular, a proper understanding of kernel methods requires\n",
        "encountering these vectors. An example of an infinite dimensional vector\n",
        "space is the set of all functions\n",
        "$f: \\mathcal{X}\\to \\mathbb{R}$ for an infinite set $\\mathcal{X}$.\n",
        "\n",
        "Apart from the example we just gave, all vector spaces in\n",
        "this practical will be finite dimensional."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "W8oJWk2VtS6V"
      },
      "source": [
        "#### Exercises\n",
        "\n",
        "_These exercises are focused on understanding the mathematical definition of a vector space. They will help your understanding in the long run but feel free to skip them for now if you like._\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "na7LS6JxaJfN"
      },
      "source": [
        "\n",
        "1. Convince yourself that the computational intuition of vectors as arrays of real numbers is a vector space by the above definition.\n",
        "  - Hint: check that the rules that we gave for addition, subtraction and scalar multiplication of arrays satisfies all of the rules in the definition of a vector spaces\n",
        "\n",
        "2. Verify that the set of all degree $n$ polynomials with real coefficients is a vector space.\n",
        "  - Hint: Show that the representation of a polynomial as an array given in the above examples is one-to-one, meaning that every degree $n$ polynomial has exactly one array representation and\n",
        "  every array representation corresponds to a polynomial. Then apply\n",
        "  exercise 1.\n",
        "\n",
        "3. Prove that $0 \\mathbf{a} = \\mathbf{0}$ for any vector $\\mathbf{a}$\n",
        "\n",
        "4. Use the vector space rules to prove that $(-1) \\mathbf{a} = \\mathbf{-a}$.\n",
        "  - Hint: Prove that multiplying $\\mathbf{a}$ by the scalar $-1$ results in the vector $\\mathbf{b}$ such that $\\mathbf{a} + \\mathbf{b} = 0$ and show that there is only one such $\\mathbf{b}$.\n",
        "\n",
        "5. Use the axioms above to prove that $\\lambda \\mathbf{0} = \\mathbf{0}$ for all\n",
        "$\\lambda \\in \\mathbf{R}$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZA_fjFj8btnX"
      },
      "source": [
        "#### Solutions"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-atas5vsbvOv"
      },
      "source": [
        "3. We have\n",
        "$$\n",
        "0\\mathbf{a} + 0\\mathbf{a} = (0+0) \\mathbf{a} = 0\\mathbf{a}\n",
        "$$\n",
        "so subtracting $0\\mathbf{a}$ from both sides gives\n",
        "$$\n",
        "0\\mathbf{a} = \\mathbf{0}\n",
        "$$\n",
        "\n",
        "4.\n",
        "For the purposes of this exercise, we will say that any vector\n",
        "$\\mathbf{b}$ which satisfies\n",
        "$$\n",
        "\\mathbf{a} + \\mathbf{b} = 0\n",
        "$$\n",
        "is an _inverse for \\mathbf{a}_.\n",
        "We will first show that inverses are unique.\n",
        "Suppose $\\mathbf{c}$ is another inverse for $\\mathbf{a}$, so\n",
        "$$\n",
        "\\mathbf{a} + \\mathbf{c} = 0\n",
        "$$\n",
        "Subtracting the equations gives\n",
        "$$\n",
        "\\mathbf{b} - \\mathbf{c} = 0\n",
        "$$\n",
        "so $\\mathbf{b} = \\mathbf{c}$ and inverses are unique.\n",
        "Now we will show that $(-1)\\mathbf{a}$ is an inverse for $\\mathbf{a}$,\n",
        "and the uniqueness of inverses will imply that\n",
        "$(-1) \\mathbf{a}= \\mathbf{-a}$.\n",
        "This is done by:\n",
        "$$\n",
        "\\mathbf{a} + (-1) \\times \\mathbf{a} = (1 + (- 1))\\mathbf{a} = \\mathbf{0}\n",
        "$$\n",
        "and the proof is complete.\n",
        "\n",
        "5. This is similar to exercise 3. We have\n",
        "$$\n",
        "\\lambda \\mathbf{0}\n",
        "=\\lambda (\\mathbf{0} + \\mathbf{0}) = \\lambda \\mathbf{0} + \\lambda \\mathbf{0}\n",
        "$$\n",
        "then subtract $\\lambda \\mathbf{0}$ from both sides."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Yu5mhS79tZvX"
      },
      "source": [
        "### Suggested Resources"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NxFtdhaLeIqx"
      },
      "source": [
        "\n",
        "- [Mathematics for Machine Learning Book](https://mml-book.github.io/book/mml-book.pdf) Chapter 1 gives a really nice intro to these viewpoints as well\n",
        "- [3Blue1Brown Lesson on Vectors](https://www.3blue1brown.com/lessons/vectors) is good for building intuition\n",
        "- [3Blue1Brown Video on Abstract Vector Spaces](https://www.3blue1brown.com/lessons/abstract-vector-spaces) for intuition on a more mathematical perspective\n",
        "-  Chapter 2 of the Cambridge course [Vectors and Matrices](https://dec41.user.srcf.net/notes/IA_M/vectors_and_matrices.pdf) for more advanced reading on the basics\n",
        "- Chapter 1 of the Cambridge course [Linear Algebra](https://dec41.user.srcf.net/notes/IB_M/linear_algebra.pdf) for a more mathematical viewpoint"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "S5WpNdur3RW1"
      },
      "source": [
        "## Matrices\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "79502w53tlzL"
      },
      "source": [
        "### Matrices as Computational Arrays"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IYFFbUyHjwY-"
      },
      "source": [
        "An $m\\times n$ real matrix is simply an $(m\\times n)$-dimensional array of real numbers\n",
        "$$\n",
        "\\begin{pmatrix}\n",
        "  a_{11} & a_{12} & \\dots \\\\\n",
        "  \\vdots & \\ddots & \\\\\n",
        "  a_{m1} &        & a_{mn}\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "The set of all $m\\times n$ real matrices is often written $\\mathbb{R}^{m\\times n}$ or $\\text{Mat}_{m\\times n}(\\mathbb{R})$. For the rest of this practical, we will just say matrix instead of real matrix.\n",
        "It is called an $m\\times n$ matrix because the array has $m$ rows and $n$ columns.\n",
        "\n",
        "> <font color='grey'>`Side Note`</font> In some textbooks, this is referred to as $n\\times m$ matrix which means it has $n$ rows, and $m$ columns. This can sometimes be confusing especially for <font color='green'>`beginners`</font>. So, it is important to understand what exactly the symbol is representing in given context by consulting the definition provided by the author. Okay, back to the tutorial.\n",
        "\n",
        "We call the number $a_{ij}$ _the $(i, j)$-component of the matrix_. The above matrix has _components_ $a_{ij}$ for $i=1, \\dots, m$ and $j=1, \\dots, n$.\n",
        "We write matrices with boldface capital letters,\n",
        "for example\n",
        "$$\n",
        "\\mathbf{A}\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "  1 & 3 \\\\\n",
        "  2 & 4 \\\\\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "The components of any matrix $\\mathbf{A}$ will often be written as $\\mathbf{A}_{ij}$.\n",
        "\n",
        "A full horizontal $(\\rightarrow)$ slice of entries of a matrix is called a _row_, while\n",
        "a full vertical ($\\downarrow$) slice is called a _column_.\n",
        "We call a $(1\\times n)$-dimensional matrix a _row vector_ and\n",
        "an $(n\\times 1)$-dimensional matrix a _column vector_.\n",
        "An $(n\\times n)$-dimensional matrix is a _square matrix_ (because the array of numbers forms a square). For example, matrix $\\mathbf{A}$ above has 2 rows and 2 columns. It's first row has components $[1, 3]$, and it's second column has components $[3, 4]$.\n",
        "\n",
        "Matrices are a very common method of representing data in machine learning and statistics.\n",
        "Very often, one will represent the features for each training example\n",
        "by a vector.\n",
        "Suppose we have $m$ examples each with $n$ features, so for each example we have a dimension $n$ vector.\n",
        "These vectors can be stacked as rows into an $m\\times n$ matrix called the\n",
        "_design matrix_.\n",
        "This is a very common approach, for instance in linear regression.\n",
        "\n",
        "Matrices can be added and subtracted element-wise just like vectors as long\n",
        "as the matrices have the same dimensions\n",
        "$$\n",
        "\\begin{pmatrix}\n",
        "  1 & 3 \\\\\n",
        "  2 & 4 \\\\\n",
        "  6 & 8 \\\\\n",
        "\\end{pmatrix}\n",
        "+\n",
        "\\begin{pmatrix}\n",
        "  8 & -2 \\\\\n",
        "  2 & 0.5 \\\\\n",
        "  -3 & 0 \\\\\n",
        "\\end{pmatrix}\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "  9 & 1 \\\\\n",
        "  4 & 4.5 \\\\\n",
        "  3 & 8 \\\\\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "and they can also be multiplied by real scalars\n",
        "$$\n",
        "3 \\times \\begin{pmatrix}\n",
        "  1 & 3 \\\\\n",
        "  2 & 4 \\\\\n",
        "\\end{pmatrix}\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "  3 & 9 \\\\\n",
        "  6 & 12 \\\\\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "In components, if $\\mathbf{A}$ and $\\mathbf{B}$ are both $m\\times n$ matrices\n",
        "then $\\mathbf{A}+\\mathbf{B}$ is an $m\\times n$ matrix with\n",
        "$$\n",
        "(\\mathbf{A}+\\mathbf{B})_{ij}\n",
        "=\n",
        "\\mathbf{A}_{ij} +\\mathbf{B}_{ij}\n",
        "$$\n",
        "and for any scalar $\\lambda \\in \\mathbb{R}$, $\\lambda \\mathbf{A}$ is an\n",
        "$m\\times n$ matrix with components\n",
        "$$\n",
        "(\\lambda \\mathbf{A})_{ij}\n",
        "= \\lambda \\times \\mathbf{A}_{ij}\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ePb2cjiPiT5f"
      },
      "source": [
        "### Representing Matrices in Jax\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NPV40ExRZFmZ"
      },
      "source": [
        "Matrices can be represented using `jax` arrays just like vectors"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "AovFAPzXiTSF",
        "outputId": "4a34de62-4d2e-4c1a-c1c6-492ebb69229f"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[1, 3],\n",
              "       [2, 4],\n",
              "       [6, 8]], dtype=int32)"
            ]
          },
          "execution_count": 7,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "jnp.array([[1, 3], [2, 4], [6, 8]])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1T2Bqu26troj"
      },
      "source": [
        "### Exercises"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Hik2EClfikHg"
      },
      "source": [
        "\n",
        "1. Let\n",
        "$$\n",
        "\\mathbf{A} =\n",
        "\\begin{pmatrix}\n",
        "  1 & 3 \\\\\n",
        "  2 & 4 \\\\\n",
        "\\end{pmatrix}\n",
        "\\quad\\text{ and }\\quad\n",
        "\\mathbf{B} =\n",
        "\\begin{pmatrix}\n",
        "  8 & -2 \\\\\n",
        "  2 & 0.5 \\\\\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "Use `jax` to calculate $2\\mathbf{A} - B$.\n",
        "\n",
        "2. [Optional, mathy]: Show that the set of all $m\\times n$ real matrices is a vector space according to the mathematical definition."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "LdSUPT4DimMp"
      },
      "outputs": [],
      "source": [
        "# Place your answer to exercise 1 here"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JVIwuO3qxS18"
      },
      "source": [
        "### Solution to exercise 1"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-T6BspQqxXkQ",
        "outputId": "1a1909d2-1657-4996-8c07-76f21a298dfa"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[-6. ,  8. ],\n",
              "       [ 2. ,  7.5]], dtype=float32)"
            ]
          },
          "execution_count": 7,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "A = jnp.array([[1, 3], [2, 4]])\n",
        "B = jnp.array([[8, -2], [2, 0.5]])\n",
        "\n",
        "answer = 2 * A - B\n",
        "answer"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_O-Jj77VtySj"
      },
      "source": [
        "### Matrix-Matrix Multiplication"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ml_SdEnms0iH"
      },
      "source": [
        "\n",
        "Multiplication of matrices is defined as follows.\n",
        "Let $\\mathbf{A}$ be an $m\\times k$ matrix and let $\\mathbf{B}$ be an $k\\times n$ matrix, multiplying $\\mathbf{B}$ by $\\mathbf{A}$ from the left produces\n",
        "an $m\\times n$ matrix $\\mathbf{C}$\n",
        "$$\n",
        "\\mathbf{C} = \\mathbf{A}\\mathbf{B}\n",
        "$$\n",
        "which has components\n",
        "$$\n",
        "\\mathbf{C}_{ij} = \\sum_{l=1}^k \\mathbf{A}_{il}\\mathbf{B}_{lj}\n",
        "$$\n",
        "\n",
        "Here's an example\n",
        "$$\n",
        "\\begin{pmatrix}\n",
        "0 & 1 & 2 & 3 \\\\\n",
        "4 & 5 & 6 & 7 \\\\\n",
        "\\end{pmatrix}\n",
        "\\begin{pmatrix}\n",
        "1 & 1 & 1  \\\\\n",
        "0 & 1 & 1  \\\\\n",
        "0 & 0 & 1  \\\\\n",
        "1 & 0 & 1  \\\\\n",
        "\\end{pmatrix}\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "(0\\times1) + (1\\times0) + (2\\times0) + (3\\times1) & ... & ... \\\\\n",
        "(4\\times1) + (5\\times0) + (6\\times0) + (7\\times1) & ... & ...\n",
        "\\end{pmatrix}\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "3 & 1 & 6 \\\\\n",
        "11 & 9 & 22\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "Multiplication is only defined when the neighbouring dimensions of the two matrices match.\n",
        "The above case is valid because second dimension of $\\mathbf{A}$ is $k$ and so is the first dimension of $\\mathbf{B}$.\n",
        "\n",
        ">Even though we can multiply matrices $\\mathbf{A}\\mathbf{B}$, the product $\\mathbf{B}\\mathbf{A}$ is _not defined (i.e not possible) unless $m=n$_. More details about this in Commuting Matrices subsection below.\n",
        "\n",
        "Also note that the dimension of the resulting matrix is not necessarily the\n",
        "same as the dimension of either of the arguments.\n",
        "\n",
        "<img src=\n",
        "\"https://lh3.googleusercontent.com/drive-viewer/AITFw-zPXr2BVQaeIMGXkD9QURdyLS8BCDsP6Yx4L0KgiRh05tKsiOTJ6DmDmDhZiZnDJS0KlCHKTQ0mfUM7Mn88RdILeFIMDw=s2560\"\n",
        "width=\"30%\"  class=\"center\"/>\n",
        "\n",
        "You might find the following images helpful for visualisation.\n",
        "If you've not seen matrix multiplication before, it will quickly become\n",
        "easy once you've practised some examples.\n",
        "\n",
        "<img src=\"\n",
        "https://www.mathwarehouse.com/algebra/matrix/images/matrix-multiplication/how-to-multiply-2-matrices-demo.gif\"\n",
        "width=\"50%\"  class=\"center\"/>\n",
        "\n",
        "<img src=\"\n",
        "https://lh3.googleusercontent.com/drive-viewer/AITFw-ykpJ8ShB0EfJeuzB9xqZsmzSEAZUbPbAFfTvcctojVcRgssi1wYHMvjLL2qyMBU_l2qPtxs3XMQEEf6C312kVgX2Hd=s2560\"\n",
        "width=\"50%\"  class=\"center\"/>\n",
        "\n",
        "<img src=\n",
        "\"https://assets.tivadardanka.com/2022_matrix_multiplication_def_01_1b4c6d7211.png\n",
        "\"\n",
        "width=\"75%\"  class=\"center\"/>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "idLN7CTvhp_2"
      },
      "source": [
        "#### Multiplying Matrices in `jax`\n",
        "\n",
        "Matrix multiplication can be calculated using `jnp.matmul` or the `@` binary operator.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7kLBCsJZjDJU"
      },
      "source": [
        "**Note**\n",
        "\n",
        "The symbol `@` has another (compeltely different!) use in python, which is to do with _decorators_.\n",
        "Don't worry about this in this practical, but it's worth knowing to avoid confusion."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "70kD4qcRiN9H",
        "outputId": "2f9df6bd-9166-4c5c-e75a-450d323721eb"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[19, 22],\n",
              "       [43, 50]], dtype=int32)"
            ]
          },
          "execution_count": 7,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "A = jnp.array([[1, 2], [3, 4]])\n",
        "B = jnp.array([[5, 6], [7, 8]])\n",
        "jnp.matmul(A, B)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "f8yPQbBEjWOz",
        "outputId": "aed8e76d-07c9-4a7b-e131-9e3384b05dd6"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[19, 22],\n",
              "       [43, 50]], dtype=int32)"
            ]
          },
          "execution_count": 8,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "A @ B"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jzKvwjbdt9Dj"
      },
      "source": [
        "#### Algebraic Properties"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "J2Z9lVfogQM-"
      },
      "source": [
        "Matrix multiplication is always _associative_. Meaning that, provided the dimensions are appropriate,\n",
        "$$\n",
        "(\\mathbf{AB})\\mathbf{C}\n",
        "=\n",
        "\\mathbf{A}(\\mathbf{BC})\n",
        "$$\n",
        "It is also _distributive_, meaning that (again assuming the dimensions are appropriate)\n",
        "$$\n",
        "\\mathbf{A}(\\mathbf{B} +\\mathbf{C})\n",
        "=\n",
        "\\mathbf{A}\\mathbf{B}\n",
        "+\n",
        "\\mathbf{A}\\mathbf{C}\n",
        "$$\n",
        "and\n",
        "$$\n",
        "(\\mathbf{A} + \\mathbf{B})\\mathbf{C}\n",
        "=\n",
        "\\mathbf{A}\\mathbf{C}\n",
        "+\n",
        "\\mathbf{B}\\mathbf{C}\n",
        "$$\n",
        "\n",
        "However, it is **not** always _commutative_, meaning $\\mathbf{AB}\\ne\\mathbf{BA}$ in general, even if both expressions are well-defined. More on this later.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "30FrS-qEuE_0"
      },
      "source": [
        "#### Exercises"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8V57WLXqfbK7"
      },
      "source": [
        "\n",
        "1. Let\n",
        "$$\n",
        "\\mathbf{A} =\n",
        "\\begin{pmatrix}\n",
        "1 & 2 & 3\\\\\n",
        "3 & 2 & 1\n",
        "\\end{pmatrix}\n",
        "\\quad \\text{ and } \\quad\n",
        "\\mathbf{B} =\n",
        "\\begin{pmatrix}\n",
        "1 & 2 \\\\\n",
        "3 & 2 \\\\\n",
        "4 & 5\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "  - Is $\\mathbf{AB}$ defined? If so, calculate it. If not, explain why not.\n",
        "  - Is $\\mathbf{BA}$ defined? If so, calculate it. If not, explain why not.\n",
        "\n",
        "2. Let\n",
        "$$\n",
        "\\mathbf{A} =\n",
        "\\begin{pmatrix}\n",
        "1 & 2\\\\\n",
        "3 & 2\n",
        "\\end{pmatrix}\n",
        "\\quad \\text{ and } \\quad\n",
        "\\mathbf{B} =\n",
        "\\begin{pmatrix}\n",
        "0 & 1 \\\\\n",
        "1 & 0\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "  - Is $\\mathbf{AB}$ defined? If so, calculate it. If not, explain why not.\n",
        "  - Is $\\mathbf{BA}$ defined? If so, calculate it. If not, explain why not.\n",
        "\n",
        "3. Use `jax` to check any calculations you have made in exercises 1 and 2.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "FacYBXxYgoWc"
      },
      "outputs": [],
      "source": [
        "# Place code here"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lrJ9PNDhx09g"
      },
      "source": [
        "#### Solutions to excercise 1 and 2"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4pjsiTARx7eS",
        "outputId": "13213815-853a-41ff-97d1-a10383cb3dff"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Answer for AB: \n",
            "[[19 21]\n",
            " [13 15]]\n",
            "\n",
            "Answer for BA: \n",
            "[[ 7  6  5]\n",
            " [ 9 10 11]\n",
            " [19 18 17]]\n",
            "\n"
          ]
        }
      ],
      "source": [
        "# Excercise 1\n",
        "A = jnp.array([[1, 2, 3], [3, 2, 1]])\n",
        "B = jnp.array([[1, 2], [3, 2], [4, 5]])\n",
        "\n",
        "answer_1 = A @ B\n",
        "print(f\"Answer for AB: \\n{answer_1}\\n\")\n",
        "answer_2 = B @ A\n",
        "print(f\"Answer for BA: \\n{answer_2}\\n\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0AvEp0rsy_5v",
        "outputId": "1cc5d960-6af9-44e4-cda3-eec6f1b1a929"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Answer for AB: \n",
            "[[2 1]\n",
            " [2 3]]\n",
            "\n",
            "Answer for BA: \n",
            "[[3 2]\n",
            " [1 2]]\n",
            "\n"
          ]
        }
      ],
      "source": [
        "# Excercise 2\n",
        "A = jnp.array([[1, 2], [3, 2]])\n",
        "B = jnp.array([[0, 1], [1, 0]])\n",
        "\n",
        "answer_1 = A @ B\n",
        "print(f\"Answer for AB: \\n{answer_1}\\n\")\n",
        "answer_2 = B @ A\n",
        "print(f\"Answer for BA: \\n{answer_2}\\n\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AgjNSkMMKxtD"
      },
      "source": [
        "### Matrix-Vector Multiplication\n",
        "You may have noticed that the vectors we defined earlier as vertical\n",
        "arrays of numbers are simply a special case of matrices.\n",
        "In particular, a dimension $n$ vector is just an $n\\times 1$ matrix.\n",
        "\n",
        "This means that we automatically have a formula for multiplying vectors\n",
        "by matrices.\n",
        "Once again, it is important that the neighbouring dimensions match.\n",
        "\n",
        "Let $\\mathbf{v}$ be a dimension $n$ vector and let $\\mathbf{A}$ be an $m\\times n$\n",
        "matrix.\n",
        "Multiplying $\\mathbf{v}$ by $\\mathbf{A}$ gives a\n",
        "dimension $m$ vector\n",
        "$$\n",
        "\\mathbf{u} = \\mathbf{Av}\n",
        "$$\n",
        "where $\\mathbf{u}$ has components\n",
        "$$\n",
        "\\mathbf{u}_i = \\sum_{j=1}^n\\mathbf{A}_{ij}\\mathbf{v}_j\n",
        "$$\n",
        "This operation is only valid when the second dimension of $\\mathbf{A}$\n",
        "(in this case $n$) is equal to the dimension of the vector.\n",
        "In other words, the number of columns in the matrix $\\mathbf{A}$ needs to\n",
        "match the number of rows in the vector $\\mathbf{v}$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WZbBqUF3vBRj"
      },
      "source": [
        "#### Matrix-Vector Multiplication in Jax\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eaujXs7gj5DK"
      },
      "source": [
        "\n",
        "Matrix-vector multiplication is performed in `jax` in the same way as\n",
        "matrix-matrix multiplication"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ZK23d7n5SaHu",
        "outputId": "72063498-067b-4fe6-ae1e-4910b7bd9935"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "A: (2, 3)\n",
            "b: (3,)\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "Array([14, 32], dtype=int32)"
            ]
          },
          "execution_count": 6,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "A = jnp.array([[1, 2, 3], [4, 5, 6]])\n",
        "b = jnp.array([1, 2, 3])\n",
        "\n",
        "print(f\"A: {A.shape}\\nb: {b.shape}\")\n",
        "jnp.matmul(A, b)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "9UDqb0IXS73w",
        "outputId": "7d7bbd38-98dc-4ffb-f886-43e0b7421b1e"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([14, 32], dtype=int32)"
            ]
          },
          "execution_count": 7,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "A @ b"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LuaKhbXYu3Cz"
      },
      "source": [
        "#### Exercise"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IGlu9UZAYnP5"
      },
      "source": [
        "For which of the following matrix-vector combinations is the expression\n",
        "$\n",
        "\\mathbf{Ab}\n",
        "$\n",
        "valid? If not, why not? If so, calculate the result and use `jax` to check your answer.\n",
        "1. $$\n",
        "\\mathbf{A}\n",
        "= \\begin{pmatrix}\n",
        "1 & 2 \\\\\n",
        "3 & 4 \\\\\n",
        "5 & 6\n",
        "\\end{pmatrix}\n",
        "\\quad\\text{ and }\\quad\n",
        "\\mathbf{b}\n",
        "= \\begin{pmatrix}\n",
        "9\\\\8\\\\7\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "2. $$\n",
        "\\mathbf{A}\n",
        "= \\begin{pmatrix}\n",
        "1 & 0 & 1\\\\\n",
        "0 & 1 & 0 \\\\\n",
        "1 & 0 & 1\\\\\n",
        "\\end{pmatrix}\n",
        "\\quad\\text{ and }\\quad\n",
        "\\mathbf{b}\n",
        "= \\begin{pmatrix}\n",
        "3\\\\ 50 \\\\6\n",
        "\\end{pmatrix}\n",
        "$$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "1BjNs1Nlj-V1"
      },
      "outputs": [],
      "source": [
        "# Place any code here"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YqBT9aJozt22"
      },
      "source": [
        "#### Solution"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "tJ7F89faz9RN",
        "outputId": "509295a6-5248-4c18-8429-7bfea64a951c"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([ 9, 50,  9], dtype=int32)"
            ]
          },
          "execution_count": 21,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# Exercise 1\n",
        "# Since A is a (3 x 2) and b is a (3 x 1) vector the product is not defined.\n",
        "\n",
        "# Excercise 2\n",
        "A = jnp.array([[1, 0, 1], [0, 1, 0], [1, 0, 1]])\n",
        "b = jnp.array([3, 50, 6])\n",
        "\n",
        "answer = A @ b\n",
        "answer"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Idrkvj8vgYvK"
      },
      "source": [
        "### Element-wise Matrix Multiplication or Hadamard Product\n",
        "An alternative multiplication operation between matrices\n",
        "(or arrays in general)\n",
        "is  _element-wise multiplication_.\n",
        "\n",
        "> This is not to be confused with matrix\n",
        "multiplication!\n",
        "\n",
        "Element-wise matrix multiplication is very simple. Take two matrices of the same\n",
        "dimensions and make a new matrix by multiplying the corresponding elements.\n",
        "If $\\mathbf{A}$ and $\\mathbf{B}$ are both $m\\times n$ matrices\n",
        "then the element-wise product is defined by\n",
        "$$\n",
        "\\mathbf{C} = \\mathbf{A} \\odot \\mathbf{B}\n",
        "$$\n",
        "where $\\mathbf{C}$ is an $m\\times n$ matrix with components\n",
        "$$\n",
        "\\mathbf{C}_{ij} = \\mathbf{A}_{ij}\\mathbf{B}_{ij}\n",
        "$$\n",
        "\n",
        "> Note that, in contrast to matrix multiplication, element-wise multiplication\n",
        "requires that _both_ of the dimensions of the matrices match, not just the\n",
        "neighbouring ones.\n",
        "\n",
        "Element-wise multiplication is used in machine learning,\n",
        "such as when applying a mask on the weights of a neural network\n",
        "in [the lottery ticket hypothesis paper](https://arxiv.org/abs/1803.03635),\n",
        "but is overall less common than matrix multiplication.\n",
        "We only mention it here to highlight the difference from matrix multiplication."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "16vWGYa7vhId"
      },
      "source": [
        "Element-wise multiplication of arrays can be achieved in python using the `*` operator.\n",
        "\n",
        "For instance,"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "VPmZ7l3d1KS1",
        "outputId": "7c7fa21d-473f-413f-f107-20c9c9e7e2c9"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "A: [[1 2]\n",
            " [3 4]]\n",
            "\n",
            "B:[[2. 2.]\n",
            " [2. 2.]]\n"
          ]
        }
      ],
      "source": [
        "A = jnp.array([[1,  2], [3, 4]])\n",
        "B = 2 * jnp.ones((2, 2)) # look this function up if you don't know it!\n",
        "print(f\"A: {A}\\n\\nB:{B}\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "GhH2p-8n1b6Q",
        "outputId": "df556544-3da5-4f57-b422-be6caba18980"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[2., 4.],\n",
              "       [6., 8.]], dtype=float32)"
            ]
          },
          "execution_count": 14,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "A * B"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qR2HKMmo1gIG"
      },
      "source": [
        "Note that this is different from matrix multiplication."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "mdsw4We01eoc",
        "outputId": "59b58427-0c37-4701-c0cf-0ef0cb3cae9e"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[ 6.,  6.],\n",
              "       [14., 14.]], dtype=float32)"
            ]
          },
          "execution_count": 15,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "jnp.matmul(A, B)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5WYADPkqvzpT"
      },
      "source": [
        "#### Exercise"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Uaz2b-zm1sB5"
      },
      "source": [
        "\n",
        "-  Is element-wise matrix multiplication _commutative_? That is, is it true that\n",
        "$$\n",
        "\\mathbf{A}\\odot\\mathbf{B} = \\mathbf{B}\\odot\\mathbf{A}\n",
        "$$\n",
        "for all $m\\times n$ matrices $\\mathbf{A}$ and $\\mathbf{B}$?\n",
        "Justify your answer.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dxSI2RJRwOah"
      },
      "source": [
        "### Commuting Matrices"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_auW_lYGlg_U"
      },
      "source": [
        "Recall that square matrices are ones whose dimensions are of the form\n",
        "$n\\times n$ (so they form a square array).\n",
        "If $\\mathbf{A}$ and $\\mathbf{B}$ are both $n\\times n$ matrices (so square), then\n",
        "the products $\\mathbf{AB}$ and $\\mathbf{BA}$ are always defined.\n",
        "\n",
        "However, and this is an important point, they are not always equal!\n",
        "This is very different from multiplying real numbers!\n",
        "\n",
        "If $\\mathbf{A}$ and $\\mathbf{B}$ are both $n\\times n$ square matrices\n",
        "such that\n",
        "$$\n",
        "\\mathbf{AB} = \\mathbf{BA}\n",
        "$$\n",
        "then we say that $\\mathbf{A}$ and $\\mathbf{B}$ _commute_.\n",
        "(For the clarity, this does not always happen!)\n",
        "\n",
        "Matrices that commute have important properties in relation to one another, but\n",
        "that is beyond the scope of this practical.\n",
        "If you're interested: look at [the wiki page for commuting matrices](https://en.wikipedia.org/wiki/Commuting_matrices), ask a tutor or check out one of the futher reading resources.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nABLxRHgwFAY"
      },
      "source": [
        "#### Exercises"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Gvx0GBTYkojB"
      },
      "source": [
        "1. Let\n",
        "$$\n",
        "\\mathbf{A} =\n",
        "\\begin{pmatrix}\n",
        "1 & 2 \\\\\n",
        "3 & 4\n",
        "\\end{pmatrix}\n",
        "\\quad \\text{ and } \\quad\n",
        "\\mathbf{B} =\n",
        "\\begin{pmatrix}\n",
        "0 & 1 \\\\\n",
        "1 & 0 \\\\\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "  - Do $\\mathbf{A}$ and $\\mathbf{B}$ commute?\n",
        "  - Check your calculations using `jax`\n",
        "\n",
        "2. [Optional] Let $a, b, c, d \\in \\mathbb{R}$ be arbitrary real numbers and define\n",
        "$$\n",
        "\\mathbf{A} =\n",
        "\\begin{pmatrix}\n",
        "a & b \\\\\n",
        "c & d\n",
        "\\end{pmatrix}\n",
        "\\quad \\text{ and } \\quad\n",
        "\\mathbf{I} =\n",
        "\\begin{pmatrix}\n",
        "1 & 0 \\\\\n",
        "0 & 1 \\\\\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "Prove that $\\mathbf{A}$ and $\\mathbf{B}$ commute."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "TcfQECezmOhr"
      },
      "outputs": [],
      "source": [
        "# Place any code here"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pZKGng2p1JhB"
      },
      "source": [
        "#### Solution"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Kw1X9Igq1M59",
        "outputId": "801bb297-8bc0-44d1-d347-78c79f5f5d9d"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "AB: \n",
            " [[2 1]\n",
            " [4 3]] \n",
            "\n",
            "BA \n",
            " [[3 4]\n",
            " [1 2]] \n",
            "\n"
          ]
        }
      ],
      "source": [
        "# Answer to exercise 1\n",
        "A = jnp.array([[1, 2], [3, 4]])\n",
        "B = jnp.array([[0, 1], [1, 0]])\n",
        "\n",
        "AB = A @ B\n",
        "BA = B @ A\n",
        "\n",
        "# See the results:\n",
        "print(f\"AB: \\n {AB} \\n\")\n",
        "print(f\"BA: \\n {BA} \\n\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NxdDyfTJ100f",
        "outputId": "88481fb5-1f06-4c4a-864e-2a96916ed380"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[-1, -3],\n",
              "       [ 3,  1]], dtype=int32)"
            ]
          },
          "execution_count": 26,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# Since the results for AB and BA are different we can conclude that\n",
        "# the matrics do not commute. We can further check this by computing their\n",
        "# difference and seeing that it is not zero.\n",
        "\n",
        "AB - BA"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Gq3dWm4Slkhm"
      },
      "source": [
        "### The Identity Matrix"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FyRPFS6dwVfC"
      },
      "source": [
        "The _identity matrix_ is the $n\\times n$ matrix\n",
        "$\\mathbf{I}$ with components\n",
        "$$\n",
        "I_{ij}\n",
        "= \\begin{cases}\n",
        "  0 \\quad \\text{if } \\; i\\ne j \\\\\n",
        "  1 \\quad \\text{if } \\; i= j\n",
        "  \\end{cases}\n",
        "$$\n",
        "As an array this looks like\n",
        "$$\n",
        "\\mathbf{I}\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "1 & 0 & 0 & \\cdots & 0 \\\\\n",
        "0 & 1 & 0 & \\cdots & 0 \\\\\n",
        "0 & 0 & 1 & \\cdots & 0 \\\\\n",
        "\\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
        "0 & 0 & 0 & \\cdots & 1 \\end{pmatrix}.\n",
        "$$\n",
        "Sometimes you will see $\\mathbf{I}_n$ when the author wants to emphasise\n",
        "that it is the $n\\times n$ identity matrix. For instance, $\\mathbf{I}_2$ would\n",
        "be\n",
        "$$\n",
        "\\mathbf{I}_2 =\n",
        "\\begin{pmatrix}\n",
        "1 & 0 \\\\\n",
        "0 & 1 \\\\\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "However, the dimension is often clear from the context so we won't write it unless necessary.\n",
        "\n",
        ">What's special about the identity matrix? It's in the name: when you multiply by the identity, nothing happens.\n",
        "In particular, if $\\mathbf{A}$ is an $n\\times n$ square matrix and $\\mathbf{I}$\n",
        "is the $n\\times n$ identity matrix, then\n",
        "$$\n",
        "\\mathbf{IA} = \\mathbf{AI} = \\mathbf{A}\n",
        "$$\n",
        "and $\\mathbf{I}$ is the _only_ matrix with this property.\n",
        "Note that this also means that identity matrix\n",
        "commutes with all matrices with the same dimensions."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zA0XMoOdviKs"
      },
      "source": [
        "#### Identity Matrices in Jax\n",
        "\n",
        "The $n\\times n$ identity matrix can be obtained in `jax` by using\n",
        "`jnp.eye(n)`. For instance, with $n=3$."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pfGnjmh3tTHq",
        "outputId": "4002609e-41a6-47b1-f287-cf5fa2e22e41"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[1., 0., 0.],\n",
              "       [0., 1., 0.],\n",
              "       [0., 0., 1.]], dtype=float32)"
            ]
          },
          "execution_count": 9,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "jnp.eye(3)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_RBiElEhtJ2x"
      },
      "source": [
        "#### Exercise\n",
        "1. Choose a square matrix $\\mathbf{A}$ and use `jax` to check that the identity matrix (of the appropriate dimension) satisfies\n",
        "$$\n",
        "\\mathbf{IA} = \\mathbf{AI} = \\mathbf{A}\n",
        "$$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "O9_NRkzQkvrY"
      },
      "outputs": [],
      "source": [
        "# Place code here"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5UEw7yBRlPWI"
      },
      "source": [
        "#### Example Solution"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NuL_88qglRV9",
        "outputId": "1295b871-3d1a-4324-bbef-4b82766bdba0"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[0., 0., 0., 0.],\n",
              "       [0., 0., 0., 0.],\n",
              "       [0., 0., 0., 0.],\n",
              "       [0., 0., 0., 0.]], dtype=float32)"
            ]
          },
          "execution_count": 22,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "I = jnp.eye(4)\n",
        "A = jnp.array([\n",
        "    [1, 2, 3, 4],\n",
        "    [5, 6, 7, 8],\n",
        "    [9, 10, 11, 12],\n",
        "    [13, 14, 15, 16],\n",
        "])\n",
        "lhs = jnp.matmul(I, A)\n",
        "rhs = jnp.matmul(A, I)\n",
        "assert jnp.allclose(lhs, rhs)\n",
        "lhs - rhs"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XwIuSWEVmSHX"
      },
      "source": [
        "### Matrix Inverse\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3qYaaErTGSim"
      },
      "source": [
        "#### What is the Matrix Inverse?\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "naTTZWQYl3iz"
      },
      "source": [
        "\n",
        "We've covered the addition and subtraction of matrices as well as matrix\n",
        "multiplication. Is there such a thing as matrix division?\n",
        "The answer is yes, but it's not always possible.\n",
        "\n",
        "Given an $n\\times n$ square matrix $\\mathbf{A}$, we say that\n",
        "$\\mathbf{A}$ is _invertible_ or _non-singular_ if there exists\n",
        "an $n\\times n$ matrix\n",
        "$\\mathbf{A}^{-1}$ such that multiplication with $\\mathbf{A}$ produces\n",
        "the $n\\times n$ identity matrix. That is\n",
        "$$\n",
        "\\mathbf{A}^{-1}\\mathbf{A} =\n",
        "\\mathbf{A}\\mathbf{A}^{-1} = \\mathbf{I}\n",
        "$$\n",
        "If such a matrix $\\mathbf{A}^{-1}$ exists, then we call it the _matrix inverse of $\\mathbf{A}$_.\n",
        "\n",
        ">Not every matrix has an inverse, but when an inverse exists\n",
        "it is unique.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FUjbba0tGRhz"
      },
      "source": [
        "\n",
        "#### When does the Inverse Exist?\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jFmSa7ptl5Ya"
      },
      "source": [
        "\n",
        "It is important to note that _not all matrices have inverses_.\n",
        "For instance, there is no $2\\times 2$ matrix $\\mathbf{B}$ such that\n",
        "$$\n",
        "\\mathbf{B}\n",
        "\\begin{pmatrix}\n",
        "0 & 0 \\\\\n",
        "0 & 0\n",
        "\\end{pmatrix}\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "1 & 0 \\\\\n",
        "0 & 1\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "Can you see why? Think about it for a few seconds, then ask the tutors if you still don't understand why\n",
        "\n",
        ">When a matrix does not have an inverse we say it is\n",
        "_not invertible_\n",
        "or\n",
        " _singular_.\n",
        "\n",
        "When the matrix inverse exists, it allows us to solve some matrix equations.\n",
        "For instance, if $\\mathbf{A}$ is invertible then\n",
        "$$\n",
        "\\mathbf{C} = \\mathbf{AB}\n",
        "\\quad\\implies\\quad\n",
        "\\mathbf{B} = \\mathbf{A}^{-1}\\mathbf{C}\n",
        "$$\n",
        "Similarly, if $\\mathbf{b}$ and $\\mathbf{c}$ are dimension $n$ vectors\n",
        "and $\\mathbf{A}$ is invertible, then\n",
        "$$\n",
        "\\mathbf{c} = \\mathbf{Ab}\n",
        "\\quad\\implies\\quad\n",
        "\\mathbf{b} = \\mathbf{A}^{-1}\\mathbf{c}\n",
        "$$\n",
        "\n",
        "There are many equivalent ways of checking whether a matrix is invertible,\n",
        "for instance see [the wiki page on invertible matrices](https://en.wikipedia.org/wiki/Invertible_matrix#The_invertible_matrix_theorem).\n",
        "Sometimes you can even just see by inspection, such as with the\n",
        "matrix of all 0s above.\n",
        "An important method is to check the _determinant_ of the matrix, which\n",
        "is a scalar quantity associated to a square matrix.\n",
        "A matrix is invertible if and only if it's determinant is non-zero.\n",
        "We will cover the determinant later in the practical.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dWbPGhU2mu-y"
      },
      "source": [
        "#### The Determinant\n",
        "\n",
        "The _determinant_ of a matrix is a special number that can be calculated from a (square) matrix."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4Nvg8Fdom0y1"
      },
      "source": [
        "For example, consider a matrix\n",
        "$$\n",
        "A = \\begin{pmatrix}\n",
        "3 & 8 \\\\\n",
        "4 & 6\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "The determinant is\n",
        "$$(3 \\times 6 ) - (8 \\times 4) = 18-32= -14$$\n",
        "\n",
        "Check out [this link](https://www.mathsisfun.com/algebra/matrix-determinant.html) for more examples."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gCGuMrjcnuIL"
      },
      "source": [
        "The determinant of a $2\\times 2$ matrix is\n",
        "\n",
        "$$\n",
        "A = \\begin{pmatrix}\n",
        "a & b \\\\\n",
        "c & d\n",
        "\\end{pmatrix}\n",
        "= ad - bc\n",
        "$$\n",
        "\n",
        "You can calculate the determinant for any kind of square matrix but this becomes more tedious to do by hand as we move from $2\\times 2$ to higher dimensions.\n",
        "\n",
        ">The determinant is important becauses it characterizes some properties of matrices. For example, if the determinant of a matrix is 0, then the matrix is _non-invertible_ i.e the inverse of the matrix does not exist, as we have defined earlier.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IbDkN8MwGPBa"
      },
      "source": [
        "\n",
        "#### Algebraic Properties [Optional]\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pg1sYpa0l7tK"
      },
      "source": [
        "\n",
        "Let $\\mathbf{A}$ and $\\mathbf{B}$ be invertible $n\\times n$ square matrices,\n",
        "then the matrix $\\mathbf{AB}$ is invertible with inverse\n",
        "$$\n",
        "(\\mathbf{AB})^{-1} = \\mathbf{B}^{-1}\\mathbf{A}^{-1}\n",
        "$$\n",
        "In general, even if both sides exist,\n",
        "$$\n",
        "(\\mathbf{A} + \\mathbf{B})^{-1} \\ne \\mathbf{A}^{-1} + \\mathbf{B}^{-1}\n",
        "$$\n",
        "This might feel a bit unfortunate, but we're not completely out of luck.\n",
        "A special case of the [Woodbury matrix identity](https://en.wikipedia.org/wiki/Woodbury_matrix_identity)\n",
        "is\n",
        "$$\n",
        "(\\mathbf{A} + \\mathbf{B})^{-1}\n",
        "=\n",
        "\\mathbf{A}^{-1} - \\mathbf{A}^{-1}(\\mathbf{A}^{-1}\n",
        "+ \\mathbf{B}^{-1})^{-1}\\mathbf{A}^{-1}\n",
        "=\n",
        "\\mathbf{A}^{-1} - (\\mathbf{A} + \\mathbf{A}\\mathbf{B}^{-1}\\mathbf{A})^{-1}\n",
        "$$\n",
        "which holds as long as the relevant inverses exist.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "je9lXYFOl_qd"
      },
      "source": [
        "\n",
        "#### Exercises\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6YihXsw4mA_z"
      },
      "source": [
        "\n",
        "1. Is the following matrix invertible? Why?\n",
        "  $$\n",
        "\\begin{pmatrix}\n",
        "0 & 0 \\\\\n",
        "0 & 1\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "2. Is the $n\\times n$ identity matrix invertible? If so, what is it's inverse?\n",
        "\n",
        "3. (Optional) Prove that matrix inverses are unique.\n",
        " That is, prove that for any $n\\times n$ matrix $\\mathbf{A}$, there is at most one matrix $\\mathbf{A}^{-1}$ such that\n",
        "$$\n",
        "\\mathbf{A}^{-1}\\mathbf{A} =\n",
        "\\mathbf{A}\\mathbf{A}^{-1} = \\mathbf{I}\n",
        "$$\n",
        "\n",
        "4. (Optional) Find a counter example (where both sides of the equation exist) to\n",
        "$(\\mathbf{A} + \\mathbf{B})^{-1}\n",
        "=\n",
        "\\mathbf{A}^{-1} + \\mathbf{B}^{-1}$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QWmZJUhLmLoi"
      },
      "source": [
        "#### Solutions"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "L9D0mhiUmOdm"
      },
      "source": [
        "\n",
        "1. No. Consider an arbitrary $2\\times 2$ matrix\n",
        "$$\n",
        "\\mathbf{A}\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "a & b\\\\\n",
        "c & d\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "where $a,b, c, d\\in\\mathbb{R}$.\n",
        "Then\n",
        "$$\n",
        "\\begin{pmatrix}\n",
        "a & b\\\\\n",
        "c & d\n",
        "\\end{pmatrix}\n",
        "\\begin{pmatrix}\n",
        "0 & 0 \\\\\n",
        "0 & 1\n",
        "\\end{pmatrix}\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "0 & b \\\\\n",
        "0 & d\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "So for all $a, b, c, d \\in \\mathbb{R}$\n",
        "$$\n",
        "\\begin{pmatrix}\n",
        "a & b\\\\\n",
        "c & d\n",
        "\\end{pmatrix}\n",
        "\\begin{pmatrix}\n",
        "0 & 0 \\\\\n",
        "0 & 1\n",
        "\\end{pmatrix}\n",
        "\\ne\n",
        "\\begin{pmatrix}\n",
        "1 & 0 \\\\\n",
        "0 & 1\n",
        "\\end{pmatrix}\n",
        "=\n",
        "\\mathbf{I}_2\n",
        "$$\n",
        "\n",
        "2. Yes, because $\\mathbf{II} = \\mathbf{I}$. It's its own inverse!\n",
        "$$\n",
        "\\mathbf{I}^{-1} = \\mathbf{I}\n",
        "$$\n",
        "\n",
        "3. Suppose that $\\mathbf{B}\\mathbf{A} = \\mathbf{I}$ and\n",
        "$\\mathbf{C}\\mathbf{A} = \\mathbf{I}$. Then\n",
        "$$\n",
        "(\\mathbf{B} - \\mathbf{C})\\mathbf{A} = 0\n",
        "$$\n",
        "so\n",
        "$$\n",
        "(\\mathbf{B} - \\mathbf{C})\\mathbf{A}\\mathbf{A}^{-1}\n",
        "=\n",
        "(\\mathbf{B} - \\mathbf{C})\\mathbf{I}\n",
        "=\n",
        "\\mathbf{B} - \\mathbf{C}\n",
        "= 0\n",
        "$$\n",
        "and $\\mathbf{B} = \\mathbf{C}$.\n",
        "\n",
        "4. There are many possible answers to this, but a very simple one\n",
        "is $\\mathbf{A} =\\mathbf{B} = \\mathbf{I}$. This gives\n",
        "$$\n",
        "(\\mathbf{A} + \\mathbf{B})^{-1} = (2\\mathbf{I})^{-1} = \\frac12 \\mathbf{I}\n",
        "$$\n",
        "while at the same time\n",
        "$\\mathbf{A}^{-1} = \\mathbf{B}^{-1} = \\mathbf{I}$. Plugging it in\n",
        "breaks the equation\n",
        "$$\n",
        "(\\mathbf{I} + \\mathbf{I})^{-1} = \\frac12 \\mathbf{I}\n",
        "\\ne\n",
        "\\mathbf{I} + \\mathbf{I}\n",
        "=2\\mathbf{I}\n",
        "$$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VJvkYB5wAsEG"
      },
      "source": [
        "#### Computing the Inverse\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MlszWS2GpOp0"
      },
      "source": [
        "\n",
        "\n",
        "Computing the inverse of a matrix is computationally intensive (see [here](https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra)).\n",
        "There are formulae for computing inverses by hand, but doing so is\n",
        "tedious even for $3\\times 3$ matrices and it gets much worse as the dimensions\n",
        "grow.\n",
        "The formula for the inverse of a $2\\times 2$ matrix is relatively simple, but\n",
        "won't get you far in machine learning. We give it here in case you've never seen it.\n",
        "\n",
        "If\n",
        "$$\n",
        "\\mathbf{A}\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "a & b\\\\\n",
        "c & d\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "with $ad - bc \\ne 0$, then\n",
        "$$\n",
        "\\mathbf{A}^{-1}\n",
        "=\n",
        "\\frac{1}{ad - bc}\n",
        "\\begin{pmatrix}\n",
        "d & -b\\\\\n",
        "-c & a\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        ">Remember that $ad - bc$ is the _determinant_!\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vyPycTUcocE0"
      },
      "source": [
        "\n",
        "#### Exercise [Optional]\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "o17isl8npQ87"
      },
      "source": [
        "\n",
        "- Verify that the above formula gives $\\mathbf{A}^{-1}\\mathbf{A} = \\mathbf{I}$.\n",
        "- Calculate the inverse of\n",
        "$$\n",
        "\\mathbf{A} = \\begin{pmatrix}\n",
        "1 & 2 \\\\\n",
        "3 & 4\n",
        "\\end{pmatrix}\n",
        "$$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OPE18pQHohm_"
      },
      "source": [
        "#### Computing the Inverse Using `jax`\n",
        "Like most linear algebra packages, `jax` provides a way to compute matrix inverses.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IJ9o_kMsEAM7",
        "outputId": "f389220c-1de2-48c1-e8f3-2cac4161bfe0"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([-0.5,  0.5], dtype=float32)"
            ]
          },
          "execution_count": 33,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "A = jnp.array([[1, 3], [2, 4]])\n",
        "jnp.linalg.inv(A)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NzxhDIcuEKyn"
      },
      "source": [
        "However, this can be numerically unstable for large matrices. In addition, what\n",
        "one often wants in the end is not $\\mathbf{A}^{-1}$, but actually $\\mathbf{A}^{-1} \\mathbf{b}$ for some vector $\\mathbf{b}$.\n",
        "For instance we might want to solve\n",
        "$$\n",
        "\\mathbf{b} = \\mathbf{A}\\mathbf{c}\n",
        "$$\n",
        "for $\\mathbf{c}$.\n",
        "In these cases, it is much better\n",
        "(both more stable and faster)\n",
        "to use `jnp.linalg.solve` than to calculate the inverse and do the multiplication. Note that this function will assume that $\\mathbf{A}$ is\n",
        "invertible.\n",
        "For a simple application to solving systems of linear equations, see Section 2.1\n",
        "of the [Mathematics for Machine Learning Book](https://mml-book.github.io/book/mml-book.pdf)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "oEfEud2galJK"
      },
      "outputs": [],
      "source": [
        "A = jnp.array([[1, 3], [2, 4]])\n",
        "b = jnp.array([1, 1])\n",
        "c = jnp.linalg.inv(A) @ b # bad way\n",
        "c = jnp.linalg.solve(A, b) # good way"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sJ810-IcbM8D"
      },
      "source": [
        "We can do a rough comparison to assess the speed difference"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DSWTF_efbCvc",
        "outputId": "69cad1e2-3565-4980-f155-68d3d50d69c2"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "1.2177441\n"
          ]
        }
      ],
      "source": [
        "# generate some random data\n",
        "rng = np.random.RandomState(seed=0)\n",
        "A = jnp.eye(100) + 0.01 * jnp.array(rng.randn(100, 100))\n",
        "b = jnp.array(rng.randn(100))\n",
        "\n",
        "# check that generated A is invertible (i.e. it's determinant is non-zero)\n",
        "# it's also worth making sure it's not too close to 0 when doing a test like this for stability purposes\n",
        "print(jnp.linalg.det(A))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "uS9YYNrkKUZT",
        "outputId": "693b427f-518c-4e67-bd0d-25002726d3c7"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "267 µs ± 161 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
          ]
        }
      ],
      "source": [
        "%%timeit\n",
        "c1 = jnp.linalg.inv(A) @ b"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "jDqpHvGKcCA0",
        "outputId": "d2ecb5ce-480f-4d67-be0e-6726ef98403b"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "91 µs ± 21.9 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
          ]
        }
      ],
      "source": [
        "%%timeit\n",
        "c2 = jnp.linalg.solve(A, b)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Okkj0vPCf95e"
      },
      "outputs": [],
      "source": [
        "# check nothing broke and that results are the same (within numerical tolerance)\n",
        "c1 = jnp.linalg.inv(A) @ b\n",
        "c2 = jnp.linalg.solve(A, b)\n",
        "assert all(np.isfinite(c1))\n",
        "assert np.allclose(c1, c2)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ldh6MIt-cSw7"
      },
      "source": [
        "#### Exercise\n",
        "\n",
        "Let\n",
        "$$\n",
        "\\mathbf{A} =\n",
        "\\begin{pmatrix}\n",
        "1 & 2 & 3 & 4 \\\\\n",
        "4 & 3 & 2 & 1 \\\\\n",
        "5 & 0 & 0 & 8 \\\\\n",
        "8 & 1 & 1 & 5\n",
        "\\end{pmatrix}\n",
        "\\quad\\text{ and }\\quad\n",
        "\\mathbf{b} =\n",
        "\\begin{pmatrix}\n",
        "1 \\\\ 0 \\\\ 0 \\\\ 1\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "Use `jax` to solve\n",
        "$$\n",
        "\\mathbf{Ac} = \\mathbf{b}\n",
        "$$\n",
        "for $\\mathbf{c}$."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "b9D9MEsHKVOc"
      },
      "outputs": [],
      "source": [
        "A = jnp.array([\n",
        "    [1, 2, 3, 4],\n",
        "    [4, 3, 2, 1],\n",
        "    [5, 0, 0, 8],\n",
        "    [8, 1, 1, 5],\n",
        "  ])\n",
        "b = jnp.array([1, 0, 0, 1])\n",
        "\n",
        "# Put your code here\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "T_Nub_1VpXoz"
      },
      "source": [
        "#### Solution"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "OzDeohN4pZMM",
        "outputId": "869b3cba-9ba4-4318-e348-c63c37f2fa08"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([ 0.17777777, -0.8666666 ,  1.        , -0.1111111 ], dtype=float32)"
            ]
          },
          "execution_count": 25,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "jnp.linalg.solve(A, b)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WXDCIqLPj_ej"
      },
      "source": [
        "### The Transpose\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7Bgb2OrrTvnU"
      },
      "source": [
        "An important operation on matrices is the _transpose_.\n",
        "If you've not seen it before, the matrix transpose will probably seem\n",
        "like an unusual and arbitrary operation without much intuition behind it.\n",
        "However, it has a deep significance in mathematics (to do with dual spaces, an advanced topic which we won't cover) and also a geometric interpretation (to do with inner products, which we will cover later). Regardless of the deeper meaning, the\n",
        "transpose will occur regularly so it's important to know how to compute it."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uIOjqUqAGqW9"
      },
      "source": [
        "#### Computing the Transpose\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gQHFlGc4TPqX"
      },
      "source": [
        "Let $\\mathbf{A}$ be an $m\\times n$ matrix, then the transpose of $\\mathbf{A}$, written $\\mathbf{A}^\\top$\n",
        "is the $n\\times m$ matrix formed from using the columns of $\\mathbf{A}$ as rows\n",
        "instead.\n",
        "The first column of $\\mathbf{A}$ is the first row of $\\mathbf{A}^\\top$,\n",
        "the second column of $\\mathbf{A}$ is the second row of $\\mathbf{A}^\\top$\n",
        "and so on.\n",
        "\n",
        "Some examples:\n",
        "- $$\n",
        "\\mathbf{A}=\n",
        "\\begin{pmatrix}\n",
        "1 & 2 \\\\\n",
        "3 & 4 \\\\\n",
        "5 & 6\n",
        "\\end{pmatrix}\n",
        "\\quad\\implies\\quad\n",
        "\\mathbf{A}^\\top\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "1 & 3 & 5 \\\\\n",
        "2 & 4 & 6\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "- $$\n",
        "\\mathbf{A}=\n",
        "\\begin{pmatrix}\n",
        "1 & 2 \\\\\n",
        "3 & 4\n",
        "\\end{pmatrix}\n",
        "\\quad\\implies\\quad\n",
        "\\mathbf{A}^\\top\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "1 & 3  \\\\\n",
        "2 & 4\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "- $$\n",
        "\\mathbf{A}=\n",
        "\\begin{pmatrix}\n",
        "1 & -1 & 0 \\\\\n",
        "-1 & 1 & -1 \\\\\n",
        "0 & -1 & 1 \\\\\n",
        "\\end{pmatrix}\n",
        "\\quad\\implies\\quad\n",
        "\\mathbf{A}^\\top\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "1 & -1 & 0 \\\\\n",
        "-1 & 1 & -1 \\\\\n",
        "0 & -1 & 1 \\\\\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        ">Note that the transpose of a non-square matrix is a matrix of a different shape,\n",
        "but that because a square matrix has the same number of rows as columns its\n",
        "shape is that same as that of its transpose.\n",
        "\n",
        "The general formula for calculating the matrix transpose is as follows.\n",
        "If $\\mathbf{A}$ is an $m\\times n$ matrix with components $\\mathbf{A}_{ij}$\n",
        "then the transpose of $\\mathbf{A}$ is the $n\\times m$ matrix\n",
        "$\\mathbf{B} = \\mathbf{A}^\\top$\n",
        "with components $\\mathbf{B}_{ij} = \\mathbf{A}_{ji}$.\n",
        "The change in order of the indices represents the switching of rows with columns.\n",
        "\n",
        ">If a matrix is equal to its transpose, so $\\mathbf{A} = \\mathbf{A}^\\top$,\n",
        "then we say that it is _symmetric_.\n",
        "\n",
        "An important class of matrices are _orthogonal matrices_, these are matrices for which $\\mathbf{A}^\\top = \\mathbf{A}^{-1}$.\n",
        "That is, matrices for which the transpose is equal to the inverse. This makes symmetric matrices super useful because for these class of matrices, we won't need to compute the inverse (which is costly!!).\n",
        "\n",
        "Right now, this might seem arbitrary, but it has important algebraic and\n",
        "geometrical significance. We will touch on some of this again later.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TLx54v7TvP9U"
      },
      "source": [
        "#### Transpose in Jax\n",
        "The matrix transpose can be calculated in `jax` easily using `A.T`\n",
        "or `A.transpose()`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pBHziikNUqGl",
        "outputId": "03198f6e-7433-4261-e75a-d88e44968367"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[1, 2],\n",
              "       [3, 4],\n",
              "       [5, 6]], dtype=int32)"
            ]
          },
          "execution_count": 5,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "A = jnp.array([[1, 2], [3, 4], [5, 6]])\n",
        "A"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Jp1pJlGdYG3O",
        "outputId": "dad3ea83-8d2f-40b9-e932-ed6b9b41126c"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[1, 3, 5],\n",
              "       [2, 4, 6]], dtype=int32)"
            ]
          },
          "execution_count": 6,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "A.T"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "BIGe30RlUwpe",
        "outputId": "52f8080c-9a44-4842-ae75-19a4abf760e0"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[1, 3, 5],\n",
              "       [2, 4, 6]], dtype=int32)"
            ]
          },
          "execution_count": 7,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "A.transpose()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mqU2QdQNZQU2"
      },
      "source": [
        "\n",
        "\n",
        "```\n",
        "# This is formatted as code\n",
        "```\n",
        "\n",
        "#### Exercise [Optional]\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BsRN4lhWptwY"
      },
      "source": [
        "\n",
        "\n",
        " Calculate the transpose of the matrix\n",
        " $$\n",
        " \\mathbf{A}\n",
        " =\n",
        " \\begin{pmatrix}\n",
        " 1 & 0 \\\\\n",
        " 0 & 1 \\\\\n",
        " -1 & -2\n",
        " \\end{pmatrix}\n",
        " $$\n",
        " and check it with `jax` below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IescE2ltZRND",
        "outputId": "b91bf099-c628-4fc8-d823-0baaf9286aae"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[ 1,  0],\n",
              "       [ 0,  1],\n",
              "       [-1, -2]], dtype=int32)"
            ]
          },
          "execution_count": 29,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "A =  jnp.array([[1, 0], [0, 1], [-1, -2]])\n",
        "# Place your code here"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9Z7yVGhV2nrQ"
      },
      "source": [
        "#### Solution [Optional]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "YnYj-kiM2qCp",
        "outputId": "abeeec23-cad0-4e24-843a-210106f53f69"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[ 1,  0, -1],\n",
              "       [ 0,  1, -2]], dtype=int32)"
            ]
          },
          "execution_count": 28,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "A_T = A.T\n",
        "A_T"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8Xdm9nxHG9Om"
      },
      "source": [
        "#### Algebraic Properties [Optional]\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nNkPhujMTYU8"
      },
      "source": [
        "Just like the matrix inverse, we have some rules for manipulating matrix transposes that are useful and easy to prove (try it!).\n",
        "\n",
        "For any $m\\times n$ matrices $\\mathbf{A}$ and $\\mathbf{B}$\n",
        "- $(\\mathbf{A}^\\top)^\\top = \\mathbf{A}$\n",
        "- $(\\mathbf{A} + \\mathbf{B})^\\top = \\mathbf{A}^\\top + \\mathbf{B}^\\top$\n",
        "\n",
        "If $\\mathbf{A}$ is an $m\\times n$ matrix and\n",
        "$\\mathbf{B}$ is an $n\\times k$ matrix then\n",
        "$$\n",
        "\\mathbf{AB}^{\\top} = \\mathbf{B}^\\top\\mathbf{A}^\\top\n",
        "$$\n",
        "\n",
        "If $\\mathbf{A}$ is an invertible square matrix then so is $\\mathbf{A}^\\top$\n",
        "and\n",
        "$$\n",
        "{(\\mathbf{A}^\\top)}^{-1}\n",
        "=\n",
        "{(\\mathbf{A}^{-1})}^{\\top}\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "chUFwXlljrAW"
      },
      "source": [
        "### Matrices as Linear Maps [Optional]\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Qe1J8G1vTfxL"
      },
      "source": [
        "So far, we have viewed matrices as arrays with certain operations such\n",
        "as multiplications, addition, inversion and the transpose.\n",
        "This is computational viewpoint provides sufficient literacy for the basics\n",
        "uses in machine learning, and is even sound from a mathematical perspective,\n",
        "but it lacks intuition.\n",
        "\n",
        "An alternative, more geometric perspective on matrices is that they represent\n",
        "_linear transformations of vectors_. Let $U$ and $V$ be a vector spaces,\n",
        "then a function $f: U \\to V$ is a _linear map_ if it satisfies\n",
        "$$\n",
        "f(\\lambda \\mathbf{a} + \\mu \\mathbf{b})\n",
        "= \\lambda f(\\mathbf{a}) + \\mu f(\\mathbf{b})\n",
        "$$\n",
        "for all $\\mathbf{a}, \\mathbf{b}\\in V$ and all $\\lambda, \\mu \\in \\mathbb{R}$.\n",
        "\n",
        "You can check from the formula that matrix multiplication is linear. In\n",
        "particular, if $\\mathbf{A}$ is an $m\\times k$\n",
        "matrix and $\\mathbf{B}$ and $\\mathbf{C}$ are $k\\times n$ matrices then\n",
        "$$\n",
        "\\mathbf{A}(\\lambda \\mathbf{B} +\\mu\\mathbf{C})\n",
        "= \\lambda \\mathbf{AB}+ \\mu\\mathbf{AC}\n",
        "$$\n",
        "The same holds with vectors $\\mathbf{b}, \\mathbf{c}\\in\\mathbb{R}^n$\n",
        "(which is just the $n=1$ case)\n",
        "$$\n",
        "\\mathbf{A}(\\lambda \\mathbf{b} +\\mu\\mathbf{c})\n",
        "= \\lambda \\mathbf{Ab}+ \\mu\\mathbf{Ac}\n",
        "$$\n",
        "\n",
        ">The set of linear transformations are important because they preserve the\n",
        "vector space structure. They map vectors to vectors (possibly in a different space)\n",
        "without messing up the addition and scalar multiplication, e.g., a linear\n",
        "map applied to a sum is just the sum of the linear map applied to the terms.\n",
        "\n",
        "Any linear mapping $f: \\mathbb{R}^n\\to\\mathbb{R}^n$ can be represented as\n",
        "an $n\\times n$ matrix. This fact can be checked by considering a _basis_ for the vector space $\\mathbb{R}^n$, which will be introduced later.\n",
        "By represented, we mean that there is a matrix $\\mathbf{A}$ such that\n",
        "$f(\\mathbf{v}) = \\mathbf{A}\\mathbf{v}$ for all vectors\n",
        "$\\mathbf{v}\\in\\mathbb{R}^n$.\n",
        "To be clear, that's _one_ matrix $\\mathbf{A}$ that works for _all_ vectors\n",
        "$\\mathbf{v}\\in\\mathbb{R}^n$ simultaenously.\n",
        "The identity function $f(\\mathbf{v}) = \\mathbf{v}$ is represented by the identity matrix\n",
        "$\\mathbf{I}$.\n",
        "\n",
        "Suppose the linear map $f$ is represented by multiplication by the\n",
        "matrix $\\mathbf{A}$, then $f$ is invertible (as a function) if and only if\n",
        "the matrix inverse $\\mathbf{A}^{-1}$ exists. When $f$ is invertible,\n",
        "$f^{-1}$ is represented by the matrix $\\mathbf{A}^{-1}$.\n",
        "\n",
        "Linear mappings, for instance from $\\mathbb{R}^n$ to $\\mathbb{R}^n$ have a geometrical interpretation.\n",
        "This is most easily visualised for linear mappings $\\mathbb{R}^2\\to\\mathbb{R}^2$\n",
        "which are linear transformations of the 2d-plane.\n",
        "These are represented by $2\\times 2$ matrices.\n",
        "For instance\n",
        "$$\n",
        "\\mathbf{R}_\\theta\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "\\cos\\theta & -\\sin\\theta \\\\\n",
        "\\sin\\theta & \\cos\\theta\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "rotates points clockwise through an angle of $\\theta$ about the origin,\n",
        "while\n",
        "$$\n",
        "\\mathbf{P}\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "1 & 0 \\\\\n",
        "0 & 0\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "projects points onto the $x$-axis.\n",
        "\n",
        "Below is an animation of a linear transformation of 2d space.\n",
        "\n",
        "<img src=\n",
        "\"https://lh3.googleusercontent.com/drive-viewer/AITFw-wsDUmp9EDNYWUacsbx7oTpHqe9xh6XcWSNGwP9CdX9VkMhO6zzgsv-sXv7zMTbElTzwLHMKAjSxUz5oKiTQC_RT0g7AQ=s1600\"\n",
        "width=\"60%\" />\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JhWLD8CQrkQz"
      },
      "source": [
        "\n",
        "#### Exercises\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-491urYjqLBF"
      },
      "source": [
        "\n",
        "1. Show that for any vector space $V$, any linear map $f: V\\to V$ has $f(\\mathbf{0}) = \\mathbf{0}$\n",
        "\n",
        "2. Calculate $\\mathbf{R}_\\theta^\\top$.\n",
        "  1. How does this relate to $\\mathbf{R}_{-\\theta}$? Thinking geometrically, what transformation does $\\mathbf{R}_\\theta^\\top \\mathbf{R}_\\theta$ represent?\n",
        "  2. Argue (trying to avoid further calculation) that $\\mathbf{R}_\\theta$ is an orthogonal matrix.\n",
        "  3. If you like, you can also check directly that $\\mathbf{R}_\\theta$ is orthgonal.\n",
        "\n",
        "3. Calculate the $2\\times 2$ matrix giving the transformation in the animation.\n",
        "  - Hint: From the animation, the transformation sends\n",
        "  $$\n",
        "  \\begin{pmatrix} 2\\\\2\\end{pmatrix}\n",
        "  \\mapsto\n",
        "  \\begin{pmatrix} 6\\\\-2 \\end{pmatrix}\n",
        "  \\quad\\text{ and }\\quad\n",
        "  \\begin{pmatrix} 1\\\\2\\end{pmatrix}\n",
        "  \\mapsto\n",
        "  \\begin{pmatrix} 5\\\\0 \\end{pmatrix}\n",
        "  $$\n",
        "\n",
        "4. Convince yourself that solving the above problem is equivalent to solving the matrix equation\n",
        "$$\n",
        "\\mathbf{A}\n",
        "\\begin{pmatrix}\n",
        "2 & 1\\\\\n",
        "2 & 2\n",
        "\\end{pmatrix}\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "6 & 5\\\\\n",
        "-2 & 0\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "for $\\mathbf{A}$ and use `jax` to calculate the solution."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "TY4sBCWgru53"
      },
      "outputs": [],
      "source": [
        "# Place any code here"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YU419hcxmx6p"
      },
      "source": [
        "### Suggested Resources"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XOWFHMdiTlyv"
      },
      "source": [
        "- 3Blue1Brown (good for intuition)\n",
        "  - [Lesson on Linear Transformations](https://www.3blue1brown.com/lessons/linear-transformations)\n",
        "  - [Video on 3D Transformations](https://www.3blue1brown.com/lessons/3d-transformations)\n",
        "  - [Lesson on Matrix Multiplication](https://www.3blue1brown.com/lessons/matrix-multiplication)\n",
        "  - [Video on Non-Square Matrices](https://www.3blue1brown.com/lessons/nonsquare-matrices)\n",
        "-  Chapters 3 and 4 of the Cambridge course [Vectors and Matrices](https://dec41.user.srcf.net/notes/IA_M/vectors_and_matrices.pdf) for more advanced reading on the basics\n",
        "- Chapter 2 of the Cambridge course [Linear Algebra](https://dec41.user.srcf.net/notes/IB_M/linear_algebra.pdf) for a more mathematical viewpoint\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gV92_pCMyitu"
      },
      "source": [
        "## The Dot Product"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6j6LD0Z9xq0q"
      },
      "source": [
        "### What is the Dot Product?\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cYJjj2itXSMe"
      },
      "source": [
        "\n",
        "The _dot product_ provides a method of multiplying vectors\n",
        "to produce a scalar.\n",
        "Given $\\mathbf{a}, \\mathbf{b}\\in\\mathbb{R}^n$, their dot product is denoted\n",
        "$\\mathbf{a}\\cdot\\mathbf{b}$\n",
        "or\n",
        "$\\mathbf{a}^\\top\\mathbf{b}$\n",
        "and is calculated using the formula\n",
        "$$\n",
        "\\mathbf{a}\\cdot\\mathbf{b}\n",
        "= \\sum_{i=1}^n \\mathbf{a}_i\\mathbf{b}_i\n",
        "$$\n",
        "which is just the sum of the products of the respective entries in the vectors.\n",
        "The dot product is only defined if the two vectors have\n",
        "the same dimension.\n",
        "The dot product is sometimes called the _scalar product_\n",
        "or the _Euclidean inner product_.\n",
        "\n",
        "Here are some examples:\n",
        "\n",
        "$$\n",
        "\\begin{pmatrix}\n",
        "1\\\\2\\\\3\\\\4\n",
        "\\end{pmatrix}\n",
        "\\cdot\n",
        "\\begin{pmatrix}\n",
        "5\\\\6\\\\7\\\\8\n",
        "\\end{pmatrix}\n",
        "=\n",
        "5 + 12 + 21 + 32\n",
        "=  70\n",
        "$$\n",
        "\n",
        "$$\n",
        "\\begin{pmatrix}\n",
        "1\\\\1\\\\1\\\\1\n",
        "\\end{pmatrix}\n",
        "\\cdot\n",
        "\\begin{pmatrix}\n",
        "1\\\\2\\\\3\\\\4\n",
        "\\end{pmatrix}\n",
        "=\n",
        "1 + 2 + 3 + 4\n",
        "=  10\n",
        "$$\n",
        "\n",
        "\n",
        "$$\n",
        "\\begin{pmatrix}\n",
        "1\\\\0\n",
        "\\end{pmatrix}\n",
        "\\cdot\n",
        "\\begin{pmatrix}\n",
        "0\\\\ 1\n",
        "\\end{pmatrix}\n",
        "=\n",
        "0 + 0\n",
        "=  0\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ryt0tx82mfOe"
      },
      "source": [
        "### Notation"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sA8LX5zjXUKs"
      },
      "source": [
        "\n",
        "It's very important to note that\n",
        "when $\\mathbf{a}$ and $\\mathbf{b}$ are vectors in\n",
        "$\\mathbb{R}^n$\n",
        "then the two notations\n",
        "$$\\mathbf{a}\\cdot\\mathbf{b}$$\n",
        "and\n",
        "$$\n",
        "\\mathbf{a}^\\top \\mathbf{b}\n",
        "$$\n",
        "_mean exactly the same thing_. This is not ideal if you're seeing the dot product for the\n",
        "first time, but the two notations are used\n",
        "interchangeably in the literature so you will see both.\n",
        "\n",
        "You can check the formula\n",
        "$$\n",
        "\\mathbf{a}^\\top\\mathbf{b}\n",
        "= \\sum_{i=1}^n \\mathbf{a}_i\\mathbf{b}_i\n",
        "$$\n",
        "by viewing $\\mathbf{a}^\\top$\n",
        "as a $1\\times n$ matrix (sometimes called a row vector)\n",
        "and $\\mathbf{b}$ as an $n\\times 1$ matrix\n",
        "(sometimes called a column vector) then applying the formula\n",
        "for matrix multiplication (try it!).\n",
        "\n",
        "Consistent with the literature, **we will use both notations in this practical**."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ETISgJzakwUI"
      },
      "source": [
        "\n",
        "### The Dot Product in Machine Learning\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "A4RvHpThXXn8"
      },
      "source": [
        "\n",
        "The dot product is very common in machine learning.\n",
        "- The prediction of a linear model with weights\n",
        "$\\mathbf{w}$ and features $\\mathbf{x}$ is\n",
        "$$\n",
        "\\mathbf{w}^\\top \\mathbf{x}\n",
        "$$\n",
        "- The output of a feedforward neural network layer with\n",
        "activation $\\sigma$,\n",
        "weights $\\mathbf{w}$, bias $b$ and inputs\n",
        "$\\mathbf{x}$\n",
        "is\n",
        "$$\n",
        "\\sigma(\\mathbf{w}^\\top \\mathbf{x} + b)\n",
        "$$\n",
        "- The attention mechanism is calculated by taking the dot product\n",
        "of the key and values vectors. For instance, see\n",
        "[Attention Is All You Need](https://arxiv.org/pdf/1706.03762.pdf)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AHFonIvJx2XK"
      },
      "source": [
        "### Calculating The Dot Product in `jax`\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CQXzjNyoXZH0"
      },
      "source": [
        "\n",
        "You can calculate the dot product in `jax` using the\n",
        "function `jnp.dot`"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "GQtHo5Cuoo5w",
        "outputId": "62f8b867-fcda-4ef3-e801-0df6da711227"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array(70, dtype=int32)"
            ]
          },
          "execution_count": 4,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "a = jnp.array([1, 2, 3, 4])\n",
        "b = jnp.array([5, 6, 7, 8])\n",
        "jnp.dot(a, b)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dSxu-vRa3YMI"
      },
      "source": [
        "### Exercise\n",
        "Calculate $\\mathbf{a}\\cdot\\mathbf{b}$ when\n",
        "\n",
        "$$\n",
        "\\mathbf{a} =\n",
        "\\begin{pmatrix}\n",
        "1\\\\0\\\\2\\\\-1\n",
        "\\end{pmatrix}\n",
        "\\quad\\text{ and }\\quad\n",
        "\\mathbf{b} =\n",
        "\\begin{pmatrix}\n",
        "-2\\\\100\\\\0.5\\\\3\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "and check your answer using `jax`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "co5ZW7EFpNle"
      },
      "outputs": [],
      "source": [
        "# Place your answer here"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TJw8rddS3bnv"
      },
      "source": [
        "### Solution"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5eRkONt93ds4",
        "outputId": "ccea6097-43ce-4eb4-e267-a66d36b0db80"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array(-4., dtype=float32)"
            ]
          },
          "execution_count": 30,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "a = jnp.array([1, 0, 2, -1])\n",
        "b = jnp.array([-2, 100, 0.5, 3])\n",
        "answer = jnp.dot(a, b)\n",
        "answer"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Vm8wwlqsrQi5"
      },
      "source": [
        "### Properties\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0MbHUdawXali"
      },
      "source": [
        "\n",
        "There are some properties of the dot product that are important to know.\n",
        "All of them are easy to check using the formula (try it!).\n",
        "\n",
        "Let $\\mathbf{a}, \\mathbf{b}\\in \\mathbb{R}^n$\n",
        "be vectors, then\n",
        "- $\\mathbf{a}\\cdot\\mathbf{b} = \\mathbf{b}\\cdot\\mathbf{a}$ (commutativity)\n",
        "- $\\mathbf{a}\\cdot\\mathbf{a} \\ge 0$\n",
        "- $\\mathbf{a}\\cdot\\mathbf{a} = 0$ if and only if $\\mathbf{a}=\\mathbf{0}$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tyTvtv_-3AUT"
      },
      "source": [
        "### Exercise\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "etASA-QcXPI8"
      },
      "source": [
        "\n",
        "\n",
        "Let $\\mathbf{a}, \\mathbf{b}, \\mathbf{c} \\in \\mathbb{R}^n$\n",
        "and let $\\lambda, \\mu\\in\\mathbb{R}$.\n",
        "\n",
        "Use the formula for the inner product to prove that\n",
        "1. $\\mathbf{a}\\cdot(\\mathbf{b} + \\mathbf{c}) =\n",
        "\\mathbf{a}\\cdot\\mathbf{b} + \\mathbf{a}\\cdot\\mathbf{c}$\n",
        "2. $(\\lambda \\mathbf{a})\\cdot (\\mu \\mathbf{b}) = (\\lambda \\mu)  (\\mathbf{a}\\cdot\\mathbf{b})$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lhD_6kr239zN"
      },
      "source": [
        "### Solution\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "T1b7cAZB5S9d"
      },
      "source": [
        "\n",
        "1. Solution:\n",
        "$$\n",
        "\\begin{align*}\n",
        "\\mathbf{a}\\cdot(\\mathbf{b} + \\mathbf{c})\n",
        "&= \\sum_{i=1}^n\n",
        "\\mathbf{a}_i(\\mathbf{b}+\\mathbf{c})_i\\\\\n",
        "&= \\sum_{i=1}^n\n",
        "\\mathbf{a}_i(\\mathbf{b}_i+\\mathbf{c}_i)\\\\\n",
        "&= \\sum_{i=1}^n \\mathbf{a}_i\\mathbf{b}_i\n",
        " \\sum_{i=1}^n \\mathbf{a}_i\\mathbf{c}_i)\\\\\n",
        "&=\n",
        "\\mathbf{a}\\cdot\\mathbf{b} + \\mathbf{a}\\cdot\\mathbf{c}\n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "2. Solution:\n",
        "$$\n",
        "\\begin{align*}\n",
        "(\\lambda \\mathbf{a})\\cdot(\\mu\\mathbf{b})\n",
        "&= \\sum_{i=1}^n\n",
        "\\lambda\\mathbf{a}_i\\mu\\mathbf{b}\\\\\n",
        "&= \\lambda \\mu\\sum_{i=1}^n\n",
        "\\mathbf{a}_i\\mathbf{b}\\\\\n",
        "&= (\\lambda\\mu)(\\mathbf{a}\\cdot\\mathbf{b})\n",
        "\\end{align*}\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QtBtP6nNqeth"
      },
      "source": [
        "### Relation to Matrix Transpose [Optional]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SsPbgNt8qh-T"
      },
      "source": [
        "The dot product offers an interpretation of the matrix transpose.\n",
        "Let $\\mathbf{a}$ and $\\mathbf{b}$ be vectors in $\\mathbb{R}^n$,\n",
        "and let $\\mathbf{M}$ be an $n\\times n$ matrix.\n",
        "\n",
        "Then we have the relationship\n",
        "$$\n",
        "(\\mathbf{Ma})\\cdot \\mathbf{b}\n",
        "=\n",
        "\\mathbf{a} \\cdot (\\mathbf{M}^\\top\\mathbf{b})\n",
        "$$\n",
        "\n",
        "So if you apply a matrix to one side of the dot product, it's the\n",
        "same as applying the transpose of that matrix to the other side of the dot product.\n",
        "\n",
        "Another way of writing the same thing (using the transpose notation)\n",
        "is\n",
        "$$\n",
        "(\\mathbf{Ma})^\\top \\mathbf{b}\n",
        "=\n",
        "\\mathbf{a}^\\top (\\mathbf{M}^\\top\\mathbf{b})\n",
        "=\n",
        "\\mathbf{a}^\\top \\mathbf{M}^\\top\\mathbf{b}\n",
        "$$\n",
        "\n",
        "This means that orthogonal matrices preserve the dot product.\n",
        "Recall that the matrix $\\mathbf{R}$ is orthogonal if $\\mathbf{R}^\\top \\mathbf{R}= \\mathbf{I}$, then\n",
        "$$\n",
        "\\mathbf{Ra}\\cdot \\mathbf{Rb}\n",
        "=\n",
        "\\mathbf{a}\\cdot (\\mathbf{R}^\\top\\mathbf{R})\\mathbf{b}\n",
        "=\n",
        "\\mathbf{a}\\cdot \\mathbf{b}\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "E_PpSXjnuOkT"
      },
      "source": [
        "### Orthogonal Vectors\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mfuibp4TRpP_"
      },
      "source": [
        "\n",
        "If $\\mathbf{a}\\cdot\\mathbf{b}=0$ then we say that\n",
        "$\\mathbf{a}$ and $\\mathbf{b}$ are _orthogonal_.\n",
        "\n",
        "Orthogonality is one of the most important concepts in\n",
        "intermediate/advanced linear algebra, but in for the\n",
        "beginner level you just need to know what the word means\n",
        "and have some basic intuition.\n",
        "We go into more details in the intermediate section of the practical.\n",
        "\n",
        "In machine learning, the dot product is often used as a measure\n",
        "of similarity or statistical dependence between\n",
        "features, representations or embeddings which are represented\n",
        "by vectors.\n",
        "You will see this regularly in the literature, for instance\n",
        "in clustering applications.\n",
        "In this context, representations corresponding to orthogonal\n",
        "vectors are as independent as possible.\n",
        "\n",
        "The most common intuition for orthogonality uses the\n",
        "geometric interpretation of vectors as directed arrows to a point in space\n",
        "(see the earlier optional section). If two vectors are orthogonal,\n",
        "then the corresponding arrows are at right-angles (90 degrees) to\n",
        "one another.\n",
        "In fact, the dot product can be used to calculate the angle between\n",
        "vectors.\n",
        "See the suggested resources (or as a tutor!) for more details.\n",
        "\n",
        "**Note [Optional]**\n",
        "\n",
        "Earlier we learned about orthogonal matrices.\n",
        "An equivalent definition of an orthogonal matrix\n",
        "is a matrix whose columns (when considered as vectors)\n",
        "are orthogonal to one another.\n",
        "(Can you prove this?)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "P3YPaCucQ6Hw"
      },
      "source": [
        "### Suggested Resources"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "D_6vmqsQQ8aH"
      },
      "source": [
        "- [3Blue1Brown Video on Dot Products](https://www.3blue1brown.com/lessons/dot-products)\n",
        "- Sections 3.1-3.4 of [Math for ML Book](https://mml-book.github.io/book/mml-book.pdf) on Norms and Inner Products\n",
        "-  Chapters 2 of the Cambridge course [Vectors and Matrices](https://dec41.user.srcf.net/notes/IA_M/vectors_and_matrices.pdf) for more advanced reading on the basics\n",
        "- (Advanced) Chapter 8 of the Cambridge course [Linear Algebra](https://dec41.user.srcf.net/notes/IB_M/linear_algebra.pdf) for a more mathematical viewpoint\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "stnvDolw50Dr"
      },
      "source": [
        "## The Magnitude of a Vector\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s-GYNjnfYHNi"
      },
      "source": [
        "\n",
        "### Definition\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cK4Yb02TYF9V"
      },
      "source": [
        "\n",
        "The _magnitude_ of a vector is a measure of it's size.\n",
        "Let $\\mathbf{a}\\in\\mathbb{R}^n$, it's magnitude is defined as\n",
        "$$\n",
        "||\\mathbf{a}||\n",
        "=\n",
        "\\sqrt{\\mathbf{a}\\cdot\\mathbf{a}}\n",
        "$$\n",
        "The magnitude of a vector is sometimes reffered to as\n",
        "the _Euclidean norm_ of the vector or\n",
        "the _length_ of the vector (don't confuse this with the number of elements in the array!).\n",
        "\n",
        "Recall from the properties of the dot product that for all vectors\n",
        "$\\mathbf{a}\\in \\mathbb{R}^n$\n",
        "$$\n",
        "\\mathbf{a}\\cdot\\mathbf{a} \\ge 0\n",
        "$$\n",
        "This means the square root in the definition is always valid.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0XlPu-gXYDb3"
      },
      "source": [
        "\n",
        "### Notation"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BRaIZxQsYEjg"
      },
      "source": [
        "\n",
        "Note that\n",
        "$$\n",
        "||\\mathbf{a}||^2\n",
        "=\n",
        "\\mathbf{a}^\\top\\mathbf{a}\n",
        "$$\n",
        "You will often see the magnitude of a vector written this way instead.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tbeQdY1eYCEd"
      },
      "source": [
        "\n",
        "### Examples\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qfHsrShcYAJ3"
      },
      "source": [
        "\n",
        "- Let\n",
        "$$\\mathbf{a} = \\begin{pmatrix} 1\\\\2\\\\3\\\\4 \\end{pmatrix}$$\n",
        "Then\n",
        "$$\n",
        "||\\mathbf{a}||\n",
        "= \\sqrt{\\mathbf{a}\\cdot\\mathbf{a}}\n",
        "= \\sqrt{1 + 2^2 + 3^2 + 4^2}\n",
        "= \\sqrt{30}\n",
        "$$\n",
        "\n",
        "- Let\n",
        "$$\\mathbf{a} = \\begin{pmatrix} 1\\\\0\\\\0 \\end{pmatrix}$$\n",
        "Then\n",
        "$$\n",
        "||\\mathbf{a}||\n",
        "= 1\n",
        "$$\n",
        "\n",
        "- Let\n",
        "$$\\mathbf{a} = \\begin{pmatrix} 1\\\\-1 \\end{pmatrix}$$\n",
        "Then\n",
        "$$\n",
        "||\\mathbf{a}||\n",
        "= \\sqrt{1^2 + (-1)^2} = \\sqrt{2}\n",
        "$$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "I18f_6qj8Vrj"
      },
      "source": [
        "### Exercise\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "t9EG1JDNMj9b"
      },
      "source": [
        "\n",
        "Use the formula for the dot product to show that\n",
        "$$\n",
        "||\\mathbf{a}||\n",
        "= \\sqrt{\\sum_{i=1}^n \\mathbf{a}_i^2}\n",
        "$$\n",
        "\n",
        "This is a very important and useful formula!\n",
        "It is sometimes used as the definition of the vector magnitude."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0uYNTCKy7Tnd"
      },
      "source": [
        "#### Solution"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2L8ckROl7WLZ"
      },
      "source": [
        "$$\n",
        "||\\mathbf{a}||^2 = \\mathbf{a}\\cdot\\mathbf{a} = \\sum_{i=1}^n \\mathbf{a}_i^2\n",
        "$$\n",
        "so\n",
        "$$\n",
        "||\\mathbf{a}|| = \\sqrt{\\sum_{i=1}^n \\mathbf{a}_i^2}\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fhph87asCRu4"
      },
      "source": [
        "### Exercise"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "voTmL0w3MhPS"
      },
      "source": [
        "\n",
        "Use the above formula to show that if $\\mathbf{a} \\in \\mathbb{R}^n$\n",
        "is the vector of all $1$s, so $\\mathbf{a}_i = 1$ for $i=1, 2, \\dots, n$ then\n",
        "$$\n",
        "||\\mathbf{a}|| = \\sqrt{n}\n",
        "$$\n",
        "\n",
        "For instance, this implies that if\n",
        "$$\n",
        "\\mathbf{a}\n",
        "=\n",
        "\\begin{pmatrix}\n",
        "1\\\\1\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "then $||\\mathbf{a}|| = \\sqrt{2}$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AFZo9TCXDV3n"
      },
      "source": [
        "#### Solution"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bcGoa9ACC-tR"
      },
      "source": [
        "$$\n",
        "||\\mathbf{a}||\n",
        "= \\sqrt{\\sum_{i=1}^n \\mathbf{a}_i^2}\n",
        "= \\sqrt{\\sum_{i=1}^n 1^2}\n",
        "= \\sqrt{n}\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Wp3P6p_fD0Fr"
      },
      "source": [
        "### Calculating the Vector Magnitude in `jax`\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "U2kBwYZeNdSK"
      },
      "source": [
        "\n",
        "The vector magnitude can be computed easily in `jax` using the\n",
        "function `jnp.linalg.norm`"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "9lAbLdzCM6x6",
        "outputId": "dd8eb84d-97fa-4a44-ca0f-8969d3910538"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array(5., dtype=float32)"
            ]
          },
          "execution_count": 11,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "a = jnp.array([3, 4])\n",
        "jnp.linalg.norm(a)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IHAbGImWD49R",
        "outputId": "8f9c02c0-c627-4fcf-b4a9-5d824084d1c4"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array(50.0062, dtype=float32)"
            ]
          },
          "execution_count": 12,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "a = jnp.array([0.1, 0.5, 0.6, 50])\n",
        "jnp.linalg.norm(a)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "q17kKasINa5K"
      },
      "source": [
        "#### Exercise"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dsT0332DNf33"
      },
      "source": [
        "Choose a vector $\\mathbf{a}$ and\n",
        "use `jax` to check the following formula in that case\n",
        "$$\n",
        "||\\mathbf{a}||\n",
        "=\n",
        "\\sqrt{\\sum_{i=1}^n \\mathbf{a}_i^2}\n",
        "$$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "GRk76YqgN_Um"
      },
      "outputs": [],
      "source": [
        "# Place your code here"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-X2F3RUPOA6u"
      },
      "source": [
        "##### Solution"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "esWXe34COC-Y"
      },
      "outputs": [],
      "source": [
        "a = jnp.array([1, 2, 3, 4, 5]) # any old vector\n",
        "lhs = jnp.linalg.norm(a) # calculate the magnitude, left hand side of the formula\n",
        "rhs = jnp.sqrt(jnp.sum(a**2)) # calculate the right hand side of the formula\n",
        "assert jnp.allclose(lhs, rhs) # assert that the formula holds within numerical tolerance"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jBBVtXU4Abxj"
      },
      "source": [
        "### Properties of the Vector Magnitude\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FgDrP1kPD8WO"
      },
      "source": [
        "#### _The magnitude of a vector is always non-negative_\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4ZdfyV7LIuCx"
      },
      "source": [
        "\n",
        "For all $\\mathbf{a}\\in\\mathbb{R}^n$\n",
        "$$\n",
        "||\\mathbf{a}|| \\ge 0\n",
        "$$\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JRNhy9p4GsLV"
      },
      "source": [
        "\n",
        "##### Proof\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8t0c5G2OGuFC"
      },
      "source": [
        "From the properties of the dot product we know that\n",
        "for all\n",
        "$\\mathbf{a}\\in \\mathbb{R}^n$\n",
        "we have\n",
        "$\n",
        "\\mathbf{a}\\cdot\\mathbf{a} \\ge 0\n",
        "$.\n",
        "So\n",
        "$$\n",
        "||\\mathbf{a}|| = \\sqrt{\\mathbf{a}\\cdot\\mathbf{a}} \\ge 0\n",
        "$$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "escmgX--Gx90"
      },
      "source": [
        "#### The magnitude is $0$ if and only if the vector is $\\mathbf{0}$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TH_VSUxlIvqJ"
      },
      "source": [
        "\n",
        "For all $\\mathbf{a}\\in\\mathbb{R}^n$\n",
        "$$\n",
        "||\\mathbf{a}|| = 0\n",
        "\\quad\\text{if and only if}\\quad\n",
        "\\mathbf{a}=\\mathbf{0}\n",
        "$$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "osoP_M1OHeCK"
      },
      "source": [
        "\n",
        "##### Proof\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YA8utb3eHeCS"
      },
      "source": [
        "From the properties of the dot product we know that\n",
        "for all\n",
        "$\\mathbf{a}\\in \\mathbb{R}^n$\n",
        "we have\n",
        "$\n",
        "\\mathbf{a}\\cdot\\mathbf{a} = 0\n",
        "$\n",
        "if and only if $\\mathbf{a}=\\mathbf{0}$,\n",
        "then use the formula $||\\mathbf{a}||=\\mathbf{a}\\cdot\\mathbf{a}$.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zC70L-dnHZRk"
      },
      "source": [
        "#### Vector Normalisation\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XHeEVKP1IxVe"
      },
      "source": [
        "\n",
        "The vector magnitude satisfies the following property.\n",
        "For all $\\lambda \\in \\mathbb{R}$ and all vectors $\\mathbf{a}$\n",
        "we have\n",
        "$$\n",
        "||\\lambda \\mathbf{a}|| = |\\lambda| \\times||\\mathbf{a}||\n",
        "$$\n",
        "This means that _any vector can be scaled to have magnitude 1_.\n",
        "In particular, the vector\n",
        "$$\n",
        "{\\mathbf{\\hat{a}}}= \\frac{1}{||\\mathbf{a}||}\\mathbf{a}\n",
        "$$\n",
        "always has $||{\\mathbf{\\hat{a}}}|| = 1$.\n",
        "A vector with magnitude 1 is sometimes called a _unit norm vector_.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QUQ3wK9eIlye"
      },
      "source": [
        "##### Proof"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "L8wUnbeyIolZ"
      },
      "source": [
        "$$\n",
        "\\begin{align*}\n",
        "||\\lambda \\mathbf{a}||\n",
        "&=\n",
        "\\sqrt{\n",
        "  \\sum_{i=1}^n \\lambda^2 \\mathbf{a}_i^2\n",
        "}\\\\\n",
        "&=\n",
        "|\\lambda|\n",
        "\\sqrt{\n",
        "  \\sum_{i=1}^n \\mathbf{a}_i^2\n",
        "}\\\\\n",
        "&=\n",
        "|\\lambda| \\times ||\\mathbf{a}||\n",
        "\\end{align*}\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cVfKnTKIIpcv"
      },
      "source": [
        "#### Triangle Rule [Optional]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elMKCP1nGXRI"
      },
      "source": [
        "For any vectors $\\mathbf{a}, \\mathbf{b} \\in \\mathbb{R}^n$ we have\n",
        "$$\n",
        "||\\mathbf{a} + \\mathbf{b}|| \\le ||\\mathbf{a}|| + ||\\mathbf{b}||\n",
        "$$\n",
        "with equality if and only if $\\mathbf{a}$ and $\\mathbf{b}$ are\n",
        "orthogonal.\n",
        "\n",
        "The triangle rule is an incredibly important inequality."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B_xihiaFZBNK"
      },
      "source": [
        "#### Cauchy-Schwarz Inequality [Optional]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "P1UY058iZEft"
      },
      "source": [
        "For any vectors $\\mathbf{a}, \\mathbf{b} \\in \\mathbb{R}^n$ we have\n",
        "$$\n",
        "|\\mathbf{a}\\cdot \\mathbf{b}| \\le ||\\mathbf{a}||||\\mathbf{b}||\n",
        "$$\n",
        "with equality if and only if $\\mathbf{a} = \\lambda \\mathbf{b}$\n",
        "for some scalar $\\lambda \\in \\mathbf{R}$ (i.e. the vectors are _parallel_).\n",
        "\n",
        "The Cauchy-Schwarz inequality is also an incredibly important inequality."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2pZ4MxmIywnv"
      },
      "source": [
        "### Suggested Resources\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xVIiCR-lQZtw"
      },
      "source": [
        "- Sections 3.1-3.4 of [Math for ML Book](https://mml-book.github.io/book/mml-book.pdf) on Norms and Inner Products"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "M263Nxob3RXG"
      },
      "source": [
        "## Example: Ridge Regression\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "60e_od-o0FvF"
      },
      "source": [
        "It's time for us to put all the tools we have developed so far to work! This section will be structured as follows: At each subsection, we will illustrate the mathematics followed by a practical example."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aJ5j25nMY6p3"
      },
      "source": [
        "### A little bit of Backgroud on Linear regression"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EEJkDWjkfwGp"
      },
      "source": [
        "Suppose we are given $n$ samples $\\{ x_i, y_i \\}^n_{i=1}$ where each $x_i= (x_{i1}, \\dots x_{ip})$ is an input vector with $p$ number of features and each $y_i \\in \\mathbb{R}$ is the target for each $x_i$. The linear regression problem is then to approximate the target value given each input vector as a linear combination of its features.\n",
        "\n",
        "$$ \\eta(x_i) = \\beta_0 + \\sum_{j=1}^p x_{ij} \\beta_j $$\n",
        "\n",
        "Here $\\eta$ is our model and its parameters are the regression weights $\\beta = (\\beta_1, \\dots, \\beta_p) \\in \\mathbb{R}^N$ and the bias term $\\beta_0 \\in \\mathbb{R}$.\n",
        "\n",
        "#### Something to note here\n",
        "\n",
        "Suppose we have only a single feature per input variable, $p=1$, we are trying to map to a corresponding target variable, the linear regression equation for a single input simpliy becomes:\n",
        "\n",
        "$$\\eta(x_i) = \\beta_0 + x \\beta_1$$\n",
        "\n",
        "Replacing the variable names $\\eta \\rightarrow y$, $\\beta_0 \\rightarrow b$ and $\\beta_1 \\rightarrow m$ here this becomes the familiar equation for a straight line!\n",
        "\n",
        "$$ y = mx + b $$\n",
        "\n",
        "In fact, this is exactly what we are trying to do in linear regression. Our goal is to find a 'line' that bests fits our data! This is ofcourse an over simplification since we are actually trying to find a 'linear combination' of each input such that we can produce the corresponding output. But the straight line equation demonstrates where 'linear' regression gets its name from."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "51WXDneuZBLG"
      },
      "source": [
        "### The linear regression objective function"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "l9K3XRkTfqs7"
      },
      "source": [
        "In order to quantify how well our line fits the data, we need some metric. The most standard of which is the mean squared error. Which is nothing but the average euclidean norm between a predicited value from our model and the true target value. This objective functoin $J(\\beta)$ can be expressed as:\n",
        "\n",
        "$$ J(\\beta) = \\left\\{ \\frac{1}{n} \\sum_{i=1}^n \\left( y_i - \\beta_0 - \\sum_{j=1}^p x_{ij} \\beta_j \\right)^2 \\right\\} $$\n",
        "\n",
        "The goal is then to find a set of parameters for our model which will minimise this objective function. We can express this as:\n",
        "\n",
        "$$ \\underset{\\beta_0, \\beta}{\\text{arg min}} \\left\\{ \\frac{1}{n} \\sum_{i=1}^n \\left( y_i - \\beta_0 - \\sum_{j=1}^p x_{ij} \\beta_j \\right)^2 \\right\\} $$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "L5ooN5saZDnC"
      },
      "source": [
        "### Ridge regression objective function"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dytqPzn8fn1m"
      },
      "source": [
        "Ridge regression extends the notion of linear regression by adding an additional term to the objective function we are trying to minimise. We won't get into detail here about why this is done, but the term is added is the  square of the L2 norm (or the squared euclidean norm) of the model parameters exclusding the bias term. Our cost function then becomes:\n",
        "\n",
        "$$ J(\\beta) = \\left\\{ \\frac{1}{n} \\sum_{i=1}^n \\left( y_i - \\beta_0 - \\sum_{j=1}^p x_{ij} \\beta_j \\right)^2 \\right\\} + \\lambda \\sum_{j=1}^p \\beta_j^2$$\n",
        "\n",
        "With the goal being to find $\\beta$ such that:\n",
        "\n",
        "$$ \\underset{\\beta_0, \\beta}{\\text{arg min}} \\left\\{ \\frac{1}{n} \\sum_{i=1}^n \\left( y_i - \\beta_0 - \\sum_{j=1}^p x_{ij} \\beta_j \\right)^2 \\right\\} + \\lambda \\sum_{j=1}^p \\beta_j^2$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sBlYs_SST8ph"
      },
      "source": [
        "### The ridge regression objective function as a matrix equation"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BbuvVSy2fkbQ"
      },
      "source": [
        "We have so far only expressed our ridge regression objective function as explicit summations. You might have noticed that some of these summations look very similar to those we saw in the section on matrices. Since we generaly arrange our input vectors in to a design matrix $X$ and since we will have a vector of target $Y$ we can re-express our objective function using matrix notation:\n",
        "$$ \\begin{equation}\n",
        "\\begin{aligned}\n",
        "J(\\beta) &= \\left\\{ \\frac{1}{n} \\sum_{i=1}^n \\left( y_i - \\beta_0 - \\sum_{j=1}^p x_{ij} \\beta_j \\right)^2 \\right\\} + \\lambda \\sum_{j=1}^p \\beta_j^2 \\\\\n",
        "& = (Y - X \\beta)^T (Y - X \\beta) + \\lambda \\beta^T \\beta\\\\\n",
        "& = \\| Y - X \\beta \\|_2^2 + \\lambda \\| \\beta \\|_2^2\n",
        "\\end{aligned}\n",
        "\\end{equation} $$\n",
        "\n",
        "Here, when using the term $\\beta$ we are only referring to the model parameters and exclusing the bias term $\\beta_0$.The bias term needs to be handled carefully."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tn8cbZghsPp2"
      },
      "source": [
        "### Group task:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7slxb-7xtldZ"
      },
      "source": [
        "Discuss with those around you how we can handle the bias term"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vHq53rFyYw-t"
      },
      "source": [
        "### Minimising the ridge regression objective function"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "h2KYBZRvfg5E"
      },
      "source": [
        "In order to minimise a function we need to set its first derivative to zero. We do this as follows. We first expand the objective function to become:\n",
        "$$\\begin{equation}\n",
        "\\begin{aligned}\n",
        "J(\\beta)&=(Y - X \\beta)^T (Y - X \\beta) + \\lambda \\beta^T \\beta \\\\\n",
        "J(\\beta)&=Y^T Y - Y^T X \\beta - \\beta^T X^T Y +  \\beta^T X^T X \\beta + \\lambda \\beta^T \\beta\n",
        "\\end{aligned}\n",
        "\\end{equation}$$\n",
        "\n",
        "Since $Y^T X \\beta$ and $\\beta^T X^T Y$ are scalar values they are equal. So we can simplify the above to be:\n",
        "\n",
        "$$\\begin{equation}\n",
        "\\begin{aligned}\n",
        "J(\\beta)&=Y^T Y - 2 \\beta^T X^T Y +  \\beta^T X^T X \\beta + \\lambda \\beta^T \\beta\n",
        "\\end{aligned}\n",
        "\\end{equation}$$\n",
        "\n",
        "We now take the derivative of the above w.r.t. $\\beta$ and set it equal to zero to obtain\n",
        "$$\\begin{equation}\n",
        "\\begin{aligned}\n",
        "\\frac{\\partial J(\\beta)}{\\partial \\beta}  \n",
        "&= - 2 X^T Y +  2X^T X \\beta + 2\\lambda \\beta = 0\n",
        "\\end{aligned}\n",
        "\\end{equation}$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BSk8RDm3d1dn"
      },
      "source": [
        "### Exercise\n",
        "Solving the minimised ridge regression objective function for the optimal model parameters."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GvR9TFdLfcUl"
      },
      "source": [
        "See if you can solve the linear equation derived above:\n",
        "$$ - 2 X^T Y +  2X^T X \\beta + 2\\lambda \\beta = 0 $$ for the optimal model parameters $\\beta$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Amsv0KNPeKLl"
      },
      "source": [
        "### Solution"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SIolOQqlgOGg"
      },
      "source": [
        "Starting with the linear equation we have derived:\n",
        "$$ - 2 X^T Y +  2X^T X \\beta + 2\\lambda \\beta = 0 $$\n",
        "Which can be rearranged as\n",
        "$$2X^T X \\beta + 2\\lambda \\beta = 2 X^T Y $$\n",
        "Dividing by 2 yields:\n",
        "$$X^T X \\beta + \\lambda \\beta = X^T Y $$\n",
        "We now introduce the identity matrix $I$:\n",
        "$$X^T X \\beta + \\lambda I \\beta = X^T Y $$\n",
        "Grouping like terms yileds:\n",
        "$$(X^T X + \\lambda I) \\beta = X^T Y $$\n",
        "Since $X^T X + \\lambda I$ is an invertible matrix we can multiply our equation from the left by the matrix inverse to yield:\n",
        "$$(X^T X + \\lambda I)^{-1}(X^T X + \\lambda I) \\beta =(X^T X + \\lambda I)^{-1} X^T Y $$\n",
        "Which gives our result for $\\beta$ as\n",
        "$$\\beta =(X^T X + \\lambda I)^{-1} X^T Y $$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lfzg9pfEVorf"
      },
      "source": [
        "### Practical application exercise"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5ZpipFb4wLQv"
      },
      "source": [
        "\n",
        "Suppose we have we have 3 examples with 3 features each given as $x_1 = [1.2, 3.2, 0.9]$, $x_2 = [0.2, 3.1, 2.4]$ and $x_3 = [10.9, 4.0, 2.1]$ pack these into a design matrix."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1p3tAolSWRZP"
      },
      "source": [
        "### Solution"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qJN5czfwwbfh"
      },
      "source": [
        "$$\\mathbf{X} =\n",
        "\\begin{bmatrix}\n",
        "1.2 & 3.2 & 0.9\\\\\n",
        "0.2 & 3.1 & 2.4 \\\\\n",
        "10.9 & 4.0 & 2.1\n",
        "\\end{bmatrix}$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BBySVv0TW4fg"
      },
      "source": [
        "### Code example:\n",
        "To create this design matrix in JAX, we can use the `.stack()` method from `jax.numpy` as follows:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 69
        },
        "id": "d71H53UqVl3G",
        "outputId": "8777eaa8-5957-4368-b91c-fe881162485e"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Array([[ 1.2,  3.2,  0.9],\n",
              "       [ 0.2,  3.1,  2.4],\n",
              "       [10.9,  4. ,  2.1]], dtype=float32)"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "x_1 = jnp.array([1.2, 3.2, 0.9])\n",
        "x_2 = jnp.array([0.2, 3.1, 2.4])\n",
        "x_3 = jnp.array([10.9, 4.0, 2.1])\n",
        "\n",
        "X = jnp.stack([x_1, x_2, x_3])\n",
        "display(X)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yoHsn1iyw2X4"
      },
      "source": [
        "### Exercise:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tYUiqBWoyLJT"
      },
      "source": [
        "Now, given a target vector $Y = [3.95, 15.62,130.07]$ see if you can solve the equation we derived previously $$\\beta = (X^T X + \\lambda I)^{-1}X^T Y$$\n",
        "for the optimal model parameters $\\beta$ to fit the function using JAX. For this example use a $\\lambda$ value of 0.01."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "S7gYfZwKyf9O"
      },
      "outputs": [],
      "source": [
        "Y = jnp.array([3.95, 15.62,130.07])\n",
        "lambda_ = 0.01\n",
        "X_T = ...\n",
        "I = ...\n",
        "\n",
        "beta = ..."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NDMyvMfDYYav"
      },
      "source": [
        "### Solution:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "IhWevjkWyroh"
      },
      "outputs": [],
      "source": [
        "# Compute X transpose\n",
        "X_T = X.T\n",
        "# Create an identity matrix with the correct shape.\n",
        "# Since we have 3 examples, with 3 features each calling `X.shape` will\n",
        "# yield a tuple of shape (3, 3). Hence we can construct the identity matrix\n",
        "# by using the first dimension of `X.shape`\n",
        "I = jnp.eye(X.shape[0])\n",
        "\n",
        "# We can then solve using the `linalg.inv()` method from jax.numpy, but\n",
        "# remember from earlier in the practical that this is not the best way...\n",
        "# (Don't do it like this in practice!)\n",
        "beta_ = jnp.linalg.inv(X_T @ X + lambda_ * I) @ (X_T @ Y)\n",
        "\n",
        "# Although the above method matches the form of the math, you will\n",
        "# recall from earlier in the practical that it is more accurate and numerically\n",
        "# stable to use `linalg.solve`. Do it this way in practice!\n",
        "beta = jnp.linalg.solve(X_T @ X + lambda_ * I, X_T @ Y)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VxAke0QRa3zl"
      },
      "source": [
        "# Linear Algebra II <font color='orange'>`Intermediate`</font>\n",
        "\n",
        "<!--\n",
        "<img src=\n",
        "\"https://lh3.googleusercontent.com/drive-viewer/AITFw-wdkXm3HR6ycdwKX5C7Mu2pvqHXSqXDzHn8rN_F4xWXRANc-5Upq9A9mjBEL3vyYA-VcWZ-9oyb35Pq1zFkuVD5kK49=s1600\"\n",
        "width=\"100%\" /> -->\n",
        "\n",
        "Imagine confronting a data maze – countless points that defy easy comprehension. Dimensionality reduction is your map to navigate this labyrinth. It's like viewing a grand painting through a prism, capturing its essence by focusing on key colors and shapes.\n",
        "\n",
        "With techniques like PCA, we distill complex data into essential dimensions, simplifying while preserving patterns. Think of a dataset about fruits: dimensionality reduction might unveil that color, size, and sweetness capture most variation.\n",
        "\n",
        "`Projections`, `determinants and traces`, `eigendecomposition`, and `PCA` each hold a puzzle piece. Projections condense data, determinants unveil transformations, eigendecomposition reveals structures, and PCA unifies these insights.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-ZUp8i37dFbU"
      },
      "source": [
        "## **Projections**\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yzlzbeL-d7x8"
      },
      "source": [
        "\n",
        "**Projection Intuitively**\n",
        "\n",
        ">Imagine you have a flashlight in a fixed position ($x$) in space ($V$) that can shine light in any direction you point it at (like a laser). Now, let's say you have a beam of light (which we'll call a vector from the flashlight to the wall) and a wall (our subspace $U$). You can point your flashlight in any direction, but you want to shine it on the wall in a way that gets it as close as possible to where the beam hits the wall ($\\pi_U(x)$). That's what projection is all about!\n",
        "1. **Getting Closest:** When you want to shine your flashlight as close as possible to the wall, you need to minimize how far away it is from the wall. That is, you want to minimize the length of the beam ($x-\\pi_U(x)$). We measure this distance using the length of the beam ($\\left\\|x-\\pi_U(x)\\right\\|$).\n",
        "2. **Math Talk:** When we talk in numbers, we describe the position where the beam hits the wall ($\\pi_U(x)$) using a basis $b$ of the subspace $U$. That is, $\\pi_U(x)=λb$. You can think of $λ$ as saying by how much we should move in the direction $b$ along the wall to reach the point $\\pi_U(x)$.\n",
        "3. **Orthogonal Friendliness:** The length of the beam is the shortest when the path it takes is at a right angle to the wall. That is, when the inner product (denoted $\\left\\langle \\cdot, \\cdot \\right\\rangle$) between the beam and the basis is zero ($\\left\\langle\\pi_U(x)-x, b\\right\\rangle$=0). This is like you pointing the flashlight directly towards the wall.\n",
        "4. **Building a Tool:** To help us do this for any light beam (vector) and any wall (subspace), we create a special tool called the \"projection matrix\" ($\\mathbf{P}_\\pi$). This tool takes any flashlight ($x$) and adjusts its light beam so it's super close to the wall ($U$).\n",
        ">\n",
        "> So, the projection is like holding your flashlight in a way that it shines as close as possible to the wall, while still respecting the wall's rules (you can not move the wall). This helps us understand how vectors and spaces interact in a neat and organized way.\n",
        "\n",
        "**Projection Mathematically**\n",
        "\n",
        "> ***\n",
        "> <font color='Yellow'>`DEFINITION`</font> `Projection`\n",
        ">\n",
        "> Let $V$ be a vector space and $U \\subseteq V$ a subspace of $V$.\n",
        ">\n",
        "> - A linear mapping $\\pi: V \\rightarrow U$ is called a projection if $\\pi^2:=\\pi \\circ \\pi=\\pi$\n",
        "> - $\\mathbf{P}_\\pi$ is a projection matrix if $\\mathbf{P}_\\pi^2=\\mathbf{P}_\\pi$.\n",
        "> ***\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EuRry98LfKxS"
      },
      "source": [
        "**Group Task:**\n",
        "\n",
        "Discuss as a group what this deffinition is saying and why it makes sense, keeping in mind the given intuition.\n",
        "\n",
        ">Hint: The notation $\\pi^2$ or $\\pi \\circ \\pi$ means applying the function $\\pi$ twice (i.e $\\pi^2:=\\pi \\circ \\pi:=\\pi(\\pi(x))$.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ii__Bc27epiJ"
      },
      "source": [
        "### 1.1 Projecting onto One Dimensional Subspaces (Line, $\\mathbb{R}^1$) - <font color='green'>`Beginner`</font>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4PbcFsfAibBu"
      },
      "source": [
        "\n",
        "\n",
        "<img src=\n",
        "\"https://lh3.googleusercontent.com/drive-viewer/AITFw-yth8ydsmqZyqNZBNDktk9plo8525uElAtDf3KTt3MT_uCh8FPGp0z_yDiY2qZj3Y_QowAxvyP5_vVNkb3X-gw4ifs-GA=s1600\"\n",
        "width=\"60%\" />\n",
        "\n",
        "The projection $\\pi_U(\\mathbf{x})$ is closest to $\\mathbf{x}$ when the distance $\\left\\|\\mathbf{x}-\\pi_U(\\mathbf{x})\\right\\|$ between them is minimized. This occurs when the difference $\\pi_U(\\mathbf{x})-\\mathbf{x}$ is perpendicular (orthogonal) to the subspace $U$. This perpendicularity is evident in the fact that their inner product $\\left\\langle\\pi_U(\\mathbf{x})-\\mathbf{x}, \\mathbf{b}\\right\\rangle$ is zero.\n",
        "\n",
        "Because the projection $\\pi_U(\\mathbf{x})$ maps $\\mathbf{x}$ into the subspace $U$, it can be represented as a scalar multiple of the basis vector $\\mathbf{b}$, denoted as $\\lambda \\mathbf{b}$, where $\\lambda$ is a real number.\n",
        "\n",
        "Hence, to build the projection matrix $\\mathbf{P}_\\pi$ that maps any $\\mathbf{x} \\in \\mathbb{R}^n$ onto $U$, the following steps are used:\n",
        "- Determine $\\lambda$ coordinate\n",
        "- Determine $\\pi_U(\\mathbf{x}) \\in U$\n",
        "- Finally construct $\\mathbf{P}_\\pi$\n",
        "\n",
        "> Finding the coordinate $\\lambda$\n",
        "- From the orthogonality condition we have that\n",
        "$$\n",
        "\\begin{aligned}\n",
        "0 & =\\left\\langle\\mathbf{x}-\\pi_u(\\mathbf{x}), \\mathbf{b}\\right\\rangle \\\\\n",
        "& =\\langle\\mathbf{x}-\\lambda \\mathbf{b}, \\mathbf{b}\\rangle \\\\\n",
        "& =\\langle\\mathbf{x}, \\mathbf{b}\\rangle-\\lambda\\langle\\mathbf{b}, \\mathbf{b}\\rangle \\text { from the bilinearity of }\\langle\\cdot, \\cdot\\rangle\n",
        "\\end{aligned}\n",
        "$$\n",
        "- We can now rearrange to obtain\n",
        "$$\n",
        "\\begin{aligned}\n",
        "\\lambda & =\\frac{\\langle\\mathbf{x}, \\mathbf{b}\\rangle}{\\langle\\mathbf{b}, \\mathbf{b}\\rangle}=\\frac{\\langle\\mathbf{b}, \\mathbf{x}\\rangle}{\\|\\mathbf{b}\\|^2}\n",
        "\\end{aligned}\n",
        "$$\n",
        "- In simpler terms, the coefficient $\\lambda$ is found by dividing the dot product of $\\mathbf{x}$ and $\\mathbf{b}$ by the dot product of $\\mathbf{b}$ with itself, which is equivalent to the squared length of $\\mathbf{b}$.\n",
        "\n",
        "> Finding the projection point $\\pi_U(\\mathbf{x}) \\in U$\n",
        "- Since $\\pi_U(\\mathbf{x})=\\lambda \\mathbf{b}$ it immediately follows that\n",
        "$$\n",
        "\\pi_U(\\mathbf{x})=\\lambda \\mathbf{b}=\\frac{\\langle\\mathbf{b}, \\mathbf{x}\\rangle}{\\langle\\mathbf{b}, \\mathbf{b}\\rangle} \\mathbf{b}\n",
        "$$\n",
        "- If the inner product we are using is the dot product, this simplifies to\n",
        "$$\n",
        "\\pi_U(\\mathbf{x})=\\frac{\\mathbf{b}^T \\mathbf{x}}{\\mathbf{b}^T\\mathbf{b}} \\mathbf{b}\n",
        "$$\n",
        "\n",
        "> Finding the projection matrix $\\mathbf{P}_\\pi$\n",
        "- Using the dot product we can make the following observation\n",
        "$$\n",
        "\\begin{aligned}\n",
        "\\pi_U(\\mathbf{x})=\\lambda \\mathbf{b} & =\\mathbf{b} \\lambda \\\\\n",
        "& =\\mathbf{b} \\frac{\\mathbf{b}^T \\mathbf{x}}{\\mathbf{b}^T\\mathbf{b}} \\\\\n",
        "& =\\frac{\\mathbf{b} \\mathbf{b}^T}{\\mathbf{b}^T\\mathbf{b}} \\mathbf{x}\n",
        "\\end{aligned}\n",
        "$$\n",
        "Recall that $\\mathbf{b}$ is a $n \\times 1$ matrix and $\\mathbf{b}^T$ is a $1 \\times n$ matrix, therefore $\\mathbf{b b}^T$ is a $n \\times n$ matrix (and is also symmetric). We call $\\mathbf{b b}^T$ an \"outer product\" (similar to the inner product $\\mathbf{b^T b}$)\n",
        "- It follows that\n",
        "$$\n",
        "\\mathbf{P}_\\pi=\\frac{\\mathbf{b} \\mathbf{b}^T}{\\mathbf{b}^T\\mathbf{b}}\n",
        "$$\n",
        "\n",
        "***\n",
        "<font color='Yellow'>`EXAMPLE`</font>\n",
        "\n",
        "Consider an example where we want to project a 2d point  $x=(64,17.76)$ onto the line spanned by the base vector\n",
        "$b = \\left[\\begin{array}{c}\n",
        "1 \\\\\n",
        "0.41\n",
        "\\end{array}\\right]$.\n",
        "\n",
        "Projection matrix:\n",
        "$$\n",
        "\\begin{aligned}\n",
        "& \\boldsymbol{P}_\\pi=\\frac{\\boldsymbol{b} b^T}{\\mathbf{b}^T\\mathbf{b}}=\\frac{1}{\\boldsymbol{b}^T \\boldsymbol{b}} \\boldsymbol{b} \\boldsymbol{b}^{\\boldsymbol{T}} \\\\\n",
        "& \\boldsymbol{P}_\\pi=\\frac{1}{\\left[\\begin{array}{ll}\n",
        "1 & 0.41\n",
        "\\end{array}\\right]\\left[\\begin{array}{c}\n",
        "1 \\\\\n",
        "0.41\n",
        "\\end{array}\\right]}\\left(\\left[\\begin{array}{c}\n",
        "1 \\\\\n",
        "0.41\n",
        "\\end{array}\\right]\\left[\\begin{array}{ll}\n",
        "1 & 0.41\n",
        "\\end{array}\\right]\\right) \\\\\n",
        "& \\boldsymbol{P}_\\pi=\\frac{1}{1.17}\\left(\\left[\\begin{array}{cc}\n",
        "1 & 0.41 \\\\\n",
        "0.41 & 0.17\n",
        "\\end{array}\\right]\\right) \\\\\n",
        "& \\boldsymbol{P}_\\pi=\\left[\\begin{array}{ll}\n",
        "0.85 & 0.35 \\\\\n",
        "0.35 & 0.15\n",
        "\\end{array}\\right]\n",
        "\\end{aligned}\n",
        "$$\n",
        "Projecting point:\n",
        "$$\n",
        "\\begin{aligned}\n",
        "\\pi_U(x)=\\boldsymbol{P}_\\pi x=\\left[\\begin{array}{ll}\n",
        "0.85 & 0.35 \\\\\n",
        "0.35 & 0.15\n",
        "\\end{array}\\right]\\left[\\begin{array}{c}\n",
        "64 \\\\\n",
        "17.76\n",
        "\\end{array}\\right] & =\\left[\\begin{array}{c}\n",
        "60.62 \\\\\n",
        "25.06\n",
        "\\end{array}\\right] \\\\\n",
        "& =60.62\\left[\\begin{array}{c}\n",
        "1 \\\\\n",
        "0.41\n",
        "\\end{array}\\right]\n",
        "\\end{aligned}\n",
        "$$\n",
        "\n",
        "***"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "axeZiGJxibBw"
      },
      "source": [
        "**Math Task:**\n",
        "\n",
        "In a machine learning project, a data scientist wants to reduce the dimensionality of their dataset by projecting each data point onto a euclidean subspace spanned by a set of basis vectors. Suppose a data point $x=\\left[\\begin{array}{c}-1 \\\\ 3 \\\\ 1\\end{array}\\right]$ is given, and the subspace $U$ is spanned by the basis vector $b=\\left[\\begin{array}{c}0 \\\\ -2 \\\\ 3\\end{array}\\right]$.\n",
        "\n",
        "a) Determine the orthogonal projection $\\pi_U(x)$ of $\\mathrm{x}$ onto $U$\n",
        "\n",
        "b) Determine the distance $d(x, U)$.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "g5VRp8QDYPqz"
      },
      "source": [
        "`ANSWER`\n",
        "Sure, I can help you solve this problem step by step.\n",
        "\n",
        "a) To determine the orthogonal projection $\\pi_U(x)$ of the vector $x$ onto the subspace $U$ spanned by the basis vectors $u_1$ and $u_2$, we follow the same proccess as before.\n",
        "\n",
        "\n",
        "Projection matrix:\n",
        "$$\n",
        "\\begin{aligned}\n",
        "& \\boldsymbol{P}_\\pi=\\frac{\\boldsymbol{b} \\boldsymbol{b}^T}{\\boldsymbol{b}^T\\boldsymbol{b}}=\\frac{1}{\\boldsymbol{b}^T \\boldsymbol{b}} \\boldsymbol{b} \\boldsymbol{b}^{\\boldsymbol{T}} \\\\\n",
        "& \\boldsymbol{P}_\\pi=\\frac{1}{\\left[\\begin{array}{lll}\n",
        "0 & -2 & 3\n",
        "\\end{array}\\right]\\left[\\begin{array}{c}\n",
        "0 \\\\\n",
        "-2 \\\\\n",
        "3\n",
        "\\end{array}\\right]}\\left(\\left[\\begin{array}{c}\n",
        "0 \\\\\n",
        "-2 \\\\\n",
        "3\n",
        "\\end{array}\\right]\\left[\\begin{array}{lll}\n",
        "0 & -2 & 3\n",
        "\\end{array}\\right]\\right) \\\\\n",
        "& \\boldsymbol{P}_\\pi=\\frac{1}{13}\\left(\\left[\\begin{array}{ccc}\n",
        "0 & 0 & 0 \\\\\n",
        "0 & 4 & -6 \\\\\n",
        "0 & -6 & 9\n",
        "\\end{array}\\right]\\right) \\\\\n",
        "& \\boldsymbol{P}_\\pi=\\left[\\begin{array}{lll}\n",
        "0 & 0 & 0 \\\\\n",
        "0 & \\frac{4}{13} & \\frac{-6}{13} \\\\\n",
        "0 & \\frac{-6}{13} & \\frac{9}{13}\n",
        "\\end{array}\\right]\n",
        "\\end{aligned}\n",
        "$$\n",
        "Projecting point:\n",
        "$$\n",
        "\\begin{aligned}\n",
        "\\pi_U(x)=\\boldsymbol{P}_\\pi x=\\left[\\begin{array}{lll}\n",
        "0 & 0 & 0 \\\\\n",
        "0 & \\frac{4}{13} & \\frac{-6}{13} \\\\\n",
        "0 & \\frac{-6}{13} & \\frac{9}{13}\n",
        "\\end{array}\\right]\\left[\\begin{array}{c}\n",
        "-1 \\\\\n",
        "3 \\\\\n",
        "1\n",
        "\\end{array}\\right] & =\\left[\\begin{array}{c}\n",
        "0 \\\\\n",
        "\\frac{6}{13} \\\\\n",
        "\\frac{-9}{13}\n",
        "\\end{array}\\right]\n",
        "\\end{aligned}\n",
        "$$\n",
        "\n",
        "So, the orthogonal projection $\\pi_U(x)$ of the vector $x$ onto the subspace $U$ is $\\left[\\begin{array}{c}\n",
        "0 \\\\\n",
        "\\frac{6}{13} \\\\\n",
        "\\frac{-9}{13}\n",
        "\\end{array}\\right] $.\n",
        "\n",
        "b) To determine the distance $d(x, U)$ between the vector $x$ and the subspace $U$, we can use the formula:\n",
        "\n",
        "$$d(x, U) = \\|x - \\pi_U(x)\\|$$\n",
        "\n",
        "Where $\\|\\cdot\\|$ represents the Euclidean norm (magnitude) of a vector.\n",
        "\n",
        "First, calculate the difference between $x$ and its projection:\n",
        "\n",
        "$$x - \\pi_U(x) = \\left[\\begin{array}{c}-1 \\\\ 3 \\\\ 1\\end{array}\\right] - \\left[\\begin{array}{c}0 \\\\ \\frac{6}{13} \\\\ \\frac{-9}{13}\\end{array}\\right] = \\left[\\begin{array}{c}-1 \\\\ \\frac{33}{13} \\\\ \\frac{4}{13}\\end{array}\\right]$$\n",
        "\n",
        "Then, calculate the Euclidean norm of this difference:\n",
        "\n",
        "$$\\|x - \\pi_U(x)\\| = \\sqrt{(-1)^2 + \\left(\\frac{33}{13}\\right)^2 + \\left(\\frac{4}{13}\\right)^2} = 2.75$$\n",
        "\n",
        "So, the distance between the vector $x$ and the subspace $U$ is approximately 3.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Rd7xAVznfBQU"
      },
      "source": [
        "### 1.2 Projecting onto General Subspaces ($\\mathbb{R}^n$) - <font color='orange'>`Intermediate`</font>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jWlwCNlqfBQV"
      },
      "source": [
        "\n",
        "<img src=\n",
        "\"https://lh3.googleusercontent.com/drive-viewer/AITFw-zEGASdI7YZJ-iaHSysatou2W2FwdIochnElA5cNw6QHlP2vElrjCh86dAd-__wHiwd_dfRZUFh3DuhOoQjtxrsNXxJNQ=s1600\"\n",
        "width=\"60%\" />\n",
        "\n",
        "Assume that $\\left(\\mathbf{b}_1, \\ldots, \\mathbf{b}_m\\right)$ is an ordered basis of $U$\n",
        "- We know that for any $\\mathbf{x} \\in \\mathbb{R}^n$ that $\\pi_U(\\mathbf{x}) \\in U$,\n",
        "$$\n",
        "\\begin{aligned}\n",
        "& \\pi_U(\\mathbf{x})=\\sum_{i=1}^m \\lambda_i \\mathbf{b}_i=\\mathbf{B} \\boldsymbol{\\lambda}, \\\\\n",
        "& \\mathbf{B}=\\left[\\mathbf{b}_1, \\ldots, \\mathbf{b}_m\\right] \\in \\mathbb{R}^{n \\times m}, \\lambda=\\left[\\lambda_1, \\ldots, \\lambda_m\\right]^T \\in \\mathbb{R}^m\n",
        "\\end{aligned}\n",
        "$$\n",
        "\n",
        "Hence, we can follow the same procedure as before to find the projection matrix, just generalised to n-dimensional subspaces. That is,\n",
        "- Determine $\\lambda$ coordinate\n",
        "- Determine $\\pi_U(\\mathbf{x}) \\in U$\n",
        "- Finally construct $\\mathbf{P}_\\pi$.\n",
        "\n",
        "> Finding the coordinate $\\lambda$\n",
        "- From the orthogonality condition we have that\n",
        "$$\n",
        "\\begin{aligned}\n",
        "\\mathbf{b}_1^T(\\mathbf{x}-\\mathbf{B} \\boldsymbol{\\lambda}) & =0 \\\\\n",
        "\\vdots & \\\\\n",
        "\\mathbf{b}_m^T(\\mathbf{x}-\\mathbf{B} \\boldsymbol{\\lambda}) & =0\n",
        "\\end{aligned}\n",
        "$$\n",
        "is a homogeneous linear equation system. Hence,\n",
        "$$\n",
        "\\begin{aligned}\n",
        "& {\\left[\\begin{array}{c}\n",
        "\\mathbf{b}_1^T \\\\\n",
        "\\vdots \\\\\n",
        "\\mathbf{b}_m^T\n",
        "\\end{array}\\right][\\mathbf{x}-\\mathbf{B} \\boldsymbol{\\lambda}]=\\mathbf{0} } \\\\\n",
        "\\Longleftrightarrow & \\mathbf{B}^T(\\mathbf{x}-\\mathbf{B} \\boldsymbol{\\lambda})=\\mathbf{0} \\\\\n",
        "\\Longleftrightarrow & \\mathbf{B}^T \\mathbf{B} \\boldsymbol{\\lambda}=\\mathbf{B}^T \\mathbf{x} \\\\\n",
        "\\lambda & =\\left(\\mathbf{B}^T \\mathbf{B}\\right)^{-1} \\mathbf{B}^T \\mathbf{x}\n",
        "\\end{aligned}\n",
        "$$\n",
        "\n",
        "> Finding the projection point $\\pi_U(\\mathbf{x}) \\in U$ :\n",
        "$$\n",
        "\\begin{aligned}\n",
        "\\pi_U(\\mathbf{x})=\\sum_{i=1}^m \\lambda_i \\mathbf{b}_i & =\\mathbf{B} \\boldsymbol{\\lambda} \\\\\n",
        "& =\\mathbf{B}\\left(\\mathbf{B}^T \\mathbf{B}\\right)^{-1} \\mathbf{B}^T \\mathbf{x}\n",
        "\\end{aligned}\n",
        "$$\n",
        "\n",
        "> Find the projection matrix $\\mathbf{P}_\\pi$ :\n",
        "$$\n",
        "\\begin{gathered}\n",
        "\\mathbf{P}_\\pi \\mathbf{x}=\\pi_U(\\mathbf{x}) \\\\\n",
        "\\mathbf{P}_\\pi=\\mathbf{B}\\left(\\mathbf{B}^T \\mathbf{B}\\right)^{-1} \\mathbf{B}^T\n",
        "\\end{gathered}\n",
        "$$\n",
        "\n",
        "This ability to do projections actually gives us an interesting perspective on solving systems of linear equations $Ax=b$.\n",
        "- If $\\boldsymbol{A}$ is invertible:\n",
        " - $\\mathrm{x}=\\mathrm{A}^{-1} \\mathrm{~b}$\n",
        "- If $\\mathbf{A}$ is not invertible:\n",
        " - $\\mathbf{A}^{\\mathrm{T}} \\mathbf{A x}=\\mathbf{A}^{\\mathrm{T}} \\mathrm{b}$\n",
        " - $\\left(\\mathbf{A}^{\\mathrm{T}} \\mathbf{A}\\right)^{-1} \\mathbf{A}^{\\mathrm{T}} \\mathbf{A x}=\\left(\\mathbf{A}^{\\mathrm{T}} \\mathbf{A}\\right)^{-\\mathbf{1}} \\mathbf{A}^{\\mathrm{T}} \\mathbf{b}$\n",
        " - $\\mathrm{x}=\\left(\\mathbf{A}^{\\mathrm{T}} \\mathbf{A}\\right)^{-\\mathbf{1}} \\mathbf{A}^{\\mathrm{T}} \\mathrm{b}$ if we assume that the symmetric matrix $\\mathbf{A}^{\\mathrm{T}} \\mathbf{A}$ is invertible (which happens when the column vectors of $\\mathbf{A}$ are linearly independent).\n",
        "- $\\left(\\mathbf{A}^{\\mathrm{T}} \\mathbf{A}\\right)^{-\\mathbf{1}} \\mathbf{A}^{\\mathrm{T}}$ is called the **Moore-Penrose pseudo-inverse** and $\\mathrm{x}$ is the best approximate solution.\n",
        "- Projection view: $\\boldsymbol{\\lambda}=\\left(\\mathbf{A}^{\\mathrm{T}} \\mathbf{A}\\right)^{-\\mathbf{1}} \\mathbf{A}^{\\mathrm{T}} \\mathrm{b}$ is the least-squares solution to the system."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iQJtf6sCfBQY"
      },
      "source": [
        "**Code Task:**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "LICrxTN5fBQZ"
      },
      "outputs": [],
      "source": [
        "def projection_matrix(B):\n",
        "    \"\"\"Compute the projection matrix onto the space spanned by `B`\n",
        "    Args:\n",
        "        B: ndarray of dimension (D, M), the basis for the subspace\n",
        "\n",
        "    Returns:\n",
        "        P: the projection matrix\n",
        "    \"\"\"\n",
        "    return np.eye(B.shape[0]) # <-- EDIT THIS to compute the projection matrix\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "id": "URLJOqNqDZoX"
      },
      "outputs": [],
      "source": [
        "# @title Run me to test your code\n",
        "\n",
        "def test_projection_matrix(projection_matrix):\n",
        "  B = np.array([[1,2,3],[1,5,6]])\n",
        "  assert (projection_matrix(B) == (B @ np.linalg.inv(B.T @ B) @ B.T)).all(), \"The projection matrix is incorrect\"\n",
        "  print(\"Nice! Your answer looks correct.\")\n",
        "\n",
        "test_projection_matrix(projection_matrix)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "wdrxamLfDZoX"
      },
      "outputs": [],
      "source": [
        "# @title Answer to code task (Try not to peek until you've given it a good try!')\n",
        "\n",
        "def projection_matrix(B):\n",
        "    \"\"\"Compute the projection matrix onto the space spanned by `B`\n",
        "    Args:\n",
        "        B: ndarray of dimension (D, M), the basis for the subspace\n",
        "\n",
        "    Returns:\n",
        "        P: the projection matrix\n",
        "    \"\"\"\n",
        "    return (B @ np.linalg.inv(B.T @ B) @ B.T)\n",
        "\n",
        "test_projection_matrix(projection_matrix)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7SrT6swYgCm9"
      },
      "source": [
        "### 1.3 Orthonormal Basis - <font color='green'>`Advanced`</font>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tYV9_wJcgCm-"
      },
      "source": [
        "Using our new found ability of projecting vectors onto subspaces, we can transform any basis (set of base vectors) into an orthonormal set of base vectors.\n",
        "\n",
        "***\n",
        "<font color='Yellow'>`DEFINITION`</font> `Orthonormal Basis`\n",
        "\n",
        "Consider an $n$-dimensional vector space $V$ and a basis $\\left\\{\\mathbf{b}_1, \\ldots, \\mathbf{b}_n\\right\\}$ of $V$. If\n",
        "$$\n",
        "\\begin{aligned}\n",
        "& \\left\\langle\\mathbf{b}_i, \\mathbf{b}_j\\right\\rangle=0 \\text { for } i \\neq j \\\\\n",
        "& \\left\\langle\\mathbf{b}_i, \\mathbf{b}_j\\right\\rangle=1 \\text { for } i=j\n",
        "\\end{aligned}\n",
        "$$\n",
        "holds for all $i, j=1, \\ldots, n$ then the basis is called an orthonormal basis (ONB).\n",
        "***\n",
        "\n",
        "They are very useful in several situations. For example, if we are projecting vectors using an orthonormal basis for $U$, then\n",
        "$$\n",
        "\\begin{aligned}\n",
        "\\pi_U(\\mathbf{x}) & =\\mathbf{B} \\boldsymbol{\\lambda} \\\\\n",
        "& =\\mathbf{B}\\left(\\mathbf{B}^T \\mathbf{B}\\right)^{-1} \\mathbf{B}^T \\mathbf{x} \\\\\n",
        "& =\\mathbf{B I}^{-1} \\mathbf{B}^T \\mathbf{x} \\\\\n",
        "& =\\mathbf{B} \\mathbf{B}^T \\mathbf{x}\n",
        "\\end{aligned}\n",
        "$$\n",
        "\n",
        "which requires much less calculations.\n",
        "\n",
        "Now, how do we get an orthonormal basis? A popular approach is `Gram-Schmidt Orthogonalization`. It obtains the orthogonal basis $\\left(\\mathbf{u}_1, \\ldots, \\mathbf{u}_n\\right)$ from any basis $\\left(\\mathbf{b}_1, \\ldots, \\mathbf{b}_n\\right)$ of $V$ as follows:\n",
        "$$\n",
        "\\begin{aligned}\n",
        "& \\mathbf{u}_1:=\\mathbf{b}_1 \\\\\n",
        "& \\mathbf{u}_k:=\\mathbf{b}_k-\\pi_{\\text {span }\\left[\\mathbf{u}_1, \\ldots, \\mathbf{u}_{k-1}\\right]}\\left(\\mathbf{b}_k\\right), k=2, \\ldots, n\n",
        "\\end{aligned}\n",
        "$$\n",
        "If we go step further and rather use $\\hat{\\mathbf{u}}_k=\\frac{\\mathbf{u}_k}{\\left\\|\\mathbf{u}_k\\right\\|}$ we have an orthonormal basis!\n",
        "\n",
        "<img src=\n",
        "\"https://lh3.googleusercontent.com/drive-viewer/AITFw-xuvxK1QVMSvjcRLoPDShh8MIBV4lpEug8HedPtJvbYfrnIKjgN0e5CthxgJLEmwAEJMoUInVAHt_2vfYForMSojggu8w=s1600\"\n",
        "width=\"60%\" />\n",
        "\n",
        "***\n",
        "<font color='Yellow'>`EXAMPLE`</font>\n",
        "\n",
        "Consider a basis $\\left(\\boldsymbol{b}_1, \\boldsymbol{b}_2\\right)$ of $\\mathbb{R}^2$, where\n",
        "$$\n",
        "\\boldsymbol{b}_1=\\left[\\begin{array}{l}\n",
        "2 \\\\\n",
        "0\n",
        "\\end{array}\\right], \\quad \\boldsymbol{b}_2=\\left[\\begin{array}{l}\n",
        "1 \\\\\n",
        "1\n",
        "\\end{array}\\right].\n",
        "$$\n",
        "Then\n",
        "$$\n",
        "\\boldsymbol{u}_1:=\\boldsymbol{b}_1=\\left[\\begin{array}{l}\n",
        "2 \\\\\n",
        "0\n",
        "\\end{array}\\right], \\\\\n",
        "\\boldsymbol{u}_2:=\\boldsymbol{b}_2-\\pi_{\\operatorname{span}\\left[\\boldsymbol{u}_1\\right]}\\left(\\boldsymbol{b}_2\\right)=\\left[\\begin{array}{l}\n",
        "1 \\\\\n",
        "1\n",
        "\\end{array}\\right]-\\left[\\begin{array}{ll}\n",
        "1 & 0 \\\\\n",
        "0 & 0\n",
        "\\end{array}\\right]\\left[\\begin{array}{l}\n",
        "1 \\\\\n",
        "1\n",
        "\\end{array}\\right]=\\left[\\begin{array}{l}\n",
        "0 \\\\\n",
        "1\n",
        "\\end{array}\\right]\n",
        "$$\n",
        "\n",
        "Verify for that $u_1$ and $u_2$ are indeed orthogonal by checking if their dot product is zero (meaning their angle is 90 degrees). That is, if $u_1^Tu_2=0$.\n",
        "***"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6tWFVqp-gCm_"
      },
      "source": [
        "**Math Task:**\n",
        "\n",
        "In a finance project, a data scientist wants to build a portfolio of stocks that minimizes risk and maximizes return. To do this, the data scientist can use a technique called principal component analysis, which involves projecting the returns of individual stocks onto an orthogonal basis. Suppose the returns of 4 stocks are represented by the basis of linearly independent vectors $b_1=\\left[\\begin{array}{c}3 \\\\ 6 \\\\ -1 \\\\ -3\\end{array}\\right]$ and $b_2=\\left[\\begin{array}{c}-2 \\\\ -3 \\\\ -4 \\\\ 6\\end{array}\\right]$. Use the Gram-Schmidt method to convert this basis to an orthogonal basis $\\left(c_1, c_2\\right)$.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WFTseLDNVUjx"
      },
      "source": [
        "> `ANSWER`\n",
        "  <!-- \\begin{aligned}\n",
        "& c_1 = {\\left[\\begin{array}{c}\n",
        "3 \\\\\n",
        "6 \\\\\n",
        "-1 \\\\\n",
        "-3\n",
        "\\end{array}\\right]},\n",
        "& c_2 = {\\left[\\begin{array}{c}\n",
        "\\frac{4}{55} \\\\\n",
        "\\frac{63}{55} \\\\\n",
        "-\\frac{258}{55} \\\\\n",
        "\\frac{216}{55}\n",
        "\\end{array}\\right] .}\n",
        "\\end{aligned} -->\n",
        "\n",
        "**1. Find $c_1$:**\n",
        "$c_1$ is simply $b_1$, so we can keep it as it is:\n",
        "$$c_1 = \\begin{bmatrix} 3 \\\\ 6 \\\\ -1 \\\\ -3 \\end{bmatrix}$$\n",
        "\n",
        "**2. Find the orthogonal projection of $b_2$ onto $c_1$:**\n",
        "The orthogonal projection of $b_2$ onto $c_1$ can be calculated as follows:\n",
        "$$c_2 = b_2 - \\frac{b_2 \\cdot c_1}{c_1 \\cdot c_1} c_1 = b_2 - \\frac{b_2^T c_1}{c_1^T c_1} c_1$$\n",
        "\n",
        "Substituting the values, calculating the inner products and simplifying:\n",
        "$$c_2 = \\left[\\begin{array}{c}\n",
        "\\frac{4}{55} \\\\\n",
        "\\frac{63}{55} \\\\\n",
        "-\\frac{258}{55} \\\\\n",
        "\\frac{216}{55}\n",
        "\\end{array}\\right]$$\n",
        "\n",
        "So, the orthogonal basis is $\\{c_1, c_2\\}$:\n",
        "$$c_1 = \\begin{bmatrix} 3 \\\\ 6 \\\\ -1 \\\\ -3 \\end{bmatrix}, \\quad c_2 = \\left[\\begin{array}{c}\n",
        "\\frac{4}{55} \\\\\n",
        "\\frac{63}{55} \\\\\n",
        "-\\frac{258}{55} \\\\\n",
        "\\frac{216}{55}\n",
        "\\end{array}\\right]$$\n",
        "\n",
        "Note: The vectors $c_1$ and $c_2$ are not normalized in this approach."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "e9NW58_3hAg2"
      },
      "source": [
        "## **Determinants and Traces**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AZUxzLWDeB1p"
      },
      "source": [
        "Imagine you're a gardener tending to a pair of flowerbeds. You have two types of flowers, roses and tulips, and you want to understand how the flowers' growth is influenced by sunlight and water. You record the following data in a matrix:\n",
        "\n",
        "$\n",
        "A=\\begin{bmatrix}\n",
        "1 & 1 \\\\\n",
        "1 & 0\n",
        "\\end{bmatrix}\n",
        "$\n",
        "\n",
        "<img src=\n",
        "\"https://lh3.googleusercontent.com/drive-viewer/AITFw-yYjQcoB7PLHmdOmhIAEZj4UZP40ZeCB8bJb1RQ_-PJRbm6vkdiVMNqC_BQX0vscvE1EHOXgolBdZDoBIzW8tXQqGxoTA=s1600\"\n",
        "width=\"60%\" />\n",
        "\n",
        "In this gardening context, the determinant of the matrix could represent a measure of the overall health and vitality of the flowerbeds. A positive determinant value, like 10, might signify that both sunlight and water are contributing positively to the growth of both roses and tulips, resulting in flourishing flowerbeds. On the other hand, a negative determinant value like -10 could indicate an imbalance in the growth factors, potentially leading to unhealthy or stunted growth of the flowers.\n",
        "\n",
        "The determinant of this matrix is -1."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bA_2coZvhAg3"
      },
      "source": [
        "### 2.1 Determinant - <font color='blue'>`Beginner`</font>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "q1I8M0zkhAg3"
      },
      "source": [
        "Geometrically, the determinant of a matrix represents the scaling factor by which the matrix transforms the area (or volume in higher dimensions) of a shape. It indicates how much the shape is stretched or compressed during the transformation. If the determinant is positive, the shape expands; if it's negative, the shape flips and expands; and if it's zero, the transformation collapses the shape into lower dimensions.\n",
        "\n",
        "Say we are in 2d space ($n=2$), and we are looking for the determinant of the matrix\n",
        "$\\boldsymbol{A}=\\left[\\begin{array}{ll}a_{11} & a_{12} \\\\ a_{21} & a_{22}\\end{array}\\right]$.\n",
        "\n",
        "<img src=\n",
        "\"https://lh3.googleusercontent.com/drive-viewer/AITFw-xIyfDYWTJ0bK2pBIvUTmEPNuceXe4Z89vck6wKY0kgq_lhckkHpuETS9qfXIlxwghpFnBaprLVf-bZs2SLWj3juz0X5Q=s1600\"\n",
        "width=\"40%\" />\n",
        "\n",
        "Then, $\\operatorname{det}(\\boldsymbol{A})=\\left|\\begin{array}{ll}a_{11} & a_{12} \\\\ a_{21} & a_{22}\\end{array}\\right|=a_{11} a_{22}-a_{12} a_{21}$\n",
        "\n",
        "***\n",
        "<font color='Yellow'>`EXAMPLE`</font>\n",
        "\n",
        "$\\begin{aligned} \\operatorname{det}(\\boldsymbol{A})=\\left|\\begin{array}{ll}1 & 2 \\\\ 3 & 4\\end{array}\\right| =(1*4-2*3) =(4-6) =-2\\end{aligned}$\n",
        "\n",
        "$\\begin{aligned} \\operatorname{det}(\\boldsymbol{A})=\\left|\\begin{array}{ll}1 & 0 \\\\ 3 & 4\\end{array}\\right| =(1*4-0*3) =(4-0) =4\\end{aligned}$\n",
        "\n",
        "$\\begin{aligned} \\operatorname{det}(\\boldsymbol{A})=\\left|\\begin{array}{ll}1 & 2 \\\\ 3 & 0\\end{array}\\right| =(1*0-2*3) =(1-6) =-6\\end{aligned}$\n",
        "***\n",
        "\n",
        "In general,\n",
        "\n",
        "\n",
        "$\\begin{aligned} \\text{ If } n=1,& \\\\ & \\operatorname{det}(A)=\\left|a_{11}\\right|=a_{11}\\end{aligned}$\n",
        "\n",
        "$\\begin{aligned} \\text{ If } n=2,& \\\\ & \\operatorname{det}(\\boldsymbol{A})=\\left|\\begin{array}{ll}a_{11} & a_{12} \\\\ a_{21} & a_{22}\\end{array}\\right|=a_{11} a_{22}-a_{12} a_{21}\\end{aligned}$\n",
        "\n",
        "$\\begin{aligned} \\text{ If } n=3,& \\\\ & \\operatorname{det}(\\boldsymbol{A})=\\left|\\begin{array}{lll}a_{11} & a_{12} & a_{13} \\\\ a_{21} & a_{22} & a_{23} \\\\ a_{31} & a_{32} & a_{33}\\end{array}\\right| \\\\ & =(-1)^{1+1} a_{11}\\left|\\begin{array}{ll}a_{22} & a_{23} \\\\ a_{32} & a_{33}\\end{array}\\right|+(-1)^{1+2} a_{12}\\left|\\begin{array}{ll}a_{21} & a_{23} \\\\ a_{31} & a_{33}\\end{array}\\right|+(-1)^{1+3} a_{13}\\left|\\begin{array}{ll}a_{21} & a_{22} \\\\ a_{31} & a_{32}\\end{array}\\right| \\\\ & \\end{aligned}$\n",
        "\n",
        "Finally, the determinant can also be used to determine if a matrix is invertable.\n",
        "That is because the determinant of a matrix and its inverse are inversely proportional. As the determinant of a matrix grows, the scale of its transformation increases, and its inverse's scale reduces accordingly. If a matrix has a large determinant, its inverse will have a smaller one, and vice versa. When the determinant is zero, the matrix is not invertible.\n",
        "To see precisely why, let's derive the formula for the inverse of a $2\\times2$ matrix by using gaussian elimation.\n",
        "\n",
        "$\\boldsymbol{A}=\\left[\\begin{array}{ll}a_{11} & a_{12} \\\\ a_{21} & a_{22}\\end{array}\\right]$\n",
        "\n",
        "$\\left[\\begin{array}{ll|ll}a_{11} & a_{12} & 1 & 0 \\\\ a_{21} & a_{22} & 0 & 1\\end{array}\\right]$\n",
        "\n",
        "$\\left[\\begin{array}{cc|cc}1 & 0 & \\frac{a_{22}}{a_{11} a_{22}-a_{12} a_{21}} & -\\frac{a_{12}}{a_{11} a_{22}-a_{12} a_{21}} \\\\ 0 & 1 & \\frac{-a_{21}}{a_{11} a_{22}-a_{12} a_{21}} & \\frac{a_{11}}{a_{11} a_{22}-a_{12} a_{21}}\\end{array}\\right]$\n",
        "\n",
        "$\\begin{aligned} \\boldsymbol{A}^{-\\mathbf{1}} & =\\frac{1}{a_{11} a_{22}-a_{12} a_{21}}\\left[\\begin{array}{cc}a_{22} & -a_{12} \\\\ -a_{21} & a_{11}\\end{array}\\right] \\\\ \\boldsymbol{A}^{-\\mathbf{1}} & =\\frac{1}{\\operatorname{det}(\\boldsymbol{A})}\\left[\\begin{array}{cc}a_{22} & -a_{12} \\\\ -a_{21} & a_{11}\\end{array}\\right]\\end{aligned}$\n",
        "\n",
        "We can see how the determinant of a matrix and its inverse are inversely proportional, and why the inverse does not exist when $det(A)=0$.\n",
        "\n",
        "***\n",
        "<font color='Yellow'>`THEOREM`</font> `Invertability`\n",
        "\n",
        "For any square matrix $\\mathbf{A} \\in \\mathbb{R}^{n \\times n}$ it holds that $\\mathbf{A}$ is invertible if and only if $\\operatorname{det}(\\mathbf{A}) \\neq 0$.\n",
        "***\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0Ue8vgIqhAg4"
      },
      "source": [
        "**Math Task:**\n",
        "\n",
        "You're an astronaut exploring a distant planet known for its peculiar crystal formations. In your analysis, you come across a magnificent crystal matrix that seems to hold the secrets of the planet's energy. The matrix describes the relationship between two types of energy sources: solar rays and magnetic pulses.\n",
        "\n",
        "The crystal matrix you've gathered looks like this:\n",
        "\n",
        "$$\n",
        "\\begin{bmatrix}\n",
        "5 & 2 \\\\\n",
        "-3 & 7\n",
        "\\end{bmatrix}\n",
        "$$\n",
        "\n",
        "Your mission directive is to calculate the determinant of this crystal matrix to determine the energy balance and potential stability of the planet's ecosystem. Compute the determinant to unveil the enigmatic forces governing this alien world's energy harmony."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PZfPUmqV39Ht"
      },
      "source": [
        "`ANSWER`\n",
        "To calculate the determinant of this matrix, you use the formula for a 2x2 matrix:\n",
        "\n",
        "$$\n",
        "det(A) = (5 \\times 7) - (2 \\times -3) = 35 + 6 = 41\n",
        "$$\n",
        "\n",
        "So, the determinant of the matrix is 41.\n",
        "\n",
        "In this context of the astronaut exploring a distant planet with crystal formations and energy sources, the determinant of the matrix might represent a measure of the equilibrium or balance between the solar ray and magnetic pulse energies. A determinant value greater than zero (such as 41) could imply a favorable energy balance that contributes to the stability of the planet's ecosystem, while a determinant value less than zero might indicate an imbalance or potential instability in the energy dynamics. However, since this is a hypothetical scenario, the precise interpretation could vary based on the specific context and scientific principles of the fictional world."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BKtMEnRkhAg9"
      },
      "source": [
        "### 2.2 Trace - <font color='blue'>`Beginner`</font>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZnFpRAi_hAg-"
      },
      "source": [
        "\n",
        "The trace is another important property of a transformation matrix. The trace of a matrix represents the sum of its diagonal elements. It corresponds to the sum of the stretches along the principal axes of a transformation. The trace captures the overall scaling effect of the transformation.\n",
        "\n",
        "\n",
        "***\n",
        "<font color='Yellow'>`DEFINITION`</font> `TRACE`\n",
        "\n",
        "The trace of a square matrix $\\mathbf{A} \\in \\mathbb{R}^{n \\times n}$ is defined as\n",
        "$$\n",
        "\\operatorname{tr}(\\mathbf{A})=\\sum_{i=1}^n a_{i i}\n",
        "$$\n",
        "***\n",
        "\n",
        "***\n",
        "<font color='Yellow'>`EXAMPLE`</font>\n",
        "\n",
        "$\\begin{aligned} \\operatorname{tr}(\\boldsymbol{A})=tr\\left[\\begin{array}{ll}1 & 2 \\\\ 3 & 4\\end{array}\\right] = 1+4 =5\\end{aligned}$\n",
        "\n",
        "$\\begin{aligned} \\operatorname{tr}(\\boldsymbol{A})=tr\\left[\\begin{array}{ll}1 & 0 \\\\ 3 & 4\\end{array}\\right] = 1+4 =5\\end{aligned}$\n",
        "\n",
        "$\\begin{aligned} \\operatorname{tr}(\\boldsymbol{A})=tr\\left[\\begin{array}{ll}1 & 2 \\\\ 3 & 0\\end{array}\\right] = 1+0 = 1\\end{aligned}$\n",
        "***\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "og6LBsyjaCWy"
      },
      "source": [
        "**Math Task:**\n",
        "\n",
        "Calculate the trace of the following matrix from the previous task:\n",
        "$$\n",
        "A=\\begin{bmatrix}\n",
        "5 & 2 \\\\\n",
        "-3 & 7\n",
        "\\end{bmatrix}\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EWki5mHpaNvc"
      },
      "source": [
        "`ANSWER`\n",
        "\n",
        "$\\begin{aligned} \\operatorname{tr}(\\boldsymbol{A})=tr\\left[\\begin{array}{ll}5 & 2 \\\\ -3 & 7\\end{array}\\right] = 5+7 = 12\\end{aligned}$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5Ckb2SjTPxgD"
      },
      "source": [
        "## **Eigenvalues and Eigenvectors**\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0Df8uXYpeIs3"
      },
      "source": [
        "Imagine you're an archaeologist investigating an ancient civilization's pottery collection. To understand the underlying patterns in the designs, you decide to apply principal component analysis (PCA) to the collection's motifs. Each pottery piece is adorned with unique combinations of two motifs: spirals and geometric shapes.\n",
        "\n",
        "After careful measurements, you construct the following covariance matrix based on the occurrences of these motifs:\n",
        "\n",
        "$\\boldsymbol{A}=\\left[\\begin{array}{cc}\n",
        "0.5 & 0 \\\\\n",
        "0 & 2\n",
        "\\end{array}\\right]$\n",
        "\n",
        "To perform PCA, you need to first perform eigendecomposition on this covariance matrix to unveil the fundamental artistic components (eigenvectors) that shape the pottery aesthetics and their corresponding artistic importance (eigenvalues).\n",
        "\n",
        "The following figure illustrates the transformation represented by $A$---the points on the leftmost figure are transformed to those shown on the rightmost). The arrows in the middle show the two eigenvectors and each $\\lambda$ is their respective eigenvalue.\n",
        "\n",
        "<img src=\n",
        "\"https://lh3.googleusercontent.com/drive-viewer/AITFw-yhWf-K5IS6rw0jpuR20SAjxpGTWTJ6WtGtoY2dNrQoiGuwR9Msld8I_ZeEAiepWOk2kfuRlpfR--QKQyujOxj6RapwGg=s1600\"\n",
        "width=\"60%\" />\n",
        "\n",
        "An eigenvalue of 2 suggests that the motif of geometric shapes has more variation compared to the motif of spirals, which has an eigenvalue of 0.5. The eigenvectors provide insights into how the motifs are related and how they contribute to the overall pattern variations observed in the pottery collection.\n",
        "\n",
        "Say the covariance matrix was\n",
        "$\\boldsymbol{A}=\\left[\\begin{array}{cc}\n",
        "1 & -1 \\\\\n",
        "-1 & 1\n",
        "\\end{array}\\right]$\n",
        "instead. Then the figure would instead be as shown below.\n",
        "\n",
        "<img src=\n",
        "\"https://lh3.googleusercontent.com/drive-viewer/AITFw-yxfZ21Sf782jxEJTAX0X7FRKG7O5ByeA3DZO292dBor33Wjpgt6BTwtZEwg0uWSM65grEiFjmQvnavrgCrg2N7pCiWmA=s1600\"\n",
        "width=\"60%\" />\n",
        "\n",
        "Eigenvalues of 0 and 2 imply that the matrix transformation stretches along one direction (associated with eigenvalue 2) while completely collapsing along another direction (associated with eigenvalue 0).\n",
        "\n",
        "In the context of the pottery motifs, this would mean that one of the motifs (represented by the eigenvector associated with eigenvalue 0) has no variability and doesn't contribute to the pattern differences in the collection. This could imply that one of the motifs is constant across all pottery pieces.\n",
        "\n",
        "The motif associated with the eigenvector corresponding to eigenvalue 2 would be responsible for all the variability and pattern differences observed in the pottery collection. This motif would be the primary contributor to the variations in design.\n",
        "\n",
        "In simpler terms, one motif remains unchanged across all pieces, while the other motif has varying patterns that lead to the observed differences. This scenario might indicate a situation where one motif is consistent (or maybe just a simple background element), and the other motif is the main focus of artistic expression and variation in the collection.\n",
        "\n",
        "***\n",
        "<font color='Yellow'>`DEFINITION`</font> `Eigenvalues and Eigenfuncions`\n",
        "\n",
        "Let $\\mathbf{A} \\in \\mathbb{R}^{n \\times n}$ be a square matrix.\n",
        "- Then $\\lambda$ is an eigenvalue of $\\mathbf{A}$ and $\\mathbf{x} \\in \\mathbb{R}^n \\backslash\\{\\mathbf{0}\\}$ is the corresponding eigenvector of $\\mathbf{A}$ if\n",
        "$$\n",
        "\\mathbf{A x}=\\lambda \\mathbf{x}.\n",
        "$$\n",
        "We call this equation the \"eigenvalue equation\".\n",
        "***\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eUNbNg6YPxgs"
      },
      "source": [
        "### 2.1 Eigenvalues - <font color='blue'>`Beginner`</font>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lyskSSGCPxgt"
      },
      "source": [
        "\n",
        "Geometrically, the eigenvalue of a matrix represents the scaling factor by which a matrix transformation stretches or compresses a vector (eigenvector). It indicates how much the vector's direction changes under the transformation.\n",
        "\n",
        "To calculate the eigenvalue given the provided geometric meaning:\n",
        "\n",
        "1. Start with the equation: $A x = \\lambda x$, where $A$ is the matrix, $\\lambda$ is the eigenvalue, and $x$ is the eigenvector.\n",
        "2. Rearrange to get $A x - \\lambda x = 0$.\n",
        "3. Factor out $x$ to get $A x - \\lambda I x = 0$, where $I$ is the identity matrix.\n",
        "4. Factor out $x$ again to get $(A - \\lambda I) x = 0$.\n",
        "5. For a nontrivial solution ($x \\neq 0$), the matrix $A - \\lambda I$ must be singular, meaning its determinant is 0.\n",
        "6. Set up the equation $\\text{det}(A - \\lambda I) = 0$ and solve for $\\lambda$. This equation gives you the eigenvalues of the matrix $A$.\n",
        "\n",
        "In summary, the eigenvalue is a value that satisfies the equation $A x = \\lambda x$, meaning that when a matrix transformation is applied to an eigenvector, the resulting vector is scaled by the eigenvalue. The eigenvalue can be found by solving the determinant equation $\\text{det}(A - \\lambda I) = 0$.\n",
        "\n",
        "\n",
        "***\n",
        "<font color='Yellow'>`EXAMPLE`</font>\n",
        "\n",
        "$$\n",
        "\\boldsymbol{A}=\\left[\\begin{array}{cc}\n",
        "0.5 & 0 \\\\\n",
        "0 & 2\n",
        "\\end{array}\\right]\n",
        "$$\n",
        "Finding Eigenvalues $\\left(\\lambda_1, \\lambda_2\\right)$ :\n",
        "$$\n",
        "\\begin{aligned}\n",
        "& \\operatorname{det}(\\boldsymbol{A}-\\lambda I)=0 \\\\\n",
        "& \\operatorname{det}\\left(\\left[\\begin{array}{cc}\n",
        "0.5 & 0 \\\\\n",
        "0 & 2\n",
        "\\end{array}\\right]-\\lambda\\left[\\begin{array}{ll}\n",
        "1 & 0 \\\\\n",
        "0 & 1\n",
        "\\end{array}\\right]\\right)=0 \\\\\n",
        "& \\operatorname{det}\\left(\\left[\\begin{array}{cc}\n",
        "0.5-\\lambda & 0 \\\\\n",
        "0 & 2-\\lambda\n",
        "\\end{array}\\right]\\right)=0 \\\\\n",
        "& (0.5-\\lambda)(2-\\lambda)=0 \\\\\n",
        "& 0.5-\\lambda=0 \\text { or } 2-\\lambda=0 \\\\\n",
        "& \\lambda_1=0.5 \\text { and } \\lambda_2=2\n",
        "\\end{aligned}\n",
        "$$\n",
        "***"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tdaC1ClPPxgu"
      },
      "source": [
        "**Math Task:**\n",
        "\n",
        "Calculate the eigenvalues of the following matrix:\n",
        "$\\boldsymbol{A}=\\left[\\begin{array}{cc}\n",
        "1 & 0.5 \\\\\n",
        "0 & 1\n",
        "\\end{array}\\right]$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "n4-tQtiAdEzr"
      },
      "source": [
        "`ANSWER`\n",
        "\n",
        "\n",
        "<img src=\n",
        "\"https://lh3.googleusercontent.com/drive-viewer/AITFw-xdFyBFBO8I9XX2FFN6VnD4DK_rKJxneSdhDAh8XtM70qfuMJmxOaFiqCV3doIl6W0gQTNJzmxVYuB9MuW9IXxl9dVEng=s1600\"\n",
        "width=\"60%\" />"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "o2-Y9ZcUAGbC"
      },
      "source": [
        "**Code Task:**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "545x1-JA_wPO"
      },
      "outputs": [],
      "source": [
        "def eig(S):\n",
        "    \"\"\"Compute the eigenvalues and corresponding eigenvectors\n",
        "        for the covariance matrix S.\n",
        "    Args:\n",
        "        S: ndarray, covariance matrix\n",
        "\n",
        "    Returns:\n",
        "        (eigvals, eigvecs): ndarray, the eigenvalues and eigenvectors\n",
        "\n",
        "    Note:\n",
        "        the eigenvals and eigenvecs should be sorted in descending\n",
        "        order of the eigen values\n",
        "    \"\"\"\n",
        "    # TODO\n",
        "    return None, None # <-- EDIT THIS to compute (eigvals, eigvecs)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "id": "zQlLZ9XbAW7O"
      },
      "outputs": [],
      "source": [
        "# @title Run me to test your code\n",
        "\n",
        "def test_eig(eig):\n",
        "  A1 = np.array([[0.5,0],[0,2]])\n",
        "  A2 = np.array([[1,0.5],[0,1]])\n",
        "  print(\"A = \",A1)\n",
        "  print(\"Eigenvalues, Eigenvectors = \", eig(A1))\n",
        "  print(\"A = \",A2)\n",
        "  print(\"Eigenvalues, Eigenvectors = \", eig(A2))\n",
        "  print(\"The answers are correct if they are the same as the ones obtained by hand above.\")\n",
        "\n",
        "test_eig(eig)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "id": "8JnKEpULBhCH"
      },
      "outputs": [],
      "source": [
        "# @title Answer to code task (Try not to peek until you've given it a good try!')\n",
        "\n",
        "def eig(S):\n",
        "    \"\"\"Compute the eigenvalues and corresponding eigenvectors\n",
        "        for the covariance matrix S.\n",
        "    Args:\n",
        "        S: ndarray, covariance matrix\n",
        "\n",
        "    Returns:\n",
        "        (eigvals, eigvecs): ndarray, the eigenvalues and eigenvectors\n",
        "\n",
        "    Note:\n",
        "        the eigenvals and eigenvecs should be sorted in descending\n",
        "        order of the eigen values\n",
        "    \"\"\"\n",
        "    eigvals, eigvecs = np.linalg.eig(S)\n",
        "    k = np.argsort(eigvals)[::-1]\n",
        "    return eigvals[k], eigvecs[:,k]\n",
        "\n",
        "test_eig(eig)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oFOc0WpmEWiX"
      },
      "source": [
        "### 2.1 Eigenvectors - <font color='orange'>`Intermediate`</font>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xiZ3tWwLEWix"
      },
      "source": [
        "\n",
        "<!-- For each eigenvalue of $A$, we can find the corresponding eigenvector $v$ by simply solving for x in the following linear system:\n",
        "$(A-\\lambda I) x=0$ -->\n",
        "Geometrically, an eigenvector of a matrix represents a direction in space that remains unchanged in direction (up to scaling) when the matrix is applied as a transformation. In other words, it's a vector that only gets stretched or compressed by the matrix, without changing its orientation.\n",
        "\n",
        "To calculate the eigenvector corresponding to a given eigenvalue of a matrix $A$:\n",
        "\n",
        "1. Start with the equation $A x = \\lambda x$, where $A$ is the matrix, $\\lambda$ is the eigenvalue, and $x$ is the eigenvector.\n",
        "2. Rearrange to get $(A - \\lambda I) x = 0$, where $I$ is the identity matrix.\n",
        "3. Solve the system of linear equations $(A - \\lambda I) x = 0$ for $x$.\n",
        "4. The solution vector $x$ is the eigenvector corresponding to the given eigenvalue $\\lambda$.\n",
        "\n",
        "In short, the eigenvector is found by solving the equation $(A - \\lambda I) x = 0$ for the vector $x$, which satisfies the transformation relationship $A x = \\lambda x$ with the given eigenvalue.\n",
        "\n",
        "\n",
        "***\n",
        "<font color='Yellow'>`EXAMPLE`</font>\n",
        "\n",
        "Remember the previous example\n",
        "$\\boldsymbol{A}=\\left[\\begin{array}{cc}\n",
        "0.5 & 0 \\\\\n",
        "0 & 2\n",
        "\\end{array}\\right]$\n",
        "with eigenvalues $\\lambda_1 =0.5, \\lambda_2 =2$.\n",
        "\n",
        "Finding Eigenvectors $\\left(v_1, v_2\\right)$ :\n",
        "$$\n",
        "\\begin{aligned}\n",
        "& (A-\\lambda I) x=0 \\\\\n",
        "& {\\left[\\begin{array}{cc}\n",
        "0.5-\\lambda & 0 \\\\\n",
        "0 & 2-\\lambda\n",
        "\\end{array}\\right] x=0}\n",
        "\\end{aligned}\n",
        "$$\n",
        "For $\\lambda=0.5$\n",
        "$$\n",
        "\\left[\\begin{array}{cc}\n",
        "0 & 0 \\\\\n",
        "0 & 1.5\n",
        "\\end{array}\\right] x=0, \\quad \\text { Hence } v_1=\\left[\\begin{array}{l}\n",
        "1 \\\\\n",
        "0\n",
        "\\end{array}\\right]\n",
        "$$\n",
        "For $\\lambda=2$\n",
        "$$\n",
        "\\left[\\begin{array}{cc}\n",
        "-1.5 & 0 \\\\\n",
        "0 & 0\n",
        "\\end{array}\\right] x=0, \\quad \\text { Hence } v_2=\\left[\\begin{array}{l}\n",
        "0 \\\\\n",
        "1\n",
        "\\end{array}\\right]\n",
        "$$\n",
        "\n",
        "***\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Uby6kpK8EWiy"
      },
      "source": [
        "**Math Task:**\n",
        "\n",
        "Suppose you're working on a computer vision project and want to reduce the dimensionality of image data to improve classification accuracy. You can use principal component analysis (PCA) to find the most important directions of variation in the data. Given the following covariance matrix of a dataset of 3 images:\n",
        "\n",
        "$$\n",
        "\\boldsymbol{A}=\\left[\\begin{array}{lll}\n",
        "1 & 0 & 0 \\\\\n",
        "4 & 5 & 6 \\\\\n",
        "7 & 8 & 9\n",
        "\\end{array}\\right]\n",
        "$$\n",
        "Perform eigendecomposition on the covariance matrix of the dataset to identify the principal components (eigenvectors) and their associated eigenvalues.\n",
        "\n",
        "a) What are its eigenvalues $\\lambda_1, \\lambda_2, \\lambda_3$?\n",
        "\n",
        "b) What are its eigenvectors $v_1, v_2, v_3$?\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iJDSZxP_EWiz"
      },
      "source": [
        "`ANSWER`\n",
        "\n",
        "Finding Eigenvalues $\\left(\\lambda_1, \\lambda_2, \\lambda_3\\right)$ :\n",
        "$$\n",
        "\\operatorname{det}(\\boldsymbol{A}-\\lambda I)=\\mathbf{0}\n",
        "$$\n",
        "$$\n",
        "\\begin{aligned}\n",
        "& \\operatorname{det}\\left(\\left[\\begin{array}{lll}\n",
        "1 & 0 & 0 \\\\\n",
        "4 & 5 & 6 \\\\\n",
        "7 & 8 & 9\n",
        "\\end{array}\\right]-\\lambda\\left[\\begin{array}{lll}\n",
        "1 & 0 & 0 \\\\\n",
        "0 & 1 & 0 \\\\\n",
        "0 & 0 & 1\n",
        "\\end{array}\\right]\\right)=0 \\\\\n",
        "& \\operatorname{det}\\left(\\left[\\begin{array}{ccc}\n",
        "1-\\lambda & 0 & 0 \\\\\n",
        "4 & 5-\\lambda & 6 \\\\\n",
        "7 & 8 & 9-\\lambda\n",
        "\\end{array}\\right]\\right)=0 \\\\\n",
        "& (-1)^{1+1}(1-\\lambda)\\left|\\begin{array}{cc}\n",
        "5-\\lambda \\\\\n",
        "8 & 6-\\lambda\n",
        "\\end{array}\\right|=0 \\\\\n",
        "& (1-\\lambda)((5-\\lambda)(9-\\lambda)-48)=0 \\\\\n",
        "& (1-\\lambda)\\left(45-5 \\lambda-9 \\lambda+\\lambda^2-48\\right)=0 \\\\\n",
        "& (1-\\lambda)\\left(\\lambda^2-14 \\lambda-3\\right)=0 \\\\\n",
        "& 1-\\lambda=0 \\quad \\text { or } \\lambda^2-14 \\lambda-3=0 \\\\\n",
        "& \\lambda_1=1, \\quad \\lambda_2=7+2 \\sqrt{13}, \\quad \\lambda_3=7-2 \\sqrt{13}\n",
        "\\end{aligned}\n",
        "$$\n",
        "\n",
        "Finding Eigenvectors $\\left(v_1, v_2, v_3\\right)$ :\n",
        "$$\n",
        "\\begin{aligned}\n",
        "& (A-\\lambda I) x=0 \\\\\n",
        "& {\\left[\\begin{array}{ccc}\n",
        "1-\\lambda & 0 & 0 \\\\\n",
        "4 & 5-\\lambda & 6 \\\\\n",
        "7 & 8 & 9-\\lambda\n",
        "\\end{array}\\right] x=0}\n",
        "\\end{aligned}\n",
        "$$\n",
        "$$\n",
        "\\left[\\begin{array}{ccc}\n",
        "1-\\lambda & 0 & 0 \\\\\n",
        "4 & 5-\\lambda & 6 \\\\\n",
        "7 & 8 & 9-\\lambda\n",
        "\\end{array}\\right] \\boldsymbol{x}=\\mathbf{0}\n",
        "$$\n",
        "For $\\lambda=1$\n",
        "$$\n",
        "\\left[\\begin{array}{lll}\n",
        "0 & 0 & 0 \\\\\n",
        "4 & 4 & 6 \\\\\n",
        "7 & 8 & 8\n",
        "\\end{array}\\right] x=0, \\quad \\text { Hence } \\quad v_1=\\left[\\begin{array}{c}\n",
        "4 \\\\\n",
        "-\\frac{5}{2} \\\\\n",
        "-1\n",
        "\\end{array}\\right]\n",
        "$$\n",
        "$$\n",
        "\\begin{aligned}\n",
        "& \\text { For } \\lambda=7+2 \\sqrt{13} \\\\\n",
        "& {\\left[\\begin{array}{ccc}\n",
        "-6-2 \\sqrt{13} & 0 & 0 \\\\\n",
        "4 & -2-2 \\sqrt{13} & 6 \\\\\n",
        "7 & 8 & 2-2 \\sqrt{13}\n",
        "\\end{array}\\right] x=0, \\quad \\text { Hence } v_2=\\left[\\begin{array}{c}\n",
        "\\mathbf{0} \\\\\n",
        "\\mathbf{1}-\\sqrt{\\mathbf{1 3}} \\\\\n",
        "\\hline \\mathbf{4} \\\\\n",
        "\\mathbf{- 1}\n",
        "\\end{array}\\right]}\n",
        "\\end{aligned}\n",
        "$$\n",
        "For $\\lambda=7-2 \\sqrt{13}$\n",
        "$$\n",
        "\\left[\\begin{array}{ccc}\n",
        "-6+2 \\sqrt{13} & 0 & 0 \\\\\n",
        "4 & -2+2 \\sqrt{13} & 6 \\\\\n",
        "7 & 8 & 2+2 \\sqrt{13}\n",
        "\\end{array}\\right] x=0, \\quad \\text { Hence } v_3=\\left[\\begin{array}{c}\n",
        "\\mathbf{0} \\\\\n",
        "\\mathbf{1}+\\sqrt{\\mathbf{1 3}} \\\\\n",
        "\\hline \\mathbf{4} \\\\\n",
        "\\mathbf{- 1}\n",
        "\\end{array}\\right]\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1mIg4N68EXuq"
      },
      "source": [
        "### 2.1 Eigendecomposition - <font color='orange'>`Intermediate`</font>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iOIoJTZjEXvL"
      },
      "source": [
        "The eigendecomposition of a matrix involves expressing the matrix as a combination of its eigenvectors and eigenvalues. It allows us to break down a complex transformation into simpler, individual transformations along specific directions, represented by the eigenvectors, each scaled by its corresponding eigenvalue. This provides insight into how the matrix distorts and scales space in different directions.\n",
        "\n",
        "***\n",
        "<font color='Yellow'>`DEFINITION`</font> `Eigendecomposition`\n",
        "\n",
        "$\\mathbf{A} \\in \\mathbb{R}^{n \\times n}$ can be factored into\n",
        "$$\n",
        "\\mathbf{A}=\\mathbf{P D P}^{-1}\n",
        "$$\n",
        "where $\\mathbf{P} \\in \\mathbb{R}^{n \\times n}$ is a matrix whose columns are all the eigenvectors, and $\\mathbf{D}$ is a diagonal matrix whose diagonal entries are the eigenvalues of $\\mathbf{A}$\n",
        "- if and only if the eigenvectors of $\\mathbf{A}$ form a basis of $\\mathbf{R}^n$.\n",
        "\n",
        "In short, only non-defective matrices can be diagonalized in this way.\n",
        "***\n",
        "\n",
        "***\n",
        "<font color='Yellow'>`EXAMPLE`</font>\n",
        "\n",
        "\\begin{aligned}\n",
        "& \\boldsymbol{A}=\\left[\\begin{array}{cc}\n",
        "0.5 & 0 \\\\\n",
        "0 & 2\n",
        "\\end{array}\\right] ; \\quad \\text { Eigenvalues } \\lambda_1=0.5, \\lambda_2=2 ; \\quad \\text { Eigenvectors } \\boldsymbol{v}_{\\mathbf{1}}=\\left[\\begin{array}{l}\n",
        "\\mathbf{1} \\\\\n",
        "\\mathbf{0}\n",
        "\\end{array}\\right], \\boldsymbol{v}_2=\\left[\\begin{array}{l}\n",
        "\\mathbf{0} \\\\\n",
        "1\n",
        "\\end{array}\\right] \\\\\n",
        "& \\boldsymbol{A}=\\boldsymbol{P} \\boldsymbol{D P}^{-1}=\\left[\\begin{array}{ll}\n",
        "v_1 & v_2\n",
        "\\end{array}\\right]\\left[\\begin{array}{cc}\n",
        "\\lambda_1 & 0 \\\\\n",
        "0 & \\lambda_2\n",
        "\\end{array}\\right]\\left[\\begin{array}{ll}\n",
        "v_1 & v_2\n",
        "\\end{array}\\right]^{-1}=\\left[\\begin{array}{cc}\n",
        "1 & 0 \\\\\n",
        "0 & 1\n",
        "\\end{array}\\right]\\left[\\begin{array}{cc}\n",
        "0.5 & 0 \\\\\n",
        "0 & 2\n",
        "\\end{array}\\right]\\left[\\begin{array}{ll}\n",
        "1 & 0 \\\\\n",
        "0 & 1\n",
        "\\end{array}\\right]^{-1}\n",
        "\\end{aligned}\n",
        "***\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sqiGWtstEXvM"
      },
      "source": [
        "**Math Task:**\n",
        "\n",
        "Imagine you're exploring a haunted house filled with spooky objects. In order to better understand the eeriness, you decide to use eigendecomposition. You collect data on the occurrences of two types of eerie objects: bats and black cats.\n",
        "\n",
        "You end up with the following covariance matrix that summarizes the relationships between the appearances of bats and black cats in your data over a number of days:\n",
        "\n",
        "$$\n",
        "\\begin{bmatrix}\n",
        "1 & 3 \\\\\n",
        "3 & 1\n",
        "\\end{bmatrix}\n",
        "$$\n",
        "\n",
        "Perform eigendecomposition on this covariance matrix to reveal the spectral components (eigenvectors) that define the haunting vibes and their corresponding spectral intensities (eigenvalues).\n",
        "\n",
        "a) What are its eigenvalues $\\lambda_1, \\lambda_2$?\n",
        "\n",
        "b) What are its eigenvectors $v_1, v_2$?\n",
        "\n",
        "c) What is its eigendecomposition $A = PDP^{-1}$?\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kt-i86wLEXvO"
      },
      "source": [
        "`ANSWER`\n",
        ">\\begin{aligned}\n",
        "\\lambda_1=-2,\n",
        "\\lambda_2=4,\n",
        "v_1 = {\\left[\\begin{array}{c}\n",
        "1 \\\\\n",
        "-1\n",
        "\\end{array}\\right]} ,\n",
        "v_2 = {\\left[\\begin{array}{c}\n",
        "1 \\\\\n",
        "1\n",
        "\\end{array}\\right]} ,\n",
        "A = {\\left[\\begin{array}{cc}\n",
        "1 & 1 \\\\\n",
        "-1 & 1\n",
        "\\end{array}\\right]}\n",
        " {\\left[\\begin{array}{cc}\n",
        "-2 & 0 \\\\\n",
        "0 & 4\n",
        "\\end{array}\\right]}\n",
        " {\\left[\\begin{array}{cc}\n",
        "\\frac{1}{2} & -\\frac{1}{2} \\\\\n",
        "\\frac{1}{2} & \\frac{1}{2}\n",
        "\\end{array}\\right]}\n",
        "\\end{aligned}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "r6mv0CvIP-K1"
      },
      "source": [
        "## **Example: Principal Component Analysis (PCA)**\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2HhYvYGDeQJJ"
      },
      "source": [
        "We will implement the PCA algorithm using the projection perspective. We will first implement PCA, then apply it to the MNIST digit dataset."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "k2l1GrnxH27N"
      },
      "source": [
        "Imagine you have a bunch of data points, like images of hand written digits from different people (this is the MNIST dataset). Each data point is like a little arrow in a high-dimensional space. But sometimes, this space is too complicated, and it's hard to see the real patterns.\n",
        "\n",
        "PCA comes to the rescue! It's like a magic trick that helps us simplify things. Here's how it works:\n",
        "\n",
        "1. **Collect Your Data:** Let's say you have data of images of how different people write digits 0-9 (like the MNIST dataset). You arrange this data into a matrix called \"X\" where each row is a vector of pixels for each hand-written digit image:\n",
        "\n",
        "   $$ X = images = \\begin{bmatrix}\n",
        "   \\text{pixel}_1 & \\text{pixel}_1 & \\text{pixel}_1 \\\\\n",
        "   \\text{pixel}_2 & \\text{pixel}_2 & \\text{pixel}_2 \\\\\n",
        "   \\vdots & \\vdots & \\vdots \\\\\n",
        "   \\text{pixel}_n & \\text{pixel}_n & \\text{pixel}_n \\\\\n",
        "   \\end{bmatrix} $$\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Wavw_q9JLEOG"
      },
      "outputs": [],
      "source": [
        "# Loding MNIST dataset\n",
        "digits = load_digits(n_class=6) # low-dimensional MNIST dataset\n",
        "images, labels = digits.data, digits.target\n",
        "size = 8\n",
        "if True: # Make it True to use the high-dimensional MNIST dataset\n",
        "    images, labels = fetch_openml('mnist_784', version=1, return_X_y=True)\n",
        "    size = 28\n",
        "print(\"Matix shape:\", images.shape)\n",
        "print(\"Dimension of each image vector is:\", size*size)\n",
        "get_ipython().run_line_magic('matplotlib', 'inline')"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "CDmM8C-vTaZ2"
      },
      "outputs": [],
      "source": [
        "# Plotting the first digit from the dataset:\n",
        "plt.figure(figsize=(4,4))\n",
        "images = images.to_numpy()\n",
        "plt.imshow(images[0].reshape((size,size)), cmap='gray');\n",
        "plt.axis(\"off\")\n",
        "plt.title(f\"First digit from the {size*size}-dimensional digits dataset\", fontsize=16)\n",
        "\n",
        "# Plotting the first 25 digits from the dataset:\n",
        "fig, axs = plt.subplots(nrows=10, ncols=10, figsize=(6, 6))\n",
        "for idx, ax in enumerate(axs.ravel()):\n",
        "    ax.imshow(images[idx].reshape((size, size)), cmap=plt.cm.binary)\n",
        "    ax.axis(\"off\")\n",
        "_ = fig.suptitle(f\"A selection from the {size*size}-dimensional digits dataset\", fontsize=16)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oXkCvnlK8heN"
      },
      "source": [
        "2. **Data Normalisation:**  Before we implement PCA, we will need to do some data preprocessing to ensure the data points are more centered around the origin.\n",
        "The preprocessing steps we will do are\n",
        " 1. Convert unsigned interger 8 (uint8) encoding of pixels to a floating point number between 0 and 1.\n",
        " 2. Subtract from each image the mean $\\boldsymbol \\mu$.\n",
        " 3. Scale each dimension of each image by $\\frac{1}{\\sigma}$ where $\\sigma$ is the stardard deviation.\n",
        "\n",
        " The steps above ensure that our images will have zero mean and one variance. These preprocessing\n",
        "steps are also known as [Data Normalization or Feature Scaling](https://en.wikipedia.org/wiki/Feature_scaling)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "wKZwyAsL_7Al"
      },
      "outputs": [],
      "source": [
        "def normalize(X):\n",
        "    \"\"\"Normalize the given dataset X\n",
        "    Args:\n",
        "        X: ndarray, dataset\n",
        "\n",
        "    Returns:\n",
        "        (Xbar, mean, std): tuple of ndarray, Xbar is the normalized dataset\n",
        "        with mean 0 and standard deviation 1; mean and std are the\n",
        "        mean and standard deviation respectively.\n",
        "\n",
        "    Note:\n",
        "        You will encounter dimensions where the standard deviation is\n",
        "        zero, for those when you do normalization the normalized data\n",
        "        will be NaN. Handle this by setting using `std = 1` for those\n",
        "        dimensions when doing normalization.\n",
        "    \"\"\"\n",
        "    mu = np.mean(X, axis=0)\n",
        "    std = np.std(X, axis=0)\n",
        "    std_filled = std.copy()\n",
        "    std_filled[std==0] = 1.\n",
        "    Xbar = ((X-mu)/std_filled)\n",
        "    return Xbar, mu, std"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FS7Pk824NazD"
      },
      "source": [
        "3. **Calculate the Covariance Matrix:** You find the \"covariance\" between the different columns of your centered data. Covariance tells you how the columns change together. Mathematically, you calculate the covariance matrix by multiplying the transposed matrix $X^T$ with $X$:\n",
        "\n",
        "   $$ \\text{Covariance Matrix (S)} = X^T \\cdot X $$\n",
        "\n",
        "4. **Find the Eigenvectors and Eigenvalues:** This part sounds complex, but bear with me. The eigenvectors are special directions in your data space, and the eigenvalues tell you how important those directions are. When you compute these, you're finding the principal components. Luckily, we now know how to compute these from the previous sections.\n",
        "\n",
        "5. **Sort Eigenvectors by Eigenvalues:** You arrange the eigenvectors in order of their corresponding eigenvalues, from largest to smallest. This way, you're putting the most important components first.\n",
        "\n",
        "6. **Choose How Many Components to Keep:** Depending on how much information you want to keep, you decide how many eigenvectors (principal components) to keep. Usually, you keep the top ones that capture most of the data's variation.\n",
        "\n",
        "7. **Project Your Data:** You now multiply your centered data by the projection matrix for the selected eigenvectors. This transforms your data into a new space, where each data point is described with fewer dimensions, the principal components.\n",
        "\n",
        "And voilà! You now understnd how to use PCA to simplify your data. Those new dimensions (principal components) are like new ways of looking at your data that highlight the important stuff. It's like turning a complex puzzle into a simpler picture.\n",
        "\n",
        "Remember, PCA is like a tool that helps you focus on the main story your data wants to tell, without getting bogged down in all the extra details. Let's now try and implement it.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0U4BqG85P-ME"
      },
      "source": [
        "### 2.1 PCA for a low dimensional dataset - <font color='blue'>`Beginner`</font>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3xPPfXQKP-MF"
      },
      "source": [
        "Now we will implement PCA by following the process outline above. That's, first do data normalization (`normalize`). Then find eigenvalues and corresponding eigenvectors for the covariance matrix $S$.\n",
        "Sort by the largest eigenvalues and the corresponding eigenvectors (`eig`).\n",
        "After these steps, we can then compute the projection and reconstruction of the data onto the spaced spanned by the top $n$ eigenvectors."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s0vw3HRKP-MP"
      },
      "source": [
        "**Code Task:**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "V6QQ3aKTP-MQ"
      },
      "outputs": [],
      "source": [
        "def PCA(X, num_components):\n",
        "    \"\"\"\n",
        "    Args:\n",
        "        X: ndarray of size (N, D), where D is the dimension of the data,\n",
        "           and N is the number of datapoints\n",
        "        num_components: the number of principal components to use.\n",
        "    Returns:\n",
        "        X_reconstruct: ndarray of the reconstruction\n",
        "        of X from the first `num_components` principal components.\n",
        "    \"\"\"\n",
        "    # your solution should take advantage of the functions we have given you and that you have implemented above.\n",
        "\n",
        "    # first perform normalization on the digits so that they have zero mean and unit variance\n",
        "    # Then compute the data covariance matrix S (remember the convariance matrix is given by the dot product)\n",
        "    ### TODO\n",
        "\n",
        "    # Next find eigenvalues and corresponding eigenvectors for S\n",
        "    ### TODO\n",
        "\n",
        "    # find indices for the largest eigenvalues, use them to sort the eigenvalues and\n",
        "    # corresponding eigenvectors. Take a look at the documenation fo `np.argsort`\n",
        "    # (https://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html),\n",
        "    # which might be useful\n",
        "    ### TODO\n",
        "\n",
        "    # dimensionality reduction of the original data\n",
        "    ### TODO\n",
        "\n",
        "    # reconstruct the images from the lower dimensional representation\n",
        "    ### TODO\n",
        "\n",
        "    return X # <-- EDIT THIS to return the reconstruction of X"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "id": "Zdk-Do-JP-MS"
      },
      "outputs": [],
      "source": [
        "# @title Run me to test your code\n",
        "\n",
        "NUM_DATAPOINTS = 1024\n",
        "X = (images.reshape(-1, size * size)[:NUM_DATAPOINTS]) / 255.\n",
        "Xbar, mu, std = normalize(X)\n",
        "\n",
        "def test_PCA(PCA):\n",
        "  for num_component in range(1, 20):\n",
        "    from sklearn.decomposition import PCA as SKPCA\n",
        "    # We can compute a standard solution given by scikit-learn's implementation of PCA\n",
        "    pca = SKPCA(n_components=num_component, svd_solver='full')\n",
        "    sklearn_reconst = pca.inverse_transform(pca.fit_transform(Xbar))\n",
        "    reconst = PCA(Xbar, num_component)\n",
        "    np.testing.assert_almost_equal(reconst, sklearn_reconst)\n",
        "    print(\"number of components:\",num_component,\"reconstruction error:\", np.square(reconst - sklearn_reconst).sum())\n",
        "\n",
        "test_PCA(PCA)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "id": "pb9Gfyu6P-MT"
      },
      "outputs": [],
      "source": [
        "# @title Answer to code task (Try not to peek until you've given it a good try!')\n",
        "\n",
        "def PCA(X, num_components):\n",
        "    \"\"\"\n",
        "    Args:\n",
        "        X: ndarray of size (N, D), where D is the dimension of the data,\n",
        "           and N is the number of datapoints\n",
        "        num_components: the number of principal components to use.\n",
        "    Returns:\n",
        "        X_reconstruct: ndarray of the reconstruction\n",
        "        of X from the first `num_components` principal components.\n",
        "    \"\"\"\n",
        "    # first perform normalization on the digits so that they have zero mean and unit variance\n",
        "    # Then compute the data covariance matrix S\n",
        "    S = 1.0/len(X) * np.dot(X.T, X)\n",
        "\n",
        "    # Next find eigenvalues and corresponding eigenvectors for S\n",
        "    eig_vals, eig_vecs = eig(S)\n",
        "\n",
        "    # find indices for the largest eigenvalues, use them to sort the eigenvalues and\n",
        "    # corresponding eigenvectors. Take a look at the documenation fo `np.argsort`\n",
        "    # (https://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html),\n",
        "    # which might be useful\n",
        "    eig_vals, eig_vecs = eig_vals[:num_components], eig_vecs[:, :num_components]\n",
        "\n",
        "    # dimensionality reduction of the original data\n",
        "    B = np.real(eig_vecs)\n",
        "    # Z = X.T.dot(W)\n",
        "    # reconstruct the images from the lower dimensional representation\n",
        "    reconst = (projection_matrix(B) @ X.T)\n",
        "    return reconst.T\n",
        "\n",
        "test_PCA(PCA)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GjLckoYXEO5q"
      },
      "source": [
        "CONGRATS!!! You now understand and know how to implement PCA (a simplified version of it where we are using eigendecomposition instead of the more general singular value decomposition), one of the most popular dimensionality reduction techniques."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9lTgJdTughKE"
      },
      "source": [
        "The greater number of of principal components we use, the smaller will our reconstruction error be. Now, let's answer the following question:\n",
        "\n",
        "> How many principal components do we need in order to reach a Mean Squared Error (MSE) of less than 100\n",
        " for our dataset?\n",
        "\n",
        "We have provided a function in the next cell that computes the mean squared error (MSE), which will be useful for answering the question above.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "30NHtYXWgjm3"
      },
      "outputs": [],
      "source": [
        "def mse(predict, actual):\n",
        "    \"\"\"Helper function for computing the mean squared error (MSE)\"\"\"\n",
        "    return np.square(predict - actual).sum(axis=1).mean()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TRKQAEG4FiIS"
      },
      "source": [
        "We can now calculate the compute the reconstruction error per number of principal components used."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "8BCuaYeJFe06"
      },
      "outputs": [],
      "source": [
        "loss = []\n",
        "reconstructions = []\n",
        "# iterate over different numbers of principal components, and compute the MSE\n",
        "for num_component in range(1, 100):\n",
        "    reconst = PCA(Xbar, num_component)\n",
        "    error = mse(reconst, Xbar)\n",
        "    reconstructions.append(reconst)\n",
        "    # print('n = {:d}, reconstruction_error = {:f}'.format(num_component, error))\n",
        "    loss.append((num_component, error))\n",
        "\n",
        "reconstructions = np.asarray(reconstructions)\n",
        "reconstructions = reconstructions * std + mu # \"unnormalize\" the reconstructed image\n",
        "loss = np.asarray(loss)\n",
        "print(\"Loss/Error: \", loss)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "O-jxbkNPguFh"
      },
      "source": [
        "We can also put these numbers into perspective by plotting them."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "9IjEQVh5g0s3"
      },
      "outputs": [],
      "source": [
        "fig, ax = plt.subplots()\n",
        "ax.plot(loss[:,0], loss[:,1]);\n",
        "ax.axhline(10**len(str(size)), linestyle='--', color='r', linewidth=2)\n",
        "ax.xaxis.set_ticks(np.arange(1, 100, 5));\n",
        "ax.set(xlabel='num_components', ylabel='MSE', title='MSE vs number of principal components');"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nHi3veing4uL"
      },
      "source": [
        "But numbers dont't tell us everything! Just what does it mean qualitatively for the loss to decrease from around 55.0\n",
        " to less than 10.0\n",
        "? (or 550-100 for the high-demsional dataset)\n",
        "\n",
        "Let's find out! In the next cell, we draw the the leftmost image is the original dight. Then we show the reconstruction of the image on the right, in descending number of principal components used."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "hF_uQXcqhBtW"
      },
      "outputs": [],
      "source": [
        "@interact(image_idx=(0, 1000))\n",
        "def show_num_components_reconst(image_idx):\n",
        "    fig, ax = plt.subplots(figsize=(20., 20.))\n",
        "    actual = X[image_idx]\n",
        "    # concatenate the actual and reconstructed images as large image before plotting it\n",
        "    x = np.concatenate([actual[np.newaxis, :], reconstructions[:, image_idx]])\n",
        "    ax.imshow(np.hstack(x.reshape(-1, size, size)[np.arange(10)]),\n",
        "              cmap='gray');\n",
        "    ax.axvline(size, color='orange', linewidth=2)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1C847ojShFQv"
      },
      "source": [
        "We can also browse throught the reconstructions for other digits. Once again, interact becomes handy for visualing the reconstruction."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "wAWbq5fyhIor"
      },
      "outputs": [],
      "source": [
        "@interact(i=(0, 10))\n",
        "def show_pca_digits(i=1):\n",
        "    \"\"\"Show the i th digit and its reconstruction\"\"\"\n",
        "    plt.figure(figsize=(4,4))\n",
        "    actual_sample = X[i].reshape(size,size)\n",
        "    reconst_sample = (reconst[i, :] * std + mu).reshape(size, size)\n",
        "    plt.imshow(np.hstack([actual_sample, reconst_sample]), cmap='gray')\n",
        "    plt.show()\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9U87-jGoP-MV"
      },
      "source": [
        "### 2.2 PCA for a high dimensional dataset - <font color='orange'>`Intermediate`</font>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "I3fmw9vPP-MX"
      },
      "source": [
        "\n",
        "Sometimes, the dimensionality of our dataset may be larger than the number of samples we have. Then it might be inefficient to perform PCA with our implementation above. Instead, we can implement PCA in a more efficient manner, which we call \"PCA for high dimensional data\" (PCA_high_dim).\n",
        "\n",
        "Below are the steps for performing PCA for high dimensional dataset\n",
        " 1. Compute the matrix $\\boldsymbol X\\boldsymbol X^T$ (a $N$ by $N$ matrix with $N \\ll D$)\n",
        " 2. Compute eigenvalues $\\lambda$s and eigenvectors $V$ for $\\boldsymbol X\\boldsymbol X^T$\n",
        " 3. Compute the eigenvectors for the original covariance matrix as $\\boldsymbol X^T\\boldsymbol V$. Choose the eigenvectors associated with the M largest eigenvalues to be the basis of the principal subspace $U$.\n",
        " 4. Compute the orthogonal projection of the data onto the subspace spanned by columns of $\\boldsymbol U$.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F-v7teR9P-Md"
      },
      "source": [
        "**Code Task:**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "OMUE3jFKP-Me"
      },
      "outputs": [],
      "source": [
        "def PCA_high_dim(X, n_components):\n",
        "    \"\"\"Compute PCA for small sample size but high-dimensional features.\n",
        "    Args:\n",
        "        X: ndarray of size (N, D), where D is the dimension of the sample,\n",
        "           and N is the number of samples\n",
        "        num_components: the number of principal components to use.\n",
        "    Returns:\n",
        "        X_reconstruct: (N, D) ndarray. the reconstruction\n",
        "        of X from the first `num_components` pricipal components.\n",
        "    \"\"\"\n",
        "    return X # <-- EDIT THIS to return the reconstruction of X"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "i4yEELhLebFe"
      },
      "source": [
        "Given the same dataset, `PCA_high_dim` and `PCA` should give the same output.\n",
        "Assuming we have implemented `PCA`, correctly, we can then use `PCA` to test the correctness of `PCA_high_dim`.\n",
        "We can use this __invariant__ to test our implementation of `PCA_high_dim`, assuming that we have correctly implemented `PCA`.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "id": "bV7y9hnfP-Me"
      },
      "outputs": [],
      "source": [
        "# @title Run me to test your code\n",
        "\n",
        "def test_PCA_high_dim(PCA_high_dim):\n",
        "  np.testing.assert_almost_equal(PCA(Xbar, 2), PCA_high_dim(Xbar, 2))\n",
        "  print(\"Nice! Your answer looks correct.\")\n",
        "\n",
        "test_PCA_high_dim(PCA_high_dim)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "id": "-zo0VAEIP-Mf"
      },
      "outputs": [],
      "source": [
        "# @title Answer to code task (Try not to peek until you've given it a good try!')\n",
        "\n",
        "def PCA_high_dim(X, n_components):\n",
        "    \"\"\"Compute PCA for small sample size but high-dimensional features.\n",
        "    Args:\n",
        "        X: ndarray of size (N, D), where D is the dimension of the sample,\n",
        "           and N is the number of samples\n",
        "        num_components: the number of principal components to use.\n",
        "    Returns:\n",
        "        X_reconstruct: (N, D) ndarray. the reconstruction\n",
        "        of X from the first `num_components` pricipal components.\n",
        "    \"\"\"\n",
        "    N, D = X.shape\n",
        "    M = np.dot(X, X.T) / N\n",
        "    eig_vals, eig_vecs = eig(M)\n",
        "    eig_vals, eig_vecs = eig_vals[:n_components], eig_vecs[:, :n_components]\n",
        "    U = (X.T @ (eig_vecs))\n",
        "    answer = np.zeros((N, D))\n",
        "    answer = ((U @ np.linalg.inv(U.T @ U) @ U.T) @ X.T).T\n",
        "    return answer\n",
        "\n",
        "test_PCA_high_dim(PCA_high_dim)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2NF-fodCd5sU"
      },
      "source": [
        "Now let's compare the running time between `PCA` and `PCA_high_dim`.\n",
        "\n",
        "**Tips for running benchmarks or computationally expensive code**:\n",
        "When you have some computation that takes up a non-negligible amount of time. Try separating the code that produces output from the code that analyzes the result (e.g. plot the results, compute statistics of the results). In this way, you don't have to recompute when you want to produce more analysis.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "IVhnbcADftS2"
      },
      "outputs": [],
      "source": [
        "NUM_DATAPOINTS = 100\n",
        "X = (images.reshape(-1, size * size)[:NUM_DATAPOINTS]) / 255.\n",
        "Xbar, mu, std = normalize(X)\n",
        "\n",
        "%time PCA(Xbar, 2)\n",
        "%time PCA_high_dim(Xbar, 2)\n",
        "pass"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "o1ndpYE50BpG"
      },
      "source": [
        "## Feedback\n",
        "\n",
        "Please provide feedback that we can use to improve our practicals in the future."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "collapsed": true,
        "id": "OIZvkhfRz9Jz",
        "outputId": "91fb5864-0cf4-48ad-808e-d4d0a8ffa1d8"
      },
      "outputs": [
        {
          "data": {
            "text/html": [
              "\n",
              "<iframe\n",
              "\tsrc=\"https://forms.gle/Cg9aoa7czoZCYqxF7\",\n",
              "  width=\"80%\"\n",
              "\theight=\"1200px\" >\n",
              "\tLoading...\n",
              "</iframe>\n"
            ],
            "text/plain": [
              "<IPython.core.display.HTML object>"
            ]
          },
          "execution_count": 26,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# @title Generate Feedback Form. (Run Cell)\n",
        "from IPython.display import HTML\n",
        "\n",
        "HTML(\n",
        "    \"\"\"\n",
        "<iframe\n",
        "\tsrc=\"https://forms.gle/Cg9aoa7czoZCYqxF7\",\n",
        "  width=\"80%\"\n",
        "\theight=\"1200px\" >\n",
        "\tLoading...\n",
        "</iframe>\n",
        "\"\"\"\n",
        ")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oglV4kHMWnIN"
      },
      "source": [
        "<img src=\"https://baobab.deeplearningindaba.com/static/media/indaba-logo-dark.d5a6196d.png\" width=\"50%\" />"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [
        "alEg193g3RWw",
        "F_MV7s_fsJ65",
        "sNeAWDXPfKvo",
        "1UxBl5KcwrfD",
        "rKOQH-S7sUyC",
        "S5WpNdur3RW1",
        "79502w53tlzL",
        "JVIwuO3qxS18",
        "_O-Jj77VtySj",
        "lrJ9PNDhx09g",
        "AgjNSkMMKxtD",
        "YqBT9aJozt22",
        "Idrkvj8vgYvK",
        "dxSI2RJRwOah",
        "pZKGng2p1JhB",
        "Gq3dWm4Slkhm",
        "zA0XMoOdviKs",
        "_RBiElEhtJ2x",
        "5UEw7yBRlPWI",
        "XwIuSWEVmSHX",
        "3qYaaErTGSim",
        "FUjbba0tGRhz",
        "dWbPGhU2mu-y",
        "IbDkN8MwGPBa",
        "je9lXYFOl_qd",
        "QWmZJUhLmLoi",
        "VJvkYB5wAsEG",
        "vyPycTUcocE0",
        "OPE18pQHohm_",
        "Ldh6MIt-cSw7",
        "T_Nub_1VpXoz",
        "WXDCIqLPj_ej",
        "uIOjqUqAGqW9",
        "TLx54v7TvP9U",
        "mqU2QdQNZQU2",
        "9Z7yVGhV2nrQ",
        "8Xdm9nxHG9Om",
        "chUFwXlljrAW",
        "JhWLD8CQrkQz",
        "YU419hcxmx6p",
        "gV92_pCMyitu",
        "Ryt0tx82mfOe",
        "ETISgJzakwUI",
        "AHFonIvJx2XK",
        "dSxu-vRa3YMI",
        "TJw8rddS3bnv",
        "Vm8wwlqsrQi5",
        "tyTvtv_-3AUT",
        "lhD_6kr239zN",
        "QtBtP6nNqeth",
        "E_PpSXjnuOkT",
        "P3YPaCucQ6Hw",
        "stnvDolw50Dr",
        "osoP_M1OHeCK",
        "QUQ3wK9eIlye",
        "jCsh-UHCx36R",
        "Krg2R2KgcuSN",
        "M263Nxob3RXG",
        "aJ5j25nMY6p3",
        "51WXDneuZBLG",
        "L5ooN5saZDnC",
        "sBlYs_SST8ph",
        "tn8cbZghsPp2",
        "vHq53rFyYw-t",
        "BSk8RDm3d1dn",
        "1p3tAolSWRZP",
        "BBySVv0TW4fg",
        "-ZUp8i37dFbU",
        "ii__Bc27epiJ",
        "Rd7xAVznfBQU",
        "7SrT6swYgCm9",
        "e9NW58_3hAg2",
        "bA_2coZvhAg3",
        "BKtMEnRkhAg9",
        "5Ckb2SjTPxgD",
        "eUNbNg6YPxgs",
        "oFOc0WpmEWiX",
        "1mIg4N68EXuq",
        "r6mv0CvIP-K1",
        "0U4BqG85P-ME",
        "9U87-jGoP-MV"
      ],
      "provenance": [],
      "toc_visible": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "version": "3.8.5"
    },
    "vscode": {
      "interpreter": {
        "hash": "145833166d986a8417df3c7acb65d917d84b716b5a452e57fcacdc66f1a168c9"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}