zcp man page

zcp — characteristic and minimal polynomial of a matrix


zcp [Options] <File>


This program reads in a square matrix and calculates its characteristic or minimal polynomial.  With no options, the characteristic polynomial is computed in a partially factored form (see below).  With -m the polynomial is split into irreducible factors. Without -G, the output is in text format. Each line contains one factor of the characteristic or minimal polynomial. The -G option may be used to generate output which is readable by the GAP computer program.  The output, then, is a sequence of sequences of finite field elements, representing the coefficients of the factors in ascending order.



Quiet, no messages.


Verbose, more messages.

-T <MaxTime>

Set CPU time limit


Produce output in GAP format.


Calculate the minimal polynomial.


Factor the polynomial.

Implementation Details

The characteristic polynomial of a matrix A is computed by constructing a sequence 0=U_0<U_1<...<U_n=V of A-invariant subspaces, where U_i/U_(i-1) is A-cyclic.  In the ith step, U_i is constructed by choosing a random vector uϵV\U_(i-1) and calculating u,uA,uA^2,... until some linear combination of these vectors falls into U_(i-1).  This yields a polynomial p_i(x) with up_i(A)ϵU_(i-1). p_i(x) is the characteristic polynomial of A on U_i/U_(i-1), and the full characteristic polynomial of A is the product of all p_i's.

The algorithm for the minimal polynomial uses the same technique of constructing a sequence (U_i) of invariant subspaces.  In the ith step, images uA,uA^2,... of a seed vector u are calculated, until a linear combination of these vectors vanishes (this is the main difference to the algorithm above). This yields a polynomial p_i(x) of minimal degree with up_i(A)=0, and the minimal polynomial of A is the least common multiple of the p_i's.

Input Files


A square matrix.


2.4.24 MeatAxe User Commands