# eigenvalue decomposition (EVD) *Entry of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org) (course edition), by Alexander Jung, Aalto University. CC BY 4.0. Updated 2026-11-10. [HTML](https://dictionaryofml.org/terms/evd.html) · [typeset PDF](https://dictionaryofml.org/terms/evd.pdf) · [LaTeX](https://dictionaryofml.org/terms/evd.tex) · [Python demo](https://dictionaryofml.org/terms/evd.py) · [notebook](https://dictionaryofml.org/terms/evd.ipynb)* Math is LaTeX with the book's macros expanded, so no notation package is needed to read it. ## Abstract 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 methods. For linear regression, each gradient descent iteration then reduces to element-wise operations. The EVD of the Laplacian matrix of an undirected graph is used by spectral clustering. ## Definition Each 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. ![Figure 1 of the entry evd](https://dictionaryofml.org/terms/fig/evd-fig1.svg) *Figure 1: Every $19$th of the $366$ days of 2024 at Krems an der Donau, $20$ days in all, drawn as gray dots. Each day is a data point with two features: the lowest and the highest temperature of that day. The ellipse is computed from the sample mean (cross) and the sample covariance matrix of all $366$ days. The solid arrow and the dashed arrow are the two eigenvectors of that sample covariance matrix, scaled to the half-axes of the ellipse, $2\sqrt{\lambda_{j}}\,{\mathbf v}^{(j)}$. Data generated by pythondemos/evd.py* An EVD for a square matrix ${\mathbf A} \in \mathbb{R}^{d \times d}$ is a factorization of the form $$ {\mathbf A} = \mathbf{V} {\boldsymbol \Lambda} \mathbf{V}^{-1} \text{.} $$ The columns of the matrix $\mathbf{V} = \big( {\mathbf v}^{(1)}, \,\ldots, \,{\mathbf v}^{(d)} \big)$ are eigenvectors of the matrix ${\mathbf A}$. The diagonal matrix ${\boldsymbol \Lambda} = {\rm diag} \big\{ \lambda_{1}, \,\ldots, \,\lambda_{d} \big\}$ contains the eigenvalues $\lambda_{j}$ corresponding to the eigenvectors ${\mathbf v}^{(j)}$. Multiplying the factorization by ${\mathbf v}^{(j)}$ gives ${\mathbf A} {\mathbf v}^{(j)} = \lambda_{j} {\mathbf v}^{(j)}$: each eigenvector is a direction that ${\mathbf A}$ only scales, by the factor $\lambda_{j}$; a single such pair satisfies ${\mathbf A} {\mathbf x} = \lambda {\mathbf x}$, and the EVD collects $d$ of them, indexed by $j$. 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, 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). Matrices 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. ![Figure 2 of the entry evd](https://dictionaryofml.org/terms/fig/evd-fig2.svg) *Figure 2: The matrix ${\mathbf A} \in \mathbb{R}^{2 \times 2}$ from the display above has the eigenvalues $\lambda_{1} = 1.7$ and $\lambda_{2} = 0.5$, with the eigenvectors ${\mathbf v}^{(1)}$ along $(2,1)^{\top}$ and ${\mathbf v}^{(2)}$ along $(-1,1)^{\top}$ (solid arrows). The dashed arrows are the images under ${\mathbf A}$, and each dotted line carries one solid arrow. The eigenvector ${\mathbf v}^{(1)}$ stays on its line, stretched to the longer dashed arrow ${\mathbf A} {\mathbf v}^{(1)} = \lambda_{1} {\mathbf v}^{(1)}$; the eigenvector ${\mathbf v}^{(2)}$ stays on its line, shrunk to the shorter dashed arrow ${\mathbf A} {\mathbf v}^{(2)} = \lambda_{2} {\mathbf v}^{(2)}$. The vector ${\mathbf u} = {\mathbf v}^{(1)} + {\mathbf v}^{(2)}$ leaves its dotted line: its image ${\mathbf A} {\mathbf u} = \lambda_{1} {\mathbf v}^{(1)} + \lambda_{2} {\mathbf v}^{(2)}$ points elsewhere, because its two expansion coefficients are scaled by different factors* Two sufficient conditions for a real-valued square matrix to be diagonalizable are that it is a symmetric matrix or that its $d$ eigenvalues are distinct (Golub and Loan, 2013; Horn and Johnson, 2013, Thm. 1.3.9, Thm. 4.1.5). For a real-valued symmetric matrix, the EVD has additional structure: the eigenvectors can be chosen to form an orthonormal basis, i.e., the matrix $\mathbf{V}$ in the factorization can be chosen to be orthogonal (Horn and Johnson, 2013, Thm. 4.1.5). The condition that is both necessary and sufficient is that every root of the minimal polynomial of the matrix is simple (Horn and Johnson, 2013, Cor. 3.3.10). For a complex-valued matrix, the first condition is that it is Hermitian; a complex symmetric matrix need not be diagonalizable (Horn and Johnson, 2013, Thm. 4.1.5, Problem 4.4.P10). 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}$. The 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 (Bishop, 2006, Sect. 12.1.1). Besides describing the shape of a dataset, the EVD can be used to speed up the implementation of a machine learning method. Consider gradient descent 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 machine learning 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 (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. If 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. ![Figure 3 of the entry evd](https://dictionaryofml.org/terms/fig/evd-fig3.svg) *Figure 3: (a) A connected undirected graph with six nodes: the cluster of nodes $1$, $2$, $3$ and the cluster of nodes $4$, $5$, $6$, each node connected to the other two of its cluster. The two clusters are joined by the single edge between nodes $3$ and $4$. (b) The Fiedler vector ${\mathbf v}^{(2)}$ of the Laplacian matrix of the graph in (a), as a column vector; a thin dotted line connects each node $i$ to its entry $v^{(2)}_{i}$. The signs of the entries recover the two clusters. Entries computed by pythondemos/evd.py* **See also:** [matrix](https://dictionaryofml.org/terms/matrix.html), eigenvector, [eigenvalue](https://dictionaryofml.org/terms/eigenvalue.html), diagonalizable, invertible, orthogonal, Laplacian matrix, algebraic connectivity, Fiedler vector, spectral clustering, [gradient descent](https://dictionaryofml.org/terms/gd.html), [linear regression](https://dictionaryofml.org/terms/linreg.html), sample covariance matrix, [principal component analysis](https://dictionaryofml.org/terms/pca.html), spectral decomposition, [singular value decomposition](https://dictionaryofml.org/terms/svd.html), minimal polynomial. ## References - Horn and Johnson (2013). Matrix Analysis. *Cambridge Univ. Press*. - Golub and Loan (2013). Matrix Computations. *The Johns Hopkins Univ. Press*. - Bishop (2006). Pattern Recognition and Machine Learning. *Springer Science+Business Media*. - Luxburg (2007). A tutorial on spectral clustering. *Statist. Comput.*. - Fiedler (1973). Algebraic connectivity of graphs. *Czechoslovak Mathematical Journal*. ## Cite this entry ```bibtex @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} } ```