# Perron–Frobenius theorem

Perron–Frobenius theorem In matrix theory, the Perron–Frobenius theorem, proved by Oskar Perron (1907) and Georg Frobenius (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 demography (Leslie population age distribution model);[3] to social networks (DeGroot learning process); to Internet search engines (PageRank);[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] [7] Contents 1 Statement 1.1 Positive matrices 1.2 Non-negative matrices 1.2.1 Classification of matrices 1.2.2 Perron–Frobenius theorem for irreducible non-negative matrices 1.3 Further properties 2 Applications 2.1 Non-negative matrices 2.2 Stochastic matrices 2.3 Algebraic graph theory 2.4 Finite Markov chains 2.5 Compact operators 3 Proof methods 3.1 Perron root is strictly maximal eigenvalue for positive (and primitive) matrices 3.1.1 Proof for positive matrices 3.1.2 Lemma 3.2 Power method and the positive eigenpair 3.3 Multiplicity one 3.4 No other non-negative eigenvectors 3.5 Collatz–Wielandt formula 3.6 Perron projection as a limit: Ak/rk 3.7 Inequalities for Perron–Frobenius eigenvalue 3.8 Further proofs 3.8.1 Perron projection 3.8.2 Peripheral projection 3.8.3 Cyclicity 4 Counterexamples 5 Terminology 6 See also 7 Notes 8 References 8.1 Further reading 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 Ak 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 Oskar Perron (1907) and concerned positive matrices. Later, Georg Frobenius (1912) found their extension to certain classes of non-negative matrices.

Positive matrices Let {displaystyle A=(a_{ij})} be an {displaystyle ntimes n} positive matrix: {displaystyle a_{ij}>0} for {displaystyle 1leq i,jleq n} . Then the following statements hold.

There is a positive real number r, called the Perron root or the Perron–Frobenius eigenvalue (also called the leading eigenvalue or dominant eigenvalue), such that r is an eigenvalue of A and any other eigenvalue λ (possibly complex) in absolute value is strictly smaller than r , |λ| < r. Thus, the spectral radius {displaystyle rho (A)} is equal to r. If the matrix coefficients are algebraic, this implies that the eigenvalue is a Perron number. The Perron–Frobenius eigenvalue is simple: r is a simple root of the characteristic polynomial of A. Consequently, the eigenspace associated to r is one-dimensional. (The same is true for the left eigenspace, i.e., the eigenspace for AT, the transpose of A.) There exists an eigenvector v = (v1,...,vn)T of A with eigenvalue r such that all components of v are positive: A v = r v, vi > 0 for 1 ≤ i ≤ n. (Respectively, there exists a positive left eigenvector w : wT A = r wT, wi > 0.) It is known in the literature under many variations as the Perron vector, Perron eigenvector, Perron-Frobenius eigenvector, leading eigenvector, or dominant eigenvector. There are no other positive (moreover non-negative) eigenvectors except positive multiples of v (respectively, left eigenvectors except w), i.e., all other eigenvectors must have at least one negative or non-real component. {displaystyle lim _{krightarrow infty }A^{k}/r^{k}=vw^{T}} , where the left and right eigenvectors for A are normalized so that wTv = 1. Moreover, the matrix v wT is the projection onto the eigenspace corresponding to r. This projection is called the Perron projection. Collatz–Wielandt formula: for all non-negative non-zero vectors x, let f(x) be the minimum value of [Ax]i / xi taken over all those i such that xi ≠ 0. Then f is a real valued function whose maximum over all non-negative non-zero vectors x is the Perron–Frobenius eigenvalue. A "Min-max" Collatz–Wielandt formula takes a form similar to the one above: for all strictly positive vectors x, let g(x) be the maximum value of [Ax]i / xi taken over i. Then g is a real valued function whose minimum over all strictly positive vectors x is the Perron–Frobenius eigenvalue. Birkhoff–Varga formula: Let x and y be strictly positive vectors. Then {displaystyle r=sup _{x>0}inf _{y>0}{frac {y^{top }Ax}{y^{top }x}}=inf _{x>0}sup _{y>0}{frac {y^{top }Ax}{y^{top }x}}=inf _{x>0}sup _{y>0}sum _{i,j=1}^{n}y_{i}a_{ij}x_{j}/sum _{i=1}^{n}y_{i}x_{i}.} [8] Donsker–Varadhan–Friedland formula: Let p be a probability vector and x a strictly positive vector. Then {displaystyle r=sup _{p}inf _{x>0}sum _{i=1}^{n}p_{i}[Ax]_{i}/x_{i}.} [9][10] Fiedler formula: {displaystyle r=sup _{z>0} inf _{x>0, y>0, xcirc y=z}{frac {y^{top }Ax}{y^{top }x}}=sup _{z>0} inf _{x>0, y>0, xcirc y=z}sum _{i,j=1}^{n}y_{i}a_{ij}x_{j}/sum _{i=1}^{n}y_{i}x_{i}.} [11] The Perron–Frobenius eigenvalue satisfies the inequalities {displaystyle min _{i}sum _{j}a_{ij}leq rleq max _{i}sum _{j}a_{ij}.} All of these properties extend beyond strictly positive matrices to primitive matrices (see below). Facts 1-7 can be found in Meyer[12] 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 {displaystyle w^{T}v=1} .

Non-negative matrices There is an extension to matrices with non-negative entries. Since any non-negative matrix can be obtained as a limit of positive matrices, 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.[13][14] However, for the example {displaystyle A=left({begin{smallmatrix}0&1\1&0end{smallmatrix}}right)} , the maximum eigenvalue r = 1 has the same absolute value as the other eigenvalue −1; while for {displaystyle A=left({begin{smallmatrix}0&1\0&0end{smallmatrix}}right)} , the maximum eigenvalue is r = 0, which is not a simple root of the characteristic polynomial, and the corresponding eigenvector (1, 0) is not strictly positive.

However, Frobenius found a special subclass of non-negative matrices — irreducible matrices — for which a non-trivial generalization is possible. For such a matrix, although the eigenvalues attaining the maximal absolute value might not be unique, their structure is under control: they have the form {displaystyle omega r} , where r is a real strictly positive eigenvalue, and {displaystyle omega } ranges over the complex hth roots of 1 for some positive integer h called the period of the matrix. 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 Let A be a n × n square matrix over field F. The matrix A is irreducible if any of the following equivalent properties holds.

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 Fn. More explicitly, for any linear subspace spanned by standard basis vectors ei1 , ..., eik, 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: {displaystyle PAP^{-1}neq {begin{pmatrix}E&F\O&Gend{pmatrix}},} where E and G are non-trivial (i.e. of size greater than zero) square matrices. Definition 3: One can associate with a matrix A a certain directed graph GA. It has n vertices labeled 1,...,n, and there is an edge from vertex i to vertex j precisely when aij ≠ 0. Then the matrix A is irreducible if and only if its associated graph GA is strongly connected. If F is the field of real or complex numbers, then we also have the following condition. Definition 4: The group representation of {displaystyle (mathbb {R} ,+)} on {displaystyle mathbb {R} ^{n}} or {displaystyle (mathbb {C} ,+)} on {displaystyle mathbb {C} ^{n}} given by {displaystyle tmapsto exp(tA)} has no non-trivial invariant coordinate subspaces. (By comparison, this would be an irreducible representation if there were no non-trivial invariant subspaces at all, not only considering coordinate subspaces.) A matrix is reducible if it is not irreducible. A real matrix A is primitive if it is non-negative and its mth power is positive for some natural number m (i.e. all entries of Am are positive). Let A be real and 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 (Am)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 GA (see Kitchens[15] page 16). The period is also called the index of imprimitivity (Meyer[12] page 674) or the order of cyclicity. If the period is 1, A is aperiodic. It can be proved that primitive matrices are the same as irreducible aperiodic non-negative matrices.

All statements of the Perron–Frobenius theorem for positive matrices remain true for primitive matrices. The same statements also hold for a non-negative irreducible matrix, except that it may possess several eigenvalues whose absolute value is equal to its spectral radius, so the statements need to be correspondingly modified. In fact the number of such eigenvalues is equal to the period.

Results for non-negative matrices were first obtained by Frobenius in 1912.

Perron–Frobenius theorem for irreducible non-negative 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 number r is a positive real number and it is an eigenvalue of the matrix A, called the Perron–Frobenius eigenvalue. The Perron–Frobenius eigenvalue r is simple. Both right and left eigenspaces associated with r are one-dimensional. A has a right eigenvector v with eigenvalue r whose components are all positive. Likewise, A has a left eigenvector w with eigenvalue r whose components are all positive. The only eigenvectors whose components are all positive are those associated with the eigenvalue r. The matrix A has exactly h (where h is the period) complex eigenvalues with absolute value r. Each of them is a simple root of the characteristic polynomial and is the product of r with an hth root of unity. Let ω = 2π/h. Then the matrix A is similar to eiωA, consequently the spectrum of A is invariant under multiplication by eiω (corresponding to the rotation of the complex plane by the angle ω). If h > 1 then there exists a permutation matrix P such that {displaystyle PAP^{-1}={begin{pmatrix}O&A_{1}&O&O&ldots &O\O&O&A_{2}&O&ldots &O\vdots &vdots &vdots &vdots &&vdots \O&O&O&O&ldots &A_{h-1}\A_{h}&O&O&O&ldots &Oend{pmatrix}},} where O denotes a zero matrix and the blocks along the main diagonal are square matrices. 9. Collatz–Wielandt formula: for all non-negative non-zero vectors x let f(x) be the minimum value of [Ax]i / xi taken over all those i such that xi ≠ 0. Then f is a real valued function whose maximum is the Perron–Frobenius eigenvalue. 10. The Perron–Frobenius eigenvalue satisfies the inequalities {displaystyle min _{i}sum _{j}a_{ij}leq rleq max _{i}sum _{j}a_{ij}.} The example {displaystyle A=left({begin{smallmatrix}0&0&1\0&0&1\1&1&0end{smallmatrix}}right)} shows that the (square) zero-matrices along the diagonal may be of different sizes, the blocks Aj need not be square, and h need not divide n.

Further properties Let A be an irreducible non-negative matrix, then: (I+A)n−1 is a positive matrix. (Meyer[12] claim 8.3.5 p. 672). For a non-negative A, this is also a sufficient condition. (Minc,[16] Corollary 2.2, p.6). Wielandt's theorem.[17][clarification needed] If |B| 1. On the other hand, all the entries in T are positive and less than or equal to those in Am so by Gelfand's formula ρ(T) ≤ ρ(Am) ≤ ρ(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 Am is positive, then Am+1, Am+2, Am+3,... are all positive.

Am+1 = AAm, so it can have zero element only if some row of A is entirely zero, but in this case the same row of Am 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 bk+1 = Abk / | Abk | converges to the eigenvector with the maximum eigenvalue. (The initial vector b0 can be chosen arbitrarily except for some measure zero set). Starting with a non-negative vector b0 produces the sequence of non-negative vectors bk. 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: Lemma: given a positive (or more generally irreducible non-negative) matrix A and v as any non-negative eigenvector for A, then it is necessarily strictly positive and the corresponding eigenvalue is also strictly positive.

Proof. One of the definitions of irreducibility for non-negative matrices is that for all indexes i,j there exists m, such that (Am)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 (An)ii >0, hence: rnvi = Anvi ≥ (An)iivi >0. Hence r is strictly positive. The eigenvector is strict positivity. Then given m, such that (Am)ij >0, hence: rmvj = (Amv)j ≥ (Am)ijvi >0, hence vj is strictly positive, i.e., the eigenvector is strictly positive.

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.[12] Given a strictly positive eigenvector v corresponding to r and another eigenvector w with the same eigenvalue. (The vectors v and 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.

If there is a Jordan cell, then the infinity norm (A/r)k∞ tends to infinity for k → ∞ , but that contradicts the existence of the positive eigenvector.

Given r = 1, or A/r. Letting v be a Perron–Frobenius strictly positive eigenvector, so Av=v, then: {displaystyle |v|_{infty }=|A^{k}v|_{infty }geq |A^{k}|_{infty }min _{i}(v_{i}),~~Rightarrow ~~|A^{k}|_{infty }leq |v|/min _{i}(v_{i})} So Ak∞ 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 Ak∞ is unbounded. For a two by two matrix: {displaystyle J^{k}={begin{pmatrix}lambda &1\0&lambda end{pmatrix}}^{k}={begin{pmatrix}lambda ^{k}&klambda ^{k-1}\0&lambda ^{k}end{pmatrix}},} hence Jk∞ = |k + λ| (for |λ| = 1), so it tends to infinity when k does so. Since Jk = C−1 AkC, then Ak ≥ Jk/ (C−1 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 AT), then rxTy = (xT A) y = xT (Ay) = λxTy, also xT y > 0, so one has: r = λ. Since the eigenspace for the Perron–Frobenius eigenvalue r is one-dimensional, non-negative eigenvector y is a multiple of the Perron–Frobenius one.[31] Collatz–Wielandt formula Given a positive (or more generally irreducible non-negative matrix) A, one defines the function f on the set of all non-negative non-zero vectors x such that f(x) is the minimum value of [Ax]i / xi taken over all those i such that xi ≠ 0. Then f is a real-valued function, whose maximum is the Perron–Frobenius eigenvalue r.

For the proof we denote the maximum of f by the value R. The proof requires to show R = r. Inserting the Perron-Frobenius eigenvector v into f, we obtain f(v) = r and conclude r ≤ R. For the opposite inequality, we consider an arbitrary nonnegative vector x and let ξ=f(x). The definition of f gives 0 ≤ ξx ≤ Ax (componentwise). Now, we use the positive right eigenvector w for A for the Perron-Frobenius eigenvalue r, then ξ wT x = wT ξx ≤ wT (Ax) = (wT A)x = r wT x . Hence f(x) = ξ ≤ r, which implies R ≤ r.[32] Perron projection as a limit: Ak/rk Let A be a positive (or more generally, primitive) matrix, and let r be its Perron–Frobenius eigenvalue.

There exists a limit Ak/rk for k → ∞, denote it by P. P is a projection operator: P2 = P, which commutes with A: AP = PA. The image of P is one-dimensional and spanned by the Perron–Frobenius eigenvector v (respectively for PT—by the Perron–Frobenius eigenvector w for AT). P = vwT, where v,w are normalized such that wT v = 1. Hence P is a positive operator.

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 r1, ... , rn on the diagonal (denote r1 = r). The matrix Mk/rk will be conjugate (1, (r2/r)k, ... , (rn/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: MMk/rk = Mk/rk M ; P2 = lim M2k/r2k = P. The third fact is also elementary: M(Pu) = M lim Mk/rk u = lim rMk+1/rk+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 MT). 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 wT), for some a. Hence its trace equals to (a wT 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 (wTv) = 1, implies P = vwT.

Inequalities for Perron–Frobenius eigenvalue For any non-negative matrix A its Perron–Frobenius eigenvalue r satisfies the inequality: {displaystyle r;leq ;max _{i}sum _{j}a_{ij}.} This is not specific to non-negative matrices: for any matrix A with an eigenvalue {displaystyle scriptstyle lambda } it is true that {displaystyle scriptstyle |lambda |;leq ;max _{i}sum _{j}|a_{ij}|} . This is an immediate corollary of the Gershgorin circle theorem. However another proof is more direct: Any matrix induced norm satisfies the inequality {displaystyle scriptstyle |A|geq |lambda |} for any eigenvalue {displaystyle scriptstyle lambda } because, if {displaystyle scriptstyle x} is a corresponding eigenvector, {displaystyle scriptstyle |A|geq |Ax|/|x|=|lambda x|/|x|=|lambda |} . The infinity norm of a matrix is the maximum of row sums: {displaystyle scriptstyle left|Aright|_{infty }=max limits _{1leq ileq m}sum _{j=1}^{n}|a_{ij}|.} Hence the desired inequality is exactly {displaystyle scriptstyle |A|_{infty }geq |lambda |} applied to the non-negative matrix A.

Another inequality is: {displaystyle min _{i}sum _{j}a_{ij};leq ;r.} 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 wi) 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 An = P + (1 − P)An. As n increases the second of these terms decays to zero leaving P as the limit of An 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. 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, Rh = P, and the cyclic group P, R, R2, ...., Rh−1 represents the harmonics of A. The spectral projection of A at the eigenvalue λ on the unit circle is given by the formula {displaystyle scriptstyle h^{-1}sum _{1}^{h}lambda ^{-k}R^{k}} . 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 An and Rn is An − Rn = (1 − P)An representing the transients of An which eventually decay to zero. P may be computed as the limit of Anh as n → ∞.

Counterexamples The matrices L = {displaystyle left({begin{smallmatrix}1&0&0\1&0&0\1&1&1end{smallmatrix}}right)} , P = {displaystyle left({begin{smallmatrix}1&0&0\1&0&0\!!!-1&1&1end{smallmatrix}}right)} , T = {displaystyle left({begin{smallmatrix}0&1&1\1&0&1\1&1&0end{smallmatrix}}right)} , M = {displaystyle left({begin{smallmatrix}0&1&0&0&0\1&0&0&0&0\0&0&0&1&0\0&0&0&0&1\0&0&1&0&0end{smallmatrix}}right)} 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 ω = eiπ/3 then ω6 = 1 and the eigenvalues of M are {1,ω2,ω3,ω4} so ω and ω5 are both absent.[citation needed] 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.[33] 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 Min-max theorem Z-matrix (mathematics) M-matrix P-matrix Hurwitz matrix Metzler matrix (Quasipositive matrix) Positive operator Notes ^ Bowles, Samuel (1981-06-01). "Technical change and the profit rate: a simple proof of the Okishio theorem". Cambridge Journal of Economics. 5 (2): 183–186. doi:10.1093/oxfordjournals.cje.a035479. ISSN 0309-166X. ^ Meyer 2000, pp. 8.3.6 p. 681 "Archived copy" (PDF). Archived from the original (PDF) on March 7, 2010. Retrieved 2010-03-07. ^ Meyer 2000, pp. 8.3.7 p. 683 "Archived copy" (PDF). Archived from the original (PDF) on March 7, 2010. Retrieved 2010-03-07. ^ Langville & Meyer 2006, p. 15.2 p. 167 Langville, Amy N.; Langville, Amy N.; Meyer, Carl D. (2006-07-23). Google's PageRank and Beyond: The Science of Search Engine Rankings. ISBN 978-0691122021. Archived from the original on July 10, 2014. Retrieved 2016-10-31. ^ Keener 1993, p. p. 80 ^ Landau, Edmund (1895), "Zur relativen Wertbemessung der Turnierresultaten", Deutsches Wochenschach, XI: 366–369 ^ Landau, Edmund (1915), "Über Preisverteilung bei Spielturnieren", Zeitschrift für Mathematik und Physik, 63: 192–202 ^ Birkhoff, Garrett and Varga, Richard S., 1958. Reactor criticality and nonnegative matrices. Journal of the Society for Industrial and Applied Mathematics, 6(4), pp.354-377. ^ 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. ^ Friedland, S., 1981. Convex spectral functions. Linear and multilinear algebra, 9(4), pp.299-316. ^ Miroslav Fiedler; Charles R. Johnson; Thomas L. Markham; Michael Neumann (1985). "A Trace Inequality for M-matrices and the Symmetrizability of a Real Matrix by a Positive Diagonal Matrix". Linear Algebra and Its Applications. 71: 81–94. doi:10.1016/0024-3795(85)90237-X. ^ Jump up to: a b c d Meyer 2000, pp. chapter 8 page 665 "Archived copy" (PDF). Archived from the original (PDF) on March 7, 2010. Retrieved 2010-03-07. ^ Meyer 2000, pp. chapter 8.3 page 670. "Archived copy" (PDF). Archived from the original (PDF) on March 7, 2010. Retrieved 2010-03-07. ^ Gantmacher 2000, p. chapter XIII.3 theorem 3 page 66 ^ Kitchens, Bruce (1998), Symbolic dynamics: one-sided, two-sided and countable state markov shifts., Springer, ISBN 9783540627388 ^ Minc, Henryk (1988), Nonnegative matrices, John Wiley&Sons,New York, ISBN 0-471-83966-3 ^ Auteur., Gradshtein, Izrailʹ Solomonovich (1899-1958). Table of integrals, series, and products. ISBN 978-0-12-384934-2. OCLC 922964628. ^ Meyer 2000, pp. claim 8.3.11 p. 675 "Archived copy" (PDF). Archived from the original (PDF) on March 7, 2010. Retrieved 2010-03-07. ^ Gantmacher 2000, p. section XIII.5 theorem 9 ^ Meyer 2000, pp. page 679 "Archived copy" (PDF). Archived from the original (PDF) on March 7, 2010. Retrieved 2010-03-07. ^ Meyer 2000, pp. example 8.3.2 p. 677 "Archived copy" (PDF). Archived from the original (PDF) on March 7, 2010. Retrieved 2010-03-07. ^ Gantmacher 2000, p. section XIII.2.2 page 62 ^ Meyer 2000, pp. example 8.3.3 p. 678 "Archived copy" (PDF). Archived from the original (PDF) on March 7, 2010. Retrieved 2010-03-07. ^ Meyer 2000, pp. chapter 8 example 8.3.4 page 679 and exercise 8.3.9 p. 685 "Archived copy" (PDF). Archived from the original (PDF) on March 7, 2010. Retrieved 2010-03-07. ^ Varga 2002, p. 2.43 (page 51) ^ Brualdi, Richard A.; Ryser, Herbert J. (1992). Combinatorial Matrix Theory. Cambridge: Cambridge UP. ISBN 978-0-521-32265-2. ^ Brualdi, Richard A.; Cvetkovic, Dragos (2009). A Combinatorial Approach to Matrix Theory and Its Applications. Boca Raton, FL: CRC Press. ISBN 978-1-4200-8223-4. ^ Mackey, Michael C. (1992). Time's Arrow: The origins of thermodynamic behaviour. New York: Springer-Verlag. ISBN 978-0-387-97702-7. ^ Gantmacher 2000, p. section XIII.2.2 page 54 ^ Smith, Roger (2006), "A Spectral Theoretic Proof of Perron–Frobenius" (PDF), Mathematical Proceedings of the Royal Irish Academy, 102 (1): 29–35, doi:10.3318/PRIA.2002.102.1.29 ^ Meyer 2000, pp. chapter 8 claim 8.2.10 page 666 "Archived copy" (PDF). Archived from the original (PDF) on March 7, 2010. Retrieved 2010-03-07. ^ Meyer 2000, pp. chapter 8 page 666 "Archived copy" (PDF). Archived from the original (PDF) on March 7, 2010. Retrieved 2010-03-07. ^ For surveys of results on irreducibility, see Olga Taussky-Todd and Richard A. Brualdi. References Perron, Oskar (1907), "Zur Theorie der Matrices", Mathematische Annalen, 64 (2): 248–263, doi:10.1007/BF01449896, hdl:10338.dmlcz/104432, S2CID 123460172 Frobenius, Georg (May 1912), "Ueber Matrizen aus nicht negativen Elementen", Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften: 456–477 Frobenius, Georg (1908), "Über Matrizen aus positiven Elementen, 1", Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften: 471–476 Frobenius, Georg (1909), "Über Matrizen aus positiven Elementen, 2", Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften: 514–518 Gantmacher, Felix (2000) [1959], The Theory of Matrices, Volume 2, AMS Chelsea Publishing, ISBN 978-0-8218-2664-5 (1959 edition had different title: "Applications of the theory of matrices". Also the numeration of chapters is different in the two editions.) Langville, Amy; Meyer, Carl (2006), Google page rank and beyond, Princeton University Press, doi:10.1007/s10791-008-9063-y, ISBN 978-0-691-12202-1, S2CID 7646929 Keener, James (1993), "The Perron–Frobenius theorem and the ranking of football teams", SIAM Review, 35 (1): 80–93, doi:10.1137/1035004, JSTOR 2132526 Meyer, Carl (2000), Matrix analysis and applied linear algebra (PDF), SIAM, ISBN 978-0-89871-454-8, archived from the original (PDF) on 2010-03-07 Minc, Henryk (1988), Nonnegative matrices, John Wiley&Sons,New York, ISBN 0-471-83966-3 Romanovsky, V. (1933), "Sur les zéros des matrices stocastiques", Bulletin de la Société Mathématique de France, 61: 213–219, doi:10.24033/bsmf.1206 Collatz, Lothar (1942), "Einschließungssatz für die charakteristischen Zahlen von Matrizen", Mathematische Zeitschrift, 48 (1): 221–226, doi:10.1007/BF01180013, S2CID 120958677 Wielandt, Helmut (1950), "Unzerlegbare, nicht negative Matrizen", Mathematische Zeitschrift, 52 (1): 642–648, doi:10.1007/BF02230720, hdl:10338.dmlcz/100322, S2CID 122189604 Further reading Abraham Berman, Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, 1994, SIAM. ISBN 0-89871-321-8. Chris Godsil and Gordon Royle, Algebraic Graph Theory, Springer, 2001. A. Graham, Nonnegative Matrices and Applicable Topics in Linear Algebra, John Wiley&Sons, New York, 1987. R. A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, 1990 Bas Lemmens and Roger Nussbaum, Nonlinear Perron-Frobenius Theory, Cambridge Tracts in Mathematics 189, Cambridge Univ. Press, 2012. S. P. Meyn and R. L. Tweedie, Markov Chains and Stochastic Stability London: Springer-Verlag, 1993. ISBN 0-387-19832-6 (2nd edition, Cambridge University Press, 2009) Seneta, E. Non-negative matrices and Markov chains. 2nd rev. ed., 1981, XVI, 288 p., Softcover Springer Series in Statistics. (Originally published by Allen & Unwin Ltd., London, 1973) ISBN 978-0-387-29765-1 Suprunenko, D.A. (2001) [1994], "Perron–Frobenius theorem", Encyclopedia of Mathematics, EMS Press (The claim that Aj has order n/h at the end of the statement of the theorem is incorrect.) Varga, Richard S. (2002), Matrix Iterative Analysis (2nd ed.), Springer-Verlag. Categories: Matrix theoryTheorems in linear algebraMarkov processes

Si quieres conocer otros artículos parecidos a **Perron–Frobenius theorem** puedes visitar la categoría **Markov processes**.

Deja una respuesta