Deterministic Truncation of Linear Matroids

Let M=(E,cal I) be a matroid. A em k-truncation of M is a matroid M'=(E,cal I') such that for any Asubseteq E, A∈ cal I' if and only if |A|≤ k and A∈ cal I. Given a linear representation of M we consider the problem of finding a linear representation of the k-truncation of this matroid. This problem can be abstracted out to the following problem on matrices. Let M be a n× m matrix over a field mathbbF. A em rank k-truncation of the matrix M is a k× m matrix Mk (over mathbbF or a related field) such that for every subset Isubseteq 1,ldots,m of size at most k, the set of columns corresponding to I in M has rank |I| if and only of the corresponding set of columns in Mk has rank |I|. Finding rank k-truncation of matrices is a common way to obtain a linear representation of k-truncation of linear matroids, which has many algorithmic applications. A common way to compute a rank k-truncation of a n × m matrix is to multiply the matrix with a random k× n matrix (with the entries from a field of an appropriate size), yielding a simple randomized algorithm. So a natural question is whether it possible to obtain a rank k-truncations of a matrix, em deterministically. In this paper we settle this question for matrices over any finite field or the field of rationals (mathbb Q). We show that given a matrix M over a field mathbbF we can compute a k-truncation Mk over the ring mathbbF[X] in deterministic polynomial time.