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. Its hardest cases are strongly regular graphs(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):
$$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.
Update: From combinatorics, adjacency matrix perspective, $t(A)$ counts some subgraphs: number of common neighbors of $a,b$ which are neighbors (not restricted in strongly regular graphs). It will not work for longer paths, which can be included if using powers of adjacency matrices - consider generalized:
$$t^{\mathbf{l}}(A)_{ab}=\sum_{ij} (A^{l_1})_{ai} (A^{l_2})_{aj} (A^{l_3})_{ij} (A^{l_4})_{ib} (A^{l_5})_{jb} $$ and test $\forall_{\mathbf{l}\in \{1..n\}^5} \forall_{k=1..n} \textrm{Tr}(t^\mathbf{l}(A)^k)=\textrm{Tr}(t^\mathbf{l}(B)^k))$.
This way still in polynomial time we test $n^6$ invariants - instead of previous $n$. As the space of possibilities $\mathbf{O}$ is pessimistically $\sim n^2$ dimensional, $n$ invariants are not sufficient to restrict to permutations only (ensuring graph isomorphism if they agree), but e.g. $n^3$ invariants should be sufficient if independent enough (?)
How to prove sufficiency of e.g. such $n^6$ invariants or some other systematic construction?
