In [1]:

#
import numpy as np
import scipy as sp
import pandas as pd
import matplotlib as mp
import matplotlib.pyplot as plt
import seaborn as sns
import sklearn
import laUtilities as ut
import slideUtilities as sl
import demoUtilities as dm
from matplotlib import animation
from importlib import reload
from datetime import datetime
from IPython.display import Image, display_html, display, Math, HTML;
qr_setting = None

mp.rcParams['animation.html'] = 'jshtml';

Announcements¶

Homework 5 due Friday 3/17
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
Weekly reading and viewing assignments
- Aggarwal sections 2.6-2.7
- 3Blue1Brown video 7 and video 8

Lecture 20: LU Decomposition + Subspaces¶

A = \begin{array}{cc} [\begin{array}{cccc} 1 & 0 & 0 & 0 \\ * & 1 & 0 & 0 \\ * & * & 1 & 0 \\ * & * & * & 1 \end{array}] & [\begin{array}{ccccc} ◼ & * & * & * & * \\ 0 & ◼ & * & * & * \\ 0 & 0 & 0 & ◼ & * \\ 0 & 0 & 0 & 0 & 0 \end{array}] \\ L & U \end{array}

[This lecture is based on lecture notes from Prof. Crovella's CS 132 and the fast.ai numerical linear algebra course.]

Recap from last lecture¶

We calculated the computational cost of matrix operations in terms of floating point operations (flops)

Matrix inversion of an $n \times n$ square matrix takes $2 n^{3}$ operations -- this is three times the cost of Gaussian elimination.
Matrix multiplication is faster and nicely parallelizable.

We started the study of matrix factorizations

A factorization of a matrix $A$ is an equation that expresses $A$ as a product of two or more matrices $A = B C$ . Typically we want to factor a matrix $A$ into "simpler" matrices that make it easier to work with $A$ or expose important properties of $A$ .
The LU factorization problem states that: given matrices $A$ and $B$ , find a matrix $X$ such that $A X = B$ . If $X$ has $p$ columns, then this requires solving $p$ different linear systems that have the same $A$ matrix.

We looked at Gaussian elimination in a new way

We saw that every elementary row operation on $A$ is a linear transformation, and therefore can be performed by multiplying $A$ by a suitable matrix.
A simple way to compute an elementary matrix $E$ is to apply the row operation starting from the identity matrix $I$ .

Elementary matrices¶

Example: find the matrix $E$ that implements the operation 'add -4 times row 1 to row 3'

We can perform this transformation starting from $I$ : $[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}] \to [\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ - 4 & 0 & 1 \end{array}]$

We introduced our first factorization: $A = L U$ where

$U$ is in row echelon form, and it has the same $m \times n$ shape as $A$ . This is an upper triangular matrix (hence its name $U$ ).
$L$ is a lower triangular square matrix of size $m \times m$ , and it has 1s on the diagonal. This is called a unit lower triangular matrix (hence its name $L$ ).

A = \begin{array}{cc} [\begin{array}{cccc} 1 & 0 & 0 & 0 \\ * & 1 & 0 & 0 \\ * & * & 1 & 0 \\ * & * & * & 1 \end{array}] & [\begin{array}{ccccc} ◼ & * & * & * & * \\ 0 & ◼ & * & * & * \\ 0 & 0 & 0 & ◼ & * \\ 0 & 0 & 0 & 0 & 0 \end{array}] \\ L & U \end{array}

The fact that $U$ is in row echelon form may suggest to you (correctly!) that we could get it from $A$ by a sequence of row operations.

For now, let us suppose that:

We never need to interchange (or swap) two rows. Let's only consider the other two elementary operations.
The row reductions that convert $A$ to $U$ only add a multiple of one row to another row below it.

Now, if you consider an elementary matrix that implements such a row reduction, you will see that it will have 1s on the diagonal, and an additional entry somewhere below the diagonal.

For example, recall the scaling matrix $E_{2}$ and addition matrix $E_{3}$ from yesterday:

\begin{aligned} E_{2} = [\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 5 \end{array}], & E_{2} A = [\begin{array}{rrr} a & b & c \\ d & e & f \\ 5 g & 5 h & 5 i \end{array}], \\ E_{3} = [\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ - 4 & 0 & 1 \end{array}], & E_{3} A = [\begin{array}{rrr} a & b & c \\ d & e & f \\ g - 4 a & h - 4 b & i - 4 c \end{array}] . \end{aligned}

