30
$\begingroup$

A few years ago, I came up with this proof of Perron's theorem for a class presentation: http://www.math.cornell.edu/~web6720/Perron-Frobenius_Hannah%20Cairns.pdf

I've written an outline of it below so that you don't have to read a link.

It's close in spirit to Wielandt's proof using $$\rho := \sup_{\substack{x \ge 0\\|x| = 1}} \min_j {|{\sum x_i A_{ij}}| \over x_j},$$ but I think it's simpler. (In particular, you don't have to divide by anything or take the sup min of anything.) The exception is the part where you prove that the spectral radius has only one eigenvector, which is exactly the same as Wieland's proof.

I believe it's correct, but it hasn't passed through any kind of verification process aside from being presented in class. And I've had a couple people write me about it, and, for God knows what reason, it comes up on Google in the first couple pages if you search for "Perron-Frobenius."

So I'd appreciate it if you would look at this and see if you see anything wrong with it. And if you don't, I'd like to know if it's original, because if so then I get to feel proud of myself.

Here is the proof:

  • Let $A > 0$ be a positive $n \times n$ matrix with eigenvalues $\lambda_1, \ldots, \lambda_n$, counted with multiplicity. Let $\rho = \max |\lambda_i|$ be the spectral radius. We want to prove that $\rho$ is a simple eigenvalue of $A$ with a positive eigenvector, and that every other eigenvalue is strictly smaller in absolute value.

  • Let $\lambda$ be an eigenvalue with $|\lambda| = \rho$, and finally let $\psi$ an eigenvector for $\lambda$. Consider $$\Psi := |\psi| = (|\psi_1|, \ldots, |\psi_n|).$$ Then $A \Psi = A |\psi| \ge |A \psi| = |\lambda \psi| = \rho |\psi| = \rho \Psi$, where "$x \ge y$" means that each coordinate of $x$ is greater than or equal to each coordinate of $y$.

  • Suppose $A \Psi \ne \rho \Psi$. Then by positivity we have $A^2 \Psi > \rho A \Psi$, which means that by continuity there is some $\varepsilon > 0$ with $A^2 \Psi \ge (\rho + \varepsilon) A \Psi$. Therefore \begin{align*}A^{n+1} \Psi &\ge (\rho + \varepsilon) A^n \Psi \\&\cdots\\&\ge (\rho + \varepsilon)^n A \Psi \ge 0\end{align*} and taking norms we get $\Vert A^{n+1} \Psi \Vert_1 \ge (\rho + \varepsilon)^n \Vert A \Psi \Vert_1$, so the operator 1-norm of $A^n$ is at least $(\rho + \varepsilon)^n$, which is a contradiction with Gelfand's formula $\lim \Vert A^n \Vert^{1/n} = \rho$.

  • Therefore $A \Psi = \rho \Psi$ and $\rho$ is an eigenvalue with positive eigenvector $\rho \Psi = A \Psi > 0$.

  • Suppose there is an eigenvalue $\lambda$ with $|\lambda| = \rho$. Let $\psi$ be an eigenvector for $\lambda$. We have seen above that $A \Psi = \rho \Psi = |A \psi|$ or $\sum_j A_{ij} |\psi_j| = |\sum_{ij} A_{ij} \psi_j|$. Fix an index $i$. Then $A_{ij} > 0$ for each row $j$, so $\sum_{ij} A_{ij} \psi_j$ is a weighted sum of $\psi_j$ where all the weights are positive, and its absolute value is the weighted sum of $|\psi_j|$ with the same weights. Those two things can only be equal if all the summands $\psi_j$ all have the same complex argument, so $\psi = e^{i\theta} \psi'$ where $\psi' \ge 0$, and $\lambda \psi' = A \psi' > 0$, so $\lambda > 0$. Therefore $\lambda = \rho$.

  • Now we know that every eigenvalue with $|\lambda| = \rho$ is $\rho$, and it has one positive eigenvector (and possibly more), but we don't know how many times $\rho$ appears in the list of eigenvalues. That is, we don't know whether it's simple or not.

  • We can prove that $\rho$ has only one eigenvector by the same argument in Wielandt's proof. We know $\Psi$ is a positive eigenvector. Suppose that there is another linearly independent eigenvector $\psi$. We can pick $\psi$ to be real (because $\mathop{\rm Re} \psi$ and $\mathop{\rm Im} \psi$ are eigenvectors or zero and at least one is linearly independent of $\Psi$). Choose $c$ so $\Psi + c \psi$ is nonnegative and has one zero entry. Then $\rho (\Psi + c \psi) = A(\Psi + c \psi) > 0$ by positivity, but it has one zero entry, which is a contradiction. So there's no other linearly independent eigenvector.

  • Now that we know there's only one eigenvector, we can prove that $\rho$ is a simple eigenvalue. By the previous reasoning, there is a positive left eigenvector $\Pi$ of $\rho$, so $\Pi A = \rho A$. Then $\Pi > 0$ and $\Psi > 0$, so $\Pi \Psi \ne 0$. Then $\Pi^0 := \{x: \Pi x = 0\}$ is an $(n-1)$-dimensional subspace of $\mathbb R^n$ and $\Psi \notin \Pi^0$, so we can decompose $\mathbb R^n$ into the direct sum $$\mathbb R^n = \mathop{\text{span}}\{\Psi\} \oplus \Pi^0.$$

  • Both of these spaces are invariant under $A$, because $A \Psi = \rho \Psi$ and $\Pi A x = \rho \Pi x = 0$. Let $x_2, \ldots, x_n$ be a basis of $\Pi^0$. Let $$X = \begin{bmatrix}\Psi&x_2&x_3&\cdots&x_n\end{bmatrix}.$$ Then the invariance means that $$X^{-1}AX = \begin{bmatrix}\rho&0\\0&Y\end{bmatrix}$$ where the top right $0$ says $\Pi^0$ is invariant under $A$ and the lower left $0$ says $\mathop{\text{span}}\{\Psi\}$ is invariant under $A$. Here $Y$ is some unknown $(n-1) \times (n-1)$ matrix.

  • $A$ is similar to the above block matrix, so the eigenvalues of $A$ are $\rho$ followed by the eigenvalues of $Y$. If $\rho$ is not a simple eigenvalue, then it must be an eigenvalue of $Y$.

  • Suppose $\rho$ is an eigenvalue of $Y$. Let $\psi'$ be an eigenvector with $Y \psi' = \rho \psi'$. Then $A X {0 \choose \psi'} = \rho X {0 \choose \psi'}$ and $X{0 \choose \psi'}$ is linearly independent of $\Psi = X {1 \choose \mathbf{0}}$. We've already proved that $A$ has only one eigenvector for $\rho$, so that is impossible. Therefore, $\rho$ is not an eigenvalue of $Y$, so $\rho$ is a simple eigenvalue of $A$. That's the last thing we had to prove.

  • Extending to $A \ge 0$ with $A^n > 0$ works as usual.

