**THE PERRON-FROBENIUS THEOREM**

.

**INTRODUCTION**

The projects in this collection are concerned with models from many
different areas; that is part of their purpose, to show that linear algebra
is a broadly applicable branch of mathematics. If one reviews them as a
whole, they do have a couple of common mathematical characteristics: eigenvalues
are very useful and the matrices studied are almost all nonnegative (all
entries in them 0 or greater). To be a bit more precise about the former,
it is often only the largest, or *dominant*, eigenvalue that we need
to know.

This makes life much easier. Computing *all* the eigenvalues of
a matrix may be a difficult task. For a 10x10 matrix from a population
model, Maple often has trouble computing all of them. Yet we only need
one of the 10 and the methods shown in Project #5 work
reliably.

The mathematical question that all of this raises is: how do we know
if the dominant eigenvalue of a matrix is __positive__? Another question
is: could there ever be positive and negative eigenvalues of the same size?
If so, the behavior of the associated system could be quite different.
The answer to this question is yes, as is shown in problem 3 of** **Project
#5

Both of these questions are answered by the Perron-Frobenius Theorem
for nonnegative matrices. The results of the theorem depend upon what kind
of nonnegative matrix one has. The first kind we look at are called*
irreducible*.

**DEFINITION** An nxn nonnegative matrix A is said to be *irreducible*
if there is no permutation of coordinates such that

where P is an nxn permutation matrix (each row and each column have
exactly one 1 entry and all others 0), A_{11} is rxr, and A_{22}
is (n-r)x(n-r). This is not a particularly inspiring definition in view
of the fact it only tells us what is NOT irreducible. About the only thing
we know for sure is that a matrix with __all __positive entries is irreducible.

To clarify the notion of irreducibility, we examine it in three different contexts:

1. **Markov Chains**. Suppose A is the transition matrix of a Markov
chain. Then it is nonnegative and suppose further it is set up so that

a_{ij}
= the probability of going from state j to state i

in one transition

If one looks at, say, the fourth row of A, then one sees the probabilities of going from state 4 to the various other states (as well as remaining in state 4). Any entry that is zero indicates that one cannot go to that state from state 4, at least in one step.

Now if A is reducible, for instance,

then we can see that it is possible to go from states 1,2 or 3 to any states but only from states 4 or 5 to themselves. This is, of course, the traditional definition of "absorbing" states in a Markov Chain. The above mentioned permutation matrix P simply amounts to labeling the states so the absorbing ones are last.

2. **Graphs**. If we considered directed graphs then each has associated
with it a nonnegative matrix with all entries 0 or 1 with

a_{ij}
= 1 if there is an arc from vertex i to vertex j.

If the associated matrix is irreducible then one can get from any vertex to any other vertex (perhaps in several steps) whereas if it is reducible then (like the Markov Chain case), there are vertices from which one cannot travel to all other vertices.

The former case, in the realm of graph theory, is called a "strongly connected" graph.

3. **Dynamical Systems**. Suppose, as in the population case we have
a system of the form

** x**(k+1)
= A **x**(k) k=0,1,...

and that A is reducible as in the definition above. Then in the manner of partitioned matrices, one can rewrite this system as

** Y**(k+1)
= A_{11} **Y**(K) + A_{12} **Z**(k)

** Z**(k+1)
= A_{22} **Z**(k)

where **Y** has the first r components of **X **and **Z** has
the last n-r so together they comprise the original vector **X**. (The
reader who has either not worked with partitioned matrices or is rusty
on the subject is urged to sketch the details out at the component level
and verify it; the result should follow in a straightforward manner.) While
this may not seem helpful at first glance, it means the solution for **Z**
may be obtained first, with no reference to the system governing **Y**,
and then the solution for **Y **obtained from the (nonhomogeneous) system
that treats **Z** as known. In the early language of such a problem,
the original system has been "reduced" to two simpler systems.
To physicists, it has been partially *decoupled*.

Saying, then, that the matrix A is irreducible means that the system
cannot be reduced; it must be treated *as a whole* in studying its
behavior.

While the above discussion may clarify the notion of an irreducible
matrix, it is not much help in verifying that a given matrix actually *is*
irreducible. For example, it is not blatantly obvious that of the two following
matrices

the latter is irreducible while the former is not. If we went strictly by the definition, we would have to keep trying permutations and looking for the critical zero submatrix to appear. But for an nxn matrix there are, of course, n! possible such matrices P making for a great deal of work ( if A is 10 x 10 then there are over 3 million possibilities!).

The following theorem is thus quite direct and helpful.

**THEOREM**. A is a nonnegative irreducible nxn matrix if and only
if

