Exercise 3.13 (Matrix inversion lemma)

(a) Following the hint, we will prove the identity by showing that the product of $(C+w{v}^{\prime })$ and the expression on the right-hand side is the identity matrix. Let the right-hand side be denoted by $B$:

We want to show that $(C+w{v}^{\prime })B=I$. We expand the product:

First, we compute the term $CB$:

Next, we compute the term $w{v}^{\prime }B$. To simplify this, we first evaluate $v^{\prime }B$, noting that $v^{\prime }{C}^{-1}w$ is a scalar:

Using this result, we can now find $w{v}^{\prime }B$:

Finally, we add the two computed parts together:

This confirms the identity, provided that the denominator $1+v^{\prime }{C}^{-1}w\ne 0$. □

(b) We use the formula from part (a) and compute the right-hand side efficiently by avoiding matrix-matrix multiplications. The procedure is as follows:

1.

Compute the vector $u=C^{-1}w$. This is a matrix-vector product, which requires $O(m^2)$ operations.

2.

Compute the scalar $\alpha =1+v^{\prime }u$. This is a vector dot product plus an addition, requiring $O(m)$ operations.

3.

Compute the row vector $r^{\prime }=v^{\prime }{C}^{-1}$. This is a vector-matrix product, which also requires $O(m^2)$ operations.

4.

The expression to be subtracted is now $\frac{u{r}^{\prime }}{\alpha }$. Forming the rank-one matrix $u{r}^{\prime }$ costs $O(m^2)$, and the subsequent scalar division costs another $O(m^2)$.

5.

Finally, subtract this result from $C^{-1}$. This matrix subtraction requires $O(m^2)$ operations.

The total cost is dominated by the matrix-vector multiplications and matrix additions/subtractions. The overall complexity is therefore $O(m^2)$. □

(c) The matrix $\bar{B}$ is identical to the matrix $B$, except that its $l$th column, $A_{B(l)}$, has been replaced by the entering column, $A_{\bar{B}(l)}$.

The difference $\bar{B}-B$ is therefore a matrix that consists of zero vectors in every column, except for the $l$th column. The $l$th column is the difference between the new and old $l$th columns, which is $(A_{\bar{B}(l)}-A_{B(l)})$.

The expression on the right-hand side is the outer product of the column vector $(A_{\bar{B}(l)}-A_{B(l)})$ and the row vector $e_l^{\prime }$. This product results in a matrix whose $k$th column is $(A_{\bar{B}(l)}-A_{B(l)})$ multiplied by the $k$th component of $e_l^{\prime }$. Since the $k$th component of $e_l^{\prime }$ is 1 if $k=l$ and 0 otherwise, the resulting matrix is zero everywhere except for the $l$th column, which is precisely $(A_{\bar{B}(l)}-A_{B(l)})$. The two sides are therefore equal. □

(d) From part (c), we have $\bar{B}=B+(A_{\bar{B}(l)}-A_{B(l)})e_l^{\prime }$. Let $w=A_{\bar{B}(l)}-A_{B(l)}$ and $v=e_l$. We can now apply the matrix inversion lemma from part (a) with $C=B$:

To find the $i$th row of ${\bar{B}}^{-1}$, we left-multiply by $e_i^{\prime }$:

This is the desired form, where the scalar $g_i$ is given by

To find a more practical form for $g_i$, let $u=B^{-1}{A}_j$ be the pivot column. Note that since $A_{B(l)}$ is the $l$-th column of $B$, we have $B^{-1}{A}_{B(l)}=e_l$. We can then simplify the terms involving $w$:

The term $e_i^{\prime }{e}_l$ is 1 if $i=l$ and 0 otherwise. The pivot element is $u_l\ne 0$. Substituting these back gives the formula:

Interpretation: The identity $e_i^{\prime }{\bar{B}}^{-1}=e_i^{\prime }{B}^{-1}-g_i{e}_l^{\prime }{B}^{-1}$ shows that the new $i$-th row of $B^{-1}$ is obtained by taking the old $i$-th row and subtracting a multiple ( $g_i$) of the old pivot row. This is precisely the elementary row operation used to update the matrix $B^{-1}$ in the revised simplex method.

(e) The full simplex tableau (excluding the zeroth row) can be represented by the matrix $T=B^{-1}[b\mid A]$. The $i$th row of this tableau is therefore $e_i^{\prime }T=e_i^{\prime }{B}^{-1}[b\mid A]$.

We right-multiply the row update formula from part (d) by the matrix $[b\mid A]$:

Distributing the product on the right-hand side gives:

This can be rewritten in terms of tableau rows as:

Interpretation: This equation shows that each row of the new simplex tableau is obtained by subtracting a multiple ( $g_i$) of the old pivot row from the corresponding old row. This is exactly the standard procedure for pivoting in the full tableau implementation:

• For the pivot row ( $i=l$), we have $g_l=\frac{u_l-1}{u_l}$. The update is ${\text{new\_row}}_l={\text{old\_row}}_l-\frac{u_l-1}{u_l}{\text{old\_row}}_l=\frac{1}{u_l}{\text{old\_row}}_l$. This is equivalent to scaling the pivot row to make the pivot element equal to 1.
• For any other row ( $i\ne l$), we have $g_i=u_i∕u_l$. The update is ${\text{new\_row}}_i={\text{old\_row}}_i-\frac{u_i}{u_l}{\text{old\_row}}_l$. This is equivalent to using the scaled pivot row to eliminate the other non-zero entries in the pivot column. □