Row Tableaux#
Extended Row Tableaux#
Let \(\mathbf{Ax+s=b}\) be a system of linear equality constraints with vector of control variables \(\mathbf{x}\) and vector of slack variables \(\mathbf{s}\).
\(\mathbf{A}_{[\text{m}\times\text{n}]}\mathbf{x}_{[\text{n}\times1]}+\mathbf{I}_{[\text{m}\times\text{m}]}\mathbf{s}_{[\text{m}\times1]}=\mathbf{b}_{[\text{m}\times1]}\)
The extended row tableau representation of this system is
\( \begin{aligned} \begin{matrix} \kern+1ex 1\left\{\right.\\ m\left\{\begin{matrix}\\\\\\\end{matrix}\right.\\ \end{matrix} \begin{bmatrix} \begin{matrix} \begin{array}{ccc} & \mathbf{x} & \\ \end{array} \begin{array}{ccc} & \mathbf{s} & \\ \end{array}\\ \hline \smash{\underbrace{ \begin{array}{ccc} & & \\ & \mathbf{A} & \\ & & \\ \end{array}}_{n}} \vphantom{\begin{matrix}\\\\\\\end{matrix}} \smash{\underbrace{ \begin{array}{ccc|} & & \\ & \mathbf{I} & \\ & & \\ \end{array}}_{m}} \vphantom{\begin{matrix}\\\\\\\end{matrix}} \begin{array}{c}\end{array} \end{matrix} \smash{\underbrace{ \begin{array}{c} \\\\\mathbf{b}\\\\ \end{array}}_{1}} \vphantom{\begin{matrix}\\\\\\\end{matrix}} \end{bmatrix} \end{aligned} \implies \left\lbrack \begin{array}{cccccc|ccccccc|c} x_1 & x_2 & \dots & x_i & \dots & x_n & s_1 & s_2 & s_3 & \dots & s_i & \dots & s_m & \\ \hline A_{11} & A_{12} & \dots & A_{1i} & \dots & A_{1n} & 1 & 0 & 0 & \dots & s_i & \dots & 0 & b_1 \\ A_{21} & A_{22} & \dots & A_{2i} & \dots & A_{2n} & 0 & 1 & 0 & \dots & 0 & \dots & 0 & b_2 \\ A_{31} & A_{32} & \dots & A_{3i} & \dots & A_{3n} & 0 & 0 & 1 & \dots & 0 & \dots & 0 & b_3 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots \\ A_{j1} & A_{j2} & \dots & A_{ji} & \dots & A_{jn} & 0 & 0 & 0 & \dots & 1 & \dots & 0 & b_j \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots \\ A_{m1} & A_{m2} & \dots & A_{mi} & \dots & A_{mn} & 0 & 0 & 0 & \dots & 0 & \dots & 1 & b_m \\ \end{array} \right\rbrack \)
The number of linear equality constraints \(m\) is the rank of the matrix \(\mathbf{A}\).
The number of linear equality constraints \(m\) is just the number \(m\) of rows in the matrix \(\mathbf{A}\), which is an upper bound on the rank of the matrix \(\mathbf{A}\).
The number of linear equality constraints \(m\) is just the number \(m\) of independent basis vectors under the slack variables, which is a lower bound on the rank of the matrix \(\mathbf{A}\).
The system of linear equality constraints always has a solution.
The basis vectors span \(\mathbb{R}^m\). For any constraint vector \(\mathbf{b}\in\mathbb{R}^m\), values of the corresponding basic variables can be found that will satisfy the row equations.
The remaining non basic variables represent the degrees of freedom in the solution space. Fixing values for the non basic variables results in \(m\) equations in the \(m\) basic variables.
Any sequence of elementary row operations on the matrix results in an equivalent matrix (a matrix with the same solution set).
The variable corresponding to the new column of the basis vector is now a basic variable and the old basic variable is now a non basic variable.
The control variables \(\mathbf{x}\) begin as non basic variables and the slack variables \(\mathbf{s}\) begin as basic variables.
\( \begin{matrix} x_1 & x_2 & s_1 & s_2 & s_3 & \\ A_{11} & A_{12} & 1 & 0 & 0 & b_1 \\ A_{21} & A_{22} & 0 & 1 & 0 & b_2 \\ A_{31} & A_{32} & 0 & 0 & 1 & b_3 \\ \end{matrix} \implies \underset{\text{elementary row operations}}{\dots} \implies \begin{matrix} x_1 & x_2 & s_1 & s_2 & s_3 & \\ A_{11} & 0 & 1 & A_{12} & 0 & b_1 \\ A_{21} & 1 & 0 & A_{22} & 0 & b_2 \\ A_{31} & 0 & 0 & A_{32} & 1 & b_3 \\ \end{matrix} \)
Pivot Operation
To move a non basic variable into the solution basis as a basic variable, replacing a variable which moves out of the solution basis as a non basic variable.
A pivot operation in an extended row tableau is understood in terms of linear algebra, not elementary algebra.
Example#
Pivot \(x_1\) into the solution basis.
\( \begin{bmatrix} x_1 & x_2 & s_1 & s_2 & s_3 & \\ -1 & -1 & 1 & 0 & 0 & -2 \\ -3 & 4 & 0 & 1 & 0 & -12 \\ 3 & -2 & 0 & 0 & 1 & 12 \\ \end{bmatrix}\\ \underset{r_2\leftarrow r_2-3r_1}{\implies}\\ \begin{bmatrix} x_1 & x_2 & s_1 & s_2 & s_3 & \\ -1 & -1 & 1 & 0 & 0 & -2 \\ 0 & 7 & -3 & 1 & 0 & -6 \\ 3 & -2 & 0 & 0 & 1 & 12 \\ \end{bmatrix}\\ \underset{r_3\leftarrow r_3+3r_1}{\implies}\\ \begin{bmatrix} x_1 & x_2 & s_1 & s_2 & s_3 & \\ -1 & -1 & 1 & 0 & 0 & -2 \\ 0 & 7 & -3 & 1 & 0 & -6 \\ 0 & -5 & 3 & 0 & 1 & 6 \\ \end{bmatrix}\\ \underset{r_1\leftarrow-r_1}{\implies}\\ \begin{bmatrix} x_1 & x_2 & s_1 & s_2 & s_3 & \\ 1 & -1 & -1 & 0 & 0 & 2 \\ 0 & 7 & -3 & 1 & 0 & -6 \\ 0 & -5 & 3 & 0 & 1 & 6 \\ \end{bmatrix} \)
Concise Row Tableaux#
Each basic variable has a non zero coefficient in just one row constraint.
To transform an extended row tableau to its concise form, solve each row equation for the basic variable (with non zero coefficient) in that row.
There is a single column of constants with a constant multiplier \(1\) at the top of the column.
The basic variables run down along the right hand side \(\text{rhs}\).
The basic variables are those variables down the right side of the tableau and the non basic variabels are those variables along the top of the tableau.
Pivot Operation
A pivot moves a non basic variable from the top of the tableau to a slot down the right side of the tableau, replacing a basic variable. That variable moves into the position along the top of the tableau as a non basic variable.
A pivot operation in a concise row tableau is understood in terms of elementary algebra, not linear algebra.
Transforming an extended row tableau into its concise form by solving each row equation for its basic variable.
\( \begin{matrix} x_1 & x_2 & s_1 & s_2 & s_3 & \\ A_{11} & A_{12} & 1 & 0 & 0 & b_1 \\ A_{21} & A_{22} & 0 & 1 & 0 & b_2 \\ A_{31} & A_{32} & 0 & 0 & 1 & b_3 \\ \end{matrix} \implies \begin{aligned} A_{11}x_1+A_{12}x_2+s_1&=b_1\\ A_{21}x_1+A_{22}x_2+s_2&=b_2\\ A_{31}x_1+A_{32}x_2+s_3&=b_3\\ \end{aligned} \implies \begin{aligned} -A_{11}x_1-A_{12}x_2+b_1&=s_1\\ -A_{21}x_1-A_{22}x_2+b_2&=s_2\\ -A_{31}x_1-A_{32}x_2+b_3&=s_3\\ \end{aligned} \implies \begin{matrix} x_1 & x_2 & 1 & \\ -A_{11} & -A_{12} & b_1 & s_1 \\ -A_{21} & -A_{22} & b_2 & s_2 \\ -A_{31} & -A_{32} & b_3 & s_3 \\ \end{matrix} \implies \begin{matrix} x_1 & x_2 & 1 & \\ a_{11} & a_{12} & b_1 & s_1 \\ a_{21} & a_{22} & b_2 & s_2 \\ a_{31} & a_{32} & b_3 & s_3 \\ \end{matrix} \)
Concise Row Tableau
\( \left\lbrack \begin{array}{ccccccc|c} x_1 & x_2 & \dots & x_j & \dots & x_n & 1 & \\ \hline a_{11} & a_{12} & \dots & a_{1j} & \dots & a_{1n} & b_1 & s_1 \\ a_{21} & a_{22} & \dots & a_{2j} & \dots & a_{2n} & b_2 & s_2 \\ a_{31} & a_{32} & \dots & a_{3j} & \dots & a_{3n} & b_3 & s_3 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots & \vdots \\ a_{i1} & a_{i2} & \dots & a_{ij} & \dots & a_{in} & b_i & s_i \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mj} & \dots & a_{mn} & b_m & s_m \\ \end{array} \right\rbrack \)
Pivot#
General Pivot Algorithm#
To pivot on the pivot entry \(a_{ij}^*\) in a concise row tableau
Solve the \(i\text{th}\) row equation for the non basic variable at the top of the \(j\text{th}\) column in terms of the other \(n-1\) non basic variables.
Substitute the formula for the \(j\text{th}\) non basic variable obtained in the previous step (i.e., the new \(i\text{th}\) row equation) into the other row equations so that all the other basic variables are now also expressed in terms of the same set of non basic variables.
\( \left\lbrack \begin{array}{ccccccc|c} x_1 & x_2 & \dots & x_j & \dots & x_n & 1 & \\ \hline a_{11} & a_{12} & \dots & a_{1j} & \dots & a_{1n} & b_1 & s_1 \\ a_{21} & a_{22} & \dots & a_{2j} & \dots & a_{2n} & b_2 & s_2 \\ a_{31} & a_{32} & \dots & a_{3j} & \dots & a_{3n} & b_3 & s_3 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots & \vdots \\ a_{i1} & a_{i2} & \dots & a_{ij}^* & \dots & a_{in} & b_i & s_i \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mj} & \dots & a_{mn} & b_m & s_m \\ \end{array} \right\rbrack \)
Pivot Formulae Derivation#
[STEP 1]
Given a “starting” tableau whose non basic variables are the LP control variables and whose basic variables are the LP slack variables, solve for \(x_j\) in terms of \(x_1,...,x_{j-1},s_i,x_{j+1},...,x_n,b_i\).
\( \begin{aligned} a_{i1}x_1+...+a_{i,j-1}x_{j-1}+a_{ij}x_j+a_{i,j+1}x_{j+1}+...+a_{in}x_n+b_i&=s_i\\ \implies\\ a_{i1}x_1+...+a_{i,j-1}x_{j-1}-s_i+a_{i,j+1}x_{j+1}+...+a_{in}x_n+b_i&=-a_{ij}x_j\\ \implies\\ -\frac{1}{a_{ij}}(a_{i1}x_1+...+a_{i,j-1}x_{j-1}-s_i+a_{i,j+1}x_{j+1}+...+a_{in}x_n+b_i)&=x_j\\ \implies\\ \left(-\frac{a_{i1}}{a_{ij}}\right)x_1+...+\left(-\frac{a_{i,j-1}}{a_{ij}}\right)x_{j-1}+\left(\frac{1}{a_{ij}}\right)s_i+\left(-\frac{a_{i,j+1}}{a_{ij}}\right)x_{j+1}+...+\left(-\frac{a_{in}}{a_{ij}}\right)x_n+\left(-\frac{b_i}{a_{ij}}\right)&=x_j\\ \end{aligned} \)
[STEP 2]
Substitute the final expression for \(x_j\) into the other row equations \(1\le k\ne i\le m\) and then group all coefficients of each variable together in the column of the variable.
\( \begin{aligned} a_{k1}x_1+...+a_{k,j-1}x_{j-1}+a_{kj}x_j+a_{k,j+1}x_{j+1}+...+a_{kn}x_n+b_k&=s_k\,\,\,\text{where}\,\,\,1\le k\ne i\le m\\ \implies\\ a_{k1}x_1+...+a_{k,j-1}x_{j-1}\\ +a_{kj}\left[\left(-\frac{a_{i1}}{a_{ij}}\right)x_1+...+\left(-\frac{a_{i,j-1}}{a_{ij}}\right)x_{j-1}+\left(\frac{1}{a_{ij}}\right)s_i+\left(-\frac{a_{i,j+1}}{a_{ij}}\right)x_{j+1}+...+\left(-\frac{a_{in}}{a_{ij}}\right)x_n+\left(-\frac{1}{a_{ij}}\right)b_i\right]\\ +a_{k,j+1}x_{j+1}+...+a_{kn}x_n+b_k&=s_k\\ \implies\\ a_{k1}x_1+...+a_{k,j-1}x_{j-1}\\ +\left(-\frac{a_{kj}a_{i1}}{a_{ij}}\right)x_1+...+\left(-\frac{a_{kj}a_{i,j-1}}{a_{ij}}\right)x_{j-1}+\left(\frac{a_{kj}}{a_{ij}}\right)s_i+\left(-\frac{a_{kj}a_{i,j+1}}{a_{ij}}\right)x_{j+1}+...+\left(-\frac{a_{kj}a_{in}}{a_{ij}}\right)x_n+\left(-\frac{a_{kj}}{a_{ij}}\right)b_i\\ +a_{k,j+1}x_{j+1}+...+a_{kn}x_n+b_k&=s_k\\ \implies\\ \left(a_{k1}-\frac{a_{kj}a_{i1}}{a_{ij}}\right)x_1+...+\left(a_{k,j-1}-\frac{a_{kj}a_{i,j-1}}{a_{ij}}\right)x_{j-1}+\left(\frac{a_{kj}}{a_{ij}}\right)s_i+\left(a_{k,j+1}-\frac{a_{kj}a_{i,j+1}}{a_{ij}}\right)x_{j+1}+...+\left(a_{kn}-\frac{a_{kj}a_{in}}{a_{ij}}\right)x_n+\left(b_k-\frac{a_{kj}b_i}{a_{ij}}\right)&=s_k\\ \end{aligned} \)
Pivot Formulae#
The pivot formulae indicate the entries in the new tableau based on their position relative to the pivot entry \(a_{ij}^*\).
[STEP 1]
\( \begin{aligned} \underbrace{a_{i1}x_1+...+a_{i,j-1}x_{j-1}}_{q}+\underbrace{a_{ij}x_j}_{p}+\underbrace{a_{i,j+1}x_{j+1}+...+a_{in}x_n+b_i}_{q}&=s_i\\ \implies\\ a_{i1}x_1+...+a_{i,j-1}x_{j-1}-s_i+a_{i,j+1}x_{j+1}+...+a_{in}x_n+b_i&=-a_{ij}x_j\\ \implies\\ -\frac{1}{a_{ij}}(a_{i1}x_1+...+a_{i,j-1}x_{j-1}-s_i+a_{i,j+1}x_{j+1}+...+a_{in}x_n+b_i)&=x_j\\ \implies\\ \underbrace{\left(-\frac{a_{i1}}{a_{ij}}\right)x_1+...+\left(-\frac{a_{i,j-1}}{a_{ij}}\right)x_{j-1}}_{-\frac{q}{p}}+\underbrace{\left(\frac{1}{a_{ij}}\right)s_i}_{\frac{1}{p}}+\underbrace{\left(-\frac{a_{i,j+1}}{a_{ij}}\right)x_{j+1}+...+\left(-\frac{a_{in}}{a_{ij}}\right)x_n+\left(-\frac{b_i}{a_{ij}}\right)}_{-\frac{q}{p}}&=x_j\\ \end{aligned} \)
[STEP 2]
\( \begin{aligned} \underbrace{a_{k1}x_1+...+a_{k,j-1}x_{j-1}}_{s}+\underbrace{a_{kj}x_j}_{r}+\underbrace{a_{k,j+1}x_{j+1}+...+a_{kn}x_n+b_k}_{s}&=s_k\,\,\,\text{where}\,\,\,1\le k\ne i\le m\\ \implies\\ a_{k1}x_1+...+a_{k,j-1}x_{j-1}\\ +a_{kj}\left[\left(-\frac{a_{i1}}{a_{ij}}\right)x_1+...+\left(-\frac{a_{i,j-1}}{a_{ij}}\right)x_{j-1}+\left(\frac{1}{a_{ij}}\right)s_i+\left(-\frac{a_{i,j+1}}{a_{ij}}\right)x_{j+1}+...+\left(-\frac{a_{in}}{a_{ij}}\right)x_n+\left(-\frac{1}{a_{ij}}\right)b_i\right]\\ +a_{k,j+1}x_{j+1}+...+a_{kn}x_n+b_k&=s_k\\ \implies\\ a_{k1}x_1+...+a_{k,j-1}x_{j-1}\\ +\left(-\frac{a_{kj}a_{i1}}{a_{ij}}\right)x_1+...+\left(-\frac{a_{kj}a_{i,j-1}}{a_{ij}}\right)x_{j-1}+\left(\frac{a_{kj}}{a_{ij}}\right)s_i+\left(-\frac{a_{kj}a_{i,j+1}}{a_{ij}}\right)x_{j+1}+...+\left(-\frac{a_{kj}a_{in}}{a_{ij}}\right)x_n+\left(-\frac{a_{kj}}{a_{ij}}\right)b_i\\ +a_{k,j+1}x_{j+1}+...+a_{kn}x_n+b_k&=s_k\\ \implies\\ \underbrace{\left(a_{k1}-\frac{a_{kj}a_{i1}}{a_{ij}}\right)x_1+...+\left(a_{k,j-1}-\frac{a_{kj}a_{i,j-1}}{a_{ij}}\right)x_{j-1}}_{s-\frac{qr}{p}}+\underbrace{\left(\frac{a_{kj}}{a_{ij}}\right)s_i}_{\frac{r}{p}}+\underbrace{\left(a_{k,j+1}-\frac{a_{kj}a_{i,j+1}}{a_{ij}}\right)x_{j+1}+...+\left(a_{kn}-\frac{a_{kj}a_{in}}{a_{ij}}\right)x_n+\left(b_k-\frac{a_{kj}b_i}{a_{ij}}\right)}_{s-\frac{qr}{p}}&=s_k\\ \end{aligned} \)
1
Pivot entry
\(a_{ij}\rightarrow\frac{1}{a_{ij}}\)
if \(p:=a_{ij}\) then \(p\rightarrow\frac{1}{p}\)
2
Each entry in the \(i\text{th}\) row other than the pivot entry
\(a_{ik,k\ne j}\rightarrow-\frac{a_{ik}}{a_{ij}}\),\(b_i\rightarrow-\frac{b_i}{a_{ij}}\)
if \(a_{ik,k\ne j},b_i:=q\) then \(q\rightarrow-\frac{q}{p}\)
3
Each entry in the \(j\text{th}\) column other than the pivot entry
\(a_{kj,k\ne i}\rightarrow\frac{a_{kj}}{a_{ij}}\),\(c_j\rightarrow\frac{c_j}{a_{ij}}\)
if \(a_{kj,k\ne i},c_j:=r\) then \(r\rightarrow\frac{r}{p}\)
4
All other entries (Each entry not in the \(i\text{th}\) row nor in the \(j\text{th}\) column)
\(a_{kl,k\ne i,l\ne j}\rightarrow a_{kl}-\frac{a_{kj}a_{il}}{a_{ij}}\),\(d\rightarrow d-\frac{c_jb_i}{a_{ij}}\)
if \(a_{kl,k\ne i,l\ne j},d:=s\) then \(s\rightarrow s-\frac{rq}{p}\)
Example#
Pivot \(x_1\) into the solution basis.
\( \begin{bmatrix} x_1 & x_2 & s_1 & s_2 & s_3 & \\ -1 & -1 & 1 & 0 & 0 & -2 \\ -3 & 4 & 0 & 1 & 0 & -12 \\ 3 & -2 & 0 & 0 & 1 & 12 \\ \end{bmatrix}\\ \underset{\text{extended to concise}}{\implies}\\ \begin{bmatrix} x_1 & x_2 & 1 & \\ 1^* & 1 & -2 & s_1 \\ 3 & -4 & -12 & s_2 \\ -3 & 2 & 12 & s_3 \\ \end{bmatrix}\\ \left( \implies\\ \begin{bmatrix} x_1 & x_2 & 1 & \\ p^* & q & q & s_1 \\ r & s & s & s_2 \\ r & s & s & s_3 \\ \end{bmatrix}\\ \implies\\ \begin{bmatrix} s_1 & x_2 & 1 & \\ \frac{1}{p} & -\frac{q}{p} & -\frac{q}{p} & x_1 \\ \frac{r}{p} & s-\frac{qr}{p} & s-\frac{qr}{p} & s_2 \\ \frac{r}{p} & s-\frac{qr}{p} & s-\frac{qr}{p} & s_3 \\ \end{bmatrix} \right)\\ \implies\\ \begin{bmatrix} s_1 & x_2 & 1 & \\ \frac{1}{1} & -\frac{1}{1} & -\frac{-2}{1} & x_1 \\ \frac{3}{1} & -4-\frac{(1)(3)}{1} & -12-\frac{(-2)(3)}{1} & s_2 \\ \frac{-3}{1} & 2-\frac{(1)(-3)}{1} & 12-\frac{(-2)(-3)}{1} & s_3 \\ \end{bmatrix}\\ \implies\\ \begin{bmatrix} s_1 & x_2 & 1 & \\ 1 & -1 & 2 & x_1 \\ 3 & -7 & -6 & s_2 \\ -3 & 5 & 6 & s_3 \\ \end{bmatrix}\\ \underset{\text{concise to extended}}{\implies}\\ \begin{bmatrix} s_1 & x_2 & x_1 & s_2 & s_3 & \\ -1 & 1 & 1 & 0 & 0 & 2 \\ -3 & 7 & 0 & 1 & 0 & -6 \\ 3 & -5 & 0 & 0 & 1 & 6 \\ \end{bmatrix} \)
Compare this to the extended row tableau pivot example above.
\( \begin{bmatrix} x_1 & x_2 & s_1 & s_2 & s_3 & \\ -1 & -1 & 1 & 0 & 0 & -2 \\ -3 & 4 & 0 & 1 & 0 & -12 \\ 3 & -2 & 0 & 0 & 1 & 12 \\ \end{bmatrix} \underset{\text{elementary row operations}}{\implies} \begin{bmatrix} x_1 & x_2 & s_1 & s_2 & s_3 & \\ 1 & -1 & -1 & 0 & 0 & 2 \\ 0 & 7 & -3 & 1 & 0 & -6 \\ 0 & -5 & 3 & 0 & 1 & 6 \\ \end{bmatrix} \)
Pivot geometry: mapping tableaux to points in Euclidean space#
Set all non basic variables equal to zero.
\( \left\lbrack \begin{array}{ccccccc|c} x_1=0 & x_2=0 & \dots & x_j=0 & \dots & x_n=0 & 1 & \\ \hline a_{11} & a_{12} & \dots & a_{1j} & \dots & a_{1n} & b_1 & s_1 \\ a_{21} & a_{22} & \dots & a_{2j} & \dots & a_{2n} & b_2 & s_2 \\ a_{31} & a_{32} & \dots & a_{3j} & \dots & a_{3n} & b_3 & s_3 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots & \vdots \\ a_{i1} & a_{i2} & \dots & a_{ij}^* & \dots & a_{in} & b_i & s_i \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mj} & \dots & a_{mn} & b_m & s_m \\ \end{array} \right\rbrack \)
\( \begin{aligned} a_{i1}x_1+...+a_{in}x_n+b_i&=s_i\\ \implies\\ a_{i1}(0)+...+a_{in}(0)+b_i&=s_i\\ \implies\\ b_i&=s_i\\ \end{aligned} \)
To satisfy the row constraints, the basic variables must equal the corresponding constants.
This is called the basic solution to the row constraints since it only assigns non zero values to basic variables.