la_08_column_space_right_inverse.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "#### Column space of a matrix"
      ],
      "metadata": {
        "id": "A4SBwbS0YGjA"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "For a matrix $A\\in \\mathbf{R}^{m \\times n}$, its `column space` or range is defined as\n",
        "\n",
        "$$R(A)=\\{Ax |x\\in\\mathbf{R}^n\\}$$\n",
        "\n",
        "$R(A)$ is a `subspace` of $\\mathbf{R}^m$"
      ],
      "metadata": {
        "id": "nidJ0w3oYKMk"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "* $R(A)$ is a set all possible $y$ as the output of $Ax$\n",
        "* $R(A)$ is a set of $y$ for which $y=Ax$ has a solution (not necessarily unique solution)\n",
        "* $R(A)=\\text{span}(a_1, a_2,\\cdots, a_n)$, where each $a_i$ is a column of $A$"
      ],
      "metadata": {
        "id": "mEI5FOktYfYb"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Onto matrix"
      ],
      "metadata": {
        "id": "Z1hkakMIaERY"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "$A$ is called `onto` if $R(A)=\\mathbf{R}^m$\n",
        "\n",
        "This is equivalent to saying\n",
        "\n",
        "* $y=Ax$ can be solved in $x$ for any $y$ (not necessarily unique solution)\n",
        "* $A$ has `right inverse`, $B\\in \\mathbf{R}^{n \\times m}$, such that $AB=I$\n",
        "  * With $A(By)=y$ and $y=Ax$, we have $x=By+\\{z|z\\in N(A)\\}$\n",
        "  * This means $x$ is a `linear combination` of columns in $B$ where $y$ are the `coefficients`\n",
        "* `rows` of $A$ are `independent`\n",
        "* $N(A^T)=\\{0\\}$\n",
        "* $\\det(AA^T)\\neq 0$"
      ],
      "metadata": {
        "id": "CRfjqzZhaG8g"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Nullspace of matrix transpose"
      ],
      "metadata": {
        "id": "IAKClBDCdFkS"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "We see that if we can show equivalence to\n",
        "\n",
        "* $N(A^T)=\\{0\\}$\n",
        "\n",
        "then, through transpose of $A$ and properties of `zero nullspace`, we would get equivalence to\n",
        "\n",
        "* $A$ has right inverse ($A^T$ has left inverse)\n",
        "* rows of $A$ are independent (columns of $A^T$ are independent)\n",
        "* $\\det(AA^T)\\neq 0$"
      ],
      "metadata": {
        "id": "DutUSf9XnEtt"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "(1) $R(A)=\\mathbf{R}^m \\Longrightarrow N(A^T)=\\{0\\}$\n",
        "\n",
        "Since $R(A)=\\mathbf{R}^m$, then, there is `no` nonzero vector $z\\in \\mathbf{R}^m$ that is `orthogonal to all columns` in $A$\n",
        "\n",
        "As a result, for $A^T\\in \\mathbf{R}^{n \\times m}$, `no` nonzero $z\\in \\mathbf{R}^m$ can satisfy\n",
        "\n",
        "$$A^Tz=0$$\n",
        "\n",
        "Therefore, $N(A^T)=\\{0\\}$"
      ],
      "metadata": {
        "id": "IIZWGcV4nnOk"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "(2) $N(A^T)=\\{0\\}\\Longrightarrow  R(A)=\\mathbf{R}^m $\n",
        "\n",
        "Since $N(A^T)=\\{0\\}$, then only solution to $A^Tz=0$ is $z=0$\n",
        "\n",
        "Therefore, `no` nonzero $z\\in \\mathbf{R}^m$ is orthogonal to all columns in $A$\n",
        "\n",
        "So, $R(A)=\\mathbf{R}^m$\n",
        "\n",
        "$R(A)=\\mathbf{R}^m$ constrains matrix $A$ to be `fat` or `square`"
      ],
      "metadata": {
        "id": "YyO40gKEkJJE"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Left and right inverse"
      ],
      "metadata": {
        "id": "RssY3FKx4K63"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "If $A$ has a `right inverse` $B$, then\n",
        "\n",
        "$$(AB)^T=B^TA^T=I$$\n",
        "\n",
        "That is, $A^T$ has a `left inverse` $B^T$"
      ],
      "metadata": {
        "id": "cESSWVgO4OzM"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "We know the left inverse of $A$ when $N(A)=\\{0\\}$ is $(A^TA)^{-1}A^T$\n",
        "\n",
        "To get right inverse of $A$ for $N(A^T)=\\{0\\}$, we first write the left inverse of $A^T$ by swapping $A^T$ and $A$\n",
        "\n",
        "$$(AA^T)^{-1}A$$\n",
        "\n",
        "Then, we transpose it to get `right inverse` of $A$\n",
        "\n",
        "$$((AA^T)^{-1}A)^T=A^T((AA^T)^{-1})^T=A^T((AA^T)^T)^{-1}=A^T(AA^T)^{-1}$$"
      ],
      "metadata": {
        "id": "AMfBAJTP4qsQ"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "8gX4WLFLomkb"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}