On the exponent of R-regular primitive matrices

Abstract

Let P_nr be the set of n-by-n r-regular primitive (0, 1)-matrices. In this paper, an explicit formula is found in terms of n and r for the minimum exponent achieved by matrices in P_nr. Moreover, matrices achieving that exponent are given in this paper. Gregory and Shen conjectured that b_nr = (n/r)² + 1 is an upper bound for the exponent of matrices in P_nr. Matrices achieving the exponent bnr are presented for the case when n is not a multiple of r. In particular, it is shown that b_2r+1,r is the maximum exponent attained by matrices in P_2r+1,r. When n is a multiple of r, it is conjectured that the maximum exponent achieved by matrices in P_nr is strictly smaller than b_nr. Matrices attaining the conjectured maximum exponent in that set are presented. It is shown that the conjecture is true when n = 2r.