Graph theory : the adjacency matrix of an n-dimensional torus Is there, in principle, an easy way to determine the adjacency matrix of an n-dimensional torus that's only connected to neighbours which it shares a corner/edge/face/volume/etc with (n>1 obviously; the connections of a circular graph is obviously trivial). Can I use the 1-dimensional adjacency matrix to build the n-dimensional one? In this specific case the torus is formed by connecting the boundaries of an n-dimensional Cartesian like grid.
I believe I have a solution to the problem, but I can't find anything pertaining to the solution anywhere online or in an introductory book to graph theory that I have (perhaps mathematicians consider it trivial).
 A: As the $n$-dimensional torus $T^n$ is (topologically speaking) the product of $n$ circles:
$$ T^n = S^1 \times S^1 \times \ldots S^1 $$
so too is the natural grid on $T^n$ resulting from equally spaced nodes on circles a Cartesian product of graphs.
Suppose that $G$ and $H$ are simple undirected graphs.  Define $G \times H$ to be the graph whose nodes are pairs $(u,v)$ of nodes $u\in G$ and $v\in H$, with the edges determined by $(u,v)$ adjacent to $(u',v')$ if and only if:


*

*$u = u'$ and $v$ adjacent to $v'$ in $H$, or

*$v = v'$ and $u$ adjacent to $u'$ in $G$.
The adjacency matrix of a Cartesian product of two graphs can be expressed as a sum of two terms, Kronecker products corresponding to the two "cases" in the above definition.  Let $A$ be the adjacency matrix of $G$ and $B$ the adjacency matrix of $H$.  Then with a suitable ordering of vertices in $G\times H$, the adjacency matrix of $G\times H$ is:
$$ (A \otimes I_{|H|} ) + (I_{|G|} \otimes B) $$
where $|G|,|H|$ count the nodes in $G,H$ respectively.
To apply this to the "rectangular" grid on the $n$-torus $T^n$, we only need to iterate the Kronecker product expression above $n$ times, since the Cartesian product of graphs is (up to graph isomorphism) associative (and so too the adjacency matrix construction, with Kronecker product distributing over matrix sums).
