This is the sixth post in an article series about MIT’s course “Linear Algebra”. In this post I will review lecture six on column spaces and null spaces of matrices. The lecture first reviews vector spaces and subspaces and then looks at the result of intersect and union of vector subspaces, and finds out when Ax=b and Ax=0 can be solved.

Here is a list of the previous posts in this article series:

• Lecture 1: Geometry of Linear Equations
• Lecture 2: Elimination with Matrices
• Lecture 3: Matrix Multiplication and Inverse Matrices
• Lecture 4: A=LU Factorization
• Lecture 5: Vector Spaces and Subspaces

Lecture 6: Column Space and Null Space

Lecture six starts with a reminder of what the vector space requirements are. If vectors v and w are in the space, then the result of adding them and multiplying them by a number stays in the space. In other words, all linear combinations of v and w stay in the space.

For example, the 3-dimensional space R³ is a vector space. You can take any two vectors in it, add them, and multiply them by a number and they will still be in the same R³ space.

Next, the lecture reminds subspaces. A subspace of some space is a set of vectors (including the 0 vector) that satisfies the same two requirements. If vectors v and w are in the subspace, then all linear combinations of v and w are in the subspace.

For example, some subspaces of R³ are:

• Any plane P through the origin (0, 0, 0).
• Any line L through the origin (0, 0, 0).

See the previous, lecture 5, on more examples of spaces on subspaces.

Now suppose we have two subspaces of R³ - plane P and line L. Is the union P∪L a subspace? No. Because if we take some vector in P and some vector in L and add them together, we go outside of P and L and that does not satisfy the requirements of a subspace.

What about intersection P∩L? Is P∩L a subspace? Yes. Because it’s either the zero vector or L.

In general, given two subspaces S and T, union S∪T is a not a subspace and intersection S∩T is a subspace.

The lecture now turns to column spaces of matrices. The notation for a column space of a matrix A is C(A).

For example, given this matrix,

The column space C(A) is all the linear combination of the first (1, 2, 3, 4), the second (1, 1, 1, 1) and the third column (2, 3, 4, 5). That is, C(A) = { a·(1, 2, 3, 4) + b·(1, 1, 1, 1) + c·(2, 3, 4, 5) }. In general, the column space C(A) contains all the linear combinations of columns of A.

A thing to note here is that C(A) is a subspace of R⁴ because the vectors contain 4 components.

Now the key question, does C(A) fill the whole R⁴? No. Because there are only three columns (to fill the whole R⁴ we would need exactly 4 columns) and also because the third column (2, 3, 4, 5) is a sum of first column (1, 2, 3, 4) and second column (1, 1, 1, 1).

From this question follows another question, the most important question in the lecture - Does Ax=b have a solution for every right-hand side vector b? No. Because the columns are not linearly independent (the third can be expressed as first+second)! Therefore the column space C(A) is actually a two-dimensional subspace of R⁴.

Another important question arises - For which right-hand sides b can this system be solved? The answer is: Ax=b can be solved if and only if b is in the column space C(A)! It’s because Ax is a combination of columns of A. If b is not in this combination, then there is simply no way we can express it as a combination.

That’s why we are interested in column spaces of matrices. They show when can systems of equation Ax=b be solved.

Now the lecture turns to null spaces of matrices. The notation for a null space of a matrix A is N(A).

Let’s keep the same matrix A:

The null space N(A) contains something completely different than C(N). N(A) contains all solutions x’s that solve Ax=0. In this example, N(A) is a subspace of R³.

Let’s find the null space of A. We need to find all x’s that solve Ax=0. The first one, obviously, is x = (0, 0, 0). Another one is x = (1, 1, -1). In general all x’s (c, c, -c) solve Ax=0. The vector (c, c, -c) can be rewritten as c·(1, 1, -1).

Note that the null space c·(1, 1, -1) is a line in R³.

The lecture ends with a proof that solutions x to Ax=0 always give a subspace. The first thing to show in the proof is that if x is a solution and x’ is a solution, then their sum x + x’ is a solution:

