[R] Add transitivity to a matrix?

Tue Jun 18 16:03:02 CEST 2019

>>>>> Eric Berger 
>>>>>     on Tue, 18 Jun 2019 16:33:40 +0300 writes:

    > That's what my code does.
    > On Tue, Jun 18, 2019 at 4:27 PM Jeff Newmiller <jdnewmil using dcn.davis.ca.us>
    > wrote:

    >> Assuming Peter's equation applies, I think a direct for loop with
    >> multiplication would be a more efficient way to obtain this answer than
    >> repeated use of a power operator.

Of course! .. I was not suggesting it for this case where all
powers are needed !

    >> On June 18, 2019 8:01:09 AM CDT, Martin Maechler <
    >> maechler using stat.math.ethz.ch> wrote:
    >> >>>>>> 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
    >> >    >>> https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do
    >> >    >>> read the posting guide
    >> >    >>> 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
    >> >    >> PLEASE do read the posting guide
    >> >    >> http://www.R-project.org/posting-guide.html and provide
    >> >    >> commented, minimal, self-contained, reproducible code.
    >> >
    >> >    > --
    >> >    > Peter Dalgaard, Professor, Center for Statistics,
    >> >    > Copenhagen Business School Solbjerg Plads 3, 2000
    >> >    > 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
    >> >    > PLEASE do read the posting guide
    >> >    > 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
    >> >PLEASE do read the posting guide
    >> >http://www.R-project.org/posting-guide.html
    >> >and provide commented, minimal, self-contained, reproducible code.
    >> 
    >> --
    >> Sent from my phone. Please excuse my brevity.
    >> 
    >> ______________________________________________
    >> R-help using r-project.org mailing list -- To UNSUBSCRIBE and more, see
    >> https://stat.ethz.ch/mailman/listinfo/r-help
    >> PLEASE do read the posting guide
    >> http://www.R-project.org/posting-guide.html
    >> and provide commented, minimal, self-contained, reproducible code.
    >> 

    > [[alternative HTML version deleted]]