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:
\[A = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{pmatrix}, \quad \quad A^\top = \begin{pmatrix} 1 & 1 \\ 2 & 2 \\ 3 & 3 \\ 4 & 4 \end{pmatrix}\]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$.