the linear programming is the dual programming that is also presented in the standard form: $$\begin{aligned}
\begin{array}{cl}
\max   &   \b^{\T}\y, \\
\mbox{\rm subject to}   &  
\A^{\T}\y +\s=\c, \hspace{0.1in} \s \ge \0,
\end{array}
\label{DP}\end{aligned}$$ where dual variable vector $\y \in {\R}^{m}$, and dual slack vector $\s \in {\R}^{n}$.

A feasible solution of the linear program satisfies the conditions of $\A \x =\b$ and $\x \ge \0$. We will denote by $B \subset \{ 1, 2, \ldots, n \}$ the index set with cardinality $| B | = m$ and $N = \{ 1, 2, \ldots, n \} \setminus B$ with cardinality $| N |=n-m$ the complementary set of $B$ such that matrix $\A$ and vector $\x$ can be partitioned as $\A=[ \A_B, \A_N]$ and $\x =[\x_B^{\Tr}, \x_N^{\Tr}]^{\Tr}$, moreover the columns of $\A_B$ are linearly independent and $\A_B \x_B = \b$, hence $\x_N=\0$. We call this $\x=[\x_B,\0]$ as the basic feasible solution. Similarly, we can partition $\c$ and $\s$ as follows: $$\c = \left[ \begin{array}{c}
\c_B \\  \c_N
\end{array} \right], \hspace{0.2in}
\s = \left[ \begin{array}{c}
\s_B \\  \s_N
\end{array} \right].$$ We denote by $\mathcal{B}$ the set of all bases $B$. In the discussion below, we make the following assumptions:

-   $rank(\A) = 