  We consider the following problem: Given a matrix A, find minimal subsets of
columns of A with cardinality no larger than a given bound that are linear
dependent or nearly so. This problem arises in various forms in optimization,
electrical engineering, and statistics. In its full generality, the problem is
known to be NP-complete. We present a Monte Carlo method that finds such
subsets with high confidence. We also give a deterministic method that is
capable of proving that no subsets of linearly dependent columns up to a
certain cardinality exist. The performance of both methods is analyzed and
illustrated with numerical experiments.
