The Exponent of a Primitive Matrix*

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

Canadian mathematical bulletin, Tome 5 (1962) no. 3, pp. 241-244

Résumé

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.

Détail

DOI : 10.4153/CMB-1962-023-2