# How can I show the corresponding dual solution is unique when the given primal solution is nondegenerate, basic feasible?

the given problem is to show that

if $x_1,...,x_n$ is a nondegenerate basic feasible solution of the primal LP

max $\sum_{j=1}^{n}c_jx_j$

s.t. $\sum_{j=1}^na_{ij}x_j\leq b_i, \forall i\in\{1,...,m\}$

$x_j\geq 0, \forall j\in\{1,...,n\}$

then the problem given as

$\sum_{i=1}^m a_{ij}y_i =c_j$ whenever $x_j>0$

$y_i=0$ whenever $\sum_{j=1}^n a_{ij}x_j < b_i$

has a unique solution.

If $B$ denote the corresponding basis of the given basic solution, letting $y^T= c_B^TB^{-1}$ guarantees the existence of the solution, where $c_B$ denotes the coefficients of the objective functions in the primal corresponding to the given basis.

Now I let $z\neq y$ be a solution of the problem below and tried to induce the contradiction, but could not proceed further. What can I do here? Or is there simpler version rather than this apagogic approach?

I think there are some details missing in your question.

Let the primal be the minimization of $$c^Tx$$, subject to $$Ax = b, x\geq 0$$. We will show the following: if the optimal simplex tableau gives us a non-degenerate basic feasible solution with $$c_i - z_i \geq 0$$ for all variables, then the dual has a unique optimal solution.

Use the complementary slackness conditions.
Note that rank$$(A^T_{n \times m})$$ = rank$$(A_{m \times n}) = m$$, a common assumption (because we can just delete rows if redundant). This means the basis matrix $$B$$ is of dimension $$m \times m$$.
There are $$m$$ constraints, and so, $$m$$ dual variables $$y_1, \ldots y_m$$.

Consider the basic variable $$x_{Bi}$$ in this optimal BFS $$x$$, and an optimal solution $$y$$ of the dual. As the BFS is non-degenerate, $$x_{Bi} > 0$$. The complementary slackness conditions give, $$x_{Bi} (A^Ty - c)_{Bi} = 0$$ which imply, $$(A^Ty)_{Bi} = a_{Bi}^Ty = c_{Bi}$$. Here, $$a_{Bi}^T$$ is the row corresponding to the basic variable $$x_{Bi}$$ in $$A^T$$. Repeating this for all the $$m$$ basic variables, we get the system of equations, compactly represented as $$(A^Ty)_{B} = c_{B}$$. By the definition of a basis, the set of all rows $$a_{B1}^T, \ldots, a_{Bm}^T$$ are all linearly independent. Thus, there exists only a unique solution $$y$$ to $$(A^Ty)_{B} = c_{B}$$.
In fact, multiplying by $$(B^{-1})^T$$ gives us $$y = (B^{-1})^Tc_{B}$$ as claimed. Thus, this solution is unique.

We must also ensure that $$y$$ is feasible for the dual. This comes from the fact that $$c_i - z_i = c_i - a_i^Ty \geq 0$$ for all $$i$$. The dual's feasible region is given by $$A^Ty \leq c$$. So, $$y$$ is feasible as well. This is what we had to show!

• I wish this came sooner... haha. Thank you anyway! – Ian Lee Apr 14 at 15:56
• No problem! Linear programming can be hard! – Ameya Apr 14 at 17:14