Wolfram Library Archive


Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings
Title

THE COMBINATORIAL INVERSE EIGENVALUE PROBLEM: COMPLETE GRAPHS AND SMALL GRAPHS WITH STRICT INEQUALITY
Authors

WAYNE BARRETT
ANNE LAZENBY
NICOLE MALLOY
CURTIS NELSON
WILLIAM SEXTON
RYAN SMITH
JOHN SINKOVIC
TIANYI YANG
Journal / Anthology

Electronic Journal of Linear Algebra
Year: 2013
Volume: 26
Page range: 656-672
Description

Let G be a simple undirected graph on n vertices and let S(G) be the class of real symmetric n n matrices whose nonzero off-diagonal entries correspond exactly to the edges of G. Given 2n − 1 real numbers 1  μ1  2  μ2   n−1  μn−1  n, and a vertex v of G, the question is addressed of whether or not there exists A 2 S(G) with eigenvalues 1, . . . , n such that A(v) has eigenvalues μ1, . . . , μn−1, where A(v) denotes the matrix with the vth row and column deleted. General results that apply to all connected graphs G are given first, followed by a complete answer to the question for Kn. Since the answer is constructive it can be implemented as an algorithm; a Mathematica code is provided to do so. Finally, for all connected graphs on 4 vertices it is shown that the answer is affirmative if all six inequalities are strict.
Subjects

*Mathematics > Algebra
*Mathematics > Algebra > Linear Algebra
Keywords

Graph, Interlacing inequalities, Inverse eigenvalue problem, Symmetric matrix.