We need to show that if Ax=0 and Ax’ = 0 then A(x + x’) = 0. This is very simple. Matrix multiplication allows to separate A(x + x’) into Ax + Ax’ = 0. But Ax=0 and Ax’=0. Therefore 0 + 0 = 0.

The second thing to show is that if x is a solution, then c·x is a solution:

We need to show that if Ax=0 then A(c·x)=0. This is again very simple. Matrix multiplication allows to bring c from A(c·x) outside c·A(x) = c·0 = 0.

That’s it. We have proven that solutions x to Ax=0 always form a subspace.

Here is the video of the sixth lecture:

Topics covered in lecture six:

• [01:00] Vector space requirements.
• [02:10] Example of spaces R³.
• [02:40] Subspaces of spaces.
• [03:00] A plane P is a subspace of R³.
• [03:50] A line L is a subspace of R³.
• [04:40] Union of P and L.
• [07:30] Intersection of P and L.
• [09:00] Intersection of two subspaces S and T.
• [11:50] The column space C(A) of a matrix A.
• [16:20] Does Ax=b have a solution for every b?
• [19:45] Which b’s allow Ax=b to be solved?
• [23:50] Can solve Ax=b exactly when b is in C(A).
• [28:50] The null space N(A) of a matrix A.
• [37:00] Why is the null space a vector space?
• [37:30] A proof that the null space is always a vector space.
• [41:50] Do the solutions to Ax=b form a subspace?

Here are my notes of lecture six:

My notes of linear algebra lecture 6 on column space and null space.

Have fun with this lecture! The next post is going to be about general theory of solving equations Ax=0, pivot variables and special solutions.

PS. This course is taught from Introduction to Linear Algebra textbook. Get it here:

This is the fifth post in an article series about MIT’s course “Linear Algebra”. In this post I will review lecture five that finally introduces real linear algebra topics such as vector spaces their subspaces and spaces from matrices. But before it does that it closes the topics that were started in the previous lecture on permutations, transposes and symmetric matrices.

Here is a list of the previous posts in this article series:

• Lecture 1: Geometry of Linear Equations
• Lecture 2: Elimination with Matrices
• Lecture 3: Matrix Multiplication and Inverse Matrices
• Lecture 4: A=LU Factorization

Lecture 5: Vector Spaces and Subspaces

Lecture starts with reminding some facts about permutation matrices. Remember from the previous lecture that permutation matrices P execute row exchanges and they are identity matrices with reordered rows.

Let’s count how many permutation matrices are there for an nxn matrix.

For a matrix of size 1x1, there is just one permutation matrix - the identity matrix.

For a matrix of size 2x2 there are two permutation matrices - the identity matrix and the identity matrix with rows exchanged.

For a matrix of size 3x3 we may have the rows of the identity matrix rearranged in 6 ways - {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}.

For a matrix of size 4x4 the number of ways to reorder the rows is the same as the number of ways to rearrange numbers {1,2,3,4}. This is the simplest possible combinatorics problem. The answer is 4! = 24 ways.

In general, for an nxn matrix, there are n! permutation matrices.

Another key fact to remember about permutation matrices is that their inverse P^-1 is their transpose P^T. Or algebraically P^T·P = I.

The lecture proceeds to transpose matrices. The transpose of a matrix exchanges its columns with rows. Another way to think about it that it flips the matrix over its main diagonal. Transpose of matrix A is denoted by A^T.

Here is an example of transpose of a 3-by-3 matrix. I color coded the columns to better see how they get exchanged:

A matrix does not have to be square for its transpose to exist. Here is another example of transpose of a 3-by-2 matrix:

In algebraic notation transpose is expressed as (A^T)_ij = A_ji, which says that an element a_ij at position ij get transposed into the position ji.

Here are the rules for matrix transposition:

• The transpose of A + B is (A + B)^T = A^T + B^T.
• The transpose of A·B is (A·B)^T = B^T·A^T.
• The transpose of A·B·C is (A·B·C)^T = C^T·B^T·A^T.
• The transpose of A^-1 is (A^-1)^T = (A^T)^-1.

Next the lecture continues with symmetric matrices. A symmetric matrix has its transpose equal to itself, i.e., A^T = A. It means that we can flip the matrix along the diagonal (transpose it) but it won’t change.

