 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/digital-systems-linear-algebra-introduction-to-formal-proof/5/c/solution

Write

U = E E_{5} E_{4} E_{3} E_{2} E_{1} M

and put

F_{i} = E E_{i} E

. Inserting

E^{2} = I

between adjacent elimination matrices gives

U = F_{5} F_{4} F_{3} F_{2} F_{1} (EM), EM = F_{1}^{- 1} F_{2}^{- 1} F_{3}^{- 1} F_{4}^{- 1} F_{5}^{- 1} U .

Each

E_{i}^{- 1}

has the restricted lower triangular pattern in part (b)(v). Also

F_{i}^{- 1} = E E_{i}^{- 1} E

, as direct multiplication verifies. Hence every

F_{i}^{- 1}

is lower triangular. Their product is lower triangular by the allowed closure property, proving the required Pivoted LU decomposition with

L = F_{1}^{- 1} \dots F_{5}^{- 1}

Explicitly,

L = 11 - 1 2 01 - 1 1 00100001, U = 10001200 1 - 1 30 1154, EM = LU .

The multipliers in rows three and four of

L

are permuted along with the rows of

M

; simply keeping the unpermuted elimination multipliers would give the wrong product. This is the mechanism in conjugating elimination matrices across a row permutation.

 New to topics? Read the docs here!