Matrices representing binary relations on finite sets

So let $X$ be a finite set of size $n$ and let $R$ be a binary relation on $X$, denoted by $xRy$ for $x, y \in X$. $R$ can be thought of as a subset of $X \times X$ where $(x, y) \in R \subseteq X\times X \iff xRy$. Thus if I’ve got an enumeration of $X$, say $X = \{x_1, \dots, x_n\}$, then I can create a matrix $A \in \{0,1\}^{n\times n}$ where
$$
A_{ij} = 1 \iff x_i R x_j
$$
so $A$ encodes $R$, but only for this enumeration.

It’ll be useful to have a more technical definition of an enumeration. An enumeration of $X$ is defined to be a permutation (bijection) from $\{1,\dots, n\}$ to $X$ (I could equivalently have defined it using the inverse of this). For some enumeration $\sigma$, the relation matrix corresponding to $\sigma$ is a matrix $A$ such that $A_{ij} = 1 \iff \sigma(i) R \sigma(j)$. $X$ being size $n$ guarantees that there is at least one such bijection by the definition of cardinality, and in fact there are $n!$ many, but for a given $R$ many permutations will lead to identical matrices. For example, if $xRy$ is defined to be “$x=y$” then any permutation will lead identically to $A = I$.

I’ll declare two matrices $A$ and $B$ to be equivalent, denoted $A \sim B$, iff there is some permutation matrix $P$ such that $A = PBP^T$. For two sets $(X, R)$ and $(Y, R’)$, I’ll declare them to be relation isomorphic iff there exists a bijection $f : X \to Y$ such that for any $u, v \in X$ $uRv \iff f(u)R’f(v)$.

Result 1: my $A\sim B$ is a valid equivalence relation.

Pf: taking $P= I$ I have $A \sim A$. Next, suppose $A \sim B$ so $A = PBP^T$. Then because $P^T =P^{-1}$ I have $P^TAP = B$ and $P^T$ is also a permutation matrix, so $B \sim A$. Finally, suppose $A\sim B$ and $B \sim C$. Then

$$
A = PBP^T=PQCQ^TP^T = (PQ)C(PQ)^T
$$

and the composition of permutations is a permutation, so $A \sim C$. Thus $\sim$ is a valid equivalence relation.

$\square$

Next up I’m going to prove a lemma to help connect permutation matrices to permutations between finite sets.

Result 2: for any matrix $A$ and permutation matrix $P$ encoding the permutation $\sigma : \{1,\dots, n\} \to \{1,\dots, n\}$,
$$
(PAP^T)_{ij} = A_{\sigma(i), \sigma(j)}
$$
where by $P$ encoding $\sigma$ I mean $(Pv)_i = v_{\sigma(i)}$.

Pf: for a permutation matrix $P$ corresponding to $\sigma$, the $i$th row is $e_{\sigma(i)}$, i.e. it is the vector with a $1$ in position $\sigma(i)$. This also means that the $i$th column of $P^T$ is $e_{\sigma(i)}$. Considering $AP^T$, I have $(AP^T)_{kj} = \langle a_k, e_{\sigma(j)}\rangle = A_{k,\sigma(j)}$ where $a_k$ is the $k$th row of $A$. Next

$$
(PAP^T)_{ij} = \sum_k P_{ik}(AP^T)_{kj} = \sum_k P_{ik} A_{k,\sigma(j)}
$$

and $P_{ik} = 1$ only for $k = \sigma(i)$ which means $(PAP^T)_{ij} =A_{\sigma(i), \sigma(j)}$ as desired.

$\square$

Result 2 will be helpful in that it will let me quickly go from showing one matrix $A$ equals another $B$ indexed via a permutation to concluding $A\sim B$.

Result 3: any two permutations of $X$ will lead to equivalent relation matrices.

