We present the first fully dynamic algorithm for computing the
characteristic polynomial of a matrix. In the generic symmetric case our
algorithm supports rank-one updates in
![$O(n^2 \log n)$](Abs/img1.gif)
randomized time and
queries in constant time, whereas in the general case the algorithm works in
![$O(n^2 k \log n)$](Abs/img2.gif)
randomized time, where
![$k$](Abs/img3.gif)
is the number of invariant
factors of the matrix. The algorithm is based on the first dynamic algorithm
for computing normal forms of a matrix such as the Frobenius normal form or
the tridiagonal symmetric form. The algorithm can be extended to solve the
matrix eigenproblem with relative error
![$2^{-b}$](Abs/img4.gif)
in additional
![$O(n \log^2 n
\log b)$](Abs/img5.gif)
time. Furthermore, it can be used to dynamically maintain the
singular value decomposition (SVD) of a generic matrix. Together with the
algorithm the hardness of the problem is studied. For the symmetric case we
present an
![$\Omega(n^2)$](Abs/img6.gif)
lower bound for rank-one updates and an
![$\Omega(n)$](Abs/img7.gif)
lower bound for element updates.