Announcements¶

• Test 1 grades are out

• Homework 4 is due today

• Homework 5 will be posted later today and due after the break

• Aggarwal Section 2.4-2.5

• Watch 3Blue1Brown video 5 and video 6

Recap¶

Onto¶

Definition. A mapping $T:R^n\to R^m$ is said to be onto $R^m$ if each $b$ in $R^m$ is the image of at least one $x$ in $R^n$.

In other words, $T$ is onto if every element of its codomain is in its range.

Here, we see that $T$ maps points in $R^2$ to a plane lying within $R^3$. That is, the range of $T$ is a strict subset of the codomain of $T$.

So $T$ is not onto $R^3$.

One-to-one¶

Definition. A mapping $T:R^n\to R^m$ is said to be one-to-one if each $b$ in $R^m$ is the image of at most one $x$ in $R^n$.

Determinant¶

So we conclude that when we use a linear transformation

the area of a unit square (or any shape) is scaled by a factor of $ad-bc$.

This quantity is a fundamental property of the matrix $A$.

So, we give it a name: it is the determinant of $A$.

We denote it as $det\left(A\right)$.

So, for a $2\times 2$ matrix $A=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]$,

Inverse of a matrix¶

Definition. A matrix $A$ is called invertible if there exists a matrix $C$ such that

In that case, $C$ is called the inverse of $A$.

Clearly, $C$ must also be square and the same size as $A$.

The inverse of $A$ is denoted $A^{-1}.$

A matrix that is not invertible is called a singular matrix. A matrix that is invertible is called nonsingular.

Here are some nice properties of the matrix inversion.

Theorem.

• If $A$ is an invertible matrix, then $A^{-1}$ is invertible, and

• If $A$ is an invertible matrix, then so is $A^T,$ and the inverse of $A^T$ is the transpose of $A^{-1}.$

• If $A$ and $B$ are $n\times n$ invertible matrices, then so is $AB,$ and the inverse of $AB$ is the product of the inverses of $A$ and $B$ in the reverse order.

Example.

If $A=\left[\begin{array}{cc}2& 5\\ -3& -7\end{array}\right]$ and $C=\left[\begin{array}{cc}-7& -5\\ 3& 2\end{array}\right]$, then:

and:

so we conclude that $C=A^{-1}.$

Lecture 18: Matrix Factorization¶

18.1 Finding the inverse of a matrix¶

How do we find $A^{-1}$? Let's first look at the special case of $2\times 2$ matrices and then consider the general case of any square matrix.

The $2\times 2$ case¶

Theorem. Let $A$ = $\left[\begin{array}{cc}a& b\\ c& d\end{array}\right].$

If $det\left(A\right)\ne 0$, then

• $A$ is invertible and
• $A^{-1}=\frac{1}{det\left(A\right)}\left[\begin{array}{cc}d& -b\\ -c& a\end{array}\right].$

If $det\left(A\right)=0$, then

• $A$ is not invertible.

Notice that this theorem tells us, for $2\times 2$ matrices, exactly which ones are invertible... namely, those that have nonzero determinant.

Example. Given a $2\times 2$ matrix $A$, if the columns of $A$ are linearly dependent, is $A$ invertible?

Solution. If the columns of $A$ are linearly dependent, then at least one of the columns is a multiple of the other.

Let the multiplier be $m.$

Then we can express $A$ as: $\left[\begin{array}{cc}a& ma\\ b& mb\end{array}\right].$

The determinant of $A$ is $a\left(mb\right)-b\left(ma\right)=0.$

So a $2\times 2$ matrix with linearly dependent columns is not invertible.

Matrices larger than $2\times 2$.¶

Now let's look at a general method for computing the inverse of $A$. Recall our definition of matrix multiplication: $AB$ is the matrix formed by multiplying $A$ times each column of $B$.

Let's look at the equation

Let's call the columns of $A^{-1}$ = $[x_1,x_2,\dots ,x_n].$

We know what the columns of $I$ are: $[e_1,e_2,\dots ,e_n].$

So:

Notice that we can break this up into $n$ separate problems:

(This is a common trick ... make sure you understand why it works!)

So here is a general way to compute the inverse of $A$:

• Solve the linear system $A{x}_1=e_1$ to get the first column of $A^{-1}.$
• Solve the linear system $A{x}_2=e_2$ to get the second column of $A^{-1}.$
• $\dots$
• Solve the linear system $A{x}_n=e_n$ to get the last column of $A^{-1}.$

If any of the systems are inconsistent or has an infinite solution set, then $A^{-1}$ does not exist.

Using Gaussian Elimination to find $A^{-1}$¶

This general strategy leads to an algorithm for inverting any matrix. We can use Gaussian Elimination on the larger augmented matrix $[A\mid I]$. The result in reduced row echelon form will be $[I\mid A^{-1}]$.

We can confirm that we found $A^{-1}$ by multiplying them together:

Computing inverse matrices¶

But solving all of these linear systems is complicated.

Any time you need to invert a matrix larger than $2\times 2,$ you may need to use a calculator or computer.

