Making a matrix transitive R

Question

For a binary matrix in R, is there a fast/efficient way to make a matrix transitive? That is, if [i, j] == 1, and [i, k] == 1, set [j, k] = 1. For example, say we have a square matrix of individuals, and a 1 in a row/column means that they are related. Is there fast way to figure out which individuals are in some way related? Take the matrix Mx ``` Mx a b c d e a 1 1 0 1 0 b 0 1 0 0 0 c 0 0 1 1 0 d 0 0 0 1 0 e 0 0 0 0 1 ``` Since [a, b] == 1, and [a,d] == 1, [b,d] and [d, b] should be set to 1. Similarly, [c, d] == 1, and since a, b, and d are related, there should be 1s for a,b,c,d. The final matrix would look like this, and should be symmetric across the diagonal. ``` Mx a b c d e a 1 1 1 1 0 b 1 1 1 1 0 c 1 1 1 1 0 d 1 1 1 1 0 e 0 0 0 0 1 ``` So for the family example, this would mean a, b, c, and d are related in some way. Right now I have a function that computes this second matrix, but it runs in n^3 time, where n is the number of rows/columns. Is there a faster way to do this?T…

Accepted Answer

Finding the equivalence relation associated to an arbitrary relation boils down to finding the connected components of the corresponding graph. It can be done with depth-first search. It is already implemented in the `igraph` package.

```
library(igraph)
n <- 5
A <- matrix( sample(0:1, n^2, prob=c(.8,.2), replace=T), n, n)
A
#      [,1] [,2] [,3] [,4] [,5]
# [1,]    0    0    0    0    0
# [2,]    0    1    0    0    0
# [3,]    0    0    1    0    1
# [4,]    1    0    1    0    1
# [5,]    0    0    0    0    0
i <- clusters(graph.adjacency(A))$membership
B <- A
B[] <- i[row(A)] == i[col(A)]
B
#     [,1] [,2] [,3] [,4] [,5]
# [1,]    1    0    1    1    1
# [2,]    0    1    0    0    0
# [3,]    1    0    1    1    1
# [4,]    1    0    1    1    1
# [5,]    1    0    1    1    1
```

If you wanted the transitive and reflexive closure (reflexive, transitive, but not necessarily symmetric -- this example was already transitive, but not reflexive):

```
library(relations)
 relation_incidence( reflexive_closure( transitive_closure( as.relation(A) ) ) )
# Incidences:
#   1 2 3 4 5
# 1 1 0 0 0 0
# 2 0 1 0 0 0
# 3 0 0 1 0 1
# 4 1 0 1 1 1
# 5 0 0 0 0 1
```

Making a matrix transitive R

Solution

Problem