title: Detecting cycles in an adjacency matrix
body: <p>Let <code>A</code> be the adjacency matrix for the graph <code>G = (V,E)</code>. <code>A(i,j) = 1</code> if the nodes <code>i</code> and <code>j</code> are connected with an edge, <code>A(i,j) = 0</code> otherwise.</p>
  
  <p>My objective is the one of understanding whether <code>G</code> is acyclic or not. A cycle is defined in the following way:</p>
  
  <ul>
  <li><code>i</code> and <code>j</code> are connected: <code>A(i,j) = 1</code></li>
  <li><code>j</code> and <code>k</code> are connected: <code>A(j,k) = 1</code></li>
  <li><code>k</code> and <code>i</code> are connected: <code>A(k,i) = 1</code></li>
  </ul>
  
  <p>I have implemented a solution which navigates the matrix as follows:</p>
  
  <ul>
  <li>Start from an edge <code>(i,j)</code></li>
  <li>Select the set <code>O</code> of edges which are outgoing from <code>j</code>, i.e., all the 1s in the <code>j</code>-th row of <code>A</code></li>
  <li>Navigate <code>O</code> in a DFS fashion</li>
  <li>If one of the paths generated from this navigation leads to the node <code>i</code>, then a cycle is detected</li>
  </ul>
  
  <p>Obviously this solution is very slow, since I have to evaluate all the paths in the matrix. If <code>A</code> is very big, the required overhead is very huge. I was wondering whether there is a way of navigating the adjacency matrix so as to find cycles without using an expensive algorithm such as DFS.</p>
  
  <p>I would like to implement my solution in MATLAB.</p>
  
  <p>Thanks in advance,</p>
  
  <p>Eleanore.</p>