0

Let me first state the problem first

Let $X$ and $X'$ be two $n$-vertex graphs with adjacency matrices $A$ and $B$ respectively . An $n \times n $ permutation matrix $P$ encodes an isomorphism $\pi$ from $X$ to $X'$ if and only if $P$ is a solution to the following $0$-$1$ integer linear program: $$AP =PB$$ $$ \sum_{i=1}^{n}{P_{ij} = 1}, 1\le j\le n$$ $$ \sum_{j=1}^{n}{P_{ij} = 1}, 1\le i\le n$$ $${P_{ij}} \in \{0,1\}, 1 \le i,j\le n. $$

one direction I have tried like this, assume $\pi$ is a bijective map ( one-one and onto) and let $P$ is a matrix corresponding to the map $\pi$, but I am not able to reason why it will satisfy the equation $AP =PB$.

I need to prove the claim in the bolded text.

1 Answers1

2

First let me state that the matrix equation should be $AP = PB$.

A graph isomorphism $\pi : X\to X'$ is a permutation of the vertices that keeps the graph structure intact, that is, $i \to j$ is an edge in $X$ if and only if $\pi(i)\to\pi(j)$ is an edge in $X'$. Or, stated in terms of adjacency matrices, $a_{ij} = b_{\pi(i)\pi(j)}$.

Given $\pi$, define $$P = P_\pi = \begin{pmatrix}e_{\pi(1)}\\\vdots\\e_{\pi(n)}\end{pmatrix}.$$

This is obviously a permutation matrix. Then $$(AP)_{ij} = \sum_{k=1}^n a_{ik} e_{\pi(k)j} = a_{i\pi^{-1}(j)}$$ and $$(PB)_{ij} = \sum_{k=1}^n e_{\pi(i)k} b_{kj} = b_{\pi(i)j}.$$

Substituting $j\mapsto \pi(j)$ gives $a_{ij}$ and $b_{\pi(i)\pi(j)}$, which we know are equal since $\pi$ is a graph isomorphism, thus $AP = PB$.

In the other direction, convince yourself that any $n\times n$ permutation matrix $P$ is of the form $P_\pi$ for some permutation $\pi$ of $\{1,\ldots,n\}$, then the same calculation shows that $\pi$ acting on the vertices of $X$ keeps the graph structure intact.

Christoph Horst
  • 63
  • I am not able to understand $$\sum_{k=1}^n a_{ik} e_{\pi(k)j} = a_{i\pi^{-1}(j)}$$ and why you substitute $j \implies \pi (j)$ not like $i \implies \pi (j)$ –  Mar 30 '17 at 17:05
  • @Shivd, $e_{\pi(k)} = (0, \ldots, 0, 1, 0, \ldots, 0)$, where the $1$ appears in the $\pi(k)$-th position. Therefore in this sum, most of the $a_{ik}$ are multiplied by $0$, except when $j=\pi(k)$, or equivalently $\pi^{-1}(j) = k$. That is, only $a_{i\pi^{-1}(j)}$ remains. I do the mentioned substitution in order to use the identity $a_{ij} = b_{\pi(i)\pi(j)}$. – Christoph Horst Mar 31 '17 at 15:16