Hostname: page-component-848d4c4894-8bljj Total loading time: 0 Render date: 2024-07-05T04:08:35.241Z Has data issue: false hasContentIssue false
  • English
  • Français

The Exponent of a Primitive Matrix*

Published online by Cambridge University Press:  20 November 2018

A. L. Dulmage  and
N. S. Mendelsohn
A. L. Dulmage
Affiliation:
University of Manitoba
N. S. Mendelsohn
Affiliation:
University of Manitoba
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let A be an n by n matrix with non-negative entries. If a permutation matrix P exists such that P-1 is of the form

where A and C are square matrices and O is a zero-matrix then A is said to be reducible. Otherwise, A is irreducible. If A is irreducible, then A is said to be primitive if there is an integer k such that Ak0, i.e., Ak has no zero entries. If A is primitive, the least integer m for which Am0 is called the exponent of A. In (4), Wielandt has shown that for n by n primitive matrices the exponent is at most (n-1)2+1. In this paper, the theory of directed graphs is used to determine conditions under which the exponent is less than (n-1)2+1. The following results are obtained. If A contains r non-zero entries along its main diagonal then its exponent is at most 2n-r-1, and this result is the best possible. If all the diagonal entries of A are zero but its graph KA (see next section for definition) contains a cycle of length d, then the exponent of A is at most d(2n-d-1). For the case where this improves Wielandt's result.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 5 , Issue 3 , September 1962 , pp. 241 - 244
Copyright
Copyright © Canadian Mathematical Society 1962

Footnotes

*

This research was supported by the United States Air Force Office of Scientific Research.

References

1. Dulmage, A.L., Johnson, D.M. and Mendelsohn, N.S., Connectivity and Reducibility of Graphs, Can. J. Math., 14, 1962, 529-539.Google Scholar
2. Dulmage, A.L. and Mendelsohn, N.S., Non Negative Matrices, to appear in Can. J. Math.Google Scholar
3. Herstein, I., A Note on Primitive Matrices, Amer. Math. Monthly, 61, 1954, 18-20.Google Scholar
4. Wielandt, H., Unzerlegbare, Nicht Negative Matrizen, Mathematische Zeitschrift, 52, 1950, 642-648.Google Scholar