Vandermonde Matrices, NP-Completeness, and Transversal Subspaces - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2002

Vandermonde Matrices, NP-Completeness, and Transversal Subspaces

(1) , (1) , (1) , (1)
1

Résumé

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.
Soit K un corps infini. Nous construisons en temps polynomial des familles de sous-espaces de dimension r de Kn satisfaisant la propriété suivante: tout sous-espace de dimension n−r de Kn est supplémentaire à au moins l’un des membres de la famille. Nous donnons également une nouvelle preuve de NPcomplétude pour le problème suivant: étant donnés deux entiers n et m tels que nxm, et une matrice A de taille nxm à coefficients entiers, décider s’il existe un sous-déterminant nxn de A qui est égal à zéro.
Fichier principal
Vignette du fichier
RR2002-31.pdf (138.1 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101906 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101906 , version 1

Citer

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⟩
10 Consultations
230 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More