Linear Algebra Rank of a Matrix, Part I

Welcome back to Educator.com and welcome back to linear algebra.0000

Today we are going to do the first part of a two-part lesson and we are going to discuss something called the rank of a matrix.0004

This is a profoundly, profoundly important concept.0013

Not that anything else that we have discussed or that we are going to be discussing is not important, it is, but this is where linear algebra starts to take on a very -- I do not know what the word for it is.0017

I know for me personally, this point when I studied rank that linear algebra became mysterious and at the same time extremely beautiful.0029

This is where the real beauty of mathematics was for me. This was the turning point. This particular topic.0040

I would definitely, definitely urge you to think very carefully about what is going on in these two lessons, and of course, using your textbook, maybe going through some of the proofs, which are not all together that difficult.0045

To make sure that you really, really wrap your mind around what is happening with this notion of a rank, and with the notion of the column space and the row space, which we are going to define and discuss in a minute.0057

So, do not worry, you do not have to know what they are yet.0070

It speaks to the strangeness that I can just take some random rectangular array of numbers, 3 by 6, 5 by 7, 10 by 14, and just throw any kind of numbers in a rectangular array.0073

Just by virtue of arranging them that way, there is a relationship that exists between the columns and the rows of that matrix that no one would ever believe should actually exist... and yet it does.0087

That is what makes this beautiful.0099

So, anyway, let us dive in, and hopefully you will feel the same way. Okay.0103

So, we are going to start off with a definition, and let us go ahead and define our matrix first that we are going to be talking about.0108

So, we will let a equal the following matrix... a11... a12... a1N... and a21... a22... so on.0116

a31 all the way down to aM1... and of course down here it is going to be aN... the subscript is mn.0142

Of course this is an m by n matrix. Okay.0156

Okay. So, this is an m by n matrix, and these entries of course are the entries of that matrix. Now, m by n. There are m rows.0163

So, 1, 2, 3, 4... m this way. n columns... that way.0171

Alright. If I take the rows of this matrix, I have m of them, right? So, let me write -- just write R1, which is equal to a11, a12, and so on, to a1n.0179

Let us say... let us just go ahead and write out row 2 also. a21, a22, all the way to a2N, so the first row, the second row, the third row.0208

If I treat them as just individual vectors, well, these rows... considered as vectors in RN.0220

The reason they are considered as vectors in RN is because they have n entries in them, right?0236

1, 2, 3, 4, 5... all the way to n. That is why they are vectors in RN.0242

A little bit better of an r here -- that one was a little bit odd.0249

Considered as vectors in RN... they span a subspace of RN called the row space.0254

So, let us stop and think about that again. If I take the rows of this m by n matrix, I have m rows.0275

Well, the rows have n entries in them, because they are n columns.0282

Well, if n entries, that means it is a vector in RN, right? Just like if I have 3 vectors, it is a vector in R3.0289

Well, those rows, let us say if I have 6 of them, they actually span a subspace of RN.0297

That subspace, we call the row space... so, let us differentiate the rows are the individual vectors from the row space, which is the space that the rows actually span.0307

I can define something called the column space analogously.0324

So, the columns... I will call them c1, c2, so forth, and I will write them as column vectors, in fact... a11, a21, all the way down to am1.0329

And, c2, I will put the second one also... a21, a22, a23, all the way down to am2.0351

Wait, I think my a2... have my indices incorrect here.0365

This is going to be a12, a22, a32, there we go... am2... it is very confusing.0374

Okay. So, if I take columns, notice now the columns have m entries in them, because they have m rows. If I take them as columns, they have m entries.0385

Well, if they have m entries, then they are vectors in RM.0396

So, the columns, considered as vectors in RM span another subspace called exactly what you think, the column space... subspace of RM, called the column space.0405

Okay. So, once again, if I just take any random matrix, any random rectangular array... m by n... if I take the rows and treat them as vectors in RN, those vectors span a space, a sub-space of RN as it turns out.0436

So, they are not just a subset, they actually span a subspace.0452

We call that the row space. If I take the columns of that matrix, any random matrix, and if I... those are going to be vectors in m-space... RM.0455

They span a space, a subspace of RM and we call that the column space.0469

So, any matrix has 2 subspaces associated with it automatically, by virtue of just picking the numbers -- a row space and a column space.0475

We are going to investigate the structure of that row space and that column space.0484

