On sets of vectors of a finite vector space in which every subset of basis size is a basis

  • Simeon Ball

    Universitat Politécnica de Catalunya, Barcelona, Spain

Abstract

It is shown that the maximum size of a set S{ S} of vectors of a kk-dimensional vector space over Fq{\mathbb F}_q, with the property that every subset of size kk is a basis, is at most q+1q+1, if kpk \leq p, and at most q+kpq+k-p, if qkp+14q \geq k \geq p+1 \geq 4, where q=phq=p^h and pp is prime. Moreover, for kpk\leq p, the sets SS of maximum size are classified, generalising Beniamino Segre's “arc is a conic'' theorem.

These results have various implications. One such implication is that a k×(p+2)k\times (p+2) matrix, with kpk \leq p and entries from Fp{\mathbb F}_p, has kk columns which are linearly dependent. Another is that the uniform matroid of rank rr that has a base set of size nr+2n \geq r+2 is representable over Fp{\mathbb F}_p if and only if np+1n \leq p+1. It also implies that the main conjecture for maximum distance separable codes is true for prime fields; that there are no maximum distance separable linear codes over Fp{\mathbb F}_p, of dimension at most pp, longer than the longest Reed-Solomon codes. The classification implies that the longest maximum distance separable linear codes, whose dimension is bounded above by the characteristic of the field, are Reed–Solomon codes.

Cite this article

Simeon Ball, On sets of vectors of a finite vector space in which every subset of basis size is a basis. J. Eur. Math. Soc. 14 (2012), no. 3, pp. 733–748

DOI 10.4171/JEMS/316