Re: C-equivalence aware hash function

Gregory G Rose wrote:
>David Wagner <daw-usenet@taverner.cs.berkeley.edu> wrote:
>>Note that swapping rows commutes with swapping columns [..]
>
>Sorting the rows might unsort the columns. [...]
>I believe I have a counterexample:
>00111
>01011
>10101
>10010
>Note that this is already sorted by columns
>(defining top as most significant). But
>after sorting the rows (defining left to be most
>significant):
>00111
>01011
>10010
>10101
>Now the last two columns are out of order.
>Sorting columns again fixes the problem.

You're right. If we start with either of the two matrices you gave,
and sort by rows then by columns, we get
 00111
 01011
 10001
 10110

However, if we start with the following third matrix (which is equivalent
to your two matrices):
 00111
 01101
 10011
 10100
and sort by rows then by columns, we get something different:
 00111
 01011
 10101
 10010
So, this is indeed a counterexample.

Thanks for the correction. I was led astray by the commutation property.

Still, it remains true that row-swaps commute with column-swaps.
I wonder whether one can use this to good effect somehow.
Received on Sat Dec 3 04:20:28 2005