Skip to Main content Skip to Navigation

Vandermonde Matrices, NP-Completeness, and Transversal Subspaces

Abstract : 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.
Document type :
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:09:27 AM
Last modification on : Saturday, September 11, 2021 - 3:19:18 AM


Files produced by the author(s)


  • HAL Id : hal-02101906, version 1



Alexander Chistov, Hervé Fournier, Leonid Gurvits, Pascal Koiran. Vandermonde Matrices, NP-Completeness, and Transversal Subspaces. [Research Report] LIP RR-2002-31, Laboratoire de l'informatique du parallélisme. 2002, 2+6p. ⟨hal-02101906⟩



Les métriques sont temporairement indisponibles