Members’ Seminar

The main object of study of this talk are matrices whose entries are linear forms in a set of formal variables (over some field). The main problem is determining if a given such matrix is invertible or singular (over the appropriate field of rational functions). As it happens, this problem has a dual life; when the underlying variables commute, and when they do not. Most of the talk will be devoted to explaining (some of) the many origins, motivations and interrelations of these two problems, in computational complexity, non-commutative algebra, (commutative) invariant theory, quantum information theory, optimization and more. I will describe the state-of-art on the complexity of these problems. For the non-commutative version, where even decidability took decades to establish, we have recently found (with Garg, Gurvits and Olivera) a deterministic polynomial time algorithm (over the rationals). Strangely perhaps, for the commutative version, where decidability is nearly trivial, the best known deterministic algorithm requires exponential time. A probabilistic polynomial time algorithm is known, and making it deterministic is major open problem. I will elaborate on all these developments in the CSDM seminars on Tue Feb 9 and Feb 16.