Linear programming: Basic solution Let $P = \{ x \in R^n : Ax \leq b, x\geq 0\}$ and $Q= \{ (x, r)' \in R^{n+m}: Ax + r= b, x \geq 0, r\geq 0\}.$ Show that
$$x \text{ is basic solution of } P \iff (x, b-Ax) \text{ is basic solution of }Q$$
Type: The restrictions in Q are associated to row vectors in $R^{n+m}$
My attempt:
Lets try the first implication. Suppose that we have n linear ative constraints in x and consider the vector (x, b-Ax). Note that this vector satisfies the equaly constraints in Q. The n linear active constraints in P will be equivalent to n active signal constraints in Q. I need, now, to find m more active constraints such that the set of all of those active connstraints is linearly independent. My guess is that those are the vectors corresponding the equaly constraints, but I couldnt show it.
Well, this iswhat I tried. It would be great to recieve some suggestions to improve it.
Thanks in advance!
 A: The main difficulty here is to write out an expressive enough set of
notations. Write
$$
\begin{array}{lcl}
x^{\sharp} &=& (x,b-Ax) \\
b &=& (b_1,\ldots,b_m) \\
x &=& (x_1,\ldots,x_n) \\ 
A &=& (a_{ij}) \ (1\leq i \leq m,1\leq j \leq n) \\
\phi_i(x_1,\ldots,x_n) &=& \sum_{j=1}^{n}a_{ij}x_j \\
\xi_j(x_1,\ldots,x_n) &=& x_j \\
\eta_j(x,r) &=& \xi_j(x) \\
\sigma_{i}(x,r) &=& r_i \\
\rho_{i}(x,r) &=& r_i+\sum_{j=1}^{n}a_{ij}x_j \\
\end{array}
$$
Then $P$ is defined by the set of $n+m$ inequalities 
$$
\left\lbrace\begin{array}{lcl}
\xi_j\geq 0, \ 1\leq j\leq n & ; &\text{we call these } \xi\text{-inequalities} . \\
\phi_i\leq b_i, \ 1\leq i\leq m & ; &  \text{we call these } \phi\text{-inequalities} . \\
\end{array}\right.\tag{1}
$$
While $Q$ is defined by the set of $n+2m$ inequalities 
$$
\left\lbrace\begin{array}{lcl}
\eta_j\geq 0, \ 1\leq j\leq n & ; &\text{we call these } \eta\text{-inequalities} . \\
\sigma_i\geq 0, \ 1\leq i\leq m & ; &  \text{we call these } \sigma\text{-inequalities} . \\
\rho_i=b_i, \ 1\leq i\leq m & ; &  \text{we call these } \rho\text{-equalities} . \\
\end{array}\right.\tag{2}
$$
Note that equivalently each equality $\rho_i=b_i$ can be replaced by the
set of two inequalities $\rho_i\leq b_i, \rho_i\geq b_i$ ; we call these
$\rho$-inequalities.
Suppose that $x$ is basic relatively to $P$. Then there
is $I\subseteq[|1..n|],J\subseteq[|1..m|] $ such that 
$|I|+|J|=n$, ${\cal F}=\lbrace \phi_i \rbrace_{i\in I} \cup \lbrace \xi_j \rbrace_{j\in J}$
is linearly independent, and $\phi_i(x)=b_i$ for $i\in I$,
$\eta_j(x)=0$ for $j\in J$. Let 
${\cal F}'=\lbrace \rho_i \rbrace_{i\in I} \cup \lbrace \eta_j \rbrace_{j\in J}
\cup \lbrace \sigma_i \rbrace_{1\leq i \leq m}$. Then $| {\cal F}' |=n+m$, and all the members of $G$
are active at $x^{\sharp}$. It will suffice therefore to show that $G$ is linearly
independent ; suppose then that we have a linear relation 
$$
\sum_{i\in I} R_i\sigma_i +
\sum_{j\in J} E_j\eta_j +
\sum_{i=1}^{m} S_i\rho_i=0 \tag{3}
$$
where the $R_i,E_j,S_i$ are scalars. This means for any $(x_1,x_2,\ldots,x_n,r_1,\ldots,r_m)\in R^{n+m}$, we have
$$
\sum_{i\in I} R_ir_i +
\sum_{j\in J} E_jx_j +
\sum_{i=1}^{m} S_i\bigg(r_i+\sum_{j=1}^{n}a_{ij}x_j\bigg)=0 \tag{4}
$$
Rearranging, we obtain
$$
\sum_{i\in I} (R_i+S_i)r_i +
\sum_{i\in I} \sum_{j=1}^{n}S_i a_{ij}x_j+
\sum_{j\in J} E_jx_j +
\sum_{i\not\in I} S_ir_i +
\sum_{i\not\in I} S_i\bigg(\sum_{j=1}^{n}a_{ij}x_j\bigg)=0 \tag{5}
$$  
We deduce that $R_i+S_i=0$ for $i\in I$, and $S_i=0$ for $i\not\in I$, and hence
$$
\sum_{i\in I} \sum_{j=1}^{n}S_i a_{ij}x_j+
\sum_{j\in J} E_jx_j=0 \tag{6}
$$   
This is equivalent to $\sum_{i\in I}S_i\phi_i+\sum_{j\in J}E_j\xi_j=0$, which is
a linear relation between elements of $\cal F$. Thus $x^{\sharp}$ is basic 
relatively to $Q$ as wished.
Conversely, suppose that $x^{\sharp}$ is basic relatively to $Q$. Then there is
a set $\cal G$ of $n+m$ linearly independent constraints from the list in (2), all active
at $x^{\sharp}$. Since $\rho_i$ and $-\rho_i$ are not linearly independent, they are
not both in $\cal F$, so $\cal F$ contains at most $m$ constraints of the form
$\rho_i\leq b_i$ or $\rho_i\geq b_i$. Throwing those away, we are left with (at least)
$n$ linearly independent $\eta$- or $\sigma$- constraints ; the corresponding 
set of $\xi$- or $\phi$- constraints show that $x$ is basic relatively to $P$.
