I am not sure if graph isomorphism is the appropriate term here.
I am looking to compare two matrices where both matrices have the following structure:
- They are square matrices of identical shape ($n \times n$)
- They are anti-symmetric
- The values in the main diagonal are always $0$
- The only possible values in the matrix are $-1$, $0$, and $1$
The matrix describes a ranking between groups. If group X is bigger than group Y, the element in row X and column Y will be $1$ and the element in row Y and column X will conversely be $-1$. This is also why the diagonals are always $0$.
The ranking process is itself a little peculiar. For two groups to not be considered equal, there must be a minimum threshold in their size that is exceeded. So it is possible to have a scenario where $A = B, B = C, A > C$ in the event that $A$ is only a little bigger than $B$ (not enough to count), $B$ is only a little bigger than $C$, but $A$ is sufficiently bigger than $C$. I'm not sure how to formally state that in terms of what structures are possible for the matrices but throwing that in here in case it counts for anything.
Two matrices are considered equivalent if they can be converted into exact copies of each other using any number of label swaps.
Here's one example of two equivalent matrices:
$$ \begin{array}{c c} & \begin{array}{c c c} a & b &c \\ \end{array} \\ \begin{array}{c c c}a\\b\\c \end{array} & \left[ \begin{array}{c c c} 0 & 1 & 1 \\ -1 & 0 & 1 \\ -1 & -1 & 0 \end{array} \right] \end{array} $$
$$ \begin{array}{c c} & \begin{array}{c c c} b & a & c \\ \end{array} \\ \begin{array}{c c c}b\\a\\c \end{array} & \left[ \begin{array}{c c c} 0 & 1 & 1 \\ -1 & 0 & 1 \\ -1 & -1 & 0 \end{array} \right] \end{array} $$
In that example, the bottom matrix would be the same as the top if I just swapped the labels a and b.
Here's another example:
$$ \begin{array}{c c} & \begin{array}{c c c} a & b &c \\ \end{array} \\ \begin{array}{c c c}a\\b\\c \end{array} & \left[ \begin{array}{c c c} 0 & 0 & 1 \\ 0 & 0 & 0 \\ -1 & 0 & 0 \end{array} \right] \end{array} $$
$$ \begin{array}{c c} & \begin{array}{c c c} a & b &c \\ \end{array} \\ \begin{array}{c c c}a\\b\\c \end{array} & \left[ \begin{array}{c c c} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 0 \end{array} \right] \end{array} $$ What was referred to as c on top is referred to as b on the bottom.
I do not know much about graph theory but given that each matrix could be drawn as a directed graph, it seemed like this could be treated as a graph isomorphism problem. I saw some other stack exchange posts discussing how there isn't really a great way to do this, but perhaps the restrictions in the form of the graphs here may make a difference. While some sort of algorithmic improvement over brute-force checking would be appreciated, I would also be very grateful for being pointed towards any directions where I can learn more about this sort of problem or the proper terminology to use when discussing it. Thanks!
It is possible to check isomorphism here, because every such ranking structure can be put into a simple canonical form.
Let's define some notation. For a group $A$, let $U(A) = \{B : A < B\}$: the set of all groups that are "sufficiently bigger" than $A$. Let $L(A) = \{B : B < A\}$: the set of groups that are "sufficiently smaller" than $A$.
For any two groups $A$ and $B$, at least one of the following must hold:
The first one is guaranteed to happen if $A$ is bigger than $B$, even if it's only by a little amount not enough to set off our threshold. Even in that case, it's true that something a lot bigger than $A$ must also be a lot bigger than $B$, and that something a lot smaller than $B$ must be a lot smaller than $A$. Similarly, the second case holds if $A$ is smaller than $B$, even if it's only by a little amount not enough to set off our threshold. It's possible for both to hold.
Let's write $A \succeq B$ in the first case and $A \preceq B$ in the second case. If both hold, then write $A \approx B$. This happens only when $U(A)=U(B)$ and $L(A) = L(B)$, and it implies that $A$ and $B$ have exactly the same ranking relationship with respect to every other group: they are indistinguishable.
We can now sort a ranking structure by the $\preceq$ relation, because we can efficiently test whether $A \succeq B$ and/or $A \preceq B$. When we do this, we end up partitioning the set into strictly ordered "clumps", where if $A,B$ are in the same clump, then $A \approx B$: $A$ and $B$ are indistinguishable. In particular, if we sort the $\{-1,0,1\}$-valued matrix by the $\preceq$ relation, then the result is unique: the only failure of uniqueness is from swapping elements of a clump, but such elements have identical rows and columns in the matrix. Therefore, after sorting, we can check isomorphism by checking if the matrices are equal.
(By the way, comparing groups using the $\preceq$ relation is equivalent to comparing their rows in the matrix pointwise, since $U(A)$ is the set of $1$'s and $L(A)$ is the set of $-1$'s in a row.)