Square-free decomposition in finite characteristic
Authors: Fortuna Elisabetta , Gianni Patrizia 
Published: January 2007

In ([GT]) has been addressed the problem of the computation of
the square-free decomposition for univariate polynomials with
coefficients in arbitrary fields. The complete square-free
decomposition can be computed over arbitrary fields of finite
characteristic solely assuming that the field satisfies the
Condition P
of Seidenberg ([Se]), which has been proven
equivalent to the ability computing such decompositions (see also
[MRR]). If we assume that the field is only an effective field
(i.e. of a field
K
where there are constructive procedures
for performing rational operations in
K
and for deciding
whether or not two elements in
K
are equal), it is possible
to obtain a weaker decomposition into powers of relatively prime
factors, not necessarily square-free, but such that within each
factor the roots have constant multiplicity. Although this is a
partial decomposition, much useful information can be gathered from
this result. As an application we present an algorithm to compute
the Jordan form of a matrix over an arbitrary effective field. In
particular we show how to handle problems of inseparability while
splitting invariant factors and constructing symbolic Jordan
form.

The computation of normal forms of a matrix, in particular of
the Jordan form, is a very important task and has many useful
applications, so it has been widely studied for many years and many
efficient algorithms, sequential and parallel ([O], [L], [Gi1],
[Gi2], [Ol], [KKS], [RV]), are already available for its
computation. There are already algorithms which compute the Jordan
form of a matrix over general fields ([GD], [RV]), but they are
based on dynamic evaluation ([D5]) and we want to avoid the use of
such a scheme, that requires a special computational environment.
Storjohann ([St]) has given a new algorithm for computing the
rational canonical form which has a deterministic complexity of
O
(
n
3
) but he does not compute the
transition matrix with the same complexity. Steel's ([S]) algorithm
for computing generalized Jordan form has a complexity
O
(
n
4
) but requires factoring polynomials
into irreducibles. Kaltofen et. al. ([KKS]) give fast parallel
algorithms for canonical forms and make the observation that one
could compute a symbolic Jordan form from a rational canonical form
by splitting the invariant factors using gcd's and square-free
decompositions. They require the computation of complete
square-free decompositions and thus also require that
K
be a
perfect field with the ability to compute

p
th

roots. They also don't compute the transition matrix. Ozello ([O])
presents an algorithm for computing the rational canonical form
which is deterministic with complexity
O
(
n
4
), and leaves the question of faster
probabilitic approaches for future work. Giesbrecht ([Gi2]) gives a
probabilistic algorithm whose complexity is essentially the same as
matrix multiplication but requires choosing
n
"good" random
vectors simultaneously thus giving only a probability of 1/4 of
making a successful choice.

Our aim is to obtain a general sequential algorithm, of a
complexity comparable with most of the existing algorithms, that
works in the widest possible setting, without requiring particular
computing resources and hence of easy and straightforward
implementation. Because of our hypothesis, in general, our
algorithm will produce a
symbolic Jordan form
([K], [RV]),
but the main difference with the other available algorithms based
on dynamic evaluation is that our algorithm is a rational
algorithm, since all the computations take place in the given
field, except for the output and eventually the computation of the
inverse of the transition matrix. To obtain all the information on
the symbolic roots of the characteristic polynomial (multiplicities
and recognition) we, at first, transform the given matrix
A
into a
pseudo-rational
form, i.e. a block diagonal matrix,
similar to
A,
with companion matrices on the diagonal
without requiring any kind of divisibility of the associated
polynomials. Then we refine the factorization of the characteristic
polynomial, given by the polynomials whose companion matrices are
on the diagonal of the pseudo-rational form, using partial
square-free decomposition and gcd computations, so that we can
identify the same roots in different blocks and also we reduce, as
much as possible without factorization, the degree of the defining
polynomials for the eigenvalues.

The pseudo-rational form is computed with a probabilistic
algorithm of complexity
O
(
n
3
) such that
each independent random choice is verifiable with probability
better than 1 - 1/
n
of success. We derive this probabilistic
algorithm from one for the computation of the rational form, which
has a complexity of
O
(
n
4
), and is obtained
via a straightforward analysis of the properties of the minimal
polynomial that leads to a natural way to construct invariant
subspaces.