  Algebraic techniques have had an important impact on graph algorithms so far.
Porting them, e.g., the matrix inverse, into the dynamic regime improved
best-known bounds for various dynamic graph problems. In this paper, we develop
new algorithms for another cornerstone algebraic primitive, the Frobenius
normal form (FNF). We apply our developments to dynamic and fault-tolerant
exact distance oracle problems on directed graphs.
  For generic matrices $A$ over a finite field accompanied by an FNF, we show
(1) an efficient data structure for querying submatrices of the first $k\geq 1$
powers of $A$, and (2) a near-optimal algorithm updating the FNF explicitly
under rank-1 updates.
  By representing an unweighted digraph using a generic matrix over a
sufficiently large field (obtained by random sampling) and leveraging the
developed FNF toolbox, we obtain: (a) a conditionally optimal distance
sensitivity oracle (DSO) in the case of single-edge or single-vertex failures,
providing a partial answer to the open question of Gu and Ren [ICALP'21], (b) a
multiple-failures DSO improving upon the state of the art (vd. Brand and
Saranurak [FOCS'19]) wrt. both preprocessing and query time, (c) improved
dynamic distance oracles in the case of single-edge updates, and (d) a dynamic
distance oracle supporting vertex updates, i.e., changing all edges incident to
a single vertex, in $\tilde{O}(n^2)$ worst-case time and distance queries in
$\tilde{O}(n)$ time.
