AKT-09/Tricolourability

The tricolourability criterion for knot diagrams may be equivalently expressed as: is it possible to associate to each strand a member of Z/3Z such that, for each crossing, the sum of the three numbers associated to the three strands involved is 0 mod 3 (that is, the three numbers are either all distinct or all the same) while excluding the case of associating the same number to every strand?

This fact can be exploited to give an algorithm for determining tricolourability of a knot diagram whose complexity is polynomial in the number of crossings. (A naive test which tried all possible colourings would require 3^(number of strands) checks.)

Define the variables $S_{1},...,S_{n}$ which are associated with the strands of a knot diagram D. Each crossing yields an equation of the form $S_{a}+S_{b}+S_{c}=0$. We can also (without loss of generality) assume $S_{1}=0$. Let M be the matrix over Z/3Z encoding the aforementioned relations. The nullity of M is non-zero if and only if there is a valid tricolouring of D.