LINEAR-ALGEBRA · Unit 5 · Video 1 · Interactive Practice

Permutation Matrices and the PA = LU Factorization

IKey Formulas

Formula	Name	Description
$PA = LU$	Universal factorization	Works for every invertible matrix
$P^{-1} = P^T$	Permutation inverse	Every permutation matrix is orthogonal
$n!$ permutation matrices	Counting formula	Number of $n \times n$ permutation matrices
$A = LU$ when $P = I$	Special case	No row swaps needed during elimination

IIVisualization 1 — What a permutation does to the rows of $A$

A permutation matrix reorders the rows of $A$ ; only some orderings place a nonzero entry in the first pivot.

Row permutation

💡 Challenge: only one of these six orderings gives a valid first pivot — find it.

IIIVisualization 2 — Building $PA = LU$ step by step

A zero pivot stalls elimination; a row swap $P$ restarts it, and $PA = LU$ records the whole run.

Step 0

Step 0 · Zero pivot

a_{11} = 0

: elimination cannot divide by the pivot.

Step 1 · Build P

Swap

R_1 \leftrightarrow R_2

on the identity to form

P

Step 2 · Form PA

PA

now has a valid pivot

(1,1) = 1

; elimination proceeds.

Step 3 · Clear (3,1)

\ell_{31} = \tfrac{2}{1} = 2

, so

R_3 \leftarrow R_3 - 2R_1

gives

[0, 3, 7]

. Store

2

L_{31}

Step 4 · Clear (3,2)

\ell_{32} = \tfrac{3}{1} = 3

, so

R_3 \leftarrow R_3 - 3R_2

gives

[0, 0, 4]

. Store

3

L_{32}

Step 5 · PA = LU

L

holds the multipliers

2, 3

;

U

holds the pivots

1, 1, 4

💡 In practice $P$ isn't known in advance — you discover the swap only when elimination stalls on a zero pivot.

IVVisualization 3 — Why $P^{-1} = P^{T}$

Applying a permutation and then its transpose returns every row home, so $P^{T}P = I$ .

Permutation

💡 $P^{T}P = I$ says the columns of $P$ are orthonormal — every permutation matrix is orthogonal, at any size.

VQuiz Questions

Question 1 · Counting Permutation Matrices

How many $4 \times 4$ permutation matrices exist?

✅ Correct! There are 4! = 24 permutation matrices of size 4×4.

❌ Not quite. The count is n! (n factorial). For n = 4, compute 4 × 3 × 2 × 1.

Show solution

Solution:

The number of $n \times n$ permutation matrices is $n!$ (n factorial).

For $n = 4$ : $4! = 4 \times 3 \times 2 \times 1 = 24$

Each permutation matrix corresponds to one possible reordering of the 4 rows. The first row can go to any of 4 positions, the second to any of the remaining 3, and so on.

Question 2 · When Is A = LU Sufficient?

True or False: The factorization $A = LU$ (without a permutation matrix $P$ ) works for every invertible matrix.

✅ Correct! A = LU only works when no row swaps are needed. PA = LU is the universal factorization.

❌ Not quite. Consider what happens when elimination encounters a zero pivot — can A = LU still work?

Show solution

Solution:

False. $A = LU$ only works when elimination requires no row swaps — that is, when every pivot encountered during elimination is nonzero without rearranging.

If a zero (or near-zero) pivot appears, we must swap rows. The permutation matrix $P$ records those swaps, giving the universal factorization $PA = LU$ .

$A = LU$ is the special case of $PA = LU$ where $P = I$ (the identity).

Question 3 · Identifying the Permutation Matrix

To fix the zero pivot in $A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 2 & 1 \\ 2 & 7 & 9 \end{bmatrix}$ , we swap rows 1 and 2.

Which matrix is the correct permutation matrix $P$ for this swap?

✅ Correct! Swapping rows 1 and 2 of the identity gives this P.

❌ Not quite. To build P, apply the needed row swap to the identity matrix. We need to swap rows 1 and 2.

Show solution

Solution:

To swap rows 1 and 2, perform the same swap on the identity matrix:

$I = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \xrightarrow{R_1 \leftrightarrow R_2} P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$

Option A swaps rows 2 and 3 (wrong pair)
Option B swaps rows 1 and 2 ✓
Option C swaps rows 1 and 3 (wrong pair)
Option D is the identity — no swap at all

Question 4 · Computing the Multiplier

After the row swap, we have $PA = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 1 & 1 \\ 2 & 7 & 9 \end{bmatrix}$ .

In the first elimination step, $R_3 \leftarrow R_3 - \ell_{31} \cdot R_1$ , what is the multiplier $\ell_{31}$ and what does row 3 become?

✅ Correct! The multiplier is 2 and row 3 becomes [0, 3, 7].

❌ Not quite. The multiplier = (entry to eliminate) / (pivot) = 2/1 = 2. Subtract 2 times row 1 from row 3.

Show solution

Solution:

The multiplier is the entry to eliminate divided by the pivot: $\ell_{31} = \frac{a_{31}}{a_{11}} = \frac{2}{1} = 2$

Then $R_3 \leftarrow R_3 - 2 \cdot R_1$ : $\begin{bmatrix} 2 & 7 & 9 \end{bmatrix} - 2 \cdot \begin{bmatrix} 1 & 2 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 3 & 7 \end{bmatrix}$

Column 1: $2 - 2(1) = 0$ ✓ (eliminated!)
Column 2: $7 - 2(2) = 3$
Column 3: $9 - 2(1) = 7$

The multiplier $\ell_{31} = 2$ is stored in position $(3,1)$ of $L$ .

Solved: 0 / 4

Permutation Matrices and the PA = LU Factorization

IKey Formulas

IIVisualization 1 — What a permutation does to the rows of AAA

IIIVisualization 2 — Building PA=LUPA = LUPA=LU step by step

IVVisualization 3 — Why P−1=PTP^{-1} = P^{T}P−1=PT

VQuiz Questions

IIVisualization 1 — What a permutation does to the rows of $A$

IIIVisualization 2 — Building $PA = LU$ step by step

IVVisualization 3 — Why $P^{-1} = P^{T}$