(I_{n}
+ A)^{n-1} > 0. (see
**[12],** p.6 for details and proof)

We note that the power in the above expression contains the same n as
in the size of the matrix. Since computer software is readily available
to compute matrix powers, the above may be readily checked. Note the result
is also an nxn matrix, and if __any__ entry is zero, then the contrapositive
of the theorem says A is __reducible. __Referring to the two matrices
above, we find that by direct computation

At this point, it seems appropriate to finally state the

**PERRON-FROBENIUS THEOREM FOR IRREDUCIBLE MATRICES**

If A is nxn, nonnegative, irreducible, then

** 1**.
one of its eigenvalues is positive and greater than or equal to (in absolute
value) all other eigenvalues

** 2**.
there is a positive eigenvector corresponding to that eigenvalue

and **3**. that eigenvalue is a simple root of
the characteristic equation of A.

Such an eigenvalue is called the "dominant eigenvalue" of A and we assume hereafter we have numbered the eigenvalues so it is the first one. We should point out that other eigenvalues may be positive, negative or complex (and if they are complex then by "absolute value" we mean modulus, or distance in the complex plane from the origin). Complex eigenvalues are a real possibility as only symmetric matrices are guaranteed to not have them, and very few of the matrices we have been discussing, in application, will be symmetric with the notable exception of undirected graphs. Part 3 of the theorem also merits brief comment. One ramification of it is that the dominant eigenvalue cannot be a multiple root. One will not be left with the classic situation of having more roots than corresponding linearly independent eigenvectors and hence having to worry about or calculate generalized eigenvectors and/or work with Jordan blocks. The same may not be said for the other eigenvalues of A but in the models here, they do not concern us.

**Primitive Matrices and the Perron-Frobenius Theorem **

Irreducible matrices are not the only nonnegative matrices of possible interest in the models we have looked at. Suppose we have a dynamical system of the form

** x**(k+1)=A**x**(k)

where

(this matrix, while containing many suspicious looking zeroes, is indeed
irreducible. The easiest way to see this is to construct the associated
graph for it and check that you can get from any vertex to any other vertex.)We
calculate that its dominant eigenvalue is 1.653 and that an associated
eigenvector is (.29,.48,.29,.35,.5,.48)^{t} so based upon the above
discussion, we believe the long term behavior of the system to be of the
form:

** x**(k) = c_{1 }(1.653)^{k
}(.29,.48,.29,.35,.5,.48)^{t} (c_{1}
determined from initial conditions)

Simulation of the system is, of course, quite easy as one just needs to keep multiplying the current solution by A to get the solution one time period later. However, in this case, doing so does not seem to validate the predicted behavior and in fact does not even seem to show any sort of limit at all! (the reader is encouraged to fire up some software, pick an initial condition and see this behavior).

So what went wrong? If one calculates all of the eigenvalues for the matrix, they turn out to be: 1.653,0,0,+\- .856i and -1.653. The latter is where the limit problem arises; since we are taking integral powers of the eigenvalues, we get an algebraic "flip-flop" effect:

** x**(k)
= c_{1} (1.653)^{k} e_{1} + **... **+ c_{6}
(-1.653)^{k} e_{6}

(It is, by the way, a known result that an irreducible matrix cannot
have two independent eigenvectors that are both nonnegative; see **[16],**
chapter 2. Thus e_{6} in the above expansion has components of
mixed sign.)

Thus 1.653 did not turn out to be as neatly "dominant" as
we would have liked. If we look back at the statement of the Perron-Frobenius
Theorem, we see it guaranteed a positive eigenvalue (with positive eigenvector)
with absolute value greater than **or equal** to that of any other eigenvalue.
In the example just considered, the equality was met.

So the question comes up: what *stronger* condition than irreducibility
should one impose so that a nonnegative matrix has a truly dominant eigenvalue;
*strictly* greater in absolute value than any other eigenvalue? The
answer is that the matrix needs to be "primitive". While there
are several possible definitions of "primitive", most of which
have a graphical context in terms of cycles, we will state a more general,
algebraic definition as the models we may wish to look at are from a diverse
group.

**DEFINITION **An nxn nonnegative matrix A is primitive iff A^{k}
> 0 for some power k.

We note the __strict__ inequality; all n^{2} entries of A^{k
}have to be positive for some power. Such a condition, again considering
the availability of computer software and ease of use, is easy to check.
If one experiments with the 6x6 from the last example, one never finds
a power where all 36 entries are positive. The question might come up:
how many powers

