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.