Opened 10 years ago

# The Hash function for matrices suffers from many collisions with permutation matrices — at Version 1

Reported by: Owned by: nthiery jason, was major sage-8.1 linear algebra Weyl groups, permutation matrices, hash sage-combinat N/A

The current hash function for generic dense matrices suffers from hard collisions with permutation matrices. For example: all permutation matrices of size 4 have hash 0!

```    sage: def mat(p): m = p.to_matrix(); m.set_immutable(); return m
sage: [ hash(mat(p)) for p in Permutations(4) ]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
```

In general, we would hope to get n! below:

```    sage: len(set([ hash(mat(p)) for p in Permutations(1) ]))
1
sage: len(set([ hash(mat(p)) for p in Permutations(2) ]))
1
sage: len(set([ hash(mat(p)) for p in Permutations(3) ]))
5
sage: len(set([ hash(mat(p)) for p in Permutations(4) ]))
1
sage: len(set([ hash(mat(p)) for p in Permutations(5) ]))
16
sage: len(set([ hash(mat(p)) for p in Permutations(6) ]))
16
sage: len(set([ hash(mat(p)) for p in Permutations(7) ]))
32
sage: len(set([ hash(mat(p)) for p in Permutations(8) ]))
1
```

I stumbled on this when profiling some code using Weyl groups that heavily used caching (the hash of a weyl group element is the hash of the underlying matrix). I gained a speed factor of 10x by just tweaking the hash of matrices as in the attached patch. Now, I have no idea if in general that would be a good hash for matrices, so please some expert write an appropriate patch.

Cheers,

Nicolas

### comment:1 Changed 10 years ago by nthiery

• Description modified (diff)
• Summary changed from The Hash function for matrices has many collisions with permutation matrices: to The Hash function for matrices suffers from many collisions with permutation matrices
Note: See TracTickets for help on using tickets.