1 00:00:14,830 --> 00:00:18,370 GILBERT STRANG: OK, in this second part, 2 00:00:18,370 --> 00:00:23,470 I'm going to start with linear equations, A times x equal b. 3 00:00:23,470 --> 00:00:26,770 And you see actually, the first real good starting point 4 00:00:26,770 --> 00:00:29,230 is A times x equals 0. 5 00:00:29,230 --> 00:00:35,800 So are there any solutions to the matrix, any combinations 6 00:00:35,800 --> 00:00:39,250 of the columns that give 0, any solutions 7 00:00:39,250 --> 00:00:41,470 to A times x equals 0? 8 00:00:41,470 --> 00:00:47,920 Now, I'm multiplying a matrix A by a vector x in a way 9 00:00:47,920 --> 00:00:49,170 you'll know. 10 00:00:49,170 --> 00:00:54,925 I take rows of x times, it's called a dot product. 11 00:00:58,330 --> 00:01:01,000 Rows of A times x. 12 00:01:01,000 --> 00:01:03,580 So I have a row of numbers. 13 00:01:03,580 --> 00:01:05,650 And x is a column of numbers. 14 00:01:05,650 --> 00:01:10,150 I multiply those numbers and add to get the dot product. 15 00:01:10,150 --> 00:01:13,630 And I'm wondering, can I get 0 for each? 16 00:01:13,630 --> 00:01:17,380 Is every row-- so having a 0 there 17 00:01:17,380 --> 00:01:23,490 is telling me, in geometry, that that row is perpendicular, 18 00:01:23,490 --> 00:01:27,130 orthogonal to that column. 19 00:01:27,130 --> 00:01:29,730 If a row dot product with a column 20 00:01:29,730 --> 00:01:34,290 gives me a 0, then in n dimensional space, 21 00:01:34,290 --> 00:01:41,580 that row is perpendicular, 90 degree angle to that column x. 22 00:01:41,580 --> 00:01:45,120 So I'm looking to see, are there any vectors x 23 00:01:45,120 --> 00:01:48,120 that are perpendicular to all the rows? 24 00:01:48,120 --> 00:01:50,750 That's what Ax equals 0 is asking for. 25 00:01:50,750 --> 00:01:53,220 Oh, and that's what I've just said right there. 26 00:01:53,220 --> 00:01:54,840 I've used the word orthogonal. 27 00:01:54,840 --> 00:01:57,910 That's more of a high level word than perpendicular. 28 00:01:57,910 --> 00:01:59,600 So I'll stay with that. 29 00:01:59,600 --> 00:02:01,320 It sounds a little cooler. 30 00:02:01,320 --> 00:02:02,040 OK. 31 00:02:02,040 --> 00:02:07,770 And now, we can also look at that transpose. 32 00:02:07,770 --> 00:02:10,710 Oh, do you know what the transpose of a matrix is? 33 00:02:10,710 --> 00:02:14,370 I take those rows and flip the matrix, 34 00:02:14,370 --> 00:02:17,460 so that those rows become the columns. 35 00:02:17,460 --> 00:02:21,630 And the columns of A become the rows of A transpose. 36 00:02:21,630 --> 00:02:24,350 So I'll look at A transpose times-- 37 00:02:24,350 --> 00:02:27,180 we'll call it y for the new problem. 38 00:02:27,180 --> 00:02:29,940 A transpose y is all 0s. 39 00:02:29,940 --> 00:02:35,490 And then the null space will be any vector, any solutions, 40 00:02:35,490 --> 00:02:41,440 any y that's perpendicular to the rows of A transpose. 41 00:02:41,440 --> 00:02:48,140 So I would need couple of hours of teaching to develop this 42 00:02:48,140 --> 00:02:50,630 properly because we're talking here 43 00:02:50,630 --> 00:02:56,570 about the fundamental theorem of linear algebra, which tells me 44 00:02:56,570 --> 00:02:59,090 that the vectors in the null space, 45 00:02:59,090 --> 00:03:03,830 like that, are perpendicular to the vectors. 46 00:03:03,830 --> 00:03:04,740 These guys are. 47 00:03:04,740 --> 00:03:06,470 That's the row space. 48 00:03:06,470 --> 00:03:09,170 Oh, but maybe I have told you. 49 00:03:09,170 --> 00:03:13,820 We've said that, from this equation, that tells you 50 00:03:13,820 --> 00:03:17,330 the geometry that that row vectors are 51 00:03:17,330 --> 00:03:21,240 perpendicular to the x vector, the thing in the null space. 52 00:03:21,240 --> 00:03:22,580 So x is there. 53 00:03:22,580 --> 00:03:23,570 The rows are there. 54 00:03:23,570 --> 00:03:25,370 And they're perpendicular. 55 00:03:25,370 --> 00:03:28,850 Now, if I transpose the matrix, remember 56 00:03:28,850 --> 00:03:31,010 that means exchanging rows and columns, 57 00:03:31,010 --> 00:03:34,460 so I have a new matrix, new size even. 58 00:03:34,460 --> 00:03:36,620 It will the same-- but it's a matrix. 59 00:03:36,620 --> 00:03:38,540 The same will be true for it. 60 00:03:38,540 --> 00:03:45,290 The rows become the columns. 61 00:03:45,290 --> 00:03:50,360 And the solutions to the new equation with A transpose 62 00:03:50,360 --> 00:03:52,940 go in that space. 63 00:03:52,940 --> 00:03:55,100 So then that little perpendicular sign 64 00:03:55,100 --> 00:03:57,770 is reminding us of the geometry. 65 00:03:57,770 --> 00:04:01,550 So rows perpendicular to the x's. 66 00:04:01,550 --> 00:04:03,710 Columns perpendicular to the y's. 67 00:04:03,710 --> 00:04:04,430 That's the best. 68 00:04:04,430 --> 00:04:07,130 I finally saw the right way to say that. 69 00:04:07,130 --> 00:04:09,380 So I have two pairs. 70 00:04:09,380 --> 00:04:14,600 And I know how big each of those four things are. 71 00:04:14,600 --> 00:04:21,459 Those are the four fundamental subspaces, two null spaces, 72 00:04:21,459 --> 00:04:23,690 two solution spaces with 0. 73 00:04:23,690 --> 00:04:24,980 Null means 0. 74 00:04:24,980 --> 00:04:30,350 So these x's are in the null space because of that 0. 75 00:04:30,350 --> 00:04:32,450 Those are the n's. 76 00:04:32,450 --> 00:04:37,170 And then this is the column space and the row space. 77 00:04:37,170 --> 00:04:40,130 So we've got four spaces altogether, two pairs. 78 00:04:40,130 --> 00:04:41,930 And now, you get to see the big picture 79 00:04:41,930 --> 00:04:45,530 of linear algebra, where the four fundamental subspaces do 80 00:04:45,530 --> 00:04:46,040 their thing. 81 00:04:46,040 --> 00:04:47,910 There you go. 82 00:04:47,910 --> 00:04:50,850 You can die happy now. 83 00:04:50,850 --> 00:04:56,190 The row spaces there, those are rows of the matrix, 84 00:04:56,190 --> 00:04:58,060 independent rows of the matrix. 85 00:04:58,060 --> 00:05:01,030 That's why I don't put in all the rows. 86 00:05:01,030 --> 00:05:02,230 There are m rows. 87 00:05:02,230 --> 00:05:04,570 But I only put in independent ones. 88 00:05:04,570 --> 00:05:08,590 So that might be a smaller number r, r the rank. 89 00:05:08,590 --> 00:05:12,100 And here are the solutions, the guys perpendicular to them. 90 00:05:12,100 --> 00:05:14,270 This is the rows of the matrix. 91 00:05:14,270 --> 00:05:16,900 These are the vectors perpendicular to it. 92 00:05:16,900 --> 00:05:18,920 These are the columns of the matrix. 93 00:05:18,920 --> 00:05:21,730 These are the vectors perpendicular to the columns. 94 00:05:21,730 --> 00:05:24,220 You see it's just a natural splitting 95 00:05:24,220 --> 00:05:31,580 of the whole spaces of vectors into two pieces and two pieces. 96 00:05:31,580 --> 00:05:35,680 And I think of the matrix A, when it multiplies stuff there, 97 00:05:35,680 --> 00:05:37,570 it gives stuff here. 98 00:05:37,570 --> 00:05:41,440 When A multiplies a vector x, you 99 00:05:41,440 --> 00:05:43,910 get a combination of the columns. 100 00:05:43,910 --> 00:05:46,310 That with the very, very first slide. 101 00:05:46,310 --> 00:05:49,150 A times x is a combination of the columns. 102 00:05:49,150 --> 00:05:52,390 And then we look at some x's, if there are 103 00:05:52,390 --> 00:05:56,890 any, where A times x gives 0. 104 00:05:56,890 --> 00:05:59,650 And there's 0 right there. 105 00:05:59,650 --> 00:06:01,350 OK. 106 00:06:01,350 --> 00:06:04,010 OK, so that's the big picture. 107 00:06:04,010 --> 00:06:09,040 And I'll just point to another little point 108 00:06:09,040 --> 00:06:10,700 that's hiding in this picture. 109 00:06:10,700 --> 00:06:13,280 You see that little symbol there, that little thing, 110 00:06:13,280 --> 00:06:15,580 and it's also here? 111 00:06:15,580 --> 00:06:18,120 What that means is that those guys are 112 00:06:18,120 --> 00:06:20,190 perpendicular to these. 113 00:06:20,190 --> 00:06:21,840 And these are perpendicular to these. 114 00:06:21,840 --> 00:06:26,880 So we have four subspaces, two pairs, two perpendicular pairs. 115 00:06:26,880 --> 00:06:32,070 And that's when you get the idea of knowing what they mean, 116 00:06:32,070 --> 00:06:36,270 knowing how to find them, at least for a small matrix, 117 00:06:36,270 --> 00:06:41,700 you've got the heart of linear algebra part one. 118 00:06:41,700 --> 00:06:44,230 This is the first half of linear algebra. 119 00:06:44,230 --> 00:06:47,040 OK, I'll just see what else there is. 120 00:06:47,040 --> 00:06:51,840 Oh, here, oh, well, this is another comment. 121 00:06:51,840 --> 00:06:55,470 I've hardly told you how to multiply two matrices. 122 00:06:55,470 --> 00:06:58,980 The usual way is rows times columns. 123 00:06:58,980 --> 00:07:03,030 But linear algebra being always interesting, 124 00:07:03,030 --> 00:07:05,490 there's another way that I happen 125 00:07:05,490 --> 00:07:09,840 to like, columns times rows. 126 00:07:09,840 --> 00:07:12,690 Now, there is a column times a row. 127 00:07:12,690 --> 00:07:16,860 Now, column times a row, we've seen that once 128 00:07:16,860 --> 00:07:18,820 for that rank one matrix. 129 00:07:18,820 --> 00:07:21,240 Do you remember I said that those rank one 130 00:07:21,240 --> 00:07:25,020 matrix, one column times is one row are the building blocks? 131 00:07:25,020 --> 00:07:26,580 Well, here is the building. 132 00:07:26,580 --> 00:07:29,660 Those are n of those blocks. 133 00:07:29,660 --> 00:07:32,640 A column times a row, a column times a row. 134 00:07:32,640 --> 00:07:35,730 And here is a reminder of the-- 135 00:07:35,730 --> 00:07:38,160 oh, we've only-- oh, we're coming up 136 00:07:38,160 --> 00:07:41,520 to A equal LU, the first one. 137 00:07:41,520 --> 00:07:44,600 Get on with it, Professor Strang. 138 00:07:44,600 --> 00:07:45,570 OK. 139 00:07:45,570 --> 00:07:47,700 OK, now we're solving equations. 140 00:07:47,700 --> 00:07:53,180 Now we're going to get L times U. So right. 141 00:07:53,180 --> 00:07:58,140 So there's two equations and two unknowns solved in high school 142 00:07:58,140 --> 00:07:59,160 and how. 143 00:07:59,160 --> 00:08:00,300 Do you remember how? 144 00:08:00,300 --> 00:08:01,800 That's the whole point. 145 00:08:01,800 --> 00:08:08,320 If I take twice that equation, so it's 4x plus 6y equal 14, 146 00:08:08,320 --> 00:08:11,110 and subtract from this one, then I 147 00:08:11,110 --> 00:08:14,980 get an easy equation for only y by itself. 148 00:08:14,980 --> 00:08:16,030 So that's what I did. 149 00:08:16,030 --> 00:08:17,310 That's called elimination. 150 00:08:17,310 --> 00:08:19,290 I eliminated this 4x. 151 00:08:19,290 --> 00:08:21,030 It's gone. 152 00:08:21,030 --> 00:08:23,400 It's 2 times that. 153 00:08:23,400 --> 00:08:26,550 That's why I chose to multiply it by 2. 154 00:08:26,550 --> 00:08:30,000 Then 2 times this gives me 4 x's. 155 00:08:30,000 --> 00:08:35,250 When I subtract it, it's gone and I'm left with 1y equal 1. 156 00:08:35,250 --> 00:08:37,980 So I know the answer y equal 1. 157 00:08:37,980 --> 00:08:43,080 And then I go backwards to x equal 2 because 2x plus, 158 00:08:43,080 --> 00:08:45,900 this is now, 3 equals 7. 159 00:08:45,900 --> 00:08:46,830 2x is 4. 160 00:08:46,830 --> 00:08:48,900 x is 2. 161 00:08:48,900 --> 00:08:55,500 And the real point about linear algebra 162 00:08:55,500 --> 00:09:00,790 done right is that all those steps 163 00:09:00,790 --> 00:09:04,510 can be expressed as a break up, another way 164 00:09:04,510 --> 00:09:09,860 to break up the matrix A into a lower triangular matrix. 165 00:09:09,860 --> 00:09:12,100 You see that that matrix is triangular. 166 00:09:12,100 --> 00:09:13,720 It's lower triangular. 167 00:09:13,720 --> 00:09:15,430 And this one is upper triangular. 168 00:09:15,430 --> 00:09:18,790 So those are called L and U. Yeah, yeah. 169 00:09:18,790 --> 00:09:24,820 So what we did here is expressed by that matrix multiplication. 170 00:09:24,820 --> 00:09:27,550 You really want to express everything, in the end, 171 00:09:27,550 --> 00:09:30,190 as multiplying a couple of matrices. 172 00:09:30,190 --> 00:09:33,370 Then you know exactly where you are. 173 00:09:33,370 --> 00:09:37,340 So that's the idea of elimination. 174 00:09:37,340 --> 00:09:41,450 And now, we only were doing a 2 by 2 matrix. 175 00:09:41,450 --> 00:09:46,660 You remember our little matrix was pathetic, 2, 3, 4, 7. 176 00:09:46,660 --> 00:09:50,110 That was our matrix A. We can't stop there. 177 00:09:50,110 --> 00:09:55,550 So linear algebra goes on to matrix of any size. 178 00:09:55,550 --> 00:10:00,980 And this is the way to find the triangular 179 00:10:00,980 --> 00:10:03,920 factor L and the upper triangular factor 180 00:10:03,920 --> 00:10:07,730 U. That would need more time. 181 00:10:07,730 --> 00:10:12,560 So all I want to say is, when you're doing elimination 182 00:10:12,560 --> 00:10:16,490 solving equations, then in the back of your mind 183 00:10:16,490 --> 00:10:23,320 or in the back page, you are producing an L matrix lower 184 00:10:23,320 --> 00:10:25,700 and a U matrix upper. 185 00:10:25,700 --> 00:10:28,550 So yeah. 186 00:10:28,550 --> 00:10:29,170 Let me see. 187 00:10:29,170 --> 00:10:30,470 Yeah, here we see them. 188 00:10:30,470 --> 00:10:35,150 The L matrix is all 0s above. 189 00:10:35,150 --> 00:10:37,670 The U matrix is all 0s below. 190 00:10:37,670 --> 00:10:42,080 And that's what is really happening. 191 00:10:42,080 --> 00:10:46,470 So that's what computer system totally focuses on. 192 00:10:46,470 --> 00:10:50,150 OK, that's the first slide of a new part. 193 00:10:50,150 --> 00:10:54,470 So I'll stop here and coming back to orthogonal vectors. 194 00:10:54,470 --> 00:10:56,020 Good.