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.**