# [R] Add transitivity to a matrix?

Martin Maechler m@ech|er @end|ng |rom @t@t@m@th@ethz@ch
Tue Jun 18 15:01:09 CEST 2019

```>>>>> peter dalgaard
>>>>>     on Tue, 18 Jun 2019 11:45:39 +0200 writes:

> Sounds like this is isomorphic to reachability in graph
> theory. I wonder if

>   (sum_1^n M^i) > 0

> would suffice?

neat! (and I guess correct)

> -pd

Which reminds me that in the relatively distant past as
maintainer of the 'expm' package I had introduced "%^%" (to
compute matrix *integer* powers) with this first part of help() :

--------------------------------------------------------------------------
Matrix Power

Description:

Compute the k-th power of a matrix. Whereas ‘x^k’ computes
_element wise_ powers, ‘x %^% k’ corresponds to k - 1 matrix
multiplications, ‘x %*% x %*% ... %*% x’.

Usage:

x %^% k

Arguments:

x: a square matrix.

k: an integer, k >= 0.

Details:

Argument k is coerced to integer using as.integer.

The algorithm uses O(log2(k)) matrix multiplications.

Value:

A matrix of the same dimension as ‘x’.

Note:

If you think you need ‘x^k’ for k < 0, then consider instead
‘solve(x %^% (-k))’.

........
........

--------------------------------------------------------------------------

and I had thought / wondered to myself if this should not be
brought into base R [or then at least 'Matrix' which is
installed with R (almost surely)] but I think never got around
to propose that.

Opinions?

>> On 18 Jun 2019, at 02:08 , Duncan Murdoch
>> <murdoch.duncan using gmail.com> wrote:
>>
>> On 17/06/2019 7:34 p.m., Bert Gunter wrote:
>>> 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.
>>
>> Right, that's a good point.
>>
>> Duncan Murdoch
>>
>>> 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
>>> <mailto: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 <mailto:R-help using r-project.org>
>>> mailing list -- To UNSUBSCRIBE and more, see
>>> http://www.R-project.org/posting-guide.html and provide
>>> commented, minimal, self-contained, reproducible code.
>>>
>>
>> ______________________________________________
>> R-help using r-project.org mailing list -- To UNSUBSCRIBE and
>> more, see https://stat.ethz.ch/mailman/listinfo/r-help
>> http://www.R-project.org/posting-guide.html and provide
>> commented, minimal, self-contained, reproducible code.

> --
> Peter Dalgaard, Professor, Center for Statistics,
> Frederiksberg, Denmark Phone: (+45)38153501 Office: A 4.23
> Email: pd.mes using cbs.dk Priv: PDalgd using gmail.com

> ______________________________________________
> R-help using r-project.org mailing list -- To UNSUBSCRIBE and
> more, see https://stat.ethz.ch/mailman/listinfo/r-help