Here is an example of a symmetric matrix. Notice that the elements on opposite sides of the diagonal are equal:

Now check this out. If you have a matrix R that is not symmetric and you multiply it with its transpose R^T as R·R^T, you get a symmetric matrix! Here is an example:

Are you wondering why it’s true? The proof is really simple. Remember that matrix is symmetric if its transpose is equal to itself. Now what’s the transpose of the product R·R^T? It’s (R·R^T)^T = (R^T)^T·R^T = R·R^T - it’s the same product, which means that R·R^T is always symmetric.

Here is another cool fact - the inverse of a symmetric matrix (if it exists) is also symmetric. Here is the proof. Suppose A is symmetric, then the transpose of A^-1 is (A^-1)^T = (A^T)^-1. But A^T = A, therefore (A^T)^-1 = A^-1.

At this point lecture finally reaches the fundamental topic of linear algebra - vector spaces. As usual, it introduces the topic by examples.

Example 1: Vector space R² - all 2-dimensional vectors. Some of the vectors in this space are (3, 2), (0, 0), (π, e) and infinitely many others. These are all the vectors with two components and they represent the xy plane.

Example 2: Vector space R³ - all vectors with 3 components (all 3-dimensional vectors).

Example 3: Vector space Rⁿ - all vectors with n components (all n-dimensional vectors).

What makes these vectors vector spaces is that they are closed under multiplication by a scalar and addition, i.e., vector space must be closed under linear combination of vectors. What I mean by that is if you take two vectors and add them together or multiply them by a scalar they are still in the same space.

For example, take a vector (1,2,3) in R³. If we multiply it by any number α, it’s still in R³ because α·(1,2,3) = (α, 2α, 3α). Similarly, if we take any two vectors (a, b, c) and (d, e, f) and add them together, the result is (a+d, b+e, f+c) and it’s still in R³.

There are actually 8 axioms that the vectors must satisfy for them to make a space, but they are not listed in this lecture.

Here is an example of not-a-vector-space. It’s 1/4 of R² (the 1st quadrant). The green vectors are in the 1st quadrant but the red one is not:

An example of not-a-vector-space.

This is not a vector space because the green vectors in the space are not closed under multiplication by a scalar. If we take the vector (3,1) and multiply it by -1 we get the red vector (-3, -1) but it’s not in the 1st quadrant, therefore it’s not a vector space.

Next, Gilbert Strang introduces subspaces of vector spaces.

For example, any line in R² that goes through the origin (0, 0) is a subspace of R². Why? Because if we take any vector on the line and multiply it by a scalar, it’s still on the line. And if we take any two vectors on the line and add them together, they are also still on the line. The requirement for a subspace is that the vectors in it do not go outside when added together or multiplied by a number.

Here is a visualization. The blue line is a subspace of R² because the red vectors on it can’t go outside of line:

An example of subspace of R².

And example of not-a-subspace of R² is any line that does not go through the origin. If we take any vector on the line and multiply it by 0, we get the zero vector, but it’s not on the line. Also if we take two vectors and add them together, they are not on the line. Here is a visualization:

An example of not-a-subspace of R².

Why not list all the subspaces of R². They are:

• the R² itself,
• any line through the origin (0, 0),
• the zero vector (0, 0).

And all the subspaces of R³ are:

• the R³ itself,
• any line through the origin (0, 0, 0),
• any plane through the origin (0, 0, 0),
• the zero vector.

The last 10 minutes of the lecture are spent on column spaces of matrices.

The column space of a matrix is made out of all the linear combinations of its columns. For example, given this matrix:

The column space C(A) is the set of all vectors {α·(1,2,4) + β·(3,3,1)}. In fact, this column space is a subspace of R³ and it forms a plane through the origin.

More about column spaces in the next lecture.

You’re welcome to watch the video lecture five:

Topics covered in lecture five:

