Editing Perron–Frobenius theorem (section)

===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''.