of A does one have to look at before concluding it is **not **primitive?
If A is primitive then the power which should have all positive entries
is less than or equal to **n ^{2} -2n +2** (this is due to Wielandt
in 1950, see [

**PERRON-FROBENIUS THEOREM FOR PRIMITIVE MATRICES **

If A is an** nxn** nonnegative primitive matrix then

1. one of its eigenvalues is positive and greater than (in absolute value) all other eigenvalues

2. there is a positive eigenvector corresponding to that eigenvalue

3. that eigenvalue is a simple root of the characteristic equation of A.

**OTHER APPLICATIONS**

In addition to the various projects, some other applications which involve the Perron Frobenious Theorem desire mention:

**Application #1:** Ranking of Football Teams.

James P. Keener has developed several models of schemes for ranking
college football teams which may be found in** [6].**

**Application #2:** Graphs**.**

In general, it should be remarked that graph theory and nonnegative matrices have a very strong relationship and that the Perron-Frobenius Theorem is often a powerful tool in graph theory. The interested reader is referred to, for example, the excellent books by Minc and Varga for an in depth discussion.

As stated above, a graph (directed or not) has associated with it a nonnegative, "adjacency" matrix whose entries are 0s and 1s. A fundamental result about lengths of cycles in the graph may be obtained by determining whether the matrix is primitive or not. The very elegant result which occurs with the help of the Perron-Frobenius Theorem is this:

* if the matrix is primitive (hence a dominant eigenvalue with absolute value strictly greater than that of all other eigenvalues) then the greatest common divisor (gcd) of the lengths of all cycles is 1

* if the matrix is irreducible but not primitive then the greatest common divisor of the lengths of all cycles is the same as the number of eigenvalues with magnitude the same as the dominant eigenvalue (and including it).

It is common to refer to graphs with matrices which are irreducible but not primitive, naturally, as imprimitive and aforementioned gcd. as the index of the graph. It should also be mentioned that the collection of such eigenvalues lie equally spaced in the complex plane on a circle of radius equaling the dominant eigenvalue.

The interested reader is encouraged to examine the following pair of graphs in light of this result:

In the case of the first graph, the eigenvalues are 1,i,-i, and -1 while in the second graph they are 1.221, -.248 +/-1.034i, and -.724, consistent with the gcd of paths for graph 1 being 4 and the gcd of paths for graph 2 being 1.

**Conclusion**

The Perron-Frobenius Theorem has proven to be a consistently powerful result for examining certain nonnegative matrices arising in discrete models. It has been shown that careful consideration need be given to what hypothesis is used; depending on whether one has an irreducible or primitive matrix. In applications, knowledge of the dominant eigenvalue and eigenvector is very helpful and also attainable while knowledge of the rest of the "spectrum" is both unnecessary and computationally extensive.

**Acknowledgment**

The author wishes to thank Dr. Kenneth Lane of KDLLabs, Satellite Beach, Florida, for many inspiring insights and conversations concerning the power and richness of the Perron-Frobenius Theorem.

**REFERENCES**

1. Berman, A. and Plemmons R. 1979. *Nonnegative Matrices in the Mathematical Sciences.*
New York: Academic Press.

2. Chartrand, G. 1977.* Graphs as Mathematical Models*. Boston:
Prindle, Weber and Schmidt.

3. Gould, Peter. 1967. The Geographic Interpretation of Eigenvalues.*Transactions
of the Institute of British Geographers* 42:
53-85.

4. Goulet, J. 1982. Mathematical Systems Analysis - A Course. *The
UMAP Journal ***3**(4):395-406.

6. Keener, James P., 1993. The Perron-Frobenius Theorem and the Ranking
of Football Teams. *SIAM Review* **35**(1): 80-93.

7. Kemeny, John and Snell, Laurie. 1960. *Finite Markov Chains*.
New York: Van Nostrand Reinhold.

8. Lane,Kenneth D.. 1983. Computing the Index of a Graph*.Congressus
Numerantium,*** 40**,143-154

9. Luenberger, D.G. 1979. *Dynamic Systems*. New York: John Wiley.

11. Maki, D.P. and Thompson, M. 1973. *Mathematical Models and Applications*.
Englewood Cliffs, New Jersey: Prentice-Hall.

12. Minc, Henryk.1988. *Nonnegative Matrices*. New York: John Wiley
and Sons.

14. Straffin, Philip D. 1980. Linear Algebra in Geography: Eigenvectors
of Networks. *Mathematics Magazine*
**53**(5): 269-276.

16. Varga, Richard S. 1962. *Matrix Iterative Analysis*. Englewood
Cliffs N.J.: Prentice-Hall.

17. Wielandt,H. 1950. "Unzerlegbare nicht negativen Matrizen"
*Math. Z*. **52**, 642-648.