Deterministic Truncation of Linear Matroids

Abstract

Let M=(E,I) be a matroid of rank n. A k-truncation of M is a matroid M′=(E,I′) such that for any A⊆ E, A∈ ∈I′ if and only if |A|≤ k and A∈ I. Given a linear representation, A, of M, we consider the problem of finding a linear representation, Ak, of the k-truncation of M. A common way to compute Ak is to multiply the matrix A with a random k× n matrix, yielding a simple randomized algorithm. Thus, a natural question is whether we can compute Akdeterministically. 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). Our algorithms are based on the properties of the classical Wronskian determinant, and the folded Wronskian determinant, which was recently introduced by Guruswami and Kopparty [23, 24] and Forbes and Shpilka [14]. Our main conceptual contribution in this article is to show that the Wronskian determinant can also be used to obtain a representation of the truncation of a linear matroid in deterministic polynomial time. An important application of our result is a deterministic algorithm to compute representative sets over linear matroids, which derandomizes a result of Fomin et al. [11, 12]. This result derandomizes several parameterized algorithms, including an algorithm for ℓ-Matroid Parity to which several problems, such as ℓ-Matroid Intersection, can be reduced.