• [01:30] Permutations.
• [03:00] A=LU elimination without row exchanges.
• [03:50] How Matlab does A=LU elimination.
• [04:50] PA=LU elimination with row exchanges
• [06:40] Permutation matrices.
• [07:25] How many permutation matrices are there?
• [08:30] Permutation matrix properties.
• [10:30] Transpose matrices.
• [11:50] General formula for transposes: (A^T)_ij = A_ji.
• [13:06] Symmetric matrices.
• [13:30] Example of a symmetric matrix.
• [15:15] R·R^T is always symmetric.
• [18:23] Why is R·R^T symmetric?
• [20:50] Vector spaces.
• [22:05] Examples of vector spaces.
• [22:55] Real vector space R².
• [23:20] Picture of R² - xy plane.
• [26:50] Vector space R³.
• [28:00] Vector space Rⁿ.
• [30:00] Example of not a vector space.
• [32:00] Subspaces of vector spaces.
• [33:00] A vector space inside R².
• [34:35] A line in R² that is subspace.
• [34:50] A line in R² that is not a subspace.
• [36:30] All subspaces of R².
• [39:30] All subspaces of R³.
• [40:20] Subspaces of matrices.
• [41:00] Column spaces of matrices C(A).
• [44:10] Example of column space of matrix with columns in R³.

Here are my notes of lecture five:

My notes of linear algebra lecture 5 on vector spaces and subspaces.

Have fun with this lecture! The next post is going to be more about column spaces and null spaces of matrices.

PS. This course is taught from Introduction to Linear Algebra textbook. Get it here:

This is the fourth post in an article series about MIT’s course “Linear Algebra”. In this post I will review lecture four on factorizing a matrix A into a product of a lower-triangular matrix L and an upper-triangular matrix U, or in other words A=LU. The lecture also shows how to find the inverse of matrix product A·B, how to find the inverse of transposed matrix A^T, and introduces permutation matrices.

Here are the previous lectures:

• Lecture 1: Geometry of Linear Equations
• Lecture 2: Elimination with Matrices
• Lecture 3: Matrix Multiplication and Inverse Matrices

Lecture 4: A=LU Factorization

Lecture four starts with a small review of inverse matrices. Remember from previous lecture that the inverse of matrix A is matrix A^-1 such that multiplying them together A·A^-1 produces the identity matrix I.

Another key fact to remember is that matrix multiplication is associative (can change parenthesis) and that for square matrices the right-inverse is also the left-inverse A·A^-1 = A^-1·A = I.

Lecture then continues with finding the inverse of matrix product A·B. The answer is found by reasoning what should we multiply A·B to get the identity matrix. Let’s try B^-1·A^-1. If this is the inverse of A·B, then multiplying it with A·B from the left and right sides should produce the identity matrix I. Let’s test this.

From the right side: (A·B)·(B^-1·A^-1). Since we can rearrange parenthesis, this is the same as A·(B·B^-1)·A^-1. But B·B^-1 is identity, therefore A·(B·B^-1)·A^-1 = A·I·A^-1 = A·A^-1 = I. Seems good so far.

Now the left side: (B^-1·A^-1)·(A·B). We rearrange parenthesis again, B^-1·(A^-1·A)·B and just like in the previous example, A^-1·A is identity and B^-1·I·B is B^-1·B = I.

We have found the inverse of (A·B). It’s (B^-1·A^-1).

Next, while we’re at it, the lecture continues with finding the inverse of transposed matrix A^T. It’s found by reasoning again. Let’s first look at the equation A·A^-1 = I. We can transpose both sides of this equation and it will still hold. If we transpose the right side, we get the same identity matrix I, because I^T=I. But what about the left-hand side? Transposing the left-hand side we get (A·A^-1)^T = (A^-1)^T·A^T. Now left-hand side is still equal to right-hand side, therefore (A^-1)^T·A^T = I. But from this equation it’s instantly obvious that the inverse of A^T is (A^-1)^T.

We can therefore note and remember that (A^T)^-1 = (A^-1)^T.

Finally the lecture moves on to today’s key topic of A=LU decomposition. As usual, the topic is introduced by an example.

Let’s take a look at this 2x2 matrix A:

And let’s try to find the elementary matrix E₂₁ that will eliminate the element at row 2, column 1. Multiplying the first row by 4 and subtracting it from the second row will produce a zero at 2, 1.

But look at the right-hand side. It’s the upper-triangular matrix U (all elements below the diagonal are 0) that we were looking for!

