Portal de Periódicos da CAPES

The Exponent of a Primitive Matrix *

1962; Cambridge University Press; Volume: 5; Issue: 3 Linguagem: Inglês

10.4153/cmb-1962-023-2

1496-4287

A. L. Dulmage, N. S. Mendelsohn,

Graph Labeling and Dimension Problems

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 A k 0, i.e., A k has no zero entries. If A is primitive, the least integer m for which A m 0 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 K A (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.