On expanders from the action of GL(2,Z)

Consider the undirected graph $G_n=(V_n,E_n)$ where $V_n=(Z\mathrm{/}nZ{)}^2$ and $E_n$ contains an edge from $(x,y)$ to $(x+1,y)$, $(x,y+1)$, $(x+y,y)$, and $(x,y+x)$ for every $(x,y)\in V_n$. Gabber and Galil, following Margulis, gave an elementary proof that $G_n$ forms an expander family. In this note, we present a somewhat simpler proof of this fact, and demonstrate its utility by isolating a key property of the linear transformations $(x,y) -> (x+y,x), (x,y+x)$ that yields expansion. As an example, consider any invertible, integral matrix $S\in G{L}_2(Z)$ and let $G_n^S=(V_n,E_n^S)$ where $E_n^S$ contains, for every $(x,y)\in V_n$, an edge from $(x,y)$ to $(x+1,y)$, $(x,y+1)$, $S(x,y)$, and $S^T(x,y)$, where $S^T$ denotes the transpose of $S$. Then {G_n^S} forms an expander family if and only if a related infinite graph has positive Cheeger constant. This latter property turns out to be elementary to analyze and can be used to show that {G_n^S} are expanders precisely when the trace of S is non-zero and S is not equal to its transpose. We also present some other generalizations.