These elementary matrices are both unit lower triangular matrices! (We are ignoring row interchanges for now because they are not lower triangular. We'll deal with row interchanges later.)

So if there is a sequence of elementary row operations that convert $A$ to $U$ , then there is a set of unit lower triangular elementary matrices $E_{1}, \dots, E_{p}$ such that

E_{p} \dots E_{1} A = U .

We know that elementary matrices are invertible, and the product of invertible matrices is invertible, so:

A = (E_{p} \dots E_{1})^{- 1} U = L U

where $L = (E_{p} \dots E_{1})^{- 1}$ = $E_{1}^{- 1} \dots E_{p}^{- 1}$ . Remember: the inverse of a product equals the product of inverses, except in the opposite order.

Fact. The product of unit lower triangular matrices is unit lower triangular. Additionally, the inverse of a unit lower triangular matrix is unit lower triangular.

(Think about how to prove this statement on your own.)

So we can conclude that $L,$ as constructed from $(E_{p} \dots E_{1})^{- 1}$ , is unit lower triangular.

Hence, we have defined the LU decomposition based on Gaussian Elimination.

We have rewritten Gaussian Elimination as:

U = L^{- 1} A

and shown that the $L$ so defined is unit lower triangular.

Let's take stock of what this all means: the LU decomposition is a way of capturing the application of Gaussian Elimination to $A$ .

It incorporates both the process of performing Gaussian Elimination, and the result:

$U$ is the row echelon form of $A$ .
$L^{- 1}$ captures the row reductions that transform $A$ to row echelon form.
$L$ is the inverse of $L^{- 1}$ .

Recall that the motivation for developing the LU decomposition is that it is more efficient than matrix inversion. So we don't want to have to invert $L^{- 1}$ in the standard way in order to find $L$ .

Here we have some good news:

Inverting each elementary row operation is simple, in fact much easier than general matrix inversion. (We have already seen examples of this.)
Multiplying elementary row operations is also simple: just apply the elementary row operation indicated by the left matrix to the right matrix. Here are some examples:

\begin{array}{rcccl} E_{2}^{- 1} E_{3}^{- 1} & = & [\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 / 5 \end{array}] [\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 4 & 0 & 1 \end{array}] & = & [\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 4 / 5 & 0 & 1 / 5 \end{array}] \\ E_{3}^{- 1} E_{2}^{- 1} & = & [\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 4 & 0 & 1 \end{array}] [\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 / 5 \end{array}] & = & [\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 4 & 0 & 1 / 5 \end{array}] \end{array}

Once again, we can verify these calculations using Numpy.

In [4]:

E2inv = np.array([[1,0,0],[0,1,0],[0,0,1/5]])
E3inv = np.array([[1,0,0],[0,1,0],[4,0,1]])
print("E2inv * E3inv ="); print(E2inv @ E3inv)
print("\nE3inv * E2inv ="); print(E3inv @ E2inv)

E2inv * E3inv =
[[1.  0.  0. ]
 [0.  1.  0. ]
 [0.8 0.  0.2]]

E3inv * E2inv =
[[1.  0.  0. ]
 [0.  1.  0. ]
 [4.  0.  0.2]]

This gives the following algorithm for LU factorization:

Reduce $A$ to an echelon form $U$ by a sequence of row replacement operations.

This is just Gaussian Elimination! But: keep track of the elementary row operations you perform along the way.

Place entries in $L$ such that the same sequence of row operations reduces $L$ to $I$ .

If we can do this step efficiently, then the cost of LU factorization will be dominated by Gaussian Elimination itself.

The fact is that constructing $L$ can be done efficiently by a simple modification of Gaussian Elimination. So, LU decomposition takes time only $\frac{2}{3} n^{3} .$

20.1 Using the LU Factorization¶

Let's return to the motivation for developing the LU factorization.

We've seen that LU decomposition is essentially Gaussian Elimination, and as such, it doesn't take time much longer than Gaussian Elimination.

Now we want to show that, once you have the LU decomposition of a matrix $A = L U$ , then the system $A x = b$ can be solved for any $b$ in time that is proportional to $n^{2}$ .

Informally, what we are going to do is to use $L$ to do a special, very efficient version of the forward step of Gaussian Elimination, and then use $U$ in the usual way to do backsubstitution.

We can write these two steps concisely as follows:

When $A = L U$ , the equation $A x = b$ can be written as $L (U x) = b .$

Let's take this apart, and write $y$ for $U x$ . Then we can find $x$ by solving the pair of equations:

L y = b,

U x = y .

The idea is that we first solve $L y = b$ for $y,$ then solve $U x = y$ for $x .$

The key observation: each equation is fast to solve because $L$ and $U$ are each triangular.

Example. Given the following LU decomposition of $A$ :

A = [\begin{array}{rrrr} 3 & - 7 & - 2 & 2 \\ - 3 & 5 & 1 & 0 \\ 6 & - 4 & 0 & - 5 \\ - 9 & 5 & - 5 & 12 \end{array}] = [\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ - 1 & 1 & 0 & 0 \\ 2 & - 5 & 1 & 0 \\ - 3 & 8 & 3 & 1 \end{array}] [\begin{array}{rrrr} 3 & - 7 & - 2 & 2 \\ 0 & - 2 & - 1 & 2 \\ 0 & 0 & - 1 & 1 \\ 0 & 0 & 0 & - 1 \end{array}] = L U

use this LU factorization of $A$ to solve $A x = b$ , where $b = [\begin{array}{r} - 9 \\ 5 \\ 7 \\ 11 \end{array}] .$

Solution. To solve $L y = b,$ note that the arithmetic takes place only in the augmented column (column 5). The zeros below each pivot in $L$ are created automatically by the choice of row operations.

[L b] = [\begin{array}{rrrrr} 1 & 0 & 0 & 0 & - 9 \\ - 1 & 1 & 0 & 0 & 5 \\ 2 & - 5 & 1 & 0 & 7 \\ - 3 & 8 & 3 & 1 & 11 \end{array}] \sim [\begin{array}{rrrrr} 1 & 0 & 0 & 0 & - 9 \\ 0 & 1 & 0 & 0 & - 4 \\ 0 & 0 & 1 & 0 & 5 \\ 0 & 0 & 0 & 1 & 1 \end{array}] = [I y] .

Next, for $U x = y$ (the "backward" phase) the row reduction is again streamlined:

[U y] = [\begin{array}{rrrrr} 3 & - 7 & - 2 & 2 & - 9 \\ 0 & - 2 & - 1 & 2 & - 4 \\ 0 & 0 & - 1 & 1 & 5 \\ 0 & 0 & 0 & - 1 & 1 \end{array}] \sim [\begin{array}{rrrrr} 1 & 0 & 0 & 0 & 3 \\ 0 & 1 & 0 & 0 & 4 \\ 0 & 0 & 1 & 0 & - 6 \\ 0 & 0 & 0 & 1 & - 1 \end{array}] .

What we have done is:

Perform the forward step of Gaussian Elimination (but in a specially streamlined, efficient way)
Then perform the backwards (backsubstitution) step in the usual (efficient) fashion.

In [7]:

# image credit: Lay, 4th edition
display(Image("images/07-lu.jpeg", width=800))

Analysis. Both the forward and backward phases of solving a system as $L (U x) = b$ have flop counts of $\sim 2 n^{2}$ .

Therefore the time consuming step is actually doing the factorization, which as we've seen is essentially Gaussian Elimination, and therefore requires $\sim \frac{2}{3} n^{3}$ flops.

Hence we have found that by using the LU decomposition, one can solve a series of systems all involving the same $A$ in $\sim \frac{2}{3} n^{3}$ flops. By contrast:

Doing Gaussian Elimination would require $\sim \frac{2}{3} n^{3}$ flops for each of the $p$ linear systems.
Using the matrix inverse would require $\sim 2 n^{3}$ flops to invert the matrix.

Up until now we have assumed that the Gaussian Elimination we used to define $U$ only involves scalar multiplications or adding a multiple of a row to a row below it.

However, in real situations, we sometime need to exchange two rows.

One reason is, as we know, that if the current row has a zero in the pivot position, we need to exchange it with a row that does not have a zero in the pivot position.

[\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] \to [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}]

