Repeated Second Eigenvalue of the Adjacency Matrix of a Graph - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T01:40:35Z http://mathoverflow.net/feeds/question/101323 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101323/repeated-second-eigenvalue-of-the-adjacency-matrix-of-a-graph Repeated Second Eigenvalue of the Adjacency Matrix of a Graph Eric Naslund 2012-07-04T17:35:21Z 2012-07-04T21:24:37Z <p>This question is motivated by a talk I went to earlier today.</p> <p>Suppose we have a $d$-regular graph $G$ with $n$ vertices, with adjacency matrix $A$. </p> <p>Let $$\lambda_1\geq \lambda_2 \geq\dots \geq \lambda_n$$ be the eigenvalues of $A$, so in particular $\lambda_1=d$. If the first two eigenvalues are the same, that is $\lambda_2=\lambda_1$, then it tells us a lot about the structure of the graph. In particular, the graph must be disconnected. (This is an if and only if condition) </p> <p>What if the second and third eigenvalues are equal? That is, suppose that $\lambda_1>\lambda_2=\lambda_3$. What does that tell us (if anything) about the structure of the graph? </p> <p><strong>Additional questions:</strong> If $\lambda_1=\lambda_2=\cdots=\lambda_k&lt;\lambda_{k+1}$, then the graph will have exactly $k$ connected components. What can we say about $G$ if $\lambda_1&lt;\lambda_2=\cdots=\lambda_{k+1}&lt;\lambda_{k+2}$? That is, the second eigenvalue has multiplicity $k$.</p> <p>What if the $n^{th}$ eigenvalue has multiplicity $k$?</p> http://mathoverflow.net/questions/101323/repeated-second-eigenvalue-of-the-adjacency-matrix-of-a-graph/101344#101344 Answer by Chris Godsil for Repeated Second Eigenvalue of the Adjacency Matrix of a Graph Chris Godsil 2012-07-04T21:24:37Z 2012-07-04T21:24:37Z <p>It you allow weighted adjacency matrices and if you insist (among there things) that the eigenspace associated to $\lambda_2$ satisfies the "strong Arnold condition", then you are dealing the Colin de Verdiere invariant. For this, the best I can do now is to refer you to the wikipedia article on this invariant.</p> <p>But you question is what can be said about connected graphs where $\lambda_1$ has multiplicity greater than one. The short answer is: very little. One reason for this that if our graph was associated with some physical of chemical system, than having $\lambda_2$ very close to $\lambda_3$ will have much the same effect as having $\lambda_2=\lambda_3$. There are certainly no results on graph spectra that relate properties of a graph to whether or not $\lambda_2$ is simple.</p> <p>It is true that the existence of non-trivial automorphisms can prevent all eigenvalues from being simple. The classic result of this type is that if the automorphism group of a graph is vertex transitive, then its eigenvalues can not all be simple. Stronger assumptions may give more, since each eigenspace provides a representation of the automorphism group, and if one of these representations is faithful, then the multiplicity is at least the minimum degree of an irreducible representation of the group.</p> <p>On the other hand though, having eigenvalues of large multiplicity tells us nothing about the automorphism group. Strongly regular graphs have large multiplicities, but in general no non-trivial automorphisms.</p>