Orbit-Stabilizer problem for $GL(\mathbb Q,n)$ (Algorithmic approach)

Question

The paper [1, section 1] mentions that the Orbit-Stabilizer problem is undecidable for general matrix groups. So my question is if the statement means the problem is undecidable for $G=GL(\mathbb Q,n)$.

Or, more generally, what does the notion of general matrix groups point to? The reference 2 suggests that it should apply for $GL(F,n)$ where $F$ is a field (potentially only infinite). Is there some reference available for the proof of such a statement?

Note. The definition of the Orbit-Stabilizer problem can be found in [1, p. 1], or it is summarised in Qiaochu Yuan's post.

[1]: Bettina Eick and Gretchen Ostheimer. 2003. On the orbit-stabilizer problem for integral matrix actions of polycyclic groups. Math. Comput. 72, 243 (July 2003), 1511–1529. https://doi.org/10.1090/S0025-5718-03-01493-5

Edit: Thanks all for the comments/answers. The ideas provided by Qiaochu Yuan should work for every infinite field. So does the undecidability follow from the fact that the stabilizer $\operatorname{Stab}(e_1)$ is not finitely-generated?

Answer 1

To actually give a definition of "the orbit-stabilizer problem" (which is two problems), as taken from the linked paper: for a group $G$ and a representation $\rho : G \to GL_n(\mathbb{Q})$,

• the orbit problem is the question of determining when two vectors $v, w \in \mathbb{Q}^n$ lie in the same $G$-orbit, and
• the stabilizer problem is, given $v \in \mathbb{Q}^n$, to compute a set of generators for the stabilizer $\text{Stab}_G(v)$.

When $G = GL_n(\mathbb{Q})$ itself the orbit problem is trivial, since every nonzero vector lies in a single orbit. The stabilizer problem, suitably interpreted, is also easy: it suffices to compute the stabilizer of any nonzero vector, which WLOG we can take to be $e_1 = (1, 0, 0, \dots )$, which has stabilizer the set of matrices of the block form

$$\left[ \begin{array}{cc} 1 & v' \\ 0 & X \end{array} \right]$$

where $v' \in \mathbb{Q}^{n-1}$ is a row vector, $X \in GL_{n-1}(\mathbb{Q})$, and $0 \in \mathbb{Q}^{n-1}$ is a column vector. This is not a finitely generated group but I guess you could write down generators using row and column operations if you really wanted to, although I think this matrix description is simpler.