To invert a matrix in Python/numpy, use the function np.linalg.inv(). For example:

What do you think happens if you call np.linalg.inv() on a matrix that is not invertible?

The right way to handle this is:

18.2 Solving linear systems using matrix inverses¶

Let's discover a new way to solve a linear system based on computing the inverse of a square matrix $A$ (if it exists!).

Theorem. If $A$ is an invertible $n\times n$ matrix, then for each $b$ in $R^n,$ the equation $Ax=b$ has the unique solution $A^{-1}b.$

Proof. Let's multiply both sides by $A^{-1}$ on the left:

This very simple, powerful theorem gives us a new way to solve a linear system.

Furthermore, this theorem tells us the number of solutions to the system. In general, we know that a system of $n$ equations in $n$ variables can have:

• No solution (it is inconsistent)
• A unique solution
• Infinitely many solutions

But this theorem says that if $A$ is invertible, then the system has a unique solution.

Example. Solve the system:

Rewrite this system as a matrix equation $Ax=b:$

The determinant of $A$ is $3\left(6\right)-4\left(5\right)=-2,$ which is nonzero, so $A$ has an inverse.

According to our $2\times 2$ formula, the inverse of $A$ is:

So the solution is:

18.3 Matrix Multiplication and Factorization¶

We know that matrix-vector multiplication should be interpreted as a linear transformation over $R^n$.

Question. What does the product of two matrices mean, geometrically?

We determined that the matrix

implements a 180 degree rotation through the origin.

But notice that we could have accomplished this another way:

• First reflect through the $x_1$ axis, using multiplication by $B=\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right]$.
• Then reflect through the $x_2$ axis, using multiplication by $A=\left[\begin{array}{cc}-1& 0\\ 0& 1\end{array}\right]$.

So, another way to reflect point $u$ through the origin would be:

• $v=Bu$
• Followed by $w=Av.$

As a result, $w=A\left(Bu\right).$ We also know that $w=Cu$. And this is true for all vectors $u$.

Therefore, multiplication of matrices corresponds to composition of linear transformations.

That is: $C$ is the result of applying the transformation corresponding to matrix $B$, and then transformation $A$. (Just like functions: the order matters, and we read them from right to left!)

Example. Let $A=\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]$ and $B=\left[\begin{array}{cc}0& 1\\ -1& 0\end{array}\right]$. Show that $A^3=B$.

You could calculate $A^3$ using the algebraic rules for matrix multiplication, but there is an easier way to think about this question geometrically.

Note that $A$ maps $e_1\mapsto e_2$ and $e_2\mapsto -e_1$, so it corresponds to a 90 degree counterclockwise rotation $T_{90}$. Similarly, $B$ corresponds to a 270 degree counterclockwise rotation $T_{270}$.

What happens if we perform a 90 degree rotation three times in a row? The result of the function $T_{90}\left(T_{90}\right(T_{90}\left(x\right)\left)\right)$ must be a 270 degree rotation. In other words, $T_{90}\circ T_{90}\circ T_{90}=T_{270}$.

Because composition of linear transformations corresponds to multiplication of matrices, it follows immediately that $A^3=B$.

We can check this computationally.

Matrix Factorization¶

A factorization of a matrix $A$ is an equation that expresses $A$ as a product of two or more matrices.

The essential difference with what we have done so far is that we have been given factors ($B$ and $C$) and then computed their product $A$.

In a factorization problem, you are given $A$, and you want to find $B$ and $C$ -- that meet some conditions.

There are a number of reasons one may want to factor a matrix.

• Recasting $A$ into a form that makes computing with $A$ faster.
• Recasting $A$ into a form that makes working with $A$ easier.
• Recasting $A$ into a form that exposes important properties of $A$.

Let's motivate this problem by calculating the cost of matrix operations:

• Matrix multiplication using the inner product method
• Matrix inversion using Gaussian elimination

Then, we will explore a new, faster way to solve linear systems.

18.4 Computational Complexity of Matrix Multiplication¶

Recall that in Python/numpy:

C = A @ B

denotes matrix multiplication.

We can manually calculate the product of two matrices $A$ and $B$ using the inner product rule.

Question. What is the computational complexity of matrix multiplication?

The machine learning algorithms we explore later in the course all rely heavily on matrix muliplication. So, minimizing the time required to do matrix multiplication is immensely important.

For two square $n\times n$ matrices $A$ and $B$, consider the definition that uses inner product:

Each element of the product $AB$ requires $2n$ floating point operations ($n$ multiplications and $n$ additions).

There are $n^2$ elements of $AB$, so the overall computation requires

operations using this algorithm.

Note: There do exist faster algorithms for computing matrix multiplication that run in time $O\left(n^{\omega }\right)$ where $2\le \omega <3$, but let's stick with this simple algorithm for now. [Image: Wikipedia]

That's not particularly good news; for two matrices of size 10,000 $\times$ 10,000 (which is not particularly large in practice), this is 2 trillion operations (2 teraflops).

Question. What is the computational complexity of matrix-vector multiplication?

