Inverse of the Squared Distance Matrix of a Complete Multipartite Graph

Joyentanuj Das, Sumit Mohanty

Abstract

Let $G$ be a connected graph on $n$ vertices and $d_{ij}$ be the length of the shortest path between vertices $i$ and $j$ in $G$. We set $d_{ii}=0$ for every vertex $i$ in $G$. The squared distance matrix $\Delta(G)$ of $G$ is the $n \times n$ matrix with $(i,j)^{th}$ entry equal to $0$ if $i = j$ and equal to $d_{ij}^2$ if $i \neq j$. For a given complete $t$-partite graph $K_{n_1,n_2,\dots,n_t}$ on $n=\sum_{i=1}^t n_i$ vertices, under some condition we find the inverse $\Delta(K_{n_1,n_2,\dots,n_t})^{-1}$ as a rank-one perturbation of a symmetric Laplacian-like matrix $\mathcal{L}$ with $\text{rank}(\mathcal{L})=n-1$. We also investigate the inertia of $\mathcal{L}$.

Introduction

In spectral graph theory, the distance matrix $D(G)$—recording shortest path lengths between vertices—is a fundamental object of study. A landmark result by Graham and Lovász established that for trees, the inverse of the distance matrix relates directly to the graph's Laplacian. This research extends this line of inquiry to the squared distance matrix $\Delta(G)$, where entries are the squares of shortest path lengths ($d_{ij}^2$).

The focus here is on complete multipartite graphs ($K_{n_1, n_2, \dots, n_t}$), where vertices are partitioned into $t$ groups. While distance matrices for trees are well-characterized, squared distance matrices for graphs with cycles, such as multipartite graphs, present significant inversion challenges. This paper derives a closed-form expression for this inverse and explores its spectral properties.

Methodology

The study utilizes an algebraic approach centered on matrix theory and combinatorial properties:

  • Block Matrix Analysis: The regular structure of complete multipartite graphs allows their squared distance matrices to be represented in block form. This symmetry is exploited to calculate determinants and cofactors.
  • Laplacian-like Construction: The authors define a symmetric matrix $\mathcal{L}$, termed "Laplacian-like," which shares the property of having zero row sums ($\mathcal{L}\mathbf{1} = \mathbf{0}$).
  • Rank-One Perturbation: The inverse $\Delta(G)^{-1}$ is proven to be the sum of $-\mathcal{L}$ and a rank-one matrix (an outer product of a specific vector $\nu$). This decomposition simplifies the complex $n \times n$ inversion into manageable components.
  • Interlacing Inequalities: Weyl’s inequality is applied to study the "inertia" (the count of positive, negative, and zero eigenvalues), determining how the rank-one perturbation shifts the eigenvalues of the underlying matrix.

Key Insights and Results

The research reveals that the "Laplacian-distance" duality is not exclusive to trees but extends to squared distances in multipartite graphs. In these graphs, distances are either 1 (different partitions) or 2 (same partition), leading to squared distances of 1 and 4. This discrete structure facilitates the elegant block-matrix inversion.

Explicit Inverse Formula

The primary result (Theorem 3.4) provides a definitive formula for $\Delta(G)^{-1}$ as a rank-one perturbation of $\mathcal{L}$. For computational applications, Theorem 3.5 specifies the exact entries of the inverse matrix in a $t \times t$ block format.

The inverse of the squared distance matrix $\Delta(G)$ for a complete multipartite graph can be expressed in a structured block format.

Spectral Properties and Inertia

The authors characterized the eigenvalues and inertia of the Laplacian-like matrix $\mathcal{L}$:

  • Eigenvalue Multiplicity: $1/4$ is an eigenvalue with multiplicity at least $n-t$. Under specific conditions, $1$ is an eigenvalue with multiplicity at least $h-1$ (where $h$ is the number of partitions of size 1).
  • Inertia Characterization: Theorem 4.4 provides the exact signature of $\mathcal{L}$, demonstrating how the distribution of eigenvalues depends on partition sizes.

Conclusion and Future Work

While providing a robust framework for complete multipartite graphs, the study notes that the inverse does not always exist; specific conditions on partition sizes can lead to a singular matrix. Future research may explore whether similar "Laplacian-like" inverses exist for squared distance matrices of other graph families, such as cycle or general block graphs. Additionally, the authors conjecture that $1/4$ and $1$ are the only positive eigenvalues of $\mathcal{L}$, a claim that remains to be formally proven.

Summary updated

Abstract

Let $G$ be a connected graph on $n$ vertices and $d_{ij}$ be the length of the shortest path between vertices $i$ and $j$ in $G$. We set $d_{ii}=0$ for every vertex $i$ in $G$. The squared distance matrix $Δ(G)$ of $G$ is the $n\times n$ matrix with $(i,j)^{th}$ entry equal to $0$ if $i = j$ and equal to $d_{ij}^2$ if $i \neq j$. For a given complete $t$-partite graph $K_{n_1,n_2,\cdots,n_t}$ on $n=\sum_{i=1}^t n_i$ vertices, under some condition we find the inverse $Δ(K_{n_1,n_2,\cdots,n_t})^{-1}$ as a rank-one perturbation of a symmetric Laplacian-like matrix $\mathcal{L}$ with $\textup{rank} (\mathcal{L})=n-1$. We also investigate the inertia of $\mathcal{L}$.
BibTeX
@inproceedings{das2024inverse,
  author = {Joyentanuj Das and Sumit Mohanty},
  title = {{Inverse of the Squared Distance Matrix of a Complete Multipartite Graph}},
  booktitle = {Electronic},
  year = {2024},
  doi = {10.13001/ela.2024.8283},
}
Figure