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
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
    0 references
    0 references
    0 references
    0 references
    digraph cycle
    0 references
    cycle length
    0 references
    characteristic polynomial
    0 references
    minimal polynomial
    0 references
    Smith form
    0 references
    0 references