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.

Fooling around in matlab, I did an eigenvalue decomposition of the adjacency matrix of $K_5$.

 A = [0     1     1     1     1;
      1     0     1     1     1;
      1     1     0     1     1;
      1     1     1     0     1;
      1     1     1     1     0];

The eigenvalues are $4, -1, -1, -1, -1$. It now seems obvious that the largest eigenvalue for the adjacency matrix for $K_n$ would be $n-1$. What I don't understand is why $-1$ is an eigenvalue of multiplicity $n-1$. Is there any special meaning to this?

share|improve this question
1  
Good question, from spectral graph theory we know that the multiplicity of $\lambda_{1}$ of Laplacian equals the number of connected components of the graph, which is may be related to your statement, therefore it looks like eigenvalues of adjacent matrix should be related to eigenvalues of Laplacian. –  com Feb 24 '12 at 20:48

5 Answers 5

up vote 10 down vote accepted

It is possible to give a lower bound on the multiplicities of the eigenvalues of the adjacency or Laplacian matrix of a graph $G$ using representation theory.

Namely, the vector space of functions $G \to \mathbb{C}$ is a representation of the symmetry group, and both the adjacency and Laplacian matrix respect this group action. It follows that each irreducible subrepresentation lies in an eigenspace of the adjacency and Laplacian matrices, so their dimensions give a lower bound on the multiplicities.

In this particular case, $K_n$ has symmetry group the full symmetric group $S_n$, and the corresponding representation decomposes into the trivial representation (this corresponds to the eigenvalue $n-1$) and an $n-1$-dimensional irreducible representation, so there can only be one other eigenvalue and it must have multiplicity $n-1$. Moreover, the sum of the eigenvalues is $0$ because the trace of the adjacency matrix is zero, so the remaining eigenvalue must be $-1$.

This is all just a very fancy way of saying that

Any permutation of an eigenvector of $K_n$ is also an eigenvector with the same eigenvalue. If the eigenvector doesn't have all of its entries equal, then its permutations span a vector space of dimension $n-1$, so the remaining eigenvalue has multiplicity $n-1$.

Which is in turn just a very fancy way of saying that

Any vector $v$ all of whose entries sum to zero is an eigenvector of the adjacency matrix $A_n$ of $K_n$; moreover, it is easy to see that $(A_n + I)v = 0$ for any such $v$, hence $A_n v = -v$.

That is a straightforward explanation but it misses the bigger lesson, which is that

Highly symmetric graphs have eigenvalues of high multiplicity.


Another argument proceeds using the observation that, on the one hand, $\text{tr}(A^k)$ counts the number of walks of length $k$ which begin and end at the same vertex and, on the other hand, $$\text{tr}(A^k) = \sum_{i=1}^n \lambda_i^k$$

where $\lambda_i$ are the eigenvalues. This sequence uniquely determines the eigenvalues (exercise), so to prove the desired result it suffices to prove that $$\text{tr}(A^k) = (n-1)^k + (n-1)(-1)^k.$$

Now, the total number of walks of length $k-1$ is just $n(n-1)^{k-1}$, where the first $n$ counts the number of possible starting vertices and each factor of $n-1$ counts the possible next vertices. If such a walk ends at the original vertex (so is itself a closed walk of length $k-1$), it cannot be extended to a closed walk of length $k$; otherwise, it can be uniquely extended as such. Thus it follows that $$n(n-1)^{k-1} = \text{tr}(A^{k-1}) + \text{tr}(A^k)$$

and then the desired result follows by induction from the initial condition $\text{tr}(A^0) = n$.

share|improve this answer
    
This is a gem. Does a high multiplicity of "near" eigenvalues ($\| \lambda_i - \lambda_j \| < \epsilon$) mean anything, or is there an abrupt transition? –  Emre Feb 26 '12 at 19:12
    
