The transitive closure of a relation $R$ on set $A$ whose relation matrix
My attempt:
If I assumed node $(1, 2, 3)$, then given is:
$R=\{(1, 2), (2, 3), (3, 1)\}$
The transitive closer would be:
$R=\{(1, 2), (2, 3), (3, 1), (1, 3), (2, 1), (1, 1), (3, 3)\}$
But none matrix is matched. Is it option $(C)$?
Can you explain it, please?
$(1,2), (2,3) \implies (1,3)$
$(1,3), (3,1) \implies (1,1)$
$(2,3), (3,1) \implies (2,1)$
$(2,1),(1,2) \implies (2,2)$
$(3,1), (1,2) \implies (3,2)$
$(3,2), (2,3) \implies (3,3)$
So the answer is $C$.
How do we derive the transitive closure of a relation( on a finite set) from its matrix, given in the following fashion?
For this, we must switch to a graph theoretic interpretation : define a graph whose vertices are the elements of the set, and edges $(v,w)$ are directed from $v \to w$ if and only if $(v,w)$ lies in the relation.
It is easy to see that the adjacency matrix of this graph, is the matrix of the relation, by definition of the graph in terms of the relation.
Now, recall what a transitive relation is : if $(a,b)$ and $(b,c)$ are in the relation, so is $(a,c)$.
What happens when we square the adjacency matrix? If we call the adjacency matrix $A$, then note that $(A^2)_{ij} = \sum_{k} A_{ik}A_{kj}$, where $i,j$ are vertices of the graph, and $k$ runs over all vertices, with $A_{ik} = 1 \iff (i,k)$ is part of the relation. Consequently, we have the following : $(i,j)$ belongs to the transitive closure if $A^2_{ij} \geq 1$, because if the sum is non-negative, then there exists $k$ such that $A_{ik}A_{kj} = 1$ i.e. each one of them is $1$, and hence $(i,k)$ and $(k,j)$ are in the relation, so $(i,j)$ is in the transitive closure.
Similarly, if $A^n_{ij} = \sum_{k_1,...,k_{n-1}} A_{ik_1}A_{k_1k_2}...A_{k_{n-1}}j$ is positive, then $(i,j)$ belongs to the transitive closure.
Note that the converse is also true : we have that $(i,j)$ lies in the transitive closure , then for some $n$, we have $A^n_{ij} > 0$. I leave you to see this as an exercise : try to show that the relation defined by $i \sim j \iff \exists n, A^n_{ij} > 0$ is a transitive relation(hint : think of sum of powers) : therefore, this contains the transitive closure, so every element in the transitive closure must have this property.
Consequently, for easy enough adjacency matrices, it is enough to see which $(i,j)$ satisfy $A^n_{ij} > 0$ for some $n$. In our case, $A$ is a permutation matrix : in fact,the permutation $(132)$ in cycle notation. Therefore, $A^2$ is the permutation matrix of $(123)$, and finally $A^3 = I$, the permutation matrix of the trivial permutation. Now, $A^n$ repeat, so a simple observation of the permutation matrices gives the answer rather than looking explicitly for transitive pairs.