Is the following claim true about the domain of solutions of a linear system with constraints?

Question

I have the following problem:

$$\begin{array}{ll} \text{Solve } A x = b\\\text{subject to} & x_{\min} \le x_i \le x_{\max}, \quad\forall i \in \{1,2,3, M\} \end{array}$$

for $x \in \mathcal{R}^{M \times 1}$, $b \in \mathcal{R}^{3 \times 1}$, $A \in \mathcal{R}^{3 \times M}$, where A have row full rank.

Now I am looking for a method to check wether a solution to the above exist for all $b ={ \begin{bmatrix} b_1 \\b_2\\b_3\end{bmatrix} } $ in the following domain :

$ { - \begin{bmatrix} c_1 \\c_2\\c_3 \end{bmatrix} } \le { \begin{bmatrix} b_1 \\b_2\\b_3\end{bmatrix} } \le{ \begin{bmatrix} c_1 \\c_2\\c_3 \end{bmatrix} } $

where the c's are positive constants

So my suggsted method is as follows:

1) Check $Ax=b_i$ has solution, for all boundaries of b:

$ \{ { b_1= \begin{bmatrix} c_1 \\c_2\\c_3 \end{bmatrix} } ,b_2= \begin{bmatrix} -c_1 \\c_2\\c_3 \end{bmatrix} b_3= { \begin{bmatrix} c_1 \\-c_2\\c_3\end{bmatrix} } , \cdots b_N= \begin{bmatrix} -c_1 \\-c_2\\-c_3 \end{bmatrix} \} $

Thus there are $2^3$ values of B to check.

2) I now want to claim that if I $Ax=b$ is solvable for all boundaries $b_i$(i.e.,the above 8 Equations), then a solution exists for all possible values of b in the domain

$ { - \begin{bmatrix} c_1 \\c_2\\c_3 \end{bmatrix} } \le { \begin{bmatrix} b_1 \\b_2\\b_3\end{bmatrix} } \le{ \begin{bmatrix} c_1 \\c_2\\c_3 \end{bmatrix} } $

So my question is, can this be shown to be true?.

Answer 1

Yes. Suppose $Ax_i=b_i$ for all $b_i$ in the corners. Suppose you have any other point $b$. You represent it as a convex combination $b=\sum t_ib_i$ with $t_i\geq 0, \sum t_i=1$. Then

$$A(\sum t_ix_i) = \sum t_i Ax_i = \sum t_ib_i = b$$

and moreover the point $\sum t_ix_i$ satisfies your box constrains because it is a convex combination of points $x_i$, all of which are in the box.