t there exists an eigenpair such that, where and. Let. It’s impossible that

for all j, for this would make

for all j. However, it’s clear that when.

Therefore, there exists some xj such that. (if not, then consider). Suppose

and t is obtained at. Let, then for all i. Either or there exists some n such that. Since if for all i, then let m be the index of the element with non-zero imaginary part. For any,

If, then according to lemma 2.5, there exists such that

It follows that, a contradiction.

The case for is similar.

If, then there exists some p such that. Let,. Require to be sufficiently small so that is still a positive vector. It follows that for any,

. But according to lemma 2.5, for any, there exists such that . Then. This again results in a contradiction, and hence the eigenpair does not exist.

Remark. The previous lemmas imply that if is the unique positive eigenpair of, then is equal to the spectral radius of A (since if is any eigenpair corresponding to an eigenvalue of the maximum absolute value, then it can be shown that is an eigenpair with positive eigenvector, and the above lemmas will then imply that.)

Lemma 2.7. The matrix

has a simple eigenvalue n and eigenvalue 0 with algebraic multiplicity. In addition, the eigenvector associated with n is positive.

Proof. Since, n is an eigenvalue of D. Likewise, are independent eigenvectors of D associated with the eigenvalue 0. So 0 is an eigenvalue for D with multiplicity. Since an matrix have only n eigenvalues, these are all the eigenvalues of D. Therefore, the eigenvalue of the greatest absolute value of D is positive and simple, and its corresponding eivenvector has positive entries.

Theorem 2.1. Let A be any positive matrix. Then A has a positive simple maximal eigenvalue r such that any other eigenvalue λ satisfies and a unique positive eigenvector v corresponding to r. In addition, this unique positive eigenpair, , can be found by following the maximal eigenpair curve of the family of matrices

where D is the matrix with defined in lemma 2.7.

Proof. The first part of the statement of the theorem follows from the previous lemmas. We will denote the eigenpair of the matrix D by and .

, , are all positive matrices. We will now examine the eigencurves, where

is a particular eigenvalue for, and is an eigenvector associated with it. The eigencurve starting at is not going to intersect any other eigencurve at any time and remains to be the largest eigenvalue. Therefore, the unique positive eigenpair, of the matrix A, can be found by following the maximal eigenpair curve.

Theorem 2.2. An estimate of r is given by:

Proof. Suppose

then

Therefore

Remark. This completes the proof of Perron-Frobenius theorem for positive matrices. The proof can be modified to prove the more general case for irreducible non-negative matrices. For example, this can be done by letting, where D is the matrix defined in Lemma 2.7. As we noted in the introduction, we will next demonstrate how to use homotopy method to find the largest eigenvalue of a positive matrix A numerically.

3. Numerical Example

In this section we use the homotopy method to approximate the positive eigenpair of the matrix:

starting with the 5 × 5 matrix D of all entries ones. In [12] it is shown that the homotopy curves that connect the eigenpairs of the starting matrix D and those of A can be followed using Newton’s method. We use these techniques to follow the eigencurve associated with the largest eigenvalue of D. While [12] finds all the eigenvalues of tridiagonal symmetric matrices, the method works well in approximating the largest eigenvalue when it is applied to any positive matrix due to the separation of its eigencurves (see [12] for details).

The eigenpath of, shown in Figure 1, is constructed using the numerical results presented in the following table:

4. An Application to Positive Interval Matrices

To differentiate ordinary matrices in the previous sections from interval matrices, we will call them point matrices in this section. As stated in Section 1.2, an interval matrix is of the form, where and

are point matrices.

Definition 4.1. We call A a positive interval matrix if and are positive. The set E is Perron’s interval eigenvalue of A if E consists of all positive real maximal eienvalues of all the positive point matrices B with.

We are interested in determing Perron’s interval eigenvalue E of A. We’ll show that if s = the Perron’s eigenvalue of, t = the Perron’s eigenvalue of, then. Therefore, we can approximate E using the Homotopy method introduced in this paper.

Lemma 4.1. Let B be an positive point matrix with Perron’s eigenpair, and C be an positive point matrix with Perron’s eigenpair. Suppose for all, then.

Proof. Let, and suppose the maximum is obtained when. Then

Figure 1. The maximal eigenvalue path for A.

Theorem 4.1. Let be a positive interval matrix, and E is its Perron’s interval eigenvalue. Suppose the Perron’s eigenvalue of, the Perron’s eigenvalue of, then.

Proof. For any and, we have. Suppose is the Perron’s eigenvalue of B, then from the previous lemma. Therefore.

Let. Define the function to be:

Then and. Since f is continuous, then from the Intermediate Value Theorem, for all there’s some such that. Therefore.

It follows that

Remark. Theorem 4.1 shows that in order to find the Perron’s interval eigenvalue E of A, we only need to find the Perron’s eigenvalues of and, which can be approximated using the technique introduced in the previous section.

5. Acknowledgements

This research was partially carried out by two students: Yun Cheng and Timothy Carson, under the supervision of Professor M. B. M. Elgindi, and was partially sponsored by the NSF Research Experience for Undergraduates in Mathematics Grant Number: 0552350 and the Office of Research and Sponsored Programs at the University of Wisconsin-Eau Claire, Eau Claire, Wisconsin 54702-4004, USA.

REFERENCES

  1. O. Perron, “The Theory of Matrices,” Mathematical Annalem, Vol. 64, No. 2, 1907, pp. 248-263.
  2. G. Frobenius, “About Arrays of Non-negative Elements,” Reimer, Berlin, 1912.
  3. S. U. Pillai, T. Suel and S. Cha, “The Perron-Frobenius Theorem: Some of Its Applications,” IEEE in Signal Processing Magazine, Vol. 22, No. 2, 2005, pp. 62-75.
  4. J. Rohn, “Explicit Inverse of an Interval Matrix with Unit Midpoint,” Electronic Journal of Linear Algebra, Vol. 22, 2011, pp. 138-150.
  5. J. Rohn, “A Handbook of Results on Interval Linear Problems,” 2005. http://uivtx.cs.cas.cz/ rohn/publist/!handbook.pdf
  6. F. R. Gantmache, “The Theory of Matrices, Volume 2,” AMS Chelsea Publishing, Providence, 2000.
  7. University of Nebraska-Lincoln, “Proof of Perron-Frobenius Theorem,” 2008. http://www.math.unl.edu/~bdeng1/Teaching/math428/Lecture%20Notes/PFTheorem.pdf
  8. A. Borobia and U. R. Trfas, “A Geometric Proof of the Perron-Frobenius Theorem,” Revista Matematica de la, Vol. 5, No. 1, 1992, pp. 57-63.
  9. H. Samelson, “On the Perron-Frobenius Theorem,” The Michigan Mathematical Journal, Vol. 4, No. 1, 1957, pp. 57-59.
  10. T. Zahng, K. H. Law and G. H. Golub, “On the Homotopy Method for Symmetric Modified Generalized Eigenvalue Problems,” 1996. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.7261
  11. M. T. Chu, “A Note on the Homotopy Method for Linear Algebraic Eigenvalue Problems,” North Carolina State University, Raleigh, 1987.
  12. P. Brockman, T. Carson, Y. Cheng, T. M. Elgindi, K. Jensen, X. Zhoun and M. B. M. Elgindi, “Homotopy Method for the Eigenvalues of Symmetric Tridiagonal Matrices,” Journal of Computational and Applied Mathematics, Vol. 237, No. 1, 2012, pp. 644-653. doi:10.1016/j.cam.2012.08.010

NOTES

*Sponsored by NSF Grant Number: 0552350.

Journal Menu >>