# Basic solution and linearly independent columns - exercise 2.3 Bertsimas and Tsitsiklis

I am trying to solve exercise 2.3 of the book "Introduction to linear optimization" by Bertsimas and Tsitsiklis, which states:

$$\textbf{ Exercise 2.3 (Basic feasible solutions in standard form polyhedra with upper bounds)}$$ Consider a polyhedron defined by the constraints $$Ax = b$$ and $$0 \leq x \leq u$$, $$u\geq0$$ and assume that the matrix has linearly independent rows.

Prove an analog of Theorem 2.4.

Where Theorem 2.4 is:

$$\textbf{Theorem 2.4}$$ Consider the constraints $$Ax=b$$ and $$\geq 0$$ and as­ sume that the $$m \times n$$ matrix $$A$$ has linearly independent rows. A vector $$x \in \mathbb{R}^n$$ is a basic solution if and only if we have $$Ax = b$$, and there exist indices $$B (1) , . . . , B (m)$$ such that:

$$\bullet\ \text{The columns A_{B(1)},...,A_{B(m)} are linearly independent} \\ \bullet\ \text{If i \neq B(1),...,B(m) then x_i=0}$$

My reformulation of theorem 2.4 would be the following:

$$\textbf{Theorem}$$ Consider the constraints $$Ax = b$$ and $$0\leq x\leq d$$ and as­sume that the $$p \times n$$ matrix $$A$$ has linearly independent rows. A vector $$x \in \mathbb{R}^n$$ is a basic solution if and only if we have Ax = b, and there exist indices $$B (1) , . . . , B (p)$$ such that:

$$\bullet\ \text{The columns A_{B(1)},...,A_{B(p)} are linearly independent;}\\ \bullet\ \text{If i\neq B (1) , . . . , B (p), then x_i = 0 or its respective upper bound d_i.}$$

$$\textit{Proof}$$: Suppose that $$x$$ satisfies both conditions. Then it is true that: \begin{align} \begin{split} Ax = \sum_{i=1}^{p} A_{B(i)} x_{B(i)}+\sum_{i\neq B(1),...B(p)} A_i x_i = b\\ \sum_{i=1}^{p} A_{B(i)} x_{B(i)} =b-\sum_{i\neq B(1),...B(p)} A_i x_i \end{split} \end{align} Since the columns $$A_{B(i)}$$ $$i=1,...,p$$ are linearly independent, $$x_{B(i)}$$ $$i=1,...,p$$ are uniquely determined. By Theorem 2.2 , there are n linearly independent active constraints, and this implies that x is a basic solution.

For the converse, let us assume x is a basic solution. Let $$B(1),...,B(k)$$ all the indices such that $$x_{B(i)} \neq 0$$ and $$x_{B(i)} \neq d_i$$ for all $$i=1,...,k$$.

Since $$x^*$$ is a basic solution, the system of equations formed by the active constraints $$\sum_{i=1}^{n} A_i x_i = b$$, $$x_i=0$$, $$x_ i=d_i$$ $$i \neq B(1),...B(k)$$ has a unique solution (Theorem 2.2). This implies that the columns $$A_{B(1)},...,A_{B(k)}$$ are linearly independent and so $$k\leq p$$.

Since $$rank(A) = p$$, we can choose $$p-k$$ more columns so that the columns $$A_{B(1)},...,A_{B(p)}$$ are linearly independent. Moreover if $$i \neq B(1),...,B(p)$$, then it is also true that $$i \neq B(1),...,B(k)$$, since $$k \leq p$$ and $$x_i=0$$ or $$x_i=d_i$$.

Where

$$\textbf{Theorem 2.2}$$ Let $$x^*$$ be an element of $$\mathbb{R}^n$$ and let I={i : $$a_i^{'}x_i=b_i$$} be the set of indices of constraints that are active at $$x^*$$. Then, the following are equivalent:

$$\bullet\ \text{There exist n vectors in the set {a_i : i \in I} that are linearly independent;}\\ \bullet\ \text{The system of equations a^{'}_ix=b_i has a unique solution}$$

Is my reformulation (and proof) of theorem 2.4 correct?