Controlling the behaviour of eigenvalues

The interlacing method

Bachelor thesis (2022)

Authors

L.K.M. Verlinde Electrical Engineering, Mathematics and Computer Science

Contributors

A. Bishnoi Discrete Mathematics and Optimization - EEMCS (supervisor 1)
A.W. Marcus Swiss Federal Institute of Technology (supervisor 1)
B. Janssens Analysis - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 Lander Verlinde
More Info
expand_more

Published Date

27-06-2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

This thesis uses the method of interlacing polynomials to study the behaviour of eigenvalues of a matrix after a rank-one update. Specifically, interlacing polynomials, common interlacing and interlacing families are exhaustively studied. These are excellent tools to find bounds on the eigenvalues of updated matrices by keeping track of how they move.

This enables us to prove results in different mathematical fields. We investigate three of them. The first one is from spectral graph theory: we prove the existence of a sharp κ-approximation for any graph.

The second result is from linear algebra. It states that if a matrix has a high stable rank, it must contain a large column submatrix with large least singular value.  

Lastly, the proof of the Kadison-Singer Problem is discussed. Despite being a problem from analysis, it was solved with the interlacing method, which is originally a method from discrete mathematics.

This thesis shows how these three seemingly different problems are all connected by the same method, highlighting its advantages. The objective is to present a clear framework of the different facets of the interlacing method and provide an insight in the situations where one can expect the said method to be useful.