Thanks!

$\endgroup$
  • 3
    $\begingroup$ An almost exactly similar proof appears in these 2015 lecture notes: maths.nuigalway.ie/~rquinlan/linearalgebra/…, but this presentation was written in 2014, so I think it predates them? $\endgroup$ – Hannah Cairns Feb 9 '18 at 17:26
  • 2
    $\begingroup$ Very nice argument! A small correction: I think the line after your formula for $X^{-1}AX$ should be the other way round: the top right $0$ says $\Pi^0$ is invariant under $A$ and the lower left $0$ says $\operatorname{span} \{\Psi\}$ is invariant under $A$. $\endgroup$ – Jochen Glueck Feb 9 '18 at 22:03
  • 4
    $\begingroup$ I think you get to feel proud of yourself in any case. You produced this. $\endgroup$ – Will Jagy Feb 9 '18 at 22:29
  • $\begingroup$ Yes, thank you, I always mix up that sort of thing if I'm not careful. I'll edit it. $\endgroup$ – Hannah Cairns Feb 9 '18 at 23:44
33
$\begingroup$

(1) Correctness: I read all arguments in detail and couldn't find anything wrong with them. Of course, this doesn't mean too much...

(2) Orginality: I think in a topic which has such an extensive historical record as Perron-Frobenius theory does, the question of "originality" or "novelty" of any particular proof is a very delicate one.

There is an enormous amount of literature out there which all deals with spectral properties of positive matrices in one way or another. I recommend to have a look at MacCluer's survey article [MacCluer: The Many Proofs and Applications of Perron’s Theorem, 2000, SIAM Review, Vol. 42, No. 3, pp. 487–498] for an overview over some proofs of Perron's theorem and for references pointing to several further proofs.

But even if somebody had an overview over all the relevant literature and could thus decide with sufficiently high probability whether the OP's proof (or a very similar one) is written somewhere in the literature, we would still face the problem that, even if the proof as a whole was new, this does not necessarily mean that any of the single arguments in the proof is new.

In fact, in addition to all the articles and textbooks with proofs of Perron's theorem, there have been extensive (and successful) attempts to generalise Perron-Frobenius theory in various directions (for instance, to matrices which leave invariant a cone in $\mathbb{R}^n$, to eventually positive matrices, to Krein-Rutman type theorems on ordered Banach spaces whose cone has non-empty interior, and to Perron-Frobenius theory for positive operators on Banach lattices, in order to mention just four of them), and many arguments used in those theories are variations of techniques from the classical theory.

