Improved Algorithms for Dynamic Matrix Inverse

The dynamic matrix inverse problem is to maintain the inverse of a matrix undergoing element and column updates. It is the main subroutine behind the best algorithms for many dynamic problems, such as maintaining the largest eigenvalue, rank and determinant of a matrix and maintaining reachability, distances, maximum matching size, and k-paths/cycles in a graph. Prior best bounds for most of these problems date back to more than a decade ago [Sankowski FOCS’04, COCOON’05, SODA’07; Kavitha FSTTCS’08; Mucha and Sankowski Algorithmica’10; Bosek et al. FOCS’14].