Linear spaces of matrices, or matrix spaces, appear naturally in the study of polynomial identity testing and group isomorphism. In this talk, we examine connections between graphs and matrix spaces, the first of which goes back to the works of Tutte, Edmonds, and Lovász. These connections provide a useful viewpoint on some algebraic algorithms and complexity classes, such as algorithms for the non-commutative rank problem and the group isomorphism problem, and the Tensor-Isomorphism complexity class. Such connections also lead to new questions in algebraic complexity, such as testing whether a matrix space contains only nilpotent matrices.
This video was produced by the University of Warwick as part of the 7th Workshop on Algebraic Complexity Theory (WACT) 2023.
