On the Computation of the Algebraic Closure of Finitely Generated Groups of Matrices

We investigate the complexity of computing the Zariski closure of a finitely generated group of matrices. The Zariski closure was previously shown to be computable by Derksen, Jeandel and Koiran, but the termination argument for their algorithm appears not to yield any complexity bound. In this paper we follow a different approach and obtain a bound on the degree of the polynomials that define the closure. Our bound shows that the closure can be computed in elementary time. We describe several applications of this result, e.g., concerning quantum automata and quantum universal gates. We also obtain an upper bound on the length of a strictly increasing chain of linear algebraic groups, all of which are generated over a fixed number field.