Okay. Now, let me... quick theorem that we are going to use before our first example.0489

If the 2 matrices a and b are 2 m by n matrices, which are row equivalent, and again row equivalence just means I have converted one to the other.0506

Like, for example, when I convert to reduced row echelon, those 2 matrices that I get are row equivalent.0527

Then, the row spaces of a and b are equal.0535

In other words, excuse me, simply by converting it by a series of those operations that we do... converting a matrix to, let us say reduced row echelon.0555

The reduced row echelon matrix still has the same row space. I have not changed anything. I added one equation to the other, I have not changed anything at all. That is what this theorem is saying.0565

So, now we are actually going to use this theorem. So, let us do our first example. Let us do it in red, here... oops, there we go.0575

Okay. We will let s equal the set of vectors v1, v2, v3... and v4.0595

Here is what the vectors are: v1 is the vector (1,-2,0,3,-4).0612

Let me write that down here, actually.0627

v2... so I do not feel so crushed in... (3,2,8,1,4).0631

v3 is (2,3,7,2,3).0642

v4 is equal to (-1,2,0,4,-3).0650

So, these vectors are vectors in R5, right? because they have 1, 2, 3, 4, 5 elements in them.0658

I have four vectors in R5. Okay.0664

We want to find a basis for a span of s, so these four vectors, they span a space.0671

I do now know what space, but I know they span a space.0684

Well, we want to find a basis for that space... for that subspace, not just any old space. Okay.0688

Let us do the following. Let us write these vectors, 1, 2, 3, 4 of them... and they are vectors in R5, so let us write them as the rows of a matrix.0699

Let us just take these random vectors and put them in matrix form.0714

So, we will let a equal to... we want to take the first vector (1,-2,0,3,-4), and I just write it our as my first row. (1,-2,0,3,-4).0720

I take vector 2, and that is (3,2,8,1,4).0734

I take vector 3, which is (2,3,7,2,3).0739

And, I take (-1,2,0,4,-3).0745

So, all I have done is I have taken these vectors and I have arranged them as the rows of a matrix.0750

Well, if I subject this matrix to reduced row echelon form, the matrix... nothing augmented... just take the vectors, stick it in matrix form and convert it to reduced row echelon form. Here is what I get.0757

(1,0,2,0,1), (0,1,1,0,1), (0,0,0,1,-1), and (0,0,0,0,0).0777

This is my reduced row echelon form. Well, as it turns out, the non-zero rows of this reduced row echelon form, in other words row 1 row 2, and row 3, they are as vectors linearly independent.0792

So we have these vectors that span a space, which means that we need to find vectors that are linearly independent.0811

As it turns out, there is a particular theorem which I did not mention here, but it is something... a result that we are using.0820

When I take a matrix and I reduce it to reduced row echelon form, the non-zero rows are linearly independent as vectors.0827

Therefore, I can take this vector as my first one, I will just call it w1. w1 = (1,0,2,0,1).0836

w2 = (0,1,1,0,1).0867

w3 = (0,0,0,1,-1).0874

This is a basis for the span of s. I was given this set of vectors.0884

I arranged these vectors as rows of a matrix. I reduced that matrix to reduced row echelon form, and the non-zero rows I just read them straight off.0894

Those non-zero rows, they form a basis for the span of those vectors.0904

Well, how many vectors do we have? 1, 2, 3.0911

So, the dimension of that space, of that span, is 3... because we have 3 linearly independent vectors that span the same space.0915

Notice, these vectors, (1,0,2,0,1)... they are vectors in R5, they have 5 entries in them.0931

(0,1,1,0,1), (0,0,0,1,-1), these are not the same vectors as these, okay? They are not from the original set.0937

They are completely different, and yet they span the same space. That is what makes this kind of extraordinary... that you can take these original vectors, arrange them in a matrix, reduced row echelon, whatever vectors are left over, they give you a vector that spans the same space.0946

Okay. So, now let us say we actually want to find a basis for the span of this space, but this time, we want vectors that are actually v1, v2, v3, v4.0961

We want vectors from this subset, whether it is v1 and v3, or v2, v3, v4, we do not know... I mean we do know, because we do know it is going to be at least 3 of them.0985

But, the idea is here we came up with 3 vectors that span this that are not from this original set, but there is actually a way to find a basis for this, consisting of vectors that are from this set.0997

