# [R] Add transitivity to a matrix?

Bert Gunter bgunter@4567 @end|ng |rom gm@||@com
Tue Jun 18 01:34:45 CEST 2019

```Depends on what you mean by "simple" of course, but suppose that:

M[i,j] & M[j,k] & M[k,n] are TRUE and M[i,k] and M[i,n] are FALSE.
Then the procedure would see that M[i,k] needs to change to TRUE, but not
that M[i,n] needs to also become TRUE *after* M[i,k] changes.  This seems
to imply that an iterative solution is necessary.

One such procedure, via repeated matrix multiplication to check for and
impose transitivity, appears to be suggested by this discussion:
https://math.stackexchange.com/questions/228898/how-to-check-whether-a-relation-is-transitive-from-the-matrix-representation

Cheers,
Bert

On Mon, Jun 17, 2019 at 10:29 AM Duncan Murdoch <murdoch.duncan using gmail.com>
wrote:

> On 17/06/2019 1:19 p.m., Duncan Murdoch wrote:
> > Suppose I have a square logical matrix M which I'm thinking of as a
> > relation between the row/column numbers.
> >
> > I can make it into a symmetric relation (i.e. M[i,j] being TRUE implies
> > M[j,i] is TRUE) by the calculation
> >
> > M <- M | t(M)
> >
> > Is there a simple way to ensure transitivity, i.e. M[i,j] & M[j,k] both
> > being TRUE implies M[i,k] is TRUE?
> >
> > The operation should only change FALSE or NA values to TRUE values; TRUE
> > values should never be changed.
>
> I also want the changes to be minimal; changing everything to TRUE would
> satisfy transitivity, but isn't useful to me.
>
> Duncan Murdoch
>
> ______________________________________________
> R-help using r-project.org mailing list -- To UNSUBSCRIBE and more, see
> https://stat.ethz.ch/mailman/listinfo/r-help