\(\newcommand{\augmatrix}[2]{\left(\begin{array}{@{}#1 |c@{}} #2 \end{array}\right)} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section2.8Permutation Matrices

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:

  1. 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.)
  2. 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.

Task61
Find an example of a matrix \(A\) such that \(A^T A = 0\), but \(A \neq 0\).
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.
  1. The block matrix \(\left( \begin{smallmatrix} A & 0 \\ 0 & A \end{smallmatrix}\right)\) is automatically symmetric.
  2. If \(A\) and \(B\) are symmetric, then their product \(AB\) is symmetric.
  3. 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.
  1. For any permutation matrix \(P\), it is the case that \(P^T P = I\).
  2. All row exchange matrices are symmetric: \(P^T = P\). (other permutation matrices may or may not be symmetric.)
  3. 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:
  1. \(A\) is not invertible.
  2. \(A\) is invertible but cannot be factored into \(LU\).
  3. \(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.