The average-case complexity of the Word Problem for groups of matrices over~$\mathbb{Q}$ is linear

Frédérique Bassino, Cyril Nicaud, Vincent Jugé +1

We show that the Word Problem in finitely generated subgroups of ${\text{GL}}_d(\mathbb{Q})$ can be solved in linear average-case complexity, both when the input words are chosen u…