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 :
Reports
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101906
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:27 AM
Last modification on : Friday, May 17, 2019 - 1:39:22 AM

File

RR2002-31.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101906, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

6

Files downloads

25