Defining a canonical ordering of matrix rows/columns [closed]

Question

I would like to find a way to define a canonical ordering of rows/columns in a matrix.

If two rows/columns cannot be ordered according to this canonical ordering (i.e. they're the "same"), then it must be true that exchanging them leaves the matrix invariant.

Note: In this context by reordering rows/columns of a matrix $M$ I mean transforming it using a permutation matrix $P$: $$M' = P M P^T$$

Note 2: I want to use this to have a unique representation of any graph using an adjacency matrix. The adjacency matrix depends on the vertex ordering.

EDIT I have a suspicion that an ordering relation that satisfies the above condition might not exist. Is this possible?

EDIT 2: I am rephrasing the question per several requests. Actually my problem is:

A graph can be represented by an adjacency matrix. However, this matrix depends on the ordering of vertices. I was looking for a canonical ordering of graph vertices that would make the adjacency matrix unique.

I was hoping that it is possible to do this by choosing the "correct" binary relation on the sit of graph vertices. However, I managed to prove that no such binary relation exists, which makes the problem too complicated to bother with for my practical application. So please do not spend more time on the question.

In short, it's possible to construct a graph for which any potentially suitable binary relation would consider vertices 1 and 2 equivalent, however exchanging 1 <-> 2 will not keep the adjacency matrix invariant (but e.g. exchanging both vertices 1 <-> 2 and 3 <-> 4 will).

Please close this question.

Answer 1

What you want to do is presumably to find an efficient way to solve the graph isomorphism problem. Good luck on this; computer scientists have been trying to do it for decades.

If you don't care about efficiency in terms of finding the ordering relation, there are lots of things you can do. For example, you could choose the lexicographically first matrix of the form $PMP^T$. This definitely is canonical; the problem is that nobody knows of any efficient algorithm for finding it.

There are a number of heuristics for graph isomorphism that work for most graphs. You might be able to use one of these might be able to get code that works most of the time.

Answer 2

Although, as Peter Shor indicated, graph isomorphism is a difficult computational problem, people have devised algorithms that work well in many practical situations. One example is Brendan McKay's nauty, which can give you a canonical labeling of a graph. You can download the code from the site http://cs.anu.edu.au/~bdm/nauty/, which also provides a literature reference. I have used the program many times to find canonical labelings of graphs up to several hundred vertices.

Answer 3

I've run into a similar issue when doing potential theory on graphs. If you want something canonical, don't work with matrices (which essentially already have a choice or basis built into them), but rather with linear transformations of an abstract vector space.

In your case, if $G$ is a graph with vertex set $V(G)$, let $W$ be the space of real-valued functions on the vertices of $\\mathbb{R}$. Writing $\chi_v$ for the characteristic function of the vertex $v$, we have $$W = \mathrm{Hom}(V(G), \mathbb{R}) \cong \bigoplus_{v \in V(G)} \mathbb{R}.\chi_v.$$ The adjacency matrix can be described as the linear operator $A:W \to W$ determined by $A(\chi_v) = \sum \chi_w$, where the sum is over all vertices $w$ adjacent to $v$.