**18 May 2020**

We have already see some special classes of matrices:

- Identity matrices, usually denoted $I$
- Upper or right triangular matrices, usually denoted $R$ or $U$
- Lower or left triangular matrices, usually denoted $L$
- Diagonal matrices, sometimes denoted $D$
- Permutation matrices (i.e. matrices of invertible functions), sometimes denoted $P$

We have also learned about the LU decomposition, which says that any square matrix $M$ can be decomposed as:

\[M = PLU\]Today, we will learn about a few more decompositions. But first, let’s talk about transposes.

## Tranposes

If $A$ is an $m \times n$ matrix, whose $(i,j)^{th}$ entry is $a_{ij}$, the **transpose** of $A$ is the $n \times m$ matrix $A^\top$ whose $(i,j)^{th}$ entry is $a_{ji}$. For example:

You can think of $A^\top$ as flipping $A$ across its diagonal.

In Python, the transpose of a matrix `A`

is given by `A.T`

or `A.transpose()`

. *Warning: Take note of the round brackets at the end of transpose!*

## Symmetric and Orthogonal matrices

A square matrix is **symmetric** if $A = A^\top$.

A square matrix is **orthogonal** if $AA^\top = A^\top A = I$

**Question 1:** Among the classes of matrices $I, R,L,D,P$, which are symmetric?

**Question 2:** What is the inverse of an orthogonal matrix $Q$?

**Question 3:** Among the classes of matrices $I, R,L,D,P$, which are orthogonal?

## The LU Decomposition

I mentioned in the lecture that if we can write a matrix $A$ as $A = LU$, then we can solve for $x$ in $Ax = b$. But I didn’t show you how to do this.

For the next question, assume that we have a fixed matrix $A$, decomposed into $A = LU$. For any $y$, let $l(y)$ be the solution of $Lx = y$ (i.e. $Ll(y) = y$), and let $u(y)$ be the solution of $Ux = y$.

(You have already seen how to compute $l(y)$ and $u(y)$ in a previous homework, using forward and backward substitution!)

**Question 4:** Express the solution of $Ax = b$, using $b$ and the functions $l$ and $u$.

## The QR decomposition

The **QR decomposition** is a decomposition of a matrix $A$ into $A = QR$ where $Q$ is orthogonal and $R$ is upper triangular.

(We usually $Q$ instead of $O$ to avoid any confusion with $0$. Recall also that an upper triangular matrix is also called *right* triangular. This explains the notation $R$.)

Now suppose $A = QR$, and for any $y$, let $r(y)$ be the solution of $Rx = y$.

**Question 5:** Express the solution of $Ax = b$, using $b$, the function $r$ and the matrix $Q$ and/or its tranpose.

## Powers of diagonal matrices

Since diagonal matrices are also triangular, they share the benefits of triangular matrices, so it’s very easy to solve equations of the form $Dx = b$ where $D$ is diagonal.

But diagonal matrices have an extra benefit that triangular matrices do not have.

**Question 6:** Let $D$ be a diagonal matrix, with entries $d_1, d_2, \dots, d_n$ on the diagonal.
What are the entries of $D^k$, for any integer $k$?

**Question 7:** Suppose that $A = M D M^{-1}$, where $D$ is a diagonal matrix, and $M$ is some invertible matrix.
Express $A^k$ in terms of $M$, $M^{-1}$ and $D^k$.