  Many algorithms use data structures that maintain properties of matrices
undergoing some changes. The applications are wide-ranging and include for
example matchings, shortest paths, linear programming, semi-definite
programming, convex hull and volume computation. Given the wide range of
applications, the exact property these data structures must maintain varies
from one application to another, forcing algorithm designers to invent them
from scratch or modify existing ones. Thus it is not surprising that these data
structures and their proofs are usually tailor-made for their specific
application and that maintaining more complicated properties results in more
complicated proofs.
  In this paper we present a unifying framework that captures a wide range of
these data structures. The simplicity of this framework allows us to give short
proofs for many existing data structures regardless of how complicated the to
be maintained property is. We also show how the framework can be used to speed
up existing iterative algorithms, such as the simplex algorithm.
  More formally, consider any rational function $f(A_1,...,A_d)$ with input
matrices $A_1,...,A_d$. We show that the task of maintaining $f(A_1,...,A_d)$
under updates to $A_1,...,A_d$ can be reduced to the much simpler problem of
maintaining some matrix inverse $M^{-1}$ under updates to $M$. The latter is a
well studied problem called dynamic matrix inverse. By applying our reduction
and using known algorithms for dynamic matrix inverse we can obtain fast data
structures and iterative algorithms for much more general problems.
