# 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.

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$.

• It is not clear that the constraints are, indeed, linearly independent when we "😕pass" from $R^n$ to \$R^{n+m}. I mean, what ensures that this new set, when you add m more vectors, is, indeed, l.i, since we were talking about only n in P? – Giiovanna Sep 19 '14 at 12:16
• @Giiovanna I have updated the presentation, taking your comment into account – Ewan Delanoy Sep 20 '14 at 13:02