Let us actually go ahead and do that. Before we do that, we are going to define this thing called the rank.1011

Well, we just calculated the dimension of that sub-space which was 3. Well, the dimension of the row space is called the row rank.1020

In a minute, we are going to talk about column rank, so I will just go ahead and write that too... the dimension of the column space is called column rank.1038

Okay. So, now let us do the same problem, but let us find a basis that actually consists of vectors from the original set.1057

This time, we take those vectors that we had... the v1, v2, v3, v4, and instead of writing them as rows, we are going to write them as columns and we are going to solve the associated homogeneous system for that.1066

Notice, for the last one, we just wrote them as rows and we converted that matrix to reduced row echelon form. Now we are going to write those as columns and we are going to augment it.1081

We are going to actually solve the associated system.1092

So, it turns out to be the following.1096

Yes... so, when I write v1, v2, v3, v4 as columns this time instead of rows, it looks like this.1113

(1,-2,0,3,-4), (3,2,8,1,4), (2,3,7,2,3), (-1,2,0,4,3)... and the augmented system.1122

Now, we have done this before, actually. If you remember a couple of lessons back when we were looking for the basis of a particular subspace, this is what we did.1150

We solved the associated homogeneous system, and then when we converted it to reduced row echelon, which we will do in a minute, the columns that have leading entries, the corresponding vectors are a basis from the original set.1156

So, let us go ahead and do that.1172

We convert to reduced row echelon and we get the following... (1,0,0,0,0), (0,1,0,0,0), (0,0,1,0,0), (11/24,0,-49/24,0,7/3), (0,0,0,0,0).1177

Okay, here we go. Now we have this column, this column, and this column, the first, second and third columns have leading entries in them.1206

Because they have leading entries in them, the original vectors corresponding to them.1216

In other words, that vector, that vector and that vector... which are part of the original set, they form a basis for the span of that original set of four vectors, right?1220

We had four vectors, but we do not need four vectors, we need just three, and that is what this procedure does.1232

It allows us to find a basis consisting of vectors from the original set.1238

Whereas the thing we did before allowed us to find a basis that had nothing to do with the set. Notice, we have three of them. It is not a coincidence.1242

So, in this particular case, we could take v1, v2, v3, the original, that is a basis for a span of s.1251

In other words, the span of s which is the row space.1267

Originally, we wrote them as rows... row vectors.1275

Here, we wrote them as columns in order to solve it in a certain way so that we end up with vectors from the original set.1280

It is still a row space, or the span of s, if you will.1287

Okay... and again, the row rank, well the row rank is a number of linearly independent vectors in the basis, or the number of vectors in the basis.1293

They are linearly independent by definition. The basis is 3.1307

Okay. So, now, let us write this out.1315

So, given a set of vectors, what it is that we just did.1321

Given a set of vectors, s, v1, v2, v3, and so on... to vk.1330

One. If we want a basis for the span of s consisting -- that is fine -- consisting of vectors from s, from the original set, then, set up the vectors as columns.1350

Augment the 0 vector, 0's, okay.1402

Convert to reduced row echelon, and then the vectors corresponding to columns with leading entries form the basis you are looking for.1411

The basis of span s. That was the second example that we did.1442

Two. Well, if we want a basis for span s consisting of vectors not necessarily in s...1449

Vectors completely different from that, but that still form a basis for that space.1480

Then, set up the vectors in s as rows of a matrix.1491

Convert to reduced row echelon.1506

Then, the non-zero rows, the actual non-zero rows of the reduced row echelon matrix form a basis which span s.1513

So, there you go. If you are given a set of vectors, and if you want to find a basis for the span of those vectors and if you want this particular basis to actually consist of vectors from the original set, then you set those vectors up as columns.1544

You solve the associated homogeneous system. You just add a zero, you augment the matrix, and then once you get the columns that have leading entries in them -- excuse me.1561

Let us say it is the first, third and fifth column, you reduce row echelon.1572

Then you go back to the original matrix and you pick the first, the third, and the fifth column. That is your basis.1576

If you want the basis for the span that has nothing to do with the original set of vectors, the set of the vectors as a row... reduced row echelon form... know worries about augmentation.1582

The non-zero rows give you the basis for the same space, and you will always end up with the same number.1591

If it is 3 for 1, it will be three for the other, if it is 2 for 1, it will be 2 for the other.1599

