worksheet-gen-eigen.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\newcommand{\\spn}{\\operatorname{span}}\n",
    "\\newcommand{\\bbm}{\\begin{bmatrix}}\n",
    "\\newcommand{\\ebm}{\\end{bmatrix}}\n",
    "\\newcommand{\\R}{\\mathbb{R}}\n",
    "\\renewcommand{\\C}{\\mathbb{C}}\n",
    "\\newcommand{\\im}{\\operatorname{im}}\n",
    "\\newcommand{\\nll}{\\operatorname{null}}\n",
    "\\newcommand{\\csp}{\\operatorname{col}}\n",
    "\\newcommand{\\rank}{\\operatorname{rank}}\n",
    "\\newcommand{\\diag}{\\operatorname{diag}}\n",
    "\\newcommand{\\tr}{\\operatorname{tr}}\n",
    "\\newcommand{\\dotp}{\\!\\boldsymbol{\\cdot}\\!}\n",
    "\\newcommand{\\len}[1]{\\lVert #1\\rVert}\n",
    "\\newcommand{\\abs}[1]{\\lvert #1\\rvert}\n",
    "\\newcommand{\\proj}[2]{\\operatorname{proj}_{#1}{#2}}\n",
    "\\newcommand{\\bz}{\\overline{z}}\n",
    "\\newcommand{\\zz}{\\mathbf{z}}\n",
    "\\newcommand{\\uu}{\\mathbf{u}}\n",
    "\\newcommand{\\vv}{\\mathbf{v}}\n",
    "\\newcommand{\\ww}{\\mathbf{w}}\n",
    "\\newcommand{\\xx}{\\mathbf{x}}\n",
    "\\newcommand{\\yy}{\\mathbf{y}}\n",
    "\\newcommand{\\zer}{\\mathbf{0}}\n",
    "\\newcommand{\\vecq}{\\mathbf{q}}\n",
    "\\newcommand{\\vecp}{\\mathbf{p}}\n",
    "\\newcommand{\\vece}{\\mathbf{e}}\n",
    "\\newcommand{\\basis}[2]{\\{\\mathbf{#1}_1,\\mathbf{#1}_2,\\ldots,\\mathbf{#1}_{#2}\\}}\n",
    "\\newcommand{\\gt}{>}\n",
    "\\newcommand{\\amp}{&}\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Worksheet: generalized eigenvectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $V$ be a finite-dimensional vector space, and let $T:V\\to V$ be a linear operator. Assume that $T$ has all real eigenvalues (alternatively, assume we're working over the complex numbers). Let $A$ be the matrix of $T$ with respect to some standard basis $B_0$ of $V\\text{.}$\n",
    "\n",
    "Our goal will be to replace the basis $B_0$ with a basis $B$ such that the matrix of $T$ with respect to $B$ is as simple as possible. (Where we agree that the \"simplest\" possible matrix would be diagonal.)\n",
    "\n",
    "Recall the following results that we've observed so far:\n",
    "- The characteristic polynomial $c_T(x)$ of $T$ does not depend on the choice of basis.\n",
    "- The eigenvalues of $T$ are the roots of this polynomial.\n",
    "- The eigenspaces $E_\\lambda(T)$ are $T$-invariant subspaces of $V\\text{.}$\n",
    "- The matrix $A$ can be diagonalized if and only if there is a basis of $V$ consisting of eigenvectors of $T\\text{.}$\n",
    "- Suppose\n",
    "$$\n",
    "c_T(x) = (x-\\lambda_1)^{m_1}(x-\\lambda_2)^{m_2}\\cdots (x-\\lambda_k)^{m_k}\\text{.}\n",
    "$$\n",
    "Then $A$ can be diagonalized if and only if $\\dim E_{\\lambda_i}(T) = m_i$ for each $i=1,\\ldots, k\\text{.}$\n",
    "\n",
    "In the case where $A$ can be diagonalized, we have the direct sum decomposition\n",
    "$$\n",
    "V = E_{\\lambda_1}(T)\\oplus E_{\\lambda_2}(T) \\oplus \\cdots \\oplus E_{\\lambda_k}(T)\\text{.}\n",
    "$$\n",
    "\n",
    "The question is: what do we do if there aren't enough eigenvectors to form a basis of $V\\text{?}$ When that happens, the direct sum of all the eigenspaces will not give us all of $V\\text{.}$\n",
    "\n",
    "The idea: replace $E_{\\lambda_j}(T)$ with a **generalized eigenspace** $G_{\\lambda_j}(T)$ whose dimension is $m_i\\text{.}$\n",
    "\n",
    "Our candidate: instead of $E_{\\lambda}(T) = \\ker(T-\\lambda I)\\text{,}$ we use $G_\\lambda(T) = \\ker((T-\\lambda I)^m)\\text{,}$ where $m$ is the multiplicity of $\\lambda\\text{.}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.\n",
    "Recall that in class we proved that $\\ker(T)$ and $\\operatorname{im}(T)$ are $T$-invariant subspaces. Let $p(x)$ be any polynomial, and prove that $\\ker (p(T))$ and $\\operatorname{im}(p(T))$ are also $T$-invariant.\n",
    "\n",
    "Hint: first show that $p(T)T=Tp(T)$ for any polynomial $T\\text{.}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Double-click here** to edit this cell and enter text to answer question 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Applying the result of Problem 1 to the polynomial $p(x) = (x-\\lambda)^m$ shows that $G_\\lambda(T)$ is $T$-invariant. It is possible to show that $\\dim G_\\lambda(T)=m$ but I won't ask you to do that. (A proof is in Nicholson if you really want to see it.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead, we will try to understand what's going on by exploring an example."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the following matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sympy import *\n",
    "init_printing()\n",
    "A=Matrix([[2,0,0,1,0],[-1,0,1,2,3],[0,1,2,0,-1],[-2,-3,2,5,3],[0,-1,0,1,4]])\n",
    "A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.\n",
    "Find (and factor) the characteristic polynomial of $A\\text{.}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.\n",
    "\n",
    "Find the eigenvectors. What are the dimensions of the eigenspaces? Based on this observation, can $A$ be diagonalized?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.\n",
    "\n",
    "Prove that for any $n\\times n$ matrix $A\\text{,}$ we have\n",
    "$$\n",
    "\\{0\\}\\subseteq \\operatorname{null}(A)\\subseteq \\operatorname{null}(A^2) \\subseteq \\cdots \\subseteq \\operatorname{null}(A^n)\\text{.}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Double-click here** to edit this cell and enter text to answer question 4."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It turns out that at some point, the null spaces stabilize. If $\\operatorname{null}(A^k)=\\operatorname{null}A^{k+1}$ for some $k\\text{,}$ then $\\operatorname{null}(A^k)=\\operatorname{null}(A^{k+l})$ for all $l\\geq 0\\text{.}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.\n",
    "\n",
    "For each eigenvalue found in problem 2, compute the nullspaces of $A-\\lambda I\\text{,}$ $(A-\\lambda I)^2\\text{,}$ $(A-\\lambda I)^3\\text{,}$ etc. until you find two consecutive nullspaces that are the same.\n",
    "\n",
    "By problem 4, any vector in $\\operatorname{null}(A-\\lambda I)^m$ will also be a vector in $\\operatorname{null}(A-\\lambda I)^{m+1}\\text{.}$ In particular, at each step, we can find a basis for $\\operatorname{null}(A-\\lambda I)^m$ that includes the basis for $\\operatorname{null}(A-\\lambda I)^{m-1}\\text{.}$\n",
    "\n",
    "For each eigenvalue found in problem 2, determine such a basis for the corresponding generalized eigenspace. You will want to list your vectors so that the vectors from the basis of the nullspace for $A-\\lambda I$ come first, then the vectors for the basis of the nullspace for $(A-\\lambda I)^2\\text{,}$ and so on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.\n",
    "Finally, let's see how all of this works. Let $P$ be the matrix whose columns consist of the vectors found in Problem 4. What do you get when you compute the matrix $P^{-1}AP\\text{?}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.6"
  },
  "name": "worksheet-gen-eigen.ipynb"
 },
 "nbformat": 4,
 "nbformat_minor": 1
}