Cycles of directed graphs defined by matrix multiplication (mod \(n\)) (Q5946751)

From MaRDI portal





scientific article; zbMATH DE number 1659498
Language Label Description Also known as
default for all languages
No label defined
    English
    Cycles of directed graphs defined by matrix multiplication (mod \(n\))
    scientific article; zbMATH DE number 1659498

      Statements

      Cycles of directed graphs defined by matrix multiplication (mod \(n\)) (English)
      0 references
      0 references
      0 references
      27 January 2002
      0 references
      Let \(A\) be a \(k\times k\) matrix over a ring \(R\) and let \(\text{GM}(A,R)\) be the digraph with vertex set \(R^k\) and an arc from \(v\) to \(w\) if and only if \(w=Av\). When \(A\) is nonsingular then \(\text{GM}(A,R)\) is a collection of disjoint directed cycles; if \(A\) is singular then \(\text{GM}(A,R)\) is a collection of disjoint directed cycles with pendant trees. The authors determine the number and the length of the cycles of \(\text{GM}(A,R)\) for a very, very special case when \(k=2\) and \(R\) is either the finite field \(F_q\) with \(q\) elements or \(\mathbb{Z}/n\mathbb{Z}\) such that \(\text{gcd}(n,\det(A))=1\).
      0 references
      digraph cycle
      0 references
      cycle length
      0 references
      characteristic polynomial
      0 references
      minimal polynomial
      0 references
      Smith form
      0 references

      Identifiers