Now if we multiply both sides by the inverse of E₂₁, we get (E₂₁)^-1·E₂₁·A = (E₂₁)^-1·U. But (E₂₁)^-1·E₂₁ is identity, therefore A = (E₂₁)^-1·U. From this equation it’s instantly obvious that the lower-triangular matrix L is nothing else but (E₂₁)^-1!

Another form of factorization is A = LDU, where D is the diagonal matrix that contains the pivots. For this example it would be:

Now imagine that we have some arbitrary 3x3 matrix A. To reduce matrix A into upper-triangular matrix U, we first eliminate the element at position 2,1, that is, we multiply A (from the left side) with elimination matrix E₂₁. Then we eliminate the element at 3,1 by multiplying (from the left side) with elimination matrix E₃₁. Finally we eliminate the element at 3,2 by multiplying with elimination matrix E₃₂:

It follows from this equation that the lower-triangular matrix is the inverse of E₃₂·E₃₁·E₂₁, that is,

We have found the factorization of a 3x3 matrix:

The algorithm for finding matrices L and U should now be clear. First do the elimination to find matrix U, then invert the product of elimination matrices used for finding U to find L. Actually it’s even easier, you don’t even need to keep elimination matrices E, or find their inverse. You can just keep the multipliers used in each elimination step. Please see the video to find out how it works.

Next, the cost of elimination algorithm is discussed. How many steps does it take to go from matrix A to U? Turns out the elimination is O(n³) process (more carefully, it takes around n³/3 steps). (See my notes on MIT’s Introduction to Algorithms for more info about O-notation.)

Since we sometimes need to do row exchanged to do elimination, the last ten minutes of lecture are spent on permutation matrices. Remember from lecture two that multiplying a matrix from the left side with a permutation matrix exchanges its rows.

The key facts about permutation matrices P are:

• The inverse of P is its transpose: P^-1 = P^T.
• There are n! permutation matrices for n_xn matrices.

Here is the video of the fourth lecture:

Topics covered in lecture four:

• [01:20] What is the inverse of A·B?
• [05:20] What is the inverse of A^T?
• [09:20] A=LU factorization for 2×2 matrices.
• [13:20] A=LDU factorization.
• [14:50] A=LU decomposition for 3×3 matrices.
• [18:30] Why is finding matrix L trivial?
• [27:25] How many operations does elimination take?
• [42:20] Permutation matrices.
• [47:20] What is the inverse of a permutation matrix?
• [48:20] How many P matrices for 3×3 and 4×4 matrices?

Here are my notes of lecture four:

My notes of linear algebra lecture 4 on the A=LU factorization.

Have fun with this lecture! The next post is going to be about transpose matrices, symmetric matrices, vector spaces, their subspaces and column spaces of matrices.

PS. This course is taught from Introduction to Linear Algebra textbook. Get it here:

This is the third post in an article series about MIT’s course “Linear Algebra”. In this post I will review lecture three on five ways to multiply matrices, inverse matrices and an algorithm for finding inverse matrices called Gauss-Jordan elimination.

The first lecture covered the geometry of linear equations and the second lecture covered the matrix elimination.

Here is lecture three.

Lecture 3: Matrix Multiplication and Inverse Matrices

Lecture three starts with five ways to multiply matrices.

The first way is the classical way. Suppose we are given a matrix A of size mxn with elements a_ij and a matrix B of size nxp with elements b_jk, and we want to find the product A·B. Multiplying matrices A and B will produce matrix C of size mxp with elements .

Here is how this sum works. To find the first element c₁₁ of matrix C, we sum over the 1st row of A and the 1st column of B. The sum expands to c₁₁ = a₁₁·b₁₁ + a₁₂·b₂₁ + a₁₃·b₃₁ + … + a_1n·b_n1. Here is a visualization of the summation:

We continue this way until we find all the elements of matrix C. Here is another visualization of finding c₂₃:

The second way is to take each column in B, multiply it by the whole matrix A and put the resulting column in the matrix C. The columns of C are combinations of columns of A. (Remember from previous lecture that a matrix times a column is a column.)

