An Algorithm for Determining the Largest Maximally Independent Set of Vectors from an R-Dimensional Vector Space over a Galois Field of n Elements

摘要

The report expands upon a paper (1) presented by Robert Silverman and Carl Maneri in the Journal of Algebra, November 1966. Two problems will be considered: a vector space packing problem, and its combinatorial generalization as a partitioning problem. The vector space packing is equivalent to finding the largest number of vectors of an r-dimensional vector space such that any r of them form a basis for the space. Other interesting equivalent formulation of these problems will be described in Section 1.2. The above paper (1) presented complete results for the first problem for Galois fields of up to eight elements. This report will give complete results for the first problem for Galois fields of up to eleven elements and partial results for fields up to thirteen elements. The major contribution of this report, however, is not the results; it is the systematic method used in obtaining these results, that is, an algorithm. Although the results for larger fields were not obtained because of the excessive computer time needed to determine them, the algorithm presented here is not limited by computer constraints, and, therefore, as faster computers are built, this algorithm will be able to generate results for larger and larger fields. (Author)