Spectral Decomposition
A symmetric matrix (Hermitian matrix in the case of real numbers) can be decomposed based on its eigenvalues and eigenvectors in a form known as spectral decomposition.
In this article, I will explain an overview of spectral decomposition and its implementation in Python.
A matrix decomposition method similar to spectral decomposition is singular value decomposition (SVD). SVD is a form of spectral decomposition often used in recommendation systems.
For more details on SVD and low-rank approximations used in recommendation systems, please refer to the following article:
http://wayama.io/rec/linalg/base/
Source Code
GitHub
- The Jupyter notebook file is available here
Google Colaboratory
- To run it on Google Colaboratory, click here
Execution Environment
The OS used is macOS. Please note that the options may differ from those in Linux or Unix commands.
!sw_vers
ProductName: macOS
ProductVersion: 13.5.1
BuildVersion: 22G90
!python -V
Python 3.9.17
Import basic libraries and use watermark to check their versions. Also, set the seeds for random and numpy.
%matplotlib inline
%config InlineBackend.figure_format = 'svg'
import random
import scipy
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
import networkx as nx
import array_to_latex as a2l
seed = 123
random_state = 123
random.seed(seed)
np.random.seed(seed)
from watermark import watermark
print(watermark(python=True, watermark=True, iversions=True, globals_=globals()))
Python implementation: CPython
Python version : 3.9.17
IPython version : 8.17.2
numpy : 1.25.2
array_to_latex: 0.91
matplotlib : 3.8.1
networkx : 3.1
scipy : 1.11.2
Watermark: 2.4.3
Overview of Spectral Decomposition
First, let’s review the properties of a symmetric matrix.
Let $\mathbf{A}$ be a symmetric matrix with real components: $\mathbf{A} = \left(a_{ij}\right) \in \mathbb{R}^{n\times n}$. Since it is a symmetric matrix, $\mathbf{A} = \mathbf{A^T}$. The eigenvalues of this matrix are all real numbers. Let the eigenvalues be $\alpha_1, \alpha_2, \cdots, \alpha_n$, and they can be defined in ascending order as follows:
$$ \alpha_1 \leqq \alpha_2 \leqq \ldots \leqq \alpha_n $$
Let the eigenvectors corresponding to each eigenvalue be $\mathbf{v_1}, \mathbf{v_2}, \cdots, \mathbf{v_n}$, then:
$$ \mathbf{A} \mathbf{x}_i = \alpha_i \mathbf{x}_i \quad (i=1,2, \ldots, n) $$
Furthermore, the eigenvectors of a Hermitian matrix (symmetric matrix in the case of real numbers) form an orthonormal basis in the vector space.
$$ \mathbf{x}_i^T \mathbf{x}_j = \delta _{i j} $$
Therefore,
$$ \mathbf{A} \left(\begin{array}{llll} \mathbf{v_1} & \mathbf{v_2} & \cdots & \mathbf{v_n} \end{array}\right) = \left(\begin{array}{llll} \mathbf{v_1} & \mathbf{v_2} & \cdots & \mathbf{v_n} \end{array}\right) \left(\begin{array}{cccc} \alpha_1 & 0 & \cdots & 0 \\ 0 & \alpha_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \alpha_n \end{array}\right) $$
If we define $\mathbf{V}$ as
$$ \mathbf{V} = \left(\begin{array}{llll} \mathbf{v_1} & \mathbf{v_2} & \cdots & \mathbf{v_n} \end{array}\right) $$
then $\mathbf{V}^T\mathbf{V} = \mathbf{I}$, and $\mathbf{V}^T = \mathbf{V}^{-1}$, thus $\mathbf{V}\mathbf{V}^T = \mathbf{I}$ also holds.
Therefore,
$$ \mathbf{A} = \left(\begin{array}{llll} \mathbf{v}_1 & \mathbf{v}_2 & \cdots & \mathbf{v}_n \end{array}\right) \left(\begin{array}{cccc} \alpha_1 & 0 & \cdots & 0 \\ 0 & \alpha_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \alpha_n\ \end{array}\right) \left(\begin{array}{c}\ \mathbf{v}_1^T \\ \mathbf{v}_2^T \\ \vdots \\ \mathbf{v}_n^T \end{array}\right) $$
By focusing on each eigenvalue and calculating, it can be decomposed into a sum as follows:
$$ \mathbf{A} = \alpha_1 \mathbf{v}_1 \mathbf{v}_1^T + \alpha_2 \mathbf{v}_2 \mathbf{v}_2^T + \cdots + \alpha_n \mathbf{v}_n \mathbf{v}_n^T $$
This is one of the matrix decomposition methods known as spectral decomposition.
Implementation of Spectral Decomposition in Python
As an example, let’s implement spectral decomposition for the following matrix $\mathbf{A}$ using Python:
$$ \mathbf{A} = \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \end{pmatrix} $$
The eigenvalues need to be calculated, but we will use numpy for this. Since $\mathbf{A}$ is a symmetric matrix, numpy.linalg.eigh() can be applied.
# Define matrix A
A = np.array(
[
[0, 0, 0, 1, 0, 0, 1],
[0, 0, 0, 1, 1, 0, 1],
[0, 0, 0, 1, 0, 0, 1],
[1, 1, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0],
[1, 1, 1, 0, 0, 0, 0],
]
)
# Calculate eigenvalues
# a represents eigenvalues, v represents eigenvectors
a, v = np.linalg.eigh(A)
To verify that the eigenvectors are correct, calculate the following value:
$$ \left(\begin{array}{llll} \mathbf{v}_1 & \mathbf{v}_2 & \cdots & \mathbf{v}_n \end{array}\right) \left(\begin{array}{cccc} \alpha_1 & 0 & \cdots & 0 \\ 0 & \alpha_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \alpha_n\ \end{array}\right) \left(\begin{array}{c}\ \mathbf{v}_1^T \\ \mathbf{v}_2^T \\ \vdots \\ \mathbf{v}_n^T \end{array}\right) $$
# Reproduction verification
_A = v @ np.diagflat(a) @ v.T
a2l.to_ltx(np.abs(_A), frmt="{:.0f}", arraytype="pmatrix")
$$ \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \end{pmatrix} $$
We can see that the eigenvalues and eigenvectors are correctly obtained.
Finally, let’s perform the calculation according to the spectral decomposition equation.
# Verification of reproducibility using spectral decomposition
__A = 0
for i in range(len(v)):
__A += a[i] * v[:, i : i + 1] @ v[:, i : i + 1].T
a2l.to_ltx(np.abs(__A), frmt="{:.0f}", arraytype="pmatrix")
$$ \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \end{pmatrix} $$
It is confirmed that the original matrix $\mathbf{A}$ can be reproduced using the spectral decomposition equation.
Conclusion
In this article, I explained an overview of spectral decomposition and implemented it in Python.