Recognizing undirected reduced Laplacian lattices

Definitions and mathematical statement

Let $A\in\mathbb Z^{n\times n}$ have nonzero determinant. Its row lattice is $\Lambda(A)=\{zA:z\in\mathbb Z^n\}\subseteq\mathbb Z^n$. Integral row operations preserving this lattice amount to multiplication by a unimodular matrix $U\in\operatorname{GL}_n(\mathbb Z)$, meaning $\det U=\pm1$. Consider finite connected undirected loopless multigraphs on labeled vertices $\{0,1,\ldots,n\}$, with $0$ designated as sink. Their reduced Laplacian $L$ is obtained by deleting the sink row and column from the usual degree-minus-adjacency matrix. Thus $L$ is symmetric, its off-diagonal entries are nonpositive integers, and its row sums are nonnegative integers recording edges to the sink. Connectivity makes $L$ positive definite.

Characterize the matrices $A$ for which there exist such a graph and $U$ with \[ UA=L. \] Equivalently, characterize full-rank sublattices of $\mathbb Z^n$ that have a basis forming a reduced undirected graph Laplacian, and give an effective recognition criterion in terms of the input lattice. Parallel edges are allowed, so arbitrary nonnegative integral multiplicities are permitted. The source explains that a directed graph can always be produced after changing the lattice basis; the remaining question is the restriction to undirected graphs. The coordinates remain the prescribed nonsink vertex coordinates: arbitrary ambient real changes of basis would discard the integer-lattice content of the question.

Short English statement

Which full-rank integer lattices admit a basis that is the reduced Laplacian of an undirected graph?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001003 (AIM-COMBINATORICS-0128), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, Generalizations of chip-firing and the critical group, item 38. Original workshop question underlying AIM-COMBINATORICS-0128. https://aimath.org/pastworkshops/chipfiringproblems.pdf.