la_24_diagonalization_left_right_eigenvector.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": [
        "#### Diagonalization of matrices"
      ],
      "metadata": {
        "id": "s9JRN0lOHziu"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "One of applications of eigenvector and eigenvalue is diagonalization of a matrix, specifically\n",
        "\n",
        "Matrix $A$ is diagonalizable `if and only if` it has independent set of eigenvectors"
      ],
      "metadata": {
        "id": "BxzeF_Ogp0bh"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "To see this\n",
        "\n",
        "(1) Suppose $v_1, \\cdots, v_n$ is a `independent set of eigenvectors` of $A\\in \\mathbf{R}^{n \\times n}$\n",
        "\n",
        "$$Av_i=\\lambda_i v_i$$\n",
        "\n",
        "We can express these as\n",
        "\n",
        "$$A\\begin{bmatrix}v_1 & \\cdots & v_n\\end{bmatrix}=\\begin{bmatrix}v_1 & \\cdots & v_n\\end{bmatrix}\\begin{bmatrix}\\lambda_1 &  & \\\\ & \\ddots & \\\\ & & \\lambda_n\\end{bmatrix}$$\n",
        "\n",
        "Let $v_1, \\cdots, v_n$  be `columns` of a matrix $T$, and $\\Lambda=\\text{diag} (\\lambda_1, \\cdots, \\lambda_n)$, then, we have\n",
        "\n",
        "$$AT=T\\Lambda$$\n",
        "\n",
        "As we assume that eigenvectors are independent, then $T$ is `invertible`. As a result, we can `diagonalize` $A$ as\n",
        "\n",
        "$$T^{-1}AT=\\Lambda$$"
      ],
      "metadata": {
        "id": "kI6DleDYnW95"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "(2) Assume that $A$ is `diagonalizable`, then by definition, there is a matrix $P$ and a diagonal matrix $D$ such that\n",
        "\n",
        "$$P^{-1}AP=D$$\n",
        "\n",
        "or\n",
        "\n",
        "$$\\begin{bmatrix}p_1 & \\cdots & p_n\\end{bmatrix}^{-1}A\\begin{bmatrix}p_1 & \\cdots & p_n\\end{bmatrix}=\\begin{bmatrix}d_1 &  & \\\\ & \\ddots & \\\\ & & d_n\\end{bmatrix}$$\n",
        "\n",
        "Right multiply each side by $\\begin{bmatrix}p_1 & \\cdots & p_n\\end{bmatrix}$\n",
        "\n",
        "we have\n",
        "\n",
        "$$A\\begin{bmatrix}p_1 & \\cdots & p_n\\end{bmatrix}=\\begin{bmatrix}p_1 & \\cdots & p_n\\end{bmatrix}\\begin{bmatrix}d_1 &  & \\\\ & \\ddots & \\\\ & & d_n\\end{bmatrix}$$\n",
        "\n",
        "Then, by `definition`, $p_1, \\cdots, p_n$ are eigenvectors of $A$ with eigenvalues $d_1, \\cdots, d_n$\n",
        "\n",
        "Since $\\begin{bmatrix}p_1 & \\cdots & p_n\\end{bmatrix}$ is `invertible`, then its columns form an `independent set`"
      ],
      "metadata": {
        "id": "CDNA8TaC-x6d"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Not all square matrices are diagonalizable"
      ],
      "metadata": {
        "id": "D7xfTW6apETs"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "For example\n",
        "\n",
        "$$A=\\begin{bmatrix}0 & 1 \\\\ 0 & 0\\end{bmatrix}$$\n",
        "\n",
        "has only eigenvalue of 0\n",
        "\n",
        "So its eigenvectors satisfy\n",
        "\n",
        "$$\\begin{bmatrix}0 & 1 \\\\ 0 & 0\\end{bmatrix}v=0$$\n",
        "\n",
        "Its eigenvectors are `not independent` as they are all in the form of $v=\\begin{bmatrix}b\\\\ 0\\end{bmatrix}$, where $b\\neq 0$"
      ],
      "metadata": {
        "id": "PmivDE0lpM80"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Matrices with distinct eigenvalues are diagonalizable"
      ],
      "metadata": {
        "id": "one9NN1uqIiM"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Let $\\lambda_1,\\cdots, \\lambda_n$ be distinct eigenvalues and $v_1,\\cdots,v_n$ be the corresponding eigenvectors of matrix $A$, that is\n",
        "\n",
        "$$Av_i=\\lambda_i v_i$$\n",
        "\n",
        "Assume that the eigenvectors are `not independent` (we want to show `contradiction` and thereby proving that eigenvectors must be independent, which can lead to diagonalization)\n",
        "\n",
        "Then, we can always reindex the eigenvectors such that eigenvectors $v_1,\\cdots, v_j$ are the smallest `dependent` set, meaning that `there is no subset of j-1 eigenvectors that is dependent`\n",
        "\n",
        "(such dependent set would contain at least two eigenvectors to be `dependent`, or $j\\geq 2$)\n",
        "\n",
        "Then, there exists a set of (`not all zero`) coefficients $a_1,\\cdots, a_{j-1}$ such that\n",
        "\n",
        "$$\\boxed{v_j=a_1 v_1+ \\cdots + a_{j-1} v_{j-1}}$$\n",
        "\n",
        "Left multiply $A$ on both side of the highlighted equation\n",
        "\n",
        "$$\\lambda_j v_j=a_1 \\lambda_1 v_1+ \\cdots + a_{j-1} \\lambda_{j-1} v_{j-1}$$\n",
        "\n",
        "Then, we multiply $\\lambda_j$ on both side of the highlighted equation\n",
        "\n",
        "$$\\lambda_j v_j=a_1 \\lambda_j v_1+ \\cdots + a_{j-1} \\lambda_j v_{j-1}$$\n",
        "\n",
        "Subtract these two, we have\n",
        "\n",
        "$$0=a_1(\\lambda_1-\\lambda_j)v_1+\\cdots+ a_{j-1}(\\lambda_{j-1}-\\lambda_j)v_{j-1}$$\n",
        "\n",
        "Since all eigenvalues are `distinct` and $a_i$'s are `not all zero`, then the only way this equation holds is that $v_i,\\cdots,v_{j-1}$ are `dependent`, which is a contradiction\n",
        "\n",
        "It follows that eigenvectors must be independent, and therefore, the matrix is diagonalizable"
      ],
      "metadata": {
        "id": "K6SC5nTL_0an"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "The reverse is `not true`, for example, $I$ is diagonalizable, but it has `repeated` eigenvalues"
      ],
      "metadata": {
        "id": "iCIZh9p6qQpu"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Diagonalization simplifies many matrix expressions"
      ],
      "metadata": {
        "id": "CjDphtAxeQXS"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "With $T^{-1}AT=\\Lambda$, and $A=T\\Lambda T^{-1}$\n",
        "\n",
        "For `resolvent`, we have\n",
        "\n",
        "$$\\begin{align*}\n",
        "(sI-A)^{-1} & = \\left(TsIT^{-1}-T\\Lambda T^{-1}\\right)^{-1} \\\\\n",
        "&=\\left(T(sI-\\Lambda)T^{-1}\\right)^{-1} \\\\\n",
        "&=T(sI-\\Lambda)^{-1}T^{-1} \\\\\n",
        "&=T \\text{diag}\\left(\\frac{1}{s-\\lambda_1},\\cdots,\\frac{1}{s-\\lambda_n}\\right)T^{-1}\n",
        "\\end{align*}$$"
      ],
      "metadata": {
        "id": "uBnkBgSQeYck"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "For `powers`\n",
        "\n",
        "$$\\begin{align*}\n",
        "A^k &= (T\\Lambda T^{-1})^k \\\\\n",
        "&= (T\\Lambda T^{-1})(T\\Lambda T^{-1})\\cdots (T\\Lambda T^{-1})(T\\Lambda T^{-1}) \\\\\n",
        "&= T\\Lambda (T^{-1}T)\\Lambda (T^{-1}\\cdots T)\\Lambda (T^{-1}T)\\Lambda T^{-1} \\\\\n",
        "&=T\\Lambda^kT^{-1}\\\\\n",
        "&=T\\text{diag}\\left(\\lambda_1^k,\\cdots,\\lambda_n^k\\right)T^{-1}\n",
        "\\end{align*}$$\n",
        "\n",
        "(for $k\\leq 0$ only if $A$ is invertible, i.e., all $\\lambda_i\\neq 0$)"
      ],
      "metadata": {
        "id": "UOVl8QkTgKqy"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "For `exponential`\n",
        "\n",
        "$$\\begin{align*}\n",
        "e^A&= I + A + A^2/2!+\\cdots \\\\\n",
        "&= I + T\\Lambda T^{-1}+ T\\Lambda^2T^{-1}/2!+\\cdots \\\\\n",
        "&=T(I+\\Lambda+\\Lambda^2/2!+\\cdots)T^{-1}\\\\\n",
        "&=Te^{\\Lambda}T^{-1}\\\\\n",
        "&=T\\text{diag}(e^{\\lambda_1},\\cdots,e^{\\lambda_n})T^{-1}\n",
        "\\end{align*}$$"
      ],
      "metadata": {
        "id": "tf55S5dThT08"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Diagonalization simplifies linear relation"
      ],
      "metadata": {
        "id": "iLVVDp8BdlGa"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Assume matrix $A$ is diagonalizable $A=T\\Lambda T^{-1}$\n",
        "\n",
        "If we have two vectors $x, y$ such that $y=Ax$, then we can write\n",
        "\n",
        "$$TT^{-1}y=ATT^{-1}x$$\n",
        "\n",
        "Denote `expansion` of the two vectors in the `eigenvectors` of $A$ as $\\hat{x}=T^{-1}x$ and $\\hat{y}=T^{-1}y$, we have\n",
        "\n",
        "$$T\\hat{y}=AT\\hat{x}\\Longrightarrow \\hat{y}=T^{-1}AT\\hat{x}=\\Lambda \\hat{x}$$\n",
        "\n",
        "That is, in the eigenspace of $A$, the two vectors are connected via a diagonal matrix of the eigenvalues of $A$ and entries in $\\hat{x}$ can be independently determined from corresponding entries in $\\hat{y}$"
      ],
      "metadata": {
        "id": "rQfpa04ddpAC"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Diagonalization and left eigenvectors"
      ],
      "metadata": {
        "id": "Nv3neGCSqns0"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Rewrite\n",
        "\n",
        "$$T^{-1}AT=\\Lambda$$\n",
        "\n",
        "as\n",
        "\n",
        "$$T^{-1}A=\\Lambda T^{-1}$$\n",
        "\n",
        "or\n",
        "\n",
        "$$\\begin{bmatrix}w_1^T \\\\ \\vdots \\\\ w_n^T\\end{bmatrix}A=\\Lambda \\begin{bmatrix}w_1^T \\\\ \\vdots \\\\ w_n^T\\end{bmatrix}$$\n",
        "\n",
        "Thus\n",
        "\n",
        "$$w_i^TA=\\lambda_iw_i^T$$\n",
        "\n",
        "That is, `rows` of $T^{-1}$ are linearly independent `left eigenvectors`"
      ],
      "metadata": {
        "id": "BC3-NcjL5Y9p"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "As a result, `left and right eigenvectors` chosen this way are `dual basis` (after normalization)\n",
        "\n",
        "$$w_i^Tv_j = \\left\\{\\begin{array}{rcl}0 &i\\neq j \\\\1 &i=j \\end{array}\\right.$$"
      ],
      "metadata": {
        "id": "vstI7yCV6ekM"
      }
    }
  ]
}