# Are these LP equivalent?

This follows from a previous post of mine (see also). In that post I assumed that there existed no pair of rows (denoted $$\mathbf x^i$$) such that $$\mathbf x^{i'}\geq\mathbf x^i$$. I believe that I can eliminate the assumption and make it a result as follows.

Let $$\mathbf{X'}=\left(x_{ij}\right)$$ be an $$n'\times 2$$ matrix with $$x_{ij}\geq 0$$ and such that there is every row and column has at least a non zero element. Denote $$\mathbf x^i$$ the $$i$$-th row of $$\mathbf X'$$ and assume that rows are ordered so that $$x_{i,1}>x_{i',1}\implies i>i'$$ (if $$x_{i,1}=x_{i',1}$$, then $$x_{i,2}>x_{i',2}\implies i>i'$$). Let $$\mathbf q, \mathbf 1$$ and $$\mathbf 0$$ be column vectors of the appropriate dimension and $$\mathbf k^e$$ a non negative column vector of dimension 2. Consider the problem $$$$\renewcommand{\arraystretch}{1.3} \begin{array}{ll} \text{maximize} &\quad \mathbf{q}^\top\cdot\mathbf{1}\\ \text{subject to} & \quad \mathbf{X'}^{\top}\mathbf{q}\leq\mathbf{k}^e\\ &\quad\mathbf{q}\geq \mathbf 0, \end{array}$$$$ and let $$\mathbf q^*$$ be its solution. We claim that there can exist some $$\mathbf{x}^i$$ for which $$q_i^*=0\;\forall\,\mathbf{k}^e$$. In particular, this will be the case for $$\mathbf{x}^{i^*}$$ if (a) there exists a set of weights $$0\leq \alpha_i\leq1$$ (with $$\sum_{i\ne i^*} \alpha_i=1$$) such that $$\mathbf{\bar x}=\sum_{i\ne i^*}\alpha_i \mathbf x^{i}=\mathbf{x}^{i^*}/\delta$$ for $$\delta\geq 1$$, (b) $$\mathbf x^2\geq\mathbf x^1$$ or (c) $$\mathbf x^{n'}\geq\mathbf x^{n'-1}$$.

To prove it, assume that $$q^*_{i^*}>0$$ and, for part (a) consider $$\hat q_{i^*}=0$$, $$\hat q_{i}=q_{i}^*+\alpha_i\delta q_{i^*}^*,\; \forall\, i\ne i^*$$. For part (b) consider $$\hat q_{2}=0$$, $$\hat q_{1}=q_{1}^*+\delta q_{2}^*$$ with $$\delta=x_{2,1}/x_{1,1}\geq 1$$. Similarly, for part (c) $$\hat q_{n'}=0$$, $$\hat q_{n'-1}=q_{n'}^*+\delta q_{n'}^*$$ with $$\delta=x_{n'-1,2}/x_{n',2}\geq 1$$. Observe that $$\mathbf{\hat q}$$ is feasible by construction and that

$$\sum_{i=1}^n \hat q_i=(\delta-1)q_{i^*}^*+\sum_{i=1}^n q_i^*.$$

As the term $$(\delta-1)q_{i^*}^*\geq 0$$, eliminating the rows for which a solution with $$q_i=0\,\forall\,\mathbf{k}^e$$ exists is immaterial. Reorder the rows of $$\mathbf{X}$$ so that such rows take indices $$n+1$$ to $$n'$$ and consider matrix $$\mathbf{X}=(x_{ij})_{1\leq i\leq n,1\leq j\leq 2}$$. If $$\mathbf{q}^*$$ is the $$n\times 1$$ vector that solves the following problem $$$$\renewcommand{\arraystretch}{1.3} \begin{array}{ll} \text{maximize} &\quad \mathbf{q}^\top\cdot\mathbf{1}\\ \text{subject to} & \quad \mathbf{X}^{\top}\mathbf{q}\leq\mathbf{k}^e\\ &\quad\mathbf{q}\geq \mathbf 0, \end{array}$$$$ then, appending $$n'-n$$ zeroes to it would solve the first.

I believe that this shows that the two problems are equivalent, in the sense that solving one or the other yields the same result (except for the need of adding or eliminating $$n'-n$$ zeroes). I'd like to know whether my proof is correct.