Vol. 14, No. 10, 2020

Download this article
Download this article For screen
For printing
Recent Issues

Volume 18
Issue 10, 1767–1943
Issue 9, 1589–1766
Issue 8, 1403–1587
Issue 7, 1221–1401
Issue 6, 1039–1219
Issue 5, 847–1038
Issue 4, 631–846
Issue 3, 409–629
Issue 2, 209–408
Issue 1, 1–208

Volume 17, 12 issues

Volume 16, 10 issues

Volume 15, 10 issues

Volume 14, 10 issues

Volume 13, 10 issues

Volume 12, 10 issues

Volume 11, 10 issues

Volume 10, 10 issues

Volume 9, 10 issues

Volume 8, 10 issues

Volume 7, 10 issues

Volume 6, 8 issues

Volume 5, 8 issues

Volume 4, 8 issues

Volume 3, 8 issues

Volume 2, 8 issues

Volume 1, 4 issues

The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
Editors' interests
 
Subscriptions
 
ISSN 1944-7833 (online)
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 GLn and the second is the left-right action of SLn × SLn. Let 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 SLn( K¯) × SLn( K¯)-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 GLn( K¯) 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 GLn( K¯) and the left-right action of SLn( K¯) × SLn( K¯) 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
Milestones
Received: 24 October 2019
Revised: 15 March 2020
Accepted: 20 June 2020
Published: 19 November 2020
Authors
Harm Derksen
Department of Mathematics
University of Michigan
Ann Arbor, MI
United States
Visu Makam
School of Mathematics
Institute for Advanced Study
Princeton, NJ
United States