evd.py, which recomputes what the entry states: the script block by block · open in ColabDictionary of Applied Machine Learning: 115 machine-learning terms, each with a definition, a figure, citations and a Python demo · All terms · Demos · Start here
Updated on 2026-11-10
Readiness 100/100
See also matrix eigenvalue gradient descent linear regression principal component analysis singular value decomposition
An eigenvalue decomposition (EVD) of a square matrix breaks the linear map it represents into elementary operations: expanding a vector in the eigenvectors of the matrix, multiplying each expansion coefficient by the corresponding eigenvalue, and summing the scaled terms up again. A matrix that has an EVD is called diagonalizable; symmetric matrices and matrices with distinct eigenvalues are diagonalizable. A dataset with numeric feature vectors can be characterized by the EVD of its sample covariance matrix. The EVD can be used to speed up computations such as the gradient step of gradient descent (GD) methods. For linear regression, each GD iteration then reduces to element-wise operations. The EVD of the Laplacian matrix of an undirected graph is used by spectral clustering.
evd.py, which recomputes what the entry states: the script block by block · open in ColabP-kremsEach day of 2024 at
the weather station Krems an der Donau (Austria) is a
data point recorded with two features, its lowest and
its highest temperature, stacked into a feature vector
${\mathbf x} = \big( x_{1}, x_{2} \big)^{\top} \in \mathbb{R}^{2}$.
Fig. 1 shows $20$ of the $m = 366$
days ${\mathbf x}^{(1)}, \ldots, {\mathbf x}^{(m)}$ as a
scatterplot together with an ellipse that is computed from
their sample mean and sample covariance matrix. The sample mean
of the days is
\[
\widehat{\boldsymbol \mu} = \frac{1}{m}
\sum_{r=1}^{m} {\mathbf x}^{(r)} \text{,}
\]
and their sample covariance matrix is
\[
\widehat{{\mathbf C}} = \frac{1}{m}
\sum_{r=1}^{m}
\big( {\mathbf x}^{(r)} - \widehat{\boldsymbol \mu} \big)
\big( {\mathbf x}^{(r)} - \widehat{\boldsymbol \mu} \big)^{\top}
\in \mathbb{R}^{2 \times 2} \text{.}
\]
The shape of the ellipse, which outlines the dataset, is
determined by an EVD of the sample covariance matrix $\widehat{{\mathbf C}}$,
whose eigenvectors are the axes of the ellipse.
pythondemos/evd.py
The EVD breaks the linear map ${\mathbf u} \mapsto {\mathbf A} {\mathbf u}$ into three elementary operations. A vector ${\mathbf u}$ is expanded in the eigenvectors, ${\mathbf u} = \sum_{j=1}^{d} \beta_{j} {\mathbf v}^{(j)}$ with the expansion coefficients $\boldsymbol{\beta} = \mathbf{V}^{-1} {\mathbf u}$; each coefficient is multiplied by its eigenvalue; and the scaled terms are summed up again, ${\mathbf A} {\mathbf u} = \sum_{j=1}^{d} \lambda_{j} \beta_{j} {\mathbf v}^{(j)}$.
Unlike the singular value decomposition (SVD), which exists for every matrix, square or not (Horn and Johnson, 2013, Thm. 2.6.3), the EVD is defined for square matrices only, and it need not exist. Moreover, the same matrix might allow for different EVDs: any nonzero linear combination of eigenvectors with the same eigenvalue is again an eigenvector with this eigenvalue. The geometric multiplicity of an eigenvalue is the maximum number of linearly independent eigenvectors with this eigenvalue (Horn and Johnson, 2013, Sect. 1.4).
P-defMatrices that allow for an EVD are called diagonalizable.
One example of a diagonalizable matrix is
\[
{\mathbf A} = \begin{pmatrix} 1.3 & 0.8 \\ 0.4 & 0.9 \end{pmatrix}
\text{.}
\]
Fig. 2 illustrates its EVD.
The matrix ${\mathbf A}$ of Fig. 2 is not symmetric, since its off-diagonal entries $0.8$ and $0.4$ differ, but its two eigenvalues $1.7$ and $0.5$ are distinct, so it has an EVD. When neither condition holds, an EVD may not exist: the matrix \[ {\mathbf N} = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} \] is not symmetric and has the eigenvalue $0$ twice, since the eigenvalues of a triangular matrix are its diagonal entries (Horn and Johnson, 2013, Sect. 1.2, exercise on upper triangular matrices after Def. 1.2.9). The eigenvectors of ${\mathbf N}$ are all located on the line $\big\{ (a, 0)^{\top} : a \in \mathbb{R} \big\}$, so there is no invertible matrix $\mathbf{V}$ whose columns are eigenvectors of ${\mathbf N}$.
P-ellipseThe ellipse in Fig. 1 is the set of feature vectors ${\mathbf x}$ for which the quadratic form $({\mathbf x} - \widehat{\boldsymbol \mu})^{\top} \widehat{{\mathbf C}}^{-1} ({\mathbf x} - \widehat{\boldsymbol \mu})$ equals $4$. This set can be characterized more conveniently using an EVD of the sample covariance matrix $\widehat{{\mathbf C}}$. The matrix $\widehat{{\mathbf C}}$ is symmetric, so it has an EVD $\widehat{{\mathbf C}} = \mathbf{V} {\boldsymbol \Lambda} \mathbf{V}^{\top}$ with an orthogonal matrix $\mathbf{V}$ that contains the eigenvectors in its columns. Transforming the feature vector ${\mathbf x}$ of a day according to $\widetilde{{\mathbf x}} := \mathbf{V}^{\top} ({\mathbf x} - \widehat{\boldsymbol \mu})$ turns the quadratic form into \[ ({\mathbf x} - \widehat{\boldsymbol \mu})^{\top} \widehat{{\mathbf C}}^{-1} ({\mathbf x} - \widehat{\boldsymbol \mu}) = \widetilde{{\mathbf x}}^{\top} {\boldsymbol \Lambda}^{-1} \widetilde{{\mathbf x}} = \frac{\widetilde{x}_{1}^{2}}{\lambda_{1}} + \frac{\widetilde{x}_{2}^{2}}{\lambda_{2}} \text{,} \] since $\widehat{{\mathbf C}}^{-1} = \mathbf{V} {\boldsymbol \Lambda}^{-1} \mathbf{V}^{\top}$. The ellipse is therefore the set where $\widetilde{x}_{1}^{2}/\lambda_{1} + \widetilde{x}_{2}^{2}/\lambda_{2} = 4$, with half-axes $2\sqrt{\lambda_{1}}$ and $2\sqrt{\lambda_{2}}$ along the coordinate axes of $\widetilde{{\mathbf x}}$, that is, along the eigenvectors. The transformed days have the sample covariance matrix $\mathbf{V}^{\top} \widehat{{\mathbf C}} \mathbf{V} = {\boldsymbol \Lambda}$: the two new coordinates have sample covariance zero, and the eigenvalues are their sample variances. Replacing each day by its first coordinate $\widetilde{x}_{1}$ alone keeps the direction of largest variance, which is the idea of principal component analysis (PCA) (Bishop, 2006, Sect. 12.1.1).
P-fastBesides describing the shape of a dataset, the EVD can be
used to speed up the implementation of a machine learning (ML) method.
Consider gradient descent (GD) for
linear regression, with the update
${\mathbf w}^{(t+1)} = {\mathbf w}^{(t)} -
(2\eta/m) {\mathbf X}^{\top}
\big( {\mathbf X} {\mathbf w}^{(t)} - {\mathbf y} \big)$
for $t = 0,1,\ldots$, with the feature matrix
${\mathbf X}$ and label vector
${\mathbf y}$ of the training set (see linear regression). The
matrix ${\mathbf X}^{\top}{\mathbf X}$ is symmetric, so
it has an EVD
${\mathbf X}^{\top}{\mathbf X} = \mathbf{V} {\boldsymbol \Lambda} \mathbf{V}^{\top}$
with an orthogonal matrix $\mathbf{V}$. In the transformed
coordinates
$\widetilde{{\mathbf w}}^{(t)} := \mathbf{V}^{\top} {\mathbf w}^{(t)}$,
the update decouples into
\[
\widetilde{w}_{j}^{(t+1)} =
\big( 1 - (2\eta/m) \lambda_{j} \big)
\widetilde{w}_{j}^{(t)}
+ (2\eta/m)
\big( \mathbf{V}^{\top} {\mathbf X}^{\top} {\mathbf y} \big)_{j}
\text{.}
\]
After the one-time computation of the EVD, each iteration is an element-wise multiplication and addition of
vectors of length $d$
(pythondemos/evd.py).
Another application of the EVD in ML is the clustering of graph-structured data (Luxburg, 2007). Consider data points represented as the nodes $i = 1, \,\ldots, \,n$ of an undirected graph $\mathcal{G}$, e.g., the users of a social network with edges given by friendships. The Laplacian matrix ${\mathbf L}^{(\mathcal{G})}$ of the graph $\mathcal{G}$ is symmetric and positive semi-definite (psd) (Luxburg, 2007, Prop. 1). It has an EVD ${\mathbf L}^{(\mathcal{G})} = \mathbf{V} {\boldsymbol \Lambda} \mathbf{V}^{\top}$ with an orthogonal matrix $\mathbf{V}$ and nonnegative eigenvalues.
P-specIf the graph $\mathcal{G}$ is
connected, the EVD has additional structure: the
eigenvalue $0$ has multiplicity one, with the all-ones
vector as its eigenvector (Luxburg, 2007, Prop. 2).
Moreover, there is then a distinguished eigenvector, called
the Fiedler vector: an eigenvector of the smallest
nonzero eigenvalue, the algebraic connectivity of $\mathcal{G}$
(Fiedler, 1973). The Fiedler vector can be used for
clustering the nodes of the graph, which is the idea of
spectral clustering (Luxburg, 2007).
Fig. 3 shows the Fiedler vector
of a connected graph with six nodes: two
clusters of three nodes and a single edge joining the two
clusters.
pythondemos/evd.py
See also: matrix, eigenvector, eigenvalue, diagonalizable, invertible, orthogonal, Laplacian matrix, algebraic connectivity, Fiedler vector, spectral clustering, gradient descent, linear regression, sample covariance matrix, principal component analysis, spectral decomposition, singular value decomposition, minimal polynomial.
@misc{dictml_evd,
author = {Jung, Alexander},
editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
title = {eigenvalue decomposition (EVD)},
howpublished = {Dictionary of Applied Machine Learning (course edition)},
year = {2026},
doi = {10.5281/zenodo.21569296},
note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-11-11},
url = {https://dictionaryofml.org/terms/evd.html}
}