We know that matrix-vector multiplication requires $n$ inner products, each of size $n$.

So, matrix-vector multiplication requires

operations.

Order matters!¶

When you look at a mathematical expression involving matrices, think carefully about what it means and how you might efficiently compute it.

Example. What is the most efficient way to compute $A^{2}x$?

Here are your choices:

1. First compute $A^2$, then compute $\left(A^2\right)x$
2. First compute $Ax$, then compute $A\left(Ax\right)$

1. First compute $A^2$, then compute $\left(A^2\right)x$:

   • Complexity: $2n^3+2n^2$
   • Runtime for $n=10,000$ rows: about 2 Trillion flops

2. First compute $Ax$, then compute $A\left(Ax\right)$:

   • Complexity: $2\cdot 2n^2=4n^2$
   • Runtime for $n=10,000$ rows: 4 Million flops $✓$

Parallelization¶

Although matrix multiplication is computationally demanding, it has a wonderful property: it is highly parallel.

That is, the computation needed for each element does not require computing the other elements.

(This is not true, for example, for Gaussian elimination; think about the role of a pivot.)

This means that if we have multiple processors, and each has access to $A$ and $B$, the work can be divided up very cleanly.

For example, let's say you have $n$ processors. Then each processor can independently compute one column $A{b}_i$ of the result, without needing to know anything about what the other processors are doing.

Since all processors are working in parallel, the elapsed time is reduced from $2n^3$ down to $2n^2.$

Even better, say you have $n^2$ processors. Then each processor can compute a single element of the result, $(AB{)}_{ij}$ as ${\sum }_{k=1}^n{A}_{ik}{B}_{kj}$.

Then the elapsed time is reduced all the way down to $2n$.

This sort of strategy is used for huge computations like web search and weather modeling.

18.5 Computational Complexity of Matrix Inverse¶

Recall that a matrix $A$ is called invertible if there exists a matrix $C$ such that

In that case, $C$ is called the inverse of $A$. Inverses are only defined for square matrices.

Matrix inversion has many uses. For instance, if a matrix $A$ is invertible then we can solve the linear system by multiplying by $A^{-1}$ on the left. $$\begin{array}{}Ax& =b& A^{-1}\left(Ax\right)& =A^{-1}b& \left(A^{-1}A\right)x& =A^{-1}b& Ix& =A^{-1}b& x& =A^{-1}b\text{(and this solution is unique)}& \text{(5)}& \text{(6)}& \text{(7)}& \text{(8)}& \text{(9)}\end{array}$$

Python contains a function np.linalg.inv() that can compute the inverse of a square matrix of any size. For example:

Question: How would you write a computer program to perform this inverse operation? How long will it take to run?

In Lecture 5, we calculated a special formula for finding the inverse of a $2\times 2$ matrix.

We also found general algorithm for inverting any matrix. We can use Gaussian Elimination on the larger augmented matrix $[A\mid I]$. The result in reduced row echelon form will be $[I\mid A^{-1}]$.

We've seen how to calculate the cost of Gaussian elimination for

• An $n\times n$ square matrix $A$
• A column vector $b$.

Here, the augmented matrix is of size $n\times (n+1)$. For this matrix, let's consider the cost of performing an elementary row operation like adding a scalar multiple of row 1 into row 2. We need

• $n+1$ multiplications
• $n+1$ additions

So the total cost is $2(n+1)$ floating point operations (or flops).

As you perform more elimination steps, you can work with smaller sub-matrices. In total, we calculated in Lecture 3 that Gaussian elimination on $\left[A|b\right]$ costs

• $\frac{2}{3}{n}^3$ floating point operations for the Elimination stage
• $n^2$ floating point operations for the Backsubstitution stage

For matrix inversion, we need to use a larger augmented matrix $\left[A|I\right]$ whose size is $n\times 2n$. For this matrix, an elementary row operation now costs $2n$ multiplications and $2n$ additions, for a total of $4n$ flops.

If you go back to the derivation of the cost of Gaussian Elimination in Lecture 3 and recalculate the results for a wider augmented matrix $\left[A|I\right]$, you will find that the costs are now:

• $\frac{5}{3}{n}^3$ floating point operations for the Elimination stage
• $\frac{1}{3}{n}^3$ floating point operations for the Backsubstitution stage

As a result, the total cost to calculate the inverse is $2n^3$ flops. This is three times the cost of an ordinary Gaussian elimination.

Hence, if I give you a matrix $A$ then you can:

1. Calculate $A^{-1}$ at a cost of $2n^3$ flops and then be able to solve linear systems $Ax=b$ for any vector $b$ you receive in the future (at a cost of $2n^2$ flops each to perform the matrix-vector multiplication).
2. Solve a single linear system $Ax=b$ at a cost of $\frac{2}{3}{n}^3$ flops.

Which option is better depends on how linear systems you will solve using the same matrix $A$.

After break, we will find a new way to solve matrix operations that is the "best of both options": given a matrix $A$, you can perform a one-time cost of $\frac{2}{3}{n}^3$ flops and then quickly solve any matrix equation of the form $Ax=b$.