ON THE EXPONENT OF R-REGULAR PRIMITIVE MATRICES ∗

Abstract. Let Pnr be the set of n-by-n r-regular primitive (0, 1)-matrices. In this paper we find an explicit formula in terms of n and r for the minimum exponent achieved by matrices in Pnr. Moreover, we give matrices achieving that exponent. Gregory and Shen [6] conjectured that bnr = ⌊ n r ⌋2 +1 is an upper bound for the exponent of matrices in Pnr. We present matrices achieving the exponent bnr when n is not a multiple of r. In particular, we show that b2r+1,r is the maximum exponent attained by matrices in P2r+1,r. When n is a multiple of r we conjecture that the maximum exponent achieved by matrices in Pnr is strictly smaller than bnr and give matrices attaining the conjectured maximum exponent in that set. We also show that our conjecture is true when n = 2r. Key words. r-regular matrices, primitive matrices, exponent of primitive matrices. AMS subject classifications. 05C20, 05C50, 15A36. 1. Introduction. A