Math Forum

From: haoyuep@aol.com (Dan Hoey)
Date: Mar 6, 2000 9:30 PM
Subject: Re: adjacency matrix of isomorphic graphs

Boris Hollas writes:

>Let G, G' be isomorphic graphs with adjacency matrices A and A'.  Why
>does then exist a permutation matrix P (i.e. an invertible matrix P
>with entries in {0,1}) such that A'=P A P^{-1} ?

You haven't quite defined "permutation matrix" correctly.  The
n x n permutation matrix P_r associated to a permutation function
r:{1,...,n}->{1,...,n} is a matrix whose i'th row has a one in column
r(i) and zeroes elsewhere.  So

1 1 0
1 0 0
0 0 1,

while invertible, is not a permutation matrix.

With this definition, note that the i'th row of A P_r is the r(i)'th
row of A and that the inverse of a permutation matrix is the same as
its transpose.  Prove that and you will know why.

Dan Hoey posted and e-mailed
haoyuep@aol.com