A semi echelonised basis is a record with the following components: vectors is a list of vectors of equal length, optionally (and optimally) they can be wrapped to a matrix. pivots is a list of integers. The number i in position j indicates that the jth vector in vectors has a one in column number i and all vectors with a number bigger than i in vectors have a zero in column number i.
Note that for technical reasons another component helper is bound containing a cvec of length 1 over the same field.
Note further that the output of the GAP library operation SemiEchelonMat (Reference: SemiEchelonMat) is not compatible to this setup, because it contains a component heads that contains at position i, if nonzero, the number of the row for that the pivot element is in column i.
‣ EmptySemiEchelonBasis( v ) | ( method ) |
Returns: a new mutable empty semi echelonised basis
The argument v must be a sample vector or matrix. If it is a matrix, then one of its rows is taken as sample vector.
‣ Vectors( b ) | ( operation ) |
Returns: a matrix
The argument b must be a semi echelonised basis. This operation returns a (mutable) matrix whose rows are the basis vectors.
‣ Length( b ) | ( operation ) |
Returns: an integer
The argument b must be a semi echelonised basis. This operation returns the number of vectors in the basis.
‣ CleanRow( b, v, extend, dec ) | ( method ) |
Returns: true or false
This is the basic operation for cleaning with a semi echelonised basis b. The vector v is cleaned with the vectors in the semi echelonised basis. The function returns true if v lies in the span of b and false otherwise.
The boolean value extend indicates, whether the basis should be extended in the latter case by the newly cleaned vector.
The argument dec is either fail in which case it is not used or a vector over the same field as v that is at least as long as the number n of vectors in b (plus one if extend is true). In this case, the first n components of dec are changed such that ∑_{i=1}^n dec_i b_i. If extend is true and v is not contained in the span of the vectors in b and dec is a vector, then the first n+1 components of dec are changed such that v = ∑_{i=1}^n+1 dec_i b_i.
‣ SemiEchelonBasisMutable( b ) | ( method ) |
Returns: a semi echelonised basis
Turns the output b of SemiEchelonMat (Reference: SemiEchelonMat) into a valid semi echelonised basis in the sense of the cvec package. This means that the component pivots is calculated from the component heads. Use this function only if absolutely necessary. Instead, directly invoke SemiEchelonBasisMutable on the original matrix.
‣ SemiEchelonBasisMutable( m ) | ( method ) |
Returns: a semi echelonised basis
The argument m must be a cmat. This method calculates a semi echelonised basis for the row space of m.
There are a number of similar operations the names of which are derived from SemiEchelonBasisMutable by appending single letters: The letters P
, T
and X
are modifiers and there are operations for most of the 8 combinations of those letters being present or not respectively. Always give the present letters in alphabetical order.
The X
indicates, that the input matrix may be destroyed, that is, the rows of m will be changed and the very same objects be used in the semi echelonised result basis.
The T
indicates, that the transformation is calculated, that is, the resulting record r will have a component coeffs, such that r.coeffs * m is equal to r.vectors component of the semi echelonised result. Further, with given letter T
there will be a component relations which is a basis for the (left) nullspace of m.
The P
indicates, that a component r.p is calculated such that r.p * r.vectors is the original matrix m.
Currently the variants with P
and T
both present are not implement because they will probably not be very useful.
‣ SemiEchelonBasisMutableX( m ) | ( method ) |
Returns: a semi echelonised basis
Same as SemiEchelonBasisMutable (6.1-6) but destructive in m.
‣ SemiEchelonBasisMutableT( m ) | ( method ) |
Returns: a semi echelonised basis
Same as SemiEchelonBasisMutable (6.1-6) but in addition stores the transformation, see SemiEchelonBasisMutable (6.1-6).
‣ SemiEchelonBasisMutableTX( m ) | ( method ) |
Returns: a semi echelonised basis
Same as SemiEchelonBasisMutableT (6.1-8) but destructive in m.
‣ SemiEchelonBasisMutableP( m ) | ( method ) |
Returns: a semi echelonised basis
Same as SemiEchelonBasisMutable (6.1-6) but in addition stores the inverse transformation, see SemiEchelonBasisMutable (6.1-6).
‣ SemiEchelonBasisMutablePX( m ) | ( method ) |
Returns: a semi echelonised basis
Same as SemiEchelonBasisMutableP (6.1-10) but destructive in m.
‣ MutableNullspaceMat( m ) | ( method ) |
Returns: a cmat
Returns a cmat the rows of which are a basis of the (left) nullspace of the cmat m. Internally, SemiEchelonBasisMutableT (6.1-8) is used and the component relations of the result is returned. The result is mutable, which is the reason for the introduction of a new operation besides NullspaceMat (Reference: NullspaceMat).
‣ MutableNullspaceMatX( m ) | ( method ) |
Returns: a cmat
Same as MutableNullspaceMat (6.1-12) but destructive in m.
‣ NullspaceMat( m ) | ( method ) |
Returns: an immutable cmat
Behaves exactly as expected. m must be a cmat.
‣ NullspaceMatDestructive( m ) | ( method ) |
Returns: an immutable cmat
Behaves exactly as expected. m must be a cmat.
‣ CharacteristicPolynomialOfMatrix( m ) | ( method ) |
‣ CharacteristicPolynomialOfMatrix( m, indetnr ) | ( method ) |
Returns: a record
Calculates the characteristic polynomial of the cmat m over its base field. Because during the calculations the polynomial automatically comes as a product of some not necessarily irreducible factors, the result is returned in a record with two components. The poly component contains the full characteristic polynomial. The factors component contains a list of not necessarily irreducibly factors the product of which is the characteristic polynomial. If an indeterminate number is given as second argument, the polynomials are written in that indeterminate, otherwise in the first indeterminate over the base field.
‣ FactorsOfCharacteristicPolynomial( m ) | ( method ) |
‣ FactorsOfCharacteristicPolynomial( m, indetnr ) | ( method ) |
Returns: a list
Calculates the characteristic polynomial of the cmat m over its base field. The result is a list of irreducible factors of the characteristic polynomial of m, the product of which is the characteristic polynomial. Because during the calculations the polynomial automatically comes as a product of some not necessarily irreducible factors, this is more efficient than just calculating the characteristic polynomial and then factoring it. If an indeterminate number is given as second argument, the polynomials are written in that indeterminate, otherwise in the first indeterminate over the base field.
‣ MinimalPolynomialOfMatrix( m ) | ( method ) |
‣ MinimalPolynomialOfMatrix( m, indetnr ) | ( method ) |
Returns: a polynomial over the base field of m
Calculates the minimal polynomial of the cmat m over its base field. The polynomial is returned. If an indeterminate number is given as second argument, the polynomials are written in that indeterminate, otherwise in the first indeterminate over the base field.
‣ CharAndMinimalPolynomialOfMatrix( m ) | ( method ) |
‣ CharAndMinimalPolynomialOfMatrix( m, indetnr ) | ( method ) |
Returns: a record
Calculates the characteristic and minimal polynomial of the cmat m over its base field. Because during the calculation of the minimal polynomial the characteristic polynomial is calculated anyway, the result is returned in a record with five components: The charpoly component contains the full characteristic polynomial. The irreds component contains the set of irreducible factors of the characteristic polynomial as a list. The mult component contains a corresponding list of multiplicities, that is in position i is the multiplicity of the irreducible factor number i in the characteristic polynomial. The component minpoly contains the minimal polynomial and the component multmin the corresponding multiplicities of the irreducible factors of the characteristic polynomial in the minimal polynomial. If an indeterminate number is given as second argument, the polynomials are written in that indeterminate, otherwise in the first indeterminate over the base field.
‣ MinimalPolynomialOfMatrixMC( m, prob[, indetnr] ) | ( operation ) |
Returns: a record
This method calculates the characteristic and minimal polynomials of the row list matrix m over its base domain. It uses the Monte Carlo algorithm by Neunhoeffer and Praeger. The second argument prob is an upper bound for the error probability, it can be 0 in which case a deterministic verification is done. The optional argument indetnr is the number of the indeterminate over the base domain to be used to express polynomials.
The result is a record with the following components bound: The component charpoly is the characteristic polynomial which is guaranteed to be correct. The component minpoly is always a divisor of the minimal polynomial and usually is equal to it. See below for details. The component irreds is a sorted list of the irreducible factors of the characteristic polynomial. The component mult is a corresponding list of the same length containing the multiplicities of these irreducible factors in the characteristic polynomial. The component minmult is a corresponding list of the same length containing the multiplicities of these irreducible factors in the polynomial given in minpoly. The component proof is set to true if the result is proved to be correct, which can happen even if prob was non-zero (for example in the case of a cyclic matrix). The component iscyclic is set to true if and only if the minimal polynomial is equal to the characteristic polynomial. The component prob is set to the probability given in prob, if that was zero then it is set to 1/10000 but proof will be true. The components A, B and S describe a base change for m to a sparse form which is obtained as a byproduct. S is a semi echelonised basis which was obtained by a spin-up computation with m and if Y is the sparse basis then Y = A ⋅ S and B=A^-1.
The given result for the minimal polynomial could be a proper divisor of the real minimal polynomial if prob was non-zero, however, the probability for this outcome is guaranteed to be less than or equal to prob. Note that it is always guaranteed that all irreducible factors of the minimal polynomial are actually present, it can only happen that the multiplicities are too small.
generated by GAPDoc2HTML