Re: Re: Generalization of Greater to matrices
- To: mathgroup at smc.vnet.net
- Subject: [mg20307] Re: [mg20303] Re: [mg20278] Generalization of Greater to matrices
- From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>
- Date: Fri, 15 Oct 1999 20:20:39 -0400
- Sender: owner-wri-mathgroup at wolfram.com
Just a small observation that you have probably also noticed. The concept
of "dominating" as defined below (and in the original message) is
non-transitive. For example {5,5,5,5,1,1,1} dominates {4,4,4,4,3,3,3} which
dominates {6,6,6,3,2,2,2}. But {6,6,6,3,2,2,2} dominates {5,5,5,5,1,1,1}. A
non-transitive binary relation is not an ordering and sorting according to
it does not really make sense.
--
Andrzej Kozlowski
Toyama International University
JAPAN
http://sigma.tuins.ac.jp
http://eri2.tuins.ac.jp
----------
>From: BobHanlon at aol.com
>To: mathgroup at smc.vnet.net
>Subject: [mg20307] [mg20303] Re: [mg20278] Generalization of Greater to matrices
>Date: Tue, 12 Oct 1999 03:39:36 -0400
>
> Hermann,
>
> Here is an approach:
>
> For a matrix (or vector) m1 to be greater than matrix (or vector) m2, then
> each element of m1 must be greater than or equal to its corresponding element
> of m2 and at least one element of m1 must be greater than its corresponding
> element of m2.
>
> greaterMatrix[m1_List, m2_List] /; Dimensions[m1] == Dimensions[m2] :=
> Module[{pairs =
> Transpose[
> Flatten /@ {m1, m2}]}, (And @@ (GreaterEqual[Sequence @@ #] & /@
> pairs)) && (Or @@ (Greater[Sequence @@ #] & /@ pairs))]
>
> For a matrix (or vector) m1 to dominate matrix (or vector) m2, then n
> elements (where n is greater than 1/2 the number of elements) of m1 must be
> greater than the corresponding elements of m2.
>
> dominantMatrix[m1_List, m2_List, n_Integer] /;
> Dimensions[m1] == Dimensions[m2] &&
> Times @@ Dimensions[m1] >= n >=
> Ceiling[(Times @@ Dimensions[m1] + 1)/2] :=
> Count[(Greater[Sequence @@ #1] & ) /@
> Transpose[Flatten /@ {m1, m2}], True] >= n
>
> M1 = Table[{{Random[Integer, {0, 10}]}, {Random[Integer, {0, 10}]}}, {3}]
> M2 = Table[{{Random[Integer, {0, 10}]}, {Random[Integer, {0, 10}]}}, {3}]
> M3 = Table[{{Random[Integer, {0, 10}]}, {Random[Integer, {0, 10}]}}, {3}]
>
> {{{8}, {7}}, {{5}, {3}}, {{9}, {10}}}
> {{{9}, {8}}, {{10}, {10}}, {{6}, {3}}}
> {{{5}, {5}}, {{0}, {1}}, {{5}, {4}}}
>
> Test for m1 = m2 and six pairwise comparisons:
>
> pairings = {{M1, M1}, {M1, M2}, {M1, M3}, {M2, M3}, {M2, M1}, {M3, M1}, {M3,
> M2}};
>
> greaterMatrix[Sequence @@ #] & /@ pairings
>
> {False, False, True, False, False, False, False}
>
> dominantMatrix[Sequence @@ Join[#, {4}]] & /@ pairings
>
> {False, False, True, True, True, False, False}
>
> dominantMatrix[Sequence @@ Join[#, {5}]] & /@ pairings
>
> {False, False, True, True, False, False, False}
>
> dominantMatrix[Sequence @@ Join[#, {6}]] & /@ pairings
>
> {False, False, True, False, False, False, False}
>
>
> Bob Hanlon
>
> In a message dated 10/11/1999 6:11:59 AM, hmeier at webshuttle.ch writes:
>
>>I tried to solve the following seemingly not to complicated problem, to
>>no
>>avail.
>>
>>M1, M2, M3 ... are matrices of equal dimensions. The task is to find
>>the
>>"greatest" among them. The elements of this matrix, say M2, should be
>>(in
>>principle) greater than all the corresponding elements of M1, M3, Mx....
>>Furthermore, a kind of a "slack variable" (s) should be introduced.
>>(Requiring a matrix to be the "strictly greatest" one would be a condition
>>too hard to meet in some of my practical applications.) A matrix should
>>therefore be considered "greatest", if all but s elements (say 8 out of
>>10)
>>are greater than the corresponding elements of the other matrices. (Such
>>a
>>matrix perhaps could be called "dominating".) The case of s = 0 is that
>>of
>>the "strictly greatest" matrix.
>>
>>Greater or GreaterEqual, Max ... do not work with matrices. Sort accepts
>>{M1,M2,M3 ..}, but there seems to be no built-in functionality to arrive
>>at
>>my desired result.
>>
>>Therefore I tried to set up GreaterMatrix (rather than overloading Greater).
>>GreaterMatrix should also work as an ordering relation in Sort. So
>>Sort[{M1,M2,M3..}, GreaterMatrix] should rank M1, M2, M3 according to the
>>above-mentioned criteria.
>>
>>GreaterMatrix can be (but has not to be) restricted to two-dimensional
>>matrices. The following expressions may be pieces usable for a solution:
>>
>>Outer[Count[(#1 - #2), _?Positive, 2] &, {M1,M2,M3}, {M1,M2,M3}, 1]
>>subtracts M1, M2, M3 from each other and counts the number of positive
>>values in the resulting matrix. A positive value equal to dim
>>(=Apply[Times,Dimensions[M1]]) at position {i,j}, say {2,3}, would
>>indicate that matrix M2 is strictly greater than M3. Outer[Count[(#1 -
>>#2),
>>_?(#>=(dim-s)?), 2] &, {M1,M2,M3}, {M1,M2,M3}, 1] may indicate a matrix
>>that
>>is just "dominating" another one.
>>
>>FoldList[GreaterMatrix, M0, {M1, M2, M3}]]//Rest - with M0 a starting matrix
>>like Table[-10^10, {First[dim]},{Last[dim]}] - may give a succession of
>>"increasing" matrices. (For this also see Mathematica Book, Online
>>Version, Further Examples to Max.)
>>
>>There is also TopologicalSort in package DiscreteMath`Combinatorica` which
>>may or may not be useful in the present context. (I am not sure if
>>TopologicalSort corresponds to the topological sort as explained in Knuth,
>>The Art of Computer Programming, Vol. 1, 3rd ed., ch. 2.2.3, p. 261 - 271.)
>>
>>The problem looks like quite a challenge (to me as a mid-level user). I
>>was
>>not able to put my pieces of code together into a working program that
>>would
>>pass all my tests. I would appreciate contributions of Mathematica experts.
>>Such contributions perhaps may even show - possible - extensions to Greater,
>>GreaterEqual, Less, LessEqual, Max, Min ... for handling matrices in a
>>future version of Mathematica.
>>
>