Algebraic Graph Theory Seminar - Chris Godsil

Thursday, August 15, 2019 — 2:30 PM EDT

Title: Upsetting Matrices

 Speaker: Chris Godsil Affiliation: University of Waterloo Room: MC 5479

Abstract:

If $A$ and $P$ are $n\times n$ matrices and the entries of $B$ are small, we may view $A+B$ as a perturbation of $A$, and expect that the spectral properties of $A+B$ should be related to those of $A$. In our case we are interested in linear combinations of the form $A+tB$, where $A$ and $B$ are Hermitian and $t$ is real, so-called Hermitian pencils. For example, if $A$ is a symmetric weighted adjacency matrix of a graph $X$, then the number of non-negative eigenvalues of $A$ is an upper bound on the independence number of $X$. It is then natural to consider what happens to the eigenvalues when we change the weight of an edge. Related problems arise in the analysis of search algorithms based on continuous quantum walks.

I will provide an introduction to perturbation theory of Hermitian pencils, focussing on what the theory predicts, and only proving the simplest parts.
Location
MC - Mathematics & Computer Building
5479
200 University Avenue West

Waterloo, ON N2L 3G1

August 2019

S M T W T F S
28
29
30
31
3
4
5
7
9
10
11
12
13
14
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1. 2019 (114)
1. August (9)
2. July (17)
3. June (18)
4. May (16)
5. April (9)
6. March (24)
7. February (13)
8. January (8)
2. 2018 (138)
1. December (2)
2. November (18)
3. October (14)
4. September (9)
5. August (2)
6. July (10)
7. June (13)
8. May (17)
9. April (9)
10. March (19)
11. February (14)
12. January (11)
3. 2017 (103)
4. 2016 (137)
5. 2015 (136)
6. 2014 (88)
7. 2013 (48)
8. 2012 (39)
9. 2011 (36)
10. 2010 (40)
11. 2009 (40)
12. 2008 (39)
13. 2007 (15)