[seqfan] Re: SeqFan Digest, Vol 60, Issue 4

Brendan McKay Brendan.McKay at anu.edu.au
Mon Sep 16 16:32:36 CEST 2013


No, it isn't true.  Here's an easy counterexample.  Take two non-equivalent n*n matrices A,B which are in sorted form (i.e. the rows are in increasing order and so are the columns). Now form a 2n*2n matrix by placing A and B in the off-diagonal blocks and zeros in the two diagonal blocks.  This matrix is in sorted form.  Interchanging A and B gives a different matrix that is also in sorted form, and yet it is easily produced from the first matrix by permuting rows and columns.  That is, one equivalence class can contain two different sorted matrices.  I expect that on average the number of sorted matrices per equivalence class is exponentially large.

Brendan.

From: Ron Hardin <rhhardin at att.net<mailto:rhhardin at att.net>>
Reply-To: Ron Hardin <rhhardin at att.net<mailto:rhhardin at att.net>>
Date: Tuesday, 17 September 2013 12:14 AM
To: Brendan McKay <Brendan.McKay at anu.edu.au<mailto:Brendan.McKay at anu.edu.au>>, "seqfan at list.seqfan.eu<mailto:seqfan at list.seqfan.eu>" <seqfan at list.seqfan.eu<mailto:seqfan at list.seqfan.eu>>, "njasloane at gmail.com<mailto:njasloane at gmail.com>" <njasloane at gmail.com<mailto:njasloane at gmail.com>>
Subject: Re: SeqFan Digest, Vol 60, Issue 4

The title looked okay to me.  If all the rows get the same permutation and all the columns get the same permutation, then sorting rows and columns represents the bunch.

Though I lose track of whether order of operations screws up the idea (so a single matrix can wind up with two different sortings) but I assume it doesn't.

rhhardin at mindspring.com<mailto:rhhardin at mindspring.com>
rhhardin at att.net<mailto:rhhardin at att.net> (either)

________________________________
From: Brendan McKay <Brendan.McKay at anu.edu.au<mailto:Brendan.McKay at anu.edu.au>>
To: "seqfan at list.seqfan.eu<mailto:seqfan at list.seqfan.eu>" <seqfan at list.seqfan.eu<mailto:seqfan at list.seqfan.eu>>; "njasloane at gmail.com<mailto:njasloane at gmail.com>" <njasloane at gmail.com<mailto:njasloane at gmail.com>>; "rhhardin at att.net<mailto:rhhardin at att.net>" <rhhardin at att.net<mailto:rhhardin at att.net>>
Sent: Monday, September 16, 2013 8:19 AM
Subject: Re: SeqFan Digest, Vol 60, Issue 4


I looked at the paper.  Proposition 1 is nonsense.  I strongly suggest that nothing be used from this paper without independent checking.

(Meanwhile our mail server has changed and the list is rejecting my posts.)

Brendan.

rhhardin at mindspring.com<mailto:rhhardin at mindspring.com>
rhhardin at att.net<mailto:rhhardin at att.net> (either)







More information about the SeqFan mailing list