But there is another, more subtle reason having to do with numerical accuracy.

We make the following observation: in general, we would like to avoid dividing by a small number.

Here is why. Consider the problem of computing $a / b$ where $a$ and $b$ are scalars.

Let's say there is some small error in the value of $a$ , call it $ϵ .$

That means that what we are really computing is $(a + ϵ) / b = a / b + ϵ / b$ .

Note that $a / b$ is the correct value, but that what we compute is off by $ϵ / b$ . Now, if $b$ is a very small number, then the error in the result ( $ϵ / b$ ) will be large.

Hence we would like to avoid dividing by small numbers whenever possible.

Now: note that in performing Gaussian Elimination, we divide each row by the value of its pivot.

What this suggests is that we would like to avoid having small pivots.

For example, consider the matrix $\begin{array}{rcl} (1) & A & = & [\begin{matrix} 10^{- 20} & 1 \\ 1 & 1 \end{matrix}] \\ (2) & = & \underset{L}{\underset{⏟}{[\begin{matrix} 1 & 0 \\ 10^{20} & 1 \end{matrix}]}} \underset{U}{\underset{⏟}{[\begin{matrix} 10^{- 20} & 1 \\ 0 & - 10^{20} \end{matrix}]}} \end{array}$

This is a valid $L U$ decomposition. But it creates several large and small numbers, which as we know can lead to arithmetic errors. It would be better to interchange the two rows of A first and then perform $L U$ decomposition on that matrix.

