The Smith normal form of distance matrices of high dimensional trees

Graham-Lovász-Pollak {GL,GP} obtained the celebrated formula ( D(Tₙ₊₁))=(-1)ⁿn2ⁿ⁻¹, for the determinant of the distance matrix D(Tₙ₊₁) for any tree Tₙ₊₁ with $n+1$ vertices. Later, Hou and Woo {HW} extended this formula to the Smith normal form (SNF) obtaining that ( D(Tₙ₊₁))= I₂⊕ 2 Iₙ₋₂⊕ [2n], for any tree Tₙ₊₁ with $n+1$ vertices. A k-{ 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 $τ$ and $τ'$ are d-cliques in a k-tree T, a d-{ walk} between $τ$ and $τ'$ is a finite sequence τ₁σ₁τ₂σ₂⋯τₗ, where τ₁=τ, τₗ=τ', and the d-cliques τᵢ and τᵢ₊₁ are incident to the same $(d+1)$-clique σᵢ. For d∈\1,,k\, the d-{ distance} from the d-cliques $τ$ and $τ'$ is the number of $(d+1)$-cliques in a minimum d-walk from $τ$ and $τ'$, and is denoted by ᵈ(τ,τ'). Let cd denote the number of d-cliques in the k-tree T. Then the d-distance matrix Dᵈ(T) of the k-tree T is the cd× cd matrix, indexed by the d-cliques of T, such that the $(i,j)$-entry is $0$ if $i=j$, and ᵈ(τᵢ,τⱼ) 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ₙ with n vertices such that n≥ k+2, the Smith normal form of Dᵏ(Tₙ) is I₍ₖ₋₁₎₍ₙ₋ₖ₎₊₂⊕ (k+1) Iₙ₋ₖ₋₂⊕ [k(k+1)(n-k)], which extends Graham-Lovász-Pollak and Hou-Woo results.