Eigenvalues, Multiplicities and Graphs

Among the n eigenvalues of an n-by-n matrix may be several repetitions (the
number of which counts toward the total of n). For general matrices over a gen-
eral 〠eld, these multiplicities may be algebraic (the number of appearances as
a root of the characteristic polynomial) or geometric (the dimension of the cor-
responding eigenspace). These multiplicities are quite important in the analysis
of matrix structure because of numerical calculation, a variety of applications,
and for theoretical interest. We are primarily concerned with geometric multi-
plicities and, in particular but not exclusively, with real symmetric or complex
Hermitian matrices, for which the two notions of multiplicity coincide.
It has been known for some time, and is not surprising, that the arrange-
ment of nonzero entries of a matrix, conveniently described by the graph
of the matrix, limits the possible geometric multiplicities of the eigenvalues.
Much less limited by this information are either the algebraic multiplicities
or the numerical values of the (distinct) eigenvalues. So, it is natural to study
exactly how the graph of a matrix limits the possible geometric eigenvalue
multiplicities.