{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "evd.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# eigenvalue decomposition (EVD) \u2014 Python demo\n\nNumerical companion to the entry [eigenvalue decomposition (EVD)](https://dictionaryofml.org/terms/evd.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nOne block per paragraph of the entry (marked [P...]): each block verifies numerically what the corresponding statement asserts. Self-contained (numpy/matplotlib only), fixed seed.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/evd.py`](https://dictionaryofml.org/terms/evd.py); CC BY 4.0."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# Notebook shim: the script resolves output paths relative to __file__,\n# which a notebook kernel does not define; everything lands in the\n# working directory instead.\nimport os\n__file__ = os.path.join(os.getcwd(), \"evd.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"\nevd.py \u2014 numerical companion to the glossary entry\n'eigenvalue decomposition (EVD)'.\n\nOne block per paragraph of the entry (marked [P...]): each block verifies\nnumerically what the corresponding statement asserts. Self-contained\n(numpy/matplotlib only), fixed seed.\n\nBlocks\n------\n[P-def]  The EVD A = V Lambda V^{-1}: reconstructing A from the factors\n         returned by np.linalg.eig gives A back with error below 1e-12;\n         the columns of V are eigenvectors and Lambda is diagonal with\n         the matching eigenvalues. The entry's 2x2 example matrix\n         [[1.3, 0.8], [0.4, 0.9]] has eigenvalues 1.7 and 0.5 with\n         eigenvectors along (2, 1) and (-1, 1), as drawn in Fig. 1.\n[P-diag] Matrices that admit an EVD are the diagonalizable ones: for the\n         defective matrix [[0, 1], [0, 0]] the eigenvector matrix is\n         singular (rank 1), so V^{-1} does not exist and no EVD is\n         possible, while the diagonalizable matrix A above passes.\n[P-fast] The EVD speeds up computations: for GD on a linear regression\n         training set, transforming with the orthogonal eigenvector\n         matrix of X^T X decouples the update into element-wise\n         operations; the decoupled recursion reproduces the plain GD\n         iterates exactly.\n[P-spec] Spectral clustering builds on the EVD of a graph Laplacian:\n         the Laplacian is symmetric and psd, so its EVD has an\n         orthogonal eigenvector matrix (V^{-1} = V^T) and real\n         nonnegative eigenvalues with lambda_1 = 0; the second-smallest\n         eigenvalue lambda_2 is positive iff the graph is connected,\n         and the signs of the entries of the corresponding eigenvector\n         (the Fiedler vector) split the two three-node clusters of the\n         entry's six-node example graph; the rounded entries match the\n         column vector displayed in the entry's Fig. 2.\n\nOutputs\n-------\nevd.png : preview figure (checking only).\n\nData generated by pythondemos/evd.py.\n\"\"\"\n\nimport numpy as np\nimport matplotlib\n\nmatplotlib.use(\"Agg\")\nimport matplotlib.pyplot as plt\nfrom matplotlib.patches import Patch\nfrom pathlib import Path\n\nOUT_DIR = Path(__file__).parent\n\nrng = np.random.default_rng(42)\nreport = []\n\n\ndef check(name, ok):\n    report.append((name, bool(ok)))\n    print(f\"  [{'ok' if ok else 'FAIL'}] {name}\")"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[P-def]** The EVD A = V Lambda V^{-1}: reconstructing A from the factors returned by np.linalg.eig gives A back with error below 1e-12; the columns of V are eigenvectors and Lambda is diagonal with the matching eigenvalues. The entry's 2x2 example matrix [[1.3, 0.8], [0.4, 0.9]] has eigenvalues 1.7 and 0.5 with eigenvectors along (2, 1) and (-1, 1), as drawn in Fig. 1."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[P-def] A = V Lambda V^{-1} reconstructs A\")\nA = np.array([[2.0, 1.0, 0.0], [1.0, 3.0, 0.5], [0.0, 0.5, 1.5]])\nlam, V = np.linalg.eig(A)\nLam = np.diag(lam)\nA_rec = V @ Lam @ np.linalg.inv(V)\ncheck(\"reconstruction error < 1e-12\",\n      np.max(np.abs(A_rec - A)) < 1e-12)\ncheck(\"columns of V are eigenvectors (A v = lambda v)\",\n      all(np.linalg.norm(A @ V[:, i] - lam[i] * V[:, i]) < 1e-12\n          for i in range(3)))\ncheck(\"Lambda is diagonal\", np.allclose(Lam, np.diag(np.diag(Lam))))\nA2 = np.array([[1.3, 0.8], [0.4, 0.9]])        # the entry's 2x2 example\nlam2 = np.sort(np.linalg.eigvals(A2))[::-1]\ncheck(\"the 2x2 example matrix has eigenvalues 1.7 and 0.5\",\n      np.allclose(lam2, [1.7, 0.5]))\ncheck(\"its eigenvectors lie along (2, 1) and (-1, 1)\",\n      np.linalg.norm(A2 @ [2, 1] - 1.7 * np.array([2, 1])) < 1e-12\n      and np.linalg.norm(A2 @ [-1, 1] - 0.5 * np.array([-1, 1])) < 1e-12)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[P-diag]** Matrices that admit an EVD are the diagonalizable ones: for the defective matrix [[0, 1], [0, 0]] the eigenvector matrix is singular (rank 1), so V^{-1} does not exist and no EVD is possible, while the diagonalizable matrix A above passes."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[P-diag] EVD exists iff the matrix is diagonalizable\")\nD = np.array([[0.0, 1.0], [0.0, 0.0]])         # defective (not diagonalizable)\nlamD, VD = np.linalg.eig(D)\nrank_VD = np.linalg.matrix_rank(VD)\ncheck(\"defective matrix: eigenvector matrix is singular (rank 1)\",\n      rank_VD == 1)\nsym = A                                         # symmetric example above\ncheck(\"diagonalizable matrix: eigenvector matrix invertible (rank 3)\",\n      np.linalg.matrix_rank(V) == 3)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[P-fast]** The EVD speeds up computations: for GD on a linear regression training set, transforming with the orthogonal eigenvector matrix of X^T X decouples the update into element-wise operations; the decoupled recursion reproduces the plain GD iterates exactly."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[P-fast] EVD of X^T X decouples the GD update for linear regression\")\nm_tr, d = 50, 4\nX = rng.normal(size=(m_tr, d))\nyv = rng.normal(size=m_tr)\nlamX, VX = np.linalg.eigh(X.T @ X)\neta = 0.02\nw = np.zeros(d)                                 # plain GD\nwt = VX.T @ w                                   # decoupled coordinates\nb = VX.T @ (X.T @ yv)\nfor _ in range(30):\n    w = w - (2 * eta / m_tr) * (X.T @ (X @ w - yv))\n    wt = (1 - (2 * eta / m_tr) * lamX) * wt + (2 * eta / m_tr) * b\ncheck(\"eigenvector matrix of the symmetric X^T X is orthogonal\",\n      np.max(np.abs(VX.T @ VX - np.eye(d))) < 1e-12)\ncheck(\"the element-wise recursion reproduces the GD iterates exactly\",\n      np.max(np.abs(VX @ wt - w)) < 1e-10)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[P-spec]** Spectral clustering builds on the EVD of a graph Laplacian: the Laplacian is symmetric and psd, so its EVD has an orthogonal eigenvector matrix (V^{-1} = V^T) and real nonnegative eigenvalues with lambda_1 = 0; the second-smallest eigenvalue lambda_2 is positive iff the graph is connected, and the signs of the entries of the corresponding eigenvector (the Fiedler vector) split the two three-node clusters of the entry's six-node example graph; the rounded entries match the column vector displayed in the entry's Fig. 2."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[P-spec] EVD of a graph Laplacian: spectral clustering\")\nn_nodes = 6\n# two clusters of three nodes each, joined by a single edge (2, 3)\nedge_list = [(0, 1), (1, 2), (0, 2), (3, 4), (4, 5), (3, 5), (2, 3)]\nL = np.zeros((n_nodes, n_nodes))\nfor i, j in edge_list:\n    L[i, j] -= 1.0\n    L[j, i] -= 1.0\n    L[i, i] += 1.0\n    L[j, j] += 1.0\nlamL, VL = np.linalg.eigh(L)\ncheck(\"Laplacian symmetric: eigenvector matrix orthogonal (V^T V = I)\",\n      np.max(np.abs(VL.T @ VL - np.eye(n_nodes))) < 1e-12)\ncheck(\"eigenvalues nonnegative with smallest lambda_1 = 0\",\n      lamL[0] > -1e-12 and abs(lamL[0]) < 1e-12)\ncheck(\"graph connected: second-smallest eigenvalue lambda_2 > 0\",\n      lamL[1] > 1e-8)\nfiedler = VL[:, 1]\nif fiedler[0] > 0:                              # the sign of an eigenvector\n    fiedler = -fiedler                          # is arbitrary; fix node 1 < 0\nside = fiedler > 0\ncheck(\"signs of the Fiedler vector recover the two clusters\",\n      len(set(side[:3])) == 1 and len(set(side[3:])) == 1\n      and side[0] != side[3])\ncheck(\"the entries match the column vector displayed in the entry's \"\n      \"Fig. 2 (rounded to two decimals)\",\n      np.allclose(np.round(fiedler, 2),\n                  [-0.46, -0.46, -0.26, 0.26, 0.46, 0.46]))\n\n# ------------------------------------------------------------ preview\nfig, ax = plt.subplots(1, 4, figsize=(12, 2.8))\nfor a, M, t in ((ax[0], A, \"A\"), (ax[1], Lam.real, \"Lambda\"),\n                (ax[2], (A_rec - A).real, \"V Lambda V^{-1} - A\")):\n    im = a.imshow(M, cmap=\"gray\"); a.set_title(t)\n    fig.colorbar(im, ax=a, shrink=0.75)\nnodes = np.arange(1, n_nodes + 1)\nbars = ax[3].bar(nodes, fiedler, color=np.where(side, \"C0\", \"C1\"))\nfor b, s in zip(bars, side):\n    if s:\n        b.set_hatch(\"//\")\nlegend_handles = [Patch(facecolor=\"C0\", hatch=\"//\", label=\"cluster 1\"),\n                  Patch(facecolor=\"C1\", label=\"cluster 2\")]\nax[3].set_xlim(0.4, n_nodes + 0.6)\nax[3].axhline(0.0, color=\"k\", lw=0.8)\nax[3].set_xlabel(\"node $i$\")\nax[3].set_ylabel(\"$v^{(2)}_i$\")\nax[3].set_title(\"[P-spec] Fiedler vector\")\nax[3].legend(handles=legend_handles, frameon=False)\nfig.suptitle(\"EVD factors, reconstruction error, and spectral clustering\")\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"evd.png\", dpi=110)\nprint(f\"\\n{sum(ok for _, ok in report)}/{len(report)} checks passed\")\nassert all(ok for _, ok in report)"
  }
 ]
}