What is the largest eigenvalue of the following matrix?

Question

Find the largest eigenvalue of the following matrix $$\begin{bmatrix} 1 & 4 & 16\\ 4 & 16 & 1\\ 16 & 1 & 4 \end{bmatrix}$$

This matrix is symmetric and, thus, the eigenvalues are real. I solved for the possible eigenvalues and, fortunately, I found that the answer is $21$.

My approach:

The determinant on simplification leads to the following third degree polynomial. $$\begin{vmatrix} 1-\lambda & 4 &16\\ 4 &16-\lambda&1\\ 16&1&4-\lambda \end{vmatrix} = \lambda^3-21\lambda^2-189\lambda+3969.$$

At a first glance seen how many people find the roots of this polynomial with pen and paper using elementary algebra. I managed to find the roots and they are $21$, $\sqrt{189}$, and $-\sqrt{189}$ and the largest value is $21$.

Now the problem is that my professor stared at this matrix for a few seconds and said that the largest eigenvalue is $21$. Obviously, he hadn't gone through all these steps to find that answer. So what enabled him answer this in a few seconds? Please don't say that he already knew the answer.

Is there any easy way to find the answer in a few seconds? What property of this matrix makes it easy to compute that answer?

Thanks in advance.

Answer 1

Requested by @Federico Poloni:

Let $A$ be a matrix with positive entries, then from the Perron-Frobenius theorem it follows that the dominant eigenvalue (i.e. the largest one) is bounded between the lowest sum of a row and the biggest sum of a row. Since in this case both are equal to $21$, so must the eigenvalue.

In short: since the matrix has positive entries and all rows sum to $21$, the largest eigenvalue must be $21$ too.

Answer 2

The trick is that $\frac1{21}$ of your matrix is a doubly stochastic matrix with positive entries, hence the bound of 21 for the largest eigenvalue is a straightforward consequence of the Perron-Frobenius theorem.

Answer 3

If you sum the row, all the rows they to the same number (21).

That indicates that $\begin {bmatrix} 1\\1\\1 \end{bmatrix}$ must be an eigenvector and 21 is the associated eigenvalue.

The trace of the matrix equal 21, and the sum of the eigenvalues equals the trace.

The remaining two eigenvalues are the negative of one another.

And $3969 < 21^3$ so the other absolute value of the other two eigenvalues are each less than $21$

Answer 4

I believe there is a more elementary argument that has not yet been mentioned.

Claim: If $A$ is an $n$-by-$n$ matrix with nonnegative entries and all row sums equal to $r$, then the largest eigenvalue of $A$ (in absolute value) is $r$.

Proof: As has been noted, the all-$1$s vector is an eigenvector of $A$ with eigenvalue $r$. Conversely, let $x=(x_1,\ldots,x_n)^T$ be an eigenvector of $A$ with eigenvalue $\lambda$. Let $x_i$ be (an) element of largest absolute value, and by scaling by $-1$, we may assume that $x_i>0$ without loss of generality. Now the $i$-th component of $Ax$ is $\lambda x_i$, and its absolute value satisfies $$|\lambda|x_i=|(Ax)_i|=|\sum_{j=1}^nA_{ij}x_j|\leq\sum_{j=1}^n|A_{ij}||x_j|\leq\sum_{j=1}^nA_{ij}x_i=x_i\sum_{j=1}^nA_{ij}=rx_i,$$ so $|\lambda|\leq r$.

Answer 5

This is based on the other answers that suggested the use of the trace. The first part of this answer is actually already contained in Doug M and Atmos's answers, but I'll reproduce it here to ease reading.

Letting $\lambda_1, \lambda_2, \lambda_3$ denote the eigenvalues of $A$ we know by the structure of the matrix that $\lambda_1 = \mathrm{tr}(A)=21$ is an eigenvalue (with eigenvector $(1,1,1)$). Moreover, since $$\lambda_1 + \lambda_2 + \lambda_3=\mathrm{tr}(A),$$ it must be that $\lambda_2=-\lambda_3$. Finally, since $$ 21\lambda_2^2=|\lambda_1\lambda_2\lambda_3|=|\det A|, $$ to conclude the proof that $\lambda_1 > |\lambda_2|$ it suffices to show that $$\tag{*}(\det A)^2 < (21)^6.$$

