A system of gaps in the exponent set of primitive matrices
Mordechai Lewin, Yehoshua Vitek · Illinois Journal of Mathematics · 1981
A matrix is nonnegative (positive) if all its entries are nonnegative (positive).A nonnegativ square matrix A is primitive if A k > 0 for some positive integer k.The smallest such k for the given matrix A is ,(A), the exponent (of primitivity) of A. Since 1950 when Wielandt [10] first proclaimed the exact general upper bound for 5,, there has been a considerable number of papers establishing bounds for special families of primitive matrices.The interested reader is referred to [1], [2], [3], [4], [6], all of which use graph theory as a major tool in the search for V.In [2] Dulmage and Mendelsohn reveal what they refer to as gaps in the exponent set of primitive matrices.Each gap is a set S of consecutive integers below Wielandt's general bound W n 2 2n + 2, such that no n-square pri- mitive matrix has an exponent in S. The gaps displayed are n 2-3n+4<,<(n-1)2 and n 2-4n+6<v<n 2-3n+2.For even n a gap contains the union of the two gaps just mentioned" n 2 4n + 6 < , < (n 1)2.It is the purpose of this paper to disclose a system of such gaps containing the two general gaps just mentioned as special eases.We show that for any integral n and there is no primitive matrix A of order n for whichFor 3, 4 these are the gaps shown in [2].For even n an additional gap is supplied indicating how further gaps may be obtained. Definitions and notationsLet G(A) be the directed graph defined by the nonnegative matrix A. A graph is primitive with exponent V, if it is a graph of a primitive matrix with exponent V. Let L(G) denote the set of lengths of the simple circuits of G and let 2(G) denote the number of the distinct lengths.It is well known that G is primitive if and only if it is strongly connected and g.c.d.{c c 6 L(G)} 1.