Deterministic Truncation of Linear Matroids

摘要

Let M = (E, I) be a matroid of raiik a. A k-truncation of M is a matroid M' = (E, I') such that for ally A subset of E, A is an element of is an element of I' if and only if vertical bar A vertical bar = k and A is an element of I. Given a linear representation, A, of M, we consider the problem of finding a linear representation, A(k), of the k-truncation of M. A common way to compute Ak is to multiply the matrix A with a random k x n matrix, yielding a simple randomized algorithm. Thus, a natural question is whether we can compute A(k) deterministically. In this article, we settle this question for matrices over any field in which the field operations can be done efficiently. This includes any finite field and the field of rational numbers (Q).