@Emre: for large graphs and small $\epsilon$ it might be indicative of approximate symmetry (think of adding a single edge to a large highly symmetric graph). –  Qiaochu Yuan Feb 27 '12 at 1:09

Note that $B = A + I$ is the $n \times n$ matrix of all $1$'s, which is $e e^T$ where $e$ is a column vector of all $1$'s. Note that $B e = n e$, so $e$ is an eigenvector of $B$ with eigenvalue $n$ (and thus an eigenvector of $A$ with eigenvalue $n-1$), while every vector orthogonal to $e$ is in $\rm Ker B$, so is an eigenvector of $B$ with eigenvalue $0$ and of $A$ with eigenvalue $-1$.

share|improve this answer

This is too much for a comment. It won't be a complete picture but it is a group of interesting ideas surrounding this question.

A connected graph of diameter $d$ has at least $d + 1$ distinct eigenvalues. Thus, the only connected graph that can possibly have only 2 distinct eigenvalues is the graph of diameter 1, the complete graph!

The class of strongly regular graphs is a class that always realizes that bound, i.e., they have exactly $d+1$ distinct eigenvalues (and no more). A complete graph is strongly regular.

All $k$-regular graphs have $k$ as an eigenvalue with multiplicity the same as the number of connected components in the graph. Thus, a connected $k$-regular graph has $k$ as an eigenvalue of multiplicity 1. And, for any other eigenvalue, $\lambda$, we have $|\lambda| \leq k$.

The first few sections of "Algebraic Graph Theory" by Biggs has a bunch of these ideas.

share|improve this answer

Each eigenvalue of the adjacency matrix of a graph corresponds to what I call a spectral geometric realization of the graph.

A geometric realization associates the vertices with a not-necessarily-distinct points in Euclidean some-dimensional space (the edges can be considered not-necessarily-non-degenerate segments joining those points).

A matrix whose rows form an orthogonal basis of the eigenspace has columns serve as coordinate vectors of vertices of a (projection of a) spectral realization. A spectral realization has two key properties:

  • It is harmonious: Each automorphism of the graph induces a "rigid" isometry on the realization.
  • It is eigenic: for any vertex $v$, we have $\lambda [v] = \sum_{u \text{ adj } v} [u]$, where $[x]$ gives the coordinate vector of vertex $x$, and $\lambda$ is the associated eigenvalue.

Now, the complete graph $K_n$ has two spectral realizations in $\mathbb{R}^n$ (though they can be projected into lower-dimensional spaces).

  • $\lambda=n-1$: The "dot", with all $n$ vertices realized by the "all 1s" coordinate vector.
  • $\lambda=-1$: The (origin-centered) "regular $n$-simplex" (segment, triangle, tetrahedron, etc).

In the case of the simplex, being origin-centered implies that its vertex vectors satisfy $[v_0]+[v_1]+[v_2]+[v_3]+[v_4]=0$. For any $v_i$, we can write

$$-1\;[v_i] = \sum_{j\ne i} [v_j]$$

Because a complete graph has each vertex adjacent to all others, this is precisely a statement of the eigenic property for eigenvalue $-1$.

Note that the "dot" realization ---while itself $0$-dimensional--- determines a $1$-dimensional vector space; the "simplex" uses-up the remaining $n-1$ dimensions, accounting for the multiplicity of eigenvalue $-1$.


For more information, see my Bloog post "Spectral Realizations of Graphs". There you'll find a link to a note that includes hundreds of illustrations of spectral realizations of highly-symmetric graphs.

share|improve this answer

consider matrix J_n has n oder of all ones. A(K_n) = J_n - I_n the eigenvalues of J_n are n and 0, the eigenvalues of I_n is 1. apply the spectral mapping theory.

share|improve this answer
1  
Hi, you seem to be new here. For some basic information about writing math at this site see e.g. here, here, here and here. Making answers easier to read will probably make it easier to have them recognised as useful. –  Tom Oldfield Dec 20 '12 at 4:20

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.