# Section2.8Permutation Matrices¶ permalink

# SubsectionThe Assignment

- Read section 2.7 of
*Strang* - Read the following and complete the exercises below.

# SubsectionLearning Goals

Before class, a student should be able to:

- Compute the transpose of a matrix.
- Correctly perform calculations where the transpose interacts with the operations of matrix sum, matrix product, and matrix inverse.
- Compute inner and outer products using the transpose.
- Decide if a matrix is symmetric or not.
- Recognize permutation matrices, and design permutation matrices which correspond to given row swaps.

Some time after class, a student should be able to:

- Find the \(LDL^T\) decomposition for symmetric matrices.
- Explain how the necessity of permuting rows during Gaussian elimination leads to the decomposition \(PA = LU\).
- Explain why \(P^T = P^{-1}\) for permutation matrices.

# SubsectionDiscussion: Transposes, Symmetric Matrices, and Permutations

An important operation on matrices we have yet to encounter is called the
*transpose*. If \(A\) is an \(m\times n\) matrix, the
transpose \(A^T\) of
\(A\) is made by changing the roles of the rows and the columns. The result
\(A^T\) will be an \(n \times m\) matrix, because of this switch.

For now, the transpose will feel like some random thing, but its primary importance comes from its connection with the dot product. If we think of column vectors \(u\) and \(v\) of size \(n\) as if they are \(n \times 1\) matrices, then the dot product \(u \cdot v\) can be computed with a nice combination of matrix multiplication and the transpose: \begin{equation*} u \cdot v = u^T v . \end{equation*} On the right, this is matrix multiplication! That makes sense because \(u^T\) is \(1 \times n\) and \(v\) is \(n \times 1\). This means that the result is a \(1\times 1\) matrix, i.e. a number.

Since the dot product contains all of the geometry of Euclidean space in
it, the transpose becomes an important operation. I know that sounds weird,
but the dot product contains all of the information we need to measure
lengths and angles, so basically all of the *metric* information in
Euclidean geometry is there.

# SubsubsectionAlgebraic results about the transpose

There are some key results about the way the transpose interacts with other matrix operations, each of these can be checked with some tedious computation:

- If \(A\) and \(B\) are matrices of the same shape, then \((A+B)^T = A^T + B^T\).
- If \(A\) and \(B\) are of sizes so that \(AB\) is defined, then \((AB)^T = B^T A^T\).
- If \(A\) is an invertible matrix, with inverse \(A^{-1}\), then \(A^T\) is also invertible and it has inverse \(\left(A^T\right)^{-1} = \left(A^{-1}\right)^T \).

# SubsubsectionSymmetric Matrices

A matrix \(A\) is called *symmetric* when \(A^T = A\). These
pop up in lots of interesting places in linear algebra. A neat result
is that a symmetric matrix has a symmetric looking \(LDU\) decomposition:
\begin{equation*}
\text{if } A^T=A\text{, then } A = LDL^T .
\end{equation*}
That is, in the LDU decomposition, \(U = L^T\).

There are several ways to get symmetric matrices. For example, if \(A\) is any matrix, the new matrix \(B = A^T A\) will be symmetric. (Check this.) Also, the matrix \(S = A^T + A\) will be symmetric.

# SubsubsectionPermutation Matrices and Pivoting strategies in Gauss-Jordan Elimination

It is sometimes the case that Gauss-Jordan elimination requires a row
swap. As we have seen, the operation of swapping a row can be achieved
by left multiplying by a matrix of a special type. If we take a bunch of
those and multiply them together, we still get a matrix which is in a
special class: *the permutation matrices*.

A permutation matrix is square matrix having a single \(1\) in each column and in each row. A helpful property of permutation matrices is that they are invertible, and their inverses are the same as their transposes: \begin{equation*} P^{-1} = P^T . \end{equation*}

Gauss-Jordan elimination is easy enough to understand, now. It is time to let go of performing all those arithmetic operations by hand. So, permutation matrices become important for a different reason! Even if Gauss-Jordan elimination can be done without a row swap, it may be numerically better for a computer to swap out for a larger number as a pivot, so a row swap is used anyway. This partial pivoting strategy is encapsulated in most computer algebra algorithms in some way, and is part of the computation involved in computing a PLU decomposition. Strang has a decent discussion of the choices, below we will discuss how SageMath handles this.

