zcp man page
zcp — characteristic and minimal polynomial of a matrix
Synopsis
zcp [Options] <File>
Description
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.
Options
- -Q
Quiet, no messages.
- -V
Verbose, more messages.
- -T <MaxTime>
Set CPU time limit
- -G
Produce output in GAP format.
- -m
Calculate the minimal polynomial.
- -f
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
- File
A square matrix.