Lab 9: LU Decomposition and Permutation Matrices

due by the end of class on Wednesday, October 28, 2026

Each lab worksheet will contain several activities, most of which will involve writing math on paper, and some of which will involve running code in a Jupyter Notebook. Lab activities are meant to last an hour, and the second hour of lab is dedicated to starting the homework assignment. To receive credit for a lab, you must show your lab TA your work on both the lab worksheet and homework assignment.

While you must get checked off by your lab TA individually, we encourage you to form groups with 1-2 other students to complete the activities together.

Activities

Activity 1: Reordering a three by three matrix
Activity 2: A general two by two matrix
Activity 3: Permutation matrices

How has the course content since fall break felt to you?

Circle one.

Do you have any concerns about the class that you would like to share?

Activity 1: Reordering a three by three matrix

Consider $A=\begin{bmatrix}3&-3&6\\6&-6&16\\-3&5&-3\end{bmatrix}$ . Throughout, use ones on the diagonal of $$L$$ .

Attempt to find an LU factorization without reordering the rows. Find the first row of $$U$$ , then the first column of $$L$$ , then the second row of $$U$$ . At which step do you get stuck? Write the equation that makes it impossible to continue.

Solution

Write the required shapes:

L=\begin{bmatrix}1&0&0\\\ell_{21}&1&0\\\ell_{31}&\ell_{32}&1\end{bmatrix},\qquad U=\begin{bmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\end{bmatrix}.

First, find the first row of $$U$$ . It must equal the first row of $$A$$ , so $u_{11}=3$ , $u_{12}=-3$ , and $u_{13}=6$ .

Next, find the first column of $$L$$ . Matching entries gives

3\ell_{21}=6,\qquad 3\ell_{31}=-3 \quad\Longrightarrow\quad \ell_{21}=2,\quad\ell_{31}=-1.

Then, find the second row of $$U$$ . We need

2(-3)+u_{22}=-6,\qquad 2(6)+u_{23}=16,

so $u_{22}=0$ and $u_{23}=4$ .

We get stuck when finding $\ell_{32}$ . Entry $$(3,2)$$ would require

(-1)(-3)+\ell_{32}(0)=5, \quad\text{or}\quad \boxed{3=5.}

No choice of $\ell_{32}$ works, so there is no LU factorization in this row order.

Choose two rows to swap so that the reordered matrix has an LU factorization. Write the reordered matrix, then restart the calculation and find its factors $$L$$ and $$U$$ .

Solution

Swap rows 2 and 3. The reordered matrix is

\begin{bmatrix}3&-3&6\\-3&5&-3\\6&-6&16\end{bmatrix}.

The first row of $$U$$ is still $\begin{bmatrix}3&-3&6\end{bmatrix}$ . Matching the first column now gives $\ell_{21}=-1$ and $\ell_{31}=2$ .

Matching the second row gives

(-1)(-3)+u_{22}=5,\qquad (-1)(6)+u_{23}=-3,

so $u_{22}=2$ and $u_{23}=3$ . Next, entry $$(3,2)$$ gives

2(-3)+2\ell_{32}=-6\quad\Longrightarrow\quad\ell_{32}=0.

Finally, entry $$(3,3)$$ gives $2(6)+0(3)+u_{33}=16$ , so $u_{33}=4$ . Thus

\boxed{L=\begin{bmatrix}1&0&0\\-1&1&0\\2&0&1\end{bmatrix},\qquad U=\begin{bmatrix}3&-3&6\\0&2&3\\0&0&4\end{bmatrix}.}

Multiply your factors to check your answer. Does their product equal $$A$$ or the reordered matrix?

Solution

Multiplying gives

LU=\begin{bmatrix}3&-3&6\\-3&3+2&-6+3\\6&-6&12+4\end{bmatrix} =\begin{bmatrix}3&-3&6\\-3&5&-3\\6&-6&16\end{bmatrix}.

The product equals the reordered matrix, not the original matrix $$A$$ .

Activity 2: A general two by two matrix

Let $$B$$ be invertible, and write

B=\begin{bmatrix}a&b\\c&d\end{bmatrix},\qquad L=\begin{bmatrix}1&0\\\ell&1\end{bmatrix},\qquad U=\begin{bmatrix}p&q\\0&r\end{bmatrix}.

Match entries in $$B=LU$$ : first find the first row of $$U$$ , then the first column of $$L$$ , then the second row of $$U$$ . At which step might you get stuck, and why?

Solution

Start by multiplying the required shapes:

LU=\begin{bmatrix}p&q\\\ell p&\ell q+r\end{bmatrix}.

The first row gives $$p=a$$ and $$q=b$$ . Matching the first column then requires $\ell a=c$ . If $a\ne0$ , this gives $\ell=c/a$ . The remaining entry gives

\ell b+r=d\quad\Longrightarrow\quad r=d-\frac{cb}{a}.

We might get stuck when finding $\ell$ : if $$a=0$$ , we cannot divide by $$a$$ . Since $$B$$ is invertible, $ad-bc\ne0$ . When $$a=0$$ , this says $-bc\ne0$ , so $c\ne0$ . The equation $\ell\cdot0=c$ is then impossible.

For which invertible matrices does this procedure work without reordering the rows? Give formulas for $$L$$ and $$U$$ . Explain why both diagonal entries of $$U$$ are nonzero and why the factors are uniquely determined.

Solution

The procedure works exactly when $\boxed{a\ne0}$ . In this case,

\boxed{L=\begin{bmatrix}1&0\\c/a&1\end{bmatrix},\qquad U=\begin{bmatrix}a&b\\0&d-cb/a\end{bmatrix}.}

The first diagonal entry of $$U$$ is $a\ne0$ . The second is

d-\frac{cb}{a}=\frac{ad-bc}{a}\ne0,

because $$B$$ is invertible. Every entry was forced: first $$p$$ and $$q$$ , then $\ell$ , then $$r$$ . Therefore, with ones on the diagonal of $$L$$ , the factors are uniquely determined.

If the procedure gets stuck, explain why swapping the rows allows you to continue. Use the invertibility of $$B$$ to justify your answer, and find the factors for the reordered matrix.

Solution

The procedure gets stuck when $$a=0$$ . Invertibility gives $-bc\ne0$ , so both $$b$$ and $$c$$ are nonzero. Swapping the rows gives

\begin{bmatrix}c&d\\0&b\end{bmatrix}.

This matrix is already upper triangular, so

\boxed{L=\begin{bmatrix}1&0\\0&1\end{bmatrix},\qquad U=\begin{bmatrix}c&d\\0&b\end{bmatrix}.}

Both diagonal entries of $$U$$ are nonzero. The swap makes the top-left entry nonzero, so we can divide by it when finding the entries of $$L$$ .

Activity 3: Permutation matrices

A permutation matrix is a square matrix with exactly one $$1$$ in each row and each column, and zeros everywhere else.

Find a $3\times3$ permutation matrix $$P$$ such that left multiplication by $$P$$ moves the first row of a matrix to the second row, the second row to the third row, and the third row to the first row.

Solution

The new row order must be old row 3, old row 1, old row 2. Reorder the rows of the identity matrix in that order:

\boxed{P=\begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix}.}

