Announcements¶

• Homework 4 is out, due 3/3

• Upcoming office hours

  • Today: Prof McDonald from 4:30-6pm in CCDS 1341
  • Tomorrow: Peer tutor Rohan Anand from 1:30-3pm in CCDS 16th floor

• Aggarwal Section 2.4-2.5

• Watch 3Blue1Brown video 5 and video 6

Lecture 17: Matrix Composition¶

[This lecture is based on Prof. Crovella's CS 132 lecture notes.]

Recap of the previous lecture¶

Last time, we discussed a geometric interpretation of matrix-vector multiplication $Ax=b$.

We think of $A$ as a linear transformation that maps the vector $x$ in the domain into a new vector $b$ in the co-domain. The resulting vector $b$ is called the image of $x$ under the transformation $A$.

We saw some example transformations like the horizontal shear matrix $A=\left[\begin{array}{cc}1& 1.5\\ 0& 1\end{array}\right]$.

To understand how matrices transform space, it suffices to understand how the matrix transforms the standard basis vectors $e_1=\left[\begin{array}{c}1\\ 0\end{array}\right]$ and $e_2=\left[\begin{array}{c}0\\ 1\end{array}\right]$, along with the unit square containing them.

Then, we can understand how the matrix applies to all of $R^2$ using the principle of linearity.

Definition. A transformation $T$ is linear if:

for all $u,v$ in the domain of $T$ and for all scalars $c,d\in R$.

We proved last time that the ideas of matrix multiplication and linear transformation of vector spaces are equivalent.

• Multiplying by an $m\times n$ matrix $A$ always produces a linear transformation from $R^n$ to $R^m$.
• Every linear transformation $T$ from vectors to vectors is equivalent to multiplication by the matrix $A=\left[T\right(e_1)\dots T(e_n\left)\right]$.

Then, we found the matrix corresponding to several linear transformations of 2-dimensional space. For example, the act of rotating counterclockwise by $\theta =90$ degrees corresponds to the matrix $A=\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]$.

17.1 Visualizing Linear Transformations of $R^2$¶

Let's examine several linear transformations of $R^2$ to $R^2$, both geometrically and computationally.

Rotation¶

Let $T:R^2\to R^2$ be the transformation that rotates each point in $R^2$ about the origin through an angle $\theta$, with counterclockwise rotation for a positive angle.

Let's find the standard matrix $A$ of this transformation.

Question. The columns of $I$ are $e_1=\left[\begin{array}{c}1\\ 0\end{array}\right]$ and $e_2=\left[\begin{array}{c}0\\ 1\end{array}\right].$ Where does $T$ map the standard basis vectors?

Referring to the diagram below, we can see that $\left[\begin{array}{c}1\\ 0\end{array}\right]$ rotates into $\left[\begin{array}{c}\cos \theta \\ \sin \theta \end{array}\right],$ and $\left[\begin{array}{c}0\\ 1\end{array}\right]$ rotates into $\left[\begin{array}{c}-\sin \theta \\ \cos \theta \end{array}\right].$

So by the Theorem above,

In particular, a 90 degree counterclockwise rotation corresponds to the matrix

Dilation¶

First, let's recall the linear transformation

With $r>1$, this is a dilation. It moves every vector further from the origin.

Let's say the dilation is by a factor of $r=2.5$.

To construct the matrix $A$ that implements this transformation, we ask: where do $e_1$ and $e_2$ go?

Under the action of $A$, $e_1$ goes to $\left[\begin{array}{c}2.5\\ 0\end{array}\right]$ and $e_2$ goes to $\left[\begin{array}{c}0\\ 2.5\end{array}\right]$.

So the matrix $A$ must be $\left[\begin{array}{cc}2.5& 0\\ 0& 2.5\end{array}\right]$. Let's see this visually.

Reflections¶

OK, now let's reflect through the $x_1$ axis. Where do $e_1$ and $e_2$ go?

What about reflection through the $x_2$ axis?

What about reflection through the line $x_1=x_2$?

What about reflection through the line $x_1=-x_2$?

Other transformations¶

What about 180-degree rotation through the origin? Note that this is different than reflection about the line $x_1=-x_2$ (how?).

We could use our rotation formula to compute this matrix, but let's instead just think about how this transformation affects $e_1$ and $e_2$.

We can expand or shrink one dimension independent of the other. Suppose we want to contract the $x_1$ dimension by a ratio of $r=0.45$, but leave the $x_2$ axis unchanged. What matrix performs this operation?

We can similarly construct a horizontal expansion by a ratio of $r=2.5$.

Matrices of the form $\left[\begin{array}{cc}1& a\\ 0& 1\end{array}\right]$ or $\left[\begin{array}{cc}1& 0\\ a& 1\end{array}\right]$ are called shears.

We have already seen a horizontal shear. Here is a vertical shear.

