Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I don't know how to solve the following problem:

Show that two simple graphs $G$ and $H$ are isomorphic if and only if there exists a permutation matrix $P$ such that $A_G=PA_HP^t$.

Here $A$ is the adjacency matrix. I have a feeling this shouldn't be very difficult, but my linear algebra is not very good, am I missing something obvious?

share|improve this question
1  
Multiplying by $P$ on the left permutes the rows of the matrix. Multiplying by $P^t$ on the right permutes the columns. The important thing here is that the two permutations are the same if you think of them as acting on indices. There is hardly any linear algebra needed, just chasing definitions. –  Harald Hanche-Olsen Mar 15 '13 at 14:17
    
You probably mean $A_G=PA_HP^t$. –  Brian M. Scott Mar 15 '13 at 14:18
    
@BrianM.Scott Yes of course, thank you. –  hannahh Mar 16 '13 at 6:56

1 Answer 1

up vote 3 down vote accepted

Here’s an example that may get you thinking in the right direction. Consider $PAP^t$, where $P$ is the permutation matrix

$$\begin{bmatrix} 0&0&0&1\\ 1&0&0&0\\ 0&0&1&0\\ 0&1&0&0 \end{bmatrix}$$

and, as an illustrative example,

$$A=\begin{bmatrix} 1&2&3&4\\ 2&3&4&5\\ 0&1&2&3\\ 3&2&1&0 \end{bmatrix}\;.$$

We have

$$PA=\begin{bmatrix} 0&0&0&1\\ 1&0&0&0\\ 0&0&1&0\\ 0&1&0&0 \end{bmatrix} \begin{bmatrix} 1&2&3&4\\ 2&3&4&5\\ 0&1&2&3\\ 3&2&1&0 \end{bmatrix}= \begin{bmatrix} 3&2&1&0\\ 1&2&3&4\\ 0&1&2&3\\ 2&3&4&5 \end{bmatrix}\;, $$

and then

$$ PAP^t=\begin{bmatrix} 3&2&1&0\\ 1&2&3&4\\ 0&1&2&3\\ 2&3&4&5 \end{bmatrix} \begin{bmatrix} 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0\\ 1&0&0&0 \end{bmatrix}= \begin{bmatrix} 0&3&1&2\\ 4&1&3&2\\ 3&0&2&1\\ 5&2&4&3 \end{bmatrix}\;. $$

The first row of $A$ is the second row of $PAP^t$, and the first column of $A$ is the second column of $PAP^t$. The second row and second column of $A$ are the fourth row and column of $PAP^t$. The fourth row and column of $A$ are the first row and column of $PAP^t$. And the third row and column of $A$ are still the third row and column of $PAP^t$. In other words, both the rows and columns have been permuted by the permutation $(1,2,4)$ in cycle notation or

$$\pmatrix{1&2&3&4\\2&4&3&1}\tag{1}$$

in two-line notation. If $A$ is the adjacency matrix of a graph, $PAP^t$ is just the adjacency matrix of the same graph after the vertices have been renumbered according to the permutation $(1)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.