67
$\begingroup$

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.

$\endgroup$
4
  • 15
    $\begingroup$ What did he say when you asked him? $\endgroup$ Jan 30, 2018 at 22:15
  • 9
    $\begingroup$ I second @MatthewLeingang advice. I have had the chance to see some successful mathematicians, at talks or meetings. All of them never hesitate to pose a question when something is not clear, without worrying if the question may be perceived as stupid. $\endgroup$ Jan 31, 2018 at 9:54
  • $\begingroup$ Do Hankel matrices diagonalize nicely? $\endgroup$ Feb 2, 2018 at 2:26
  • $\begingroup$ So how's your jam preparation going on ? $\endgroup$
    – Daman
    Feb 8, 2018 at 16:02

11 Answers 11

49
$\begingroup$

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.

$\endgroup$
42
$\begingroup$

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.

$\endgroup$
5
  • 23
    $\begingroup$ Even quicker: since all the rows sum to $21$ and all entries are positive, the dominant eigenvalue is $21$ by the same Perron-Frobenius theorem. $\endgroup$ Jan 30, 2018 at 17:18
  • 5
    $\begingroup$ @CloudJR: links added to the answer. The easiest way in this case is just to recall a classical and central result. $\endgroup$ Jan 30, 2018 at 17:22
  • 52
    $\begingroup$ @CloudJR Just because you’re learning elementary linear algebra doesn’t mean your professor couldn’t have used more advanced tricks. $\endgroup$ Jan 30, 2018 at 17:39
  • 3
    $\begingroup$ @CloudJR: The gist of what Jack is telling you is this: Your square matrix has nonnegative entries and has all column and row sums equal. Then the largest eigenvalue is that sum. Such matrices have important applications (e.g. Google's Page Rank algorithm). $\endgroup$
    – hardmath
    Feb 2, 2018 at 1:37
  • $\begingroup$ @JackD'Aurizio I am fan of yours. $\endgroup$
    – Daman
    Feb 8, 2018 at 16:04
25
$\begingroup$

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$

$\endgroup$
3
  • 3
    $\begingroup$ Nice, but the $3969$ is not so easy to find "mentally". So it would be nice with another "quick" argument that the remaining two eigenvalues do not exceed $21$ in absolute value. $\endgroup$ Jan 31, 2018 at 16:53
  • 1
    $\begingroup$ The OP said that they already had the characteristic equation. So, that was not the problem in this case. $\endgroup$
    – Doug M
    Jan 31, 2018 at 16:58
  • $\begingroup$ The first row (1,4,16) seems to be cyclically permuted to obtain the second and third rows. Is this true in general? If the entries are all positive integers, and you cyclically permute the first row to get the second and third, will the sum of the terms in the first row be the largest eigenvalue? Maybe he knew this fact and realized right away? I am just guessing here!! $\endgroup$
    – student
    Feb 7, 2018 at 5:12
11
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ The above is true for matrices with non negative entries. If the matrix contain negative elements the above result is not true. $\endgroup$
    – SKarantha
    Apr 21, 2018 at 4:51
10
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Great answer. I suspect that this is the mental technique used by the professor (see OP). $\endgroup$ Jan 31, 2018 at 18:39
6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Great idea, but this only gives that $\lambda_1=21$ and $\lambda_2=-\lambda_3$. How can you rule out that, for example, $\lambda_2=1000, \lambda_3=-1000$? $\endgroup$ Jan 31, 2018 at 9:50
  • $\begingroup$ That's what i explained, you can make a quick calculus of $\text{det}\left(A\right)$ $\endgroup$
    – Atmos
    Jan 31, 2018 at 12:21
  • 1
    $\begingroup$ And is there a way to compute $\det A$ quickly? Actually it would be enough to prove that $\det A <(21)^3$. This bound could be provided by Hadamard's inequality, but I have not checked. (I suspect that my objection is exactly the same as Joonas Ilmavirta's one.) $\endgroup$ Jan 31, 2018 at 12:28
  • $\begingroup$ The procedure of using the trace combined with the inequality $\det A<(21)^3$ is the one given in Doug M's answer. I think that the downside of this procedure is that it does not give a quick way of computing $\det A$. $\endgroup$ Jan 31, 2018 at 12:38
  • 1
    $\begingroup$ @GiuseppeNegro I agree, and your suspicion is quite accurate. The determinant gives indeed a way to bound the other eigenvalues, but that requires an estimation of $\det(A)$ or $\sqrt{\det(A)/21}$ or some such thing. I'm not convinced that's easy to do mentally. $\endgroup$ Feb 1, 2018 at 16:14
3
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Yes of course.. The trace is 21. So the sum of the eigenvalues is 21. From that how can I conclude the largest value. $\endgroup$
    – Cloud JR K
    Jan 30, 2018 at 17:20
  • 1
    $\begingroup$ @CloudJR Note that since the rows are just permutations of each other, $(1,1,1)$ is an eigenvector. What eigenvalue does that eigenvector have..? $\endgroup$ Jan 30, 2018 at 17:26
  • 13
    $\begingroup$ @CameronWilliams That does indeed show that 21 is an eigenvalue, and the trace shows that they sum to 21. But what guarantees that the other two eigenvalues are not $\pm25$? I would guess it is, but I can't intuitively or quickly see that that's indeed the case. $\endgroup$ Jan 30, 2018 at 20:26
  • 1
    $\begingroup$ @JoonasIlmavirta Oh true! Silly me. $\endgroup$ Jan 31, 2018 at 1:18
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ No, it's not circulant (at least with the standard definition). $\endgroup$ Jan 30, 2018 at 21:37
  • $\begingroup$ @FedericoPoloni : Yep you are right. But it shares some similarities with it. $\endgroup$ Jan 30, 2018 at 21:52
  • $\begingroup$ I wonder if these aren't Hartley basis functions. $\endgroup$ Jan 30, 2018 at 21:58
  • 2
    $\begingroup$ @FedericoPoloni new question if you are curious: math.stackexchange.com/questions/2628822/… $\endgroup$ Jan 30, 2018 at 22:30
  • 1
    $\begingroup$ With minor modifications this argument works. The matrix in question is anti-circulant rather than circulant. See this question for a completion of the desired argument: math.stackexchange.com/questions/2514187/… $\endgroup$
    – Yly
    Feb 2, 2018 at 5:17

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.