Having trouble understanding this proposition from my textbook.

Question

I'm seeing this perplexing proposition in my optimization textbook:

Suppose an LP

$$\max\{z(x)=\vec{c}^{T}x+\bar{z}:A\vec{x}=\vec{b},\vec{x}\geq\vec{0}\}$$

and a basis $B$ of $A$ are given. Then, the following linear program is an equivalent linear program in canonical form for the basis $B$,

$$\max\hspace{1em}z(x)=\vec{y}^{T}\vec{b}+\bar{z}+(\vec{c}^{T}-\vec{y}^{T}A)\vec{x} $$subject to $$A_{B}^{-1}A\vec{x}=A_{B}^{-1}\vec{b}$$$$\vec{x}\geq\vec{0}$$where $\vec{y}=A_B^{-T}\vec{c}_B$.

Apparently, in this case "basis" means a set of columns in a vector which are linearly independent (rather than anything doing with spanning a vectorspace). $M_B$ denotes an ordered matrix of the columns of $M$ which are members of $B$.

My main trouble is two points:

• What on earth is $A_B^{-T}$?
• Why is $\vec{c}^{T}-\vec{y}^{T}A$ well defined? It seems very possible for $y$ and $c$ to have different lengths.
• The book did not give a good proof of this, just a worked example with real numbers that happens to fit this pattern. Is there an approachable resource I can use to understand optimization of linear models better? Googling only gives resources way above my head, and the textbook for our course is badly written.

Answer 1

1. $A_B^{-T}$ is a shorthand for $(A_B^T)^{-1}$ or equivalently, $(A_B^{-1})^T$.
2. Yes, $\vec{y}$ and $\vec{c}$ may have different lengths, but $\vec{c}^{T}$ and $\vec{y}^{T}A$ have identical lengths and so one can calculate their difference. For instance, you can compute $(1,2)-(3,4,5)\pmatrix{1&2\\ 3&4\\ 5&6}$ although $(1,2)$ is a 2-vector and $(3,4,5)$ is a 3-vector.
3. Multiplying $A_{B}^{-1}A\vec{x}=A_{B}^{-1}\vec{b}$ by $A_B$ on both sides, the constraint is equivalent to $A\vec{x}=\vec{b}$. Hence the new linear program has the same constraints as the old one. In addition, \begin{align*} \vec{y}^{T}\vec{b}+\bar{z}+(\vec{c}^{T}-\vec{y}^{T}A)\vec{x} &=\vec{y}^{T}(\vec{b}-A\vec{x})+\bar{z}+\vec{c}^{T}\vec{x}\\ \end{align*} Under the constraint $A\vec{x}=\vec{b}$, we have $\vec{y}^{T}(\vec{b}-A\vec{x})=0$ and the objective function in the new linear program is equal to the old one. Hence the two linear programs are equivalent.