Usbrth

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^nc_jx_j$

s.t. $sum_j=1^na_ijx_jleq b_i, forall iin1,...,m$

$x_jgeq 0, forall jin1,...,n$

then the problem given as

$sum_i=1^m a_ijy_i =c_j$ whenever $x_j>0$

$y_i=0$ whenever $sum_j=1^n a_ijx_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 $zneq 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, xgeq 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 I]^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!