Minimal and Characteristic Polynomials and Eigenvalues

The functions in this section deal with minimal and characteristic polynomials and related operations and they match the functions defined for dense matrices; see Section Minimal and Characteristic Polynomials and Eigenvalues for more information on the functions and the possible parameters.

MinimalPolynomial(A: parameters) : MtrxSprs -> RngUPolElt

Given a square sparse matrix A over a ring R, return the minimal polynomial of A.

CharacteristicPolynomial(A: parameters) : MtrxSprs -> RngUPolElt

    Al: MonStg                          Default: "Modular"

    Proof: BoolElt                      Default: true

Given a square sparse matrix A over a ring R, return the characteristic polynomial of A.

MinimalAndCharacteristicPolynomials(A: parameters) : MtrxSprs -> RngUPolElt, RngUPolElt

MCPolynomials(A) : MtrxSprs -> RngUPolElt, RngUPolElt

Given a square sparse matrix A over a ring R, return the minimal and characteristic polynomials of A.

FactoredMinimalPolynomial(A: parameters) : MtrxSprs -> [ <RngUPolElt, RngIntElt>]

Given a square sparse matrix A over a ring R, return the factorization of the minimal polynomial of A.

FactoredCharacteristicPolynomial(A: parameters) : MtrxSprs -> [ <RngUPolElt, RngIntElt>]

Given a square sparse matrix A over a ring R, return the factorisation of the characteristic polynomial of A.

FactoredMinimalAndCharacteristicPolynomials(A: parameters) : MtrxSprs -> [<RngUPolElt, RngIntElt>], [<RngUPolElt, RngIntElt>]

FactoredMCPolynomials(A: parameters) : MtrxSprs -> [<RngUPolElt, RngIntElt>], [<RngUPolElt, RngIntElt>]

Given a square matrix sparse A over a ring R, return the factorizations of the minimal and characteristic polynomials of A, respectively.

Eigenvalues(A) : MtrxSprs -> { <FldElt, RngIntElt> }

Given a square matrix A over a ring R, return the eigenvalues of A as a set of pairs, each of which gives the value of a distinct eigenvalue and its multiplicity.

Eigenspace(A, e) : AlgMatElt, FldElt -> ModTup

Given a square matrix A over a ring R, and an element e of R, return the eigenspace of A corresponding to e.

Elementary Divisors (Smith Form)

ElementaryDivisors(A) : MtrxSprs -> [RngElt]

Given an m x n matrix A over the Euclidean ring or field R, return the elementary divisors of A. These are simply the non-zero diagonal entries of the Smith form of A, in order.

The divisors are returned as a sequence Q = [e₁, ..., e_d], e_i | e_{i + 1} (i=1, ..., d - 1) of d elements of R (which may include ones), where d is the rank of A. If R is a field, the result is always a sequence of r ones, where r is the rank of A.

A function for computing the Smith normal form is not supplied for sparse matrices since the form may be trivially derived from the elementary divisors, and the sequence Q containing the divisors is often more convenient (and takes less memory). As transformation matrices are dense in general, they are not supported for the sparse representation.

The algorithm first performs sparse elimination using Markowitz pivoting to obtain a smaller dense matrix ([DEJ84, Sec. 9.2]; this is similar to the techniques described in [HHR93]). Then it invokes the dense Smith normal form algorithm for normal (dense-representation) matrices (SmithForm).

Verbosity

SetVerbose("SparseMatrix", v) : MonStgElt, RngIntElt ->

(Procedure.) Set the verbose printing level for all sparse matrix algorithms to be v. Currently the legal values for v are true, false, 0, 1, 2, and 3 (false has the same effect as 0, and true has the same effect as 1).