 # Basic

Associated with a submatrix of $LaTeX: A$, say $LaTeX: B$, whose columns comprise a basis for $LaTeX: \mathbb{R}^m$ (i.e., $LaTeX: B$ consists of $LaTeX: m$ linearly independent columns of $LaTeX: A$, which is a basis for $LaTeX: \mathbb{R}^m$).

Here are some related terms that arise in linear programming.

• Adjacent basis. One that differs in exactly one column from a given basis.
• Basic column. A column of the basis matrix.
• Basic variable. The variable, say $LaTeX: x_j$, associated with the $LaTeX: j$-th column of the basis matrix.
• Basic level. The value of a basic variable.
• Basic solution. The solution, $LaTeX: x$, obtained by setting nonbasic values to some bound value, like 0, resulting in a unique solution for the basic variables. That is, $LaTeX: Ax=b$ is equivalent to $LaTeX: Bu + Nv = b$, where $LaTeX: A=[B \; N]$ and $LaTeX: x=[u^T \; v^T]^T$. Upon fixing the value of $LaTeX: v$, the nonsingularity of $LaTeX: B$ gives the basic solution with $LaTeX: u = B^{-1}(b - Nv)$. In a standard linear program, $LaTeX: v=0$, and hence $LaTeX: u = B^{-1} b$.
• Basic feasible solution. A basic solution that is feasible --i.e., the basic values satisfy their bounds. (In a standard LP, this means $LaTeX: B^{-1}b \ge 0$.)
• Basis kernel. After performing forward triangularization, if the basis does not triangularize completely, backward triangularization is applied. The result is a (rearranged) blocking of the basis into three segments:
```                |\
| \ <--- Forward triangle
|__\ ______
|   |      |
|   |      | <--- Kernel
|   |______|
|          |\
|          | \ <--- Backward triangle
|__________|__\
```
Each row and column in the kernel has at least 2 nonzeroes.