Eigenvalues of Matrices and Graphs

The interplay between spectrum and structure of graphs is the recurring theme of the three more or less independent chapters of this thesis. The first chapter provides a method to relate the eigensolutions of two matrices, one being the principal submatrix of the other, via an arbitrary annihilating polynomial. This is extended to lambda-matrices and to matrices the entries of which are rational functions in one variable. The extension may be interpreted as a possible generalization of other known techniques which aim at reducing the size of a matrix while preserving the spectral information. Several aspects of an application in order to reduce the computational costs of ordinary eigenvalue problems are discussed. The second chapter considers the straightforward extension of the well known concept of equitable partitions to weighted graphs, i.e. complex matrices. It provides a method to divide the eigenproblem into smaller parts corresponding to the front divisor and its complementary factor in an easy and stable way with complexity which is only quadratic in matrix size. The exploitation of several equitable partitions ordered by refinement is discussed and a suggestion is made that preserves hermiticity if present. Some generalizations of equitable partitions are considered and a basic procedure for finding an equitable partition of complex matrices is given. The third chapter deals with isospectral and unitary equivalent graphs. It introduces a construction for unitary equivalent graphs which contains the well known GM-switching as a special case. It also considers an algebra of graph matrices generated by the adjacency matrix that corresponds to the 1-dimensional Weisfeiler-Lehman stabilizer in a way that mimics the correspondence of the coherent closure and the 2-dimensional Weisfeiler-Lehman stabilizer. The algebra contains the degree matrix, the (combinatorial, signless and normalized) Laplacian and the Seidel matrix. An easy construction produces graph pairs that are simultaneously unitary equivalent w.r.t. that algebra