Abstract

We give a deterministic polynomial-time algorithm for the following problem: given a tuple of square matrices A_1, ?, A_m, decide whether there exist invertible matrices B and C, such that every BA_iC is (skew-)symmetric. This can be cast as an instance of symbolic determinant identity testing, so our algorithm derandomizes this problem when the underlying field is large enough. The algorithm is inspired by those for the module isomorphism testing problem (Brooksbank-Luks, Ivanyos-Karpinski-Saxena), and the analysis relies crucially on the structure of *-algebras, namely algebras with an anti-automorphism of order at most 2. We also explain why this problem is interesting in light of the recent progress on the non-commutative rank problem. Based on joint work with Gábor Ivanyos, arXiv:1708.03495.

Video Recording