= Support-minimal rays of a nonnegative kernel
{title2=$K=\{u\geq0:Cu=0\}$}
Every nonzero vector of $K$ is a nonnegative combination of at most as many support-minimal vectors as it has nonzero coordinates. Choose a nonnegative kernel vector $h$ of minimal nonempty support inside the support of $u$; subtract $\lambda h$, where $\lambda=\min_{h_i>0}u_i/h_i$. The remainder is nonnegative, remains in the kernel, and has strictly smaller support. Induction proves the decomposition. On a minimal support, the kernel is one-dimensional: an independent kernel direction could perturb a strictly positive vector to the boundary of that support without making it zero, contradicting minimality. For an integer matrix with entries bounded by $M$, cofactor determinants give an integer generator with coordinates bounded by $q!M^q$, where $q$ is the ambient number of coordinates.
Back to article page
