17
$\begingroup$

Show that $0,2,4$ are the eigenvalues for the matrix $A$: $$A=\pmatrix{ 2 & -1 & -1 & 0 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ 0 & -1 & -1 & 2 \\ }$$ and conclude that $0,2,4$ are the only eigenvalues for $A$.


I know that you can find the eigenvalues by finding the $\det(A-\lambda \cdot I)$, but it seems to me that the computation will be rather difficult to compute as it is a $4 \times 4$ matrix.

My question: is there an easier method to calculate the eigenvalues of $A$? And if I have to conclude that these are the only eigenvalues, is there a theorem that argues how many eigenvalues a matrix can have?

$\endgroup$
  • 9
    $\begingroup$ The sum of all eigenvalues is the trace, so if you have three of them, the last comes for free. $\endgroup$ – Lord Shark the Unknown Apr 27 '18 at 10:30
  • 1
    $\begingroup$ I can't see any easy method. I think you have to plow through the calculations. The only obvious one is $0$ because it is the sum of each row. Because it is a symmetric matrix, you also know the eigenvalues are real numbers. Finally the Gershgorin Circle Theorem allows you to bound them, but not is any sufficiently useful way. $\endgroup$ – Git Gud Apr 27 '18 at 10:39
  • 1
    $\begingroup$ sum of each row is zero, so zero is one eigenvalue( with $(1,1,...,1)^t$ as an eigenvector) $\endgroup$ – Chinnapparaj R Apr 27 '18 at 10:53
23
$\begingroup$

$A$ has zero row sums. Therefore the all-one vector $\mathbf e$ is an eigenvector of $A$ for the eigenvalue $0$. Since $A$ is also real symmetric, $\mathbf e$ can be extended to an orthogonal eigenbasis $\{\mathbf u,\mathbf v,\mathbf w,\mathbf e\}$ of $A$. But this is also an eigenbasis of $A+\mathbf e\mathbf e^\top$. Hence the spectrum of $A$ is $\{a,b,c,0\}$ if and only if the spectrum of $A+\mathbf e\mathbf e^\top$ is $\{a,b,c,\|\mathbf e\|^2\}=\{a,b,c,4\}$. It is easy to see that four eigenvalues of $$ A+\mathbf e\mathbf e^\top=\pmatrix{3&0&0&1\\ 0&4&0&0\\ 0&0&4&0\\ 1&0&0&3} $$ are $2,4,4,4$. Therefore the eigenvalues of $A$ are $2,4,4,0$.

$\endgroup$
  • $\begingroup$ Why is it that $\text{spec}(A)=\{0, a, b, c\}\implies \text{spec}(A+\mathbf e\mathbf e^\top)=\{a, b, c, 4\}$? $\endgroup$ – Git Gud Apr 27 '18 at 11:15
  • 1
    $\begingroup$ @GitGud Since $Av=av$ for some $v\perp\mathbf e$, we also have $(A+\mathbf e\mathbf e^\top)v=av$. Similarly for $b$ and $c$. Finally, $(A+\mathbf e\mathbf e^\top)\mathbf e=(\mathbf e^\top\mathbf e)\mathbf e=4\mathbf e$. $\endgroup$ – user1551 Apr 27 '18 at 11:18
  • $\begingroup$ Ohhhhh. Thanks. $\endgroup$ – Git Gud Apr 27 '18 at 11:21
15
$\begingroup$

It helps to notice that this matrix comes from a graph. It is the so called Laplacian of a graph. Notice the position of $-1$'s. If you take four points and join the $i$th and $j$th if there is a $-1$ at position $(i,j)$ you get a graph. It's fairly symmetric: its edges are the sides of a square and one diagonal. Consider different ways to associate a number to the vertices of the square. From one such distribution of numbers, you can produce another distribution as follows: at each vertex, the new number will be (old number) x (degree of the vertex) - (sum of numbers associated to the vertices that are joined with this one).

