Combinatorial Matrix Theory

A collection of projects in combinatorial matrix theory and inverse eigenvalue problems, implementing algorithms from research in spectral graph theory, structured matrix construction, and signed graph Laplacians.

Table of Contents

Inverse Eigenvalue Problems

Given a graph and desired spectral data, construct a real symmetric matrix matching both the graph structure and the spectrum.

Project	Description	Language
Lambda-SIEP	Structured Inverse Eigenvalue Problem using the Jacobian/Newton method	SageMath
Lambda-Mu for Trees	Prescribe eigenvalues of a tree matrix and its principal submatrix (vertex deletion)	SageMath
Lambda-Tau for Trees	Prescribe eigenvalues of a tree matrix and its principal submatrix (edge deletion / two-vertex deletion)	SageMath
Lambda-ISPMPG	Inverse Spectral Problem for Matrix Polynomials and Graphs	SageMath
Nowhere-Zero Construction	Construct nowhere-zero symmetric matrices with prescribed eigenvalues	SageMath

Laplacian Matrices of Signed Graphs

Study the spectral properties of Laplacian matrices of signed graphs, including eigenvalue crossings and achievable inertias.

Project	Description	Language
Eigenvalue Crossings	Track Laplacian eigenvalue crossings through zero as edge weights vary	MATLAB
Laplacian Inertia	Comprehensive library for signed graph Laplacian inertias, flexibility, and the polynomial $M(\Gamma(t))$	SageMath

Background

Combinatorial Matrix Theory

Combinatorial matrix theory studies the interplay between the combinatorial structure of a matrix (its zero/nonzero pattern, or equivalently its associated graph) and its algebraic properties (eigenvalues, rank, inertia). A central theme is:

How does the graph of a matrix constrain its possible spectra?

The Inverse Eigenvalue Problem

The Inverse Eigenvalue Problem for Graphs (IEPG) asks: given a graph $G$ on $n$ vertices and real numbers $\lambda_1, \ldots, \lambda_n$, does there exist a real symmetric matrix $A$ with $G(A) = G$ and $\text{spec}(A) = {\lambda_1, \ldots, \lambda_n}$? Here $G(A)$ denotes the graph whose edges correspond to the nonzero off-diagonal entries of $A$.

Signed Graph Laplacians

A signed graph assigns a sign ($+$ or $-$) to each edge. The signed Laplacian $L = D - A_\sigma$ (where $A_\sigma$ is the signed adjacency matrix) generalizes the classical Laplacian. Unlike the unsigned case, signed Laplacians can have negative eigenvalues, and the achievable inertias are governed by the flexibility $\tau = n + c - c_+ - c_-$.

Requirements

• SageMath (version 8+) for the inverse eigenvalue problem solvers and the Laplacian inertia library
• MATLAB for the eigenvalue crossings code
• Python 3 with NumPy, SciPy, Matplotlib, NetworkX for the visualization scripts

References

• K. Hassani Monfared, The Jacobian Method: The Art Of Finding More Needles in Nearby Haystacks, PhD dissertation, University of Wyoming, 2014.
• J. Bronski and L. DeVille, Spectral Theory for Dynamics on Graphs Containing Attractive and Repulsive Interactions, SIAM J. Appl. Math., 74(1), 2014.
• W. Barrett, A. Lazenby, N. Malloy, C. Nelson, W. Sexton, The combinatorial inverse eigenvalue problems: complete graphs and small graphs with strict inequality, Electronic Journal of Linear Algebra, 26, 2013.

Author

Keivan Hassani Monfared (k1monfared)