3
$\begingroup$

Using the following command in MATLAB, I am finding out that the eigenvalues of a complete graph are $-1$ with the multiplicity $n-1$ and $n-1$ with multiplicity of $1$. However I believe that the eigenvalues of $K_n$ should be zero with multiplicity $1$ and $n$ with multiplicity $n-1$. To make matters worse I have just noted that the determinant of the adjacency matrix of a complete graph with n vectors is $(-1)^{n-1}(n-1)$ which also mean my belief is also not correct.

n = 6;
i = 1;
while (i <= n)
    i = i + 1;
    M = ones(i) - eye(i);
    [v, d] = eig(M)
end

How can I determine the spectrum of a complete graph analytically?

$\endgroup$
  • $\begingroup$ Related and gives the answer math.stackexchange.com/questions/957126/… $\endgroup$ – Bertrand R Sep 5 '15 at 13:21
  • $\begingroup$ @BertrandR, the user [ math.stackexchange.com/questions/957126/… has asked how one can show that $K_n$ is uniquely determined by its spectrum. But I want a method of finding that spectrum using a proof. Please, help in that area. $\endgroup$ – Patrick Chidzalo Sep 5 '15 at 13:31
  • $\begingroup$ Should be eigenvalue $n-1$ with multiplicity $1$, not eigenvalue $n$ (since the graph $K_{n}$ is $(n-1)$-regular. It does not have $0$ as an eigenvalue because the matrix is nonsingular (remember it has $0$ on the diagonal; this also shows that $A+I$ has rank 1, giving $-1$ as an eigenvalue with multiplicity $n-1$). $\endgroup$ – Morgan Rodgers Sep 5 '15 at 16:21
  • 1
    $\begingroup$ Hint: Verify that the all-ones vector is an eigenvector, and also the vector $e_{i} - e_{j}$ for $i \neq j$ (where $e_{i}$ is the vector with a $1$ in position $i$ and $0$ everywhere else). What are the eigenvalues? What are the dimensions of the spaces spanned by these vectors? $\endgroup$ – Morgan Rodgers Sep 5 '15 at 16:58
  • $\begingroup$ I will make such corrections @MorganRodgers. $\endgroup$ – Patrick Chidzalo Sep 5 '15 at 17:01
7
$\begingroup$

The eigenvalues should be $n-1$, with multiplicity $1$, and $-1$, with multiplicity $n-1$. The best way to see this in this particular case is through explicitly giving the eigenvectors.

First, the graph $K_{n}$ is $(n-1)$-regular; a $k$-regular graph always has $k$ as an eigenvalue with eigenvector $j$ (the all-ones vector). All other eigenvectors will have to be orthogonal to $j$.

To find the other eigenvectors, consider the adjacency matrix $A$ of $K_{n}$; it is all $1$s, except with $0$ on the diagonal. If we consider $A+I$, we get the all-ones matrix, which has rank $1$ (and so its null space has dimension $n-1$, giving $n-1$ linearly independent eigenvectors for the eigenvalue $-1$). These vectors all take the form $e_{i}-e_{j}$ for $i \neq j$ (where $e_{i}$ represents the vector with a $1$ in position $i$ and a $0$ everywhere else). We can find $n-1$ linearly independent vectors of this type, it is easiest to just consider $e_{1} - e_{j}$ for $0 < j \leq n$.

$\endgroup$
  • 1
    $\begingroup$ Thanks @MorganRodgers, I find this solution to be useful. $\endgroup$ – Patrick Chidzalo Sep 6 '15 at 9:04
  • $\begingroup$ No problem, glad to help! $\endgroup$ – Morgan Rodgers Sep 6 '15 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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