50.3 Decomposition

Decomposition( A, B, depth )
Decomposition( A, B, "nonnegative" )

For a m times n matrix A of cyclotomics that has rank m leq n, and a list B of cyclotomic vectors, each of dimension n, Decomposition tries to find integral solutions x of the linear equation systems x * A = B[i] by computing the p--adic series of hypothetical solutions.

Decomposition( A, B, depth ), where depth is a nonnegative integer, computes for every vector B[i] the initial part sum_{k=0}^{<depth>} x_k p^k (all x_k integer vectors with entries bounded by pmfrac{p-1}{2}). The prime p is 83 first; if the reduction of A modulo p is singular, the next prime is chosen automatically.

A list X is returned. If the computed initial part really is a solution of x * A = B[i], we have X[i] = x, otherwise X[i] = false.

Decomposition( A, B, "nonnegative" ) assumes that the solutions have only nonnegative entries, and that the first column of A consists of positive integers. In this case the necessary number depth of iterations is computed; the i-th entry of the returned list is false if there exists no nonnegative integral solution of the system x * A = B[i], and it is the solution otherwise.

If A is singular, an error is signalled.

    gap> a5:= CharTable( "A5" );; a5m3:= CharTable( "A5mod3" );;
    gap> a5m3.irreducibles;
    [ [ 1, 1, 1, 1 ], [ 3, -1, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ],
      [ 3, -1, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 4, 0, -1, -1 ] ]
    gap> reg:= CharTableRegular( a5, 3 );;
    gap> chars:= Restricted( a5, reg, a5.irreducibles );
    [ [ 1, 1, 1, 1 ], [ 3, -1, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ],
      [ 3, -1, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 4, 0, -1, -1 ],
      [ 5, 1, 0, 0 ] ]
    gap> Decomposition( a5m3.irreducibles, chars, "nonnegative" );
    [ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ],
      [ 1, 0, 0, 1 ] ]
    gap> last * a5m3.irreducibles = chars;
    true

Subroutines of Decomposition.

Previous Up Top Next
Index