Murray R. Bremner
Department of Mathematics and Statistics
University of Saskatchewan
Saskatoon, Canada
An evolutionary algorithm for finding an optimal basis of a subspace
Abstract: We present an evolutionary algorithm for finding an optimal basis of the nullspace of a matrix over the rational numbers. This algorithm employs a novel variation operator in which an existing (old) basis is combined with one or more randomly generated (new) bases and then filtered by a greedy algorithm to select a better candidate basis. We study the effectiveness of this algorithm on random matrices of sizes 5 by 10 and 10 by 20; for the first matrix we compare the algorithm to an exhaustive search. We present a third example which applies this algorithm to the simplification of known 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.