{
"cells": [
{
"cell_type": "markdown",
"id": "81b1d2f0",
"metadata": {},
"source": [
"---\n",
"title: \"Linear Algebra\"\n",
"subtitle: \"\"\n",
"abstract: \"\"\n",
"date: 2026-02-19\n",
"format:\n",
" html:\n",
" other-links:\n",
" - text: This notebook\n",
" href: App2.ipynb\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "db6fe346",
"metadata": {},
"outputs": [],
"source": [
"#| echo: false\n",
"\n",
"using Plots, LaTeXStrings"
]
},
{
"cell_type": "markdown",
"id": "16b4a7e5",
"metadata": {},
"source": [
"* $(\\lambda, x)$ *eigenpair* of $A$ where $A x = \\lambda x$ and $x \\not= 0$. Here, $\\lambda$ is an *eigenvalue* and $x$ is an *eigenvector*, \n",
"* we say $x$ or $(\\lambda,x)$ is normalised if $|x| = 1$ (normally with respect to $|\\cdot| = |\\cdot|_2$), \n",
"* $\\sigma(A) := \\{ \\lambda : \\exists x \\not= 0 \\text{ s.t. } A x = \\lambda x \\}$: *spectrum* of $A$, \n",
"* $\\rho(A) := \\max_{\\lambda \\in \\sigma(A)} |\\lambda|$: *spectral radius* of $A$, \n",
"* $A^\\star$: conjugate transpose of $A$ given by $A^\\star_{ij} = \\overline{A_{ji}}$, \n",
"* $U$ is *unitary* if $U^\\star = U^{-1}$, \n",
"\n",
"::: {#def-normal}\n",
"\n",
"We say $A$ is *normal* if $A^\\star A = A A^\\star$ where $A^\\star$ is the conjugate transpose of $A$.\n",
"\n",
":::\n",
"\n",
"::: {#exr-normal}\n",
"\n",
"Show that real symmetric matrices are normal.\n",
"\n",
"::: \n",
"\n",
"::: {#thm-normal}\n",
"\n",
"$A$ is normal if and only if there exists a *unitary* matrix $U$ (i.e. $U^\\star = U^{-1}$) and a diagonal matrix $\\Lambda$ such that \n",
"\n",
"\\begin{align}\n",
" A = U \\Lambda U^\\star.\n",
"\\end{align}\n",
"\n",
"On defining $\\lambda_j := \\Lambda_{jj}$ and $u_j$ the $j^\\text{th}$ column of $U$, we have \n",
"\n",
"\\begin{align}\n",
" A = \\sum_{j=1}^n \\lambda_j u_j u_j^\\star\n",
"\\end{align}\n",
"\n",
"where $(\\lambda_j, u_j)$ are orthonormal eigenpairs of $A$.\n",
"\n",
":::\n",
"\n",
"\n",
"Proof. \n",
"\n",
"If $A = U \\Lambda U^\\star$, then \n",
"\n",
"\\begin{align}\n",
" A^\\star A &= (U \\Lambda U^\\star)^\\star U \\Lambda U^\\star \\nonumber\\\\\n",
" %\n",
" &= U \\Lambda^\\star (U^\\star U) \\Lambda U^\\star \\nonumber\\\\\n",
" %\n",
" &= U \\Lambda \\Lambda^\\star U^\\star \\nonumber\\\\\n",
" %\n",
" &= U \\Lambda U^\\star U \\Lambda^\\star U^\\star \\nonumber\\\\\n",
" %\n",
" &= (U \\Lambda U^\\star) (U \\Lambda U^\\star)^\\star\n",
" %\n",
" = AA^\\star .\n",
"\\end{align}\n",
"\n",
"Here, we have used the fact that $\\Lambda^\\star \\Lambda = \\Lambda\\Lambda^\\star$ because $\\Lambda$ is diagonal.\n",
"\n",
"To prove the other direction, we will assume Schur's decompostion: for a general matrix $A$ there exists a unitary matrix $U$ and upper triangular matrix $T$ such that \n",
"\n",
"\\begin{align}\n",
" A = U T U^\\star.\n",
"\\end{align}\n",
"\n",
"::: {.callout-note}\n",
"# Schur decomposition\n",
"\n",
"Schur decomposition is not too difficult to prove: there exists an eigenpair $(\\lambda_1,v_1)$ of $A$ which can be extended to an orthonormal basis $v_1,\\dots,v_n$. On defining $U = [v_1 | \\cdots | v_n]$, we have \n",
"\n",
"\\begin{align}\n",
" U^\\star A U = \\begin{pmatrix}\n",
" \\lambda_1 & x^T \\\\\n",
" 0 & B\n",
" \\end{pmatrix}\n",
"\\end{align}\n",
"\n",
"where $x^T$ is some row vector and $B$ is $(n-1)\\times (n-1)$. Writing the Schur decomposition of $B$ as matrix $B = V T V^\\star$, we have \n",
"\n",
"\\begin{align}\n",
" A &= U\\begin{pmatrix}\n",
" 1 & 0\\\\\n",
" 0 & V \n",
" \\end{pmatrix} \\begin{pmatrix}\n",
" \\lambda_1 & x^T \\\\\n",
" 0 & T \n",
" \\end{pmatrix} \n",
" \\begin{pmatrix}\n",
" 1 & 0\\\\\n",
" 0 & V^\\star\n",
" \\end{pmatrix}\n",
" U^\\star.\n",
"\\end{align}\n",
"\n",
"The result follows by showing that this is a Schur decomposition of $A$.\n",
"\n",
":::\n",
"\n",
"Since $A$ is normal, \n",
"\n",
"\\begin{align}\n",
" U T T^\\star U^\\star &= U T U^\\star (U T U^\\star)^\\star \\nonumber\\\\\n",
" %\n",
" &= AA^\\star = A^\\star A \\nonumber\\\\\n",
" %\n",
" &= (U T U^\\star)^\\star U T U^\\star \\nonumber\n",
" %\n",
" &= U T^\\star T U^\\star.\n",
"\\end{align}\n",
"\n",
"As a result, $T$ is normal (i.e. $TT^\\star = T^\\star T$). Since $T$ is upper triangular,\n",
"\n",
"\\begin{align}\n",
" \\sum_{k} |T_{1k}|^2 &= (TT^\\star)_{11} \\nonumber\\\\\n",
" %\n",
" &= (T^\\star T)_{11} = \\sum_k |T_{1k}|^2 \\nonumber\\\\\n",
" %\n",
" &= |T_{11}|^2\n",
"\\end{align}\n",
"\n",
"and so $T_{1k} = 0$ for all $k\\not=1$. By applying the exact same argument on the remaining $(n-1)\\times(n-1)$ submatrix, we find that $T$ is diagonal.\n",
"\n",
"Let $u$ be column $j$ of $U$. Then \n",
"\n",
"\\begin{align}\n",
" (A u)_i &= \\sum_{km} U_{ik} \\Lambda_{kk} U^\\star_{km} u_{m} \\nonumber\\\\\n",
" %\n",
" &= \\sum_{km} U_{ik} \\Lambda_{kk} U^\\star_{km} U_{mj} \\nonumber\\\\\n",
" %\n",
" &= U_{ij} \\Lambda_{jj} \n",
" %\n",
" = \\Lambda_{jj} u_i.\n",
"\\end{align}\n",
"\n",
"Finally, we have \n",
"\n",
"\\begin{align}\n",
" A_{ij} &= \\sum_{k} \\Lambda_{kk} U_{ik} U_{kj}^\\star\n",
" \\nonumber\\\\\n",
" %\n",
" &= \\sum_{k} \\Lambda_{kk} (u_k)_i \\overline{(u_k)_j}\n",
"\\end{align}\n",
"\n",
"where $u_k$ is the $k^\\text{th}$ column of $U$.\n",
"\n",
"
\n",
"\n",
"::: {#thm-rho}\n",
"\n",
"If $A$ is normal, then $\\rho(A) = \\|A\\|_2$. \n",
"\n",
":::\n",
"\n",
"\n",
"Proof. \n",
"\n",
"By the previous theorem, we can write \n",
"\n",
"\\begin{align}\n",
" A = U \\Lambda U^\\star = \\sum_j \\lambda_j u_j u_j^\\star\n",
"\\end{align}\n",
"\n",
"where $(\\lambda_j,u_j)$ are normalised eigenpairs of $A$. Moreover, since $U = [u_1|\\dots|u_n]$ is unitary, we have $u_{i}^\\star u_j = \\sum_k \\overline{(u_i)_k} (u_j)_k = \\delta_{ij}$. \n",
"\n",
"Write $x = \\alpha_1 u_1 + \\dots + \\alpha_n u_n$ where $|x|_2 = 1$. We have\n",
"\n",
"\\begin{align}\n",
" 1 &= |x|_2^2 \n",
" = \\sum_k \\overline{x_k} x_k \\nonumber\\\\\n",
" &= \\sum_k \\overline{(\\alpha_1 u_1 + \\cdots + \\alpha_n u_n)_k} (\\alpha_1 u_1 + \\cdots + \\alpha_n u_n)_k \\nonumber\\\\\n",
" %\n",
" &= |\\alpha_1|^2 + \\cdots + |\\alpha_n|^2\n",
"\\end{align}\n",
"\n",
"and \n",
"\n",
"\\begin{align}\n",
" | Ax |_2^2 \n",
" %\n",
" &= \\sum_k \\overline{(Ax)_k} (Ax)_k \\nonumber\\\\\n",
" %\n",
" &= |\\alpha_1 \\lambda_1|^2 + \\cdots + |\\alpha_n \\lambda_n|^2.\n",
"\\end{align}\n",
"\n",
"Suppose $|\\lambda_j| = \\max_i |\\lambda_i|$. Then, the maximum of $| Ax |_2^2$ is achieved when $\\alpha_j = 1$ and $\\alpha_i = 0$ for all $i \\not= j$.\n",
"\n",
"
\n",
"\n",
"::: {#lem-rho}\n",
"\n",
"$\\rho(A) \\leq \\|A\\|$ for every submultiplicative matrix norm.\n",
"\n",
":::\n",
"\n",
"\n",
"Proof. \n",
"\n",
"In [Lecture 8](L8.html) we proved this for any induced matrix norm. Here, we take any submultiplicative matrix norm $\\|\\cdot\\|$.\n",
"\n",
"Let $(\\lambda, x)$ be an eigenpair of $A$ and notice that $B := xx^T$ satisies \n",
"\n",
"\\begin{align}\n",
" AB = (Ax) x^T = (\\lambda x) x^T = \\lambda B . \n",
"\\end{align}\n",
"\n",
"As a result, since $\\|\\cdot\\|$ is submultiplicative, we have $|\\lambda| \\| B\\| = \\| A B \\| \\leq \\|A\\| \\|B\\|$. Dividing by $\\|B\\|$ gives $|\\lambda| \\leq \\|A\\|$.\n",
"\n",
"
\n",
"\n",
"::: {#thm-rho}\n",
"\n",
"For fixed $A$ and $\\epsilon > 0$, there exists a submultiplicative matrix norm $\\| \\cdot \\|_\\epsilon$ such that \n",
"\n",
"\\begin{align}\n",
" \\rho(A) \\leq \\| A \\|_{\\epsilon} \\leq \\rho(A) + \\epsilon.\n",
"\\end{align}\n",
"\n",
":::\n",
"\n",
"\n",
"Proof. \n",
"\n",
"We have already seen $\\rho(A) \\leq \\| A \\|_{\\epsilon}$ for all submultiplicative matrix norms $\\| \\cdot \\|_\\epsilon$. \n",
"\n",
"We use the Schur decomposition of $A$ to write $A = U TU^\\star$ with $U$ unitary and $T$ upper triangular and let \n",
"\n",
"\\begin{align}\n",
" D := \\begin{pmatrix}\n",
" \\delta & \\\\\n",
" & \\delta^2 \\\\\n",
" & & \\delta^3 \\\\\n",
" & & & \\ddots \\\\\n",
" & & & & \\delta^{n}\n",
" \\end{pmatrix}.\n",
"\\end{align}\n",
"\n",
"Then, $\\|B\\|' := \\| D^{-1} U^\\star B U D \\|_{\\infty}$ is a submultiplicative matrix norm with \n",
"\n",
"\\begin{align}\n",
" \\|A\\|' &= \\| D^{-1} U^\\star A U D \\|_{\\infty} \\nonumber\\\\\n",
" %\n",
" &= \\| D^{-1} T D \\|_{\\infty} \\nonumber\\\\\n",
" %\n",
" &= \\max_{i} \\sum_j | [D^{-1} T D]_{ij} | \\nonumber\\\\\n",
" %\n",
" &= \\max_i \\sum_j \\delta^{j-i} |T_{ij}| \\nonumber\\\\\n",
" %\n",
" &= \\max_i \\big[ |\\lambda_i| + \\sum_{j>i} \\delta^{j-i} |T_{ij}|\\big] .\n",
"\\end{align}\n",
"\n",
"Choosing $\\delta$ sufficiently small, we can make $\\sum_{j>i} \\delta^{j-i} |T_{ij}| \\leq \\epsilon$ and define $\\| \\cdot \\|_{\\epsilon} := \\|\\cdot\\|'$ for this choice of $\\delta$.\n",
" \n",
"
"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Julia 1.11",
"language": "julia",
"name": "julia-1.11"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "1.11.6"
}
},
"nbformat": 4,
"nbformat_minor": 5
}