Re: Algorithm to determine matrix similarity

On 19 Jan, 23:17, Rainer Rosenthal <r.rosent...@xxxxxx> wrote:
quasi wrote:

But let me ask -- how do you arrive at A' and B'?

Oops, my first idea was, to let you see my Maple code.
But then I had to admit: it was gone somewhere in the
Bit-Nirwana. Then I thought it would be easy to
program the lines again. And then ... I wasn't sure
any more whether I had programmed it ever. I remember
that for my matrices M1 and M2 (see below) I had been
lucky to find a correspondence establishing their
equivalence. After that I was told the sorting trick
and thought: "how ingenious!" I could have sworn that I
had tested the trick, just for fun, but obviously I
did not :-(

I will have to think again, but in the meantime I will
show you my 16x16 matrices M1 and M2 as well as
my correspondence K:{1..16}->{1..16} which satisfies
M1[i,j] = M2[K[i],K[j]] for all i and j.
It took me quite a while and I felt like Sherlock Holmes
having found
K = [2,3,13,8,4,9,7,11,6,1,12,10,5,14,15,16], i.e.

n    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
---------------------------------------------------
K[n] 2  3 13  8  4  9  7 11  6  1 12 10  5 14 15 16

My matrices M1 and M2 were:

M1 := Matrix([[4,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3]
             ,[1,4,2,2,3,3,1,1,2,2,3,1,1,2,3,3]
             ,[1,2,4,3,2,3,1,2,1,3,2,2,3,1,1,1]
             ,[1,2,3,4,3,2,2,1,3,1,2,3,2,1,3,3]
             ,[1,3,2,3,4,2,2,3,1,2,1,1,3,3,2,2]
             ,[1,3,3,2,2,4,3,2,2,1,1,3,1,3,1,1]
             ,[2,1,1,2,2,3,4,3,3,1,1,2,3,2,3,3]
             ,[2,1,2,1,3,2,3,4,1,3,1,3,2,2,1,1]
             ,[2,2,1,3,1,2,3,1,4,1,3,2,1,3,2,2]
             ,[2,2,3,1,2,1,1,3,1,4,3,1,2,3,3,3]
             ,[2,3,2,2,1,1,1,1,3,3,4,3,3,1,2,2]
             ,[3,1,2,3,1,3,2,3,2,1,3,4,2,1,1,1]
             ,[3,1,3,2,3,1,3,2,1,2,3,2,4,1,2,2]
             ,[3,2,1,1,3,3,2,2,3,3,1,1,1,4,2,2]
             ,[3,3,1,3,2,1,3,1,2,3,2,1,2,2,4,0]
             ,[3,3,1,3,2,1,3,1,2,3,2,1,2,2,0,4]
            ]);
M2 := Matrix([[4,2,2,2,2,1,1,1,1,1,3,3,3,3,3,3]
             ,[2,4,1,1,3,2,2,1,1,3,2,2,1,3,3,3]
             ,[2,1,4,3,1,2,1,2,3,1,1,3,2,2,3,3]
             ,[2,1,3,4,3,1,2,3,2,1,3,1,2,3,2,2]
             ,[2,3,1,3,4,1,3,2,1,2,2,3,3,1,2,2]
             ,[1,2,2,1,1,4,3,3,2,2,1,3,1,3,2,2]
             ,[1,2,1,2,3,3,4,2,3,2,3,1,1,2,3,3]
             ,[1,1,2,3,2,3,2,4,2,3,1,2,3,1,3,3]
             ,[1,1,3,2,1,2,3,2,4,3,2,1,3,3,1,1]
             ,[1,3,1,1,2,2,2,3,3,4,3,3,2,1,1,1]
             ,[3,2,1,3,2,1,3,1,2,3,4,1,2,2,1,1]
             ,[3,2,3,1,3,3,1,2,1,3,1,4,2,1,2,2]
             ,[3,1,2,2,3,1,1,3,3,2,2,2,4,1,1,1]
             ,[3,3,2,3,1,3,2,1,3,1,2,1,1,4,2,2]
             ,[3,3,3,2,2,2,3,3,1,1,1,2,1,2,4,0]
             ,[3,3,3,2,2,2,3,3,1,1,1,2,1,2,0,4]
            ]);

I'd like to say where these matrices stem from. Any
two different people among the 16 people at a party are
in exactly one of the three relationships 1, 2 or 3,
except for one pair in a different relationship 0.
Both matrices depict such a situation, using entry 4 for
the identity relation. The interesting thing and motivation
for finding these matrices: they are completely "intransitive"
in the following sense: whenever a and b are in the same
relation r as b and c, then a and c are *not* in this same
relation r. (Problem Matx#329-part 4 in de.rec.denksport).
Example: In M1 we have M1[1,2]=1 and M1[2,7]=1; so it is not
         allowed to have M1[1,7]=1. And indeed: M1[1,7]=2.
(It is possible to find a 17x17 matrix with this property,
but 17 is the largest dimension for that.)

Cheers and thanks for your critical remarks. Sorry to the OP,
who liked the sorting idea as well as I did. But I fear he
will get into the same troubles as I did some minutes ago,
trying to "rewrite" my code :-(

Cheers,
Rainer Rosenthal
r.rosent...@xxxxxx

Well, I thought I understood your proposed algorithm and implemented
the following to find the matrix A' (defined in a post above) from A
as follows:
- Define a total order < on the matrices by lexicographical ordering
- done=false;
while (!done)
{
done=true;
for (i=0;i<N-1;i++)
{
At=exchangecolumns(exchangerows(A,i,i+1),i,i+1);
if (At<A)
{
A=At;
done=false;
}
}
}

This is a rather crude variaty of bubblesort. It does find quite a few
equivalence relationships. But in light of the discussion below, I now
am uncertain whether this algorithm always converges to a unique A'
for all matrices in the equivalence class. Will continue to test. If
it works, I intend to optimise the sort algorithm.


.

Relevant Pages

  • Re: A Definition of an Algorithm
    ... implement or express that algorithm. ... partitioned into equivalence classes. ... the set of primitive recursive functions is considered. ... As to your irrelevant comments about trees versus programs as linear ...
    (sci.math.research)
  • Re: A Definition of an Algorithm
    ... The first is seemingly endemic to modern forms of definition: ... define an algorithm as an algorithm without defining what algorithms ... that that the number 42 is the equivalence class of all sets of size ... an algorithm is an equivalence class of programs. ...
    (comp.ai.philosophy)
  • Re: A Definition of an Algorithm
    ... The first is seemingly endemic to modern forms of definition: ... define an algorithm as an algorithm without defining what algorithms ... that that the number 42 is the equivalence class of all sets of size ... programs" to define algorithm just the way modern mathematikers use ...
    (comp.ai.philosophy)
  • Re: Equivalent sets and equivalence relations
    ... Then, equivalence in this is sense, for subsets of some ... The way that some relation is an equivalence relation is uually ... Show that if there is a one-to-one correspondence bewteen a subset A ... darüber muss man schweigen" ...
    (sci.math)
  • Re: A Definition of an Algorithm
    ... Towards a Definition of an Algorithm ... partitioned into equivalence classes. ... the set of primitive recursive functions is considered. ... say when two such trees are ``essentially'' the same. ...
    (comp.ai.philosophy)
Quantcast