Now let's look at a particular kind of transformation called a projection.

Imagine we took any given point and 'dropped' it onto the $x_1$-axis.

Question. What happens to the shape of the point set? What about its area?

Here is a projection in the $x_2$ axis.

17.2 Existence and Uniqueness¶

Notice that some of these transformations map multiple inputs to the same output, and some are incapable of generating certain outputs.

For example, the projections above can send multiple different points to the same point.

We need some terminology to understand these properties of linear transformations.

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.

Another (important) way of thinking about this is that $T$ is onto if there is a solution $x$ of

for all possible $b.$

This is asking an existence question about a solution of the equation $T\left(x\right)=b$ for all $b.$

Question. For the transformation $T$ pictured below, is $T$ onto?

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$.

Examples¶

Consider the following two transformations (a reflection and a projection). In each case, the red points are the images of the blue points. Is each transformation onto $R^2$?

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$.

If $T$ is one-to-one, then for each $b,$ the equation $T\left(x\right)=b$ has either a unique solution, or none at all. This is asking an existence question about a solution of the equation $T\left(x\right)=b$ for all $b$.

Relationship to consistency¶

Let's examine the relationship between these ideas and some previous definitions.

Question. If the equation $Ax=b$ is consistent (i.e., has at least one solution) for all $b$, is $T\left(x\right)=Ax$ onto? Is it one-to-one?

• $T\left(x\right)$ is onto.
• $T\left(x\right)$ may or may not be one-to-one. If the system has multiple solutions for some $b$, $T\left(x\right)$ is not one-to-one.

Question. If $Ax=b$ is consistent and has a unique solution for all $b$, is $T\left(x\right)=Ax$ onto? Is it one-to-one?

• Yes to both.

Question. If $Ax=b$ is not consistent for all $b$, is $T\left(x\right)=Ax$ onto? one-to-one?

• $T\left(x\right)$ is not onto.
• $T\left(x\right)$ may or may not be one-to-one.

Questions. (Think about these on your own.)

• If $T\left(x\right)=Ax$ is onto, is $Ax=b$ consistent for all $b$? is the solution unique for all $b$?

• If $T\left(x\right)=Ax$ is one-to-one, is $Ax=b$ consistent for all $b$? is the solution unique for all $b$?

17.3 Area is Scaled by the Determinant¶

Notice that in some of the transformations above, the "size" of a shape grows or shrinks.

Let's look at how area (or volume) of a shape is affected by a linear transformation.

Thanks to linearity, it suffices to ask what happens to the unit square (or cube, or hypercube). All other areas or volumes will scale similarly.

Let's denote the matrix of a general 2-dimensional linear transformation as:

Then, here is what happens to the unit square:

Now, let's determine the area of the blue diamond in terms of $a,b,c$, and $d$.

To do that, we'll use this diagram:

Each of the triangles and rectangles has an area we can determine in terms of $a,b,c$ and $d$.

• The large rectangle has sides $(a+b)$ and $(c+d)$, so its area is $(a+b)(c+d)$.
• We need to subtract $bd$ (red triangles), $ac$ (gray triangles), and $2bc$ (green rectangles).

So the area of the blue diamond is:

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]$,

The determinant can be defined for any $n\times n$ square matrix. For a square matrix $A$ larger than $2\times 2$, the determinant tells us how the volume of a unit (hyper)cube is scaled when it is linearly transformed by $A$.

We will see how to compute these determinants in a later lecture.

For non-square matrices, the determinant is not defined because we aren't scaling the area of a shape; we are moving it to a different space entirely.

Zero determinant¶

A special case to consider is when the determinant of a matrix is zero.

Question. When does it happen that $det\left(A\right)=0$?

Consider when $A$ is the matrix of a projection.

The unit square has been collapsed onto the $x$-axis, resulting in a shape with area of zero.

This is confirmed by the determinant, which is

17.4 Inverse of a matrix¶

Next, we investigate the idea of the "inverse" of a matrix. It is analogous to inverses of real numbers, where each non-zero number $r$ has a multiplicative inverse $r^{-1}$ such that $r\cdot r^{-1}=1$.

This inverse does not exist for all matrices.

• It only exists for square matrices (why?)
• And not even for all square matrices.

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.

Example. As in the previous 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 $B$ is the inverse of $A$.

We know that $AB$ corresponds to performing a 270 degree rotation $T_{270}$ followed by a 90 degree rotation $T_{90}$. The result is a 360 degree rotation -- that is, every vector ends up back where it started, which is the identity transformation. Hence, $AB=I$.

Similarly, $BA$ corresponds to performing a 90 degree rotation followed by a 270 degree rotation, so once again the result $BA=I$ is the identity matrix.

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.

(I will let you verify these properties on your own.)

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}.$

17.6 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.

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}]$.

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: