  This paper describes an algorithm which computes the characteristic
polynomial of a matrix over a field within the same asymptotic complexity, up
to constant factors, as the multiplication of two square matrices. Previously,
this was only achieved by resorting to genericity assumptions or randomization
techniques, while the best known complexity bound with a general deterministic
algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic
factors. Our algorithm computes more generally the determinant of a univariate
polynomial matrix in reduced form, and relies on new subroutines for
transforming shifted reduced matrices into shifted weak Popov matrices, and
shifted weak Popov matrices into shifted Popov matrices.
