Show that $\bf x$ is a basic feasible solution

1.5k Views Asked by At

Consider the standard form polyhedron

$${\mathsf P} := \left\{ {\bf x} \in {\Bbb R}^n \mid {\bf A} {\bf x} = {\bf b}, {\bf x} \ge {\bf 0}_n \right\}.$$

Suppose that the $m \times n$ matrix $\bf A$ has linearly independent rows, and that all basic feasible solutions are non-degenerate. Let $\bf x \in \mathsf P$ have exactly $m$ positive components. Show that $\bf x$ is a basic feasible solution.

1

There are 1 best solutions below

0
On

Hint 1: If $x$ is a basic feasible solution, then the columns corresponding to the nonzero components of $x$ must be linearly independent (why?). What would happen if that was not the case?

Hint 2: How does the assumption on linearly independent rows help you? Arguing by contradiction, can you use it to construct a basis which would lead to a degenerate solution? Clearly, you would have to modify $x$ and the corresponding columns of $A$ somehow.

If none of these hints help, you can find the last resort solution here.