It may happen that the new distribution of numbers is proportional to the old one. So the old distribution is an eigenvector, and the constant of proportionality is an eigenvalue.

Suppose that you start with a distribution with all numbers equal ( say $1$). Then the new distribution is $0$ everywhere. So we got an eigenvector with eigenvalue $0$

Say we place $1$ at the ends of the (joined ) diagonal, and $-1$ at the other two points. Check that we get an eigenvector for eigenvalue $4$.

enter image description here

Say we place $1$, $-1$ at the diagonal, $0$, $0$ at the others. Check that we get an eigenvector with eigenvalue $4$.

Say we place $0$ at the diagonal, $-1$, $1$ at the other points. Check that we get eigenvector with eigenvalue $2$.

Note that this is a small example where it can be done by hand.

$\endgroup$
  • $\begingroup$ I'm not going to bother with understanding your answer, but this really doesn't feel like an easier method. $\endgroup$ – Git Gud Apr 27 '18 at 11:03
  • 1
    $\begingroup$ @Git Gud: I added a picture, that might help. $\endgroup$ – Orest Bucicovschi Apr 27 '18 at 11:43
  • $\begingroup$ Nice observation on this being the Laplacian of a graph. I think two more observations allow the eigenvalues to be determined exactly without simulating node distributions (see my answer). $\endgroup$ – Jared Goguen Apr 27 '18 at 18:54
  • $\begingroup$ @Jared Goguen: Thanks. Super info your answer! $\endgroup$ – Orest Bucicovschi Apr 27 '18 at 22:57
12
$\begingroup$
  1. $\lambda=2$ is obviously an eigenvalue: look at the first and the last columns of $A-2I$.
  2. $\lambda=0$ is also en eigenvalue: sum up all the columns of $A$ (dependent?).
  3. Try to do similar trick for $\lambda=4$.
  4. The last eigenvalue: The sum of all eigenvalues is the trace, so if you have three of them, the last comes for free.(c) comment by Lord Shark the Unknown.

EDIT: If a calculation of eigenvalues is of your primal curiosity then you can do the following: \begin{align} \det(\lambda I-A)&=\begin{vmatrix}\lambda-2 & 1 & 1 & 0\\1 & \lambda-3 & 1 & 1\\1 & 1 & \lambda-3 & 1\\0 & 1 & 1 & \lambda-2\end{vmatrix}\stackrel{(1)}{=} \begin{vmatrix}\lambda & 1 & 1 & 0\\\lambda & \lambda-3 & 1 & 1\\\lambda & 1 & \lambda-3 & 1\\\lambda & 1 & 1 & \lambda-2\end{vmatrix}\\ &\stackrel{(2)}{=}\lambda\begin{vmatrix}1 & 1 & 1 & 0\\1 & \lambda-3 & 1 & 1\\1 & 1 & \lambda-3 & 1\\1 & 1 & 1 & \lambda-2\end{vmatrix}\stackrel{(3)}{=} \lambda\begin{vmatrix}1 & 1 & 1 & 0\\0 & \lambda-4 & 0 & 1\\0 & 0 & \lambda-4 & 1\\0 & 0 & 0 & \lambda-2\end{vmatrix}. \end{align} Explanations:

(1): add all columns to the first one,

(2): factor out $\lambda$ in the first column,

(3): eliminate in the first column.

