Re: C-equivalence aware hash function

Francois Grieu wrote:
>For some fixed positive n and m, I consider the set S of matrixes
>of n rows, m columns, containing elements of the set {-1,0,+1}.
>
>Two matrixes in S are defined to be C-equivalent when we can go
>from one to the other by swaping rows, swaping colums, and/or
>changing polarity of whole columns.
>
>C-equivalence is obviously an equivalence relation.

Note that swapping rows commutes with swapping columns, and
changing polarity commutes with both.

Given a matrix M, you can first canonicalize it with respect to
polarity (e.g., by making each column have minimum number of positive
elements), then canonicalize it with respect to column-swaps (by
sorting the columns), and finally canonicalize it with respect to
row-swaps (by sorting the rows). The result will be canonical
representative for M with respect to C-equivalent. You can then
hash that canonical representative.

Does this work?
Received on Sat Dec 3 04:20:12 2005