Algorithms for orbit closure separation for invariants and semi-invariants of matrices
Harm Derksen, Visu Makam · Algebra & Number Theory · 2020
We consider two group actions on [math] -tuples of [math] matrices with entries in the field [math] . The first is simultaneous conjugation by [math] and the second is the left-right action of [math] . Let [math] be the algebraic closure of the field [math] . Recently, a polynomial time algorithm was found to decide whether [math] lies in the Zariski closure of the [math] -orbit of a given [math] -tuple by Garg, Gurvits, Oliveira and Wigderson for the base field [math] . An algorithm that also works for finite fields of large enough cardinality was given by Ivanyos, Qiao and Subrahmanyam. A more general problem is the orbit closure separation problem that asks whether the orbit closures of two given [math] -tuples intersect. For the conjugation action of [math] a polynomial time algorithm for orbit closure separation was given by Forbes and Shpilka in characteristic [math] . Here, we give a polynomial time algorithm for the orbit closure separation problem for both the conjugation action of [math] and the left-right action of [math] in arbitrary characteristic. We also improve the known bounds for the degree of separating invariants in these cases.