Eigenvalues of complement of regular graphsSo I have encountered the following fact:Let G be a d-regular graph with adjacency eigenvalues λ 1 ≥ . . . ≥ λ n . Then its complement graph G ¯ has eigenvalues n − 1 − λ 1 , − ( λ 2 + 1 ) , . . . , − ( λ n + 1 )The proof uses the fact that A ( G ¯ ) = J − A ( G ) − I, where J is the matrix with all ones. So if vi is an eigenvector of λ i , then A ( G ¯ ) v i = J v i − A ( G ) v i − v i . If i=1, then since G is regular, v 1 must be the vector of all ones, hence J v 1 = n v 1 But for i&gt;1, then does the equation A ( G ¯ ) v i = J v i − A ( G ) v i − v i = J v i − λ i v i − v i = − ( λ i + 1 ) v i imply that J v i = 0? If it does, then I can't see why it is true.

Question

Eigenvalues of complement of regular graphsSo I have encountered the following fact:Let G be a d-regular graph with adjacency eigenvalues       λ    1    ≥  .  .  .  ≥      λ    n  . Then its complement graph             G      ¯       has eigenvalues   n  −  1  −      λ    1    ,  −  (      λ    2    +  1  )  ,  .  .  .  ,  −  (      λ    n    +  1  )The proof uses the fact that   A  (            G      ¯        )  =  J  −  A  (  G  )  −  I, where J is the matrix with all ones. So if vi is an eigenvector of       λ    i  , then   A  (            G      ¯        )      v    i    =  J      v    i    −  A  (  G  )      v    i    −      v    i  . If i=1, then since G is regular,       v    1   must be the vector of all ones, hence   J      v    1    =  n      v    1  But for i&amp;gt;1, then does the equation   A  (            G      ¯        )      v    i    =  J      v    i    −  A  (  G  )      v    i    −      v    i    =  J      v    i    −      λ    i        v    i    −      v    i    =  −  (      λ    i    +  1  )      v    i   imply that   J      v    i    =  0? If it does, then I can&#039;t see why it is true.

jennasyliang4tr · Accepted Answer

Yes,   J      v    i    =  0 for all i&amp;gt;1. This is because, the matrix of 1s has only one nonzero eigenvalue, n. Thus, since we have already covered its eigenvalue in       v    i  , and since a symmetric matrix has all independent eigenvectors, which are orthogonal to each other, therefore the vectors       v    i   for i&amp;gt;1 are in the null space of   A  (      G    ¯    ), whence   J      v    i    =  0

Eigenvalues of complement of regular graphs So I have encountered the following fact: Let G be a d-regular graph with adjacency eigenvalues lambda1>=...>=lambdan. Then its complement graph bar G has eigenvalues n−1−lambda1,−(lambda2+1),...,−(lambdan+1).

Answered question

Answer & Explanation

New Questions in Descriptive Statistics