  Invertible map equivalences are approximations of graph isomorphism that
refine the well-known Weisfeiler-Leman method. They are parametrised by a
number k and a set Q of primes. The intuition is that two graphs G and H which
are equivalent with respect to k-Q-IM-equivalence cannot be distinguished by a
refinement of k-tuples given by linear operators acting on vector spaces over
fields of characteristic p, for any p in Q. These equivalences first appeared
in the study of rank logic, but in fact they can be used to delimit the
expressive power of any extension of fixed-point logic with linear-algebraic
operators. We define an infinitary logic with k variables and all
linear-algebraic operators over finite vector spaces of characteristic p in Q
and show that the k-Q-IM-equivalence is the natural notion of elementary
equivalence for this logic.
  By means of a new and much deeper algebraic analysis of a generalized
variant, for any prime p, of the CFI-structures due to Cai, F\"urer, and
Immerman, we prove that, as long as Q is not the set of all primes, there is no
k such that k-Q-IM-equivalence is the same as isomorphism. It follows that
there are polynomial-time properties of graphs which are not definable in the
infinitary logic with all Q-linear-algebraic operators and finitely many
variables, which implies that no extension of fixed-point logic with
linear-algebraic operators can capture PTIME, unless it includes such operators
for all prime characteristics. Our analysis requires substantial algebraic
machinery, including a homogeneity property of CFI-structures and Maschke's
Theorem, an important result from the representation theory of finite groups.