Pf: Let $\sigma$ and $\tau$ be two permutations of $X$ and let $A$ and $B$ be the corresponding relation matrices. Suppose $A_{ij}=1$ so $\sigma(i) R \sigma(j)$. $\sigma(i)$ and $\sigma(j)$ are elements of $X$ so, letting $\rho = \tau^{-1} \circ \sigma$, I have $B_{\rho(i),\rho(j)} = 1$. Similarly, supposing $B_{\rho(i), \rho(j)} = 1$ then $A_{ij} = 1$ so $A_{ij} = 1 \iff B_{\rho(i), \rho(j)} = 1$. Since the only other value $A$ and $B$ can take on is $0$, this means $A_{ij} = B_{\rho(i), \rho(j)}$ for all $i$ and $j$. $\rho$ is a permutation so by Result 2 $A \sim B$.

$\square$

Now I’ll generalize this to two sets of the same size. Result 4 will be the most general one I prove.

Result 4: for two sets $(X, R)$ and $(Y, R’)$, $X$ is relation isomorphic to $Y$ if and only if there exist enumerations with relation matrices $A$ on $X$ and $B$ on $Y$ such that $A \sim B$.

Pf: In both cases let $\sigma$ and $\tau$ be arbitrary enumerations on $X$ and $Y$ respectively, leading to relation matrix $A$ on $X$ and $B$ on $Y$.

First suppose $f : X \to Y$ gives a relation isomorphism, so that $\forall u, v \in X$ $u R v \iff f(u)R’f(v)$. Suppose $A_{ij} = 1$ so that $\sigma(i) R \sigma(j)$. Then $f(\sigma(j)) R’ f(\sigma(j))$. For any $i \in \{1,\dots, n\}$ $(f\circ \sigma)(i)$ is just some element of $Y$, so $\tau^{-1}$ (which is also a permutation) maps this element to something in $\{1,\dots, n\}$ again. Thus
$$
f(\sigma(j)) R’ f(\sigma(j)) \implies B_{(\tau^{-1}\circ f\circ\sigma)(i), (\tau^{-1}\circ f\circ\sigma)(j)} = 1.
$$
Letting $\rho = \tau^{-1}\circ f\circ\sigma$ this means $A_{ij} = 1 \implies B_{\rho(i),\rho(j)} = 1$. Now suppose $B_{\rho(i),\rho(j)} = 1$. Then this process can be walked back to give $A_{ij}=1$, so $A_{ij}=1 \iff B_{\rho(i),\rho(j)} =1$. As in Result 3, $A$ and $B$ are binary which means $A_{ij} = B_{\rho(i), \rho(j)}$ for all indices $i$ and $j$. By Result 2 this means $A = PBP^T$ for $P$ encoding $\rho$, so $A\sim B$.

Now for the other direction, suppose $\sigma$ and $\tau$ lead to $A\sim B$. Let $\rho$ be a permutation giving $A \sim B$ and define $f = \tau \circ \rho \circ \sigma^{-1}$ and note that $f$ is a permutation from $X$ to $Y$. I’ll show that this is a relation isomorphism. So let $u, v \in X$ and suppose $u R v$ in $X$. Then this means $A_{\sigma^{-1}(u), \sigma^{-1}(v)} = 1$, which in turn implies
$$
B_{(\rho \circ \sigma^{-1})(u), (\rho \circ \sigma^{-1})(v)} = 1
$$
so
$$
(\tau \circ \rho \circ \sigma^{-1})(u) = f(u) R’ f(v) = (\tau \circ \rho \circ \sigma^{-1})(v)
$$
or in other words, $uRv \implies f(u)R’f(v)$. For the other direction, suppose $f(u)R’f(v)$. Again this can be directly unrolled to lead to $uRv$, so $f$ is indeed a relation isomorphism.

$\square$

So I think this is nice because so long as I’m only considering properties of $A$ which are permutation-invariant then it really doesn’t matter what relation matrix I’m considering. For example, let’s say I’ve got an adjacency matrix $A$ for a graph $G = (V, E)$. I could enumerate $V$ in a different way to get another adjacency matrix $B$, but by result 3 I know $A \sim B$. Let’s suppose I’ve got an eigenpair $(\lambda, x)$ of $A$. Then

$$
Ax = \lambda x \implies PBP^Tx = \lambda x \implies BP^Tx = \lambda P^T x
$$