“Perron–Frobenius theorem”的意思、由来-开放百科全书

In linear algebra, the Perron–Frobenius theorem, proved by {{harvs|txt|authorlink=Oskar Perron|first=Oskar|last= Perron|year=1907}} and {{harvs|txt|authorlink=Georg Frobenius|first=Georg |last=Frobenius|year=1912}}, asserts that a real square matrix with positive entries has a unique largest real eigenvalue and that the corresponding eigenvector can be chosen to have strictly positive components, and also asserts a similar statement for certain classes of nonnegative matrices. This theorem has important applications to probability theory (ergodicity of Markov chains); to the theory of dynamical systems (subshifts of finite type); to economics (Okishio's theorem,^[1] Hawkins–Simon condition^[2]);

to social networks (DeGroot learning process), to Internet search engines^[4] and even to ranking of football

teams.^[5] The first to discuss the ordering of players within tournaments using Perron–Frobenius eigenvectors is Edmund Landau.^[6]

Statement

Let positive and non-negative respectively describe matrices with exclusively positive real numbers as elements and matrices with exclusively non-negative real numbers as elements. The eigenvalues of a real square matrix A are complex numbers that make up the spectrum of the matrix. The exponential growth rate of the matrix powers A^k as k → ∞ is controlled by the eigenvalue of A with the largest absolute value (modulus). The Perron–Frobenius theorem describes the properties of the leading eigenvalue and of the corresponding eigenvectors when A is a non-negative real square matrix. Early results were due to {{harvs|txt|authorlink=Oskar Perron|first=Oskar|last= Perron|year=1907}} and concerned positive matrices. Later, {{harvs|txt|authorlink=Georg Frobenius|first=Georg |last=Frobenius|year=1912}} found their extension to certain classes of non-negative matrices.

Positive matrices

These claims can be found in Meyer^[10] [https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf chapter 8] claims 8.2.11–15 page 667 and exercises 8.2.5,7,9 pages 668–669.

The left and right eigenvectors w and v are sometimes normalized so that the sum of their components is equal to 1; in this case, they are sometimes called stochastic eigenvectors. Often they are normalized so that the right eigenvector v sums to one, while

Non-negative matrices

An extension of the theorem to matrices with non-negative entries is also available. In order to highlight the similarities and differences between the two cases the following points are to be noted: every non-negative matrix can be obtained as a limit of positive matrices, thus one obtains the existence of an eigenvector with non-negative components; the corresponding eigenvalue will be non-negative and greater than or equal, in absolute value, to all other eigenvalues.^[10]^[11] However, the simple examples

show that for non-negative matrices there may exist eigenvalues of the same absolute value as the maximal one ((1) and (−1) – eigenvalues of the first matrix); moreover the maximal eigenvalue may not be a simple root of the characteristic polynomial, can be zero and the corresponding eigenvector (1,0) is not strictly positive (second example). So it may seem that most properties are broken for non-negative matrices, however Frobenius found the right way to generalize to this case.

The key feature of theory in the non-negative case is to find some special subclass of non-negative matrices— irreducible matrices— for which a non-trivial generalization is possible. Namely, although the eigenvalues attaining the maximal absolute value may not be unique, the structure of maximal eigenvalues is under control: they have the form e^i2πl/hr, where h is an integer called the period of matrix, r is a real strictly positive eigenvalue, and l = 0, 1, ..., h − 1.

The eigenvector corresponding to r has strictly positive components (in contrast with the general case of non-negative matrices, where components are only non-negative). Also all such eigenvalues are simple roots of the characteristic polynomial. Further properties are described below.

Classification of matrices

Definition 1 : A does not have non-trivial invariant coordinate subspaces.

Here a non-trivial coordinate subspace means a linear subspace spanned by any proper subset of standard basis vectors of Rⁿ. More explicitly, for any linear subspace spanned by standard basis vectors e_i₁, ...,

e_{i_k}, 0 < k < n its image under the action of A is not contained in the same subspace.

Definition 2: A cannot be conjugated into block upper triangular form by a permutation matrix P:

Definition 3: For every pair of indices i and j, there exists a natural number m such that (A^m)_ij is positive.

Definition 4: One can associate with a matrix A a certain directed graph G_A. It has exactly n vertices, where n is size of A, and there is an edge from vertex i to vertex j precisely when A_ij > 0. Then the matrix A is irreducible if and only if its associated graph G_A is strongly connected.

This notion is somewhat reminiscent of that of a free action of a group; if one could somehow build a group out of A, then the space Rⁿ would be an irreducible representation. (One can build a group by considering the exponential

.) However, the notion of an irreducible matrix is fundamentally easier to satisfy than an irreducible representation, because only coordinate subspaces are considered.

Let A be non-negative. Fix an index i and define the period of index i to be the greatest common divisor of all natural numbers m such that (A^m)_ii > 0. When A is irreducible, the period of every index is the same and is called the period of A. In fact, when A is irreducible, the period can be defined as the greatest common divisor of the lengths of the closed directed paths in G_A (see Kitchens page 16). The period is also called the index of imprimitivity

A matrix A is primitive if it is non-negative and its mth power is positive for some natural number m (i.e. the same m works for all pairs of indices). It can be proved that primitive matrices are the same as irreducible aperiodic non-negative matrices.

A positive square matrix is primitive and a primitive matrix is irreducible. All statements of the Perron–Frobenius theorem for positive matrices remain true for primitive matrices. However, a general non-negative irreducible matrix A may possess several eigenvalues whose absolute value is equal to the spectral radius of A, so the statements need to be correspondingly modified. Actually the number of such eigenvalues is exactly equal to the period. Results for non-negative matrices were first obtained by Frobenius in 1912.

Perron–Frobenius theorem for irreducible matrices

Let A be an irreducible non-negative n × n matrix with period h and spectral radius ρ(A) = r. Then the following statements hold.

The matrix

shows that the (square) zero-matrices along the diagonal may be of different sizes, the blocks A_j need not be square, and h need not divide n.

Further properties

One of the definitions of primitive matrix requires A to be non-negative and there exists m, such that A^m is positive. One may one wonder how big m can be, depending on the size of A. The following answers this question.

Applications

Numerous books have been written on the subject of non-negative matrices, and Perron–Frobenius theory is invariably a central feature. The following examples given below only scratch the surface of its vast application domain.

Non-negative matrices

The Perron–Frobenius theorem does not apply directly to non-negative matrices. Nevertheless, any reducible square matrix A may be written in upper-triangular block form (known as the normal form of a reducible matrix)^[19]

where P is a permutation matrix and each B_i is a square matrix that is either irreducible or zero. Now if A is

non-negative then so too is each block of PAP⁻¹, moreover the spectrum of A is just the union of the spectra of the

The invertibility of A can also be studied. The inverse of PAP⁻¹ (if it exists) must have diagonal blocks of the form B_i⁻¹ so if any

Conversely let D be the block-diagonal matrix corresponding to PAP⁻¹, in other words PAP⁻¹ with the

asterisks zeroised. If each B_i is invertible then so is D and D⁻¹(PAP⁻¹) is equal to the

identity plus a nilpotent matrix. But such a matrix is always invertible (if N^k = 0 the inverse of 1 − N is

Therefore, many of the spectral properties of A may be deduced by applying the theorem to the irreducible B_i. For example, the Perron root is the maximum of the ρ(B_i). While there will still be eigenvectors with non-negative components it is quite possible

Stochastic matrices

A row (column) stochastic matrix is a square matrix each of whose rows (columns) consists of non-negative real numbers whose sum is unity. The theorem cannot be applied directly to such matrices because they need not be irreducible.

If A is row-stochastic then the column vector with each entry 1 is an eigenvector corresponding to the eigenvalue 1, which is also ρ(A) by the remark above. It might not be the only eigenvalue on the unit circle: and the associated eigenspace can be multi-dimensional. If A is row-stochastic and irreducible then the Perron projection is also row-stochastic and all its rows are equal.

Algebraic graph theory

The theorem has particular use in algebraic graph theory. The "underlying graph" of a nonnegative n-square matrix is the graph with vertices numbered 1, ..., n and arc ij if and only if A_ij ≠ 0. If the underlying graph of such a matrix is strongly connected, then the matrix is irreducible, and thus the theorem applies. In particular, the adjacency matrix of a strongly connected graph is irreducible.^[20]^[21]

Finite Markov chains

The theorem has a natural interpretation in the theory of finite Markov chains (where it is the matrix-theoretic equivalent of the convergence of an irreducible finite Markov chain to its stationary distribution, formulated in terms of the transition matrix of the chain; see, for example, the article on the subshift of finite type).

Compact operators

More generally, it can be extended to the case of non-negative compact operators, which, in many ways, resemble finite-dimensional matrices. These are commonly studied in physics, under the name of transfer operators, or sometimes Ruelle–Perron–Frobenius operators (after David Ruelle). In this case, the leading eigenvalue corresponds to the thermodynamic equilibrium of a dynamical system, and the lesser eigenvalues to the decay modes of a system that is not in equilibrium. Thus, the theory offers a way of discovering the arrow of time in what would otherwise appear to be reversible, deterministic dynamical processes, when examined from the point of view of point-set topology.^[22]

Proof methods

A common thread in many proofs is the Brouwer fixed point theorem. Another popular method is that of Wielandt (1950). He used the Collatz–Wielandt formula described above to extend and clarify Frobenius's work.^[23] Another proof is based on the spectral theory^[28] from which part of the arguments are borrowed.

Perron root is strictly maximal eigenvalue for positive (and primitive) matrices

If A is a positive (or more generally primitive) matrix, then there exists a real positive eigenvalue r (Perron–Frobenius eigenvalue or Perron root), which is strictly greater in absolute value than all other eigenvalues, hence r is the spectral radius of A.

This statement does not hold for general non-negative irreducible matrices, which have h eigenvalues with the same absolute eigenvalue as r, where h is the period of A.

Proof for positive matrices

Let A be a positive matrix, assume that its spectral radius ρ(A) = 1 (otherwise consider A/ρ(A)). Hence, there exists an eigenvalue λ on the unit circle, and all the other eigenvalues are less or equal 1 in absolute value. Assume that λ ≠ 1. Then there exists a positive integer m such that A^m is a positive matrix and the real part of λ^m is negative. Let ε be half the smallest diagonal entry of A^m and set T = A^m − ε which is yet another positive matrix. Moreover, if Ax = λx then A^mx = λ^mx thus λ^m − ε is an eigenvalue of T. Because of the choice of m this point lies outside the unit disk consequently ρ(T) > 1. On the other hand, all the entries in T are positive and less than or equal to those in A^m so by Gelfand's formula ρ(T) ≤ ρ(A^m) ≤ ρ(A)^m = 1. This contradiction means that λ=1 and there can be no other eigenvalues on the unit circle.

Absolutely the same arguments can be applied to the case of primitive matrices; we just need to mention the following simple lemma, which clarifies the properties of primitive matrices.

Lemma

Given a non-negative A, assume there exists m, such that A^m is positive, then A^m+1, A^m+2, A^m+3,... are all positive.

A^m+1 = AA^m, so it can have zero element only if some row of A is entirely zero, but in this case the same row of A^m will be zero.

Applying the same arguments as above for primitive matrices, prove the main claim.

Power method and the positive eigenpair

For a positive (or more generally irreducible non-negative) matrix A the dominant eigenvector is real and strictly positive (for non-negative A respectively non-negative.)

This can be established using the power method, which states that for a sufficiently generic (in the sense below) matrix A the sequence of vectors b_k+1 = Ab_k / | Ab_k | converges to the eigenvector with the maximum eigenvalue. (The initial vector b₀ can be chosen arbitrarily except for some measure zero set). Starting with a non-negative vector b₀ produces the sequence of non-negative vectors b_k. Hence the limiting vector is also non-negative. By the power method this limiting vector is the dominant eigenvector for A, proving the assertion. The corresponding eigenvalue is non-negative.

The proof requires two additional arguments. First, the power method converges for matrices which do not have several eigenvalues of the same absolute value as the maximal one. The previous section's argument guarantees this.

Second, to ensure strict positivity of all of the components of the eigenvector for the case of irreducible matrices. This follows from the following fact, which is of independent interest:

Proof. One of the definitions of irreducibility for non-negative matrices is that for all indexes i,j there exists m, such that (A^m)_ij is strictly positive. Given a non-negative eigenvector v, and that at least one of its components say j-th is strictly positive, the corresponding eigenvalue is strictly positive, indeed, given n such that (Aⁿ)_ii >0, hence: rⁿv_i =

>0. Hence r is strictly positive. The eigenvector is strict positivity. Then given m, such that (A^m)_ij >0, hence: r^mv_j =

Multiplicity one

This section proves that the Perron–Frobenius eigenvalue is a simple root of the characteristic polynomial of the matrix. Hence the eigenspace associated to Perron–Frobenius eigenvalue r is one-dimensional. The arguments here are close to those in Meyer.^[24]

Given a strictly positive eigenvector v corresponding to r and another eigenvector w with the same eigenvalue. (Vector w can be chosen to be real, because A and r are both real, so the null space of A-r has a basis consisting of real vectors). Assuming at least one of the components of w is positive (otherwise multiply w by −1). Given maximal possible α such that u=v- α w is non-negative, then one of the components of u is zero, otherwise α is not maximum. Vector u is an eigenvector. It is non-negative, hence by the lemma described in the previous section non-negativity implies strict positivity for any eigenvector. On the other hand, as above at least one component of u is zero. The contradiction implies that w does not exist.

Case: There are no Jordan cells corresponding to the Perron–Frobenius eigenvalue r and all other eigenvalues which have the same absolute value.

Given r = 1, or A/r. Letting v be a Perron–Frobenius strictly positive eigenvector, so Av=v, then:

So A^k_∞ is bounded for all k. This gives another proof that there are no eigenvalues which have greater absolute value than Perron–Frobenius one. It also contradicts the existence of the Jordan cell for any eigenvalue which has absolute value equal to 1 (in particular for the Perron–Frobenius one), because existence of the Jordan cell implies that A^k_∞ is unbounded. For a two by two matrix:

hence J^k_∞ = |k + λ| (for |λ| = 1), so it tends to infinity when k does so. Since J^k = C⁻¹ A^kC, then A^k ≥ J^k/ (C⁻¹ C ), so it also tends to infinity. The resulting contradiction implies that there are no Jordan cells for the corresponding eigenvalues.

Combining the two claims above reveals that the Perron–Frobenius eigenvalue r is simple root of the characteristic polynomial. In the case of nonprimitive matrices, there exist other eigenvalues which have the same absolute value as r. The same claim is true for them, but requires more work.

No other non-negative eigenvectors

Given positive (or more generally irreducible non-negative matrix) A, the Perron–Frobenius eigenvector is the only (up to multiplication by constant) non-negative eigenvector for A.

Other eigenvectors must contain negative or complex components since eigenvectors for different eigenvalues are orthogonal in some sense, but two positive eigenvectors cannot be orthogonal, so they must correspond to the same eigenvalue, but the eigenspace for the Perron–Frobenius is one-dimensional.

Assuming there exists an eigenpair (λ, y) for A, such that vector y is positive, and given (r, x), where x – is the left Perron–Frobenius eigenvector for A (i.e. eigenvector for A^T), then

Collatz–Wielandt formula

Given a positive (or more generally irreducible non-negative matrix) A, for all non-negative non-zero vectors x and f(x) as the minimum value of [Ax]_i / x_i taken over all those i such that x_i ≠ 0, then f is a real valued function whose maximum is the Perron–Frobenius eigenvalue r.

Here, r is attained for x taken to be the Perron–Frobenius eigenvector v. The proof requires that values f on the other vectors are less or equal. Given a vector x. Let ξ=f(x), so 0≤ξx≤Ax and w to be the right eigenvector for A, then w^T ξx ≤ w^T (Ax) = (w^T A)x = r w^T x . Hence ξ≤r.^[26]

Perron projection as a limit: A^k/r^k

Let A be a positive (or more generally, primitive) matrix, and let r be its Perron–Frobenius eigenvalue.

Hence P is a spectral projection for the Perron–Frobenius eigenvalue r, and is called the Perron projection. The above assertion is not true for general non-negative irreducible matrices.

Actually the claims above (except claim 5) are valid for any matrix M such that there exists an eigenvalue r which is strictly greater than the other eigenvalues in absolute value and is the simple root of the characteristic polynomial. (These requirements hold for primitive matrices as above).

Given that M is diagonalizable, M is conjugate to a diagonal matrix with eigenvalues r₁, ... , r_n on the diagonal (denote r₁ = r). The matrix M^k/r^k will be conjugate (1, (r₂/r)^k, ... , (r_n/r)^k), which tends to (1,0,0,...,0), for k → ∞, so the limit exists. The same method works for general M (without assuming that M is diagonalizable).

The projection and commutativity properties are elementary corollaries of the definition: MM^k/r^k = M^k/r^k M ; P² = lim M^2k/r^2k = P. The third fact is also elementary: M(Pu) = M lim M^k/r^k u = lim rM^k+1/r^k+1u, so taking the limit yields M(Pu) = r(Pu), so image of P lies in the r-eigenspace for M, which is one-dimensional by the assumptions.

Denoting by v, r-eigenvector for M (by w for M^T). Columns of P are multiples of v, because the image of P is spanned by it. Respectively, rows of w. So P takes a form (a v w^T), for some a. Hence its trace equals to (a w^T v). Trace of projector equals the dimension of its image. It was proved before that it is not more than one-dimensional. From the definition one sees that P acts identically on the r-eigenvector for M. So it is one-dimensional. So choosing (w^Tv) = 1, implies P = vw^T.

Inequalities for Perron–Frobenius eigenvalue

For any non-nonegative matrix A its Perron–Frobenius eigenvalue r satisfies the inequality:

This is not specific to non-negative matrices: for any matrix A with an eigenvalue

it is true

Any matrix induced norm satisfies the inequality

for any eigenvalue

because, if

is a corresponding eigenvector,

. The infinity norm of a matrix is the maximum of row sums:

Hence the desired inequality is exactly

applied to the non-negative matrix A.

This fact is specific to non-negative matrices; for general matrices there is nothing similar. Given that A is positive (not just non-negative), then there exists a positive eigenvector w such that Aw = rw and the smallest component of w (say w_i) is 1. Then r = (Aw)_i ≥ the sum of the numbers in row i of A. Thus the minimum row sum gives a lower bound for r and this observation can be extended to all non-negative matrices by continuity.

Another way to argue it is via the Collatz-Wielandt formula. One takes the vector x = (1, 1, ..., 1) and immediately obtains the inequality.

Further proofs

Perron projection

The proof now proceeds using spectral decomposition. The trick here is to split the Perron root from the other eigenvalues. The spectral projection associated with the Perron root is called the Perron projection and it enjoys the following property:

The Perron projection of an irreducible non-negative square matrix is a positive matrix.

Perron's findings and also (1)–(5) of the theorem are corollaries of this result. The key point is that a positive projection always has rank one. This means that if A is an irreducible non-negative square matrix then the algebraic and geometric multiplicities of its Perron root are both one. Also if P is its Perron projection then AP = PA = ρ(A)P so every column of P is a positive right eigenvector of A and every row is a positive left eigenvector. Moreover, if Ax = λx then PAx = λPx = ρ(A)Px which means Px = 0 if λ ≠ ρ(A). Thus the only positive eigenvectors are those associated with ρ(A). If A is a primitive matrix with ρ(A) = 1 then it can be decomposed as P ⊕ (1 − P)A so that Aⁿ = P + (1 − P)Aⁿ. As n increases the second of these terms decays to zero leaving P as the limit of Aⁿ as n → ∞.

The power method is a convenient way to compute the Perron projection of a primitive matrix. If v and w are the positive row and column vectors that it generates then the Perron projection is just wv/vw. It should be noted that the spectral projections aren't neatly blocked as in the Jordan form. Here they are overlaid and each generally has complex entries extending to all four corners of the square matrix. Nevertheless, they retain their mutual orthogonality which is what facilitates the decomposition.

Peripheral projection

The analysis when A is irreducible and non-negative is broadly similar. The Perron projection is still positive but there may now be other eigenvalues of modulus ρ(A) that negate use of the power method and prevent the powers of (1 − P)A decaying as in the primitive case whenever ρ(A) = 1. So we consider the peripheral projection, which is the spectral projection of A corresponding to all the eigenvalues that have modulus ρ(A). It may then be shown that the peripheral projection of an irreducible non-negative square matrix is a non-negative matrix with a positive diagonal.

Cyclicity

Suppose in addition that ρ(A) = 1 and A has h eigenvalues on the unit circle. If P is the peripheral projection then the matrix R = AP = PA is non-negative and irreducible, R^h = P, and the cyclic group P, R, R², ...., R^h−1 represents the harmonics of A. The spectral projection of A at the eigenvalue λ on the unit circle is given by the formula

. All of these projections (including the Perron projection) have the same positive diagonal, moreover choosing any one of them and then taking the modulus of every entry invariably yields the Perron projection. Some donkey work is still needed in order to establish the cyclic properties (6)–(8) but it's essentially just a matter of turning the handle. The spectral decomposition of A is given by A = R ⊕ (1 − P)A so the difference between Aⁿ and Rⁿ is Aⁿ − Rⁿ = (1 − P)Aⁿ representing the transients of Aⁿ which eventually decay to zero. P may be computed as the limit of A^nh as n → ∞.

Caveats

The matrices L =

, P =

, T =

, M =

provide simple examples of what can go wrong if the necessary conditions are not met. It is easily seen that the Perron and peripheral projections of L are both equal to P, thus when the original matrix is reducible the projections may lose non-negativity and there is no chance of expressing them as limits of its powers. The matrix T is an example of a primitive matrix with zero diagonal. If the diagonal of an irreducible non-negative square matrix is non-zero then the matrix must be primitive but this example demonstrates that the converse is false. M is an example of a matrix with several missing spectral teeth. If ω = e^iπ/3 then ω⁶ = 1 and the eigenvalues of M are {1,ω²,ω³,ω⁴} so ω and ω⁵ are both absent.{{Citation needed|date=January 2012}}

Terminology

A problem that causes confusion is a lack of standardisation in the definitions. For example, some authors use the terms strictly positive and positive to mean > 0 and ≥ 0 respectively. In this article positive means > 0 and non-negative means ≥ 0. Another vexed area concerns decomposability and reducibility: irreducible is an overloaded term. For avoidance of doubt a non-zero non-negative square matrix A such that 1 + A is primitive is sometimes said to be connected. Then irreducible non-negative square matrices and connected matrices are synonymous.^[27]

The nonnegative eigenvector is often normalized so that the sum of its components is equal to unity; in this case, the eigenvector is the vector of a probability distribution and is sometimes called a stochastic eigenvector.

Perron–Frobenius eigenvalue and dominant eigenvalue are alternative names for the Perron root. Spectral projections are also known as spectral projectors and spectral idempotents. The period is sometimes referred to as the index of imprimitivity or the order of cyclicity.

See also

Notes

1. ^{{Cite journal|last=Bowles|first=Samuel|date=1981-06-01|title=Technical change and the profit rate: a simple proof of the Okishio theorem|url=https://academic.oup.com/cje/article/1699192/Technical|journal=Cambridge Journal of Economics|language=en|volume=5|issue=2|pages=183–186|doi=10.1093/oxfordjournals.cje.a035479|issn=0309-166X}}
2. ^{{harvnb|Meyer|2000|pp=8.3.6 p. 681 {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |accessdate=2010-03-07 |deadurl=yes |archiveurl=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archivedate=March 7, 2010 |df= }}}}
3. ^{{harvnb|Meyer|2000|pp=8.3.7 p. 683 {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |accessdate=2010-03-07 |deadurl=yes |archiveurl=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archivedate=March 7, 2010 |df= }}}}
4. ^{{harvnb|Langville|Meyer|2006|p=[https://books.google.com/books?id=hxvB14-I0twC&lpg=PP1&dq=isbn%3A0691122024&pg=PA167#v=onepage&q&f=false 15.2 p. 167]}} {{cite book |url=https://books.google.com/books?id=hxvB14-I0twC&lpg=PP1&dq=isbn%3A0691122024&pg=PA167 |title=Google's PageRank and Beyond: The Science of Search Engine Rankings |accessdate=2016-10-31 |deadurl=bot: unknown |archiveurl=https://web.archive.org/web/20140710041730/https://books.google.com/books?id=hxvB14-I0twC&lpg=PP1&dq=isbn%3A0691122024&pg=PA167#v=onepage&q&f=false |archivedate=July 10, 2014 |df= |isbn=978-0691122021 |last1=Langville |first1=Amy N. |last2=Langville |first2=Amy N. |last3=Meyer |first3=Carl D. |date=2006-07-23 }}
5. ^{{harvnb|Keener|1993|p=[https://www.jstor.org/stable/2132526 p. 80]}}
6. ^{{citation | title = Zur relativen Wertbemessung der Turnierresultaten| pages = 366–369| volume = XI | number = | journal = Deutsches Wochenschach | year=1895 | first1=Edmund | last1=Landau | url = | doi= }}
7. ^{{citation | title = Über Preisverteilung bei Spielturnieren| pages = 192–202| volume = 63 | number = | journal =Zeitschrift für Mathematik und Physik | year=1915 | first1=Edmund | last1=Landau | url = http://iris.univ-lille1.fr/handle/1908/2031 | doi= }}
8. ^Donsker, M.D. and Varadhan, S.S., 1975. On a variational formula for the principal eigenvalue for operators with maximum principle. Proceedings of the National Academy of Sciences, 72(3), pp.780-783.
9. ^Friedland, S., 1981. Convex spectral functions. Linear and multilinear algebra, 9(4), pp.299-316.
10. ^{{harvnb|Meyer|2000|pp=chapter 8.3 page 670 {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |accessdate=2010-03-07 |deadurl=yes |archiveurl=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archivedate=March 7, 2010 |df= }}}}
11. ^{{harvnb|Gantmacher|2000|p=[https://books.google.com/books?id=cyX32q8ZP5cC&lpg=PA178&vq=preceding%20section&pg=PA66#v=onepage&q&f=false chapter XIII.3 theorem 3 page 66]}}
12. ^{{harvnb|Meyer|2000|pp=claim 8.3.11 p. 675 {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |accessdate=2010-03-07 |deadurl=yes |archiveurl=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archivedate=March 7, 2010 |df= }}}}
13. ^{{harvnb|Gantmacher|2000|p=section XIII.5 theorem 9}}
14. ^{{harvnb|Meyer|2000|pp=page 679 {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |accessdate=2010-03-07 |deadurl=yes |archiveurl=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archivedate=March 7, 2010 |df= }}}}
15. ^{{harvnb|Meyer|2000|pp=example 8.3.2 p. 677 {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |accessdate=2010-03-07 |deadurl=yes |archiveurl=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archivedate=March 7, 2010 |df= }}}}
16. ^{{harvnb|Gantmacher|2000|p=[https://books.google.com/books?id=cyX32q8ZP5cC&lpg=PA178&vq=preceding%20section&pg=PA62#v=onepage&q&f=true section XIII.2.2 page 62]}}
17. ^{{harvnb|Meyer|2000|pp= example 8.3.3 p. 678 {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |accessdate=2010-03-07 |deadurl=yes |archiveurl=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archivedate=March 7, 2010 |df= }}}}
18. ^{{harvnb|Meyer|2000|pp=chapter 8 example 8.3.4 page 679 and exercise 8.3.9 p. 685 {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |accessdate=2010-03-07 |deadurl=yes |archiveurl=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archivedate=March 7, 2010 |df= }}}}
19. ^{{harvnb|Varga|2002|p=2.43 (page 51)}}
20. ^{{cite book |authorlink=Richard A. Brualdi |first=Richard A. |last=Brualdi |authorlink2=H. J. Ryser |first2=Herbert J. |last2=Ryser |title=Combinatorial Matrix Theory |location=Cambridge |publisher=Cambridge UP |year=1992 |isbn=978-0-521-32265-2 }}
21. ^{{cite book |authorlink=Richard A. Brualdi |first=Richard A. |last=Brualdi |first2=Dragos |last2=Cvetkovic |title=A Combinatorial Approach to Matrix Theory and Its Applications |publisher=CRC Press |location=Boca Raton, FL |year=2009 |isbn=978-1-4200-8223-4 }}
22. ^{{cite book |first=Michael C. |last=Mackey |title=Time's Arrow: The origins of thermodynamic behaviour |location=New York |publisher=Springer-Verlag |year=1992 |isbn=978-0-387-97702-7 }}
23. ^{{harvnb|Gantmacher|2000|p=[https://books.google.ru/books?id=cyX32q8ZP5cC&lpg=PR5&dq=Applications%20of%20the%20theory%20of%20matrices&pg=PA54#v=onepage&q&f=false section XIII.2.2 page 54]}}
24. ^¹²³{{harvnb|Meyer|2000|pp=chapter 8 page 665 {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |accessdate=2010-03-07 |deadurl=yes |archiveurl=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archivedate=March 7, 2010 |df= }}}}
25. ^{{harvnb|Meyer|2000|pp=chapter 8 claim 8.2.10 page 666 {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |accessdate=2010-03-07 |deadurl=yes |archiveurl=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archivedate=March 7, 2010 |df= }}}}
26. ^{{harvnb|Meyer|2000|pp=chapter 8 page 666 {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |accessdate=2010-03-07 |deadurl=yes |archiveurl=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archivedate=March 7, 2010 |df= }}}}
27. ^For surveys of results on irreducibility, see Olga Taussky-Todd and Richard A. Brualdi.
28. ^¹{{citation | title = A Spectral Theoretic Proof of Perron–Frobenius| pages = 29–35| volume = 102 | number = 1 | journal =Mathematical Proceedings of the Royal Irish Academy | year=2006 | first1=Roger | last1=Smith | url = ftp://emis.maths.adelaide.edu.au/pub/EMIS/journals/MPRIA/2002/pa102i1/pdf/102a102.pdf | doi=10.3318/PRIA.2002.102.1.29}}

References

Original papers

url = https://books.google.com/books?id=cyX32q8ZP5cC&lpg=PA178&vq=preceding%20section&pg=PA53#v=onepage&q&f=true}} (1959 edition had different title: "Applications of the theory of matrices". Also the numeration of chapters is different in the two editions.)

Statement

Positive matrices

Non-negative matrices

Classification of matrices

Perron–Frobenius theorem for irreducible matrices

Further properties

Applications

Non-negative matrices

Stochastic matrices

Algebraic graph theory

Finite Markov chains

Compact operators

Proof methods

Perron root is strictly maximal eigenvalue for positive (and primitive) matrices

Proof for positive matrices

Lemma

Power method and the positive eigenpair

Multiplicity one

No other non-negative eigenvectors

Collatz–Wielandt formula

Perron projection as a limit: Ak/rk

Inequalities for Perron–Frobenius eigenvalue

Further proofs

Perron projection

Peripheral projection

Cyclicity

Caveats

Terminology

See also

Notes

References

Original papers

Further reading

Perron projection as a limit: A^k/r^k