On the relative power of algebraic approximations of graph isomorphism

We compare the capabilities of two approaches to approximating graph isomorphism using linear algebraic methods: the emph{invertible map tests} (introduced by Dawar and Holm) and proof systems with algebraic rules, namely emph{polynomial calculus}, emph{monomial calculus} and emph{Nullstellensatz calculus}. In the case of fields of characteristic zero, these variants are all essentially equivalent to the the Weisfeiler-Leman algorithms. In positive characteristic we show that the invertible map method can simulate the monomial calculus and identify a potential way to extend this to the monomial calculus.