Let A be a square integral matrix, p an odd prime. The reduction of A modulo p is overline{A}, its entries are chosen in the interval [-frac{p-1}{2}, frac{p-1}{2}]. If overline{A} is regular over the field with p elements, we can form A^{prime} = overline{A}^{-1}. Now consider the integral linear equation system x A = b, i.e., we look for an integral solution x. Define b_0 = b, and then iteratively compute
[ x_i = (b_i A^prime) bmod p, b_i+1 = frac1p (b_i - x_i A) mboxrm for i = 0, 1, 2, ldots . ]
By induction, we get
[ p^i+1 b_i+1 + ( sum_j=0^i p^j x_j ) A = b . ]
If there is an integral solution x, it is unique, and there is an index l such that b_{l+1} is zero and x = sum_{j=0}^{l} p^j x_j.
There are two useful generalizations. First, A need not be square; it is only necessary that there is a square regular matrix formed by a subset of columns. Second, A does not need to be integral; the entries may be cyclotomic integers as well, in this case one has to replace each column of A by the columns formed by the coefficients (which are integers). Note that this preprocessing must be performed compatibly for A and b.
And these are the subroutines called by Decomposition:
LinearIndependentColumns( A )
returns for a matrix A a maximal list lic of positions such that the
rank of List( A, x - Sublist( x, lic ) ) is the same as the rank
of A.
InverseMatMod( A, p )
returns for a square integral matrix A and a prime p a matrix
A^{prime} with the property that A^{prime} A is congruent to the
identity matrix modulo p; if A is singular modulo p, false is
returned.
PadicCoefficients( A, Amodpinv, b, p, depth )
returns the list [ x_0, x_1, ldots, x_l, b_{l+1} ] where l = <depth> or l is minimal with the property that b_{l+1} = 0.
IntegralizedMat( A )
IntegralizedMat( A, inforec )
return for a matrix A of cyclotomics a record intmat with components
mat and inforec. Each family of galois conjugate columns of A is
encoded in a set of columns of the rational matrix intmat.mat by
replacing cyclotomics by their coefficients. intmat.inforec is a
record containing the information how to encode the columns.
If the only argument is A, the component inforec is computed that can
be entered as second argument inforec in a later call of
IntegralizedMat with a matrix B that shall be encoded compatible with
A.
DecompositionInt( A, B, depth )
does the same as Decomposition (see Decomposition), but only for
integral matrices A, B, and nonnegative integers depth.
GAP 3.4.4