> < ^ Date: Fri, 19 Mar 1993 12:45:34 +0100
> < ^ From: Thomas Breuer <Thomas.Breuer@Math.RWTH-Aachen.DE >
< ^ Subject: Re: Linear combinations in Gap

Dear Mrs. and Mr. Forum,
Lee Hawkins writes in his mail

I have a list of lists, each of which I wish to express as a Z-linear
combination of a set of given lists (each list involved consists of
integers). How can I do this in Gap 3.2 ?????

Let 'X' be an integral matrix with linearly independent rows, and 'b' an
integral vector of same dimension as the rows of 'X'. The GAP function
'Decomposition' computes the integral coefficient vector 'a' (if exists)
such that 'a * X = b'.

The method used is p-adic approximation, that is, a square submatrix of 'X'
of full rank is inverted modulo a suitable prime p, and the initial part
of the p-adic series of a solution 'a' is computed. If no solution is found
then 'false' is returned, what means that either no integral solution exists
or the maximal length of the computed initial part was chosen too small.
The details can be found in the GAP manual in section "Decomposition".

It should be noted that 'X' need not be integral, the algorithm also works
for matrices over the ring of cyclotomic integers.

Best wishes,
Thomas Breuer

> < [top]