Cycles of directed graphs defined by matrix multiplication (modn)

AbstractLet A be a k×k matrix over a ring R; let GM(A,R) be the digraph with vertex set Rk, and an arc from v to w if and only if w=Av. In this paper, we determine the numbers and lengths of the cycles of GM(A,R) for k=2 in the following two cases. (a) R=Fq, the q-element finite field, and (b) R=Z/nZ and GCD(n,det(A))=1. This extends previous results for k=1 and R=Z/nZ. We make considerable use of the Smith form of a matrix; other than that, the most powerful tool we use is the Chinese Remainder Theorem