%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2021}
\articlenumber{62}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{enumitem}
\usepackage{graphicx}
\newcommand{\mbb}{\mathbb}
\newcommand{\Z}{\mbb Z}
\renewcommand{\a}{\mf a}
\renewcommand{\b}{\mf b}
\newcommand{\D}{\mathbf D}
\newcommand{\p}{\mf p}
\newcommand{\q}{\mf q}
\newcommand{\m}{\mf m}
\newcommand{\R}{\mbb R}
\newcommand{\C}{\mbb C}
\newcommand{\Q}{\mbb Q}
\newcommand{\N}{\mbb N}
\newcommand{\E}{\mathcal E}
\newcommand{\B}{\mathcal B}
\newcommand{\I}{\mathcal I}
\newcommand{\T}{\mathcal T}
\newcommand{\Sand}{\mathcal S}
\renewcommand{\tilde}{\widetilde}
\renewcommand{\P}{\mbb P}
\renewcommand{\hat}{\widehat}
\newcommand{\what}{\widehat}
\newcommand{\F}{\mathcal F}
\newcommand{\lr}{\leftrightarrow}
\newcommand{\mf}{\mathfrak}
\DeclareMathOperator{\Ima}{im}
\DeclareMathOperator{\spn}{span}
\DeclareMathOperator{\rk}{rk}
\newcommand{\Tor}{\text{Tor}}
\newcommand{\hto}{\hookrightarrow}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\xto}{\xrightarrow}
\newcommand{\vp}{\varphi}
\newcommand{\ilim}{\varprojlim}
\newcommand{\verteq}{\rotatebox{90}{$\,=$}}
\newcommand{\un}{\underline}
\newcommand{\Fl}{\mathcal C}
\newcommand{\Cu}{\what{\mathcal C}}
\newcommand{\col}[1]{x_{#1}}
\newcommand{\hcol}[1]{\widehat x_{#1}}
\newcommand{\indB}[1]{k_{#1}}
\newcommand{\hindB}[1]{\widehat k_{#1}}
\newcommand{\jndB}[1]{j_{#1}}
\newcommand{\CB}{x_B}
\newcommand{\hCB}{x_{\widehat B}}
\newcommand{\CBs}{x_{\B(D)}}
\newcommand{\hCBs}{x_{\B(\widehat D)}}
\newcommand{\colB}[1]{x_{k_{#1}}}
\newcommand{\hcolB}[1]{\widehat x_{k_{#1}}}
\newcommand{\CS}{x_S}
\newcommand{\w}{\mathfrak w}
\newcommand{\Cut}{\operatorname{Cocirc}}
\newcommand{\Flow}{\operatorname{Circ}}

\usepackage{tikz-cd}
%\usepackage{pst-node}
\usetikzlibrary{arrows.meta}
\usetikzlibrary{calc}
\usetikzlibrary{patterns}
\usepackage{blkarray, bigstrut} 

\newtheorem{theorem}{Theorem}[section]
\newtheorem{fact}[theorem]{Fact}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\newtheorem{construction}[theorem]{Construction}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{coro}[theorem]{Corollary}
\newtheorem{algorithm}[theorem]{Algorithm}
\theoremstyle{definition}
\newtheorem{rema}[theorem]{Remark}
\newtheorem{defi}[theorem]{Definition}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{exam}[theorem]{Example}

%% define your title in the usual way
\title[Matrix-Tree Multijections]{A Combinatorial Mapping for the Higher-Dimensional Matrix-Tree Theorem}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Alex McDonough\thanks{\href{mailto:amcd@ucdavis.edu}{amcd@ucdavis.edu}. Current address: Department of Mathematics, University of California, Davis, One Shields Avenue, Davis, CA 95616, USA.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Brown University}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{For a natural class of $r \times n$ integer matrices, we construct a non-convex polytope which periodically tiles $\R^n$. From this tiling, we provide a family of geometrically meaningful maps from a generalized sandpile group to a set of generalized spanning trees which give multijective proofs for several higher-dimensional matrix-tree theorems. In particular, these multijections can be applied to graphs, regular matroids, cell complexes with a torsion-free spanning forest, and representable arithmetic matroids with a multiplicity one basis. This generalizes a bijection given by Backman, Baker, and Yuen and extends work by Duval, Klivans, and Martin.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{sandpile group, matroid, cell complex, tiling}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{62McDonough.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

Given a connected graph $G$, the \textit{sandpile group} $\Sand(G)$ is a finite abelian group related to a discrete dynamical system. This group, and the related \textit{abelian sandpile model}, have been applied to a wide variety of subjects, such as algebraic geometry, electrical networks, and statistical mechanics~\cite{Lorenzini,Electric,BTW}. In different contexts, the sandpile group is also called the \textit{critical group}, \textit{graph Jacobian}, \textit{graph Picard group}, or \textit{group of components}. 

One striking property of $\Sand(G)$ is that its size is equal to the number of \textit{spanning trees} of $G$. This relationship follows from Kirchhoff's matrix-tree theorem, a classical graph theoretical result with many generalizations (see~\cite{Seth}). There has been a great deal of interest in providing combinatorially meaningful bijections between sandpile group equivalence classes and spanning trees. See, for example,~\cite{Dhar92,Holroyd,Bernardi}.

The sandpile group, spanning trees, and the matrix-tree theorem can all be generalized to larger classes of objects such as regular matroids (see \cite{Merino,Gioan2,Gioan}) and cell complexes (see \cite{Simp,Crit,CutsFlows}). For this extended abstract, as well as the full paper (see~\cite{mymultijections}), our primary objects of interest will be a class of integer matrices called \textit{standard representative matrices}. In the author's dissertation, he shows that any graph, regular matroid, cell complex with a torsion-free spanning forest, or orientable arithmetic matroid with a multiplicity one basis is associated with a standard representative matrix~\cite{mythesis}. 

Let $D$ be a standard representative matrix (see Definition~\ref{def:standrep}). In Section~\ref{sec:Background}, we define the \textit{sandpile group} $\Sand(D)$, the \textit{bases} $\B(D)$, and the \textit{basis multiplicity function} $m$ which maps each $B \in \B(D)$ to a positive integer. In this context, we get the following theorem, which is a reframing of Theorem 8.1 from~\cite{CutsFlows}.

\begin{theorem}[Sandpile matrix-tree theorem on standard representative matrices]\label{thm:OAmtt} 
\[|\Sand(D)| = \sum_{B \in \mathcal B(D)} m(B)^2.\]
\end{theorem}

When $D$ is associated with a regular matroid, $m(B) = 1$ for all $B \in \B(D)$ and thus Theorem~\ref{thm:OAmtt} implies that $|\Sand(D)| = |\B(D)|$ (this is Theorem 4.6.1 from~\cite{Merino}). In 2017 (published in 2019), Backman, Baker, and Yuen define a family of geometric bijections between $\Sand(D)$ and $\B(D)$ for the regular matroid case~\cite{BBY,Yuen}. However, their construction does not easily generalize to the case where not all bases have multiplicity 1.

Our main result is Theorem~\ref{thm:Hellyeah}, which gives the analogue of a bijection for an arbitrary standard representative matrix. In particular, we define a family of geometrically meaningful maps $f: \Sand(D) \to \mathcal B(D)$ such that for any $B \in \mathcal B(D)$, we have $|f^{-1}(B)| = m(B)^2$. We call these maps \textit{sandpile multijections}. 

Our general construction is geometric, as in~\cite{BBY}. We associate each basis with a parallelepiped of volume $m(B)^2$. These parallelepipeds do not intersect and their union produces a non-convex polyhedron that periodically tiles $\R^{|E|}$. Using our shifting vector, we associate $m(B)^2$ points of $\Z^{|E|}$ to each parallelepiped. Furthermore, we show that these points are all distinct in $\Sand(D)$. 

In Section~\ref{sec:Background}, we define relevant terms. In Section~\ref{sec:tiling}, we show how to construct a periodic tiling of $\R^n$ from any standard representative matrix. In Section~\ref{sec:multi}, we use this tiling to construct a family of sandpile multijections. In Section~\ref{sec:Lower}, we demonstrate how to generate lower-dimensional tilings which produce equivalent multijections. Finally, in Section~\ref{sec:quest}, we provide some open questions for further study.  

\section{Important Definitions}\label{sec:Background}

\begin{defi}\label{def:standrep}
An $r \times n$ integer matrix $D$ is a \textit{standard representative matrix} if it is of the form:
\[D = \begin{pmatrix} I_r & M\end{pmatrix},\]
where $I_r$ is the $r \times r$ identity matrix and $M$ is any $r \times (n-r)$ integer matrix. A standard representative matroid $D$ is associated with two other matrices:
\[\what D = \begin{pmatrix} -M^T & I_{n-r}\end{pmatrix} \hspace{.4 cm}\text{ and }\hspace{.4 cm} \D = \begin{pmatrix} D \\ \what D \end{pmatrix} = \begin{pmatrix}  I_r & M\\  -M^T & I_{n-r}\end{pmatrix}.\]
We call $\what D$ the \textit{dual matrix} of $D$ and $\D$ the \textit{full matrix} of $D$. 
\end{defi}
For the remainder of this paper, $D$ will always indicate an $r \times n$ standard representative matrix, and $\what D$ and $\D$ indicate the dual matrix and full matrix of $D$ respectively. 
\begin{rema}
The term \textit{standard representative matrix}, which appears in~\cite[Section 2.2]{Oxley}, is named for the fact that every \textit{representable matroid} can be \textit{represented} by a matrix of this form (after rearranging columns). However, it is worth noting that we can only represent \textit{oriented arithmetic matroids} using a matrix of this form if they have a \textit{basis of multiplicity one} (see~\cite[Corollary 4.3.13]{mythesis}).\footnote{We also need to restrict to oriented arithmetic matroids satisfying the \textit{strong GCD property} or else not all oriented arithmetic matroids are representable (see~\cite[Section 4.2]{mythesis}). For this paper, whenever we mention oriented arithmetic matroids, we will always assume this property.} In~\cite[Chapter 5]{mythesis}, the set of representations for an arbitrary oriented arithmetic matroid are classified. 
\end{rema}

\begin{lemma}\label{lem:flowofcut}
If $D$ is a standard representative matrix, then $\ker_\Z(D) = \Ima_\Z(\what D^T)$, $\Ima_\Z(D^T) = \ker_\Z(\what D)$, and $\Ima_\Z(\D^T) = \Ima_\Z(D^T) \oplus \ker_\Z(D)$. 
\end{lemma}

\begin{defi}\label{def:sandpile}
The \textit{sandpile group} of a standard representative matrix $D$, denoted $\Sand(D)$, is the finite abelian group
\[\Sand(D) = \Z^n / (\Ima_\Z(D^T) \oplus \ker_\Z(D)) = \Z^n / (\Ima_\Z(\D^T)).\]
\end{defi}

\begin{defi}\label{def:bandm}
The set of \textit{bases} of $D$, written $\mathcal B(D)$, is the set of $r$-tuples of columns of $D$ such that the determinant of $D$ restricted to these columns is nonzero. For $B \in \mathcal B(D)$, let $m(B)$ be the absolute value of this determinant. This $m(B)$ is called the \textit{multiplicity} of $B$. 
\end{defi}

\begin{rema} These definitions come from the theory of \textit{arithmetic matroids}. In \cite{CutsFlows}, the authors work with \textit{cell complexes} instead of standard representative matroids (although they note in Remark 4.2 that their ideas can be translated to an integer matrix context). Our bases correspond to what they call \textit{cellular spanning forests}, basis multiplicity correspond to the size of the \textit{torsion subgroup} of a certain \textit{relative homology}, and the sandpile group corresponds to what they call the \textit{cutflow group}. See~{\cite[Section 6.6]{mythesis}} for more discussion on the sandpile group of a cell complex and how this relates to the sandpile group of a standard representative matrix. 
\end{rema}

Recall that the sandpile matrix-tree theorem for standard representative matrices (Theorem~\ref{thm:OAmtt}) says that:
\[|\Sand(D)| = \sum_{B \in \mathcal B(D)} m(B)^2.\]

In the following example, we give a demonstration of this theorem. 
\begin{exam}\label{ex:fave0}
Suppose that for $r=2$ and $n=3$, we have the following standard representative matrix:
\[ D = \begin{pmatrix}1 & 0 & 3\\ 0 & 1 & 2\end{pmatrix}.\]
Because all of the maximal minors are nonzero, $\B(D) = \{\{1,2\},\{1,3\},\{2,3\}\}$. Furthermore, $m(\{1,2\}) = 1$, $m(\{1,3\}) = 2$, and $m(\{1,2\}) = 3$. Theorem~\ref{thm:OAmtt} says that $|\Sand(D)| = 1^2 + 2^2 + 3^2 = 14$. Recall that by definition of $\Sand(D)$, this is the number of elements in $\Z^3 / \Ima_\Z(\D^T)$ where $\D$ is the full matrix associated with $D$. 
\end{exam}


\section{A Tiling of $\R^n$}\label{sec:tiling}

In this section, we will associate each $B \in \B(D)$ with a lattice parallelepiped and then show that the non-convex polytope formed by their union periodically tiles $\R^n$. In the next section, we will show how to use this tiling to construct a family of multijections. 

We think of $B \in \B(D)$ as a set of column indices. These simultaneously describe a set of columns of $D$, $\widehat D$ or $\D$. Because we are working in $\R^n$, it will be useful to allow for a version of the sandpile group whose representatives are real vectors. 

\begin{defi}
The \textit{continuous sandpile group} of $D$ is the group:
\[\tilde \Sand(D) = \R^n / (\Ima_\Z(D^T) \oplus \ker_\Z(D)) = \R^n/\Ima_\Z(\D^T)\]
\end{defi}

We introduce some definitions and notation that can be found in~\cite{Beck}. Let $A$ be a square matrix with columns $\{\col 1,\dots,\col k\}$.
\begin{defi}\hfill\label{def:parpip}
\begin{itemize}
    \item The \textit{fundamental parallelepiped} of $A$, denoted $\Pi_\bullet(A)$, is:
\[ \left\{\sum_{i=1}^k a_i \col i \mid 0 \le a_i \le 1\right\}.\]
    \item The \textit{half-open fundamental parallelepiped} of $A$, denoted $\Pi_\circ(A)$, is:
\[ \left\{\sum_{i=1}^k a_i \col i \mid 0 \le a_i < 1\right\}.\]
\end{itemize}
\end{defi}

It is a classical result that the volume of $\Pi_\bullet(A)$ or $\Pi_\circ(A)$ is the magnitude of $\det(A)$. 

\begin{defi} \label{def:p1p2p}
For any basis $B\in \B(D)$:
\begin{itemize}
    \item $P_1(B)$ is the fundamental parallelepiped of $D$ restricted to columns in $B$. 
    \item $P_2(B)$ is the fundamental parallelepiped of $\widehat D$ restricted to columns \textit{not} in $B$.
    \item $P(B)$ is the direct product of $P_1(B)$ and $P_2(B)$.
\end{itemize}
\end{defi}

Note that $P_1(B)$ is $r$-dimensional, $P_2(B)$ is $(n-r)$-dimensional, and $P(B)$ is $n$-dim\-en\-sion\-al.

\begin{lemma}\label{lem:pipedvol}For any basis $B\in \mathcal B(D)$, $P_1(B)$ and $P_2(B)$ each have volume $m(B)$ while $P(B)$ has volume $m(B)^2$.
\end{lemma}

We can also describe $P(B)$ in the following way.
For each column of $\D$, if this column corresponds to an index of $B$, replace the last $(n-r)$ entries with 0's. If this column does not correspond to an index of $B$, replace the first $r$ entries with 0's. The fundamental parallelepiped of this matrix is $P(B)$. See Example~\ref{ex:favorite}. 

\begin{exam}\label{ex:favorite}
Consider the matrix 
\[D = \begin{pmatrix}
1 & 0 & 3 \\
0 & 1 & 2\\
\end{pmatrix}
\text{ whose associated full matrix is }
\D = \begin{pmatrix}
1 & 0 & 3 \\
0 & 1 & 2\\
-3&-2 & 1\\
\end{pmatrix}.\]

\noindent As we saw in Example~\ref{ex:fave0}, there are 3 bases of $\mathcal B(D)$, one for every pair of columns. The associated parallelepipeds are given below:
\[
P_1(\{1,2\}) = \Pi_\bullet\begin{pmatrix}
1 & 0 \\
0 & 1 \\
\end{pmatrix}\hspace{.5cm}
P_2(\{1,2\}) = \Pi_\bullet\begin{pmatrix}
1 \\
\end{pmatrix}\hspace{.5cm}
P(\{1,2\}) = \Pi_\bullet\begin{pmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1\\
\end{pmatrix}\]
\[
P_1(\{1,3\}) = \Pi_\bullet\begin{pmatrix}
1 & 3 \\
0 & 2 \\
\end{pmatrix}\hspace{.5cm}
P_2(\{1,3\}) = \Pi_\bullet\begin{pmatrix}
-2 \\
\end{pmatrix}\hspace{.5cm}
P(\{1,3\}) = \Pi_\bullet\begin{pmatrix}
1 & 0 & 3\\
0 & 0 & 2\\
0 & -2 & 0\\
\end{pmatrix}\]
\[
P_1(\{2,3\}) = \Pi_\bullet\begin{pmatrix}
0 & 3 \\
1 & 2 \\
\end{pmatrix}\hspace{.5cm}
P_2(\{2,3\}) = \Pi_\bullet\begin{pmatrix}
-3 \\
\end{pmatrix}\hspace{.5cm}
P(\{2,3\}) = \Pi_\bullet\begin{pmatrix}
0 & 0 & 3\\
0 & 1 & 2\\
-3& 0 & 0\\
\end{pmatrix}.\]


\begin{figure}
\centering

\begin{tikzpicture}
    \tikzstyle{every node} = [circle,fill,inner sep=1pt,minimum size = 1.5mm];
\node(aaa) at (0,0) {};
\node(aba) at (0,1){};
\node(bba) at (1,1){};
\node(baa) at (1,0){}; 
\node(aab) at (.3,.6){};
\node(abb) at (.3,1.6){};
\node(bbb) at (1.3,1.6){};
\node(bab) at (1.3,.6){};

\node(c) at (3.9,1.8){};
\node(d) at (3.6,1.2){};
\node(e) at (4.6,1.2){};

\node(f) at (0,-2){};
\node(g) at (3.6,-.8){};
\node(h) at (4.6,-.8){};
\node(i) at (1,-2){};

\node(j) at (0,-3){};
\node(k) at (3.6,-1.8){};
\node(l) at (3.9,-1.2){};
\node(m) at (0.3,-2.4){};

\draw (aaa) -- (aba) -- (bba) -- (baa) -- (aaa) ;
\draw (abb) -- (bbb) -- (bab);
\draw[dashed] (bab)--(aab);
\draw[dashed] (aaa)--(aab);
\draw[dashed] (aab)--(abb);
\draw(aba) -- (abb);
\draw(bba) -- (bbb);
\draw(baa) -- (bab);

\draw[dashed] (aab)--(1.3,0.6+1/3);
\draw (1.3,0.6+1/3)-- (c) -- (d) -- (1.2,0.4);
\draw[dashed] (1.2,0.4)--(aaa);
\draw (baa)--(e)--(d);
\draw (aaa)--(f) -- (i) -- (baa);
\draw (i) -- (h) -- (e);
\draw[dashed](f) -- (g) -- (d);
\draw[dashed](g) --(h);

\draw (f)--(j) -- (k) -- (l);
\draw[dashed] (j) -- (m) -- (l);
\draw[dashed] (m) -- (aab);
\draw (k) -- (3.6,-1.133);
\draw [dashed] (3.6,-1.133) -- (g);
\draw(c) -- (3.9,1.2);
\draw[dashed] (3.9,1.2) -- (l);
\end{tikzpicture}

\caption{Here is a plot of the three parallelepipeds from Example~\ref{ex:favorite} in $3$-dimensional space. The cube is $P(\{1,2\})$, the smaller of the two remaining parallelepipeds is $P(\{1,3\})$, and the larger is $P(\{2,3\})$. We will see in Corollary~\ref{cor:tiling} that the union of these parallelepipeds periodically tiles the plane.}
\label{favefig}
\end{figure}

\end{exam}

See Figure~\ref{favefig} for a plot of these three parallelepipeds. Notice that they only intersect at their boundaries. We show that this is true in general. 

\begin{prop}\label{prop:nointersect}
The parallelepipeds $P(B)$ for each basis $B\in \B(D)$ do not intersect except at their boundaries.
\end{prop}

\begin{defi}
$T(D)$, the \textit{tile associated with $D$}, is 
\[T(D) = \bigcup_{B \in \B(D)} P(B).\]
\end{defi}

\noindent Corollary~\ref{cor:tiling} will justify why we call this non-convex polyhedron a \textit{tile}. 

The following corollary follows directly from Lemma~\ref{lem:pipedvol} which gives the size of each $P(B)$ and Proposition~\ref{prop:nointersect} which says that they don't intersect.

\begin{coro}\label{cor:voltile}
The volume of $T(D)$ is equal to
\[\sum_{B \in \B(D)} m(B)^2.\]
\end{coro}
\noindent Note that this sum is also equal to $|\Sand(D)|$ by Theorem~\ref{thm:OAmtt}. 

When considering all of $T(D)$, we can strengthen Proposition~\ref{prop:nointersect} to the following:

\begin{prop}\label{prop:lastDomino}
Two distinct points of $T(D)$ can only be equivalent as elements of $\tilde \Sand(D)$ if they are both on the boundary of $T(D)$. 
\end{prop}

The next corollary shows that copies of $T(D)$ can be used to periodically tile $\R^{n}$.

\begin{coro}\label{cor:tiling}
The set of translates $T(D) + \D^T(z_1,\dots, z_{n})^T$ for all $(z_1,\dots, z_{n}) \in \Z^{n}$ cover all of $\R^{n}$ and only intersect at their boundaries. 
\end{coro}

\section{Constructing the Sandpile to Basis Multijections}\label{sec:multi}
In order to define our multijections, we will need $T(D)$ and an appropriate $\R^{n}$ direction vector.

\begin{defi}\label{def:shifting}
A \textit{shifting vector} $\w = (\w_1,\dots,\w_{n})$ of $D$ is a vector in $\R^{n}$ that is not in the span of a facet of $P(B)$ for any $B \in \B(D)$. 
\end{defi}

\begin{rema}In \cite[Section~8]{mymultijections}, the author shows how a choice of \textit{shifting vector} corresponds to a choice of \textit{chamber} from a \textit{hyperplane arrangement} and how these chambers relate to \textit{acyclic circuit and cocircuit signatures}.\end{rema}

It will sometimes be useful to split our shifting vector into two smaller vectors. Consider the vectors $w = (w_1,\dots,w_r) \in \R^r$ and $\widehat w = (\widehat w_1,\dots, \widehat w_{n-r})\in \R^{n-r}$. We write $(w,\widehat w)$ for their concatenation, which is an $\R^n$ vector.
\begin{lemma}\label{lem:splitshift}
$(w,\widehat w)$ is a shifting vector for $D$ if and only if for all $B \in \B(D)$, $w$ does not lie in the span of any facet of $P_1(B)$ and $\widehat w$ does not lie in the span of any facet of $P_2(B)$. 
\end{lemma}

\begin{defi}\label{def:reps}
Let $\w = (w,\widehat w)$ be a shifting vector.
\begin{itemize}
\item For any $v \in \R^{n}$, $ v$ is a \textit{$\w$-representative} of $\tilde \Sand(D)$ if $ v+\epsilon \w \in T(D)$ for all sufficiently small $\epsilon>0$. If $ v+ \epsilon \w \in P(B)$, we say that $ v$ is \textit{$\w$-associated} with $B$. 

\item For any $z \in \Z^{n}$, $z$ is a \textit{$\w$-representative} of $\Sand(D)$ if $z+\epsilon \w \in T(D)$ for all sufficiently small $\epsilon>0$. If $z+ \epsilon \w \in P(B)$, we say that $z$ is \textit{$\w$-associated} with $B$. 

\item For any $v \in \R^r$ if $v+ \epsilon w \in P_1(B)$ for all sufficiently small $\epsilon>0$, we say that $v$ is \textit{$w$-associated} with $B$. 

\item For any $\widehat v \in \R^{n-r}$ if $\widehat v+ \epsilon \widehat w \in P_2(B)$ for all sufficiently small $\epsilon>0$, we say that $\widehat v$ is \textit{$\widehat w$-associated} with $B$. 
\end{itemize}
\end{defi}

\begin{lemma}\label{lem:splitassoc}
Suppose $\w = (w,\widehat w)$ is a shifting vector, $v \in \R^r$, and $\widehat v \in \R^{n-r}$. Then, $(v,\widehat v)$ is $\w$-associated with $B$ if and only if $v$ is $w$-associated with $B$ and $\widehat v$ is $\widehat w$-associated with $B$. 
\end{lemma}

\begin{lemma}\label{lem:associated}
Each $\w$-representative of $\tilde \Sand(D)$ or $\Sand(D)$ is $\w$-associated with exactly one $B \in \B(D)$. 
\end{lemma}

\begin{prop}\label{prop:justone}
For any shifting vector $\w$, there is exactly one $\w$-representative in $\R^{n}$ for each equivalence class of $\tilde \Sand(D)$ and exactly one $\w$-representative in $\Z^{n}$ for each equivalence class of $\Sand(D)$.
\end{prop}

\begin{prop}\label{prop:Ehrhart}
For any shifting vector $\w$, and for any $B \in \B(D)$, there are exactly $m(B)^2$ $\w$-representatives of $\Sand(D)$ that are $\w$-associated with $B$.
\end{prop}
To prove this result, we apply the following lemma from Ehrhart Theory:
\begin{lemma}[{\cite[Lemma 9.2]{Beck}}]\label{lem:Ehrhart}
For any integer matrix $M$, the number of integer points in the half-open fundamental parallelepiped $\Pi_\circ(M)$ is equal to its volume (the magnitude of $\det(M)$). 
\end{lemma}


We now define a function $\tilde f_{\w}$ from $\tilde \Sand(D) \to \B(D)$ given a shifting vector $\w$. For any $s \in \tilde \Sand(D)$, we first take the $\w$-representative $z$ of $s$ (which is unique by Proposition~\ref{prop:justone}). Then, we let $\tilde f_{\w}(s) = B$, where $B$ is the $\w$-associated basis of $z$ (which is unique by Lemma~\ref{lem:associated}). 

\begin{defi}\label{def:restrictedf}
$f_{\w}$ is $\tilde f_{\w}$ (as defined above) but with its domain restricted to $\Sand(D)$. 
\end{defi}

The following theorem is the main result of this paper.

\begin{theorem}\label{thm:Hellyeah}
For any $B\in \B(D)$, we have $|f_{\w}^{-1}(B)| = m(B)^2$.
\end{theorem}

\begin{proof}
We showed in Propositions~\ref{prop:justone} and~\ref{prop:nointersect} that $f_{\w}$ is a well-defined map from $\Sand(D)$ to $\B(D)$. The fact that $|f_{\w}^{-1}(B)| = m(B)^2$ is a corollary of Proposition~\ref{prop:Ehrhart}.
\end{proof}

\begin{exam}\label{ex:fave2}
Consider the matrix and associated tile from Example~\ref{ex:favorite}. One can show that $\w = (1,1,1)$ satisfies the requirements of a shifting vector. There are 14 different $\w$-representatives of $\Sand(D)$ given in the list below:
\begin{align*}
\{&(0,0,0),(0,0,-1),(1,0,-1),(1,1,-1),(2,1,-1),(2,2,-1),(0,0,-2),\\
&(1,0,-2),(1,1,-2),(2,1,-2),(2,2,-2),(0,0,-3),(1,1,-3),(2,2,-3)\}.
\end{align*}
Furthermore, we have:
\begin{align*}
f_\w^{-1}(\{1,2\}) = \{&(0,0,0)\}.\\
f_\w^{-1}(\{1,3\}) = \{&(1,0,-1),(2,1,-1),(1,0,-2),(2,1,-2)\}.\\
f_\w^{-1}(\{2,3\}) = \{&(0,0,-1),(1,1,-1),(2,2,-1),(0,0,-2),(1,1,-2),\\
&(2,2,-2),(0,0,-3),(1,1,-3),(2,2,-3)\}.
\end{align*}
\noindent where each $\w$-representative is shorthand for ``the equivalence class of $\Sand(D)$ containing this $\w$-representative''. We can confirm that $f_{\w}$ is a multijection by noting that:
\begin{align*}
|f_\w^{-1}(\{1,2\})| &= 1 = m(\{1,2\})^2.\\
|f_\w^{-1}(\{1,3\})| &= 4 = m(\{1,3\})^2.\\
|f_\w^{-1}(\{2,3\})| &= 9 = m(\{2,3\})^2.
\end{align*}

If we use a different shifting vector, some of our representatives may change. For example, for $\w' = (-1,2,-2)$, we have:
\begin{align*}
f_{\w'}^{-1}(\{1,2\}) = \{&(1,0,1)\}.\\
f_{\w'}^{-1}(\{1,3\}) = \{&(1,0,0),(2,1,0),(1,0,-1),(2,1,-1)\}.\\
f_{\w'}^{-1}(\{2,3\}) = \{&(3,2,0),(1,1,0),(2,2,0),(3,2,-1),(1,1,-1),\\
&(2,2,-1),(3,2,-2),(1,1,-2),(2,2,-2)\}.
\end{align*}

Note that interior points of $P(B)$ are always associated with $B$, but boundary points depend on the shifting vector. 
\end{exam}

\section{Lower-Dimensional Representatives}\label{sec:Lower}

In Section~\ref{sec:tiling}, we showed how to construct a tiling of $\R^{n}$ and then in Section~\ref{sec:multi}, we used this tiling to produce a set of representatives for $\Sand(D)$ (see Theorem~\ref{thm:Hellyeah}). In this section, we show how to use the tiling of $\R^{n}$ to produce a tiling of $\R^r$ or that also (given a shifting vector) produces a set of representatives of $\Sand(D)$. These representatives have zero in their last $n-r$ entries. However, even though the representatives of $\Sand(D)$ change, the multijection does not.\footnote{There is also a similar construction for a tiling of $\R^{n-r}$, see~\cite{mymultijections}.} 

One benefit of this alternate construction is that it is often easier to work in lower dimensional space. In particular, we are now able to produce a wide variety of tilings of $\R^2$ (see Figure~\ref{fig:tilings}).

The main tool we use in this section is the following lemma. 

\begin{lemma}\label{lem:lowerdim}
Let $D$ be the standard representative matrix $D = \begin{pmatrix}
I_n &M \\
\end{pmatrix}$ and let 
\[z = (z_1,\dots, z_r,\widehat z_1,\dots, \widehat z_{n-r})^T\in \Z^{n}.\]
 Then, $z$ is equivalent, with respect to $\Sand(D)$, to the vector whose first $r$ entries are given by
\[(z_1,\dots, z_r)^T + M^T(\widehat z_1,\dots,\widehat z_{n-r})^T,\]

\noindent and whose last $(n-r)$ entries are zero. 

\end{lemma}

Recall from Definition~\ref{def:p1p2p} that for any $B \in \B(D)$, we have parallelepipeds $P_1(B)$, $P_2(B)$, and $P(B)$, where $P(B)$ is the direct product of $P_1(B)$ and $P_2(B)$. Consider the vectors $w = (w_1,\dots,w_r) \in \R^r$, $\widehat w = (\widehat w_1,\dots, \widehat w_{n-r})\in \R^{n-r}$, and $\w = (w,\widehat w)$. Recall from Lemma~\ref{lem:splitshift} that $(w,\widehat w)$ is a shifting vector if $w$ is not in the span of any facet of $P_1(B)$ and $\widehat w$ is not in the span of any facet of $P_2(B)$. 

By a slight adjustment of Proposition~\ref{prop:Ehrhart}, one can show that there are $m(B)$ integer vectors $w$-associated with $P_1(B)$ and $m(B)$ integer vectors $\widehat w$-associated with $P_2(B)$.

\begin{defi}
\[ T'(D) = \bigcup_{B \in \B(D)} \left(\bigcup_{z\in \Z^{n-r} \text{ $\widehat w$-associated with } P_2(B)} \left(P_1(B) + M^T z^T\right)\right)\]
\end{defi}
 $T'(D)$ is made up of $m(B)$ parallelepipeds for each $B \in \B(D)$ and depends on $(\widehat w_1,\dots, \widehat w_{n-r})$ but not $(w_1,\dots, w_r)$. Figure~\ref{fig:tilings} gives an example of $T'(D)$.

The following theorem says that $T'(D)$ has many similar properties to $T(D)$. This is the main result of this section.
\clearpage
\begin{theorem}
\hspace{2pt} \nopagebreak[4]
\begin{itemize}
    \item The parallelepipeds that make up $T'(D)$ only intersect at their boundaries. 
    \item The set of translates $T'(D) + DD^T(z_1,\dots,z_r)^T$ for all $(z_1,\dots,z_r) \in \Z^r$ cover all of $\R^r$ and only intersect at their boundaries. 
    \item For each $B\in \B(D)$, there are exactly $m(B)^2$ integer points $(z_1,\dots, z_n)$ of $T'(D)$ such that for all sufficiently small $\epsilon>0$, $(z_1,\dots, z_n) + \epsilon(w_1,\dots,w_n)$ is in one of the translates of $P_1(B)$ that make up $T'(D)$. 
\end{itemize}
\end{theorem}

Figure~\ref{fig:tilings} gives some examples of tiles in $\R^2$ computed using Sage. On the left is the tile with different colors indicating different bases and on the right is 9 copies of the tile to show how the tiling works.  

\begin{rema}
When $m(B) = 1$ for every $B \in \B(D)$, the tile $T'(D)$ consists of a single parallelepiped for each $B \in \B(D)$. It is possible to translate each of these parallelepipeds by vectors that are trivial with respect to $\Sand(D)$ and obtain the \textit{zonotope} formed by the columns of $D$. In~\cite{BBY}, the authors use this zonotope to construct bijections between $\B(D)$ and $\Sand(D)$ (when $m(B) = 1$ for all $B \in \B(D)$).  
\end{rema}

\begin{figure}[t]
\centering
\includegraphics[width=.48\linewidth]{tile3.png}
\includegraphics[width=.48\linewidth]{tile35.png}
\linebreak
\centering

$D = \begin{pmatrix}
1 & 0 & 1 & 3 & -4 & 3 & 2 \\
0 & 1 & -3 & -2 & -1 & 0 & 1\\
\end{pmatrix}  \hspace{1cm}\w = (1,1,5,4,3,2,2)$

\caption{On the left is the tile $T'(D)$ with color-coded bases. On the right are nine
copies of $T'(D)$ to show how it tiles the plane.}
\label{fig:tilings}
\end{figure}

\section{Further Questions}\label{sec:quest}

The main purpose of our map was to associate each equivalence class of the sandpile group to a basis. However, in constructing this map, we also give a representative for each equivalence class. In particular, this is the set of $\w$-representatives. 


\begin{question}
What are some properties of the $\w$-representatives that we get from different choices of distinguished basis or shifting vector? Are they generalizations of any known sets of representatives of the graphical sandpile group (such as superstable or critical configurations)? What about the lower dimensional representatives from Section~\ref{sec:Lower}?
\end{question}

In~\cite[Chapter 9]{mythesis}, the multijections in this paper are generalized to a larger class of objects. However, the sandpile group must be replaced with its \textit{Pontryagin dual}. Note that the Pontryagin dual of the cokernel of a lattice generated by the rows of a matrix is the cokernel of the lattice generated by its columns.  In the case of standard representative matrices, the sandpile group is canonically isomorphic to its Pontryagin dual. In general, the the groups are isomorphic, but these isomorphisms are non-canonical. 

\begin{question}\label{q:canonlattice}
What are some properties of this Pontryagin dual sandpile group and why does it allow for more natural multijections?
\end{question}

In this paper, we focus on standard representative matrices, but the ideas can naturally be restated in terms of \textit{representable arithmetic matroids} (more precisely \textit{orientable arithmetic matroids with the strong GCD property}) which is the framework used in~\cite{mythesis}. However, it is essential for our definition that these matroids are \textit{representable}.
\begin{question}
Is there a reasonable way to define the sandpile group of some class of non-representable matroids?
\end{question}

\acknowledgements{
The author would like to thank Matthew Baker, Seth Chaiken, Galen Dorpalen-Barry, Caroline Klivans, Giovanni Inchiostro, Mariel Supina, Chi Ho Yuen, and the anonymous reviewers for useful conversation, comments, and suggestions.}

\printbibliography

\end{document}