\begin{array}{rcl} (3) & A^{'} & = & [\begin{matrix} 1 & 1 \\ 10^{- 20} & 1 \end{matrix}] \\ (4) & = & \underset{L}{\underset{⏟}{[\begin{matrix} 1 & 0 \\ 10^{- 20} & 1 \end{matrix}]}} \underset{U}{\underset{⏟}{[\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}]}} \end{array}

Note that this factorization is not quite correct! The bottom right entry is now $1 + 10^{- 20}$ rather than the correct value of $1$ . But this error will vanish in the computer's approximate addition anyway: remember that the computer only remembers numbers to 16 digits of precision. And this way we have only one really small number in our factorization, and no really large numbers.

This factorization is more stable, even if it is less accurate.

A stable algorithm gives nearly the right answer to nearly the right question (Trefethen, pg 104)

For instance, if we start with the matrix

A = [\begin{matrix} 10^{- 20} & 1 \\ 1 & 1 \end{matrix}]

then it is best to interchange the two rows because it's better to start with 1 as a pivot rather than $10^{- 20}$ .

Permutation Matrices¶

There is a simple way to address this. In processing any particular row, we can avoid having a small pivot by interchanging the current row with one of those below it.

We would like to exchange the current row with the row that has the largest absolute value of its pivot. This algorithmic technique is called "partial pivoting."

Now, a row interchange is an elementary row operation, and can be implemented by an elementary matrix. This elementary matrix is the identity with its corresponding rows interchanged.

An elementary matrix that exchanges rows is called a permutation matrix. The product of permutation matrices is a permutation matrix.

Hence, the net result of all the partial pivoting done during Gaussian Elimination can be expressed in a single permutation matrix $P$ .

This means that the final factorization of $A$ is:

A = P L U .

You can read this equation in three ways:

$A$ is the product of a unit lower triangular matrix $L$ and an echelon form matrix $U$ , and the rows of their product have been reordered according to the permulation $P$ . This is $A = P (L U) .$
$A$ is the product of a permuted lower triangular matrix $P L$ and an echelon form matrix $U$ . This is $A = (P L) U .$
There is a permuted version of $A$ that does factor into the product of lower and upper triangular matrices. Namely, $P^{⊤} A = L U$ ,

$P^{T} P = I$ , so $P^{T} = P^{- 1}$

Vector Subspace and Basis¶

In [2]:

#
fig = ut.three_d_figure((0,0), fig_desc = 'H = Span{a1, a2, a3}',
                        xmin = -10, xmax = 10, ymin = -10, ymax = 10, zmin = -10, zmax = 10, qr = qr_setting)
a1 = [-8.0, 8.0, 5.0]
a2 = [3.0,  2.0, -2.0]
a3 = 2.5 * np.array(a2)
fig.text(a1[0]+.5, a1[1]+.5, a1[2]+.5, r'$\bf a_1$', 'a_1', size=18)
fig.text(a3[0]+.5, a3[1]+.5, a3[2]+.5, r'$\bf a_3$', 'a_3', size=18)
fig.text(a2[0]+.5, a2[1]+.5, a2[2]+.5, r'$\bf a_2$', 'a_2', size=18)
fig.plotSpan(a1, a2,'Green')
fig.plotPoint(a1[0], a1[1], a1[2],'r')
fig.plotPoint(a3[0], a3[1], a3[2],'r')
fig.plotPoint(a2[0], a2[1], a2[2],'r')
fig.plotLine([[0, 0, 0], a3], 'r', '--')
fig.plotLine([[0, 0, 0], a1], 'r', '--')
# fig.plotPoint(a3[0], a3[1], a3[2],'r')
fig.text(0.1, 0.1, -3, r'$\bf 0$', '0', size=12)
fig.plotPoint(0, 0, 0, 'b')
# fig.set_title(r'$H$ = Span$\{{\bf a}_1, {\bf a}_2, {\bf a}_3\}$')
fig.text(9, -9, -7, r'H', 'H', size = 16)
img = fig.dont_save()

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

20.3 The Invertible Matrix Theorem¶

We have seen in this course that invertible matrices are "nicer" to work with when solving systems of linear equations. For instance, if a matrix $A$ is invertible, then $A x = b$ has a unique solution for any $b$ .

This suggests a deep connection between the invertibility of $A$ and the nature of the linear system $A x = b .$

In fact, we are now at the point where we can collect together in a fairly complete way much of what we have learned about matrices and linear systems.

This remarkable collection of ten interrelated properties is called the Invertible Matrix Theorem (IMT). (And we will grow this list further in future lectures.)

Invertible Matrix Theorem. Let $A$ by a square $n \times n$ matrix.

Then the following statements are equivalent; that is, they are either all true or all false.

$A$ is an invertible matrix.

$A^{T}$ is an invertible matrix.
- Proof by direct construction: $(A^{T})^{- 1} = (A^{- 1})^{T} .$

The equation $A x = b$ has a unique solution for each $b$ in $R^{n} .$
- We saw in a previous lecture that the solution is $x = A^{- 1} b$ .

A is row equivalent to the identity matrix.
- If $A x = b$ has a unique solution for any $b,$ then the reduced row echelon form of $A$ is $I$ .

A has $n$ pivot positions.
- Follows directly from the previous statement.

The homogeneous equation $A x = 0$ has only the trivial solution.
- If $A x = b$ has a unique solution for any $b,$ then the unique solution for $b = 0$ must be $0.$

The columns of $A$ form a linearly independent set.
- Follows directly the previous statement and the definition of linear independence.

The columns of $A$ span $R^{n} .$
- For any $b \in R^{n},$ there is a set of coefficients $x$ which can be used to construct $b$ from the columns of $A .$

The linear transformation $x \mapsto A x$ maps $R^{n}$ onto $R^{n} .$
- Follows directly from the previous statement.

The linear transformation $x \mapsto A x$ is one-to-one.
- Follows directly from the fact that $A x = b$ has a unique solution for any $b .$

We provided arguments above to show that if $A$ is invertible, then all the other statements are true.

In fact, the converse holds as well: if $A$ is not invertible, then all the other statements are false. We will skip the proof of the converse, but it's not difficult.

The Invertible Matrix Theorem has wide-ranging implications.

It divides the set of all $n \times n$ matrices into two disjoint classes:

the invertible (nonsingular) matrices, and
the noninvertible (singular) matrices.

The power of the IMT lies in the connections it provides among so many important concepts.

For example, notice how it connects linear independence of the columns of a matrix $A$ to the existence of solutions to equations of the form $A x = b .$

This allows us to bring many tools to bear as needed to solve a problem.

Example. Let $A = [\begin{array}{rr} 3 & 7 \\ - 6 & - 14 \end{array}]$ .

Decide if $A x = b$ has a solution for all $b$ ... or in other words if the linear transformation defined by $A$ is onto.

Solution. The determinant of $A$ is $(3 \cdot - 14) - (7 \cdot - 6) = 0$ .

So $A$ is not invertible, so $A x = b$ does not have a solution for all $b$ .

Example. Decide if $A$ is invertible:

A = [\begin{array}{rrr} 1 & 0 & - 2 \\ 3 & 1 & - 2 \\ - 5 & - 1 & 9 \end{array}] .

(If we knew the determinant of $A$ , then we could decide whether it is invertible by checking if $det (A) \neq 0$ . But we don't yet know how to take the determinant of a $3 \times 3$ matrix.)

Solution.

A \sim [\begin{array}{rrr} 1 & 0 & - 2 \\ 0 & 1 & 4 \\ 0 & - 1 & - 1 \end{array}] \sim [\begin{array}{rrr} 1 & 0 & - 2 \\ 0 & 1 & 4 \\ 0 & 0 & 3 \end{array}] .

$A$ has three pivot positions and hence is invertible, by the IMT.

Note. Keep in mind: while the IMT is quite powerful, it does not completely settle issues that arise with respect to $A x = b .$

This is because it only applies to square matrices.

So if $A$ is nonsquare, then we can't use the IMT to conclude anything about the existence or nonexistence of solutions to $A x = b .$

Invertible Linear Transformations¶

A linear transformation $T : R^{n} \to R^{n}$ is invertible if there exists a function $S : R^{n} \to R^{n}$ such that

S (T (x)) = x for all x \in R^{n},

and

T (S (x)) = x for all x \in R^{n} .

Theorem. Let $T : R^{n} \to R^{n}$ be a linear transformation and let $A$ be the standard matrix for $T$ . Then,

$T$ is invertible if and only if $A$ is an invertible matrix.
In that case, the linear transformation $S$ given by $S (x) = A^{- 1} x$ is the unique function satisfying the definition.

Let's look at some invertible and non-invertible linear transformations.

Example. Here is a horizontal contraction

A = [\begin{array}{rr} 0.5 & 0 \\ 0 & 1 \end{array}] .

In [9]:

#
square = np.array([[0.0,1,1,0],[1,1,0,0]])
A = np.array(
    [[0.5, 0], 
     [  0, 1]])
# print("A ="); print(A)
dm.plotSetup()
dm.plotSquare(square)
dm.plotSquare(A @ square,'r')
# Latex(r'Horizontal Contraction')

Its determinant is $1 (0.5) - 0 (0) = 0.5,$ so this linear transformation is invertible. Its inverse is:

\frac{1}{0.5} [\begin{array}{rr} 1 & 0 \\ 0 & 0.5 \end{array}] = [\begin{array}{rr} 2 & 0 \\ 0 & 1 \end{array}] .

Clearly, just as $A$ contracted the $x_{1}$ direction by 0.5, $A^{- 1}$ will expand the $x_{1}$ direction by 2.

Example. Consider the projection onto the $x_{2}$ axis

A = [\begin{array}{rr} 0 & 0 \\ 0 & 1 \end{array}] .

The determinant of $A$ is zero, so this linear transformation is not invertible.

In [10]:

#
A = np.array(
    [[0,0],
     [0,1]])
print("A = "); print(A)
ax = dm.plotSetup()
dm.plotSquare(square)
dm.plotSquare(A @ square)
ax.arrow(1.0,1.0,-0.9,0,head_width=0.15, head_length=0.1, length_includes_head=True);
ax.arrow(1.0,0.0,-0.9,0,head_width=0.15, head_length=0.1, length_includes_head=True);

A = 
[[0 0]
 [0 1]]

By the IMT, there are many equivalent ways to look at this:

The mapping $T$ is not onto $R^{2} .$ (Only a subset of $R^{2}$ can be output by $T$ ).
The mapping $T$ is not one-to-one. (There are many values $x$ that give the same $A x .$ )
$A$ does not have 2 pivots.
The columns of $A$ do not span $R^{2} .$
$A x = 0$ has a non-trivial solution.

Announcements¶

Lecture 20: LU Decomposition + Subspaces¶

Recap from last lecture¶

Elementary matrices¶

Finding $L$ ¶

20.1 Using the LU Factorization¶

20.2 Pivoting¶

Permutation Matrices¶

Vector Subspace and Basis¶

20.3 The Invertible Matrix Theorem¶

Invertible Linear Transformations¶

Announcements¶

Lecture 20: LU Decomposition + Subspaces¶

Recap from last lecture¶

Elementary matrices¶

Finding LL¶

20.1 Using the LU Factorization¶

20.2 Pivoting¶

Permutation Matrices¶

Vector Subspace and Basis¶

20.3 The Invertible Matrix Theorem¶

Invertible Linear Transformations¶

Finding $L$ ¶