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

Question

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?

Answer 1

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.

Answer 2

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$

Answer 3

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$.

Answer 4

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\}$$