Hence, it is quite save to say that, for any argument used in any "new" proof of Perron's theorem, we can find a similar argument somewhere in the related literature. Here are a few examples to back up this claim (in the following, I assume for simplicity that the spectral radius equals $1$; this is no loss of generality since we can replace $A$ with $A/\rho$):

  • The second bullet point in the question essentially says that, for every eigenvector $\psi$ belonging to a unimodular eigenvalue, the modulus $|\psi|$ is a super-fixed point of $A$. This observation is essential for many arguments in Perron-Frobenius theory on Banach lattices (see for instance [Schaefer: Banach Lattices and Positive Operators, 1974, Springer, Proposition V.4.6])

  • The argument in the third bullet point in the question is for instance used in [Karlin, Positive Operators, 1959, Lemma 3 and Theorem 8 on page 921]. In the subsequent corollary, Karlin uses this argument in the same way as the OP to deduce the same result (on infinite-dimensional spaces, though).

  • The argument in the seventh bullet point in the question (which shows that the spectral radius is a geometrically simple eigenvalue and which is attributed to Wielandt by the OP) can for instance be found in [Karlin, op. cit., Theorem 9 on p. 922], where the argument is in turn attributed to Krein and Rutman (but I don't know who was earlier).

  • The OP's subsequent argument (which proves algebraic simplicity) actually shows the following general spectral theoretic observation (which is independent of any positivity assumptions): If $\lambda$ is a geometrically simple eigenvalue of a matrix $A$ and if there exists an eigenvector $\Psi$ and a dual eigenvector $\Pi$ such that $\Pi\Psi \not= 0$, then $\lambda$ is also algebraically simple (positivity of $A$ is only used to show the existence of such $\Psi$ and $\Pi$ and to deduce the geometric simplicity).

    [Actually, I wasn't aware of this spectral theoretic fact, and the question brought this to my attention - so let me express my gratitude to the OP for that.] I do not know any place in the literature where this can be found, but it seems very likely that this is known. Maybe somebody else can help out with a reference here?

Of course, one could argue that most proofs published (even of new results) are just a recombination of known arguments from various branches in mathematics, but here we have the very special situation that the known arguments which are combined all stem from essentially one field, namely from the spectral theory of positive matrices and its generalisations - and that they were all used in the literature to prove results which are very closely related to the already known theorem under consideration.

Thus, I would argue that one should rather not consider the OP's proof to be really "novel", even if it might not be written down explicitly in the literature.

Those things said, I feel obliged to add the following three points:

  • It is certainly rewarding, though, to seek for versions and variations of proofs of Perron's theorem. A proof which efficiently combines a few elegant arguments - as the OP's proof definitely does - can be very helpful in teaching (and after all, that's where the proof under discussion comes from, if I understood the OP correctly)

  • I personally find the OP's version of the proof quite appealing. It's very clear and easy to follow.

  • Concerning your motivation to "feel proud of yourself": well, you certainly should feel proud of yourself - you found that proof, and a good one at that.

$\endgroup$
  • 2
    $\begingroup$ Thank you very much for your careful reply, and for the interesting references! $\endgroup$ – Hannah Cairns Feb 10 '18 at 2:02
  • 6
    $\begingroup$ This answer is superlative in at least two ways: its helpful and encyclopedic runthrough of the literature, and in its thoughtful and careful analysis of the different aspects of originality. $\endgroup$ – Tom Church Feb 10 '18 at 16:49
6
$\begingroup$

As someone who lives and dies by the Perron-Frobenius theorem (PFT) and who is familiar with a good deal of the literature on nonnegative matrices (and generalizations of nonnegative matrices), your proof is, to the best of my knowledge, original and correct.

IMHO, the demonstration is worthwhile because it is accessible to advanced undergraduate students who have taken a second course in linear algebra and because positivity is instrumental in the demonstration (contrast with the proof of the PFT via the Brouwer fixed-point theorem, which is quite elegant but many students at the undergraduate level will not have exposure to it). Even though, as Jochen thoroughly notes in his response, your proof (unintentionally) draws on ideas from other proofs, your demonstration pulls these ideas together in a very accessible way, which is the novelty.

Given the above, I think you should consider submitting a carefully revised version of what you posted to the The American Mathematical Monthly or The College Mathematics Journal as a note — if it is not successful those journals, then you can certainly try some research journals (e.g., Positivity or the linear algebra journals ELA, LAA, and LaMA).

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