Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Related: math.stackexchange.com/questions/18945/… –  Aryabhata Feb 9 '11 at 20:52
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
1  
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.