# Carathéodory rank

Let [math]A=\{a_1,\dots,a_k\}[/math] be a finite set of vectors in [math]{\mathbb Z}^n[/math]. The **integer cone** of *A* is the set of vectors arising as nonnegative integer combinations of vectors in *A*:

[math]\mbox{int.cone}(A)=\left\{\sum_{i=1}^{k} \lambda_i a_i:\ \lambda_i \in {\mathbb Z}_+\ (i=1,\dots,k)\right\}.[/math]

The **Carathéodory rank** of the set *A* is the smallest integer *t* such that every vector in int.cone(*A*) is the nonnegative integer combination of at most *t* vectors in *A*.

Sebő ^{[1]} proved that if *A* is a Hilbert basis, then the Carathéodory rank of *A* is at most [math]2n-2[/math]. Note that deciding if *A* is a Hilbert basis is a coNP-complete problem, even for 0-1 vectors ^{[2]}. Bruns et al.^{[3]} showed an example where the Carathéodory rank is more than *n* (in fact, they showed that in *n* dimensions the maximal Carathéodory rank is at least [math]\lfloor 7/6 \rfloor n[/math]). It is open if it can be upper bounded by [math](2-\varepsilon)n[/math] for some [math]\varepsilon[/math].

## References

- ↑ A. Sebő,
*Hilbert bases, Carathéodory’s theorem and combinatorial optimization*, in: R. Kannan, W.R. Pulleyblank (Eds.), Integer Programming and Combinatorial Optimization, Univ. of Waterloo Press, Waterloo, Canada, 1990, pp. 431–455, Author link - ↑ J. Pap,
*Recognizing conic TDI systems is hard*, DOI link - ↑ W. Bruns, J. Gubeladze, M. Henk, A. Martin, R. Weismantel,
*A counterexample to an integer analogue of Carathéodory’s theorem*, J. Reine Angew. Math. 510 (1999) 179–185. DOI link, Author link