For example, to get column 1 of matrix C, we multiply A·(column 1 of matrix B):

The third way is to take each row in A, multiply it by the whole matrix B and put the resulting row in the matrix C. The rows of C are combinations of rows of B. (Again, remember from previous lecture that a row times a matrix is a row.)

For example, to get row 1 of matrix C, we multiply row 1 of matrix A with the whole matrix B:

The fourth way is to look at the product of A·B as a sum of (columns of A) times (rows of B).

Here is an example:

The fifth way is to chop matrices in blocks and multiply blocks by any of the previous methods.

Here is an example. Matrix A gets subdivided in four submatrices A₁ A₂ A₃ A₄, matrix B gets divided in four submatrices B₁ B₂ B₃ B₄ and the blocks get treated like simple matrix elements.

Here is the visualization:

Element C₁, for example, is obtained by multiplying A₁·B₁ + A₂·B₃.

Next the lecture proceeds to finding the inverse matrices. An inverse of a matrix A is another matrix, such that A^-1·A = I, where I is the identity matrix. In fact if A^-1 is the inverse matrix of a square matrix A, then it’s both the left-inverse and the right inverse, i.e., A^-1·A = A·A^-1 = I.

If a matrix A has an inverse then it is said to be invertible or non-singular.

Matrix A is singular if we can find a non-zero vector x such that A·x = 0. The proof is easy. Suppose A is not singular, i.e., there exists matrix A^-1. Then A^-1·A·x = 0·A^-1, which leads to a false statement that x = 0. Therefore A must be singular.

Another way of saying that matrix A is singular is to say that columns of matrix A are linearly dependent (one ore more columns can be expressed as a linear combination of others).

Finally, the lecture shows a deterministic method for finding the inverse matrix. This method is called the Gauss-Jordan elimination. In short, Gauss-Jordan elimination transforms augmented matrix (A|I) into (I|A^-1) by using only row eliminations.

Please watch the lecture to find out how it works in all the details:

Topics covered in lecture three:

• [00:51] The first way to multiply matrices.
• [04:50] When are we allowed to multiply matrices?
• [06:45] The second way to multiply matrices.
• [10:10] The third way to multiply matrices.
• [12:30] What is the result of multiplying a column of A and a row of B?
• [15:30] The fourth way to multiply matrices.
• [18:35] The fifth way to multiply matrices by blocks.
• [21:30] Inverses for square matrices.
• [24:55] Singular matrices (no inverse matrix exists).
• [30:00] Why singular matrices can’t have inverse?
• [36:20] Gauss-Jordan elimination.
• [41:20] Gauss-Jordan idea A·I -> I·A^-1.

Here are my notes of lecture three:

My notes of linear algebra lecture 3 on the matrix multiplication and inverses.

Have fun with this lecture! The next post is going to be about the A=LU matrix decomposition (also known as factorization).

PS. This course is taught from Introduction to Linear Algebra textbook. Get it here:

This is the second post in an article series about MIT’s course “Linear Algebra”. In this post I will review lecture two on solving systems of linear equations by elimination and back-substitution. The other topics in the lecture are elimination matrices (also known as elementary matrices) and permutation matrices.

The first post covered the geometry of linear equations.

One of my blog readers, Seyed M. Mottaghinejad, had also watched this course and sent me his lecture notes. They are awesome. Grab them here: lecture notes by Seyed M. Mottaghinejad (includes .pdf, .tex and his document class).

Okay, here is the second lecture.

Lecture 2: Elimination with Matrices

Elimination is the way every software package solves equations. If the elimination succeeds it gets the answer. If the matrix A in Ax=b is a “good” matrix (we’ll see what a good matrix is later) then the elimination will work and we’ll get the answer in an efficient way. It’s also always good to ask how can it fail. We’ll see in this lecture how elimination decides if the matrix A is good or bad. After the elimination there is a step called back-substitution to complete the answer.

Okay, here is a system of equations. Three equations in three unknowns.

Remember from lecture one, that every such system can be written in the matrix form Ax=b, where A is the matrix of coefficients, x is a column vector of unknowns and b is the column vector of solutions (the right hand side). Therefore the matrix form of this example is the following:

