Given parameters $r < n$, define $m = {n \choose r}$ and let $A$ be the $n\times m$ matrix whose columns are all the vectors with $r$ $1$'s and $n-r$ $0$'s. Let $b$ be a positive $n$-vector. Is there a simple solution to the linear program: $$ \max \sum_i x_i$$ subject to $$ Ax \le b$$ and $$ x\ge 0\,?$$


1 Answer 1


Let $\|\cdot\|=\|\cdot \|_1$ be the $1$-norm.

Let $C$ be the convex cone generated by the columns of your matrix. So you need to find $b^*\in C$ such that $b^*\leq b$ (entry-wise) and $\|b^*\|$ is maximal (the required maximum will be $\|b^*\|/r$).

Notice that all generators (and hence all $y=[y_i]\in C$) satisfy the following constraints: \begin{align*} y_i&\geq 0, &i&\in[n];\\ \sum_{i\notin \mathcal I}y_i&\geq \left(1-\frac{|\mathcal I|}r\right)\|y\|, &\mathcal I&\subset[n], \quad 1\leq |\mathcal I|\leq r-1. \tag{$*$} \end{align*} Hence, if we assume that $b=[b_i]$ with $b_1\geq \dots\geq b_n\geq 0$, then we have \begin{equation} \|b^*\|\leq \mu(b):=\min_{0\leq j\leq r-1}\left(1-\frac jr\right)^{-1} \sum_{i=j+1}^n b_i. \tag{$**$} \end{equation} We will show that the equality can always be met (in particular, ths yields that $C$ is determined by the above inequalities).

Induction on $n+r$. If $r=1$ or $r=n$, the claim is obvious. If $b_n=0$, then we may decrease $n$ by $1$. So, in the sequel we assume that $n>r>0$ and $b_1>0$.

Let $j_0$ be the maximal minimizer in $(**)$. Two cases are possible.

Case 1. $j_0>0$. Notice that $$ \left(1-\frac {j_0}r\right)^{-1} \sum_{i=j_0+1}^n b_i\leq \left(1-\frac {j_0-1}r\right)^{-1} \sum_{i=j_0}^n b_i, $$ which yields $$ (r-j_0)b_{j_0}\geq \sum_{i=j_0+1}^n b_i=\frac{r-j_0}r\mu(b), $$ so that $b_1\geq\dots\geq b_{j_0}\geq \mu(b)/r$. Informally, this means that we may harmlessly use the vectors having ones at coordinates $1,2,\dots,j_0$.

So, now consider $b'=[b_{j_0+1},\dots,b_n]$, and set $n'=n-j_0$ and $r'=r-j_0$. For a new set up, for every $0\leq j<r'$ we have $$ \sum_{i=j+1}^{n'}b_{i+j_0}\geq \left(1-\frac {j+j_0}r\right)\mu(b) =\frac{r-j-j_0}{r-j_0} \sum_{i=1}^{n'}b_{i+j_0}=\frac{r'-j}{r'}\sum_{i=1}^{n'}b_{i+j_0}. $$ This means that $b'$ satisfies the inequalities $(**)$ and thus, by the hypothesis, $b'$ is represented as a nonnegative combination of the $n'$-columns with $r'$ ones in each. Augmenting those vectors by the prefix of $j_0$ ones we get a required vector $$ b^*=[\underbrace{\mu(b),\dots,\mu(b)}_{j_0},b_{j_0+1},\dots,b_n]^T $$ with $\|b^*\|=\mu(b)$.

Case 2. $j_0=0$. This means that $b$ satisfies all inequaliies in $(*)$; moreover, they are all strict.

In this case, subtract from $b$ a positive multiple $\alpha\mathbf{1}$ of the all-ones vector (which is clearly in $C$) so that either the last coordinate vanishes or some inequality in $(*)$ turns into equality (so that the new vector $b'=b-\alpha\mathbf{1}$ will have a positive minimizer in $(**)$). Then apply the above arguments.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.