# Space of change of basis matrices between two similar matrices - how to reduce it with additional tests?

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?