For the elimination process we need the matrix A and the column vector b. The idea is very simple, first we write them down in the augmented matrix form A|b:

Next we subtract rows from one another in such a way that the final result is an upper triangular matrix (a matrix with all the elements below the diagonal being zero).

So the first step is to subtract the first row multiplied by 3 from the second row. This gives us the following matrix:

The next step is to subtract the second row multiplied by 2 from the third row. This is the final step and produces an upper triangular matrix that we needed:

Now let’s write down the equations that resulted from the elimination:

Working from the bottom up we can immediately find the solutions z, y, and x. From the last equation, z = -10/5 = -2. Now we put z in the middle equation and solve for y. 2y = 6 + 2z = 6 + 2(-2) = 6 - 4 = 2 => y = 1. And finally, we can substitute y and z in the first equation and solve for x. x = 2 - 2y - z = 2 - 2(1) - (-2) = 2.

We have found the solution, it’s (x=2, y=1, z=-2). The process we used to find it is called the back-substitution.

The elimination would fail if taking a multiple of one row and adding to the next would produce a zero on the diagonal (and there would be no other row to try to exchange the failing row with).

The lecture continues with figuring out how to do the elimination by using matrices. In the first lecture we learned that a matrix times a column vector gave us a combination of the columns of the matrix. Similarly, a row times a matrix gives us a combination of the rows of the matrix.

Let’s look at our first step of elimination again. It was to subtract 3 times the first row from the second row. This can be expressed as matrix multiplication (forget the column b for a while):

Let’s call the matrix on the right E as elimination matrix (or elementary matrix), and give it subscript E₂₁ for making a zero in the resulting matrix at row 2, column 1.

The next step was twice the second row minus the third row:

The matrix on the right is again an elimination matrix. Let’s call it E₃₂ for giving a zero at row 3, column 2.

But notice that these two operations can be combined:

And we can write E₃₂(E₂₁A) = U. Now remember that matrix operations are associative, therefore we can change the parenthesis (E₃₂E₂₁)A = U. If we multiply (E₃₂E₂₁) we get a single matrix E that we will call the elimination matrix. What we have done is expressed the whole elimination process in matrix language!

Next, the lecture continues takes a step back and looks at permutation matrices. The question asked is “what matrix would exchange two rows of a matrix?” and “what matrix would exchange two columns of a matrix?”

Watch the lecture to find the answer to these questions!

Topics covered in lecture two:

• [00:25] Main topic for today: elimination.
• [02:35] A system with three equations and three unknowns:
• [03:30] Elimination process. Taking matrix A to U.
• [08:35] Three pivots of matrix U.
• [10:15] Relation of pivots to determinant of a matrix.
• [10:40] How can elimination fail?
• [14:40] Back substitution. Solution (x=2, y=1, z=-2).
• [19:45] Elimination with matrices.
• [21:10] Matrix times a column vector is a linear combination of columns the matrix.
• [22:15] A row vector times a matrix is a linear combination of rows of the matrix.
• [23:40] Matrix x column = column.
• [24:10] Row x matrix = row.
• [24:20] Elimination matrix for subtracting three times row one from row two.
• [26:55] The identity matrix.
• [30:00] Elimination matrix for subtracting two times row two from row three.
• [32:40] E₃₂E₂₁A = U.
• [37:20] Permutation matrices.
• [37:30] How to exchange rows of a 2×2 matrix?
• [37:55] Permutation matrix P to exchange rows of a 2×2 matrix.
• [38:40] How to exchange columns of a 2×2 matrix?
• [39:40] Permutation matrix P to exchange columns of a 2×2 matrix.
• [42:00] Commutative law does not hold for matrices.
• [44:25] Introduction to inverse matrices.
• [47:10] E^-1E = I.

Here are my notes of lecture two:

My notes of linear algebra lecture 2 on elimination with matrices.

Have fun with this lecture! The next post is going to be either on lectures three and four together or just lecture three. Lecture three will touch a bit more on matrix multiplication and then dive into the inverse matrices. Lecture four will cover A=LU matrix decomposition (also called factorization).

PS. This course is taught from Introduction to Linear Algebra textbook. Get it here: