Dear GAP Forum,
Benjamin Sambale had reported a bug in the GAP function
'OrthogonalEmbeddings'.
Indeed, the GAP implementation that is available for about 20 years
is not correct, some solutions may be missing from the result.
A corrected version of the function can be found at
http://www.math.rwth-aachen.de/~Thomas.Breuer/gapfix/fix_orthemb_4_7_5
The fix may become available in one of the next GAP releases.
Benjamin had also mentioned a problem with the documentation of the
function; this will then be fixed as well.
All the best,
Thomas
P.S.:
Wrong results occur in the following situation:
- Setup:
Suppose that the matrix $A$ is given as the argument of the function,
that is, we are interested in all integral matrices $X$ such that
$X X^{tr} = A$ holds.
Further suppose that there are $m$ vectors (up to sign) that can occur
as the columns of the solution matrices $X$.
Each solution is described by the vector (called $\iota$ in the
underlying paper) of multiplicities of these $m$ vectors.
- Technical description:
The algorithm enumerates the relevant coefficient vectors in reverse
lexicographical order, and the bug in the program has the effect that
the following illegal shortcut happens.
Whenever the $(m-1)$-th coefficient shall be decreased by $1$ during
the enumeration, it is erroneously set to zero,
and also the $(m-2)$-th coefficient gets decreased by $1$.
Thus all those solutions with given coefficients of the first $m-2$
vectors are skipped for which the $(m-1)$-th vector does not occur
with the maximal possible multiplicity.
- Conceptual description:
The error strikes whenever solutions exist that differ only w. r. t.
the multiplicities of the last two vectors,
in other words, if a solution is not determined already by the
multiplicities of the first $m-2$ vectors.
In this situation, all those solutions are missing for which the
$(m-1)$-th coefficient is smaller than the maximal value.
Additionally, if a solution is determined by the multiplicities of
the first $m-2$ vectors then it is missing if the coefficient of the
$(m-1)$-th vector is smaller than the maximal possible value for it,
as is computed by the algorithm in this situation.
- Examples:
1. In Benjamin's example, we have $A = [ [ 4 ] ]$,
$m = 2$, and the possible vectors are $x_1 = [ 2 ]$ and $x_2 = [ 1 ]$.
The current function finds the solution with the coefficient
vector $[ 1, 0 ]$ but not the one with the vector $[ 0, 4 ]$.
2. In the case $A = [ [ 1, 0 ], [ 0, 4 ] ]$,
we have $m = 3$ and $x_1 = [ 1, 0 ]$, $x_2 = [ 0, 2 ]$,
$x_3 = [ 0, 1 ]$.
The coefficient vector $[ 1, 1, 0 ]$ is found but the vector
$[ 1, 0, 4 ]$ is not.
3. In the case $A = [ [ 4, 0 ], [ 0, 1 ] ]$,
we have $m = 3$ and $x_1 = [ 2, 0 ]$, $x_2 = [ 0, 1 ]$,
$x_3 = [ 1, 0 ]$.
In this case, the two solutions $[ 1, 1, 0 ]$ and $[ 0, 1, 4 ]$
are found.
On Fri, Sep 05, 2014 at 07:37:15AM +0200, Benjamin Sambale wrote:
> Dear GAP people,
>
> according to the manual, the command OrthogonalEmbeddings does the
> following: Given an integral symmetric matrix M, compute all integral
> matrices X such that X^tr X = M where X^tr denotes the transpose of X.
> The solution matrices X are given up to permutations and signs of their
> rows.
>
> If I do (with GAP 4.7.5) OrthogonalEmbeddings([[4]]), I only get one
> solution, namely X = [[2]]. However, there is another solution X =
> [[1],[1],[1],[1]] which is somehow missing! What is wrong here?
> Apparently, the implementation is quite old and based on a paper by
> Plesken from 1995.
>
> There is also an inaccuracy in the manual: It says: "the list L = [ x_1,
> x_2, ..., x_n ] of vectors that may be rows of a solution; these are
> exactly those vectors that fulfill the condition x_i ⋅ gram^{-1} ⋅
> x_i^tr ≤ 1 (see ShortestVectors (25.6-2)), and we have gram = ∑_{i =
> 1}^n x_i^tr ⋅ x_i".
>
> The last equation is usually not true. The equation only holds for the
> set of vectors of a solution. Moreover, one should mention that the list
> of vectors is only up to signs.
>
> Thanks and best wishes,
> Benjamin
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
