Dynamic Matrix Rank

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Department of Computer Science
We consider maintaining information about the rank of a matrix under changes of the entries. For n×n matrices, we show an upper bound of O(n1.575) arithmetic operations and a lower bound of Ω(n) arithmetic operations per element change. The upper bound is valid when changing up to O(n0.575) entries in a single column of the matrix. We also give an algorithm that maintains the rank using O(n2) arithmetic operations per rank one update. These bounds appear to be the first nontrivial bounds for the problem. The upper bounds are valid for arbitrary fields, whereas the lower bound is valid for algebraically closed fields. The upper bound for element updates uses fast rectangular matrix multiplication, and the lower bound involves further development of an earlier technique for proving lower bounds for dynamic computation of rational functions.
Original languageEnglish
JournalTheoretical Computer Science
Volume410
Issue41
Pages (from-to)4085-4093
Number of pages9
ISSN0304-3975
DOIs
Publication statusPublished - 2009

    Research areas

  • Matrix rank, Dynamic algorithms, Lower bounds

See relations at Aarhus University Citationformats

ID: 17795143