We prove that the solvability of systems of linear equations and related linear algebraic properties are definable in a fragment of fixed-point logic with counting that only allows polylogarithmically many iterations of the fixed-point operators. This enables us to separate the descriptive complexity of solving linear equations from full fixed-point logic with counting by logical means. As an application of these results, we separate an extension of first-order logic with a rank operator from fixed-point logic with counting, solving an open problem due to Holm [21]. We then draw a connection from this work in descriptive complexity theory to graph isomorphism testing and propositional proof complexity. Answering an open question from [7], we separate the strength of certain algebraic graph-isomorphism tests. This result can also be phrased as a separation of the algebraic propositional proof systems “Nullstellensatz” and “monomial PC”.

@inproceedings{GroheP17,
  title = {Descriptive complexity of linear equation systems and applications to propositional proof complexity},
  author = {Martin Grohe and Wied Pakusa},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005081}
}