Vol. 14, No. 10, 2020

 Recent Issues
 The Journal About the Journal Editorial Board Editors’ Interests Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement ISSN: 1944-7833 (e-only) ISSN: 1937-0652 (print) Author Index To Appear Other MSP Journals
Algorithms for orbit closure separation for invariants and semi-invariants of matrices

Harm Derksen and Visu Makam

Vol. 14 (2020), No. 10, 2791–2813
Abstract

We consider two group actions on $m$-tuples of $n×n$ matrices with entries in the field $K$. The first is simultaneous conjugation by ${GL}_{n}$ and the second is the left-right action of ${SL}_{n}×{SL}_{n}$. Let $\overline{K}$ be the algebraic closure of the field $K$. Recently, a polynomial time algorithm was found to decide whether $0$ lies in the Zariski closure of the ${SL}_{n}\left(\overline{K}\right)×{SL}_{n}\left(\overline{K}\right)$-orbit of a given $m$-tuple by Garg, Gurvits, Oliveira and Wigderson for the base field $K=ℚ$. 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 $m$-tuples intersect. For the conjugation action of ${GL}_{n}\left(\overline{K}\right)$ a polynomial time algorithm for orbit closure separation was given by Forbes and Shpilka in characteristic $0$. Here, we give a polynomial time algorithm for the orbit closure separation problem for both the conjugation action of ${GL}_{n}\left(\overline{K}\right)$ and the left-right action of ${SL}_{n}\left(\overline{K}\right)×{SL}_{n}\left(\overline{K}\right)$ in arbitrary characteristic. We also improve the known bounds for the degree of separating invariants in these cases.

Keywords
orbit closure intersection, null cone, matrix semi-invariants, matrix invariants, separating invariants
Mathematical Subject Classification 2010
Primary: 13A50
Secondary: 14L24, 68W30