$\endgroup$
  • 2
    $\begingroup$ Sure, $2$ is obviously an eigenvalue if you look at $A-2I$, but why would you ever look at that matrix? $\endgroup$ – Git Gud Apr 27 '18 at 10:57
  • 2
    $\begingroup$ @GitGud the question asks to prove that $0,2,4$ are the eigenvalues of the matrix, So it makes sense to consider $A-2I$ and prove it is singular. $\endgroup$ – idok Apr 27 '18 at 11:05
  • 2
    $\begingroup$ @GitGud The problem says "Show that given numbers are eigenvalues". If it were "Find the eigenvalues..." then I would agree with your comment. $\endgroup$ – A.Γ. Apr 27 '18 at 11:06
  • 2
    $\begingroup$ No, that's not the OP's question. That the problem statement question. The OP is asking how to find the eigenvalues easily: "My question: is there an easier method to calculate the eigenvalues of $A$?" @idok $\endgroup$ – Git Gud Apr 27 '18 at 11:10
  • 2
    $\begingroup$ @GitGud: if you assume this could be a special case, it is reasonable to ask yourself which $\lambda$ might make two of the rows or two of the columns of $A-\lambda I$ equal to each other. And it is not difficult to spot that $2$ and $4$ do this $\endgroup$ – Henry Apr 27 '18 at 15:39
9
$\begingroup$

Perhaps there is no easier way of explaining how to find the eigenvalues of $A$. At the end, it all comes down to how much you are familiar with matrices that have some special properties. I’m using the very same insight as orangeskid but explained in a different way.

Consider this matrix: $$\color{red}{L=\left[\begin{array}{r} 1&-1\\ -1&1 \end{array}\right]}$$ which has eigenvalues $\color{red}{0}$ and $\color{red}{2}$. Now consider this bigger matrix $$M=\left[\begin{array}{r|rr|r} \color{red}{1}&0&0&\color{red}{-1}\\ \hline 0&\color{blue}{0}&\color{blue}{0}&0\\ 0&\color{blue}{0}&\color{blue}{0}&0\\ \hline \color{red}{-1}&0&0&\color{red}{1} \end{array}\right]$$ which is blockwise similar to the latter, and has eigenvalues $\color{blue}{0}$, $\color{blue}{0}$, $\color{red}{0}$ and $\color{red}{2}$ (the former two because of the $\color{blue}{2\times2}$ $\color{blue}{\text{zero matrix in the middle}}$; the latter two because of reusing $\color{red}{\text{the entries of the smaller matrix in the same fashion}}$.)

Now consider this matrix $$\color{purple}{K=\left[\begin{array}{r} 3&-1&-1&-1\\ -1&3&-1&-1\\ -1&-1&3&-1\\ -1&-1&-1&3\\ \end{array}\right]}$$ which is of the form $\color{purple}{4 \, I_4 -\boldsymbol{1}^{\rm T}_4 \boldsymbol{1}_4}$ and has eigenvalues $\color{purple}{0}$, $\color{purple}{4}$, $\color{purple}{4}$ and $\color{purple}{4}$. Now note that all matrices $L$, $M$, $A$ and $K$ are Laplacian matrices corresponding to undirected, unweighted simple graphs, and since $$M+A=K,$$ there is a result for Laplacian matrices that relates the sorted eigenvalues of $M$ and $A$ with those of $K$. For starters, the first eigenvalue of $A$ is $\bbox[yellow]{0}$. Then, the other three eigenvalues of $A$ are computed in the following fashion:

Take the eigenvalues of $K$ and remove a zero. Take the decreasingly sorted eigenvalues of $M$ and remove a zero. Then their difference gives the eigenvalues of $A$ other that the first zero eigenvalue we mentioned.

Thus, $$\color{purple}{4}-\color{red}{2}=\bbox[yellow]{2}, \qquad\qquad \color{purple}{4}-\color{red}{0}=\bbox[yellow]{4}, \qquad\qquad \text{and } \color{purple}{4}-\color{blue}{0}=\bbox[yellow]{4},$$ are the other three eigenvalues of $A$.

$\endgroup$
8
$\begingroup$

You would be correct about the determinant method of finding the eigenvalues being potentially difficult since the degree is 4 (though in this case where the roots are rational, they can be found easily).

But note that finding the eigenvalues is NOT what you've been asked to do. You are given three of them, and have only to verify that they are indeed eigenvalues. Simply compute the characteristic polynomial for each of the three values and show that it is $0$.

