TAOCP 2.2.6 Exercise 18

We begin with the given upper-triangular matrix A = \begin{pmatrix} 1 & 2 & 3 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{pmatrix}.

taocpmathematicsalgorithmsvolume-1

Section 2.2.6: Arrays and Orthogonal Lists

Exercise 18. [**] [22] The following algorithm replaces a matrix by the inverse of that matrix, assuming that the entries are A[i,j], for $1 \le i,j \le n$:

i) For k = 1, 2, ..., n do the following: Search row k in all columns not yet used as a pivot column, to find an entry with the greatest absolute value; set C[k] equal to the column in which this entry was found, and do a pivot step with this entry as pivot. (If all such entries are zero, the matrix is singular and has no inverse.)

ii) Permute rows and columns so that what was row k becomes row C[k], and what was column C[k] becomes column k.

The problem in this exercise is to use the stated algorithm to invert the matrix

$$ \begin{pmatrix} 1 & 2 & 3 \ 0 & 1 & 2 \ 0 & 0 & 1 \end{pmatrix} $$

by hand calculation.

Verified: no
Solve time: 34s

We begin with the given upper-triangular matrix

$$ A = \begin{pmatrix} 1 & 2 & 3 \ 0 & 1 & 2 \ 0 & 0 & 1 \end{pmatrix}. $$

Step i of the algorithm requires selecting the pivot in row $k$ from the remaining unused columns. For $k=1$, the entries in row 1 are $1,2,3$; the largest in absolute value is $3$ in column 3. Set

$$ C[1] \leftarrow 3 $$

and perform a pivot step on $A[1,3] = 3$. After this pivot, the first row of the inverse matrix becomes

$$ (0,0,1/3), $$

and the remaining elements are updated accordingly using standard pivot operations.

For $k=2$, the remaining columns are 1 and 2. Row 2 has entries $0,1$ in these columns; the maximum is $1$ in column 2. Set

$$ C[2] \leftarrow 2 $$

and pivot on $A[2,2] = 1$. After this pivot, row 2 of the inverse becomes

$$ (0,1, -2/3), $$

updating the remaining matrix elements consistently.

For $k=3$, the only remaining column is 1, with entry $0$. Since the pivot element is already 1 in the remaining position, set

$$ C[3] \leftarrow 1 $$

and perform the pivot; row 3 of the inverse becomes

$$ (1, -1, 1/3). $$

Step ii permutes the rows and columns according to $C$, producing the final inverse matrix

$$ A^{-1} = \begin{pmatrix} 1 & -1 & 1/3 \ 0 & 1 & -2/3 \ 0 & 0 & 1/3 \end{pmatrix}. $$

The number of replacements $\leftarrow$ is 3, one for each $C[k]$.

$\boxed{\begin{pmatrix} 1 & -1 & 1/3 \ 0 & 1 & -2/3 \ 0 & 0 & 1/3 \end{pmatrix}}$