Square-free Discriminants of Matrices and the Generalized Spectral Characterizations of Graphs

Abstract

Let $S_n(\mathbb{Z})$ and $O_n(\mathbb{Q})$ denote the set of all $n\times n$ symmetric matrices over the ring of integers $\mathbb{Z}$ and the set of all $n\times n$ orthogonal matrices over the field of rational numbers $\mathbb{Q}$, respectively. The paper is mainly concerned with the following problem: Given a matrix $A\in S_n(\mathbb{Z})$. How can one find all rational orthogonal matrices $Q\in O_n(\mathbb{Q})$ such that $Q^{T}AQ\in S_n(\mathbb{Z})$, and in particular, when does $Q^{T}AQ\in S_n(\mathbb{Z})$ with $Q\in O_n(\mathbb{Q})$ imply that $Q$ is \emph{a signed permutation matrix} (i.e., the matrix obtained from a permutation matrix $P$ by replacing each 1 in $P$ with 1 or $-1$)? A surprisingly simple answer was given in terms of whether the discriminant of the characteristic polynomial of $A$ is odd and square-free, which partially answers the above questions. More precisely, let $Δ_A=\pm \res(ϕ,ϕ')$ be \emph{the discriminant of matrix $A$}, where $\res(ϕ,ϕ')$ is \emph{the resultant} of the characteristic polynomial $\ddot{I}•$ of $A$ and its derivative $\ddot{I}{•}^{\prime }$. We show that if $\hat{I}{”}_A$ is odd and square-free, then $Q^{T}AQ\in S_n(\mathbb{Z})$ with $Q\in O_n(\mathbb{Q})$ implies that $Q$ is a signed permutation matrix. As an application, we present a simple and efficient method for testing whether a graph is determined by the generalized spectrum, which significantly extends our previous work.