An evolutionary algorithm for finding an optimal basis of a subspace
This paper presents an evolutionary algorithm for finding a basis of
the nullspace of a matrix over the rational numbers which is optimal
in the sense that the basis vectors have integral components with no
common factors and the absolute values of the components are as
small as possible. The algorithm employs a novel variation operator
in which an existing basis is combined with one or more randomly
generated bases and then filtered by a greedy algorithm to produce a
better candidate basis. The paper studies the effectiveness of this
algorithm on three examples: (1) a random matrix of size 5 by 10:
for this matrix the algorithm is compared with an exhaustive search;
(2) a random matrix of size 10 by 20: for this matrix the algorithm
is tested with population sizes from 1 to 10; (3) a matrix of size
120 by 90 arising from a computational study of polynomial
identities for nonassociative algebras. The better bases located
with the algorithm presented here permit the automatic discovery of
new algebraic identities with simple statements. This simplification
is critical to permitting researchers in abstract algebra to access
the intuition embedded in automatically discovered identities.
M. R. Bremner < bremner@math.usask.ca >