We can prove (*) quickly by using Hadamard's inequality: $$ (\det A)^2\le \prod_{i=1}^3\sum_{j=1}^3 a_{i{}j}^2,$$which in our case simplifies to $$(\det A)^2 \le (1+16+16^2)^3,$$so it remains to prove that $1+16+16^2<21^2$, which can be done quickly by rewriting it as $$17<21^2-16^2=(21-16)(21+16)=5\cdot 37,$$that is manifestly true.

The advantage of the use of Hadamard's inequality over the computation of $\det(A)$ is that it exploits the structure of the matrix, simplifying computations a bit. One might even be able to carry out these computations mentally (I sure cannot, I must say).

Answer 6

Since all of the rows of your matrix sum to $21$, $21$ is an eigenvalue with corresponding eigenvector $[1,1,1]^T$, and you only need to show that your matrix has no larger eigenvalue.

One method for estimating the eigenvalues of a matrix is the Gershgorin circle theorem. This theorem states that for any matrix square $A = [a_{ij}]_{1\le i,j\le n}$, the eigenvalues of $A$ lie in the disks $$D_i = \{\lambda: |\lambda - a_{ii}| \le \sum_{j\neq i} |a_{ij}|\}$$ (that is, $D_i$ is centered at the $i$th diagonal entry of $A$ and has a radius equal to the sum of absolute values of the off-diagonal entries in the $i$th row of $A$).

Applied to your matrix, the theorem shows that all the eigenvalues of $A$ must lie in the disks $$D_1 = \{\lambda : |\lambda - 1| \le 20\}$$ $$D_2 = \{\lambda : |\lambda - 16| \le 5\}$$ $$D_3 = \{\lambda : |\lambda - 4| \le 17\}$$ since none of these disks contain any real numbers larger than $21$, $\lambda = 21$ is the largest eigenvalue of your matrix.

---

You mention that you are in an introductory linear algebra class. The Gershgorin cirlce theorem is not commonly taught in introductory classes, but it certainly could be. I'd encourage you to check out the proof in the link I gave above: it's entirely elementary.

Answer 7

In fact if $\lambda_1, \lambda_2$ and $\lambda_3$ are the three eigen values of your matrix, the trace of your matrix ( sum of diagonal terms ) equals to $\lambda_1+\lambda_2+\lambda_3$. With your matrix, it is obvious with $(1,1,1)$ to obtain that $21$ is an eigenvalue. The trace equals to $21$ this means that other values are $0$ or opposite.

If he quickly evaluated the determinant, it equals to $\lambda_1\lambda_2\lambda_3=\text{det}\left(A\right)$ then you see it is the greater one.

Answer 8

Hint: Have a look at $Tr(A)$, the trace of your matrix

Answer 9

Here's a variant that doesn't require to calculate the determinant.

First, as others already said, you get that $21$ is an eigenvalue because all rows add up to it. And because the trace is also $21$, the other two eigenvalues add up to $0$, thus are of equal absolute value.

Now is its easily seen that $\operatorname{tr}(A^2) = 3\cdot(1^2+4^2+16^2)$ and you need not even calculate that value to see that it certainly is less than $3\cdot 21^2$. Thus the other two eigenvalues must be less than $21$.

Those considerations are simple enough to do them quickly in the head.

Answer 10

Perron-Frobenius is hardly (if ever) mentioned in undergraduate linear algebra courses. A more elementary solution is to notice that, since all rows have the same sum, [1,1,1]^t is an eigenvector, associated to the eigenvalue 21 (=1+4+16). Now, trace = 21 and determinant = -3969, so that the other two eigevalues (let's call them x and y) satisfy: x + y = 0 and xy = -3969/21 = -189 ==> x = -y ~ 13.75. Conclusion: the largest eigenvalue is 21.

Answer 11

EDIT: This answer is wrong, but at least the follow up can maybe help give some deeper understanding of these kinds of matrices (which have properties which seem quite related to circulant matrices).

---

Another trick is that the matrix is a circulant matrix and therefore has eigenspectrum equal to the complex exponentials of frequencies multiple of one third. So you know that the lowest frequency complex exponential ( the constant [1,1,1] ) must be an eigenvector. You can calculate it's eigenvalue and then deflate the matrix and then based on your results you can easily conclude it must have been the biggest one you managed to extract.