# Canonical form of a matrix?

• Feb 24th 2010, 11:37 AM
NickZA
Canonical form of a matrix?
The question is actually about matrices rather than about graphs, however it relates to the concept of planarity testing in graph, so anyone with the great insight into matrices, please don't be put off and read on...

Given a graph G, in order to test conclusively for non-planarity, we reduce G -> G' to find minimal isomorphic subgraphs, and then isolate one of the Kuratoswki subgraphs K5 or K3,3.

In software, one of the benefits of encoding a graph as an adjacency matrix is that we can perform equality comparisons on cliques, i.e. we test equality of the matrix of a given clique in G against the matrix representing K5 or K3,3, in order to prove non-planarity.

Isolating K5 is trivial; due to it's connectivity it has only one representative matrix -- the inverse of the 5x5 identity matrix, incidentally.

However, K3,3 (the complete bipartite graph on 3 vertices, see it here), as a result of different vertex orderings, can have up to 10 individual representative permutations (at least that I've isolated) that could represent it. Using the above link to the image of K3,3, I provide an example of just 2 permutations, to give you a base on which to visualise the problem:

Fig.1. {v1, v2, v3} is one half of the bipartite graph, and {v4, v5, v6} the other:

v 1 2 3 4 5 6
1 0 0 0 1 1 1
2 0 0 0 1 1 1
3 0 0 0 1 1 1
4 1 1 1 0 0 0
5 1 1 1 0 0 0
6 1 1 1 0 0 0

Fig.2. {v1, v4, v5} is one half of the bipartite graph, and {v2, v3, v5} the other:

v 1 2 3 4 5 6
1 0 1 1 0 1 0
2 1 0 0 1 0 1
3 1 0 0 1 0 1
4 0 1 1 0 1 0
5 0 1 1 0 1 0
6 1 0 0 1 0 1

The reason for my needing to find a single form of the ten permutations, is so that I can optimise a program which tests planarity on an adjacency matrix representative of the graph. Rather than testing against 10 separate permutations on every pertinent clique, I want to know if there is any way to derive some single "canonical form", if you will, a form that represents all ten combinations of vertex orderings.