Assume we have two real symmetric $n\times n$ matrices: $A, B$. We can easily test their similarity: $\textrm{Tr}(A^k)=\textrm{Tr}(B^k)$ for $k=1..n$. In this case both can be rotated to the same diagonal matrix $D=\textrm{diag}(\{\lambda_i\})$ made of their eigenvalues - there exist orthogonal $O_A,O_B$ such that: 

$$O_A A O_A^T=D=O_B^T BO_B\qquad \textrm{hence}\qquad B=(O_B O_A)A(O_B O_A)^T$$

making $(O_B O_A)$ a change of basis matrix between them. However, there are more of them if eigenspectrum is degenerated: we can insert $D=S^TDS$ to above equation for any orthogonal $S$ rotating inside blocks of identical values of $D$ (degenerated eigenvalues). It allows to characterize the space of change of basis matrices between $A$ and $B$:
$$\mathbf{O}:=\{O:OO^T=I, B=O^T A O\} = \{O_B S O_A: D=S^T DS,\ S^TS=I\} $$

**The general question is how to reduce possible $O$ by some additional tests?** (beside $\forall_k \textrm{Tr}(A^k)=\textrm{Tr}(B^k)$)

Being able to reduce it to permutations only, we would solve the [graph isomorphism problem][1]. Its hardest cases are [strongly regular graphs][2](SRG) - which adjacency matrices are very degenerated: have always only 3 unique eigenvalues, making $\mathbf{O}$ very large - it seems difficult to test if such $\mathbf{O}$ contains a permutation (which would define graph isomorphism).

I have recently found such test which distinguishes at least some SRGs ([all I have tested - file][3]):

$$t(A)_{ab}=\sum_{ij} A_{ai} A_{aj} A_{ij} A_{ib} A_{jb}\quad  \textrm{and checking}\quad\forall_{k=1..n}\textrm{Tr}(t(A)^k)=^? \textrm{Tr}(t(B)^k)$$
Hence such agreement allows to restrict the original $\mathbf{O}$ set of possible similarity matrices, still containing permutations: $t(P^TAP)=P^T\, t(A)\, P$ for any permutation $P$ (often not true for orthogonal non-permutations).

**The question is how to characterize this restriction?** What is $\{O:OO^T=I, B=O^T A O\}$ additionally knowing that $\forall_k \textrm{Tr}(t(A)^k)=\textrm{Tr}(t(B)^k))$?

Understanding it, we might be able to choose more tests allowing to restrict to permutations only - solving the graph isomorphism problem, hopefully in polynomial time.

  [1]: https://en.wikipedia.org/wiki/Graph_isomorphism_problem
  [2]: https://en.wikipedia.org/wiki/Strongly_regular_graph
  [3]: https://www.dropbox.com/s/g3cf255cwajs199/srginvadj.pdf