Linear_Algebra_Review.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Linear_Algebra_Review.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rfZ7Lz4ARPXs"
      },
      "source": [
        "# Linear Algebra Review\n",
        "\n",
        "[Colab notebook](https://colab.research.google.com/drive/1T5Tg-xY9y3cVS6HuFw_D8814H4oYrP-8?usp=sharing)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fsfs0wriWzbv"
      },
      "source": [
        "## Scalars, Vectors, Matrices\n",
        "\n",
        "Values consisting of one numerical quantity are called **scalars**. \n",
        "For example, the average annual temperature in New York City is $53^\\circ$F. \n",
        "In the following, we adopt the mathematical notation where **scalar** variables are denoted by ordinary lower-cased letters (e.g., $x, y,$ and $z$). \n",
        "\n",
        "We denote the space of real-valued scalars by $\\mathbb{R}$. Formally, $x \\in \\mathbb{R}$ means that $x$ is a real-valued scalar, where the symbol $\\in$ is pronounced \"in,\" and simply denotes membership in a set. \n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Itt9P9WxVEeG",
        "outputId": "26bd112b-3059-455c-9ef2-695eca6a502c"
      },
      "source": [
        "a = 1 #scalar\n",
        "b = 2.5 #scalar\n",
        "a, b"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(1, 2.5)"
            ]
          },
          "metadata": {},
          "execution_count": 1
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6aALHTKrPE1N"
      },
      "source": [
        "**Vector** is a list (a.k.a., array) of scalar values.\n",
        "We denote vectors in bold, lower-case letters (e.g., $\\mathbf{x}$). \n",
        "Vectors can be presented either as a **column** or as a **row**.\n",
        "In example,\n",
        "\n",
        "$$\n",
        "\\mathbf{x} =\n",
        "\\begin{bmatrix}\n",
        "x_{1}\\\\ x_{2} \\\\ \\vdots \\\\x_{n}\n",
        "\\end{bmatrix}\n",
        "\\quad\\text{or}\\quad\n",
        "\\mathbf{x}^\\top = \\begin{bmatrix}x_1 & x_2 & ... & x_n\\end{bmatrix}.\n",
        "$$\n",
        "\n",
        "We refer to each element in a vector using a subscript.\n",
        "For example, the $i^\\mathrm{th}$ element of $\\mathbf{x}$ is denoted as $x_i$ and is a scalar.\n",
        "Formally, we say that a vector $\\mathbf{x}$\n",
        "consists of $n$ real-valued scalars, $\\mathbf{x} \\in \\mathbb{R}^n$.\n",
        "The length of a vector is commonly called the **dimension** of the vector.\n",
        "\n",
        "Vectors can be interpreted in multilpe ways. One interpretation is that vectors symbolize the location of points in space relative to some reference location which is called the **origin**. This view is useful when separating points to distinct clusters of points in space.\n",
        "Corresponding interpretation is as a **directions** in space from some reference location. This view allows us to operate on vectors: adding, subtructing, multiplying, etc.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "WixEuh6yTmV9",
        "outputId": "b793cf42-77c8-44d4-a214-5828d7f50976"
      },
      "source": [
        "import numpy as np\n",
        "x = np.array([1, 2, 3, 4]) #vector, 1-d array\n",
        "x"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([1, 2, 3, 4])"
            ]
          },
          "metadata": {},
          "execution_count": 2
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8pu2nqT4W24j",
        "outputId": "20a47a52-a497-4201-e1c2-c18cec34ccf3"
      },
      "source": [
        "len(x), x.shape"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(4, (4,))"
            ]
          },
          "metadata": {},
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YutFkMosPeZc"
      },
      "source": [
        "**Matrices** concatenate vectors similar to the way that vectors concatenate scalars.\n",
        "Here, matrices are denoted with bold, capital letters (e.g., $\\mathbf{A}$).\n",
        "Formally, $\\mathbf{A} \\in \\mathbb{R}^{m \\times n}$ means that the matrix $\\mathbf{A}$ consists of $m$ rows and $n$ columns of real-valued scalars.\n",
        "Visually, we can illustrate the matrix $\\mathbf{A}$ as a table,\n",
        "where each element $a_{ij}$ belongs to the $i^{\\mathrm{th}}$ row and $j^{\\mathrm{th}}$ column. That is,\n",
        "\n",
        "$$\\mathbf{A}=\n",
        "\\begin{bmatrix} \n",
        "a_{11} & a_{12} & \\cdots & a_{1n} \\\\ a_{21} & a_{22} & \\cdots & a_{2n} \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ a_{m1} & a_{m2} & \\cdots & a_{mn} \\\\ \n",
        "\\end{bmatrix}.$$\n",
        "\n",
        "The shape of $\\mathbf{A}$ is $m \\times n$.\n",
        "When a matrix has the same number of rows and columns it is called a **square** matrix."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "plqR2i8zTpXb",
        "outputId": "1faf7c66-a4a6-44f6-cc66-b6788b4771df"
      },
      "source": [
        "A = np.array([[1, 2], [3, 4], [5, 6]]) #3x2 matrix \n",
        "A"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[1, 2],\n",
              "       [3, 4],\n",
              "       [5, 6]])"
            ]
          },
          "metadata": {},
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3QIwkWUoXDCI",
        "outputId": "b8747129-5c50-422d-9a4c-f0764961b5ee"
      },
      "source": [
        "A.shape"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(3, 2)"
            ]
          },
          "metadata": {},
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "nwAv0Pt2UMMa",
        "outputId": "da007958-2f3c-4127-9937-be5d491d149c"
      },
      "source": [
        "A[2,1]"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "6"
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FeWFj_q0UH15"
      },
      "source": [
        "We can exchange a matrix's rows and columns and the result is called the **transpose** of the matrix.\n",
        "Formally, we denote the transpose of $\\mathbf{A}$ by $\\mathbf{A}^\\top$.\n",
        "Thus, the transpose of $\\mathbf{A}$ is\n",
        "a $n \\times m$ matrix.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "50IvKy41TpZy",
        "outputId": "c7ce8fd5-5549-4801-c60f-dc17f049bab5"
      },
      "source": [
        "A_T = A.T # Vector transposition\n",
        "A_T"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[1, 3, 5],\n",
              "       [2, 4, 6]])"
            ]
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "aBPRwDwgVM3D",
        "outputId": "8ee8c659-a41c-4782-92c0-f5c7af619aaa"
      },
      "source": [
        "A_T.shape"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(2, 3)"
            ]
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AqpDkB2pVaQj"
      },
      "source": [
        "As a special type of a square matrix is the **symmetric** matrix $\\mathbf{A}$ in which its transpose is equal to itself. That is, $\\mathbf{A}=\\mathbf{A}^\\top $.  "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "t6zAbwjwVsj2",
        "outputId": "6a64c75d-95d7-4273-8fb7-3c0c184a4060"
      },
      "source": [
        "A=np.array([[1,5,0],[5,2,0],[0,0,3]])\n",
        "(A == A.T).all()"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {},
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2L7pt59MWSOa"
      },
      "source": [
        "Matrices are useful data structures, and they allow us to organize data efficiently. As an example, it is common to organize data in a way that the **rows** of a matrix correspond to different measurments, while the **columns** correspond to the various features or attributes. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HDREfqKNXS_n"
      },
      "source": [
        "## Arithmetic Operations\n",
        "\n",
        "Adding/subtracting scalars, vectors, or matrices of the same shape is performed **elementwise**. It is also possible to multiply/divide scalars, vectors, or matrices elementwise."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "muAS73XgXaAf",
        "outputId": "6223926a-c7b7-4222-a7c0-5a16528e790c"
      },
      "source": [
        "A = np.array([[1, 2], [3, 4], [5, 6]])\n",
        "A"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[1, 2],\n",
              "       [3, 4],\n",
              "       [5, 6]])"
            ]
          },
          "metadata": {},
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3pJ3EYYnTpce",
        "outputId": "d549e75b-3111-4268-d64c-e5532ea977b4"
      },
      "source": [
        "B = np.array([[2, 5], [7, 4], [4, 3]])\n",
        "B"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[2, 5],\n",
              "       [7, 4],\n",
              "       [4, 3]])"
            ]
          },
          "metadata": {},
          "execution_count": 11
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ljBDNI4ETpfA",
        "outputId": "4a97cbc8-34da-4501-fc1c-3a756331f4cf"
      },
      "source": [
        "A+B # elementwise addition"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 3,  7],\n",
              "       [10,  8],\n",
              "       [ 9,  9]])"
            ]
          },
          "metadata": {},
          "execution_count": 12
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "dICZA7NTXD_g",
        "outputId": "7fa8b492-cfd7-4de2-925a-490161e35a25"
      },
      "source": [
        "A-B # elementwise subtraction"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[-1, -3],\n",
              "       [-4,  0],\n",
              "       [ 1,  3]])"
            ]
          },
          "metadata": {},
          "execution_count": 13
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lgw1X1DEXICZ",
        "outputId": "6397d8aa-18e6-4041-ba01-8f5b6df93bdf"
      },
      "source": [
        "A*B # elementwise multiplication, aka Hadamard product"
      ],
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 2, 10],\n",
              "       [21, 16],\n",
              "       [20, 18]])"
            ]
          },
          "metadata": {},
          "execution_count": 14
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Mks8Ctd8XVun",
        "outputId": "5d1982dd-cafc-4eb7-ec91-85ce5c7d13fd"
      },
      "source": [
        "A/B # elementwise division"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[0.5       , 0.4       ],\n",
              "       [0.42857143, 1.        ],\n",
              "       [1.25      , 2.        ]])"
            ]
          },
          "metadata": {},
          "execution_count": 15
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dmz1gU41X2Z7"
      },
      "source": [
        "## Reduction\n",
        "A common operation that can be performed on arbitrary matrices\n",
        "is to **sum** elements.\n",
        "Formally, we express sums using the $\\sum$ symbol.\n",
        "To express the sum of the elements in a vector $\\mathbf{x}$ of length $n$,\n",
        "we write $\\sum_{i=1}^n x_i$.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2biDngnZYWbs",
        "outputId": "4ecdcfef-c323-4ec2-f101-29168d3386a2"
      },
      "source": [
        "x = np.arange(10)\n",
        "x, x.sum()"
      ],
      "execution_count": 16,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]), 45)"
            ]
          },
          "metadata": {},
          "execution_count": 16
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0xHlSpqfYyOZ"
      },
      "source": [
        "A = np.array([[1, 2], [3, 4], [5, 6]])"
      ],
      "execution_count": 17,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XxoRT6O_Yr0o"
      },
      "source": [
        "The sum of **all** the elements in $\\mathbf{A}$ is denoted $\\sum_{i=1}^{m} \\sum_{j=1}^{n} a_{ij}$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CQP9344CYbuw",
        "outputId": "a0a20034-c847-482a-a5e3-fbbd0760e4af"
      },
      "source": [
        "A.sum()"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "21"
            ]
          },
          "metadata": {},
          "execution_count": 18
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8x-ANCvJYr9t"
      },
      "source": [
        "Summing up elements along **rows** reduces the row dimension (axis 0) $\\sum_{i=1}^{m} a_{ij}$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lgLFpSPAZBDT",
        "outputId": "17b6013a-fc91-49cd-82ea-a99f97093317"
      },
      "source": [
        "A.sum(axis=0)"
      ],
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([ 9, 12])"
            ]
          },
          "metadata": {},
          "execution_count": 19
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uTMxJ7UPYsJE"
      },
      "source": [
        "Summing up elements along **columns** reduces the row dimension (axis 1) $\\sum_{j=1}^{n} a_{ij}$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "LCnAGR6gaupR",
        "outputId": "89a51804-8ab2-4335-e945-db9c312582b7"
      },
      "source": [
        "A.sum(axis=1)"
      ],
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([ 3,  7, 11])"
            ]
          },
          "metadata": {},
          "execution_count": 20
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uFV7TsWZXkX1"
      },
      "source": [
        "## Broadcasting"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wCgAQ-rhX0sd"
      },
      "source": [
        "Broadcasting describes how numpy handles arrays with different shapes during arithmetic operations. Subject to certain constraints, the smaller array is \"broadcast\" across the larger array so that they have compatible shapes. \n",
        "NumPy operations are done on **pairs** of arrays on an element-by-element basis. \n",
        "\n",
        "The simplest broadcasting example occurs when an array and a scalar value are combined in an operation"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "eNNaAjzgTph8",
        "outputId": "2d1a61ab-82ca-40f0-c229-cc3f853a654a"
      },
      "source": [
        "A = np.array([1, 2,3])\n",
        "A+4 # broadcasting"
      ],
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([5, 6, 7])"
            ]
          },
          "metadata": {},
          "execution_count": 21
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hGsJ0GH9pYY2"
      },
      "source": [
        "This result is equivalent to "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "BmVzwt9JplZT",
        "outputId": "db0383f9-a1b9-415c-a29d-6689cbe5a83a"
      },
      "source": [
        "A + np.array([4, 4, 4])"
      ],
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([5, 6, 7])"
            ]
          },
          "metadata": {},
          "execution_count": 22
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ms21SrqIqX-6"
      },
      "source": [
        "When operating on two arrays, NumPy compares their shapes element-wise. It starts with the **rightmost** dimensions and works its way left. Two dimensions are compatible when\n",
        "\n",
        "* they are equal, or\n",
        "* one of them is 1.\n",
        "\n",
        "If these conditions are not met, a ValueError is thrown. Here are a few more examples:\n",
        "\n",
        "\n",
        "Ex 1.  | Shape  | Ex 2.  | Shape      | Ex 3.  | Shape         |\n",
        "--     | --     | --     | --         |  --    | --            | \n",
        "A      | 3 x 2  | A      | 10 x 3 x 3 | A      | 6 x 1 x 4 x 1 | \n",
        "B      | 1 x 2  | B      | 10 x 1 x 3 | B      | 1 x 5 x 1 x 3 | \n",
        "A+B    | 3 x 2  | A+B    | 10 x 3 x 3 | A+B    | 6 x 5 x 4 x 3 | \n",
        "\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xKyz5buDYEtK"
      },
      "source": [
        "## Multiplying Vectors and Matrices\n",
        "\n",
        "One of the fundamental operations in Linear Algebra is the **dot product**.\n",
        "Given two vectors $\\mathbf{x}, \\mathbf{y} \\in \\mathbb{R}^n$, their dot product $\\mathbf{x} \\cdot \\mathbf{y}=\\mathbf{x}^\\top \\mathbf{y}$ is a sum over the elements at the same positions. In example, $\\mathbf{x}^\\top \\mathbf{y} = \\sum_{i=1}^{n} x_i y_i$ resulting in a scalar."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "inwnGrODblKB",
        "outputId": "a39ac28b-7fd2-4379-9dfd-32db76789121"
      },
      "source": [
        "x = np.ones(4); y = 2*np.ones(4)\n",
        "x, y, np.dot(x, y)"
      ],
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(array([1., 1., 1., 1.]), array([2., 2., 2., 2.]), 8.0)"
            ]
          },
          "metadata": {},
          "execution_count": 23
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "esCtUVFJp8Hj"
      },
      "source": [
        "The dot product has a geometric interpretation related to the **angle** between the two vectors\n",
        "\n",
        "$$\n",
        "\\mathbf{x}\\cdot\\mathbf{y} = \\mathbf{x}^\\top\\mathbf{y} = \\|\\mathbf{x}\\|\\|\\mathbf{y}\\|\\cos\\theta,\n",
        "$$\n",
        "\n",
        "where $\\| \\cdot \\|$ is the **norm** operator applied to tha vector. Norms will be discussed later on. \n",
        "\n",
        "In the Machine Learning contexts, the angle $\\theta$ is often used to measure the closeness, or similarity, of two vectors. This can be computed as\n",
        "\n",
        "$$\n",
        "\\cos\\theta = \\frac{\\mathbf{x}^\\top\\mathbf{y}}{\\|\\mathbf{x}\\|\\|\\mathbf{y}\\|}.\n",
        "$$\n",
        "\n",
        "This (cosine) similarity takes values between -1 and 1. A maximum value of $1$\n",
        "when the two vectors point in the same direction, a minimum value of $-1$ when pointing in opposite directions, and a value of $0$ when orthogonal."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "wUCjcZIUqW6y",
        "outputId": "dc69cc9e-8231-4018-f471-b1047f3aa92d"
      },
      "source": [
        "np.arccos(x.dot(y) / (np.linalg.norm(x) * np.linalg.norm(y)))"
      ],
      "execution_count": 24,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0.0"
            ]
          },
          "metadata": {},
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AOvA-09gb8HJ"
      },
      "source": [
        "Consider now the dot product of a matrix $\\mathbf{A} \\in \\mathbb{R}^{m \\times n}$ and a vector $\\mathbf{x} \\in \\mathbb{R}^n$.\n",
        "To follow with the above dot-product definition we write the matrix $\\mathbf{A}$ in terms of its **row** vectors\n",
        "\n",
        "$$\\mathbf{A}=\n",
        "\\begin{bmatrix}\n",
        "\\mathbf{a}^\\top_{1} \\\\\n",
        "\\mathbf{a}^\\top_{2} \\\\\n",
        "\\vdots \\\\\n",
        "\\mathbf{a}^\\top_m \\\\\n",
        "\\end{bmatrix},$$\n",
        "\n",
        "where each $\\mathbf{a}^\\top_{i} \\in \\mathbb{R}^n$\n",
        "is a **row** vector of length $n$, representing the $i^\\mathrm{th}$ row of the matrix $\\mathbf{A}$.\n",
        "Now, the matrix-vector dot product $\\mathbf{A}\\mathbf{x}$\n",
        "is simply a column vector of length $m$,\n",
        "whose $i^\\mathrm{th}$ element is the dot product $\\mathbf{a}^\\top_i \\cdot \\mathbf{x}=\\mathbf{a}_i \\mathbf{x}$\n",
        "\n",
        "$$\n",
        "\\mathbf{A}\\cdot\\mathbf{x}\n",
        "= \\begin{bmatrix}\n",
        "\\mathbf{a}^\\top_{1} \\\\\n",
        "\\mathbf{a}^\\top_{2} \\\\\n",
        "\\vdots \\\\\n",
        "\\mathbf{a}^\\top_m \\\\\n",
        "\\end{bmatrix}\\cdot\\mathbf{x}\n",
        "= \\begin{bmatrix}\n",
        " \\mathbf{a}^\\top_{1}\\cdot \\mathbf{x}  \\\\\n",
        " \\mathbf{a}^\\top_{2}\\cdot \\mathbf{x} \\\\\n",
        "\\vdots\\\\\n",
        " \\mathbf{a}^\\top_{m}\\cdot \\mathbf{x}\\\\\n",
        "\\end{bmatrix}\n",
        "= \\begin{bmatrix}\n",
        " \\mathbf{a}_{1} \\mathbf{x}  \\\\\n",
        " \\mathbf{a}_{2} \\mathbf{x} \\\\\n",
        "\\vdots\\\\\n",
        " \\mathbf{a}_{m} \\mathbf{x}\\\\\n",
        "\\end{bmatrix}\n",
        "= \\begin{bmatrix}\n",
        " b_{1} \\\\\n",
        " b_{2} \\\\\n",
        "\\vdots\\\\\n",
        " b_{m}\\\\\n",
        "\\end{bmatrix}.\n",
        "$$\n",
        "\n",
        "To make it clear, in the above example there are $m$ dot products, each $\\mathbf{a}^\\top_i \\mathbf{x}$ which is a multiplcation of an $n$-sized $\\mathbf{a}^\\top_i$ by an $n$-sized $\\mathbf{x}$. The result of each dot product is a scalar.\n",
        "\n",
        "We can think of the multiplication of $\\mathbf{A}\\in \\mathbb{R}^{m \\times n}$ by $\\mathbf{x}\\in \\mathbb{R}^n$ as a transformation that projects vectors, $\\mathbf{x}\\in \\mathbb{R}^n$,\n",
        "from $\\mathbb{R}^{n}$ to $\\mathbb{R}^{m}$.\n",
        "Note that the column dimension of $\\mathbf{A}$ must be the same as the dimension of $\\mathbf{x}$.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "eL7qTrDUUUx5",
        "outputId": "8336123a-b0cb-4f04-c504-39bebe25a97d"
      },
      "source": [
        "A = np.array([[1, 2], [3, 4], [5, 6]])\n",
        "x = np.array([1,1])\n",
        "np.dot(A, x)"
      ],
      "execution_count": 25,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([ 3,  7, 11])"
            ]
          },
          "metadata": {},
          "execution_count": 25
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PL7VFqE1E52v"
      },
      "source": [
        "Whereas this is computation results in broadcasting "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "gv9uhkBZCkFo",
        "outputId": "12102709-d121-4cc9-9b24-c4db9579d7a7"
      },
      "source": [
        "A*x"
      ],
      "execution_count": 26,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[1, 2],\n",
              "       [3, 4],\n",
              "       [5, 6]])"
            ]
          },
          "metadata": {},
          "execution_count": 26
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZUibzMcgGO2m"
      },
      "source": [
        "Next we consider matrix-matrix multiplication.\n",
        "Given two matrices $\\mathbf{A} \\in \\mathbb{R}^{m \\times k}$ and $\\mathbf{B} \\in \\mathbb{R}^{k \\times n}$:\n",
        "\n",
        "$$\\mathbf{A}=\\begin{bmatrix}\n",
        " a_{11} & a_{12} & \\cdots & a_{1k} \\\\\n",
        " a_{21} & a_{22} & \\cdots & a_{2k} \\\\\n",
        "\\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
        " a_{m1} & a_{m2} & \\cdots & a_{mk} \\\\\n",
        "\\end{bmatrix},\\quad\n",
        "\\mathbf{B}=\\begin{bmatrix}\n",
        " b_{11} & b_{12} & \\cdots & b_{1n} \\\\\n",
        " b_{21} & b_{22} & \\cdots & b_{2n} \\\\\n",
        "\\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
        " b_{k1} & b_{k2} & \\cdots & b_{kn} \\\\\n",
        "\\end{bmatrix}.$$\n",
        "\n",
        "\n",
        "Denote by $\\mathbf{a}^\\top_{i} \\in \\mathbb{R}^k$\n",
        "the row vector representing the $i^\\mathrm{th}$ row of the matrix $\\mathbf{A}$,\n",
        "and let $\\mathbf{b}_{j} \\in \\mathbb{R}^k$\n",
        "be the column vector of the $j^\\mathrm{th}$ column of the matrix $\\mathbf{B}$.\n",
        "The dot matrix-matrix product $\\mathbf{C} = \\mathbf{A}\\cdot\\mathbf{B}$, is easiest to understand with $\\mathbf{A}$ specified by its row vectors and $\\mathbf{B}$ specified by its column vectors,\n",
        "\n",
        "$$\n",
        "\\mathbf{A}=\n",
        "\\begin{bmatrix}\n",
        "\\mathbf{a}^\\top_{1} \\\\\n",
        "\\mathbf{a}^\\top_{2} \\\\\n",
        "\\vdots \\\\\n",
        "\\mathbf{a}^\\top_m \\\\\n",
        "\\end{bmatrix},\n",
        "\\quad \\mathbf{B}=\\begin{bmatrix}\n",
        " \\mathbf{b}_{1} & \\mathbf{b}_{2} & \\cdots & \\mathbf{b}_{n} \\\\\n",
        "\\end{bmatrix}.\n",
        "$$\n",
        "\n",
        "\n",
        "The matrix product $\\mathbf{C}\\in \\mathbb{R}^{m \\times n}$ is produced by computing each element $c_{ij}$ as the dot product $\\mathbf{a}^\\top_i \\mathbf{b}_j$:\n",
        "\n",
        "$$\n",
        "\\begin{align}\n",
        "\\mathbf{C} &= \\mathbf{A\\cdot B} \\\\\n",
        "&= \\begin{bmatrix}\n",
        "\\mathbf{a}^\\top_{1} \\\\\n",
        "\\mathbf{a}^\\top_{2} \\\\\n",
        "\\vdots \\\\\n",
        "\\mathbf{a}^\\top_m \\\\\n",
        "\\end{bmatrix}\n",
        "\\cdot\n",
        "\\begin{bmatrix}\n",
        " \\mathbf{b}_{1} & \\mathbf{b}_{2} & \\cdots & \\mathbf{b}_{n} \\\\\n",
        "\\end{bmatrix}\\\\\n",
        "&= \\begin{bmatrix}\n",
        "\\mathbf{a}^\\top_1\\cdot \\mathbf{b}_1 & \\mathbf{a}^\\top_1\\cdot\\mathbf{b}_2& \\cdots & \\mathbf{a}^\\top_1\\cdot \\mathbf{b}_n \\\\\n",
        " \\mathbf{a}^\\top_2\\cdot\\mathbf{b}_1 & \\mathbf{a}^\\top_2\\cdot \\mathbf{b}_2 & \\cdots & \\mathbf{a}^\\top_2\\cdot \\mathbf{b}_n\\\\\n",
        " \\vdots & \\vdots & \\ddots &\\vdots\\\\\n",
        "\\mathbf{a}^\\top_m\\cdot \\mathbf{b}_1 & \\mathbf{a}^\\top_m\\cdot\\mathbf{b}_2& \\cdots& \\mathbf{a}^\\top_m\\cdot \\mathbf{b}_n\n",
        "\\end{bmatrix}\\\\\n",
        "&= \\begin{bmatrix}\n",
        "\\mathbf{a}_1\\mathbf{b}_1 & \\mathbf{a}_1\\mathbf{b}_2& \\cdots & \\mathbf{a}_1 \\mathbf{b}_n \\\\\n",
        " \\mathbf{a}_2\\mathbf{b}_1 & \\mathbf{a}_2 \\mathbf{b}_2 & \\cdots & \\mathbf{a}_2 \\mathbf{b}_n\\\\\n",
        " \\vdots & \\vdots & \\ddots &\\vdots\\\\\n",
        "\\mathbf{a}_m \\mathbf{b}_1 & \\mathbf{a}_m\\mathbf{b}_2& \\cdots& \\mathbf{a}_m \\mathbf{b}_n\n",
        "\\end{bmatrix}.\n",
        "\\end{align}\n",
        "$$\n",
        "\n",
        "Again, $\\mathbf{a}_1\\mathbf{b}_1$ is the dot product of the 1st row in $\\mathbf A$ by the 1st column in $\\mathbf B$, etc.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "v8svglKCKZ8R"
      },
      "source": [
        "It is common notation practice to *omit* the dot while writing $\\mathbf A \\cdot \\mathbf x$ or $\\mathbf A \\cdot \\mathbf B$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "YTKZejaNUivZ",
        "outputId": "13df1cce-eec9-410f-9b90-9c00a829ab58"
      },
      "source": [
        "A = np.array([[1, 2], [3, 4], [5, 6]])\n",
        "B = np.array([[5, 3], [2, 2]])\n",
        "A.dot(B) "
      ],
      "execution_count": 27,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 9,  7],\n",
              "       [23, 17],\n",
              "       [37, 27]])"
            ]
          },
          "metadata": {},
          "execution_count": 27
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "D-iLXK5Xessk"
      },
      "source": [
        "Matrix mutliplication is **distributive**, i.e. $\\mathbf{A}(\\mathbf{B}+\\mathbf{C})=\\mathbf{A}\\mathbf{B}+\\mathbf{A}\\mathbf{C}$:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "JdQDBqjYUi0g",
        "outputId": "5bb91ba2-785f-4949-b127-accc6e6f0b7a"
      },
      "source": [
        "A = np.array([[2, 3], [1, 4], [7, 6]])\n",
        "B = np.array([[5], [2]])\n",
        "C = np.array([[4], [3]])\n",
        "(A.dot(B+C) == A.dot(B)+A.dot(C)).all()"
      ],
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {},
          "execution_count": 28
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nvb0PHDkexFT"
      },
      "source": [
        "Matrix mutliplication is **associative**, i.e. $\\mathbf{A}(\\mathbf{B}\\mathbf{C})=(\\mathbf{A}\\mathbf{B})\\mathbf{C}$:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "N3Omzn1eUi3M",
        "outputId": "469334cb-cb30-40b0-8c7b-862031b25dbe"
      },
      "source": [
        "A = np.array([[2, 3], [1, 4], [7, 6]])\n",
        "B = np.array([[5, 3], [2, 2]])\n",
        "C = np.array([[4], [3]])\n",
        "(A.dot(B.dot(C)) == (A.dot(B)).dot(C)).all()"
      ],
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {},
          "execution_count": 29
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lwc0DEQ0fVJ6"
      },
      "source": [
        "Vector multiplication is commutative, i.e. $\\mathbf{x}^\\top\\mathbf{y}=\\mathbf{y}^\\top\\mathbf{x}$"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "mRfTyRIXUi8c",
        "outputId": "a2852d93-61a1-4816-ad5c-ad66ab3fb1d1"
      },
      "source": [
        "x = np.array([[2], [6]])\n",
        "y = np.array([[5], [2]])\n",
        "(x.T.dot(y) == y.T.dot(x)).all()"
      ],
      "execution_count": 30,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {},
          "execution_count": 30
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cFCNZV_ZfD3A"
      },
      "source": [
        "However, matrix multiplication is **not commutative**, i.e. $\\mathbf{A}\\mathbf{B}\\ne\\mathbf{B}\\mathbf{A}$:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-o_1JP_fUi5l",
        "outputId": "2486b6d3-7241-4ddb-fbeb-a66a28a55982"
      },
      "source": [
        "A = np.array([[2, 3], [6, 5]])\n",
        "B = np.array([[5, 3], [2, 2]])\n",
        "(np.dot(A, B) == np.dot(B, A)).all()"
      ],
      "execution_count": 31,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "False"
            ]
          },
          "metadata": {},
          "execution_count": 31
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "56HqWX-d0-xp"
      },
      "source": [
        "## Norms\n",
        "\n",
        "One of the important operators in linear algebra are the **norms**.\n",
        "The norm of a vector tells you how large a vector is by maping a vector\n",
        "to a scalar. This scalar measures, not the dimensions, but the magnitude of the components.\n",
        "Formally, given any vector $\\mathbf{x}$, the vector norm is a function $f$ that has multiple propeerties: \n",
        "* The first is a scaling property that says\n",
        "that if we scale all the elements of a vector\n",
        "by a constant factor $\\alpha$,\n",
        "its norm also scales by the **absolute value**\n",
        "of the same constant factor. In example,\n",
        "\n",
        "$$f(\\alpha \\mathbf{x}) = |\\alpha| f(\\mathbf{x}).$$\n",
        "\n",
        "* The second property is the triangle inequality:\n",
        "\n",
        "$$f(\\mathbf{x} + \\mathbf{y}) \\leq f(\\mathbf{x}) + f(\\mathbf{y}).$$\n",
        "\n",
        "* The third property simply says that the norm must be non-negative:\n",
        "\n",
        "$$f(\\mathbf{x}) \\geq 0.$$\n",
        "\n",
        "The final property requires that the smallest norm is achieved if and only if \n",
        "by a vector consisting of all zeros.\n",
        "\n",
        "$$\\forall i, \\mathbf{x}_i = 0 \\Leftrightarrow f(\\mathbf{x})=0.$$\n",
        "\n",
        "The familiar **Euclidean distance** is a norm, typically named \n",
        "the $L_2$ norm, and is defined as square root of the sum of vector elements' squares:\n",
        "\n",
        "$$\\|\\mathbf{x}\\|_2 = \\sqrt{\\sum_{i=1}^n x_i^2}.$$\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4JIq38QmHnkZ",
        "outputId": "318cca88-37b4-4d73-9ca5-7b3d60b7ecad"
      },
      "source": [
        "import numpy as np\n",
        "u = np.array([1,2,3]) # L2 norm\n",
        "np.linalg.norm(u, ord=2)"
      ],
      "execution_count": 32,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3.7416573867739413"
            ]
          },
          "metadata": {},
          "execution_count": 32
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3glDpn80NJf1"
      },
      "source": [
        "The $L_1$ norm is defined as the sum of the absolute values of the vector elements:\n",
        "\n",
        "$$\\|\\mathbf{x}\\|_1 = \\sum_{i=1}^n \\left|x_i \\right|.$$"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "1WGa0D2KIOLd",
        "outputId": "005eca2f-d9e7-49af-e7bd-00481421fc7d"
      },
      "source": [
        "u = np.array([1,2,3])\n",
        "np.linalg.norm(u, ord=1) # L1 norm"
      ],
      "execution_count": 33,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "6.0"
            ]
          },
          "metadata": {},
          "execution_count": 33
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7I6Z3xDRHyhy"
      },
      "source": [
        "In more generality, the $L_p$ norm is defined as \n",
        "\n",
        "$$\\|\\mathbf{x}\\|_p = \\left(\\sum_{i=1}^n \\left|x_i \\right|^p \\right)^{1/p}.$$"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3oyf3VupIW9Y",
        "outputId": "c93f1714-9509-44ca-b3d5-fb97ac68651c"
      },
      "source": [
        "u = np.array([1,2,3])\n",
        "np.linalg.norm(u, ord=np.inf) # L-inf norm, basically choosing the maximum value within the array"
      ],
      "execution_count": 34,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3.0"
            ]
          },
          "metadata": {},
          "execution_count": 34
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1zOUYpzLgQ9X"
      },
      "source": [
        "## Identity matrices\n",
        "\n",
        "The identity matrix of size n is the $n \\times n$ square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by $\\mathbf I_n$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2mgVh7frUU0u",
        "outputId": "5a97a88e-0f38-45a4-d4a2-ced97b0178fc"
      },
      "source": [
        "A = np.eye(3)\n",
        "A"
      ],
      "execution_count": 35,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[1., 0., 0.],\n",
              "       [0., 1., 0.],\n",
              "       [0., 0., 1.]])"
            ]
          },
          "metadata": {},
          "execution_count": 35
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DuRY1HnfUU3p",
        "outputId": "f6a471fc-e93c-4ac1-c087-a078f7d331c9"
      },
      "source": [
        "x = np.array([[2], [6], [3]])\n",
        "x"
      ],
      "execution_count": 36,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[2],\n",
              "       [6],\n",
              "       [3]])"
            ]
          },
          "metadata": {},
          "execution_count": 36
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zw-FDOW2gKaA",
        "outputId": "8f945d2a-db4e-4557-cf4c-65927490d73b"
      },
      "source": [
        "b = A.dot(x)\n",
        "b"
      ],
      "execution_count": 37,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[2.],\n",
              "       [6.],\n",
              "       [3.]])"
            ]
          },
          "metadata": {},
          "execution_count": 37
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Pb23t0tPgVgu"
      },
      "source": [
        "## Inverse matrices\n",
        "\n",
        "An $n\\times n$ square matrix $\\mathbf A$ is called invertible (also nonsingular or nondegenerate), if there exists an $n\\times n$ square matrix $\\mathbf B$ such that\n",
        "\n",
        "$$\n",
        "\\mathbf {AB} =\\mathbf {BA} =\\mathbf {I} _{n}.\n",
        "$$\n",
        "\n",
        "In this case, the matrix $\\mathbf B$ is uniquely determined by $\\mathbf A$, and is called the inverse of $\\mathbf A$, denoted by $\\mathbf A^{-1}$.\n",
        "A square matrix that is not invertible is called singular or degenerate. \n",
        "This topic will be discussed further in later sections."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3hB-6vVngKcP",
        "outputId": "04867de2-4eed-424d-ec96-085326a257e8"
      },
      "source": [
        "A = np.array([[3, 0, 2], [2, 0, -2], [0, 1, 1]])\n",
        "A"
      ],
      "execution_count": 38,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 3,  0,  2],\n",
              "       [ 2,  0, -2],\n",
              "       [ 0,  1,  1]])"
            ]
          },
          "metadata": {},
          "execution_count": 38
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ARFFY1sVgKfJ",
        "outputId": "f857b273-3b04-41ec-b447-114fc6fdf981"
      },
      "source": [
        "A_inv = np.linalg.inv(A)\n",
        "A_inv"
      ],
      "execution_count": 39,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 0.2,  0.2,  0. ],\n",
              "       [-0.2,  0.3,  1. ],\n",
              "       [ 0.2, -0.3, -0. ]])"
            ]
          },
          "metadata": {},
          "execution_count": 39
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ZFYOqIhtgKg5",
        "outputId": "d674c9a9-7a20-4776-afa9-d34327bb6a64"
      },
      "source": [
        "A_inv.dot(A)"
      ],
      "execution_count": 40,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 1.00000000e+00,  0.00000000e+00, -5.55111512e-17],\n",
              "       [ 0.00000000e+00,  1.00000000e+00,  0.00000000e+00],\n",
              "       [ 0.00000000e+00,  0.00000000e+00,  1.00000000e+00]])"
            ]
          },
          "metadata": {},
          "execution_count": 40
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lKtv4rawxElY"
      },
      "source": [
        "## Hyperplanes"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "r1JmccHgLqj4"
      },
      "source": [
        "\n",
        "\n",
        "A key object in linear algebra is the **hyperplane**.\n",
        "In two dimensions the hyperplane is a **line**, and in three dimensions it is a **plane**. In more generality, in an $d$-dimensional vector space, a hyperplane has $d-1$ dimensions\n",
        "and **divides the space into two half-spaces**. \n",
        "In the Machine Learning language in the contex of classification hyperplanes that separate the space are named **decision planes**. \n",
        "\n",
        "In example, \n",
        "* if $\\mathbf{a}=(1,2)$ the equation $\\mathbf{a} \\cdot \\mathbf{b}=1$ defines the **line** $2y = 1 - x$ in the **two dimensional** space, while\n",
        "* if $\\mathbf{a}=(1,2,3)$ and $\\mathbf{a} \\cdot \\mathbf{b}=1$ defines the **plane** $ z= 1 - x-2y$ in the **three dimensional** space.\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B-yrv9cOgmjp"
      },
      "source": [
        "## Solving a system of linear equations\n",
        "\n",
        "The set of equations\n",
        "\n",
        "$$\n",
        "\\mathbf A \\mathbf x = \\mathbf b\n",
        "$$\n",
        "\n",
        "where $\\mathbf{A}\\in \\mathbb{R}^{m \\times n}$, $\\mathbf{x}\\in \\mathbb{R}^n$, and $\\mathbf{b}\\in \\mathbb{R}^m$, has the solution\n",
        "\n",
        "$$\n",
        "\\mathbf A^{-1} \\mathbf A \\mathbf x =\\mathbf I_n\\mathbf x =\\mathbf x=\\mathbf A^{-1}  \\mathbf b\n",
        "$$\n",
        "\n",
        "given that $\\mathbf A^{-1}$ exists.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dSrLEFo-h2p5"
      },
      "source": [
        "with $m=n=2$:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "I3qXBAsrgKjU",
        "outputId": "55568bd8-2718-4775-8ca5-2ec97db1e5d9"
      },
      "source": [
        "A = np.array([[2, -1], [1, 1]])\n",
        "b = np.array([0, 3])\n",
        "x = np.linalg.inv(A).dot(b)\n",
        "x"
      ],
      "execution_count": 41,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([1., 2.])"
            ]
          },
          "metadata": {},
          "execution_count": 41
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BbEdBHowiEaB"
      },
      "source": [
        "with $m=3$, and $n=2$ we use a **pseudoinverse**:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "E6_IGeiviBvu",
        "outputId": "18c16630-6ab8-45f7-b894-85d72d123358"
      },
      "source": [
        "A = np.array([[2, -1], [1, 1], [1, 1]])\n",
        "b = np.array([0,3,0])\n",
        "x = np.linalg.pinv(A).dot(b)\n",
        "x"
      ],
      "execution_count": 42,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([0.5, 1. ])"
            ]
          },
          "metadata": {},
          "execution_count": 42
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZTY5gLUihcFl"
      },
      "source": [
        "## Linear equations"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "t39Khka7a4A5"
      },
      "source": [
        "The set of equations\n",
        "\n",
        "$$\\mathbf{A}\\mathbf{x}=\\mathbf{b}$$\n",
        "\n",
        "correspond to an $m$ equations with $n$ unknowns\n",
        "\n",
        "$$\n",
        "\\begin{align}\n",
        "a_{1,1}x_1 + a_{1,2}x_2 + \\cdots + a_{1,n}x_n = b_1 \\\\\\\\\n",
        "a_{2,1}x_1 + a_{2,2}x_2 + \\cdots + a_{2,n}x_n = b_2 \\\\\\\\\n",
        "\\cdots \\\\\\\\\n",
        "a_{m,1}x_1 + a_{m,2}x_2 + \\cdots + a_{m,n}x_n = b_m\n",
        "\\end{align}\n",
        "$$\n",
        "\n",
        "or\n",
        "\n",
        "$$\n",
        "\\begin{align}\n",
        "\\begin{bmatrix}\n",
        "    a_{1,1} & a_{1,2} & \\cdots & a_{1,n} \\\\\\\\\n",
        "    a_{2,1} & a_{2,2} & \\cdots & a_{2,n} \\\\\\\\\n",
        "    \\cdots & \\cdots & \\cdots & \\cdots \\\\\\\\\n",
        "    a_{m,1} & a_{m,2} & \\cdots & a_{m,n}\n",
        "\\end{bmatrix}\n",
        "\\begin{bmatrix}\n",
        "    x_1 \\\\\\\\\n",
        "    x_2 \\\\\\\\\n",
        "    \\cdots \\\\\\\\\n",
        "    x_n\n",
        "\\end{bmatrix}\n",
        "=\n",
        "\\begin{bmatrix}\n",
        "    b_1 \\\\\\\\\n",
        "    b_2 \\\\\\\\\n",
        "    \\cdots \\\\\\\\\n",
        "    b_m\n",
        "\\end{bmatrix}.\n",
        "\\end{align}\n",
        "$$\n",
        "\n",
        "Commonly, we are given $\\mathbf{A}$ and $\\mathbf{b}$ as inputs, and we solve for $\\mathbf{x}$ that satisfy the above equations.\n",
        "\n",
        "How many solutions does $\\mathbf{A}\\mathbf{x}=\\mathbf{b}$ have? There are the three possibilites:\n",
        "1. No solution\n",
        "2. One solution\n",
        "3. Infinite number of solutions\n",
        " \n",
        "Why can't there be more than one solution and less than an infinite number of solutions?\n",
        "\n",
        "On the intuition level, it is because we are working with linear equations.\n",
        "It is clear if we consider the simple scenario of two equations and two unknowns: the solution of this system corresponds to the intersection of lines. \n",
        "1. One possibility is that the two lines never cross (parallel). \n",
        "2. Another possibility is that they cross exactly once. \n",
        "3. And the last possibility is that they cross everywhere (superimposed)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nTpf_m2Aa4A6"
      },
      "source": [
        "There are two ways to describe a system of linear equations: the **row view** and the **column view**."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nLbk94SDa4A7"
      },
      "source": [
        "## Row view\n",
        "\n",
        "The row view is probably more intuitive than the column view.\n",
        "We mentioned that the solution of a linear system of equations are the sets of values of $\\mathbf x = (x_1, x_2, ... x_n)$ that satisfy all equations. For instance, in the case of $\\mathbf{A}\\in \\mathbb{R}^{m \\times n}$ with $m=n=2$ the equations correspond to 2 lines in the 2-dimensional space and the solution of the system is the intersection of these lines.\n",
        "\n",
        "As mentioned before, a linear system can be viewed as a set of $(n-1)$-dimensional hyperplanes in a $n$-dimensional space. The system can also be characterized by its number of equations $m$, and the number of unknown variables $n$.\n",
        "\n",
        "* If $m \\gt n$, there are more equations than unknowns, the system is called **overdetermined**. For example, consider a system of 3 equations (represented by 3 lines) and 2 unknowns (corresponding to 2 dimensions). If the equations (or lines) are independent in this system, there is no solution since there is no point that belongs to the three lines.\n",
        "* If $m \\lt n$, there are more unknowns than equations, and the system is termed **underdetermined**. For example, consider a system of 1 equation (1 line) and 2 dimensions. In this case, each point along the line is a solution to the system, resulting in an infinite number of solutions.\n",
        "\n",
        "Let's look at these examples in more depth:\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1QQXW5dqa4A7"
      },
      "source": [
        "### Example 1: 1 equation and 2 variables\n",
        "\n",
        "Let us start with an **underdetermined** example with  $m=1$ and  $n=2$:\n",
        "\n",
        "$$\n",
        "a_{1,1}x_1 + a_{1,2}x_2 = b_1\n",
        "$$\n",
        "\n",
        "The graphical interpretation of $n=2$ is that we have a 2-dimensional space represented visually by 2 axes. Since the hyperplane is of $n-1$-dimensional, we have a 1-dimensional hyperplane which is simply a line. As $m=1$, we have only one equation. This means that we have only one line characterizing the linear system.\n",
        "\n",
        "Note that the last equation can also be written in a way that may be more common:\n",
        "\n",
        "$$\n",
        "x_2 = \\frac{a_{1,1}}{a_{1,2}}x_1 +\\frac{b_1}{a_{1,2}}b_1,\\quad\\text{or}\\quad\n",
        "y = \\frac{a_{1,1}}{a_{1,2}}x +\\frac{b_1}{a_{1,2}}b_1,\n",
        "$$\n",
        "\n",
        "where $y=x_2$, and $x=x_1$.\n",
        "\n",
        "The solutions of this linear system correspond to ALL the values of $x$ and $y$ such that $y = \\frac{a_{1,1}}{a_{1,2}}x +\\frac{b_1}{a_{1,2}}b_1$ holds. Practicly, it corresponds to each and every point along the line so there are  infinite number of solutions.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UGi70ZGumAMc"
      },
      "source": [
        "### Example 2: 2 equation and 2 variables\n",
        "\n",
        "Let us explore an example with  $m=2$ and  $n=2$:\n",
        "\n",
        "$$\n",
        "a_{1,1}x_1 + a_{1,2}x_2 = b_1\\\\\n",
        "a_{2,1}x_1 + a_{2,2}x_2 = b_2.\n",
        "$$\n",
        "\n",
        "The graphical interpretation of $n=2$ is as before. That is, we have a system in the 2-dimensional space, represented visually with 2 axes, and each equation represents a $1$-dimensional hyperplane which is simply a line. \n",
        "\n",
        "But, here $m=2$, which means that we have two equations or 2 lines in the 2-dimensional space.\n",
        "Now, there are multiple scenarios:\n",
        "\n",
        "* The two lines run in parallel, and there is no solution,\n",
        "* The two lines intersect, and there is a unique solution, or\n",
        "* The two lines superimpose representing the same equation (or line). In this case, there is an infinite number of solutions since each point along the lines correspond to a solution.\n",
        "\n",
        "<!-- Same conclusion can be drawn with higher values of $m$ (number of equations) and $n$ (number of dimensions). For example, two 2-dimensional planes in a 3-dimensional space can be \n",
        "* parallel (no solution),\n",
        "* cross (infinitely many solutions since their crossing is a line), or\n",
        "* superimposed (infinitely many solutions).  -->\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NvvEPKu0o9Nv"
      },
      "source": [
        "### Example 3: 3 equation and 2 variables\n",
        "\n",
        "Let us explore an **overdetermined** example with  $m=3$ and  $n=2$:\n",
        "\n",
        "$$\n",
        "a_{1,1}x_1 + a_{1,2}x_2 = b_1\\\\\n",
        "a_{2,1}x_1 + a_{2,2}x_2 = b_2\\\\\n",
        "a_{3,1}x_1 + a_{3,2}x_2 = b_3\n",
        "$$\n",
        "\n",
        "The graphical interpretation of $n=2$ is as before. That is, we have a system in the 2-dimensional space, represented by 2 axes, and each equation represents an $1$-dimensional hyperplane which, as before, is simply a line. \n",
        "\n",
        "Here $m=3$, which means that we have three equations, or 3 lines in a 2-dimensional space.\n",
        "\n",
        "There are multiple scenarios:\n",
        "* The three lines run in parallel, and there is no solution,\n",
        "* The three lines intersect. If the three lines are independent, there are multiple intersections with no unique solution,\n",
        "* Two lines are dependent, and the third is independent: we have a unique solution at the intersection of the dependent's two with the third line, or\n",
        "* The three lines superimpose: there is an infinite number of solutions.\n",
        "\n",
        "These examples can be generalized to higher spaces."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uxc0YeSd8uHB"
      },
      "source": [
        "## Linear combination\n",
        "\n",
        "The linear combination of 2 vectors corresponds to their weighted sum.\n",
        "In example:\n",
        "\n",
        "$$\n",
        "\\mathbf{x}^\\top=(1,2,3),~\\mathbf{y}^\\top=(4,5,6),\n",
        "\\quad \\text{and}\n",
        "\\quad \\mathbf{z}^\\top=a\\mathbf{x}^\\top+b\\mathbf{y}^\\top,\\text{with}~ a=1,~b=2.\n",
        "$$\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4qVrxGr28w-a",
        "outputId": "d03c4c83-1857-4811-f945-51fd925228e5"
      },
      "source": [
        "a=1.;b=2.;\n",
        "a*np.array([1,2,3])+b*np.array([4,5,6])"
      ],
      "execution_count": 43,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([ 9., 12., 15.])"
            ]
          },
          "metadata": {},
          "execution_count": 43
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "n_roc_eFxNxa"
      },
      "source": [
        "## Span"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bpDRxg31a4A-"
      },
      "source": [
        "\n",
        "\n",
        "Consider the above $\\mathbf{x}$ and $\\mathbf{y}$: ALL the points that can be reached by their combination via some $a$ and $b$ are called the set of points is the **span** of the vectors $\\{\\mathbf{x}$, $\\mathbf{y}\\}$.\n",
        "Vector **space** means all the points that can be reached by this vector. In example, \n",
        "* the space of all real numbers is $\\mathbb{R}$, and\n",
        "* for $n$-dimensions the space is $\\mathbb{R}^n$. \n",
        "\n",
        "Vector **subspace** means that the space occupies only part of the space. In example, \n",
        "* a 2-dimensional plane is a subspace in $\\mathbb{R}^3$, and \n",
        "* a line is a subspace in $\\mathbb{R}^2$.\n",
        "\n",
        "In general, we will say that a collection of vectors\n",
        "$\\mathbf{x}_1,\\mathbf{x}_2, \\ldots, \\mathbf{x}_n$ are linearly **dependent**\n",
        "if there exist coefficients $a_1,a_2 \\ldots, a_n$, not all zeros, such that\n",
        "\n",
        "$$\n",
        "\\sum_{i=1}^n a_i\\mathbf{x_i} = 0.\n",
        "$$\n",
        "\n",
        "In this case, we can solve for one of the vectors in terms of a combination of the others, and thus this vector is **redundant**.\n",
        "Similarly, a linear dependence in the columns of a matrix means that this matrix can be **compressed** down to a lower dimension. \n",
        "\n",
        "If there is no linear dependence, we say the vectors are **linearly independent**. In a matrix, if the columns are linearly independent, the matrix cannot be compressed to a lowed dimension.\n",
        "\n",
        "A set of vectors that is linearly **independent** and **spans** some vector space forms a **basis** for that vector space. \n",
        "The **standard basis** (also called natural basis or canonical basis) in $\\mathbb{R}^n$ is the set of vectors whose components are all zero, except one that equals 1. For example, the standard basis in $\\mathbb{R}^2$ is formed by the vectors $\\mathbf{x}^\\top=(1,0)^\\top$ and $\\mathbf{y}^\\top=(0,1)^\\top$.\n",
        "\n",
        "The linear combination of vectors in a space stays in the same space. For instance, any linear combination of two lines in a $\\mathbb{R}^2$ results in another vector in $\\mathbb{R}^2$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SH7ZAk2-a4A_"
      },
      "source": [
        "## Column view\n",
        "\n",
        "It is also possible to represent the solution $\\mathbf{b}$ to the equations $\\mathbf{A}\\mathbf{x}=\\mathbf{b}$ as a linear combination of the columns in $\\mathbf{A}$.\n",
        "\n",
        "To see that, the set of equations\n",
        "\n",
        "$$\n",
        "a_{1,1}x_1 + a_{1,2}x_2 + a_{1,n}x_n = b_1 \\\\\\\\\n",
        "a_{2,1}x_1 + a_{2,2}x_2 + a_{2,n}x_n = b_2 \\\\\\\\\n",
        "\\cdots \\\\\\\\\n",
        "a_{m,1}x_1 + a_{m,2}x_2 + a_{m,n}x_n = b_m\n",
        "$$\n",
        "\n",
        "can be written by grouping the columns in $\\mathbf{A}$\n",
        "\n",
        "$$\n",
        "\\begin{align}\n",
        "x_1\n",
        "\\begin{bmatrix}\n",
        "    a_{1,1}\\\\\\\\\n",
        "    a_{2,1}\\\\\\\\\n",
        "    a_{m,1}\n",
        "\\end{bmatrix}\n",
        "+\n",
        "x_2\n",
        "\\begin{bmatrix}\n",
        "    a_{1,2}\\\\\\\\\n",
        "    a_{2,2}\\\\\\\\\n",
        "    a_{m,2}\n",
        "\\end{bmatrix}\n",
        "+\\cdots+\n",
        "x_n\n",
        "\\begin{bmatrix}\n",
        "    a_{1,n}\\\\\\\\\n",
        "    a_{2,n}\\\\\\\\\n",
        "    a_{m,n}\n",
        "\\end{bmatrix}\n",
        "=\n",
        "\\begin{bmatrix}\n",
        "    b_1\\\\\\\\\n",
        "    b_2\\\\\\\\\n",
        "    b_m\n",
        "\\end{bmatrix}.\n",
        "\\end{align}\n",
        "$$\n",
        "\n",
        "In this view, the solution $\\mathbf{b}$ is a linear combination of the columns of $\\mathbf{A}$, weighted by the components of $\\mathbf{x}$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fA2sIoL8F8L3"
      },
      "source": [
        "\n",
        "* For the **overdetermined** system $m\\gt n$ and there is **no solution**. For example, in the column view,\n",
        "\n",
        "$$\n",
        "\\begin{align}\n",
        "a_{1,1}x_1+a_{1,2}x_2=b_1\\\\\n",
        "a_{2,1}x_1+a_{2,2}x_2=b_2\\\\\n",
        "a_{3,1}x_1+a_{3,2}x_2=b_3\\\\\n",
        "\\end{align}\n",
        "\\quad\\text{corresponds to}\\quad\\\n",
        "x_1\n",
        "\\begin{bmatrix}\n",
        "    a_{1,1}\\\\\n",
        "    a_{2,1}\\\\\n",
        "    a_{3,1}\\\\\n",
        "\\end{bmatrix}\n",
        "+x_2\n",
        "\\begin{bmatrix}\n",
        "    a_{1,2}\\\\\n",
        "    a_{2,2}\\\\\n",
        "    a_{3,2}\n",
        "\\end{bmatrix}\n",
        "=\n",
        "\\begin{bmatrix}\n",
        "    b_{1}\\\\\n",
        "    b_{2}\\\\\n",
        "    b_{3}\n",
        "\\end{bmatrix}.\n",
        "$$\n",
        "\n",
        "In the row view, we have 3 lines, and we are looking for a unique intersection in the 2-dimensional plane. The three lines (if independent) will intersect in multiple points resulting in no solution. In the column view, because $n=2$ the linear combination of two 3-dimensional vectors is not enough to span the 3-dimensional space, unless the vector $\\mathbf{b}$ lies, for some reason, in the subspace formed by these two vectors.\n",
        "\n",
        "* For the **underdetermined** system, $m \\lt n$ and the system has **infinite number of solutions**. As an example in the column view,\n",
        "\n",
        "$$\n",
        "\\begin{align}\n",
        "a_{1,1}x_1+a_{1,2}x_2+a_{1,3}x_3=b_1\\\\\n",
        "a_{2,1}x_1+a_{2,2}x_2+a_{2,3}x_3=b_2\n",
        "\\end{align}\n",
        "\\quad\\text{corresponds to}\\quad\\\n",
        "x_1\n",
        "\\begin{bmatrix}\n",
        "    a_{1,1}\\\\\n",
        "    a_{2,1}\n",
        "\\end{bmatrix}\n",
        "+x_2\n",
        "\\begin{bmatrix}\n",
        "    a_{1,2}\\\\\n",
        "    a_{2,2}\n",
        "\\end{bmatrix}\n",
        "+x_3\n",
        "\\begin{bmatrix}\n",
        "    a_{1,3}\\\\\n",
        "    a_{2,3}\n",
        "\\end{bmatrix}\n",
        "=\n",
        "\\begin{bmatrix}\n",
        "    b_{1}\\\\\n",
        "    b_{2}\n",
        "\\end{bmatrix}.\n",
        "$$\n",
        "\n",
        "But, if the columns of $\\mathbf{A}$ are independent, two of them are enough to reach any point in $\\mathbb{R}^2$. So, two components out of the three in $\\mathbf{x}$ are used to determine the solution while the third is free, meaning that there is an infinite number of solutions.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7XW6ZNIza4BB"
      },
      "source": [
        "## Linear dependency\n",
        "\n",
        "The number of **columns** can thus provide information on the number of solutions. But the number that we have to take into account is the number of linearly **independent** columns. Columns are linearly **dependent** if one of them is a linear combination of the others. In the column view, the direction of two linearly dependent vectors is the same, and this doesn't add value in spanning the space.\n",
        "\n",
        "As an example,\n",
        "\n",
        "$$\n",
        "\\begin{align}\n",
        "x_1+2x_2=b_1\\\\\n",
        "2x_1+4x_2=b_2\n",
        "\\end{align}\n",
        "$$\n",
        "\n",
        "which in the column view is\n",
        "\n",
        "$$\n",
        "\\begin{align}\n",
        "x_1\n",
        "\\begin{bmatrix}\n",
        "    1 \\\\\n",
        "    2\n",
        "\\end{bmatrix}\n",
        "+\n",
        "x_2\n",
        "\\begin{bmatrix}\n",
        "    2 \\\\\n",
        "    4\n",
        "\\end{bmatrix}\n",
        "=\n",
        "\\begin{bmatrix}\n",
        "    b_1 \\\\\n",
        "    b_2\n",
        "\\end{bmatrix}.\n",
        "\\end{align}\n",
        "$$\n",
        "\n",
        "The columns $(1,2)^\\top$ and $(2,4)^\\top$ are **dependent** and hence their linear combination is not enough to span the full $\\mathbb{R}^2$ and reach all points in this space. If $\\mathbf{b}=(3,6)^\\top$ there is a solution $\\mathbf{x}^\\top=(1,1)^\\top$ because the vector $(1,2)^\\top$ spans a subspace of $\\mathbb{R}^2$ that contains the vector $\\mathbf{b}=(3,6)^\\top$.\n",
        "But for a more general solution, as say $\\mathbf{b}=(3,7)$, there is no solution as linear combinations of $(1,2)^\\top$ are not enough to reach all points in $\\mathbb{R}^2$. This is an example of an **overdetermined** system with $m=2\\gt n=1$ because of the linear dependency between the columns.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YrfWgk6Ga4BC"
      },
      "source": [
        "## Square matrix\n",
        "\n",
        "When $\\mathbf{A}\\in\\mathbb{R}^{m\\times n}$ and $m=n$, the matrix $\\mathbf{A}$ is called square matrix and if the columns are linearly **independant** there is a unique solution to $\\mathbf{A}\\mathbf{x}=\\mathbf{b}$.\n",
        "The solution is simply $\\mathbf{x}=\\mathbf{A}^{-1}\\mathbf{b}$, where $\\mathbf{A}^{-1}$ is the inverse of $\\mathbf{A}$.\n",
        "\n",
        "When $\\mathbf{A}^{-1}$ exist, we say that $\\mathbf{A}$ is invertible (a.k.a., nonsingular, or nondegenerate). \n",
        "In this case, the columns and rows of $\\mathbf{A}$ are linearly independent.\n",
        "\n",
        "\n",
        "\n",
        "<!-- A is invertible, that is, A has an inverse, is nonsingular, or is nondegenerate.\n",
        "A is row-equivalent to the n-by-n identity matrix In.\n",
        "A is column-equivalent to the n-by-n identity matrix In.\n",
        "A has n pivot positions.\n",
        "det A ≠ 0. In general, a square matrix over a commutative ring is invertible if and only if its determinant is a unit in that ring.\n",
        "A has full rank; that is, rank A = n.\n",
        "Based on the rank A=n, the equation Ax = 0 has only the trivial solution x = 0. and the equation Ax = b has exactly one solution for each b in Kn.\n",
        "The kernel of A is trivial, that is, it contains only the null vector as an element, ker(A) = {0}.\n",
        "The columns of A are linearly independent.\n",
        "The columns of A span Kn.\n",
        "Col A = Kn.\n",
        "The columns of A form a basis of Kn.\n",
        "The linear transformation mapping x to Ax is a bijection from Kn to Kn.\n",
        "There is an n-by-n matrix B such that AB = In = BA.\n",
        "The transpose AT is an invertible matrix (hence rows of A are linearly independent, span Kn, and form a basis of Kn).\n",
        "The number 0 is not an eigenvalue of A.\n",
        "The matrix A can be expressed as a finite product of elementary matrices.\n",
        "The matrix A has a left inverse (that is, there exists a B such that BA = I) or a right inverse (that is, there exists a C such that AC = I), in which case both left and right inverses exist and B = C = A−1. -->"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ppi8tufgo6m2",
        "outputId": "7c899e97-1d51-4aab-f2a6-ddbf880d80b6"
      },
      "source": [
        "A = np.array([[3, 0, 2], [2, 0, -2], [0, 1, 1]])\n",
        "np.linalg.inv(A)"
      ],
      "execution_count": 44,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 0.2,  0.2,  0. ],\n",
              "       [-0.2,  0.3,  1. ],\n",
              "       [ 0.2, -0.3, -0. ]])"
            ]
          },
          "metadata": {},
          "execution_count": 44
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uIFgIxFdAR6E"
      },
      "source": [
        "## Rank\n",
        "\n",
        "The **column rank** of $\\mathbf{A}$ is the dimension of the column space of $\\mathbf{A}$ (i.e., the number of linearly independent columns), while the **row rank** of $\\mathbf{A}$ is the dimension of the row space of $\\mathbf{A}$ (i.e., the number of linearly independent rows).\n",
        "\n",
        "A fundamental result in linear algebra is that the column rank and the row rank are **always equal**, and this number is called the rank of $\\mathbf{A}$.\n",
        "A matrix $\\mathbf{A}\\in\\mathbb{R}^{m\\times n}$ is said to have **full rank** if it's rank equals to $\\min(m, n$); otherwise, the matrix is **rank deficient**."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "P8wDZ6ZbAVg2",
        "outputId": "442db5fe-1f49-4b99-9972-503a8c018d36"
      },
      "source": [
        "A = np.array([[1,2],[3,4]]); \n",
        "print(A)\n",
        "B = np.array([[1,2],[2,4]]); \n",
        "print(B)\n",
        "C = np.array([[1,0,0],[0,1,0],[0,0,1]])\n",
        "print(C)\n",
        "\n",
        "np.linalg.matrix_rank(A), np.linalg.matrix_rank(B), np.linalg.matrix_rank(C)"
      ],
      "execution_count": 45,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[1 2]\n",
            " [3 4]]\n",
            "[[1 2]\n",
            " [2 4]]\n",
            "[[1 0 0]\n",
            " [0 1 0]\n",
            " [0 0 1]]\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(2, 1, 3)"
            ]
          },
          "metadata": {},
          "execution_count": 45
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dzmF_K5B_Dl-"
      },
      "source": [
        "## Invertibility\n",
        "\n",
        "An $n\\times n$ square matrix $\\mathbf{A}$ is called **invertible** (also **nonsingular** or **nondegenerate**), if there exists an $n\\times n$ square matrix $\\mathbf{B}$ such that\n",
        "\n",
        "$$\n",
        "\\mathbf{A}\\mathbf{B}=\\mathbf{B}\\mathbf{A}=\\mathbf{I}_n\n",
        "$$\n",
        "\n",
        "where $\\mathbf{I}_n$ denotes the $n\\times n$ identity matrix. In this case, then the matrix $\\mathbf{B}$ is uniquely determined by $\\mathbf{A}$, and is called the inverse of $\\mathbf{A}$, denoted by $\\mathbf{A}^{-1}$.\n",
        "\n",
        "A square matrix that is not invertible is called **singular** or **degenerate**. Non-square matrices ($m\\times n$ matrices with $n\\ne n$) do not have an inverse (but they may have a left inverse or right inverse). \n",
        "A square matrix is singular if and only if its determinant is zero. In practice, singular square matrices are pretty rare. \n",
        "\n",
        "\n",
        "\n",
        "$$\n",
        "\\mathbf{A} = \\begin{bmatrix}\n",
        "a & b \\\\\n",
        "c & d\n",
        "\\end{bmatrix},\n",
        "$$\n",
        "\n",
        "then we can see that the inverse is\n",
        "\n",
        "$$\n",
        " \\frac{1}{ad-bc}  \\begin{bmatrix}\n",
        "d & -b \\\\\n",
        "-c & a\n",
        "\\end{bmatrix}.\n",
        "$$\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "sLLk-iAfprap",
        "outputId": "ac358108-7a5e-4cf4-8d4f-21daa71f37fc"
      },
      "source": [
        "A = np.array([[1,2],[2,4]]); \n",
        "np.linalg.det(A)"
      ],
      "execution_count": 46,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0.0"
            ]
          },
          "metadata": {},
          "execution_count": 46
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XhbB4FYnpw4H"
      },
      "source": [
        ""
      ],
      "execution_count": 46,
      "outputs": []
    }
  ]
}