To show that they are the only eigenvalues, divide the characteristic polynomial by $x$, the result by $x-2$, and finally by $x-4$. You will find that the remaining polynomial is another factor of $x-4$.

$\endgroup$
  • $\begingroup$ Instead of dividing the characteristic polynomial by $x$, $x-2$, and $x-4$, in succession, I would employ the trace, e.g $\DeclareMathOperator{\Tr}{Tr} \Tr(A) = \sum_i \lambda_i = 10$. From the three eigenvalues already found, it is then clear the last one must also be 4, too. $\endgroup$ – rcollyer Apr 28 '18 at 17:11
  • $\begingroup$ One could simply verify that $A(A-2I)(A-4I)=0$ and that omitting one factor yields a nonzero matrix. This confirms that the minimal polynomial of $A$ is $\lambda(\lambda-2)(\lambda-4)$ without having to compute invariants. As to multiplicity: $A$ is symmetric hence diagonalizable, therefore no multiple factors are needed. $\endgroup$ – ccorn Apr 28 '18 at 20:33
  • $\begingroup$ @rcollyer - that indeed would be easier, though with synthetic division, dividing the polynomials is not particularly hard. $\endgroup$ – Paul Sinclair Apr 29 '18 at 0:12
  • $\begingroup$ @ccorn - I haven't counted out the operations, but I am doubtful that multiplying 4x4 matrices four times is computationally easier than finding the characteristic polynomial. $\endgroup$ – Paul Sinclair Apr 29 '18 at 0:13
4
$\begingroup$

Let $ \lambda_1 \le \lambda_2 \le \lambda_3 \le \lambda_4 $ be the eigenvalues of this matrix.

Since this is a Laplacian matrix, the smallest eigenvalue is $\lambda_1 = 0$.

The second smallest eigenvalue of a Laplacian matrix is the algebraic connectivity of the graph. This is bounded above by the traditional connectivity of the graph, so $\lambda_2 \le 2$.

From the trace, $8 \le \lambda_3 + \lambda_4 \le 2\lambda_4 \rightarrow \lambda_4 \ge 4$.

From Brouwer and Haemers (2011) Proposition 3.9.3, $\lambda_4 \le 1 + \underset{x}{\rm{max}}\;d_x=4$.

Thus, $\lambda_2=2, \lambda_3=4, \lambda_4=4$.

$\endgroup$
2
$\begingroup$

You can easily guess some eigenvectors: $$ \begin{pmatrix} 2 & -1 & -1 & 0 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ 0 & -1 & -1 & 2 \end{pmatrix} \begin{pmatrix} 1\\1\\1\\1 \end{pmatrix} = \begin{pmatrix} 0\\0\\0\\0 \end{pmatrix} \\ \begin{pmatrix} 2 & -1 & -1 & 0 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ 0 & -1 & -1 & 2 \end{pmatrix} \begin{pmatrix} 1\\0\\0\\-1 \end{pmatrix} = \begin{pmatrix} 2\\0\\0\\-2 \end{pmatrix} \\ \begin{pmatrix} 2 & -1 & -1 & 0 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ 0 & -1 & -1 & 2 \end{pmatrix} \begin{pmatrix} 1\\-1\\-1\\1 \end{pmatrix} = \begin{pmatrix} 4\\-4\\-4\\4 \end{pmatrix} \\ \begin{pmatrix} 2 & -1 & -1 & 0 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ 0 & -1 & -1 & 2 \end{pmatrix} \begin{pmatrix} 0\\1\\-1\\0 \end{pmatrix} = \begin{pmatrix} 0\\4\\-4\\0 \end{pmatrix} $$ The corresponding eigenvalues are $0,2,4,4$. It is not hard to check that the latter two vectors are linearly independent, and so these are all eigenvalues of the matrix.

$\endgroup$
  • 1
    $\begingroup$ I'm not the original poster, but this doesn't seem to be much easier than solving the characteristic polynomial. $\endgroup$ – Alex Apr 27 '18 at 22:52

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.