C-equivalence aware hash function

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.

I would like to build an easily computable "C-equivalence aware
hash function", transforming an element of S into a (say) 256-bit
string, with the property that two C-equivalent matrixes always
(or overwhelmingly often, if that's the best we can do) give
the same results, but it is computationaly impossible to exhibit
distinct matrixes with the same hash that are not C-equivalent.

An application is to organize a dictionary of SAT instances
in Conjunctive Normal Form, in a manner allowing search
within C-equivalence.

I have some heuristics repeately sorting the matrix [normalizing
columns polarity, line and columns orders, according to number of
0 and +1 in previously sorted subsets of columns and lines];
but I fail to prove full "C-equivalence awareness", and conjecture
I do not reach it for some highly regular subset of matrixes.

TIA,

  François Grieu
Received on Sat Dec 3 04:20:11 2005