Vandermonde Matrices, NP-Completeness, and Transversal Subspaces |
| |
| Authors: | Alexander Chistov, Hervé Fournier, Leonid Gurvits Pascal Koiran |
| |
| Affiliation: | (1) Saint Petersburg Institute for Informatics and Automation of the Academy of Sciences of Russia, Saint Petersburg 199178, Russia;(2) Université de Versailles Saint-Quentin en Yvelines, 45, avenue des États-Unis, 78035 Versailles Cedex, France;(3) Los Alamos National Laboratory, CCS-3, Los Alamos, NM 87545, USA;(4) LIP, Ecole Normale Supérieure de Lyon, 46 allee d!["rsquo"]("/content/etgld6gflrmn5r1q/xlarge8217.gif") Italie, 69364 Lyon Cedex 07, France |
| |
| 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 leq m and a n × m matrix A with entries in Z, decide whether there exists an n × n subdeterminant of A which is equal to zero. |
| |
| Keywords: | Vandermonde Matrices NP-Completeness Transversal Subspaces |
| 本文献已被 SpringerLink 等数据库收录！ |
|
