0
$\begingroup$

I'm currently reading the CLRS Linear Programming chapter and there is something i don't understand.

The goal is to prove that given a basic set of variables, the associated slack form is unique

They first prove a lemma :

enter image description here

And then they prove the result :

enter image description here

My concern is that to prove the second lemma, they apply the first lemma. However equations (29.79) -> (29.82) only holds for feasable solutions, which is not for any x, so why can they apply the first lemma ?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ The notion of being a set of basic variables and non-basic depend on the system of equations only, and the set in question. They are studying a linear system of equations on its own. There is no LP problem in the context of these lemmas, and in particular no inequalities $x_k\geq0$. $\endgroup$ – plop Aug 2 '20 at 18:46
  • $\begingroup$ Still, not every vector x verify the equations (29.79) - (29.82) $\endgroup$ – lairv Aug 2 '20 at 19:17
  • 1
    $\begingroup$ The variables $x_j,j\in N$ are independent. Those are the only ones that are needed for the application of Lemma 29.3 in which they take $I=N$. $\endgroup$ – plop Aug 2 '20 at 19:20
  • $\begingroup$ Ah you are right thanks a lot $\endgroup$ – lairv Aug 2 '20 at 19:27
  • $\begingroup$ @plop Could you please write that as answer? I'd be happy to upvote. $\endgroup$ – Juho Aug 2 '20 at 20:02
2
$\begingroup$

Lemma 29.4 mentions an LP, because that is what they need it for, but it is really a statement in linear algebra about the system of equations $Ax=b$ and a linear form $\phi(x)=c\cdot x$, which in the LP is the objective function.

Lemma 29.4:

If the variables $x_i,i\in B$ are basic variables, i.e. if the corresponding columns of $A$ are a maximal set of linearly independent columns, then you can solve for those variables in terms of the rest of the variables $x_i,i\in N$ and the polynomials obtained are unique. In addition, if you write $\phi(x)=\psi(x_i,i\in N)$, the polynomial $\psi$ is also unique.

(Well, this version of the lemma includes the assertion that one can solve for those variables. This is due to Gaussian elimination.)

Now, for the uniqueness, as they did, you assume that you have two expressions of the basic variables in terms of the non-basic ones

$(x_i)_{i\in B}=(b_i)_{i\in B}+S(x_j)_{j\in N}$ for some matrix $S$ and $(x_i)_{i\in B}=(b_i')_{i\in B}+S'(x_j)_{j\in N}$.

So the polynomials $(b_i)_{i\in B}+S(x_j)_{j\in N}$ and $(b_i')_{i\in B}+S'(x_j)_{j\in N}$ are the same.

By definition $(b_i)_{i\in B}=(b_i')_{i\in B}$ and $S=S'$.

There is no real need to talk about values of the variables, since all the statements are purely algebraic, in the ring of polynomials in the variables $x_i$. So, there is no need for Lemma 29.3. Of course, the equations written have to be thought as equations between polynomials and not as equations between values of functions that are satisfied for all values of the variables. Ignore this paragraph if it causes confusion.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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