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

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

-
–  Aryabhata Feb 9 '11 at 20:52

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.

-
Actually if the graph is undirected and $d$-regular, then its largest eigenvalue is $d$ and it is also the largest eigenvalue in absolute value (and hence is the spectral radius of the adjacency matrix). –  David Kohler May 23 '11 at 23:36

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.?

-
This should have been either added to the question or asked as a separate question. Please use answers only to answer questions. Thanks! –  Mariano Suárez-Alvarez Sep 5 '11 at 15:45
Sorry for my late answer. Actually the property I was referring to is the ergodicity of a chain. Actually we have ergodicity if the state probability vector to tend to a finite value for k (step) tending to infinite. To compute state prob for every step we multiply the initial state with probability transition matrix elevated to the number of steps. –  Andry Feb 14 '12 at 0:05
If we put this to limit, the only quantity interested by the number of steps (k) is the probability transition matrix. So, if multiplying that matrix for itself many many times, we get a final constant element, then the chain is ergodic. Hope I answered your question. Sorry, very sorry for being so late. –  Andry Feb 14 '12 at 0:05