Abstract:
Nonnegative matrices have a myriad of applications in the biological, social, and
physical genres. Of particular importance are the primitive matrices. A
nonnegative matrix, M, is primitive exactly when there is a positive integer, k,
such that M[superscript k] has only positive entries; that is, all the entries in M[superscript k] are strictly greater than zero. This method of determining if a matrix is primitive uses matrix
multiplication and so would require time Ω(n[superscipt α]) where α>2.3 even if fast matrix
multiplication were used. Our goal is to find a much faster algorithm. This can be
achieved by viewing a nonnegative matrix, M, as the adjacency matrix for a graph,
G(M). The matrix, M, is primitive if and only if G(M) is strongly connected and
the greatest common divisor of the cycle lengths in G(M) is 1. We devised an
algorithm based in breadth-first search which finds a set of cycle lengths whose
gcd is the same as that of G(M). This algorithm has runtime O(e) where e is the
number of nonzero entries in M and therefore equivalent to the number of edges in
G(M). A proof is given shown the runtime of O(n + e) along with some empirical
evidence that supports this finding.
