| Vandermonde Matrices, NP-Completeness, (2002) | |||||||||||||||||
Abstract | |||||||||||||||||
| Let K be an infinite field. We give polynomial time constructions of families of r-dimensional subspaces of K n with the following transversality property: any linear subspace of K n 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 with n � m and a n × m matrix A with entries in Z, decide whether there exists a n × n sub-determinant of A which is equal to zero. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||