The Smith normal form of distance matrices of high dimensional trees

Abstract

Graham-Lovász-Pollak \cite{GL,GP} obtained the celebrated formula $$\det (\mathsf{D}(T_{n+1}))=(-1{)}^{n}n{2}^{n-1},$$ for the determinant of the distance matrix $\mathsf{D}(T_{n+1})$ for any tree $T_{n+1}$ with $n+1$ vertices. Later, Hou and Woo \cite{HW} extended this formula to the Smith normal form (SNF) obtaining that $\SNF({\sf D}(T_{n+1}))={\sf I}_2\oplus 2{\sf I}_{n-2}\oplus [2n]$, for any tree $T_{n+1}$ with $n+1$ vertices. A $k$-{\it tree} is either a complete graph on $k$ vertices or a graph obtained from a smaller $k$-tree by adjoining a new vertex together with $k$ edges connecting it to a $k$-clique. If $\tau$ and ${\tau }^{\prime }$ are $d$-cliques in a $k$-tree $T$, a $d$-{\it walk} between $\tau$ and ${\tau }^{\prime }$ is a finite sequence ${\tau }_1{\sigma }_1{\tau }_2{\sigma }_2\cdots {\tau }_l$, where ${\tau }_1=\tau$, ${\tau }_l={\tau }^{\prime }$, and the $d$-cliques ${\tau }_i$ and ${\tau }_{i+1}$ are incident to the same $(d+1)$-clique ${\sigma }_i$. For $d\in \{1,\dots ,k\}$, the $d$-{\it distance} from the $d$-cliques $\tau$ and ${\tau }^{\prime }$ is the number of $(d+1)$-cliques in a minimum $d$-walk from $\tau$ and ${\tau }^{\prime }$, and is denoted by $\dist^d(τ,τ')$. Let $c_d$ denote the number of $d$-cliques in the $k$-tree $T$. Then the $d$-distance matrix ${\mathsf{D}}^d(T)$ of the $k$-tree $T$ is the $c_d\times c_d$ matrix, indexed by the $d$-cliques of $T$, such that the $(i,j)$-entry is $0$ if $i=j$, and $\dist^d(τ_i,τ_j)$ otherwise. Here, we show that, for $k$ and $n$ fixed, the SNF of the $k$-distance matrix is the same for any $k$-tree with $n$ vertices. Specifically, for any $k$-tree $T_n$ with $n$ vertices such that $n\ge k+2$, the Smith normal form of ${\mathsf{D}}^k(T_n)$ is $${\mathsf{I}}_{(k-1)(n-k)+2}\oplus (k+1){\mathsf{I}}_{n-k-2}\oplus [k(k+1)(n-k)],$$ which extends Graham-Lovász-Pollak and Hou-Woo results.