Distinguishing finite metric spaces via similarity spectra

Abstract

We study spectra and characteristic polynomials of similarity matrices associated with finite metric spaces, where the similarity matrix of a finite metric space $X=\{x_1,\dots ,x_n\}$ is given by $Z(q)=(q^{d(x_i,x_j)}{)}_{i,j}$. % We introduce two spectral invariants of finite metric spaces, the $q$-spectrum and the transition $q$-spectrum, defined respectively from $Z(q)$ and its transition matrix. In the case of graphs, these invariants recover the adjacency spectrum and the Laplacian spectrum in the limit $q\to 0$. Our main result shows that the $q$-spectrum determines a large class of finite metric spaces under a natural nondegeneracy condition. We also prove that all four-point metric spaces are determined by their $q$-spectra. % The key observation is that the coefficients of the characteristic polynomial of $Z(q)$ encode cycle structures of the underlying metric space. % We further investigate the transition $q$-spectrum \jb{and show that strongly regular graphs with the same parameters have identical $q$-spectra and transition $q$-spectra, providing infinitely many non-isomorphic examples that cannot be distinguished by these invariants. Finally, we present computational examples comparing these invariants with classical graph spectra.}

16 pages, 13 figures