## 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


To make pandas tables more readable, CSS settings are applied to HTML tables.

from IPython.core.display import HTML

style = """
<style>
.dataframe thead tr:only-child th {
text-align: right;
}

.dataframe thead th {
text-align: left;
padding: 5px;
}

.dataframe tbody tr th {
vertical-align: top;
padding: 5px;
}

.dataframe tbody tr:hover {
background-color: #ffff99;
}

.dataframe {
background-color: white;
color: black;
font-size: 16px;
}

</style>
"""
HTML(style)


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.