Permutation matrices: reorder the rows
Slide 5 turned a matrix on its side. This last slide meets the matrices that only reorder rows. Back in lesson 2, a zero pivot forced us to swap two rows. Now we write that swap as a matrix. Think of a playlist. The songs stay the same, only the order in which they play changes. A permutation matrix P does that to the rows of A: PA has the same rows as A, in a new order. P is easy to build: it is the identity I with its rows in that new order. To undo a reordering, you send every row back to its old place, and that turns out to be the transpose: P⁻¹ = Pᵀ.
Lesson 3 · slide 6Permutations- A permutation matrix is I with its rows reordered. Each row and each column of P contains a single 1.
- PA reorders the rows of A; AP reorders its columns (see the rows-or-columns example below).
- P⁻¹ = Pᵀ: transposing undoes the reordering.
- With row exchanges, elimination gives PA = LU.
Build P from the identity
PA is like a playlist with slots: first, second, third. Each slot gets one row of A. To build P, write the rows of I in the order you want. For the order 3, 1, 2, row 1 of P is row 3 of I, and so on:
Read P like this: a 1 in row i, column j means "slot i takes row j". The 1 at (1, 3) says slot 1 takes row 3.
P times A reorders the rows
Use a matrix A whose rows are full of 1s, 2s and 3s, so you can see where each row goes. Row 1 of PA is 001 times A: 0 of row 1, 0 of row 2 and 1 of row 3. That is row 3 of A.
On a single vector, P reorders the numbers: P·102030 = 301020.
Undoing a permutation: P⁻¹ = Pᵀ
To undo P, send each row back. If slot i took row j, the undo says "slot j takes row i back": a 1 at (j, i). Slot 1 took row 3, so the undo has a 1 at (3, 1). Moving every 1 from (i, j) to (j, i) flips P across its diagonal, which gives Pᵀ. So P⁻¹ = Pᵀ for every permutation matrix.
The 2 by 2 swap
In the plane the only reordering, apart from I, is the swap P = 0110. It trades the two numbers of a vector: P·xy = yx. Doing it twice puts them back, so P⁻¹ = P = Pᵀ. Its determinant (slide 2) is 0·0 − 1·1 = −1.
How many are there?
n rows can be ordered in n! = n·(n − 1)⋯1 ways. So there are 2! = 2 permutation matrices of size 2, and 3! = 6 of size 3, counting I. For 10 rows there are already 3,628,800.
Back to elimination: PA = LU
In lesson 2, a zero pivot meant exchanging rows. If A is invertible, run elimination once to discover which exchanges are needed. Collect them into one permutation P. Then PA can be eliminated with no exchanges at all: PA = LU.
A bigger example: a 3 × 3 that needs a swap
NumPy and other solvers compute this PA = LU form for matrices with thousands of rows. They even swap when they don't have to, picking the row with the largest pivot, because big pivots keep rounding errors small.
Next: The recap puts the whole lesson on one page.
Examples
Example 1 · Rows or columns
P = 0110, A = 1234.
Show solutionHide solution
Why columns? Column j of AP is A times column j of P (Ax by columns, lesson 1). Each column of P has a single 1, so it picks out one column of A. Column 1 of P is 01, which picks column 2 of A.
Example 2 · Reverse order
P = 001010100 puts rows in the order 3, 2, 1.
Show solutionHide solution
Example 3 · PA = LU
A = 0231 has a zero first pivot.
Show solutionHide solution
Example 4
How many 3 by 3 permutation matrices are there? Which are their own inverse?
Show solutionHide solution
3! = 6. Four are their own inverse: I and the three single swaps. The other two, the orders 2, 3, 1 and 3, 1, 2, undo each other.
Example 5
What is the determinant of the 2 by 2 swap 0110?
Show solutionHide solution
det 0110 = 0·0 − 1·1 = −1, by slide 2's ad − bc. Lesson 6 explains the sign.
Questions and comments
Stuck on something, or found a mistake? Ask here and I'll answer. You sign in with GitHub.