4.4: Swapping rows

When the first pivot is zero¶

Consider

\begin{bmatrix}0&3\\2&-1\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} =\begin{bmatrix}6\\8\end{bmatrix}.

To find an LU factorization, we would need

\begin{bmatrix}0&3\\2&-1\end{bmatrix} =\begin{bmatrix}1&0\\\ell&1\end{bmatrix}\begin{bmatrix}p&q\\0&r\end{bmatrix}.

The first row forces $p=0$ and $q=3$ . But then the bottom-left entry of the product is $\ell\cdot0=0$ , whereas we need it to be 2. There is no LU factorization in this row order.

The system itself is easy to solve: $3y=6$ gives $y=2$ , and $2x-y=8$ then gives $x=5$ .

Swap the two equations, keeping each right-hand side with its equation:

\begin{bmatrix}2&-1\\0&3\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} =\begin{bmatrix}8\\6\end{bmatrix}.

Now the matrix is upper triangular, so its LU factorization has $L=I_2$ and $U=\begin{bmatrix}2&-1\\0&3\end{bmatrix}$ .

Permutation matrices¶

We can describe a row reordering with matrix multiplication too.

For two rows,

P=\begin{bmatrix}0&1\\1&0\end{bmatrix},\qquad P\begin{bmatrix}a&b\\c&d\end{bmatrix}=\begin{bmatrix}c&d\\a&b\end{bmatrix},\qquad P\begin{bmatrix}b_1\\b_2\end{bmatrix}=\begin{bmatrix}b_2\\b_1\end{bmatrix}.

For example, our reordered system above has $PA=LU$ .

Multiplying the original equation by $P$ gives

A\vec x=\vec b\quad\Longleftrightarrow\quad PA\vec x=P\vec b \quad\Longleftrightarrow\quad LU\vec x=P\vec b.

The equivalence holds because a row reordering can be undone: $P$ is invertible.

For our example, $P\vec b=\begin{bmatrix}8\\6\end{bmatrix}$ . Since $L=I_2$ , the first solve gives $\vec y=P\vec b$ , and the second gives $\vec x=\begin{bmatrix}5\\2\end{bmatrix}$ .

Activity 1

Try to factor $A=\begin{bmatrix}0&2\\1&3\end{bmatrix}$ without swapping rows. Which entry makes this impossible?
Find $P,L,U$ with $PA=LU$ , then solve $A\vec x=\begin{bmatrix}4\\7\end{bmatrix}$ .
Let $Q=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}$ . Describe how $Q$ reorders the rows of a matrix, and compute $Q\begin{bmatrix}a\\b\\c\end{bmatrix}$ .
Does $Q^2=I_3$ ? Explain why undoing a general row reordering need not mean applying the same reordering again.

Solution

1. The first row of $U$ would have to be $\begin{bmatrix}0&2\end{bmatrix}$ . Then entry $(2,1)$ of $LU$ would be $\ell_{21}\cdot0=0$ , but entry $(2,1)$ of $A$ is 1. No choice of $\ell_{21}$ works.

2. Swapping the two rows gives

P=\begin{bmatrix}0&1\\1&0\end{bmatrix},\qquad L=I_2,\qquad U=\begin{bmatrix}1&3\\0&2\end{bmatrix},\qquad PA=LU.

The reordered right-hand side is $P\begin{bmatrix}4\\7\end{bmatrix}=\begin{bmatrix}7\\4\end{bmatrix}$ . Since $L=I_2$ , the intermediate vector is $\vec w=\begin{bmatrix}7\\4\end{bmatrix}$ . Solving $U\begin{bmatrix}x\\y\end{bmatrix}=\vec w$ gives $2y=4$ , so $y=2$ , then $x+3(2)=7$ , so $x=1$ . In the original equations, $2(2)=4$ and $1+3(2)=7$ .

3. The matrix $Q=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}$ puts row 2 first, row 3 second, and row 1 third. Thus

Q\begin{bmatrix}a\\b\\c\end{bmatrix}=\begin{bmatrix}b\\c\\a\end{bmatrix}.

4. Applying $Q$ twice sends $\begin{bmatrix}a\\b\\c\end{bmatrix}$ to $\begin{bmatrix}c\\a\\b\end{bmatrix}$ , so $Q^2\ne I_3$ . Applying it three times returns the original vector: $Q^3=I_3$ , so $Q^{-1}=Q^2$ . A single swap undoes itself, but a cyclic reordering of three rows does not.

Existence and uniqueness¶

The theorem does not say that $P$ is unique, or that every invertible matrix factors without reordering. Our first example shows why we may need a row swap.

Why reordering helps¶

At each stage, we subtract contributions already accounted for and look for the next nonzero pivot among the remaining rows. If the current row supplies a zero but a later row supplies a nonzero value, we move that row into the next position.

For an invertible matrix, a suitable row reordering always exists. We’ll explain why in Chapter 5, after introducing linear independence. For now, we’ll work out the complete two-by-two argument below.

Why the factors are unique¶

Once the row ordering is fixed, matching entries forces the first row of $U$ . The nonzero first pivot forces the first column of $L$ . Next, matching entries forces the second row of $U$ , and its nonzero pivot forces the second column of $L$ . Continuing leaves no choices.

