# Computing the eigenvalues of $\mathbb{1}-I$

Let $A=\mathbb{1}-I \in \{0,1\}^{n \times n}$, the matrix having 0 in the diagonal and 1 everywhere else. To compute the eigenvalues I tried to compute the characteristic polynomial using recursion, but this turns out to be quite complicated, I think.

Is there some easier approach for finding the eigenvalues of such easy matrices? Maybe some guessing strategy?

And how, if we only have guessed some eigenvalues, do we know the (geometric) multiplicity of it?

Are there some easy tricks?

• This is easy if you know all the eigenvalues and eigenvectors of $\Bbb 1$. – Omnomnomnom Jul 20 '15 at 13:24
• See 5xum's answer below for "how to deal with $I$". Another way to think about it is to note that every vector is an eigenvector of $I$, so $\Bbb 1 - I$ will have the same eigenvectors as $\Bbb 1$. – Omnomnomnom Jul 20 '15 at 13:34
• As for how to deal with $\Bbb 1$... note that $\Bbb 1$ is a rank 1 matrix. What can you say about a matrix whose rank is $1$? – Omnomnomnom Jul 20 '15 at 13:35
• That's about the sum of it. The fact that 5xum mentions holds for any multiple of the identity too: for a matrix $A$ and constant $\mu$, if $\lambda$ is an eigenvalue of $A$ with eigenvector $x$, then $\lambda + \mu$ is an eigenvalue of $A + \mu I$ with the same eigenvector $x$. – Omnomnomnom Jul 20 '15 at 13:47
• Yep. Note that since $\mu$ can be negative (or anything really), the forward statement implies its own converse. – Omnomnomnom Jul 20 '15 at 13:54

Observe that the rank of the matrix $\mathbb{1}$ is $1$. Therefore, it has one nonzero eigenvalue and $n-1$ zero eigenvalues. The nonzero eigenvalue is $n$ corresponding to the vector of ones. The remaining eigenvector corresponds to $e_1-e_i$ (for $i=2,\dots,n$).

Now, use @5xum 's answer to compute the eigenvalues.

The main thing you need to use is:

For any matrix $A$, $Ax = \lambda x$ is true if and only if $(A-I)x = (\lambda - 1)x$

Let $z$ denote the vector consisting of only $1$s. We can write $A$ as $$A = zz^T - I$$ In particular, $$Ax = zz^Tx - Ix = \langle z,x \rangle z - x$$

Now, consider two cases: first, suppose that $x=z$. We then have $$Ax = Az = \langle z,z \rangle z - z = (\langle z,z \rangle - 1)z$$ Next, suppose $x$ is perpendicular to $z$. We then have $$Ax = \langle z,x \rangle z - x = -x$$ We may use this information to get a basis of eigenvectors, and deduce that the eigenvalues are $-1$ and $\|z^2\| - 1$.

• This is the one and only elegant solution here. No explicit components and chosen coordinate frames, not even an explicit dimensionality, just the symmetry-preserving information about the matrix. – orion Jul 20 '15 at 13:34

You can do it "by hand" here :

You have that

$$(Ax)_i = \left( \sum_{k=1}^n x_k\right) - x_i$$

So if $x$ is an eigenvector with eigenvalue $\lambda_x$, this imply that

$$\forall i \in [|1,n|], \left( \sum_{k=1}^n x_k\right) = (\lambda_x+1) x_i$$

• if $\lambda_x \neq -1$

$$\forall i \in [|1,n|], x_i = \frac{\left( \sum_{k=1}^n x_k\right)}{\lambda_x+1}$$

This imply that

$x_1 = x_2 = x_3 = \cdots = x_n$

And $\lambda_x = n-1$

• if $\lambda_x = -1$, this imply that

$$\sum_{k=1}^n x_k = 0$$

So

$$x \in \{ (x_1, x_2, \cdots, x_{n-1} , - \sum_{k=1}^{n-1} x_k ) \}$$

Or

$$x \in \text{Span} \left\{ e_1-e_n, e_2-e_n, \cdots, e_{n-1}-e_n \right\}$$