EXPONENTS OF r−REGULAR PRIMITIVE MATRICES

Abstract. A Boolean matrix A is said to be r−regular if each vertex in its digraph G(A) = G has outdegree and indegree exactly r. A is primitive if and only if there exist minimum integer k such that Ak> 0. For such a matrix, its digraph G is strongly connected and given any ordered pair of vertices x and y there is a directed walk from x to y of length k. Using the graph theory, we determine the lower bounds and upper bounds of r−regular primitive matices in this paper. We also proved that the exponent of r−regular primitive tournament T is just 3 and the exponent of r−regular primitive symmetric matrix A satisfys exp(A) ≤ 2(n − r). 1. basic concepts Boolean matrix has a close relationship with the digraph. Many problems in digraph theory can be reformulated as Boolean matrix problems and we can deal with many problem of Boolean matrix by using the digraph theory. So it is worth to introduce the concepts on the Boolean matrix and digraph simultaneously. Definition 1.1. The Boolean operations {+, ·, c} over set {0, 1} as following