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

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^TAQ\in {S_n($\mathbb{Z}$)}$,andinparticular,whendoes$Q^TAQ\in {S_n($\mathbb{Z}$)}$with$Q\in{O_n($\mathbb{Q}$)}$implythat$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 $\Delta_A=\pm \res(\phi,\phi’)be \emph{the discriminant of matrixA}, where\res(\phi,\phi’)$is\mathit{\text{the}}\mathit{\text{resultant}}ofthecharacteristicpolynomial$\phi$of$A$anditsderivative$\phi’$\mathrm{.}Weshowthatif$\Delta_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.