1 00:00:00,000 --> 00:00:12,150 2 00:00:12,150 --> 00:00:13,421 This is lecture twelve. 3 00:00:13,421 --> 00:00:13,920 OK. 4 00:00:13,920 --> 00:00:15,650 We've reached twelve lectures. 5 00:00:15,650 --> 00:00:20,590 And this one is more than the others about applications 6 00:00:20,590 --> 00:00:21,890 of linear algebra. 7 00:00:21,890 --> 00:00:24,630 And I'll confess. 8 00:00:24,630 --> 00:00:29,010 When I'm giving you examples of the null space and the row 9 00:00:29,010 --> 00:00:32,470 space, I create a little matrix. 10 00:00:32,470 --> 00:00:35,970 You probably see that I just invent that matrix 11 00:00:35,970 --> 00:00:37,540 as I'm going. 12 00:00:37,540 --> 00:00:41,240 And I feel a little guilty about it, 13 00:00:41,240 --> 00:00:49,090 because the truth is that real linear algebra uses matrices 14 00:00:49,090 --> 00:00:51,570 that come from somewhere. 15 00:00:51,570 --> 00:00:55,470 They're not just, like, randomly invented by the instructor. 16 00:00:55,470 --> 00:00:57,740 They come from applications. 17 00:00:57,740 --> 00:01:00,560 They have a definite structure. 18 00:01:00,560 --> 00:01:07,330 And anybody who works with them gets, uses that structure. 19 00:01:07,330 --> 00:01:11,330 I'll just report, like, this weekend 20 00:01:11,330 --> 00:01:15,560 I was at an event with chemistry professors. 21 00:01:15,560 --> 00:01:19,180 OK, those guys are row reducing matrices, and what 22 00:01:19,180 --> 00:01:21,250 matrices are they working with? 23 00:01:21,250 --> 00:01:26,350 Well, their little matrices tell them how much of each element 24 00:01:26,350 --> 00:01:28,400 goes into the -- 25 00:01:28,400 --> 00:01:30,920 or each molecule, how many molecules of each 26 00:01:30,920 --> 00:01:34,170 go into a reaction and what comes out. 27 00:01:34,170 --> 00:01:37,460 And by row reduction they get a clearer picture 28 00:01:37,460 --> 00:01:40,030 of a complicated reaction. 29 00:01:40,030 --> 00:01:44,650 And this weekend I'm going to -- 30 00:01:44,650 --> 00:01:49,720 to a sort of birthday party at Mathworks. 31 00:01:49,720 --> 00:01:55,060 So Mathworks is out Route 9 in Natick. 32 00:01:55,060 --> 00:01:57,640 That's where Matlab is created. 33 00:01:57,640 --> 00:02:01,840 It's a very, very successful, software, 34 00:02:01,840 --> 00:02:03,750 tremendously successful. 35 00:02:03,750 --> 00:02:08,650 And the conference will be about how linear algebra is used. 36 00:02:08,650 --> 00:02:11,500 And so I feel better today to talk 37 00:02:11,500 --> 00:02:16,990 about what I think is the most important model 38 00:02:16,990 --> 00:02:19,040 in applied math. 39 00:02:19,040 --> 00:02:24,130 And the discrete version is a graph. 40 00:02:24,130 --> 00:02:26,710 So can I draw a graph? 41 00:02:26,710 --> 00:02:29,590 Write down the matrix that's associated with it, 42 00:02:29,590 --> 00:02:33,670 and that's a great source of matrices. 43 00:02:33,670 --> 00:02:34,500 You'll see. 44 00:02:34,500 --> 00:02:38,260 So a graph is just, so a graph -- 45 00:02:38,260 --> 00:02:42,500 to repeat -- has nodes and edges. 46 00:02:42,500 --> 00:02:47,020 47 00:02:47,020 --> 00:02:47,720 OK. 48 00:02:47,720 --> 00:02:53,100 And I'm going to write down the graph, a graph, so I'm just 49 00:02:53,100 --> 00:02:55,730 creating a small graph here. 50 00:02:55,730 --> 00:02:59,140 As I mentioned last time, we would be very interested 51 00:02:59,140 --> 00:03:01,600 in the graph of all, websites. 52 00:03:01,600 --> 00:03:04,170 53 00:03:04,170 --> 00:03:05,970 Or the graph of all telephones. 54 00:03:05,970 --> 00:03:09,980 I mean -- or the graph of all people in the world. 55 00:03:09,980 --> 00:03:18,550 Here let me take just, maybe nodes one two three -- 56 00:03:18,550 --> 00:03:19,910 well, I better put in an -- 57 00:03:19,910 --> 00:03:25,350 I'll put in that edge and maybe an edge to, to a node four, 58 00:03:25,350 --> 00:03:27,810 and another edge to node four. 59 00:03:27,810 --> 00:03:30,340 How's that? 60 00:03:30,340 --> 00:03:34,480 So there's a graph with four nodes. 61 00:03:34,480 --> 00:03:37,790 So n will be four in my -- 62 00:03:37,790 --> 00:03:38,945 n equal four nodes. 63 00:03:38,945 --> 00:03:41,570 64 00:03:41,570 --> 00:03:45,330 And the matrix will have m equal the number -- 65 00:03:45,330 --> 00:03:47,170 there'll be a row for every edge, 66 00:03:47,170 --> 00:03:52,080 so I've got one two three four five edges. 67 00:03:52,080 --> 00:03:56,310 So that will be the number of rows. 68 00:03:56,310 --> 00:04:01,290 And I have to to write down the matrix that I want to, 69 00:04:01,290 --> 00:04:05,170 I want to study, I need to give a direction to every edge, 70 00:04:05,170 --> 00:04:07,710 so I know a plus and a minus direction. 71 00:04:07,710 --> 00:04:10,240 So I'll just do that with an arrow. 72 00:04:10,240 --> 00:04:13,580 Say from one to two, one to three, two to three, 73 00:04:13,580 --> 00:04:15,940 one to four, three to four. 74 00:04:15,940 --> 00:04:24,690 That just tells me, if I have current flowing on these edges 75 00:04:24,690 --> 00:04:29,260 then I know whether it's -- to count it as positive 76 00:04:29,260 --> 00:04:32,880 or negative according as whether it's with the arrow or against 77 00:04:32,880 --> 00:04:34,110 the arrow. 78 00:04:34,110 --> 00:04:36,880 But I just drew those arrows arbitrarily. 79 00:04:36,880 --> 00:04:37,460 OK. 80 00:04:37,460 --> 00:04:41,960 Because I -- my example is going to come -- the example I'll -- 81 00:04:41,960 --> 00:04:46,750 the words that I will use will be words like potential, 82 00:04:46,750 --> 00:04:50,570 potential difference, currents. 83 00:04:50,570 --> 00:04:54,690 In other words, I'm thinking of an electrical 84 00:04:54,690 --> 00:04:55,690 network. 85 00:04:55,690 --> 00:05:00,470 But that's just one possibility. 86 00:05:00,470 --> 00:05:03,890 My applied math class builds on this example. 87 00:05:03,890 --> 00:05:07,770 It could be a hydraulic network, so we could be doing, 88 00:05:07,770 --> 00:05:11,940 flow of water, flow of oil. 89 00:05:11,940 --> 00:05:18,080 Other examples, this could be a structure. 90 00:05:18,080 --> 00:05:21,120 Like the -- a design for a bridge or a design 91 00:05:21,120 --> 00:05:27,030 for a Buckminster Fuller dome. 92 00:05:27,030 --> 00:05:30,240 Or many other possibilities, so many. 93 00:05:30,240 --> 00:05:34,340 So l- but let's take potentials and currents 94 00:05:34,340 --> 00:05:38,170 as, as a basic example, and let me 95 00:05:38,170 --> 00:05:42,020 create the matrix that tells you exactly what the graph tells 96 00:05:42,020 --> 00:05:42,520 you. 97 00:05:42,520 --> 00:05:43,394 That's --, that's it. 98 00:05:43,394 --> 00:05:49,876 So now I'll call it the incidence matrix, incidence 99 00:05:49,876 --> 00:05:50,375 matrix. 100 00:05:50,375 --> 00:05:54,320 101 00:05:54,320 --> 00:05:56,760 So let me write it down, and you'll see, 102 00:05:56,760 --> 00:05:58,950 OK. 103 00:05:58,950 --> 00:06:01,140 what its properties are. 104 00:06:01,140 --> 00:06:04,900 So every row corresponds to an edge. 105 00:06:04,900 --> 00:06:07,210 I have five rows from five edges, 106 00:06:07,210 --> 00:06:12,260 and let me write down again what this graph looks like. 107 00:06:12,260 --> 00:06:19,720 OK, the first edge, edge one, goes from node one to two. 108 00:06:19,720 --> 00:06:25,140 So I'm going to put in a minus one and a plus one in th- this 109 00:06:25,140 --> 00:06:30,970 corresponds to node one two three and four, 110 00:06:30,970 --> 00:06:33,390 That's a basis for the null space. the four columns. 111 00:06:33,390 --> 00:06:37,000 The five rows correspond -- the first row corresponds to edge 112 00:06:37,000 --> 00:06:37,760 one. 113 00:06:37,760 --> 00:06:42,410 Edge one leaves node one and goes into node two, and that -- 114 00:06:42,410 --> 00:06:44,750 and it doesn't touch three and four. 115 00:06:44,750 --> 00:06:50,050 Edge two, edge two goes -- oh, I haven't numbered these edges. 116 00:06:50,050 --> 00:06:54,160 I just figured that was probably edge one, but I didn't say so. 117 00:06:54,160 --> 00:06:56,740 Let me take that to be edge one. 118 00:06:56,740 --> 00:06:58,700 Let me take this to be edge two. 119 00:06:58,700 --> 00:07:00,660 Let me take this to be edge three. 120 00:07:00,660 --> 00:07:02,990 This is edge four. 121 00:07:02,990 --> 00:07:06,870 Ho, I'm discovering -- no, wait a minute. 122 00:07:06,870 --> 00:07:07,970 Did I number that twice? 123 00:07:07,970 --> 00:07:09,750 Here's edge four. 124 00:07:09,750 --> 00:07:10,980 And here's edge five. 125 00:07:10,980 --> 00:07:11,480 All right. 126 00:07:11,480 --> 00:07:11,980 OK? 127 00:07:11,980 --> 00:07:15,690 128 00:07:15,690 --> 00:07:20,780 So, so edge one, as I said, goes from node one to two. 129 00:07:20,780 --> 00:07:24,810 Edge two goes from two to three, node two to three, so 130 00:07:24,810 --> 00:07:30,420 minus one and one in the second and third columns. 131 00:07:30,420 --> 00:07:32,210 Edge three goes from one to three. 132 00:07:32,210 --> 00:07:36,679 133 00:07:36,679 --> 00:07:39,220 I'm, I'm tempted to stop for a moment with those three edges. 134 00:07:39,220 --> 00:07:39,330 The null space is actually one dimensional, and it's the line 135 00:07:39,330 --> 00:07:41,400 Edges one two three, those form what would we, 136 00:07:41,400 --> 00:07:45,130 A basis for the null space will be 137 00:07:45,130 --> 00:07:50,250 just that.1 what do you call the, the little, the little, 138 00:07:50,250 --> 00:07:54,750 the subgraph formed by edges one, two, and three? 139 00:07:54,750 --> 00:07:56,680 That's a loop. 140 00:07:56,680 --> 00:07:59,780 And the number of loops and the position of the loops 141 00:07:59,780 --> 00:08:01,230 will be crucial. 142 00:08:01,230 --> 00:08:01,940 OK. 143 00:08:01,940 --> 00:08:06,410 Actually, here's a interesting point about loops. 144 00:08:06,410 --> 00:08:09,480 If I look at those rows, corresponding 145 00:08:09,480 --> 00:08:13,150 to edges one two three, and these guys made a loop. 146 00:08:13,150 --> 00:08:18,100 147 00:08:18,100 --> 00:08:19,640 You want to tell me -- 148 00:08:19,640 --> 00:08:22,900 if I just looked at that much of the matrix 149 00:08:22,900 --> 00:08:25,790 it would be natural for me to ask, 150 00:08:25,790 --> 00:08:29,320 are those rows independent? 151 00:08:29,320 --> 00:08:31,270 Are the rows independent? 152 00:08:31,270 --> 00:08:35,370 And can you tell from looking at that if they are or are not 153 00:08:35,370 --> 00:08:36,179 independent? 154 00:08:36,179 --> 00:08:41,140 Do you see a, a relation between those three rows? 155 00:08:41,140 --> 00:08:42,030 Yes. 156 00:08:42,030 --> 00:08:47,760 If I add that row to that row, I get this row. 157 00:08:47,760 --> 00:08:52,020 So, so that's like a hint here that loops correspond 158 00:08:52,020 --> 00:08:54,850 to dependent, linearly dependent column -- 159 00:08:54,850 --> 00:08:59,540 linearly dependent give me a basis for the null space. 160 00:08:59,540 --> 00:09:00,040 rows. 161 00:09:00,040 --> 00:09:03,290 OK, let me complete the incidence matrix. 162 00:09:03,290 --> 00:09:09,410 Number four, edge four is going from node one to node four. 163 00:09:09,410 --> 00:09:12,960 And the fifth edge is going from node three to node four. 164 00:09:12,960 --> 00:09:16,190 165 00:09:16,190 --> 00:09:16,880 OK. 166 00:09:16,880 --> 00:09:17,880 There's my matrix. 167 00:09:17,880 --> 00:09:20,500 168 00:09:20,500 --> 00:09:24,700 It came from the five edges and the four nodes. 169 00:09:24,700 --> 00:09:31,390 And if I had a big graph, I'd have a big matrix. 170 00:09:31,390 --> 00:09:37,800 And what questions do I ask about matrices? 171 00:09:37,800 --> 00:09:40,150 Can I ask -- 172 00:09:40,150 --> 00:09:42,484 here's the review now. 173 00:09:42,484 --> 00:09:44,900 There's a matrix that comes from somewhere. of all vectors 174 00:09:44,900 --> 00:09:45,608 through that one. 175 00:09:45,608 --> 00:09:48,500 If, if it was a big graph, it would be a large matrix, 176 00:09:48,500 --> 00:09:50,490 but a lot of zeros, right? 177 00:09:50,490 --> 00:09:53,840 Because every row only has two non-zeros. 178 00:09:53,840 --> 00:09:57,680 So the number of -- it's a very sparse matrix. 179 00:09:57,680 --> 00:10:03,020 The number of non-zeros is exactly two times 180 00:10:03,020 --> 00:10:04,960 five, it's two m. 181 00:10:04,960 --> 00:10:07,090 Every row only has two non-zeros. 182 00:10:07,090 --> 00:10:10,170 And that's with a lot of structure. 183 00:10:10,170 --> 00:10:13,350 And -- that was the point I wanted to begin with, 184 00:10:13,350 --> 00:10:18,570 that graphs, that real graphs from real -- 185 00:10:18,570 --> 00:10:24,990 real matrices from genuine problems have structure. 186 00:10:24,990 --> 00:10:25,490 OK. 187 00:10:25,490 --> 00:10:27,823 We can ask, and because of the structure, we can answer, 188 00:10:27,823 --> 00:10:31,410 If it -- yeah, let me ask you just always, 189 00:10:31,410 --> 00:10:33,570 the, the main questions about matrices. 190 00:10:33,570 --> 00:10:38,990 So first question, what about the null space? 191 00:10:38,990 --> 00:10:41,940 So what I asking if I ask you for the null space of that 192 00:10:41,940 --> 00:10:43,150 matrix? 193 00:10:43,150 --> 00:10:47,590 I'm asking you if I'm looking at the columns of the matrix, 194 00:10:47,590 --> 00:10:47,710 four columns, and I'm asking you, So there's a basis for it, 195 00:10:47,710 --> 00:10:50,085 and here is the whole null are those columns independent? 196 00:10:50,085 --> 00:11:02,470 If the columns are independent, then what's in the null space? 197 00:11:02,470 --> 00:11:04,650 Only the zero vector, right? 198 00:11:04,650 --> 00:11:10,460 The null space contains -- tells us what combinations 199 00:11:10,460 --> 00:11:14,040 of the columns -- it tells us how to combine columns to get 200 00:11:14,040 --> 00:11:14,540 zero. 201 00:11:14,540 --> 00:11:17,390 202 00:11:17,390 --> 00:11:21,400 Can -- and is there anything in the null space of this matrix 203 00:11:21,400 --> 00:11:23,320 other than just the zero vector? 204 00:11:23,320 --> 00:11:26,679 In other words, are those four columns 205 00:11:26,679 --> 00:11:27,720 independent or dependent? 206 00:11:27,720 --> 00:11:30,260 What else is in the null space? 207 00:11:30,260 --> 00:11:31,020 OK. 208 00:11:31,020 --> 00:11:33,390 That's our question. 209 00:11:33,390 --> 00:11:40,070 Let me, I don't know if you see the answer. 210 00:11:40,070 --> 00:11:42,850 Whether there's -- so let's see. 211 00:11:42,850 --> 00:11:44,780 I guess we could do it properly. 212 00:11:44,780 --> 00:11:45,280 space. 213 00:11:45,280 --> 00:11:49,890 We could solve Ax=0. 214 00:11:49,890 --> 00:11:54,180 So let me solve Ax=0 to find the null space. 215 00:11:54,180 --> 00:11:54,680 OK. 216 00:11:54,680 --> 00:11:55,355 What's Ax? 217 00:11:55,355 --> 00:11:58,800 218 00:11:58,800 --> 00:12:01,200 Can I put x in here in, in little letters? 219 00:12:01,200 --> 00:12:04,070 220 00:12:04,070 --> 00:12:08,960 x1, x2, x3, x4, that's -- it's got four columns. 221 00:12:08,960 --> 00:12:13,320 Ax now is that matrix times x. 222 00:12:13,320 --> 00:12:17,530 And what do I get for Ax? 223 00:12:17,530 --> 00:12:22,680 If the camera can keep that matrix multiplication there, 224 00:12:22,680 --> 00:12:25,040 I'll put the answer here. 225 00:12:25,040 --> 00:12:30,350 Ax equal -- what's the first component of Ax? 226 00:12:30,350 --> 00:12:35,730 Can you take that first row, minus one one zero zero, 227 00:12:35,730 --> 00:12:40,180 and multiply by the x, and of course you get x2-x1. 228 00:12:40,180 --> 00:12:41,230 space. 229 00:12:41,230 --> 00:12:41,370 The second row, I get x3-x2. 230 00:12:41,370 --> 00:12:41,530 From the third row, I get x3-x1. 231 00:12:41,530 --> 00:12:44,030 Any multiple of one one one one, it's the whole line in four 232 00:12:44,030 --> 00:12:56,990 From the fourth row, I get x4-x1. 233 00:12:56,990 --> 00:13:01,440 And from the fifth row, I get x4-x3. 234 00:13:01,440 --> 00:13:05,700 And I want to know when is the thing zero. 235 00:13:05,700 --> 00:13:09,120 236 00:13:09,120 --> 00:13:12,170 This is my equation, Ax=0. 237 00:13:12,170 --> 00:13:15,400 Notice what that matrix A is doing, 238 00:13:15,400 --> 00:13:19,350 what we've created a matrix that computes 239 00:13:19,350 --> 00:13:22,200 the differences across every edge, the differences 240 00:13:22,200 --> 00:13:27,090 in potential. differences are zero, and that x is in the null 241 00:13:27,090 --> 00:13:30,750 Let me even begin to give this interpretation. 242 00:13:30,750 --> 00:13:38,930 I'm going to think of this vector x, which is x1 x2 x3 x4, 243 00:13:38,930 --> 00:13:42,840 as the potentials at the nodes. 244 00:13:42,840 --> 00:13:45,760 So I'm introducing a word, potentials at the nodes. 245 00:13:45,760 --> 00:13:50,450 246 00:13:50,450 --> 00:13:57,600 And now if I multiply by A, I get these -- 247 00:13:57,600 --> 00:14:01,635 I get these five components, x2-x1, et cetera. 248 00:14:01,635 --> 00:14:04,730 249 00:14:04,730 --> 00:14:07,210 And what are they? 250 00:14:07,210 --> 00:14:09,130 They're potential differences. 251 00:14:09,130 --> 00:14:11,350 That's what A computes. 252 00:14:11,350 --> 00:14:14,530 If I have potentials at the nodes and I multiply by A, 253 00:14:14,530 --> 00:14:18,520 it gives me the potential differences, the differences 254 00:14:18,520 --> 00:14:21,735 in potential, across the edges. 255 00:14:21,735 --> 00:14:25,870 256 00:14:25,870 --> 00:14:26,810 OK. 257 00:14:26,810 --> 00:14:29,830 When are those differences all zero? 258 00:14:29,830 --> 00:14:33,310 So I'm looking for the null space. 259 00:14:33,310 --> 00:14:37,810 Of course, if all the (x)s are zero then I get zero. 260 00:14:37,810 --> 00:14:40,900 That, that just tells me, of course, the zero vector 261 00:14:40,900 --> 00:14:43,240 is in the null space. 262 00:14:43,240 --> 00:14:47,870 But w- there's more in the null space. 263 00:14:47,870 --> 00:14:51,040 Those columns are -- of A are dependent, right -- 264 00:14:51,040 --> 00:14:54,790 because I can find solutions to that equation. 265 00:14:54,790 --> 00:14:56,172 dimensional space. 266 00:14:56,172 --> 00:14:57,255 Tell me -- the null space. 267 00:14:57,255 --> 00:15:00,620 268 00:15:00,620 --> 00:15:04,010 Tell me one vector in the null space, so tell me an x, 269 00:15:04,010 --> 00:15:10,490 it's got four components, and it makes that thing zero. 270 00:15:10,490 --> 00:15:13,890 So what's a good x to do that? 271 00:15:13,890 --> 00:15:22,000 One one one one, constant potential. 272 00:15:22,000 --> 00:15:52,130 If the potentials are constant, then all the potential 273 00:15:52,130 --> 00:16:03,430 Do you see that that's the null space? 274 00:16:03,430 --> 00:16:12,260 So the, so the dimension of the null space of A is one. 275 00:16:12,260 --> 00:16:14,690 And there's a basis for it, and there's 276 00:16:14,690 --> 00:16:16,190 everything that's in it. 277 00:16:16,190 --> 00:16:17,000 Good. 278 00:16:17,000 --> 00:16:23,250 And what does that mean physically? 279 00:16:23,250 --> 00:16:25,240 I mean, what does that mean in the application? 280 00:16:25,240 --> 00:16:26,850 That guy in the null space. 281 00:16:26,850 --> 00:16:33,170 It means that the potentials can only 282 00:16:33,170 --> 00:16:36,560 be determined up to a constant. 283 00:16:36,560 --> 00:16:39,560 Potential differences are what make current flow. 284 00:16:39,560 --> 00:16:40,970 That's what makes things happen. 285 00:16:40,970 --> 00:16:45,360 286 00:16:45,360 --> 00:16:47,140 It's these potential differences that 287 00:16:47,140 --> 00:16:50,320 will make something move in the, in our network, 288 00:16:50,320 --> 00:16:53,950 between x2- between node two and node one. 289 00:16:53,950 --> 00:16:57,650 Nothing will move if all potentials are the same. 290 00:16:57,650 --> 00:17:01,710 If all potentials are c, c, c, and c, then nothing will move. 291 00:17:01,710 --> 00:17:06,190 So we're, we have this one parameter, 292 00:17:06,190 --> 00:17:10,060 this arbitrary constant that raises or drops 293 00:17:10,060 --> 00:17:11,359 all the potentials. 294 00:17:11,359 --> 00:17:14,339 It's like ranking football teams, whatever. 295 00:17:14,339 --> 00:17:16,510 We have a, there's a, there's a constant -- 296 00:17:16,510 --> 00:17:20,540 or looking at temperatures, you know, 297 00:17:20,540 --> 00:17:23,770 there's a flow of heat from higher temperature to lower 298 00:17:23,770 --> 00:17:26,349 temperature. 299 00:17:26,349 --> 00:17:28,840 If temperatures are equal there's no flow, 300 00:17:28,840 --> 00:17:30,700 and therefore we can measure -- 301 00:17:30,700 --> 00:17:36,950 we can measure temperatures by, Celsius or we 302 00:17:36,950 --> 00:17:40,050 can start at absolute zero. 303 00:17:40,050 --> 00:17:44,000 And that arbitrary -- it's the same arbitrary constant that, 304 00:17:44,000 --> 00:17:46,660 that was there in calculus. 305 00:17:46,660 --> 00:17:49,030 In calculus, right, when you took 306 00:17:49,030 --> 00:17:53,050 the integral, the indefinite integral, there was a plus c, 307 00:17:53,050 --> 00:17:58,030 and you had to set a starting point to know what that c was. 308 00:17:58,030 --> 00:18:02,370 So here what often happens is we fix one of the potentials, 309 00:18:02,370 --> 00:18:06,370 like the last one. 310 00:18:06,370 --> 00:18:12,050 So a typical thing would be to ground that node. 311 00:18:12,050 --> 00:18:16,040 To set its potential at zero. 312 00:18:16,040 --> 00:18:19,070 And if we do that, if we fix that potential 313 00:18:19,070 --> 00:18:25,570 so it's not unknown anymore, then that column disappears 314 00:18:25,570 --> 00:18:29,440 and we have three columns, and those three columns 315 00:18:29,440 --> 00:18:30,420 are independent. 316 00:18:30,420 --> 00:18:33,630 So I'll leave the column in there, 317 00:18:33,630 --> 00:18:35,950 but we'll remember that grounding a node 318 00:18:35,950 --> 00:18:38,520 is the way to get it out. 319 00:18:38,520 --> 00:18:42,680 And grounding a node is the way to -- setting a node -- 320 00:18:42,680 --> 00:18:47,890 setting a potential to zero tells us the, the base for all 321 00:18:47,890 --> 00:18:48,510 potentials. 322 00:18:48,510 --> 00:18:51,370 Then we can compute the others. 323 00:18:51,370 --> 00:18:55,070 But what's the -- now I've talked enough to ask 324 00:18:55,070 --> 00:18:58,420 OK. what the rank of the matrix is? 325 00:18:58,420 --> 00:19:01,240 What's the rank then? 326 00:19:01,240 --> 00:19:03,000 The rank of the matrix. 327 00:19:03,000 --> 00:19:06,030 So we have a five by four matrix. 328 00:19:06,030 --> 00:19:11,680 We've located its null space, one dimensional. 329 00:19:11,680 --> 00:19:13,870 How many independent columns do we have? 330 00:19:13,870 --> 00:19:15,050 What's the rank? 331 00:19:15,050 --> 00:19:17,880 It's three. 332 00:19:17,880 --> 00:19:21,180 And the first three columns, or actually any three columns, 333 00:19:21,180 --> 00:19:22,920 will be independent. 334 00:19:22,920 --> 00:19:28,800 Any three potentials are independent, good variables. 335 00:19:28,800 --> 00:19:35,490 The fourth potential is not, we need to set, 336 00:19:35,490 --> 00:19:38,160 and typically we ground that node. 337 00:19:38,160 --> 00:19:38,660 OK. 338 00:19:38,660 --> 00:19:40,270 Rank is three. 339 00:19:40,270 --> 00:19:43,820 Rank equals three. 340 00:19:43,820 --> 00:19:45,200 OK. 341 00:19:45,200 --> 00:19:48,420 Let's see, do I want to ask you about the column space? 342 00:19:48,420 --> 00:19:52,360 The column space is all combinations of those columns. 343 00:19:52,360 --> 00:19:55,560 I could say more about it and I will. 344 00:19:55,560 --> 00:20:01,870 Let me go to the null space of A transpose, 345 00:20:01,870 --> 00:20:07,680 because the equation A transpose y equals zero 346 00:20:07,680 --> 00:20:10,090 is probably the most fundamental equation 347 00:20:10,090 --> 00:20:11,410 of applied mathematics. 348 00:20:11,410 --> 00:20:14,860 All right, let's talk about that. 349 00:20:14,860 --> 00:20:17,230 That deserves our attention. 350 00:20:17,230 --> 00:20:21,590 A transpose y equals zero. 351 00:20:21,590 --> 00:20:29,510 Let's -- let me put it on here. 352 00:20:29,510 --> 00:20:32,991 So A transpose y equals zero. 353 00:20:32,991 --> 00:20:33,490 OK. 354 00:20:33,490 --> 00:20:38,360 So now I'm finding the null space of A transpose. 355 00:20:38,360 --> 00:20:41,200 Oh, and if I ask you its dimension, 356 00:20:41,200 --> 00:20:43,760 you could tell me what it is. 357 00:20:43,760 --> 00:20:49,140 What's the dimension of the null space of A transpose? 358 00:20:49,140 --> 00:20:51,640 We now know enough to answer that question. 359 00:20:51,640 --> 00:20:55,030 What's the general formula for the dimension of the null space 360 00:20:55,030 --> 00:20:55,770 of A transpose? 361 00:20:55,770 --> 00:20:58,760 362 00:20:58,760 --> 00:21:02,560 A transpose, let me even write out A transpose. 363 00:21:02,560 --> 00:21:10,070 This A transpose will be n by m, right? 364 00:21:10,070 --> 00:21:12,770 In this case, it'll be four by five. 365 00:21:12,770 --> 00:21:13,960 n by m. 366 00:21:13,960 --> 00:21:16,320 Those columns will become rows. 367 00:21:16,320 --> 00:21:25,480 Minus one zero minus one minus one zero is now the first row. 368 00:21:25,480 --> 00:21:31,710 The second row of the matrix, one minus one and three zeros. 369 00:21:31,710 --> 00:21:36,210 The third column now becomes the third row, zero one one 370 00:21:36,210 --> 00:21:38,480 zero minus one. 371 00:21:38,480 --> 00:21:41,905 And the fourth column becomes the fourth row. 372 00:21:41,905 --> 00:21:45,730 373 00:21:45,730 --> 00:21:46,560 OK, good. 374 00:21:46,560 --> 00:21:48,400 There's A transpose. 375 00:21:48,400 --> 00:21:55,965 That multiplies y, y1 y2 y3 y4 and y5. 376 00:21:55,965 --> 00:22:00,740 377 00:22:00,740 --> 00:22:01,410 OK. 378 00:22:01,410 --> 00:22:03,830 Now you've had time to think about this question. 379 00:22:03,830 --> 00:22:09,370 What's the dimension of the null space, if I set all those 380 00:22:09,370 --> 00:22:10,705 -- wow. 381 00:22:10,705 --> 00:22:13,410 382 00:22:13,410 --> 00:22:15,960 Usually -- sometime during this semester, 383 00:22:15,960 --> 00:22:19,570 I'll drop one of these erasers behind there. 384 00:22:19,570 --> 00:22:20,880 That's a great moment. 385 00:22:20,880 --> 00:22:22,570 There's no recovery. 386 00:22:22,570 --> 00:22:29,390 There's -- centuries of erasers are back there. 387 00:22:29,390 --> 00:22:29,890 OK. 388 00:22:29,890 --> 00:22:35,100 389 00:22:35,100 --> 00:22:38,020 OK, what's the dimension of the null space? 390 00:22:38,020 --> 00:22:40,640 391 00:22:40,640 --> 00:22:42,510 Give me the general formula first 392 00:22:42,510 --> 00:22:46,050 in terms of r and m and n. 393 00:22:46,050 --> 00:22:49,580 This is like crucial, you -- 394 00:22:49,580 --> 00:22:54,200 we struggled to, to decide what dimension meant, 395 00:22:54,200 --> 00:22:59,980 and then we figured out what it equaled for an m 396 00:22:59,980 --> 00:23:05,850 by n matrix of rank r, and the answer was m-r, right? 397 00:23:05,850 --> 00:23:14,200 There are m=5 components, m=5 columns of A transpose. 398 00:23:14,200 --> 00:23:18,400 And r of those columns are pivot columns, 399 00:23:18,400 --> 00:23:19,960 because it'll have r pivots. 400 00:23:19,960 --> 00:23:21,410 It has rank r. 401 00:23:21,410 --> 00:23:28,090 And m-r are the free ones now for A transpose, 402 00:23:28,090 --> 00:23:32,060 so that's five minus three, so that's two. 403 00:23:32,060 --> 00:23:35,040 404 00:23:35,040 --> 00:23:39,400 And I would like to find this null space. 405 00:23:39,400 --> 00:23:41,800 I know its dimension. 406 00:23:41,800 --> 00:23:45,440 Now I want to find out a basis for it. 407 00:23:45,440 --> 00:23:48,780 And I want to understand what this equation is. 408 00:23:48,780 --> 00:23:53,500 So let me say what A transpose y actually represents, why I'm 409 00:23:53,500 --> 00:23:57,120 interested in that equation. 410 00:23:57,120 --> 00:24:04,090 I'll put it down with those old erasers and continue this. 411 00:24:04,090 --> 00:24:07,430 Here's the great picture of applied mathematics. 412 00:24:07,430 --> 00:24:09,560 So let me complete that. 413 00:24:09,560 --> 00:24:14,040 There's a matrix that I'll call C 414 00:24:14,040 --> 00:24:17,830 that connects potential differences to currents. 415 00:24:17,830 --> 00:24:21,840 So I'll call these -- these are currents on the edges, 416 00:24:21,840 --> 00:24:27,990 y1 y2 y3 y4 and y5. 417 00:24:27,990 --> 00:24:30,340 Those are currents on the edges. 418 00:24:30,340 --> 00:24:34,160 419 00:24:34,160 --> 00:24:39,090 And this relation between current and potential 420 00:24:39,090 --> 00:24:41,820 difference is Ohm's Law. 421 00:24:41,820 --> 00:24:43,340 This here is Ohm's Law. 422 00:24:43,340 --> 00:24:47,060 423 00:24:47,060 --> 00:24:50,300 Ohm's Law says that the current on an edge 424 00:24:50,300 --> 00:24:56,080 is some number times the potential drop. 425 00:24:56,080 --> 00:24:59,820 That's -- and that number is the conductance of the edge, 426 00:24:59,820 --> 00:25:01,290 one over the resistance. 427 00:25:01,290 --> 00:25:08,850 This is the old current is, is, the relation 428 00:25:08,850 --> 00:25:13,960 of current, resistance, and change in potential. 429 00:25:13,960 --> 00:25:17,760 So it's a change in potential that makes some current happen, 430 00:25:17,760 --> 00:25:22,170 and it's Ohm's Law that says how much current happens. 431 00:25:22,170 --> 00:25:22,820 OK. 432 00:25:22,820 --> 00:25:25,940 And then the final step of this framework 433 00:25:25,940 --> 00:25:31,070 is the equation A transpose y equals zero. 434 00:25:31,070 --> 00:25:33,950 435 00:25:33,950 --> 00:25:38,990 And that's -- what is that saying? 436 00:25:38,990 --> 00:25:40,470 It has a famous name. 437 00:25:40,470 --> 00:25:50,590 It's Kirchoff's Current Law, KCL, Kirchoff's Current Law, 438 00:25:50,590 --> 00:25:53,030 A transpose y equals zero. 439 00:25:53,030 --> 00:25:55,950 So that when I'm solving, and when I go back up with this 440 00:25:55,950 --> 00:26:03,770 blackboard and solve A transpose y equals zero, 441 00:26:03,770 --> 00:26:05,950 it's this pattern of -- 442 00:26:05,950 --> 00:26:08,110 that I want you to see. 443 00:26:08,110 --> 00:26:11,360 That we had rectangular matrices, but -- 444 00:26:11,360 --> 00:26:17,070 and real applications, but in those real applications comes A 445 00:26:17,070 --> 00:26:18,500 and A transpose. 446 00:26:18,500 --> 00:26:22,030 So our four subspaces are exactly the right things 447 00:26:22,030 --> 00:26:23,461 to know about. 448 00:26:23,461 --> 00:26:23,960 All right. 449 00:26:23,960 --> 00:26:28,030 Let's know about that null space of A transpose. 450 00:26:28,030 --> 00:26:31,990 Wait a minute, where'd it go? 451 00:26:31,990 --> 00:26:33,190 There it is. 452 00:26:33,190 --> 00:26:34,680 OK. 453 00:26:34,680 --> 00:26:35,720 OK. 454 00:26:35,720 --> 00:26:38,210 Null space of A transpose. 455 00:26:38,210 --> 00:26:40,070 We know what its dimension should be. 456 00:26:40,070 --> 00:26:43,340 457 00:26:43,340 --> 00:26:47,670 Let's find out -- tell me a vector in it. 458 00:26:47,670 --> 00:26:50,150 Tell me -- now, so what I asking you? 459 00:26:50,150 --> 00:26:53,850 I'm asking you for five currents that 460 00:26:53,850 --> 00:26:57,320 satisfy Kirchoff's Current Law. 461 00:26:57,320 --> 00:26:59,650 So we better understand what that law says. 462 00:26:59,650 --> 00:27:01,780 That, that law, A transpose y equals 463 00:27:01,780 --> 00:27:09,430 zero, what does that say, say in the first row of A transpose? 464 00:27:09,430 --> 00:27:13,100 That says -- the so the first row of A transpose says minus 465 00:27:13,100 --> 00:27:19,280 y1 minus y3 minus y4 is zero. 466 00:27:19,280 --> 00:27:22,740 467 00:27:22,740 --> 00:27:25,020 Where did that equation come from? 468 00:27:25,020 --> 00:27:27,470 Let me -- I'll redraw the graph. 469 00:27:27,470 --> 00:27:31,600 Can I redraw the graph here, so that we -- maybe here, 470 00:27:31,600 --> 00:27:34,900 so that we see again -- 471 00:27:34,900 --> 00:27:39,470 there was node one, node two, node three, 472 00:27:39,470 --> 00:27:41,750 node four was off here. 473 00:27:41,750 --> 00:27:45,310 That was, that was our graph. 474 00:27:45,310 --> 00:27:47,220 We had currents on those. 475 00:27:47,220 --> 00:27:50,650 We had a current y1 going there. 476 00:27:50,650 --> 00:27:53,120 We had a current y -- what were the other, 477 00:27:53,120 --> 00:27:58,900 what are those edge numbers? y4 here and y3 here. 478 00:27:58,900 --> 00:28:01,480 479 00:28:01,480 --> 00:28:04,990 And then a y2 and a y5. 480 00:28:04,990 --> 00:28:07,860 I'm, I'm just copying what was on the other board 481 00:28:07,860 --> 00:28:10,470 so it's ea- convenient to see it. 482 00:28:10,470 --> 00:28:15,260 What is this equation telling me, this first equation 483 00:28:15,260 --> 00:28:19,230 of Kirchoff's Current Law? 484 00:28:19,230 --> 00:28:21,900 What does that mean for that graph? 485 00:28:21,900 --> 00:28:29,320 Well, I see y1, y3, and y4 as the currents leaving node one. 486 00:28:29,320 --> 00:28:32,930 So sure enough, the first equation refers to node one, 487 00:28:32,930 --> 00:28:34,720 and what does it say? 488 00:28:34,720 --> 00:28:39,430 It says that the net flow is zero. 489 00:28:39,430 --> 00:28:43,230 That, that equation A transpose y, Kirchoff's Current Law, 490 00:28:43,230 --> 00:28:47,860 is a balance equation, a conservation law. 491 00:28:47,860 --> 00:28:51,770 Physicists, be overjoyed, right, by this stuff. 492 00:28:51,770 --> 00:28:56,520 It, it says that in equals out. 493 00:28:56,520 --> 00:29:01,770 And in this case, the three arrows are all going out, 494 00:29:01,770 --> 00:29:05,070 so it says y1, y3, and y4 add to zero. 495 00:29:05,070 --> 00:29:07,280 Let's take the next one. 496 00:29:07,280 --> 00:29:16,150 The second row is y1-y2, and that's all that's in that row. 497 00:29:16,150 --> 00:29:19,790 And that must have something to do with node two. 498 00:29:19,790 --> 00:29:25,780 And sure enough, it says y1=y2, current in equals current out. 499 00:29:25,780 --> 00:29:33,300 The third one, y2 plus y3 minus y5 equals 500 00:29:33,300 --> 00:29:34,200 zero. 501 00:29:34,200 --> 00:29:38,340 That certainly will be what's up at the third node. 502 00:29:38,340 --> 00:29:43,350 y2 coming in, y3 coming in, y5 going out has to balance. 503 00:29:43,350 --> 00:29:48,770 And finally, y4 plus y5 equals zero 504 00:29:48,770 --> 00:29:57,760 says that at this node, y4 plus y5, the total flow, 505 00:29:57,760 --> 00:30:01,530 We don't -- you know, charge doesn't accumulate at is zero. 506 00:30:01,530 --> 00:30:03,000 the nodes. 507 00:30:03,000 --> 00:30:06,180 It travels around. 508 00:30:06,180 --> 00:30:07,030 OK. 509 00:30:07,030 --> 00:30:09,940 Now give me -- 510 00:30:09,940 --> 00:30:12,580 I come back now to the linear algebra question. 511 00:30:12,580 --> 00:30:17,310 What's a vector y that solves these equations? 512 00:30:17,310 --> 00:30:19,860 Can I figure out what the null space 513 00:30:19,860 --> 00:30:28,470 is for this matrix, A transpose, by looking at the graph? 514 00:30:28,470 --> 00:30:33,070 I'm happy if I don't have to do elimination. 515 00:30:33,070 --> 00:30:35,780 I can do elimination, we know how to do, 516 00:30:35,780 --> 00:30:39,110 we know how to find the null space basis. 517 00:30:39,110 --> 00:30:42,580 We can do elimination on this matrix, 518 00:30:42,580 --> 00:30:48,150 and we'll get it into a good reduced row echelon form, 519 00:30:48,150 --> 00:30:51,330 and the special solutions will pop right out. 520 00:30:51,330 --> 00:30:56,040 But I would like to -- even to do it without that. 521 00:30:56,040 --> 00:30:59,820 Let me just ask you first, if I did elimination 522 00:30:59,820 --> 00:31:06,780 on that, on that, matrix, what would the last row become? 523 00:31:06,780 --> 00:31:10,220 What would the last row -- if I do elimination on that matrix, 524 00:31:10,220 --> 00:31:16,380 the last row of R will be all zeros, right? 525 00:31:16,380 --> 00:31:17,190 Why? 526 00:31:17,190 --> 00:31:19,770 Because the rank is three. 527 00:31:19,770 --> 00:31:22,720 We only going to have three pivots. 528 00:31:22,720 --> 00:31:26,540 And the fourth row will be all zeros when we eliminate. 529 00:31:26,540 --> 00:31:32,020 So elimination will tell us what, what we spotted earlier, 530 00:31:32,020 --> 00:31:36,160 what's the null space -- all the, all the information, 531 00:31:36,160 --> 00:31:38,450 what are the dependencies. 532 00:31:38,450 --> 00:31:42,790 We'll find those by elimination, but here in a real example, 533 00:31:42,790 --> 00:31:44,830 we can find them by thinking. 534 00:31:44,830 --> 00:31:46,030 OK. 535 00:31:46,030 --> 00:31:52,320 Again, my question is, what is a solution y? 536 00:31:52,320 --> 00:31:55,940 How could current travel around this network 537 00:31:55,940 --> 00:32:02,440 without collecting any charge at the nodes? 538 00:32:02,440 --> 00:32:03,650 Tell me a y. 539 00:32:03,650 --> 00:32:04,540 OK. 540 00:32:04,540 --> 00:32:12,650 So a basis for the null space of A transpose. 541 00:32:12,650 --> 00:32:15,980 How many vectors I looking for? 542 00:32:15,980 --> 00:32:17,220 Two. 543 00:32:17,220 --> 00:32:18,750 It's a two dimensional space. 544 00:32:18,750 --> 00:32:21,350 My basis should have two vectors in it. 545 00:32:21,350 --> 00:32:23,570 Give me one. 546 00:32:23,570 --> 00:32:24,750 One set of currents. 547 00:32:24,750 --> 00:32:28,470 Suppose, let me start it. 548 00:32:28,470 --> 00:32:31,801 Let me start with y1 as one. 549 00:32:31,801 --> 00:32:32,300 OK. 550 00:32:32,300 --> 00:32:38,860 So one unit of -- one amp travels on edge one with 551 00:32:38,860 --> 00:32:40,120 the arrow. 552 00:32:40,120 --> 00:32:41,480 OK, then what? 553 00:32:41,480 --> 00:32:42,275 What is y2? 554 00:32:42,275 --> 00:32:44,790 555 00:32:44,790 --> 00:32:47,000 It's one also, right? 556 00:32:47,000 --> 00:32:50,230 And of course what you did was solve Kirchoff's Current Law 557 00:32:50,230 --> 00:32:52,770 quickly in the second equation. 558 00:32:52,770 --> 00:32:53,600 OK. 559 00:32:53,600 --> 00:32:57,400 Now we've got one amp leaving node one, coming around to node 560 00:32:57,400 --> 00:32:57,900 three. 561 00:32:57,900 --> 00:32:58,990 What shall we do now? 562 00:32:58,990 --> 00:33:01,920 563 00:33:01,920 --> 00:33:05,350 Well, what shall I take for y3 in other words? 564 00:33:05,350 --> 00:33:08,870 Oh, I've got a choice, but why not make it what you said, 565 00:33:08,870 --> 00:33:11,530 negative one. 566 00:33:11,530 --> 00:33:16,150 So I have just sent current, one amp, around that loop. 567 00:33:16,150 --> 00:33:19,130 568 00:33:19,130 --> 00:33:23,000 What shall y4 and y5 be in this case? 569 00:33:23,000 --> 00:33:25,050 We could take them to be zero. 570 00:33:25,050 --> 00:33:31,410 This satisfies Kirchoff's Current Law. 571 00:33:31,410 --> 00:33:36,190 We could check it patiently, that minus y1 minus y3 572 00:33:36,190 --> 00:33:37,050 gives zero. 573 00:33:37,050 --> 00:33:38,920 We know y1 is y2. 574 00:33:38,920 --> 00:33:42,710 The others, y4 plus y5 is certainly zero. 575 00:33:42,710 --> 00:33:46,880 Any current around a loop satisfies -- 576 00:33:46,880 --> 00:33:49,090 satisfies the Current Law. 577 00:33:49,090 --> 00:33:52,140 Now you know how to get another one. 578 00:33:52,140 --> 00:33:53,150 OK. 579 00:33:53,150 --> 00:33:55,890 Take current around this loop. 580 00:33:55,890 --> 00:34:04,650 So now let y3 be one, y5 be one, and y4 be minus one. 581 00:34:04,650 --> 00:34:10,400 And so, so we have the first basis vector sent current 582 00:34:10,400 --> 00:34:13,260 around that loop, the second basis vector 583 00:34:13,260 --> 00:34:14,500 sends current around that 584 00:34:14,500 --> 00:34:15,590 loop. 585 00:34:15,590 --> 00:34:18,219 And I've -- and those are independent, 586 00:34:18,219 --> 00:34:23,980 and I've got two solutions -- two vectors in the null space 587 00:34:23,980 --> 00:34:28,650 of A transpose, two solutions to Kirchoff's Current Law. 588 00:34:28,650 --> 00:34:31,590 Of course you would say what about sending 589 00:34:31,590 --> 00:34:34,830 current around the big loop. 590 00:34:34,830 --> 00:34:36,889 What about that vector? 591 00:34:36,889 --> 00:34:44,560 One for y1, one for y2, nothing f- on y3, one for y5, 592 00:34:44,560 --> 00:34:46,889 and minus one for y4. 593 00:34:46,889 --> 00:34:48,690 What about that? 594 00:34:48,690 --> 00:34:52,630 Is that, is that in the null space of A transpose? 595 00:34:52,630 --> 00:34:53,860 Sure. 596 00:34:53,860 --> 00:35:01,790 So why don't we now have a third vector in the basis? 597 00:35:01,790 --> 00:35:05,890 Because it's not independent, right? 598 00:35:05,890 --> 00:35:07,430 It's not independent. 599 00:35:07,430 --> 00:35:10,910 This vector is the sum of those two. 600 00:35:10,910 --> 00:35:14,200 If I send current around that and around that -- 601 00:35:14,200 --> 00:35:18,940 then on this edge y3 it's going to cancel out and I'll have 602 00:35:18,940 --> 00:35:23,080 altogether current around the whole, the outside loop. 603 00:35:23,080 --> 00:35:24,700 That's what this one is, but it's 604 00:35:24,700 --> 00:35:28,240 a combination of those two. 605 00:35:28,240 --> 00:35:33,300 Do you see that I've now, I've identified the null space of A 606 00:35:33,300 --> 00:35:36,260 transpose -- 607 00:35:36,260 --> 00:35:40,640 but more than that, we've solved Kirchoff's Current Law. 608 00:35:40,640 --> 00:35:43,160 609 00:35:43,160 --> 00:35:48,590 And understood it in terms of the network. 610 00:35:48,590 --> 00:35:49,180 OK. 611 00:35:49,180 --> 00:35:53,010 So that's the null space of A transpose. 612 00:35:53,010 --> 00:35:58,030 I guess I -- there's always one more space to ask you about. 613 00:35:58,030 --> 00:36:04,370 Let's see, I guess I need the row space of A, the column 614 00:36:04,370 --> 00:36:05,440 space of A transpose. 615 00:36:05,440 --> 00:36:10,550 616 00:36:10,550 --> 00:36:14,240 So what's N, what's its dimension? 617 00:36:14,240 --> 00:36:15,800 Yup? 618 00:36:15,800 --> 00:36:18,450 What's the dimension of the row space of A? 619 00:36:18,450 --> 00:36:21,672 If I look at the original A, it had five rows. 620 00:36:21,672 --> 00:36:22,755 How many were independent? 621 00:36:22,755 --> 00:36:27,220 622 00:36:27,220 --> 00:36:30,620 Oh, I guess I'm asking you the rank again, right? 623 00:36:30,620 --> 00:36:33,490 And the answer is three, right? 624 00:36:33,490 --> 00:36:35,610 Three independent rows. 625 00:36:35,610 --> 00:36:38,760 When I transpose it, there's three independent columns. 626 00:36:38,760 --> 00:36:42,650 Are those columns independent, those three? 627 00:36:42,650 --> 00:36:45,620 The first three columns, are they the pivot columns 628 00:36:45,620 --> 00:36:46,720 of the matrix? 629 00:36:46,720 --> 00:36:48,180 No. 630 00:36:48,180 --> 00:36:51,450 Those three columns are not independent. 631 00:36:51,450 --> 00:36:56,000 There's a in fact, this tells me a relation between them. 632 00:36:56,000 --> 00:36:57,940 There's a vector in the null space that 633 00:36:57,940 --> 00:37:01,530 says the first column plus the second column 634 00:37:01,530 --> 00:37:03,400 equals the third column. 635 00:37:03,400 --> 00:37:07,490 They're not independent because they come from a loop. 636 00:37:07,490 --> 00:37:11,570 So the pivot columns, the pivot columns of this matrix 637 00:37:11,570 --> 00:37:18,630 will be the first, the second, not the third, but the fourth. 638 00:37:18,630 --> 00:37:24,360 One, columns one, two, and four are OK. 639 00:37:24,360 --> 00:37:28,170 Where are they -- those are the columns of A transpose, 640 00:37:28,170 --> 00:37:30,350 those correspond to edges. 641 00:37:30,350 --> 00:37:35,340 So there's edge one, there's edge two, 642 00:37:35,340 --> 00:37:37,600 and there's edge four. 643 00:37:37,600 --> 00:37:42,370 644 00:37:42,370 --> 00:37:46,930 So there's a -- that's like -- 645 00:37:46,930 --> 00:37:49,040 is a, smaller graph. 646 00:37:49,040 --> 00:37:52,860 If I just look at the part of the graph that I've, that 647 00:37:52,860 --> 00:37:56,610 I've, thick -- used with thick edges, 648 00:37:56,610 --> 00:38:00,240 it has the same four nodes. 649 00:38:00,240 --> 00:38:03,400 It only has three edges. 650 00:38:03,400 --> 00:38:08,520 And the, those edges correspond to the independent guys. 651 00:38:08,520 --> 00:38:14,970 And in the graph there -- those three edges have no loop, 652 00:38:14,970 --> 00:38:15,900 right? 653 00:38:15,900 --> 00:38:19,550 The independent ones are the ones that don't have a loop. 654 00:38:19,550 --> 00:38:22,820 All the -- dependencies came from loops. 655 00:38:22,820 --> 00:38:25,800 They were the things in the null space of A transpose. 656 00:38:25,800 --> 00:38:28,140 If I take three pivot columns, there 657 00:38:28,140 --> 00:38:31,620 are no dependencies among them, and they form a graph 658 00:38:31,620 --> 00:38:34,630 without a loop, and I just want to ask you 659 00:38:34,630 --> 00:38:37,640 what's the name for a graph without a loop? 660 00:38:37,640 --> 00:38:43,590 So a graph without a loop is -- has got not very many edges, 661 00:38:43,590 --> 00:38:44,520 right? 662 00:38:44,520 --> 00:38:48,180 I've got four nodes and it only has three edges, 663 00:38:48,180 --> 00:38:53,360 and if I put another edge in, I would have a loop. 664 00:38:53,360 --> 00:38:56,390 So it's this graph with no loops, 665 00:38:56,390 --> 00:39:01,670 and it's the one where the rows of A are independent. 666 00:39:01,670 --> 00:39:04,400 And what's a graph called that has no loops? 667 00:39:04,400 --> 00:39:06,810 It's called a tree. 668 00:39:06,810 --> 00:39:11,980 So a tree is the name for a graph with no loops. 669 00:39:11,980 --> 00:39:17,290 670 00:39:17,290 --> 00:39:24,400 And just to take one last step here. 671 00:39:24,400 --> 00:39:28,170 Using our formula for dimension. 672 00:39:28,170 --> 00:39:33,710 Using our formula for dimension, let's look -- 673 00:39:33,710 --> 00:39:41,370 once at this formula. 674 00:39:41,370 --> 00:39:49,560 The dimension of the null space of A transpose is m-r. 675 00:39:49,560 --> 00:39:51,230 OK. 676 00:39:51,230 --> 00:39:58,720 This is the number of loops, number of independent loops. 677 00:39:58,720 --> 00:40:00,300 m is the number of edges. 678 00:40:00,300 --> 00:40:04,250 679 00:40:04,250 --> 00:40:05,210 And what is r? 680 00:40:05,210 --> 00:40:08,780 681 00:40:08,780 --> 00:40:12,460 What is r for our -- we'll have to remember way back. 682 00:40:12,460 --> 00:40:17,970 The rank came -- from looking at the columns of our matrix. 683 00:40:17,970 --> 00:40:19,950 So what's the rank? 684 00:40:19,950 --> 00:40:21,130 Let's just remember. 685 00:40:21,130 --> 00:40:26,710 Rank was -- you remember there was one -- 686 00:40:26,710 --> 00:40:29,750 we had a one dimensional -- rank was n minus one, 687 00:40:29,750 --> 00:40:33,690 that's what I'm struggling to say. 688 00:40:33,690 --> 00:40:37,810 Because there were n columns coming from the n nodes, 689 00:40:37,810 --> 00:40:45,030 so it's minus, the number of nodes minus one, 690 00:40:45,030 --> 00:40:50,070 because of that C, that one one one one vector 691 00:40:50,070 --> 00:40:51,920 in the null space. 692 00:40:51,920 --> 00:40:54,210 The columns were not independent. 693 00:40:54,210 --> 00:40:58,190 There was one dependency, so we needed n minus one. 694 00:40:58,190 --> 00:41:01,610 This is a great formula. 695 00:41:01,610 --> 00:41:06,230 This is like the first shall I, -- 696 00:41:06,230 --> 00:41:09,410 write it slightly differently? 697 00:41:09,410 --> 00:41:14,890 The number of edges -- let me put things -- 698 00:41:14,890 --> 00:41:17,940 have I got it right? 699 00:41:17,940 --> 00:41:22,630 Number of edges is m, the number -- r- is m-r, OK. 700 00:41:22,630 --> 00:41:24,500 So, so I'm getting -- 701 00:41:24,500 --> 00:41:27,070 let me put the number of nodes on the other side. 702 00:41:27,070 --> 00:41:31,130 So I -- the number of nodes -- 703 00:41:31,130 --> 00:41:34,890 I'll move that to the other side -- 704 00:41:34,890 --> 00:41:46,320 minus the number of edges plus the number of loops is -- 705 00:41:46,320 --> 00:41:50,060 I have minus, minus one is one. 706 00:41:50,060 --> 00:41:52,190 The number of nodes minus the number 707 00:41:52,190 --> 00:41:56,030 of edges plus the number of loops is one. 708 00:41:56,030 --> 00:41:58,460 These are like zero dimensional guys. 709 00:41:58,460 --> 00:42:01,230 They're the points on the graph. 710 00:42:01,230 --> 00:42:03,570 The edges are like one dimensional things, 711 00:42:03,570 --> 00:42:06,480 they're, they connect nodes. 712 00:42:06,480 --> 00:42:09,420 The loops are like two dimensional things. 713 00:42:09,420 --> 00:42:12,240 They have, like, an area. 714 00:42:12,240 --> 00:42:16,030 And this count works for every graph. 715 00:42:16,030 --> 00:42:22,950 And it's known as Euler's Formula. 716 00:42:22,950 --> 00:42:26,770 We see Euler again, that guy never stopped. 717 00:42:26,770 --> 00:42:28,940 OK. 718 00:42:28,940 --> 00:42:33,400 And can we just check -- so what I saying? 719 00:42:33,400 --> 00:42:37,340 I'm saying that linear algebra proves Euler's Formula. 720 00:42:37,340 --> 00:42:43,650 Euler's Formula is this great topology fact about any graph. 721 00:42:43,650 --> 00:42:45,660 I'll draw, let me draw another graph, 722 00:42:45,660 --> 00:42:51,980 let me draw a graph with more edges and loops. 723 00:42:51,980 --> 00:42:53,610 Let me put in lots of -- 724 00:42:53,610 --> 00:42:54,530 OK. 725 00:42:54,530 --> 00:42:56,500 I just drew a graph there. 726 00:42:56,500 --> 00:42:58,990 So what are the, what are the quantities in that formula? 727 00:42:58,990 --> 00:43:00,870 How many nodes have I got? 728 00:43:00,870 --> 00:43:01,630 Looks like five. 729 00:43:01,630 --> 00:43:04,180 730 00:43:04,180 --> 00:43:05,730 How many edges have I got? 731 00:43:05,730 --> 00:43:10,700 One two three four five six seven. 732 00:43:10,700 --> 00:43:12,150 How many loops have I got? 733 00:43:12,150 --> 00:43:15,010 One two three. 734 00:43:15,010 --> 00:43:19,810 And Euler's right, I always get one. 735 00:43:19,810 --> 00:43:27,700 That, this formula, is extremely useful in understanding 736 00:43:27,700 --> 00:43:31,560 the relation of these quantities -- the number of nodes, 737 00:43:31,560 --> 00:43:34,780 the number of edges, and the number of loops. 738 00:43:34,780 --> 00:43:35,970 OK. 739 00:43:35,970 --> 00:43:39,890 Just complete this lecture by completing 740 00:43:39,890 --> 00:43:42,310 this picture, this cycle. 741 00:43:42,310 --> 00:43:45,320 So let me come to the -- 742 00:43:45,320 --> 00:43:50,610 743 00:43:50,610 --> 00:43:57,200 so this expresses the equations of applied math. 744 00:43:57,200 --> 00:43:59,800 This, let me call these potential differences, 745 00:43:59,800 --> 00:44:04,100 say, E. So E is A x. 746 00:44:04,100 --> 00:44:08,010 That's the equation for this step. 747 00:44:08,010 --> 00:44:11,890 The currents come from the potential differences. 748 00:44:11,890 --> 00:44:15,020 y is C E. 749 00:44:15,020 --> 00:44:20,230 The potential -- the currents satisfy Kirchoff's Current Law. 750 00:44:20,230 --> 00:44:23,230 Those are the equations of -- 751 00:44:23,230 --> 00:44:25,290 with no source terms. 752 00:44:25,290 --> 00:44:32,590 Those are the equations of electrical circuits of many -- 753 00:44:32,590 --> 00:44:37,940 those are like the, the most basic three equations. 754 00:44:37,940 --> 00:44:41,110 Applied math comes in this structure. 755 00:44:41,110 --> 00:44:43,690 The only thing I haven't got yet in the picture 756 00:44:43,690 --> 00:44:49,260 is an outside source to make something happen. 757 00:44:49,260 --> 00:44:52,650 I could add a current source here, 758 00:44:52,650 --> 00:44:55,610 I could, I could add external currents 759 00:44:55,610 --> 00:44:57,370 going in and out of nodes. 760 00:44:57,370 --> 00:44:59,790 I could add batteries in the edges. 761 00:44:59,790 --> 00:45:01,530 Those are two ways. 762 00:45:01,530 --> 00:45:05,860 If I add batteries in the edges, they, they come into here. 763 00:45:05,860 --> 00:45:07,650 Let me add current sources. 764 00:45:07,650 --> 00:45:13,160 If I add current sources, those come in here. 765 00:45:13,160 --> 00:45:16,030 So there's a, there's where current sources go, 766 00:45:16,030 --> 00:45:22,160 because the F is a like a current coming from outside. 767 00:45:22,160 --> 00:45:25,080 So we have our edges, we have our graph, 768 00:45:25,080 --> 00:45:33,370 and then I send one amp into this node and out of this node 769 00:45:33,370 --> 00:45:36,970 -- and that gives me, a right-hand side 770 00:45:36,970 --> 00:45:38,840 in Kirchoff's Current Law. 771 00:45:38,840 --> 00:45:41,290 And can I -- to complete the lecture, 772 00:45:41,290 --> 00:45:45,420 I'm just going to put these three equations together. 773 00:45:45,420 --> 00:45:49,240 So I start with x, my unknown. 774 00:45:49,240 --> 00:45:51,350 I multiply by A. 775 00:45:51,350 --> 00:45:53,520 That gives me the potential differences. 776 00:45:53,520 --> 00:45:57,100 That was our matrix A that the whole thing started with. 777 00:45:57,100 --> 00:45:59,720 I multiply by C. 778 00:45:59,720 --> 00:46:03,280 Those are the physical constants in Ohm's Law. 779 00:46:03,280 --> 00:46:05,500 Now I have y. 780 00:46:05,500 --> 00:46:12,270 I multiply y by A transpose, and now I have F. 781 00:46:12,270 --> 00:46:16,660 So there is the whole thing. 782 00:46:16,660 --> 00:46:22,870 There's the basic equation of applied math. 783 00:46:22,870 --> 00:46:28,700 Coming from these three steps, in which the last step is 784 00:46:28,700 --> 00:46:30,140 this balance equation. 785 00:46:30,140 --> 00:46:33,560 There's always a balance equation to look for. 786 00:46:33,560 --> 00:46:34,880 These are the -- 787 00:46:34,880 --> 00:46:37,350 when I say the most basic equations of applied 788 00:46:37,350 --> 00:46:37,980 mathematics -- 789 00:46:37,980 --> 00:46:41,500 I should say, in equilibrium. 790 00:46:41,500 --> 00:46:43,820 Time isn't in this problem. 791 00:46:43,820 --> 00:46:47,800 I'm not -- and Newton's Law isn't acting here. 792 00:46:47,800 --> 00:46:51,230 I'm, I'm looking at the -- equations when everything has 793 00:46:51,230 --> 00:46:54,110 settled down, how do the currents distribute 794 00:46:54,110 --> 00:46:55,780 in the network. 795 00:46:55,780 --> 00:47:00,480 And of course there are big codes to solve the -- 796 00:47:00,480 --> 00:47:04,860 this is the basic problem of numerical linear algebra 797 00:47:04,860 --> 00:47:09,190 for systems of equations, because that's how they come. 798 00:47:09,190 --> 00:47:13,320 And my final question. 799 00:47:13,320 --> 00:47:18,940 What can you tell me about this matrix A transpose C A? 800 00:47:18,940 --> 00:47:21,400 Or even A transpose A? 801 00:47:21,400 --> 00:47:24,310 I'll just close with that question. 802 00:47:24,310 --> 00:47:28,280 What do you know about the matrix A transpose A? 803 00:47:28,280 --> 00:47:32,400 It is always symmetric, right. 804 00:47:32,400 --> 00:47:33,350 OK, thank. 805 00:47:33,350 --> 00:47:38,590 So I'll see you Wednesday for a full review of these chapters, 806 00:47:38,590 --> 00:47:41,230 and Friday you get to tell me. 807 00:47:41,230 --> 00:47:42,780 Thanks. 808 00:47:42,780 --> 00:47:56,858