For computing the decomposition of a vector of integers into the rows of a matrix of integers, with integral coefficients, one can use p-adic approximations, as follows.
Let A be a square integral matrix, and p an odd prime. The reduction of A modulo p is [`(A)], its entries are chosen in the interval [-[(p-1)/2], [(p-1)/2]]. If [`(A)] is regular over the field with p elements, we can form A¢ = [`(A)]-1. Now we consider the integral linear equation system x A = b, i.e., we look for an integral solution x. Define b0 = b, and then iteratively compute
|
|
There are two useful generalizations of this idea. First, A need not be square; it is only necessary that there is a square regular matrix formed by a subset of columns of A. Second, A does not need to be integral; the entries may be cyclotomic integers as well, in this case one can replace each column of A by the columns formed by the coefficients w.r.t. an integral basis (which are integers). Note that this preprocessing must be performed compatibly for A and b.
GAP provides the following functions for this purpose (see also InverseMatMod).
Decomposition( A, B, depth ) F
Decomposition( A, B, "nonnegative" ) F
For a m ×n matrix A of cyclotomics that has rank m £ n,
and a list B of cyclotomic vectors, each of length n,
Decomposition tries to find integral solutions 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 each vector B[i] the initial part
åk = 0depth xk pk,
with all xk vectors of integers with entries bounded by
±[(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 for x * A = B[i] is a solution,
we have X[i] = x, otherwise X[i] = fail.
Decomposition( A, B, "nonnegative" ) assumes that the solutions
have only nonnegative entries,
and that the first column of A consists of positive integers.
This is satisfied, e.g., for the decomposition of ordinary characters
into Brauer characters.
In this case the necessary number depth of iterations can be computed;
the i-th entry of the returned list is fail if there exists no
nonnegative integral solution of the system x * A = B[i], and it
is the solution otherwise.
Note that the result is a list of fail if A has not full rank,
even if there might be a unique integral solution for some equation
system.
LinearIndependentColumns( mat ) F
Called with a matrix mat, LinearIndependentColumns returns a maximal
list of column positions such that the restriction of mat to these
columns has the same rank as mat.
PadicCoefficients( A, Amodpinv, b, prime, depth ) F
Let A be an integral matrix,
prime a prime integer,
Amodpinv an inverse of A modulo prime,
b an integral vector,
and depth a nonnegative integer.
PadicCoefficients returns the list [ x0, x1, ¼, xl, bl+1 ]
describing the prime-adic approximation of b (see above),
where l = depth
or l is minimal with the property that bl+1 = 0.
IntegralizedMat( A ) F
IntegralizedMat( A, inforec ) F
IntegralizedMat returns for a matrix A of cyclotomics
a record intmat with components mat and inforec.
Each family of algebraic conjugate columns of A is encoded in a set of
columns of the rational matrix intmat.mat by replacing cyclotomics
in A by their coefficients w.r.t. an integral basis.
intmat.inforec is a record containing the information how to encode
the columns.
If the only argument is A, the value of 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 compatibly
with A.
DecompositionInt( A, B, depth ) F
DecompositionInt does the same as Decomposition
(see Decomposition),
except that A and B must be integral matrices, and depth must be
a nonnegative integer.
[Top] [Previous] [Up] [Next] [Index]
GAP 4 manual