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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.