[R] Add transitivity to a matrix?
Eric Berger
er|cjberger @end|ng |rom gm@||@com
Tue Jun 18 15:33:40 CEST 2019
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.
>
> 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]]
More information about the R-help
mailing list