1

As part of a review of some famous proofs in Hypergraphs matching I ran into this lemma in Linear programming that I am having difficulty showing (or finding an existing proof online):

Let $P=\{\vec{x}\mid A\vec{x}\leq\vec{b}\}$ be the feasible solutions polyhedron. Let $\vec{x}_0\in P$ be a vertex of $P$. Denote $$I = \{ i \in [n] \mid \vec{a}_i\vec{x}_0= b_i \}$$ ($\vec{a}_i$ and $b_i$ are $A$'s and $\vec{b}$'s $i$-th rows accordingly). That is, $I$ is the set of indices of constraints (rows) that $\overrightarrow{x_0}$ exhuasts.

Let $\vec{c}$ be some vector. Then $\vec{x}_0$ maximizes $\vec{c}\vec{x}$ $\iff$ there exists non-negative $\alpha_i$ such that $\vec{c}=\sum_{i \in I}{\alpha_i a_i}$.

Clearly the direction $\impliedby$ is trivial. It's the other direction that's interesting.

Community
  • 1
eladidan
  • 339

1 Answers1

1

I'll prove the nontrivial implication by proviing the contrapositive. Suppose $\vec c$ is not a linear combination of the $\vec a_i$'s for $i\in I$ with non-negative coefficients. By Farkas's Lemma, there is a vector $\vec z$ that has a positive inner product with $\vec c$ but non-positive inner products with the $\vec a_i$ for $i\in I$. Consider the vector $\vec y=\vec x_0+\varepsilon\vec z$ for some small, positive $\varepsilon$.

I claim that $\vec y\in P$ when $\varepsilon$ is sufficiently small. That means I need to check the inequalities $\vec a_i\vec y\leq b_i$ for all $i$, and this amounts to $$ (\vec a_i\vec x_0)+\varepsilon(\vec a_i\vec z)\leq b_i. $$ For $i\in I$, the first of the two inner products here equals $b_i$ (by definition of $I$) and the second is non-positive (by choice of $\vec z$ and positivity of $\varepsilon$), so the inequality holds. For $i\notin I$, the first inner product is $<b_i$, so the desired inequality will hold provided we pick $\varepsilon$ small enough. This completes the verification that, by a suitable choice of $\varepsilon>0$, we can get $\vec y\in P$.

But $\vec c\vec y=(\vec c\vec x_0)+\varepsilon(\vec c\vec z)>(\vec c\vec x_0)$, by our choice of $\vec z$. So $\vec x_0$ doesn't maximize $\vec c\vec x$ over all $\vec x\in P$.

Andreas Blass
  • 71,833