# SubsectionSageMath and Transposes, Symmetry, Permutations, and Pivots

There is a lot going on in this little section. At first glance, it is a bit intimidating. But we have seen most of the ideas before.

# SubsubsectionThe Transpose

The transpose of a matrix is what you get by switching the roles of rows and columns. SageMath has a simple method for this.

One place that the transpose is useful is in describing the dot product. Check this out.

To be sure, we check what the “parent” of `U` is.

See! SageMath thinks of `U` as a matrix with 3 rows and 1 column.

Now we do the same with `v`

Now the magic.

That is the dot product, but stuffed into a \(1\times 1\) matrix!

# SubsubsectionOther Properties

The transpose has other useful properties. Strang lists the big ones, including how the transpose interacts with matrix multiplication and matrix inverses.

# SubsubsectionSymmetry

A matrix is called *symmetric* when it is equal to its
transpose. SageMath has some built-in commands for this.

Strang notes a really neat property of symmetric matrices. Their \(LDU\) decompostions are nicer than average.

# SubsubsectionPermutations and Pivots

We have seen that elimination sometimes requires us to perform a row
operation of swapping the position of two rows to put a pivot in a good
place. At first, we want to do this to avoid a zero. But for computational
reasons, a machine really likes to have a *big* number as a pivot.
So software often uses rows swaps even when not strictly needed.

If all we care about is finding the reduced row echelon form (rref), then this won't worry us. You do whatever operations you want, and the rref is always the same thing. But if we want to keep track with matrices, things get a little complicated.

Here is the important stuff to remember:

- A row swap is performed by a permutation matrix. A permutation matrix is a matrix with exactly one \(1\) in each column and in each row. These matrices have the important property that their transposes and their inverses are equal. That is, if \(P\) is a permutation matrix, then \(P^T\) is equal to \(P^{-1}\). (Not every matrix with this extra property is a permutation matrix. Be careful.)
- It is possible to figure out what all of the row swaps should be, and then rearrange all of the amtrices in an LU decomposition routine. If you do it correctly, you get: \begin{equation*} P'A = LU \end{equation*} or \begin{equation*} A = PLU \end{equation*} where \(P'\) and \(P\) are permutation matrices.

Note: Strang prefers to write things as \(P'A = LU\), but SageMath writes \(A = PLU\). Fortunately, there is a simple relationship here. Strang's \(P'\) is the transpose (and hence the inverse!) of SageMath's \(P\).

If you haven't figured it out by now, I think that row reduction by hand is really for chumps. SageMath (or whatever computational tool you use) makes it waaaaaaaaay easier.

# SubsectionExercises

Keep this in mind. The computations are simple, but tedious. Perhaps you want to use an appropriate tool.

##### Task62

These are true or false questions. If the statement is true, explain why you know it is true. If the statement is false, give an example that shows it is false.- The block matrix \(\left( \begin{smallmatrix} A & 0 \\ 0 & A \end{smallmatrix}\right)\) is automatically symmetric.
- If \(A\) and \(B\) are symmetric, then their product \(AB\) is symmetric.
- If \(A\) is not symmetric, then \(A^{-1}\) is not symmetric.

##### Task63

If \(P_1\) and \(P_2\) are permuation matrices, then so is \(P_1P_2\). Give examples with \(P_1P_2 \neq P_2P_1\) and \(P_3P_4 = P_4P_3\).##### Task64

Explain the following phenomena in terms of row operations.- For any permutation matrix \(P\), it is the case that \(P^T P = I\).
- All row exchange matrices are symmetric: \(P^T = P\). (other permutation matrices may or may not be symmetric.)
- If \(P\) is a row exchange matrix, then \(P^2 = I\).

##### Task65

For each of the following, find an example of a \(2\times 2\) symmetric matrix with the given property:- \(A\) is not invertible.
- \(A\) is invertible but cannot be factored into \(LU\).
- \(A\) can be factored into \(LDL^T\), but not into \(LL^T\) because \(D\) has negative entries.

##### Task66

This is a new factorization of \(A\) into *triangular
times symmetric*:

Start with \(A = LDU\). Then \(A = B S\), where \(B = L\left(U^T\right)^{-1}\) and \(S = U^T D U\).

Explain why this choice of \(B\) is lower triangular with \(1\)'s on the diagonal. Expain why \(S\) is symmetric.