On congruence in \(\mathbb{Z}^ n\) and the dimension of a multidimensional circulant (Q1894764)

From MaRDI portal
Revision as of 05:07, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
On congruence in \(\mathbb{Z}^ n\) and the dimension of a multidimensional circulant
scientific article

    Statements

    On congruence in \(\mathbb{Z}^ n\) and the dimension of a multidimensional circulant (English)
    0 references
    0 references
    27 November 1995
    0 references
    If \(\mathbb{Z}^n\) denotes integer vectors and \(M\) is an integral matrix, then \(\mathbb{Z}^n/ M\mathbb{Z}^n\) is the abelian group of congruence classes modulo \(M\) (that is, modulo the lattice of integer linear combinations of the columns of \(M\)). Selecting a subset \(A\) of this group defines a Cayley (di)graph, whose vertices are the elements of the group, with edges joining each vertex \(x\) to \(x+a\) for \(a\in A\). If \(n=1\) the group is cyclic and the Cayley graph is called a circulant. In this paper the author studies multidimensional circulants (Cayley digraphs of abelian groups) in terms of integral matrices \(M\) and the Smith normal form of \(M\). Isomorphic graphs may arise from matrices of more than one size, and the minimum such \(n\) is called the dimension of the multidimensional circulant. This equals the minimum rank (minimum number of generators) of the (abelian) groups for which the graph is a Cayley digraph. The author proves that the cartesian product of \(n\) circulants of order \(p\) has dimension \(n\), for primes \(p>2\) (unlike the case \(p=2\), as Leighton showed in 1983 that the \(n\)-dimensional hypercube graph has dimension \(\lfloor (n+ 1)/2 \rfloor\) in this sense). For 2-step multidimensional circulants (where \(|A|=2\) so the dimension is at most two), the author proves a characterization of precisely when the dimension is one (in terms of the \(n\times n\) matrix \(M\) and the two vectors in \(A\)).
    0 references
    integral matrix
    0 references
    congruence
    0 references
    Cayley graph
    0 references
    circulant
    0 references
    multidimensional circulants
    0 references
    abelian groups
    0 references
    Cayley digraph
    0 references
    dimension
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references