Using permutation matrices to compare isomorphic and bipartite graphs

An adjacency matrix is a way of representing a network or graph as a mathematical matrix.

One of the advantages of representing a graph that way is that computers can process matrices very easily. In this article, we will look at permutation matrices, and see how they can be applied to adjacency matrices.

Identity matrices

An identity matrix I is a square matrix where all the elements are 0 except for the leading diagonal, where every element is 1. Here is a 4 by 4 identity matrix:

If we multiply another 4 by 4 matrix, A, by the identity matrix I, the result will be A (that is true whether I is placed before or after A):

Our matrix has specially chosen values. Each element is a 2-digit number where the first digit is equal to the matrix row, and the second element is equal to the matrix column. So row 1, column 1 has value 11. Row 2, column 3 has value 23, and so on. This means that, when we start moving elements around, we can easily see where they came from.

Before we move on from the identity matrix, it will be useful to look at how it works in slightly more detail. We will replace each diagonal 1 with a variable i1 to i4. These variables will still have a value of 1, but naming them allows us to see which value affects which elements of the result. If we multiply the matrices using the i values we get this:

This tells us that the 1 in the first column of the identity matrix is responsible for placing the first row of the source matrix in the first row of the result matrix. The 1 in the second column of the identity matrix is responsible for placing the second row of the source matrix in the second row of the result matrix. And so on.

Permutation matrices - row permutation