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.

Info

2.4.24 MeatAxe User Commands