60
$\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$
  • 12
    $\begingroup$ What did he say when you asked him? $\endgroup$ – Matthew Leingang Jan 30 '18 at 22:15
  • 8
    $\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$ – Giuseppe Negro Jan 31 '18 at 9:54
  • $\begingroup$ Do Hankel matrices diagonalize nicely? $\endgroup$ – Cosmas Zachos Feb 2 '18 at 2:26
  • $\begingroup$ So how's your jam preparation going on ? $\endgroup$ – Daman deep Feb 8 '18 at 16:02

11 Answers 11

32
$\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$
43
$\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$
  • 6
    $\begingroup$ Sir. I don't know what these means. I am learning elementary linear algebra. That's why I asked for an easy way. But anyhow thanks for your answer. $\endgroup$ – Cloud JR Jan 30 '18 at 17:17
  • 22
    $\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$ – Nigel Overmars Jan 30 '18 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$ – Jack D'Aurizio Jan 30 '18 at 17:22
  • 51
    $\begingroup$ @CloudJR Just because you’re learning elementary linear algebra doesn’t mean your professor couldn’t have used more advanced tricks. $\endgroup$ – Chase Ryan Taylor Jan 30 '18 at 17:39
  • 2
    $\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 '18 at 1:37
19
$\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
    $\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$ – Jeppe Stig Nielsen Jan 31 '18 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 '18 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 '18 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$
  • $\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 '18 at 4:51
9
$\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$
7
$\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$
  • $\begingroup$ Great answer. I suspect that this is the mental technique used by the professor (see OP). $\endgroup$ – Giuseppe Negro Jan 31 '18 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$
  • $\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$ – Giuseppe Negro Jan 31 '18 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 '18 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$ – Giuseppe Negro Jan 31 '18 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$ – Giuseppe Negro Jan 31 '18 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$ – Joonas Ilmavirta Feb 1 '18 at 16:14
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$
2
$\begingroup$

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

$\endgroup$
  • $\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 Jan 30 '18 at 17:20
  • $\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$ – Cameron Williams Jan 30 '18 at 17:26
  • 12
    $\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$ – Joonas Ilmavirta Jan 30 '18 at 20:26
  • $\begingroup$ @JoonasIlmavirta Oh true! Silly me. $\endgroup$ – Cameron Williams Jan 31 '18 at 1:18
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$
  • $\begingroup$ No, it's not circulant (at least with the standard definition). $\endgroup$ – Federico Poloni Jan 30 '18 at 21:37
  • $\begingroup$ @FedericoPoloni : Yep you are right. But it shares some similarities with it. $\endgroup$ – mathreadler Jan 30 '18 at 21:52
  • $\begingroup$ I wonder if these aren't Hartley basis functions. $\endgroup$ – mathreadler Jan 30 '18 at 21:58
  • 2
    $\begingroup$ @FedericoPoloni new question if you are curious: math.stackexchange.com/questions/2628822/… $\endgroup$ – mathreadler Jan 30 '18 at 22:30
  • $\begingroup$ Why leave a wrong answer instead of deleting it or removing the wrong part? $\endgroup$ – Ruslan Feb 1 '18 at 19:47
0
$\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$

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.