Discussion on linear programming problems in standard often refers to a special class of solutions called basic solutions.
We will assume throughout that \(\operatorname{rank}(\mathbf{A})= m\). If not, the system \(\mathbf{A} \mathbf{x} = \mathbf{b}\) can be reduced to an equivalent system whose coefficient matrix has full row rank or is determined to be inconsistent.
It is known in linear algebra that if the system \(\mathbf{A} \mathbf{x} = \mathbf{b}\) has a solution, then there is one that has at most \(m\) nonzero entries. (To see this, notice that \(\mathbf{A}\) has \(m\) linearly independent columns since rank \(\operatorname{rank}(\mathbf{A}) = m\). As every column of \(\mathbf{A}\) is an element of \(\mathbb{R}^m\), any set of \(m\) linearly columns of \(\mathbf{A}\) gives a basis for \(\mathbb{R}^m\). Hence, there exists a linear combination of some \(m\) columns of \(\mathbb{A}\) that equals \(\mathbb{b}\).) This fact leads to the following definitions.
An \(m\)-element subset \(B\) of \(\{1,\ldots,n\}\) is said to be a basis (with respect to \(\mathbf{A}\)) if the columns of \(\mathbf{A}\) indexed by the elements in \(B\) are linearly independent.
We say that \(\mathbf{x^*} \in \mathbb{R}^n\) is a basic solution to the system \(\mathbf{A} \mathbf{x} = \mathbf{b}\) if there exists a basis \(B\) such that
\(\mathbf{A} \mathbf{x}^* = \mathbf{b}\);
\(x^*_j = 0\) for all \(j \notin B\).
We say that the basis \(B\) determines the basic solution \(\mathbf{x}^*\). Observe that there cannot be two different basic solutions determined by the same basis. This is because if \(\mathbf{x}^*\) is determined by \(B\), then \(\sum_{j \in B} x^*_j\mathbf{A}_j = \mathbf{b}\) where \(\mathbf{A}_j\) denotes the \(j\)th column of \(\mathbf{A}\). Hence, \(x^*_j\), \(j \in B\) are uniquely determined since the \(m\) columns \(\mathbf{A}_j\), \(j\in B\), are linearly independent.
Given a basis \(B\), the variables \(x_j\), \(j \in B\) are called basic variables. Variables that are not basic are called nonbasic variables. Note that from the definition, in a basic solution, only the basic variables can take on values that are nonzero.
It is possible for a basic solution to be determined by different bases. Here is an extreme example. Consider the system \begin{eqnarray*} x_1 - x_2 + 2 x_3 = 0\\ 2x_1 + x_2 - 3 x_3 = 0 \end{eqnarray*} The basic solution \(\mathbf{x}^* = \begin{bmatrix} 0 \\ 0 \\0\end{bmatrix}\) is determined by the basis \(B=\{1,2\}\) or \(B=\{1,3\}\) or \(B=\{2,3\}\). Note that if a basic solution has exactly \(m\) nonzero entries, then it is determined by a unique basis. A basic solution that can be determined by multiple bases is said to be degenerate.
Proposition 4.1. Let \(\mathbf{A} \in \mathbb{R}^{m\times n}\) with \(\operatorname{rank}(\mathbf{A}) = m\) and let \(\mathbf{b} \in \mathbb{R}^m\). Let \(\mathbf{x}^*\) be a solution to the system \(\mathbf{A}\mathbf{x} = \mathbf{b}\). Let \(J = \{ i \in \{1,\ldots, n\} : x^*_i \neq 0\}. \) Prove that \(\mathbf{x}^*\) is a basic solution to \(\mathbf{A}\mathbf{x} = \mathbf{b}\) if and only if the columns of \(\mathbf{A}\) indexed by \(J\) are linearly independent.
Proof. Suppose that \(\mathbf{x}^*\) is a basic solution determined by a basis \(B\). Clearly, \(J \subseteq B\) since all nonbasic variables are 0. By definition, the columns of \(\mathbf{A}\) indexed by \(B\), and hence those by \(J\), are linearly independent.
Conversely, suppose that the columns of \(\mathbf{A}\) indexed by elements of \(J\) are linearly independent. As \(\operatorname{rank}(\mathbf{A}) = m\), \(|J| \subseteq m\). If \(|J| = m\), then \(J\) is a basis determining the basic solution \(\mathbf{x}^*\). Otherwise, by a result in linear algebra, the columns indexed by elements of \(J\) can be extended to \(m\) linearly independent columns of \(\mathbf{A}\). The \(m\) indices of these column form a basis determining the basic solution \(\mathbf{x}^*\). Hence, \(\mathbf{x}^*\) is a basic solution.
As we are interested in more than solving systems of linear equations, we need to work with solutions to \(\mathbf{A}\mathbf{x} = \mathbf{b}\) that satisfy all the constraints of \((P)\). A basic solution \(\mathbf{x}^*\) to \(\mathbf{A}\mathbf{x} = \mathbf{b}\) with nonnegative components is called a basic feasible solution to the system \(\mathbf{A}\mathbf{x} = \mathbf{b},\ \mathbf{x} \geq \mathbf{0}.\)
Example. Consider the system \(\mathbf{A}\mathbf{x} = \mathbf{b}\) where \(\mathbf{A} = \begin{bmatrix} 1 & -2 & 1 & 1 \\ 0 & -4 & 1 & 2 \\ 0 & -6 & 0 & 3 \end{bmatrix}\) and \(\mathbf{b} = \begin{bmatrix}3\\3\\3\end{bmatrix}.\) Then \(\mathbf{x}^* = \begin{bmatrix} 1\\0\\1\\1\end{bmatrix}\) is a basic solution determined by the basis \(B = \{1,3,4\}\) because it satisfies the system and columns 1, 3 and 4 of \(A\) are linearly independent. Since all components are nonnegative, \(\mathbf{x}^*\) is a basic feasible solution to \(\mathbf{A}\mathbf{x} = \mathbf{b},\ \mathbf{x} \geq \mathbf{0}.\)
Note that \(\mathbf{x}' = \begin{bmatrix} 1\\-\frac{1}{2}\\1\\0\end{bmatrix}\) is a basic solution to \(\mathbf{A}\mathbf{x} = \mathbf{b}\) determined by the basis \(B = \{1,2,3\}\) but it is not a basic feasible solution to \(\mathbf{A}\mathbf{x} = \mathbf{b},\ \mathbf{x} \geq \mathbf{0}.\) because the second component is negative.
Let \(\mathbf{A} \in \mathbb{R}^{m\times n}\) with \(\operatorname{rank}(\mathbf{A}) = m\). Prove that every basis with respect to \(\mathbf{A}\) determines the same basic solution to \(\mathbf{A}\mathbf{x} = \mathbf{0}\).
Let \(\mathbf{A} \in \mathbb{R}^{m\times n}\) with \(\operatorname{rank}(\mathbf{A}) = m\) and let \(\mathbf{b} \in \mathbb{R}^m\). Let \(\mathbf{x}^*\) be a solution to the system \(\mathbf{A}\mathbf{x} = \mathbf{b}\). Let \(J = \{ i \in \{1,\ldots, n\} : x^*_i \neq 0\}. \) Prove that \(\mathbf{x}^*\) is a basic solution to \(\mathbf{A}\mathbf{x} = \mathbf{b}\) if and only if the columns of \(\mathbf{A}\) indexed by \(J\) are linearly independent.
Let \(\mathbf{A} = \begin{bmatrix} 1 & 2 & 0 \\ -1 & 1 & 1\end{bmatrix}\). Let \(\mathbf{b} = \begin{bmatrix} 4 \\ 2 \end{bmatrix}\). Determine all the basic feasible solutions to \(\begin{array}{r}\mathbf{A}\mathbf{x} = \mathbf{b}\\ \mathbf{x} \geq \mathbf{0}\end{array}\).