Unextendible Product Bases

N. Alon, L. Lovász

Research output: Contribution to journalArticlepeer-review

51 Scopus citations


Let C denote the complex field. A vector v in the tensor product ⊗mi=1Cki is called a pure product vector if it is a vector of the form v1⊗v2...⊗vm, with vi∈Cki. A set F of pure product vectors is called an unextendible product basis if F consists of orthogonal nonzero vectors, and there is no nonzero pure product vector in ⊗mi=1Cki which is orthogonal to all members of F. The construction of such sets of small cardinality is motivated by a problem in quantum information theory. Here it is shown that the minimum possible cardinality of such a set F is precisely 1+∑mi=1(ki-1) for every sequence of integers k1, k2, ..., km≥2 unless either (i) m=2 and 2∈{k1, k2} or (ii) 1+∑mi=1(ki-1) is odd and at least one ki is even. In each of these two cases, the minimum cardinality of the corresponding F is strictly bigger than 1+∑mi=1(ki-1).

Original languageEnglish (US)
Pages (from-to)169-179
Number of pages11
JournalJournal of Combinatorial Theory. Series A
Issue number1
StatePublished - Jul 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Unextendible Product Bases'. Together they form a unique fingerprint.

Cite this