# Will constraints in this LP be satisfied as equalities?

This is a follow up of my previous question. I repeat it below with an additional condition (in italics).

Say $$\mathbf{X}$$ is a $$n\times m$$ matrix with no negative entries and such that every row and every column have at least a non zero element.

Let $$\mathbf{x}^i$$ be the $$i$$-th row of $$\mathbf{X}$$ and assume further that $$\mathbf{x}^i\not\leq\mathbf{x}^j$$ and $$\mathbf{x}^j\not\leq\mathbf{x}^i\;\forall i,j$$.

Denote $$\langle\mathbf{X}\rangle$$ the cone spanned by $$\mathbf{X}$$. Let $$\mathbf{q},\mathbf{k}, 1$$, and $$0$$ be vectors of the suitable dimension. In the following LP $$\begin{array}{ll} \text{maximize} &\quad \mathbf{q}\cdot 1\\ \text{subject to} & \quad \mathbf{X}^{\top}\mathbf{q}\leq\mathbf{k}\\ &\quad\mathbf{q}\geq 0, \end{array}$$

let $$\mathbf{q}^*$$ be its solution. I see that $$\mathbf{k}\not\in\langle\mathbf{X}\rangle\implies \mathbf{X}^{\top}\mathbf{q}^*\leq\mathbf{k}$$ (with $$\mathbf{X}^{\top}\mathbf{q}^*\ne\mathbf{k}$$), because $$\mathbf{k}\not\in\langle\mathbf{X}\rangle$$ implies that there does not exist a set of positive weights satisfying $$\mathbf{X}^{\top}\mathbf{q}=\mathbf{k}$$.

However, I believe that $$\mathbf{k}\in\langle\mathbf{X}\rangle\implies \mathbf{X}^{\top}\mathbf{q}^*=\mathbf{k}$$. Is this true? Why?

$$X^{T}=\left[\begin{array}{cc} 1 & 5 & 6\\ 0 & 1 & 0\\ 6 & 5 & 1 \end{array}\right],\ k=\left[\begin{array}{c} 12\\ 1\\ 12 \end{array}\right].$$
• Thanks. I believe that it is only true for $m=2$ Commented Feb 16, 2022 at 19:18