# 50.4 Subroutines of Decomposition

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
April 1997