Knowledge about Graph Spectral Theory and correlation between a graph Weighted Adjacency matrix and its eigenvalues

Question

I know that this question is some sort of bridge between Informatics and Mathematics, not knowing the best place where to post this question, I opted for this place because of the type of answer I want (which concerns Math more than anything).

Consider to have a graph represented by a collection of nodes and connections. The best way to describe the graph is through the adjacency matrix (AM): a matrix that has 0 or 1 if one node is connected to another (we consider non-directed graphs, so we have all bidirectional connections).

Does anyone know whether the eigenvalues of the matrix implies something for the graph??? properties, topology.... I ask this question because I've almost finished studying Markov Chains. In a chain, the matrix of transition probabilities P (for discrete time markov chains), or the matrix of transition frequencies Q (for cont-time markov chains), can be evaluated (their eigenvalues) in order to inspect whether the chain is ergodic or not (with a parallelism to Control Theory: eigenvalues in the unitary circle or in the negative half-plane).

I am trying to find something similar for graphs.

Thank you

Answer 1

There are a lot of properties on eigenvalues of adjacency matrix.

If the diameter of $G$ is d, then $A$ has at least $d+1$ distinct eigenvalues.

For instance, if a graph is $d$-regular, then its largest eigenvalue is bound by d. He is connected if and only the multiplicity of d is 1.

A complete bipartite graph $K_{m,n}$ has three eigenvalues : 0, $\lambda$, $-\lambda$ where $\lambda = \sqrt{mn}$.

For more, you should check a book on algebraic graph theory like Algebraic Graph Theory, Godsile and Royle, Springer.

Note : The AM is not the "best" way to describe a graph. It's one way, very interesting in case you're looking to compute paths.

Answer 2

I'm also interested on the convergence of Markov chains on a graph and found your questions very interesting. As per my knowledge, for adjacancy matrices, eigenvalues of AM implies many things. It implies the connectivity of the graph. If the difference between the largest eigenvalue and the second largest eigenvalue (this is known as spectral gap) is large, it means that the graph is a well-connected graph. In fact in spectral graph theory expansion parameter of a graph (for a d-regular graph) is lower bounded by the spectral gap of the adjacency matrix. You can read more on this in http://www.math.ias.edu/~boaz/ExpanderCourse/allnotes.pdf

I have a question on one thing you mentioned. It's about what you mentioned as "In a chain, the matrix of transition probabilities P (for discrete time markov chains), or the matrix of transition frequencies Q (for cont-time markov chains), can be evaluated (their eigenvalues) in order to inspect whether the chain is ergodic or not (with a parallelism to Control Theory: eigenvalues in the unitary circle or in the negative half-plane)."

Can you please elaborate more on this and help me to get an idea about which properties can be implied using the eigenvalues of the transition probability matrix of a markov chain on graph.?