10
$\begingroup$

In general, can the Zariski closure of the semigroup of matrices $\langle M_1, \ldots, M_k \rangle$ be algorithmically computed (at least in theory)?

For this purpose I'm happy to assume the matrices have rational entries, or are otherwise "nice". If the answer is "no", are there known classes of matrices for which these Zariski closures are effectively computable? (I know that the answer is "yes" for unitary matrices over algebraic numbers.)

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What do you mean by computable in this context? It might not even be countable. $\endgroup$
    – Benjamin Steinberg
    Commented Aug 30, 2017 at 23:36
  • 2
    $\begingroup$ I'm looking for an effective representation of the Zariski closure, for instance a finite list of the polynomials that generate the corresponding ideal. $\endgroup$
    – Joël Ouaknine
    Commented Aug 31, 2017 at 17:23

1 Answer 1

Reset to default
4
$\begingroup$

This problem has been solved (the answer is 'yes') in the paper "Polynomial Invariants for Affine Programs", by Ehud Hrushovski, Joël Ouaknine, Amaury Pouly, and James Worrell, published in the Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 2018. An author copy is available at https://people.mpi-sws.org/~joel/publications/zariski18abs.html .

The main result is stated as Theorem 16 (and Corollary 17 for the real Zariski closure) in Section 6 (it applies in fact more generally to constructible -- not merely finite -- sets of generators).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .