title: Making a matrix transitive R
body: <p>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?</p>
  
  <p>Take the matrix Mx</p>
  
  <pre><code> 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
  </code></pre>
  
  <p>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.</p>
  
  <pre><code>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
  </code></pre>
  
  <p>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?Thanks</p>
  
  <p>n^3 function:</p>
  
  <pre><code>   # Repeat loop three times for completion
       for (rep in 1:3) {
     # For every individual i
         for (i in 1:N) {
     # For every individual j
           for (j in 1:N) {
     # For every individual k
             for (k in 1:N) {
      # If i and j are related and j and k are related
              if (Mx[i,j] == 1 &amp;&amp; Mx[j, k] == 1) {
          #i and k are related
                Mx[i,k] &lt;- 1
                Mx[k,i] &lt;- 1
                      }
                    }
                 }
              }
           }
  </code></pre>