For any matrix $$M$$ with three rows, the rows of $$PM$$ are $$M$$ ’s third, first, and second rows. Thus each original row moves to the requested position.

Write down the inverses of the following matrices. Are their inverses also permutation matrices?

Q=\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix},\qquad R=\begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix}.

Solution

Undo $$Q$$ . The matrix $$Q$$ swaps rows 1 and 2. Swapping those rows again restores the original order, so

\boxed{Q^{-1}=Q=\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}.}

Undo $$R$$ . The matrix $$R$$ changes the row order from $$(1,2,3)$$ to $$(3,1,2)$$ . To undo this, select the current rows in order $$(2,3,1)$$ , giving

\boxed{R^{-1}=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}.}

Each inverse has exactly one 1 in each row and each column, with zeros elsewhere. Both inverses are permutation matrices. Applying each reordering and its inverse, in either order, restores every row.

Consider the three permutation matrices $$P_1,P_2,P_3$$ and the matrix $$B$$ :

P_1=\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix},\qquad P_2=\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix},

P_3=\begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix},\qquad B=\begin{bmatrix}2&-1&4\\0&3&5\\-2&6&1\end{bmatrix}.

Find each product by observing how the entries are reordered, without explicitly carrying out matrix multiplication. Write each answer as a $3\times3$ matrix.

\text{(i) }P_1P_2\qquad \text{(ii) }P_2B\qquad \text{(iii) }P_3B\qquad \text{(iv) }P_1P_2B\qquad \text{(v) }BP_1

Solution

Left multiplication by a permutation matrix reorders rows; right multiplication reorders columns. For a sequence of row reorderings, the rightmost permutation matrix acts first.

(i) $$P_1$$ swaps the first two rows of $$P_2$$ , so

\boxed{P_1P_2=\begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix}=P_3.}

(ii) $$P_2$$ swaps the last two rows of $$B$$ :

\boxed{P_2B=\begin{bmatrix}2&-1&4\\-2&6&1\\0&3&5\end{bmatrix}.}

(iii) $$P_3$$ puts the rows of $$B$$ in order $$(3,1,2)$$ :

\boxed{P_3B=\begin{bmatrix}-2&6&1\\2&-1&4\\0&3&5\end{bmatrix}.}

(iv) First $$P_2$$ swaps rows 2 and 3, then $$P_1$$ swaps the current rows 1 and 2. The resulting order is $$(3,1,2)$$ :

\boxed{P_1P_2B=\begin{bmatrix}-2&6&1\\2&-1&4\\0&3&5\end{bmatrix}.}

This agrees with part (i), since $$P_1P_2=P_3$$ .

(v) Multiplying $$B$$ on the right by $$P_1$$ swaps its first two columns, not its rows, so

\boxed{BP_1=\begin{bmatrix}-1&2&4\\3&0&5\\6&-2&1\end{bmatrix}.}

Return to your factorization in Activity 1, where

A=\begin{bmatrix}3&-3&6\\6&-6&16\\-3&5&-3\end{bmatrix}.

Write your answer as $$PA=LU$$ for a permutation matrix $$P$$ , and then as $$A=P’LU$$ for a permutation matrix $$P’$$ . Write all matrices explicitly in both equations.

Solution

Our factorization swaps rows 2 and 3, so take

P=\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix}.

With the factors from Activity 1, $$PA=LU$$ becomes

\boxed{ \begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix} \begin{bmatrix}3&-3&6\\6&-6&16\\-3&5&-3\end{bmatrix} = \begin{bmatrix}1&0&0\\-1&1&0\\2&0&1\end{bmatrix} \begin{bmatrix}3&-3&6\\0&2&3\\0&0&4\end{bmatrix}.}

To recover $$A$$ , multiply on the left by $P^{-1}$ . A row swap undoes itself, so $P’=P^{-1}=P$ . Thus $$A=P’LU$$ is

\boxed{ \begin{bmatrix}3&-3&6\\6&-6&16\\-3&5&-3\end{bmatrix} = \begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix} \begin{bmatrix}1&0&0\\-1&1&0\\2&0&1\end{bmatrix} \begin{bmatrix}3&-3&6\\0&2&3\\0&0&4\end{bmatrix}.}