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

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\)).