M.Sc Thesis
M.Sc Student Farber Miriam Bounds for the Eigenvalues of Symmetric Matrices Department of Mathematics Professor Emeritus Abraham Berman

Abstract

This thesis contains several contributions to the study of eigenvalues of real symmetric matrices.

In chapter 3, we study weighted graphs. For a weighted graph G, we prove that the second largest Laplacian eigenvalue is equal to or greater than the third largest degree. An upper bound for the second smallest eigenvalue of the signless Laplacian of G is also obtained. We also present several applications, including an upper bound for the independence number of a graph.

In chapter 4, we define NPO(k) to be the smallest number n such that the adjacency matrix of any unweighted graph with n vertices or more has at least k nonpositive eigenvalues. We prove that the values of NPO(k) for k=1,2,3,4,5 are 1,3,6,10,16 respectively. In addition, we prove that for all k>4, R(k,k) > NPO(k) > T_k, where R(k,k) is the Ramsey number for k and k, and T_k is the k-th triangular number. This implies that the k-th largest Laplacian eigenvalue is bounded from below the NPO(k)-th largest degree.

In chapter 5, we study hollow, symmetric nonnegative (HSN) matrices. We show that among n-by-n such matrices, any number k, 1 < k < n of nonpositive eigenvalues is possible. However, as n grows, small numbers of nonpositive eigenvalues become increasingly rare. Nonetheless, we show that every n-by-n HSN matrix with positive off-diagonal entries and with 2 nonpositive eigenvalues may be embedded, as a principal submatrix, in an (n)-by-(n) such matrix. Our proof recognizes some special, anti-Morishima structure of Schur complements.

In chapter 6, we investigate the Schur complement structure with respect to 2-by-2 principal submatrices, in HSN matrices with 2 nonpositive eigenvalues. The investigation leads a unique and surprising graph theoretical connection. For larger numbers of nonpositive eigenvalues, connections to polyhedra are also presented. Exact relations to copositive matrices and Morishima matrices are described as well.

It is known that majorization is a complete description of the relations between the eigenvalues and diagonal entries of real symmetric matrices. However, for large subclasses of such matrices, the diagonal entries impose much greater restrictions on the eigenvalues. In chapter 7 we study the additional restrictions that come from the off-diagonal sign-pattern classes of real symmetric matrices. Several results are given for the all nonpositive and all nonnegative classes and for the third class that appears when n=4. Complete descriptions of the possible relationships are given in low dimensions.