Dynamic matrix rank (Q843102)

The authors consider the problem for maintaining information about the rank of a matrix under changes of the entries. For \(n \times n\) matrices, an upper bound of \(O(n^{1.575})\) arithmetic operations and a lower bound of \(O(n)\) arithmetic operations per element change are derived. It is shown that the upper bound is valid when changing up to \(O(n^{0.575})\) entries in a single column of the matrix. An algorithm is presented that maintains the rank using \(O(n^{2})\) arithmetic operations per rank one update. The upper bounds are valid for arbitrary fields, whereas the lower bound is valid for arbitrary closed fields. The upper bound for element updates uses a fast rectangular matrix multiplication, and the lower bound involves a further development of an earlier technique for proving lower bounds for dynamic computation of rational functions.