What is a good hash function for small nonsingular matrices over a field $\mathbb{F}_p$ for $p$ prime? I'm looking for an integer function which is close to being injective (but not necessarily perfectly injective) and doesn't take too long to compute in Matlab.

Things I've tried include the trace, the 3 diagonal elements (this can be turned into an integer function $A \mapsto A_{11}+pA_{22}+p^2A_{33}+...$), 4 randomly chosen elements, and the 3 column sums. But all of these make my program take an unreasonably long time for groups of order more than a few thousand.

Many thanks for any help with this!

  • 1
    $\begingroup$ Does the hash value need to be in $\mathbb F_p$? $\endgroup$ – axblount Aug 28 '12 at 17:20
  • $\begingroup$ No, not necessarily. It should be an integer though (which is why I ruled out e.g. sum of eigenvalues). $\endgroup$ – Harry Macpherson Aug 28 '12 at 17:23
  • $\begingroup$ What exactly does "close to being injective" mean here? IOW how large should/can the values be. For example, there are $(p^2-1)(p^2-p)$ (or close to $p^4$) non-singular 2x2 matrices, so will you allow values up to $p^4$ or is something smaller ok? (for large $p$ nearly all matrices are non-singular, so...) $\endgroup$ – Jyrki Lahtonen Aug 28 '12 at 17:47
  • $\begingroup$ Oh, and sum of eigenvalues (counted suitably, i.e. with multiplicities as roots of the characteristic polynomial, and in a suitable extension field of $\mathbb{F}_p$) is always the trace, so it is an element of $\mathbb{F}_p$. $\endgroup$ – Jyrki Lahtonen Aug 28 '12 at 17:49
  • $\begingroup$ @JyrkiLahtonen: values up to $p^4$ should be fine. The primes I'm considering are all less than 15. By 'close to being injective', I mean it doesn't matter if two or three matrices have the same hash function, but not twenty matrices. $\endgroup$ – Harry Macpherson Aug 28 '12 at 18:43

There is a very simple algorithm which gives you a hash function, assuming you store your matrix entries with integers in $\{0,1,...,p-1\}$:

hash = 0
for i=1..n
  for j=1..n

Also please note that the examples you provide are not really good hash functions. There are way too many collisions, which would give serious performance hits if used in e.g. a hash table. The example I provided above is a perfect hash function (i.e. an injective map from the $\mathbb{F}_p$ matrices to $\mathbb{Z}$), so no collisions can exist here (unless $n$ and $p$ are large enough to cause overflow, but even then the probability is very small).

I don't think one can do much better than this, since any good hash would take all matrix entries into account, and this only does one addition and one multiplication per entry. If this is still not working for you, chances are that you don't just need a hash.

  • $\begingroup$ Thanks - this is more or less what I ended up using! $\endgroup$ – Harry Macpherson Oct 14 '12 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.