/* Determine whether a digraph has cycles.
Suppose that the vertices of a digraph are numbered 1,2,...,N.
Let A be the connection matrix of the graph, where
A(i,j) = 1, if there is a directed edge from vertex j to vertex i
= 0, if not.
DEFINITION. Write j->i if there is a directed path in the digraph leading
from vertex j to vertex i.
LEMMA. j->i if and only if A^p(i,j)>0 for some integer power p.
PROOF. A^p(i,j)>0 if and only if there is a p-step path i->...->j. []
DEFINITION. An cycle in the digraph is an ordered list of vertices
C={i1,...,iK} such that j->i for every pair i,j in C.
DEFINITION. Vertex i is a pure source if there is no vertex j with j->i.
DEFINITION. Vertex j is a pure sink if there is no vertex i with j->i.
LEMMA. Vertex i is a pure source if and only if row i of A is zero.
Vertex j is a pure sink if and only if column j of A is zero.
PROOF. If row i of A is zero, then row i of A^p will be zero for all p>0.
Likewise, if column i of A is zero, then column i of A^p will be zero for
all p>0. []
THEOREM. A has a cycle {i1,...,iK} if and only if A/(Id - c*A) has a
strictly positive submatrix consisting of the rows and columns labeled
i1,i2,...,iK, where 0) If there is a cycle {i1,...,iK}, then for each pair (i,j) of
vertices in the cycle, there will be some power p=p(i,j) for which the
matrix A^p will have a strictly positive coefficient A^p(i,j). But then
B(i,j)>0, since it is the sum of nonnegative numbers.
(<==) Suppose B(i,j)>0 for all pairs (i,j) taken from {i1,...,iK}. Then
for each such pair (i,j) there must be some finite power p=p(i,j) such
that A^p(i,j)>0. []
DEFINITION. The eventual connection matrix C of a digraph A has the
coefficients C(i,j)=1, if j->i, with C(i,j)-0 otherwise.
LEMMA. Put B=A/(Id-cA) for 00. []
DEFINITION. Let r=r(C) be the vector of row sums of the {0,1}-matrix C.
Then r(C) = C*(1,...,1)'. Let r0=r0(C) be the nondecreasing rearrangement
of r(C).
DEFINITION. Let s=s(C) be the vector of column sums of the matrix C.
Then s(c) = (1,...,1)*C. Let s0=s0(C) be the nondecreasing rearrangement
of s(C).
DEFINITION. A trivial cycle is a single vertex i for which A(i,i)=1.
THEOREM. A contains no cycles if its eventual connection matrix C
satisfies r0(C) < (1,2,...,N).
*/
#include
/* #define N 42 */
#define N 38
typedef int Matrix[N][N];
void
multiply( Matrix out, Matrix inleft, Matrix inright )
{
int i,j,k;
for(i=0; i