Re: Generalization of Greater to matrices

*To*: mathgroup at smc.vnet.net*Subject*: [mg20303] Re: [mg20278] Generalization of Greater to matrices*From*: BobHanlon at aol.com*Date*: Tue, 12 Oct 1999 03:39:36 -0400*Sender*: owner-wri-mathgroup at wolfram.com

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. >