The graph isomorphism problem is defined as follows.
If $\Gamma_1$ and $\Gamma_2$ are two graphs with adjacency matrices $A_1$ and $A_2$ respectively, is there a permutation $\pi$ such that $A_1 = M_\pi A_2 M^T_\pi$ where $M_\pi$ is the permutation matrix for $\pi$?
Without the loss of generality we may assume that both graphs are of same $n$ number of vertices.
My question:
If $a_{1_{ij}}$ is an element in $A_1$, $a_{2_{kl}}$ is an element in $A_2$, $m_{\pi_{pq}}$ is an element in $M_\pi$, how can we express the relation $A_1 = M_\pi A_2 M^T_\pi$ in terms of their elements i.e. express $a_{1_{ij}}$ in terms of $a_{2_{kl}}$ and $m_{\pi_{pq}}$?
Our assumption promises that $A_1$, $A_2$ and $M_\pi$ are all $n \times n$ matrices.
My effort so far:
I already know that the relation can be expressed in terms of $a_{1_{ij}}$, $a_{2_{kl}}$ and $\pi$ as $a_{1_{ij}} = a_{2_{\pi(i) \pi(j)}}$.
If we express the intermediate product as $X = A_2 M^T_\pi$, $x_{kq} = \sum^n_r a_{2_{kr}} m_{\pi_{qr}}$.
- The final product is than $A_1 = M_\pi X$. So, $a_{1_{ij}} = \sum^n_s m_{\pi_{is}} x_{sj} = \sum^n_s m_{\pi_{is}} \left(\sum^n_r a_{2_{sr}} m_{\pi_{jr}}\right) $
Is my expression correct?