Transcript

okay this is linear algebra lecture 11 and at the end of lecture 10 I was talking about some Vector spaces but there the the things in those Vector spaces were not what we usually call vectors nevertheless you could add them and you could multiply by numbers so we can call them vectors I think the example I was working with they were matrices so the m so we had like a matrix space the space of all 3x3 matrices and I'd like to just pick up on that because uh we've been so specific about n dimensional space here here and you really want to see that the same ideas work as long as you can add and multiply by scalers so these new new Vector spaces the example I took was the space m of all 3x3 matrices okay I can add the I can multiply by scalers I can multiply two of them together but I don't do that that's not part of the vector space picture the vector space part is just adding the matrices and multiplying by numbers and that's fine we all we stay within this space of 3x3 matrices and I had some subspaces that were interesting like the symmetric the Subspace of symmetric matrices symmetric 3x3 or the Subspace of upper triangular 3x3 now I I use the word Subspace because it follows the rule that if I add two symmetric matrices I'm still symmetric If I multiply two symmetric matrices is the product automatically symmetric no but I'm not multiplying matrices I'm just adding so I'm fine these this is a Subspace similarly if I add two upper triangular matrices I'm still upper triangular and uh that's a Subspace now I just want to take these as examples and ask well what's the basis for that Subspace what's the dimension of that Subspace and what's the dimension of the whole Space so uh there's a natural basis for all 3x3 matrices and why don't we just write it down so so M A basis for M again all 3x3 okay and then I'll just count how many members are in that basis and I'll know the dimension and okay it's going to take me a little time in fact what is the dimension what any idea of what I'm what I'm coming up with next how many numbers does it take to specify that 3x3 Matrix nine nine is the is the dimension I'm going to find and the most obvious basis would be the Matrix that's that Matrix and then this Matrix with a one there and that's two of them so I put in the third one and then onwards and the last one maybe would end with the one okay that's like the standard basis in fact our space is practically the same as nine-dimensional space it's just the nine numbers are written in a square instead of in a column but somehow it's different and and ought to be thought of as uh in sort of natural for itself because now what about the symmetric 3x3 so that's a Subspace just let's just think what's the dimension of that Subspace and what's a basis for that Subspace okay and I guess this question occurs to me if I look at this Subspace of symmetric 3x3 well how many of these original basis members belong to the Subspace I think only three of them do that this one is symmetric this last one is symmetric and the one in the Middle with a with a one in that position in the 2 two position would be symmetric but so I've got three of these original nine are symmetric but uh so this is an example where but that's that's not all right what's the dimension let's put the dimensions down dimension of the of m was nine what's the dimension of should we call this s is what what what's the dimension of this I'm I'm sort of taking simple examples where we can we can uh spot the answer to these questions so how many if I have a symmetric think of all symmetric matrices as a Subspace how many parameters do I choose in 3x3 symmetric matrices six right if I choose the diagonal that's three and the three entries above the diagonal then I know what the three entri is below so the dimension is six I guess what's the dimension of this here let's call this space u for upper triangular so what's the dimension of that space of all upper triangular 3x3 again six again six and uh but we haven't got a we haven't seen a b well actually maybe we have got a basis here for uh the upper triangulars I guess six of these guys one two three four and and a couple more would be upper triangular so there's an accidental case where the big basis contains in it a basis for the Subspace but with the symmetric guy it didn't happen the symmetric guy the the basis so you see what a basis is the basis for the big space we generally need to think it all over again to get a basis for the Subspace and then how do I get other subspaces well uh we spoke before about uh the Subspace the symmetric matrices and the upper triangle this is symmetric and upper triangular okay what's the uh what's the dimension of that space what's in that space so what's a m if a matrix is symmetric and also upper triangular that makes it diagonal so this is the same as the diagonal matrices diagonal 3x3 and the dimension of this of s intersect U right you're okay with that symbol that's that's the vectors that are in both s and U and that's D so s intersect U is the diagonals and the dimension of the diagonal matrices is three and we've got a basis no problem okay as I write that I think okay what about putting get so this is like this intersection is taking all the vectors that are in both that are that are symmetric and also upper triangular now we looked at the union suppose I take the matrices that are symmetric or upper triangular what why was that no good so why is why is it no why is why am I not interested in the union putting together those two subspaces so this these are matrices that are in s or in U or possibly both so they the diagonals included but what's bad about this it's it's not a Subspace it's like having taking you know a couple of lines in the plane and stopping there a line this is so there's a three-dimensional Subspace of a nine-dimensional space there's oh sorry six there's a six-dimensional Subspace of a nine-dimensional space there's another one but they they're headed in different directions so it we can't just put them together we have to fill in so that's what we do to get get this bigger space that I'll write with a plus sign this is combinations of things in s and things in U okay so that's that's the final space I'm going to introduce I have a a couple of subspaces I can take their intersection and now I'm interested in not their Union but their sums so this would be the this is the intersection and this will be their sum so what's what do I need for a for a Subspace here I take anything in S Plus anything in U I don't just take things that are in s and pop in also separately things that are in youu this is the sum of any element of s that is any symmetric Matrix plus any in U any element of U okay now as long as we've got an example here tell me what we get if I take every symmetric Matrix take all symmetric matrices and add them to all upper triangular matrices then I've got a whole lot of matrices and it is a Subspace and what's it or it's a vector space and what Vector space would I then have any idea what what matrices can I get out of a symmetric plus an upper triangular I can get anything I get all matricies I get all 3x3 it's worth thinking about that it's just like stretch your mind a little just a little to to think of these subspaces and what their intersection is and what their sum is and now can I give you a little oh let's figure out the dimension so what's the dimension of S Plus u in this example is nine cuz we got all three by3 so the original spaces had the original symmetric space had Dimension six and the original upper triangular space had Dimension six and actually I'm seeing here a nice formula that the dimension of S Plus the dimension of U if I have two subspaces the dimension of one plus the dimension of the other other equals the dimension of their intersection plus the dimension of their sum 6 + 6 is 3 + 9 it's kind of satisfying that these natural operations and we these this is it actually this is the this is the the the set of natural things to do with with subspaces that uh the dimensions come out in a good way okay maybe I'll take just one more example of a vector space that doesn't have vectors in it it's it say take come from differential equations so this is a one more new Vector space that we'll give just a few minutes to suppose I have a differential equation like DC y dx2 + y = 0 okay I look at the solutions to that equation so what are the solutions to that equation y equal cos x is a solution y = sinx is a solution y = well e to the IX is a solution if you want if you allow me to put that in oh but why should I put that in it's already there I'm you see I'm really looking at a null space here I'm looking at the null space of a differential equation that's the solution space and describe the solution space all solutions to this differential equation so the equation is y Prime + y = 0 cosine cosine is a solution s is a solution now tell me all the solutions there're so I don't need e to the iix forget that what are all the what are all the complete solution is what a combination of these the complete solution is y = Su multiple of the cosine plus Su multiple of the sign that's a vector space that's a vector space what's the dimension of that space what's the basis for that space okay let me ask you a basis first if I take the set of solutions to that second order differential equation there it is those are the solutions what's a basis for that space now remember what's the what question am I asking because if you know the question I'm asking you'll see the answer a basis means all the guys in the space are combinations of these basis vectors well this is a basis sinx cos x there is a basis those two you they're like the special Solutions right we had special solutions to axal B now we've got special solutions to differential equations sorry we had special solutions to ax equals z I misspoke the special Solutions were for the null space just as here we're talking about the null space do you see that here is a those two and what's the dimension of the solution space is how many vectors in this basis two the sign and cosine are those the only basis for the space by no means e to theix and e to the minus I would be another basis lots of bases but you see that really what a course in differential in linear differential equations is about is finding a basis for the solution space the dimension of the solution space will always be will be two because we have a second order equation so that's like there's 1803 in 5 minutes of 1806 is enough to take care of 1803 okay so there's a that's one more example and of course the point of the example is these things don't look like vectors they look like functions but we can call them vectors because we can add them and we can multiply by constants so we can take linear combinations that's all we have to be allowed to do so that's really why this idea of linear algebra and basis and dimension and so on plays a wider role than than than our constant discussions of n byn matrices okay that's what I wanted wanted to say about that topic now of course the key uh number associated with matrices to go back to that number is the rank and the rank what do we know about the rank well we know it's not bigger than M and it's not bigger than n so but I'd like to have a little discussion on the rank maybe I'll put that here so I'm picking up this topic of rank one matrices and the reason I'm interested in rank one matrices is that they ought to be simple if the rank is only one The Matrix can't get away from us so for example let me take let me create a rank one Matrix okay suppose it's 3 suppose it's 2x3 and let me give you the first row what's what can the second row be what tell me a possible second row here for for this Matrix to have rank one a possible second row is 2810 the second row is a multiple of the first row it's not independent so tell me a basis for the oh yeah sorry to keep bringing up these same questions after the quiz I'll stop but for now tell me a basis for the row space a basis for the row space of that Matrix is the first row right the first row 145 a basis for the column space of this Matrix is what's the dimension of the column space the dimension of the column space is also one right because it's also the rank the dimension you remember the dimension of the column space equals the rank equals the dimension of the column space of the transpose which is the row space of a okay and in this case it's one R is one and sure enough all the columns are all the other columns are multiples of that column now there's there ought to be a nice way to see that and here it is is I can write that Matrix as it's pivot column 1 2 times it's time 145 a column time a row one column time one row gives me a matrix right if I multiply a column by a row that that's 2x one Matrix times a 1x3 matrix and the result of the multiplication is 2x3 and it comes out right so what I want to my my point is that rank one matrices that every rank one Matrix has the form sum column times sum row so U is a column vector v is a column Vector but I make it into a row by putting in V transpose so that's the that's the uh that's the complete picture of rank one matrices we'll be interested in rank one matrices later we'll find oh their determinant that'll be easy their igen values that'll be interesting uh rank one matrices are like the building blocks for all matrices and actually maybe you can guess and if I took any Matrix a 5 by 17 Matrix of rank four then it seems pretty likely and it's true that I could break that 5x 17 Matrix down as a combination of rank one matrices and probably how many of those would I need if I have a 5x 17 Matrix of rank four I'll need four of them four rank one matrices so the rank one matrices are the are the building blocks and out I can produce every I can produce every five every rank four Matrix out of four rank one matrices okay that brings me to a question of course would the rank four matrices form a Subspace let me take all 5 by 17 matrices and think about rank four M the the subset of rank four matrices let me I'll write this down you see I'm I'm reviewing for the quiz because because I'm asking the kind of questions that are short enough but that bring out do you know what these words mean so I take my Matrix bace n now is all 5 5 17 Matrix and now the sub the the question I ask is the subset of of rank four mates is that a Subspace if I add a matrix of so if I multiply a matrix of rank four by of rank four or less let's say because I have to let the zero Matrix in if it's if it's going to be a Subspace but that doesn't just because the zero Matrix got in there doesn't mean I have a Subspace so if I so the the question really comes down to if I add two rank four matrices is the sum rank four what do you think no not usually not usually if I add two rank four matrices the sum is probably what could I say about the sum well actually well the rank could be if it's a general fact actually that the rank of a plus b can't be more than rank of a plus the rank of B so this would say if I added two of those the rank couldn't be larger than eight but I know actually the rank couldn't be as large as eight anyway what how big could the rank be for the rank of a matrix in M could be as large as right right so they're all sort of natural ideas so rank four matrices or rank one matrices let me let me change that to rank one let me take the subset of rank one matrices is that a vector space if I add a rank one Matrix to a rank one Matrix no it's most likely going to have rank two so this is so I'll just make that point not a Subspace okay okay those are topics that I wanted to uh just fill out the the previous lectures I'll ask one more Subspace question a more a more uh likely example suppose I'm in let me put put this example on a new board suppose I'm in our in R4 so my typical my my typical Vector in R4 has four components V1 V2 V3 and V4 suppose I take the Subspace of vectors whose components add to zero so I let s be all V all vectors V in four dimensional space with V1 + V2 + V3 + V4 = Z so I just want to consider that bunch of vectors is it a Subspace first of all it is a Subspace it is a sub space what's how do we see that it is a Subspace I formally I should check if I have one vector that with whose components add to zero and I multiply that vector by six the components still add a zero just six * 6 * Z if I have a couple of V and a w and I add them the components still add to zero okay it's a Subspace what's the dimension of that space and what's the basis for that space so you see how I can just describe a space and we we can ask for the dimension as for the basis first and the dimension course the dimension is the one that's easy to tell me in a single word what's the dimension of our Subspace s here and a basis tell me a tell me some vectors in it well I'm going to make you ask you again to guess the dimension again I think I heard it three the dimension is three how does this connect to our axal Z is this the n space of something is that the null space of a matrix and then we can look at the Matrix and and we know everything about those subspaces this is the null space of what Matrix what's the Matrix where the null space is then AV = 0 so I want this equation to be a = z v is now the vector and what's the Matrix that that we're seeing there it's the Matrix of 41 do you see that that's that if I look at AAL Z for this Matrix a I multiply by B and I get this requirement that the components add to zero so I'm really at when I speak about s I'm speaking about the no space of that Matrix okay let's just say we've got a matrix now we want it null space well wait tell me it's rank first the rank of that Matrix is one thanks so R is one what's the general formula for the dimension of the null space the dimension of the null space of a matrix is in general an M byn Matrix of rank R how many independent guys in the null space n- r right N - R in this case is four four columns the rank is one so the no space is three dimensional so of course you could see it in this case but you can also see it here in our systematic way of dealing with the four fundamental subspaces of a matrix so what actually what what are all four subspaces then the RO row space is clear the row space is in R4 yeah can can can we take the four fundamental subspaces of this Matrix this's just kill this example the row space is onedimensional it's it's all multiples of that of that Row the null space is threedimensional oh you better give me a basis for the null space so what the basis is for the n space the special solutions to find the special Solutions I look for the free variables the free variables here are there's the pivot the free variables are 2 three and four so the basis basis for S for S will be I'm expecting three vectors Three Special Solutions I give the value one to that three variable and what's the pivot variable if the this is going to be a vector in s minus one now the rows add to Z the the entries add to zero the second special solution has a one in the second free variable and again a minus1 makes it right the third one has a one in the third free variable and again A minus one makes it right that's my answer that's the answer I would be looking for the a basis for the Subspace s you would just list three vectors and those would be the natural three to list not the only possible three but the the those are the special three okay tell me about the column space what's the column space of this Matrix a so the column space is a Subspace of r one because m is only one The Columns only have one component so the column space of s the column space of a is somewhere in the space R1 because we only have these col colums are short and what is the column space actually I just it's just talking with these words is what I'm doing the column space for that Matrix is R1 the column space for that Matrix is all multiples of that column there there's and all multiples give you all of R1 and what's the the remaining fourth space the null space of a transpose is what so we transpose a we look for combinations of the of of the of the columns now that gives zero for for a transpose and there aren't any the only thing the only combination of these rows to give the zero row is the zero combination okay so let's just check Dimensions the null space has Dimension three the row space has Dimension 1 3 + 1 is 4 the column space has Dimension One and what's the dimension of this like smallest possible space what's the dimension of the zero space it's a it's a Subspace zero what else could it be I mean let's we have to take a reasonable answer and the only reasonable answer is zero so one plus 0 gives this was n the number of columns and this is M the number of rows and let's just let me just say again then the the the Subspace that has only that one point that point is Zero Dimensional of course and the basis is empty because if if the dimension is zero there shouldn't be anybody in the basis so the basis of that smallest Subspace is the empty set and the the number of members in the empty set is zero so that's the dimension okay good now I have just five minutes to to tell you about well actually about some some some this is now this last topic of small world graphs and leads into uh a lecture about graphs and linear algebra but let me tell you the in these last minutes the graph that I'm interested in uh it's the graph where so what is a graph better tell you that first okay what's a graph okay this isn't calculus we're not I'm not thinking of like some sign curve the word graph is used in a complete different way it's a set of a bunch of nodes and edges edges connecting the nodes so I have nodes like five nodes and edges I'll put in some edges I could could include them all there's well let me put in a couple more there's a graph with five nodes and 1 2 3 4 five six edges and some 5x6 Matrix is going to tell us everything about that graph let me leave that Matrix the next time and tell you about the question I'm interested in suppose suppose the graph isn't just just doesn't have just five nodes but suppose every suppose every person in this room is a node and suppose there's an edge between two nodes if those two people are friends so have I described a graph it's a pretty big graph 100 hundred nodes and I don't know how many edges are in there there's an edge if you're friend I so that's the graph for this class a similar graph you could take for the whole country so 260 million nodes and edges between friends and the question for that graph is how many steps does it take to get from anybody to anybody what's what two people are furthest apart in this friendship graph say for the US by furthest apart I mean the distance from well I'll tell you my distance to Clinton it's two I happen to go to college with somebody who knows Clinton I don't know so my distance to Clinton is not one cuz I don't happily or not don't know him but I know somebody who does he's a senator and so I presume he knows it okay I don't know what your well what's your distance to Clinton well not more than three right actually true you know me I take credit for reducing your Clinton distance uh what's your distance to Monica uh not um anybody below below four is in trouble here uh or maybe three but uh right so uh what's Hillary's distance to mon I don't think we better put that on the tape here one or two I guess is that right I don't well we won't think more about that so actually the the real question is what's what are big large distances who how how far apart could people be separated and roughly this number six degrees of separation has kind of appeared it's a movie title it's a book title and it's with this meaning that that roughly speaking uh six might be a fairly not too many people if you sit next to somebody on an airplane you get talking to them you begin to discuss mutual friends to sort of find out okay what connections do you have and very often you'll find you're connected in like two or three or four steps and you remark It's a small world and that's how this expression small world came up uh but six I don't know if you could find if it took six I don't know if you would successfully discover those six in a in an airplane conversation but here's the math question and I'll leave it for next for lecture 12 and do a lot of linear algebra in lecture 12 but the qu the the interesting point is that with a few shortcuts the distances come down dramatically that that uh I mean all your distances to Clinton immediately drop to three by taking linear Al that's like extra bonus for taking linear Al uh and to understand mathematically what it is about these graphs or like the graphs of the worldwide web there's a fantastic graph so many people would like to understand and model the web what are the con where the edges are links and the nodes are are sites websites uh I'll leave you with that grab and I'll see you have a good weekend and see you on Monday