Dictionary of Applied Machine Learning · eigenvalue decomposition (EVD)
Updated on 2026-11-03
Numerical companion to the entry eigenvalue decomposition (EVD): it recomputes what the entry states and prints one line per check
One block per paragraph of the entry (marked [P...]): each block verifies numerically what the corresponding statement asserts. Self-contained (numpy/matplotlib only, stdlib urllib for the download), fixed seed.
Run it without installing anything:uv run https://dictionaryofml.org/terms/evd.py
uv downloads this script and the pinned NumPy and Matplotlib it needs, then runs it; the script fetches any input file it uses. To keep the output files, download evd.py into a folder and run uv run evd.py there. With NumPy and Matplotlib already installed, python3 evd.py, from any directory — it writes its output files into the current directory. Fixed seeds, so the printed numbers reproduce exactly. Download evd.py · Notebook · Open in Colab
Before running a downloaded copy, scan it: uvx bandit -q -t B102,B307,B602,B605 evd.py (B102,B307,B602,B605 are the exec, eval and shell checks of bandit) reports nothing: the script runs no shell command and evaluates no generated code.
One cell per block of the script: the code, and what that code printed when it last ran here
"""
evd.py — numerical companion to the glossary entry
'eigenvalue decomposition (EVD)'.
One block per paragraph of the entry (marked [P...]): each block verifies
numerically what the corresponding statement asserts. Self-contained
(numpy/matplotlib only, stdlib urllib for the download), fixed seed.
Blocks
------
[P-krems] The days of 2024 at the GeoSphere Austria weather station Krems
an der Donau (station id 3805), each with its lowest and its
highest temperature in degrees Celsius: the records are
downloaded from the GeoSphere data hub (dataset klima-v2-1d)
and written to evd_weather.csv. The sample covariance matrix of
the two temperatures is symmetric, so its eigenvector matrix is
orthogonal and the EVD reads C = V Lambda V^T, with eigenvalues
130.9 and 7.9 squared degrees. The ellipse of Fig. 1, the set of
points whose quadratic form (x - mu)^T C^{-1} (x - mu) equals 4,
has its two main axes along the eigenvectors and half-lengths
2 sqrt(lambda_j), two standard deviations; the block writes the
scatterplot, the ellipse and the two axes as CSV files and
counts the days the ellipse encloses.
[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. 2.
[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.
[P-ellipse] Why the ellipse has those axes: in the coordinates
z = V^T (x - mu) the quadratic form becomes
z_1^2 / lambda_1 + z_2^2 / lambda_2, the equation of an
axis-aligned ellipse, and the sample covariance matrix of the
transformed days is the diagonal matrix Lambda, so the sample
covariance of the two new coordinates is zero and the
eigenvalues are their sample variances.
[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.
[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. 3.
Outputs
-------
evd_weather.csv : date, lowest and highest temperature of each day of 2024
evd_points.csv : the 366 days as points (x1 = lowest, x2 = highest, deg C)
evd_points_plot.csv : every 19th of those days, the 20 drawn in Fig. 1
evd_ellipse.csv : the two-standard-deviation ellipse, 181 points
evd_axis1.csv, evd_axis2.csv : the two main axes, from the sample mean
to the ellipse along each eigenvector
evd.png : preview figure (checking only).
Data generated by pythondemos/evd.py.
"""
# /// script
# requires-python = ">=3.10"
# dependencies = ["matplotlib==3.10.7", "numpy==2.3.4"]
# ///
import json
import urllib.request
import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
from matplotlib.patches import Patch
from pathlib import Path
OUT_DIR = Path(__file__).parent
rng = np.random.default_rng(42)
report = []
def check(name, ok):
report.append((name, bool(ok)))
print(f" [{'ok' if ok else 'FAIL'}] {name}")
The days of 2024 at the GeoSphere Austria weather station Krems an der Donau (station id 3805), each with its lowest and its highest temperature in degrees Celsius: the records are downloaded from the GeoSphere data hub (dataset klima-v2-1d) and written to evd_weather.csv. The sample covariance matrix of the two temperatures is symmetric, so its eigenvector matrix is orthogonal and the EVD reads C = V Lambda V^T, with eigenvalues 130.9 and 7.9 squared degrees. The ellipse of Fig. 1, the set of points whose quadratic form (x - mu)^T C^{-1} (x - mu) equals 4, has its two main axes along the eigenvectors and half-lengths 2 sqrt(lambda_j), two standard deviations; the block writes the scatterplot, the ellipse and the two axes as CSV files and counts the days the ellipse encloses.
print("[P-krems] the ellipse fitted to the days at Krems")
PARAMS = ["tlmin", "tlmax"]
URL = ("https://dataset.api.hub.geosphere.at/v1/station/historical/"
f"klima-v2-1d?parameters={','.join(PARAMS)}&station_ids=3805"
"&start=2024-01-01&end=2024-12-31")
weather_csv = OUT_DIR / "evd_weather.csv"
try:
with urllib.request.urlopen(URL, timeout=120) as resp:
payload = json.load(resp)
params = payload["features"][0]["properties"]["parameters"]
stamps = [t[:10] for t in payload["timestamps"]]
X = np.stack([np.array(params[p]["data"], dtype=float) for p in PARAMS], 1)
with open(weather_csv, "w") as f:
f.write("date," + ",".join(PARAMS) + "\n")
for day, row in zip(stamps, X):
f.write(day + "," + ",".join(f"{v:g}" for v in row) + "\n")
except (OSError, KeyError, ValueError) as err: # offline: committed copy
print(f" download failed ({err}); reading {weather_csv.name}")
rows = np.genfromtxt(weather_csv, delimiter=",", skip_header=1, dtype=str)
stamps = [str(s) for s in rows[:, 0]]
X = rows[:, 1:].astype(float)
m = len(X)
check("366 days, each with its lowest and its highest temperature",
X.shape == (366, 2))
check("the record matches the archive (Feb 1: -3.8 to 10.4 deg)",
stamps[31] == "2024-02-01" and np.allclose(X[31], [-3.8, 10.4]))
mu = X.mean(axis=0) # sample mean
C = (X - mu).T @ (X - mu) / m # sample covariance matrix
lamC, VC = np.linalg.eigh(C)
order = np.argsort(lamC)[::-1]
lamC, VC = lamC[order], VC[:, order]
for j in (0, 1): # the sign of an eigenvector
if VC[0, j] < 0: # is arbitrary; fix x1 > 0
VC[:, j] = -VC[:, j]
check("the sample covariance matrix is symmetric", np.allclose(C, C.T))
check("its eigenvector matrix is orthogonal (V^T V = I)",
np.max(np.abs(VC.T @ VC - np.eye(2))) < 1e-12)
check("C = V Lambda V^T reconstructs C",
np.max(np.abs(VC @ np.diag(lamC) @ VC.T - C)) < 1e-10)
check("the eigenvalues are 130.9 and 7.9 squared degrees",
np.allclose(np.round(lamC, 1), [130.9, 7.9]))
print(f" sample mean ({mu[0]:.1f}, {mu[1]:.1f}) deg; standard deviations "
f"along the eigenvectors {np.sqrt(lamC[0]):.1f} and "
f"{np.sqrt(lamC[1]):.1f} deg; v1 = ({VC[0, 0]:.2f}, {VC[1, 0]:.2f}), "
f"v2 = ({VC[0, 1]:.2f}, {VC[1, 1]:.2f})")
LEVEL = 4.0 # (2 standard deviations)^2
theta = np.linspace(0.0, 2.0 * np.pi, 181)
E = mu + (np.sqrt(LEVEL * lamC[0]) * np.cos(theta)[:, None] * VC[:, 0]
+ np.sqrt(LEVEL * lamC[1]) * np.sin(theta)[:, None] * VC[:, 1])
Cinv = np.linalg.inv(C)
qform = lambda P: np.einsum("ij,jk,ik->i", P - mu, Cinv, P - mu)
check("every point of the ellipse has (x - mu)^T C^{-1} (x - mu) = 4",
np.allclose(qform(E), LEVEL))
tips = [mu + np.sqrt(LEVEL * lamC[j]) * VC[:, j] for j in (0, 1)]
check("the axis tips lie on the ellipse and the half-axes are 2 sqrt(lambda_j)",
np.allclose(qform(np.array(tips)), LEVEL)
and all(np.isclose(np.linalg.norm(tips[j] - mu),
2.0 * np.sqrt(lamC[j])) for j in (0, 1)))
inside = int(np.sum(qform(X) <= LEVEL))
print(f" the ellipse encloses {inside} of the {m} days")
check("the ellipse encloses 328 of the 366 days", inside == 328)
np.savetxt(OUT_DIR / "evd_points.csv", X, delimiter=",", header="x1,x2",
comments="", fmt="%.1f")
# the book figure draws every 19th day, 20 of the 366, so the dots do not
# crowd the ellipse; the ellipse and the arrows come from all 366 days
X_plot = X[::19]
check("every 19th day gives 20 days for the scatterplot", X_plot.shape[0] == 20)
np.savetxt(OUT_DIR / "evd_points_plot.csv", X_plot, delimiter=",",
header="x1,x2", comments="", fmt="%.1f")
np.savetxt(OUT_DIR / "evd_ellipse.csv", E, delimiter=",", header="x1,x2",
comments="", fmt="%.3f")
for j in (0, 1):
with open(OUT_DIR / f"evd_axis{j + 1}.csv", "w") as f:
f.write("x1,x2\n" + f"{mu[0]:.3f},{mu[1]:.3f}\n"
+ f"{tips[j][0]:.3f},{tips[j][1]:.3f}\n")
[P-krems] the ellipse fitted to the days at Krems
[ok] 366 days, each with its lowest and its highest temperature
[ok] the record matches the archive (Feb 1: -3.8 to 10.4 deg)
[ok] the sample covariance matrix is symmetric
[ok] its eigenvector matrix is orthogonal (V^T V = I)
[ok] C = V Lambda V^T reconstructs C
[ok] the eigenvalues are 130.9 and 7.9 squared degrees
sample mean (7.2, 17.9) deg; standard deviations along the eigenvectors 11.4 and 2.8 deg; v1 = (0.61, 0.79), v2 = (0.79, -0.61)
[ok] every point of the ellipse has (x - mu)^T C^{-1} (x - mu) = 4
[ok] the axis tips lie on the ellipse and the half-axes are 2 sqrt(lambda_j)
the ellipse encloses 328 of the 366 days
[ok] the ellipse encloses 328 of the 366 days
[ok] every 19th day gives 20 days for the scatterplot
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. 2.
print("[P-def] A = V Lambda V^{-1} reconstructs A")
A = np.array([[2.0, 1.0, 0.0], [1.0, 3.0, 0.5], [0.0, 0.5, 1.5]])
lam, V = np.linalg.eig(A)
Lam = np.diag(lam)
A_rec = V @ Lam @ np.linalg.inv(V)
check("reconstruction error < 1e-12",
np.max(np.abs(A_rec - A)) < 1e-12)
check("columns of V are eigenvectors (A v = lambda v)",
all(np.linalg.norm(A @ V[:, i] - lam[i] * V[:, i]) < 1e-12
for i in range(3)))
check("Lambda is diagonal", np.allclose(Lam, np.diag(np.diag(Lam))))
A2 = np.array([[1.3, 0.8], [0.4, 0.9]]) # the entry's 2x2 example
lam2 = np.sort(np.linalg.eigvals(A2))[::-1]
check("the 2x2 example matrix has eigenvalues 1.7 and 0.5",
np.allclose(lam2, [1.7, 0.5]))
check("its eigenvectors lie along (2, 1) and (-1, 1)",
np.linalg.norm(A2 @ [2, 1] - 1.7 * np.array([2, 1])) < 1e-12
and np.linalg.norm(A2 @ [-1, 1] - 0.5 * np.array([-1, 1])) < 1e-12)
[P-def] A = V Lambda V^{-1} reconstructs A
[ok] reconstruction error < 1e-12
[ok] columns of V are eigenvectors (A v = lambda v)
[ok] Lambda is diagonal
[ok] the 2x2 example matrix has eigenvalues 1.7 and 0.5
[ok] its eigenvectors lie along (2, 1) and (-1, 1)
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.
print("[P-diag] EVD exists iff the matrix is diagonalizable")
D = np.array([[0.0, 1.0], [0.0, 0.0]]) # defective (not diagonalizable)
lamD, VD = np.linalg.eig(D)
rank_VD = np.linalg.matrix_rank(VD)
check("defective matrix: eigenvector matrix is singular (rank 1)",
rank_VD == 1)
sym = A # symmetric example above
check("diagonalizable matrix: eigenvector matrix invertible (rank 3)",
np.linalg.matrix_rank(V) == 3)
[P-diag] EVD exists iff the matrix is diagonalizable [ok] defective matrix: eigenvector matrix is singular (rank 1) [ok] diagonalizable matrix: eigenvector matrix invertible (rank 3)
Why the ellipse has those axes: in the coordinates z = V^T (x - mu) the quadratic form becomes z_1^2 / lambda_1 + z_2^2 / lambda_2, the equation of an axis-aligned ellipse, and the sample covariance matrix of the transformed days is the diagonal matrix Lambda, so the sample covariance of the two new coordinates is zero and the eigenvalues are their sample variances.
print("[P-ellipse] the eigenvector coordinates make the ellipse axis-aligned")
Z = (X - mu) @ VC # z = V^T (x - mu), per day
ZE = (E - mu) @ VC # the ellipse in z coordinates
check("in z coordinates the ellipse satisfies z1^2/lambda_1 + z2^2/lambda_2 = 4",
np.allclose(ZE[:, 0] ** 2 / lamC[0] + ZE[:, 1] ** 2 / lamC[1], LEVEL))
CZ = Z.T @ Z / m # sample covariance of z
check("the sample covariance matrix of the transformed days is Lambda",
np.allclose(CZ, np.diag(lamC)))
check("the sample covariance of the two new coordinates is zero",
abs(CZ[0, 1]) < 1e-10)
check("the eigenvalues are the sample variances of the new coordinates",
np.allclose(Z.var(axis=0), lamC))
[P-ellipse] the eigenvector coordinates make the ellipse axis-aligned [ok] in z coordinates the ellipse satisfies z1^2/lambda_1 + z2^2/lambda_2 = 4 [ok] the sample covariance matrix of the transformed days is Lambda [ok] the sample covariance of the two new coordinates is zero [ok] the eigenvalues are the sample variances of the new coordinates
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.
print("[P-fast] EVD of X^T X decouples the GD update for linear regression")
m_tr, d = 50, 4
Xtr = rng.normal(size=(m_tr, d))
yv = rng.normal(size=m_tr)
lamX, VX = np.linalg.eigh(Xtr.T @ Xtr)
eta = 0.02
w = np.zeros(d) # plain GD
wt = VX.T @ w # decoupled coordinates
b = VX.T @ (Xtr.T @ yv)
for _ in range(30):
w = w - (2 * eta / m_tr) * (Xtr.T @ (Xtr @ w - yv))
wt = (1 - (2 * eta / m_tr) * lamX) * wt + (2 * eta / m_tr) * b
check("eigenvector matrix of the symmetric X^T X is orthogonal",
np.max(np.abs(VX.T @ VX - np.eye(d))) < 1e-12)
check("the element-wise recursion reproduces the GD iterates exactly",
np.max(np.abs(VX @ wt - w)) < 1e-10)
[P-fast] EVD of X^T X decouples the GD update for linear regression [ok] eigenvector matrix of the symmetric X^T X is orthogonal [ok] the element-wise recursion reproduces the GD iterates exactly
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. 3.
print("[P-spec] EVD of a graph Laplacian: spectral clustering")
n_nodes = 6
# two clusters of three nodes each, joined by a single edge (2, 3)
edge_list = [(0, 1), (1, 2), (0, 2), (3, 4), (4, 5), (3, 5), (2, 3)]
L = np.zeros((n_nodes, n_nodes))
for i, j in edge_list:
L[i, j] -= 1.0
L[j, i] -= 1.0
L[i, i] += 1.0
L[j, j] += 1.0
lamL, VL = np.linalg.eigh(L)
check("Laplacian symmetric: eigenvector matrix orthogonal (V^T V = I)",
np.max(np.abs(VL.T @ VL - np.eye(n_nodes))) < 1e-12)
check("eigenvalues nonnegative with smallest lambda_1 = 0",
lamL[0] > -1e-12 and abs(lamL[0]) < 1e-12)
check(f"graph connected: second-smallest eigenvalue lambda_2 = {lamL[1]:.2f} > 0, well below "
f"the next eigenvalue lambda_3 = {lamL[2]:.0f} (the single edge between the clusters)",
lamL[1] > 1e-8 and lamL[1] < 0.2 * lamL[2])
fiedler = VL[:, 1]
if fiedler[0] > 0: # the sign of an eigenvector
fiedler = -fiedler # is arbitrary; fix node 1 < 0
side = fiedler > 0
check("signs of the Fiedler vector recover the two clusters",
len(set(side[:3])) == 1 and len(set(side[3:])) == 1
and side[0] != side[3])
check("the entries match the column vector displayed in the entry's "
"Fig. 3 (rounded to two decimals)",
np.allclose(np.round(fiedler, 2),
[-0.46, -0.46, -0.26, 0.26, 0.46, 0.46]))
# ------------------------------------------------------------ preview
fig, ax = plt.subplots(1, 5, figsize=(17, 3.6),
gridspec_kw=dict(width_ratios=[1.8, 1, 1, 1, 1.3]))
ax[0].plot(X[:, 0], X[:, 1], ".", color="gray", ms=3, label="days of 2024")
ax[0].plot(E[:, 0], E[:, 1], "k-", lw=1.2, label="2 s.d. ellipse")
for j, (ls, lab) in enumerate((("-", "$v^{(1)}$"), ("--", "$v^{(2)}$"))):
ax[0].annotate("", xy=tips[j], xytext=mu,
arrowprops=dict(arrowstyle="->", color="k", lw=1.6, ls=ls))
ax[0].text(*tips[j], " " + lab, fontsize=8, va="center")
ax[0].set_aspect("equal")
ax[0].set_xlabel("lowest temperature of the day (deg C)")
ax[0].set_ylabel("highest temperature (deg C)")
ax[0].set_title("[P-krems] Krems 2024: ellipse axes = eigenvectors")
ax[0].legend(frameon=False, fontsize=7, loc="upper left")
for a, M, t in ((ax[1], A, "A"), (ax[2], Lam.real, "Lambda"),
(ax[3], (A_rec - A).real, "V Lambda V^{-1} - A")):
im = a.imshow(M, cmap="gray"); a.set_title(t)
a.set_xlabel("column"); a.set_ylabel("row")
fig.colorbar(im, ax=a, shrink=0.75)
nodes = np.arange(1, n_nodes + 1)
bars = ax[4].bar(nodes, fiedler, color=np.where(side, "C0", "C1"))
for bar, s in zip(bars, side):
if s:
bar.set_hatch("//")
legend_handles = [Patch(facecolor="C0", hatch="//", label="cluster 1"),
Patch(facecolor="C1", label="cluster 2")]
ax[4].set_xlim(0.4, n_nodes + 0.6)
ax[4].axhline(0.0, color="k", lw=0.8)
ax[4].set_xlabel("node $i$")
ax[4].set_ylabel("$v^{(2)}_i$")
ax[4].set_title("[P-spec] Fiedler vector")
ax[4].legend(handles=legend_handles, frameon=False)
fig.suptitle("EVD: the Krems ellipse, factors, reconstruction error, and spectral clustering")
fig.tight_layout()
fig.savefig(OUT_DIR / "evd.png", dpi=110)
print(f"\n{sum(ok for _, ok in report)}/{len(report)} checks passed")
assert all(ok for _, ok in report)
[P-spec] EVD of a graph Laplacian: spectral clustering [ok] Laplacian symmetric: eigenvector matrix orthogonal (V^T V = I) [ok] eigenvalues nonnegative with smallest lambda_1 = 0 [ok] graph connected: second-smallest eigenvalue lambda_2 = 0.44 > 0, well below the next eigenvalue lambda_3 = 3 (the single edge between the clusters) [ok] signs of the Fiedler vector recover the two clusters [ok] the entries match the column vector displayed in the entry's Fig. 3 (rounded to two decimals) 28/28 checks passed

P-spec writes when the script runs