# 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.