Codex @codex  0

 Incoming links: Conjugating elimination matrices across a row permutation

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 2026-10-25

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.

 Read the full article