[R] transitivity

[Huntsinger, Reid]

For transitivity, if P is your incidence matrix of 0s and 1s, then P%*%P has
i,j
entry equal to the number of k with Pik = 1 and Pkj = 1. So you want to
check that when P%*%P has a nonzero (i,j) entry, then Pij = 1 too. 

Acyclicity: more generally the nth matrix power of P counts the number of
paths from i to j of length n in its ij entry. I guess you could check that
the powers all have zeros on the diagonal. (You would want to eliminate any
1s on the diagonal of P (loops in the graph) first, of course.) It's
tempting to compute the infinite sum I + P + P%*%P/2! + P%*%P%*%P/3! + ...
ie the matrix exponential. The powers of P will have zero diagonals if and
only if this sum has 1s on the diagonal. If you can diagonalize P the sum is
easy to compute because the powers diagonalize via the same similarity and
you have the usual exponential for the diagonal entries. But I see some
potential difficulty with numerical accuracy; it might be a good idea to
have a look at a book on graph theory covering analytic methods. 

Reid Huntsinger



Reid Huntsinger

-----Original Message-----
From: r-help-bounces at stat.math.ethz.ch
[mailto:r-help-bounces at stat.math.ethz.ch] On Behalf Of alex pegucci
Sent: Thursday, October 28, 2004 5:27 PM
To: r-help at stat.math.ethz.ch
Subject: [R] transitivity


Dear all,

Is there a function in R that checks transitivity and acyclicity of a
given nXn matrix with entries representing a decision-maker's
comparisons of n objects? Like 

0 1 0 1 1 1
0 0 0 1 0 0
1 0 0 0 1 1
0 0 1 0 0 0
0 1 0 1 0 1
0 1 0 1 0 0

1 represents xPy and 0 represents ~xPy. Is there a vectorized solution
to this? n can be quite large. 

Thanks in advance,

Alex

______________________________________________
R-help at stat.math.ethz.ch mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide!
http://www.R-project.org/posting-guide.html