The ones on the diagonal of $L$ matter. Without that convention, even $A=I_2$ could be written as $(2I_2)(\frac12I_2)$ as well as $I_2I_2$ .

The general two-by-two case¶

Let $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$ be invertible. Matching entries in

\begin{bmatrix}a&b\\c&d\end{bmatrix} =\begin{bmatrix}1&0\\\ell&1\end{bmatrix} \begin{bmatrix}p&q\\0&r\end{bmatrix}

gives $p=a$ , $q=b$ , $\ell a=c$ , and $\ell b+r=d$ .

Case 1: $a\ne0$ ¶

We can divide by $a$ , giving $\ell=c/a$ and $r=d-cb/a$ . Thus

\boxed{A=\begin{bmatrix}1&0\\c/a&1\end{bmatrix} \begin{bmatrix}a&b\\0&d-cb/a\end{bmatrix}.}

The second pivot is nonzero because

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

and invertibility means $ad-bc\ne0$ , by the two-by-two inverse formula from Chapter 3.6. Every entry of the factors was forced, so they are unique.

Case 2: $a=0$ ¶

Since $A$ is invertible, $ad-bc=-bc\ne0$ . Thus both $b$ and $c$ are nonzero. The equation $\ell\cdot0=c$ is impossible, so there is no LU factorization in the original row order.

Swapping the rows gives

\boxed{PA=\begin{bmatrix}c&d\\0&b\end{bmatrix} =\underbrace{\begin{bmatrix}1&0\\0&1\end{bmatrix}}_L \underbrace{\begin{bmatrix}c&d\\0&b\end{bmatrix}}_U.}

Both pivots are nonzero, so substitution works.

For an invertible two-by-two matrix, we now have a complete rule: factor in the original order when $a\ne0$ ; swap the equations first when $a=0$ . Larger matrices can require swaps at later stages too.

Activity 2

Consider the invertible matrix

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

Start matching entries in $A=LU$ . Find the first row of $U$ , the first column of $L$ , and the second row of $U$ .
What happens when you try to match entry $(3,2)$ ?
Reorder the original rows as row 1, row 3, row 2. Find a (P)LU factorization $PA=LU$ and check your product.
Use those factors to solve $A\vec x=\begin{bmatrix}3\\6\\5\end{bmatrix}$ , remembering to reorder the right-hand side.

Solution

1. For $A=\begin{bmatrix}1&1&0\\1&1&1\\0&1&1\end{bmatrix}$ , matching entries gives the first row of $U$ as $\begin{bmatrix}1&1&0\end{bmatrix}$ . Its first pivot is 1, so $\ell_{21}=1$ and $\ell_{31}=0$ ; the first column of $L$ is $\begin{bmatrix}1\\1\\0\end{bmatrix}$ .

Matching the second row gives $1+u_{22}=1$ and $0+u_{23}=1$ , so $u_{22}=0$ and $u_{23}=1$ . The second row of $U$ is $\begin{bmatrix}0&0&1\end{bmatrix}$ .

2. Entry $(3,2)$ of $LU$ would be $\ell_{31}u_{12}+\ell_{32}u_{22}=0(1)+\ell_{32}(0)=0$ . But entry $(3,2)$ of $A$ is 1. The zero second pivot prevents this factorization, despite the nonzero first pivot.

3. Reorder the original rows as row 1, row 3, row 2:

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

Matching entries now gives

L=\begin{bmatrix}1&0&0\\0&1&0\\1&0&1\end{bmatrix},\qquad U=\begin{bmatrix}1&1&0\\0&1&1\\0&0&1\end{bmatrix}.

Checking the product gives $LU=\begin{bmatrix}1&1&0\\0&1&1\\1&1&1\end{bmatrix}=PA$ .

4. The reordered right-hand side is $P\begin{bmatrix}3\\6\\5\end{bmatrix}=\begin{bmatrix}3\\5\\6\end{bmatrix}$ . Forward substitution in $L\vec y=P\vec b$ gives $y_1=3$ , $y_2=5$ , and $y_1+y_3=6$ , so $y_3=3$ .

Back substitution in $U\vec x=\begin{bmatrix}3\\5\\3\end{bmatrix}$ gives $x_3=3$ , $x_2+x_3=5$ gives $x_2=2$ , and $x_1+x_2=3$ gives $x_1=1$ . Thus

\boxed{\vec x=\begin{bmatrix}1\\2\\3\end{bmatrix}.}

The original system checks: $A\vec x=\begin{bmatrix}1+2\\1+2+3\\2+3\end{bmatrix}=\begin{bmatrix}3\\6\\5\end{bmatrix}$ .

A zero pivot by itself does not tell us that a matrix is non-invertible. We first need to ask whether reordering can resolve it. Next, we’ll turn to square matrices that really are non-invertible, and then to systems whose coefficient matrices aren’t square.

When the first pivot is zero¶

Permutation matrices¶

Existence and uniqueness¶

Why reordering helps¶

Why the factors are unique¶

The general two-by-two case¶

Case 1: a≠0a\ne0a=0¶

Case 2: a=0a=0a=0¶

Case 1: $a\ne0$ ¶

Case 2: $a=0$ ¶