Okay. Let us do another example here. We will let -- this time, we will just throw out the matrix itself as opposed to given the vectors, we will just give you the matrix.1604

Often, it is done that way. You remember the definition at the beginning of this lesson was some row space and some column space. That is what we do. We just sort of often given a random matrix, and we have to treat the rows and columns as vectors.1616

So we will let a, let me go back to blue here, let a equal (1,2,-1), (1,9,-1), (-3,8,3), and (-2,8,2). That is a.1631

We want to find a basis for the row space of this matrix.1655

So for the row space of a, first part, we want this basis to consist of vectors which are not rows of a.1667

Part b, we want it to consist of vectors, the basis consisting of vectors which are rows of a.1691

Okay. So, we have a row space, so find the basis for the row space.1711

Well ,the row space is just these treated as vectors, and they are vectors in R3... 1, 2, 3... 1, 2, 3... 1, 2, 3... 1, 2, 3.1715

We have four vectors in R3. So, let us set them up.1725

Let us do part a first. Now, they want us to find a basis for this row space consisting of vectors, which are not actually these vectors at all.1732

These rows... So, for that, we need to set these vectors up as columns and solve the associated homogeneous system.1744

So, let us go ahead and do that.1753

Not -- no sorry -- we are consisting of vectors that are not rows of a. Okay.1761

Since we are doing it that are not rows of a, we are actually just going to set them up as rows. They are already set up as rows. My apologies.1770

It is hard to keep these straight sometimes. So, not rows of a. We set them up as this.1779

So, we are just going to go ahead and solve this matrix. Convert to reduced row echelon form.1784

So, let us rewrite it... (1,2,-1), so we write them as rows... yes. (1,2,-1).1791

(1,9,-1), (-3,8,3), and (-2,3,2).1798

Okay. We convert to reduced row echelon form, and we end up with the following: (1,0,-1), (0,1,0), (0,0,0), (0,0,0).1808

Okay. That, oops I wanted blue. So, that is a non-zero row, that is a non-zero row.1825

Therefore, I can take my basis as the set (1,0,-1)... that and that.1839

(1,0,-1)... and (0,1,0)... there two vectors form a basis for the row space of this matrix.1859

In other words, there are four vectors, 1, 2, 3, 4 vectors in R3. Three entries.1875

Well, they span a space, it is called the row space.1882

By simply leaving them as rows or arranging these as rows, row echelon, I get 2 non-zero vectors.1887

These two non-zero vectors, they span the same space.1893

So, dimension is, in other words, the row rank is equal to 2, because I have 2 vectors.1897

Okay. Now let us do part b. We want to find a basis for this row space that consists of vectors which are rows of a.1909

So, if they are rows of a, that means I have to solve a homogeneous system.1915

So, I will set up these rows as actual columns.1922

Okay. So, that is going to look like this... (1,2,-1), (1,9,-1), (-3,8,3), (-2,3,2)... and setting up a homogeneous system... (0,0,0).1928

Now, I need to convert this to reduced row echelon form, and when I do that, I get the following.1951

I get (1,0,0), (0,1,0), (-5,2,0), (-3,1,0), (0,0,0).1958

Go back to red... this column has a leading entry, this column has a leading entry... there they are.1973

Therefore, my basis consists of the original vectors corresponding to those two columns.1980

Now, my basis is the vector (1,2,-1) and the vector (1,9,-1).1988

This basis spans the same space as the other basis that I just found.2001

The rank is, well, 2.2006

It is pretty amazing, is it not?2013

Now, think about this for a second. I take some random vectors, and I arrange them in rows, and I convert to reduced row echelon form and I get the dimension of 2... i get a row rank of 2... two non-zero vectors.2019

Then, I write them as columns, and I solve the homogeneous system and I end up with, even though I end up with no non-zero columns, I mean I end up with two columns with leading entries.2035

I still end up with 2... that is kind of extraordinary. At least it is to me.2050

That you can just arrange these things as columns or rows and still end up essentially in the same place.2054

Now, this space, this row space, this space that is spanned by the original vectors that we had, this is a perfectly good basis for it, and the basis that we got otherwise is also a perfectly good basis for it.2063

Notice, both of them. They have 2 vectors in them. Okay.2074

So, row rank, row space. Profoundly important concepts.2082

We will continue this discussion in the next lesson. Thank you for joining us here at Educator.com. Take care.2097