la_26_symmetric_matrix.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    },
    "gpuClass": "standard"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "#### Eigendecomposition of symmetric matrices"
      ],
      "metadata": {
        "id": "CfWMiHIGCqu8"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##### Symmetric matrix has `real` eigenvalues"
      ],
      "metadata": {
        "id": "-eOmGSZ-EkiO"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Assume for a symmetric matrix $A$, it has an eigenvector $v \\in C^n, v\\neq 0$\n",
        "\n",
        "Then, we have\n",
        "\n",
        "$$\\bar{v}^TAv=\\bar{v}^T(Av)=\\lambda \\bar{v}^Tv$$\n",
        "\n",
        "and (use `conjugate symmetry`)\n",
        "\n",
        "$$\\bar{v}^TAv=\\bar{v}^TA^Tv=(\\bar{A}\\bar{v})^Tv=\\bar{\\lambda}\\bar{v}^Tv$$\n",
        "\n",
        "Therefore, $\\lambda = \\bar{\\lambda}$, so the eigenvalue $\\lambda$ is real"
      ],
      "metadata": {
        "id": "-G6ZbElQEwzm"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##### Symmetric matrix has orthogonal eigenvectors"
      ],
      "metadata": {
        "id": "szBiWanTHPar"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "With symmetric matrix $A$ having real eigenvalues, assume we have two distinct real eigenvalues $\\lambda_i\\neq\\lambda_j$ and their corresponding eigenvectors $v_i$ and $v_j$, we have the following\n",
        "\n",
        "$$\\begin{align*}\n",
        "\\lambda_i ( v_i^T v_j)&= (\\lambda_i v_i)^T v_j\\\\\n",
        "&=(Av_i)^T  v_j\\\\\n",
        "&=(v_i^TA^T) v_j\\\\\n",
        "&=v_i^T (Av_j)\\\\\n",
        "&=v_i^T(\\lambda_jv_j)\\\\\n",
        "&=\\boxed{\\lambda_j( v_i^T v_j)}\n",
        "\\end{align*}$$\n",
        "\n",
        "We move the highlighted part to the left hand side\n",
        "\n",
        "$$(\\lambda_i-\\lambda_j)( v_i^T v_j)=0$$\n",
        "\n",
        "As $\\lambda_i\\neq\\lambda_j$, then\n",
        "\n",
        "$$v_i^T v_j=0$$\n",
        "\n",
        "As a result, eigenvectors $v_i$ and $v_j$ are `orthogonal`"
      ],
      "metadata": {
        "id": "nf8SfKYaIO9b"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Equivalence between transpose and inverse"
      ],
      "metadata": {
        "id": "1EWGrhwyLLky"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "For any eigenvector and eigenvalue pair\n",
        "\n",
        "$$Av=\\lambda v$$\n",
        "\n",
        "we can normalize the eigenvector without affecting the equation\n",
        "\n",
        "We denote the normalized eigenvector $v_i$ as $q_i$\n",
        "\n",
        "Then, from orthogonality among eigenvectors, we have\n",
        "\n",
        "$$q_i^Tq_j = \\left\\{\\begin{array}{rcl}0 &i\\neq j \\\\1 &i=j \\end{array}\\right.$$\n"
      ],
      "metadata": {
        "id": "GjfV_Iw8Lb13"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "We write out all eigenvectors and represent the above two properties using matrix notation\n",
        "\n",
        "$$Q^TQ=\\begin{bmatrix}--- & q_1^T &---\\\\--- & q_2^T &---\\\\\\vdots & \\vdots &\\vdots\\\\--- & q_n^T &---\\end{bmatrix}\\begin{bmatrix}| & | &| & |\\\\q_1 & q_2 & \\cdots & q_n\\\\| & | &| & |\\end{bmatrix}=I$$\n",
        "\n",
        "Since\n",
        "\n",
        "$$Q^{-1}Q=I$$\n",
        "\n",
        "we have\n",
        "\n",
        "$$Q^T=Q^{-1}$$"
      ],
      "metadata": {
        "id": "m5kPObnTMdSm"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "As columns of $Q$ are eigenvectors of $A$, we know that rows of $Q^{-1}=Q^T$ are left eigenvectors of $A$\n",
        "\n",
        "Since the rows of $Q^T$ are just $q_i$'s, we see that $q_i$ are `both left and right eigenvectors` of $A$"
      ],
      "metadata": {
        "id": "d8lMVDc_AYLi"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Multiplication between symmetry matrix and vector"
      ],
      "metadata": {
        "id": "i9hlr2-aGXt4"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "We can expand $A$ as\n",
        "\n",
        "$$\\boxed{A=Q\\Lambda Q^{-1}=Q\\Lambda Q^T=\\sum_{i=1}^n\\lambda_i q_i q_i^T}$$\n",
        "\n",
        "and we see that when $A$ is acting on a vector $x$, it\n",
        "\n",
        "* `resolves` $x$ into $q_i$ direction with coefficient $(q_i^Tx)$\n",
        "* `scales` coefficient by $\\lambda_i$  $$\\lambda_i(q_i^Tx)$$\n",
        "* `reconstructs` using scaled coefficient with basis $q_i$\n",
        "$$\\sum_{i=1}^n\\lambda_iq_i(q_i^Tx)$$"
      ],
      "metadata": {
        "id": "E353W6TIXH4z"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "e5DJ2byib5Cg"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}