## `linalg::charpoly` -- characteristic polynomial of a matrix

#### Introduction

`linalg::charpoly``(A, x)` computes the characteristic polynomial of the matrix A. The characteristic polynomial of a n x n matrix is defined by pA(x):=det(x*I-A), where I denotes the n x n identity matrix.

#### Call(s)

`linalg::charpoly(A, x)`

#### Parameters

`A` | - | a square matrix of a domain of category `Cat::Matrix`
`x` | - | an indeterminate

#### Returns

a polynomial of the domain `Dom::DistributedPolynomial``([x],R)`, where `R` is the component ring of `A`.

#### Related Functions

`linalg::charmat`, `linalg::det`, `linalg::hessenberg`, `linalg::minpoly`

#### Details

- The component ring of `A` must be a commutative ring, i.e., a domain of category `Cat::CommutativeRing`.

#### Example 1

We define a matrix over the rational numbers:

    >> A := Dom::Matrix(Dom::Rational)([[1, 2], [3, 4]])

                                    +-      -+
                                    |  1, 2  |
                                    |        |
                                    |  3, 4  |
                                    +-      -+

Then the characteristic polynomial pA(x) is given by:

    >> linalg::charpoly(A, x)

                                    2
                                   x  - 5 x - 2

It is of the domain type:

    >> domtype(%)

             Dom::DistributedPolynomial([x], Dom::Rational, LexOrder)

#### Example 2

We define a matrix over Z7:

    >> B := Dom::Matrix(Dom::IntegerMod(7))([[1, 2], [3, 0]])

                              +-                  -+
                              |  1 mod 7, 2 mod 7  |
                              |                    |
                              |  3 mod 7, 0 mod 7  |
                              +-                  -+

The characteristic polynomial pB(x) of `B` is given by:

    >> p := linalg::charpoly(B, x)

                                 2
                      (1 mod 7) x  + (6 mod 7) x + (1 mod 7)

We compute the zeros of pB(x), i.e., the eigenvalues of the matrix `B`:

    >> solve(p)

                              x in {3 mod 7, 5 mod 7}

#### Background

- `linalg::charpoly` implements Hessenberg's algorithm to compute the characteristic polynomial of a square matrix A. See: Henri Cohen: A Course in Computational Algebraic Number Theory, GTM 138, Springer Verlag.

  This algorithm works for any field and requires only O(n^3) field operations, in contrast to O(n^4) when computing the determinant of the characteristic matrix of A.

  Since the size of the components of A in intermediate computations of Hessenberg's algorithm can swell extremely, it is only applied for matrices over `Dom::Float` and `Dom::IntegerMod`.

  For any other component ring, the characteristic polynomial is computed using the Berkowitz algorithm. Reference: A. Jounaidi: The Berkowitz Algorithm, Maple and Computing the Characteristic Polynomial in an Arbitrary Commutative Ring. Equipe de Mathèmatiques de Besancon, Universitè de Franche - Comtè, 25030 Besancon Cedex, May 1996.

#### Changes

- used to be called `linalg::charPolynomial`

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000