Editing Perron–Frobenius theorem (section)

==Statement==
Let [[nonnegative matrix|'''positive''']] and '''non-negative''' respectively describe [[matrix (mathematics)|matrices]] with exclusively [[positive number|positive]] real numbers as elements and matrices with exclusively non-negative real numbers as elements. The [[eigenvalue]]s of a real [[square matrix]] ''A'' are [[complex numbers]] that make up the [[spectrum of a matrix|spectrum]] of the matrix. The [[exponential growth|exponential growth rate]] of the matrix powers ''A''<sup>''k''</sup> as ''k'' → ∞ is controlled by the eigenvalue of ''A'' with the largest [[absolute value]] ([[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===
Let <math>A = (a_{ij}) </math> be an <math> n \times n </math> positive matrix: <math> a_{ij} > 0 </math> for <math> 1 \le i,j \le n </math>. 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''', '''principal eigenvalue''' or '''dominant eigenvalue'''), such that ''r'' is an eigenvalue of ''A'' and any other eigenvalue ''λ'' (possibly [[complex number|complex]]) in [[absolute value]] is strictly smaller than ''r'' , |''λ''| < ''r''. Thus, the [[spectral radius]] <math>\rho(A) </math> 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 ''A<sup>T</sup>'', the transpose of ''A''.)
# There exists an eigenvector ''v'' = (''v''<sub>1</sub>,...,''v''<sub>''n''</sub>)''<sup>T</sup>'' of ''A'' with eigenvalue ''r'' such that all components of ''v'' are positive: ''A v'' = ''r v'', ''v''<sub>''i''</sub> > 0 for 1 ≤ ''i'' ≤ ''n''. (Respectively, there exists a positive left eigenvector ''w'' : ''w<sup>T</sup> A'' = ''w<sup>T</sup>'' r, ''w''<sub>''i''</sub> > 0.) It is known in the literature under many variations as the '''Perron vector''', '''Perron eigenvector''', '''Perron-Frobenius eigenvector''', '''leading eigenvector''', '''principal eigenvector''' or '''dominant eigenvector'''. 
# There are no other positive (moreover non-negative) eigenvectors except positive multiples of ''v'' (respectively, left eigenvectors except ww'w''), i.e., all other eigenvectors must have at least one negative or non-real component.
# <math> \lim_{k \rightarrow \infty} A^k/r^k = v w^T</math>, where the left and right eigenvectors for ''A'' are normalized so that ''w<sup>T</sup>v'' = 1. Moreover, the matrix ''vw<sup>T</sup>'' is the [[Jordan canonical form#Invariant subspace decompositions|projection onto the eigenspace]] corresponding to&nbsp;''r''. This projection is called the '''Perron projection'''.
# '''[[Lothar Collatz|Collatz]]–Wielandt formula''': for all non-negative non-zero vectors ''x'', let ''f''(''x'') be the minimum value of [''Ax'']<sub>''i''</sub> / ''x''<sub>''i''</sub> taken over all those ''i'' such that ''x<sub>i</sub>'' ≠ 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'']<sub>''i''</sub> / ''x''<sub>''i''</sub> taken over ''i''. Then ''g'' is a real valued function whose [[minimum]] over all strictly positive vectors ''x'' is the Perron–Frobenius eigenvalue.
# '''[[Garrett Birkhoff|Birkhoff]]–[[Richard S. Varga|Varga]] formula''': Let ''x'' and ''y'' be strictly positive vectors.  Then,<ref>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.</ref><math display="block">r = \sup_{x>0} \inf_{y>0} \frac{y^\top A x}{y^\top x} = \inf_{x>0} \sup_{y>0} \frac{y^\top A x}{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.</math> 
# '''[[Monroe D. Donsker|Donsker]]–[[S. R. Srinivasa Varadhan|Varadhan]]–[[Shmuel Friedland|Friedland]] formula''': Let ''p'' be a probability vector and ''x'' a strictly positive vector.  Then,<ref>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.</ref><ref>Friedland, S., 1981. Convex spectral functions. Linear and multilinear algebra, 9(4), pp.299-316.</ref> <math display="block">r = \sup_p \inf_{x>0} \sum_{i=1}^n p_i[Ax]_i/x_i.</math> 
# '''[[Miroslav Fiedler|Fiedler]] formula''':<ref>{{cite journal |author1=Miroslav Fiedler |author2=Charles R. Johnson |author3=Thomas L. Markham |author4=Michael Neumann |title=A Trace Inequality for M-matrices and the Symmetrizability of a Real Matrix by a Positive Diagonal Matrix |journal=Linear Algebra and Its Applications |date=1985 |volume=71 |pages=81–94 |doi=10.1016/0024-3795(85)90237-X |doi-access=free }}</ref> <math display="block">r = \sup_{z > 0} \ \inf_{x>0, \ y>0,\ x \circ y = z} \frac{y^\top A x}{y^\top x} = \sup_{z > 0} \ \inf_{x>0, \ y>0,\ x \circ y = z}\sum_{i,j=1}^n y_i a_{ij} x_j/\sum_{i=1}^n y_i x_i.</math>
# The Perron–Frobenius eigenvalue satisfies the inequalities <math display="block">\min_i \sum_{j} a_{ij} \le r \le \max_i \sum_{j} a_{ij}.</math>

All of these properties extend beyond strictly positive matrices to '''primitive matrices''' (see below).  Facts 1–7 can be found in Meyer<ref name="Meyer"/> [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 <math>w^T v=1</math>.

===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.<ref>{{harvnb|Meyer|2000|pp=[http://www.matrixanalysis.com/Chapter8.pdf chapter 8.3 page 670]. {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |access-date=2010-03-07 |url-status=dead |archive-url=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archive-date=March 7, 2010 }}}}</ref><ref>{{harvnb|Gantmacher|2000|p=[https://books.google.com/books?id=cyX32q8ZP5cC&q=preceding%20section&pg=PA66  chapter XIII.3 theorem 3 page 66]}}</ref> However, for the example <math>A = \left(\begin{smallmatrix}0 & 1\\
1 & 0\end{smallmatrix}\right)</math>, the maximum eigenvalue ''r'' = 1 has the same absolute value as the other eigenvalue −1; while for <math>A = \left(\begin{smallmatrix}0 & 1\\
0 & 0\end{smallmatrix}\right)</math>, 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 <math>\omega r</math>, where ''<math>r</math>'' is a real strictly positive eigenvalue, and <math>\omega</math> ranges over the complex ''h''' th [[root of unity|roots of 1]] for some positive integer ''h'' called the [[iterated function|period]] of the matrix.
The eigenvector corresponding to ''<math>r</math>'' 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''&nbsp;×&nbsp;''n'' square matrix over [[field (mathematics)|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 ''F<sup>n</sup>''. More explicitly, for any linear subspace spanned by standard basis vectors ''e''<sub>''i''<sub>1</sub> </sub>, ...,
''e''<sub>''i''<sub>k</sub></sub>, 0&nbsp;< ''k''&nbsp;<&nbsp;''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'':
: <math>PAP^{-1} \ne
\begin{pmatrix} E & F \\ O & G \end{pmatrix},</math>
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]] ''G''<sub>''A''</sub>. It has ''n'' vertices labeled 1,...,''n'', and there is an edge from vertex ''i'' to vertex ''j'' precisely when ''a''<sub>''ij''</sub> ≠ 0. Then the matrix ''A'' is irreducible if and only if its associated graph ''G''<sub>''A''</sub> is [[strongly connected component|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 <math>(\mathbb R, +)</math> on <math>\mathbb{R}^n</math> or <math>(\mathbb C, +)</math> on <math>\mathbb{C}^n</math> given by <math>t \mapsto\exp(tA)</math> 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 ''m''th power is positive for some natural number ''m'' (i.e. all entries of ''A<sup>m</sup>'' 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 (''A''<sup>''m''</sup>)<sub>''ii''</sub> > 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''<sub>''A''</sub> (see Kitchens<ref name="Kitchens"/> page 16). The period is also called the index of imprimitivity (Meyer<ref name="Meyer"/> 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 <math>A</math> be an irreducible non-negative <math>N\times N</math> matrix with period <math>h</math> and [[spectral radius]] <math>\rho(A) = r</math>. 
Then the following statements hold.

* The number <math>r\in\mathbb{R}^+</math> is a positive real number and it is an eigenvalue of the matrix <math>A</math>. It is called '''Perron–Frobenius eigenvalue'''.
* The Perron–Frobenius eigenvalue <math>r</math> is [[Eigenvalues and eigenvectors#Algebraic multiplicity|simple]]. Both right and left eigenspaces associated with <math>r</math> are one-dimensional.
* <math>A</math> has both a right and a left eigenvectors, respectively <math>\mathbf v</math> and <math>\mathbf w</math>, with eigenvalue <math>r</math> and whose components are all positive. Moreover the '''only''' eigenvectors whose components are all positive are those associated with the eigenvalue <math>r</math>.
* The matrix <math>A</math> has exactly <math>h</math> (where <math>h</math> is the '''period''') complex eigenvalues with absolute value <math>r</math>. Each of them is a simple root of the characteristic polynomial and is the product of <math>r</math> with an <math>h</math>th [[root of unity]].
* Let <math>\omega = 2\pi/h</math>. Then the matrix <math>A</math> is [[similar matrix|similar]] to <math>e^{i\omega}A</math>, consequently the spectrum of <math>A</math> is invariant under multiplication by <math>e^{i\omega}</math> (i.e. to rotations of the complex plane by the angle <math>\omega</math>).
* If <math>h>1</math> then there exists a permutation matrix <math>P</math> such that
::<math>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 & O
\end{pmatrix},
</math>
::
where <math>O</math> denotes a zero matrix and the blocks along the main diagonal are square matrices.

* '''[[Lothar Collatz|Collatz]]–Wielandt formula''': for all non-negative non-zero vectors ''<math>\mathbf x
</math>'' let ''<math>f(\mathbf x)
</math>'' be the minimum value of ''<math>[A\mathbf x]_i/x_i
</math>'' taken over all those <math>i
</math> such that <math>x_i\neq0
</math>. Then <math>f
</math> is a real valued function whose [[maximum]] is the Perron–Frobenius eigenvalue.

* The Perron–Frobenius eigenvalue satisfies the inequalities
::<math>\min_i \sum_{j} a_{ij} \le r \le \max_i \sum_{j} a_{ij}.</math>

The example <math>A =\left(\begin{smallmatrix}
0 & 0 & 1 \\
0 & 0 & 1 \\
1 & 1 & 0 
\end{smallmatrix}\right)</math> shows that the (square) zero-matrices along the diagonal may be of different sizes, the blocks ''A''<sub>''j''</sub> need not be square, and ''h'' need not divide&nbsp;''n''.

===Further properties===
Let ''A'' be an irreducible non-negative matrix, then:
# (I+''A'')<sup>''n''−1</sup> is a positive matrix. (Meyer<ref name="Meyer"/> [https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf claim 8.3.5 p. 672]). For a non-negative ''A'', this is also a sufficient condition.<ref name="Minc">{{cite book |first=Henryk |last= Minc |author-link=Henryk Minc |title=Nonnegative matrices |isbn=0-471-83966-3 |year=1988 |publisher=John Wiley & Sons |location=New York |page=6 [Corollary 2.2] }}</ref>
# Wielandt's theorem.<ref>{{Cite book |author=Gradshtein, Izrailʹ Solomonovich |url=http://worldcat.org/oclc/922964628 |title=Table of integrals, series, and products |date=18 September 2014 |publisher=Elsevier |isbn=978-0-12-384934-2 |oclc=922964628}}</ref>{{clarify|reason=What are the restrictions on ''B''?|date=March 2015}} If |''B''|<''A'', then ''ρ''(''B'')≤''ρ''(''A''). If equality holds (i.e. if ''μ=ρ(A)e<sup>iφ</sup>'' is eigenvalue for ''B''), then ''B'' = ''e''<sup>''iφ''</sup> ''D AD''<sup>−1</sup> for some diagonal unitary matrix ''D'' (i.e. diagonal elements of ''D'' equals to ''e''<sup>''iΘ''<sub>''l''</sub></sup>, non-diagonal are zero).<ref name="Meyer675">{{harvnb|Meyer|2000|pp=[http://www.matrixanalysis.com/Chapter8.pdf claim 8.3.11 p. 675] {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |access-date=2010-03-07 |url-status=dead |archive-url=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archive-date=March 7, 2010 }}}}</ref>
# If some power ''A<sup>q</sup>'' is reducible, then it is completely reducible, i.e. for some permutation matrix ''P'', it is true that: <math>
P A^q P^{-1}= \begin{pmatrix}
A_1 & O & O & \dots & O \\
O & A_2 & O & \dots & O \\
\vdots & \vdots & \vdots & & \vdots \\
O & O & O & \dots & A_d \\
\end{pmatrix}
</math>, where ''A<sub>i</sub>'' are irreducible matrices having the same maximal eigenvalue. The number of these matrices ''d'' is the greatest common divisor of ''q'' and ''h'', where ''h'' is period of ''A''.<ref>{{harvnb|Gantmacher|2000|p=section XIII.5 theorem 9}}</ref>
# If ''c''(''x'') ''= x<sup>n</sup> + c<sub>k<sub>1</sub></sub> x<sup>n-k<sub>1</sub></sup> + c<sub>k<sub>2</sub></sub> x<sup>n-k<sub>2</sub></sup> + ... + c<sub>k<sub>s</sub></sub> x<sup>n-k<sub>s</sub></sup>'' is the characteristic polynomial of ''A'' in which only the non-zero terms are listed, then the period of ''A'' equals the greatest common divisor of ''k<sub>1</sub>, k<sub>2</sub>, ... , k<sub>s</sub>''.<ref>{{harvnb|Meyer|2000|pp=[http://www.matrixanalysis.com/Chapter8.pdf page 679] {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |access-date=2010-03-07 |url-status=dead |archive-url=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archive-date=March 7, 2010 }}}}</ref>
# [[Cesàro summation|Cesàro]] [[summability theory|averages]]: <math> \lim_{k \rightarrow \infty} 1/k\sum_{i=0,...,k} A^i/r^i = ( v w^T),</math> where the left and right eigenvectors for ''A'' are normalized so that ''w''<sup>''T''</sup>''v'' = 1. Moreover, the matrix ''v w<sup>T</sup>'' is the [[Spectral theorem|spectral projection]] corresponding to ''r'', the Perron projection.<ref>{{harvnb|Meyer|2000|pp=[http://www.matrixanalysis.com/Chapter8.pdf example 8.3.2 p. 677] {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |access-date=2010-03-07 |url-status=dead |archive-url=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archive-date=March 7, 2010 }}}}</ref>
# Let ''r'' be the Perron–Frobenius eigenvalue, then the adjoint matrix for (''r''-''A'') is positive.<ref>{{harvnb|Gantmacher|2000|p=[https://books.google.com/books?id=cyX32q8ZP5cC&q=preceding%20section&pg=PA62 section XIII.2.2 page 62]}}</ref>
# If ''A'' has at least one non-zero diagonal element, then ''A'' is primitive.<ref>{{harvnb|Meyer|2000|pp= [http://www.matrixanalysis.com/Chapter8.pdf example 8.3.3 p. 678] {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |access-date=2010-03-07 |url-status=dead |archive-url=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archive-date=March 7, 2010 }}}}</ref>
# If 0 ≤ ''A'' < ''B'', then ''r''<sub>''A''</sub> ≤ ''r''<sub>''B.''</sub> Moreover, if ''B'' is irreducible, then the inequality is strict: ''r<sub>A</sub> < r<sub>B</sub>''.

A matrix ''A'' is primitive provided it is non-negative and ''A<sup>m</sup>'' is positive for some ''m'', and hence ''A<sup>k</sup>'' is positive for all ''k ≥ m''. To check primitivity, one needs a bound on how large the minimal such ''m'' can be, depending on the size of ''A'':<ref>{{harvnb|Meyer|2000|pp=[http://www.matrixanalysis.com/Chapter8.pdf chapter 8 example 8.3.4 page 679 and exercise 8.3.9 p.&nbsp;685] {{cite web |url=http://www.matrixanalysis.com/Chapter8.pdf |title=Archived copy |access-date=2010-03-07 |url-status=dead |archive-url=https://web.archive.org/web/20100307021652/http://www.matrixanalysis.com/Chapter8.pdf |archive-date=March 7, 2010 }}}}</ref>
* If ''A'' is a non-negative primitive matrix of size ''n'', then ''A''<sup>''n''<sup>2</sup>&nbsp;−&nbsp;2''n''&nbsp;+&nbsp;2</sup> is positive. Moreover, this is the best possible result, since for the matrix ''M'' below, the power ''M<sup>k</sup>'' is not positive for every ''k'' < ''n''<sup>2</sup>&nbsp;−&nbsp;2''n''&nbsp;+&nbsp;2, since (''M''<sup>''n''<sup>2</sup>&nbsp;−&nbsp;2''n''+1</sup>)<sub>1,1</sub> = 0.
:<math>M=
\left(\begin{smallmatrix}
0 & 1 & 0 & 0 & \cdots & 0 \\
0 & 0 & 1 & 0 & \cdots & 0 \\
0 & 0 & 0 & 1 & \cdots & 0 \\
\vdots & \vdots & \vdots & \vdots & & \vdots \\
0 & 0 & 0 & 0 & \cdots & 1 \\
1 & 1 & 0 & 0 & \cdots & 0
\end{smallmatrix}\right)
</math>