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: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of alex pegucci Sent: Thursday, October 28, 2004 5:27 PM To: [EMAIL PROTECTED] 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 ______________________________________________ [EMAIL PROTECTED] mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html ______________________________________________ [EMAIL PROTECTED] mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
