| Vandermonde Matrices, NP-Completeness, and Transversal Subspaces. (2002) | |||||||||||||
|
|||||||||||||
Abstract | |||||||||||||
| (eng) Let E be a vector space of dimension n over an infinite field K. We give polynomial time constructions of families of r-dimensional subspaces of E with the following transversality property: any linear subspace of E of dimension n-r is transversal to at least one element of the family. We also give a new NP-completeness proof for the following problem: given two integers n and m (m bigger than n) and a n times m matrix A with integer entries, decide whether there exists a n times n sub-determinant of A which is equal to zero. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||