Showing that A-transpose x A is invertible

OK. I've got some matrix A. It's an n by k matrix. Let's say it's not just any n by k matrix. This matrix A has a bunch of columns that are all linearly independent. So, a1. a2, all the way through ak are linearly independent. They are linearly independent columns. Let me write that down. a1, a2, all the column vectors of A. All the way through ak are linearly independent. Now, what does that mean? That means that the only solution to x1 times a1 plus x2 times a2, plus all the way to xk times ak. The only solution to this is all of these x's have to be 0. So, all xi's must be equal to 0. That's what linear independence implies. Or another way to write it is all the solutions to this equation x1, x2, all the way down to xk equaling the zero vector. That all the solutions to this are all of these entries have to be equal to 0. This is just another way of writing this right there. We've seen it multiple times. That's the zero vector right there. So if all of these have to be 0, that's like saying that the only solution to ax is equal to 0, is x is equal to the zero vector. Or another way to say it-- this is all coming out of the fact that this guy's columns are linearly independent. So linear independence of columns. Based on that, we can say, since the only solution to ax is equal to 0 is x is equal to the zero vector, we know that the null space of a must be equal to the zero vector. Or it's a set with the just the zero vector in it. And that is all a bit of review. Now, n by k. We don't know its dimensions. It may or may not be a square matrix. So we don't know, necessarily, whether it's invertible and all of that. But maybe we can construct an invertible matrix with it. So, let's study a transpose times a. a transpose times a. A is an n by k matrix. A transpose will be a k by n matrix. So, A transpose a is going to be a k by k matrix. So it's a square matrix. So that's a nice place to start for an invertible matrix. So let's see if it is actually invertible. We don't know anything about A. All we know is its columns are linearly independent. Let's see if A transpose a is invertible. Essentially, to show that it's invertible, if we can show that all of its columns are linearly independent, then we'll know it's invertible. If we have any-- and I'll get back to this at the end of the video. But if you have a square matrix with linearly independent columns-- remember, the linearly independent columns all are associated with pivot columns when you put them in reduced row echelon form. So if you have a square matrix, then you're going to have exactly-- so if it's a k by k matrix, that means you're going to have k-- that means that the reduced row echelon form of a matrix will have k pivot columns and be k by k. And be a square k by k matrix. And there's only one k by k matrix with k pivot columns. And that's the identity matrix. The k by k identity matrix. And if when you do something to reduce row echelon form, and it you got the identity matrix, that means that your matrix is invertible. I could have probably left that to the end of the video, but I just want to show you. If we can show that-- we already know that this guy's square, that a transpose A is a square matrix. If we can show that, given that a has linearly independent columns, that a transpose times A also has linearly independent columns, and given the columns are linearly independent, and it's a square matrix, that tells us that when we put it into reduced row echelon form, we'll get the identity matrix. And that tells us that this thing would be invertible. Let's see if we can prove that all of this guy's columns are linearly independent. So let's say I have some vector V. Let's say my vector V is a member of the null space of a transpose A. That means that if I take a transpose A times my vector v, I'm going to get the zero vector. Fair enough? Now, what happens if I multiply both sides of the equation times the transpose of this guy? So I'll get a v transpose-- actually let me just do it right here. I multiply v transpose on this side, and v transpose on this side. You could view this as a matrix vector product. Right? Or, in general, if you take a row vector times a column vector, it's essentially their dot product. So this right-hand side of the equation, you dot anything with the zero vector. That is just going to be the zero vector. Now what is the left-hand side of this going to be? We've seen this before. If you have the transpose of-- we can view this as, even though it's a transpose of a vector, you can view it as a-- it is a row factor, but you could also view it as a matrix. Right? Let's say v is a k by 1 matrix. v transpose will be a 1 by k matrix. We've seen this before. That that is equal to the reverse product, the transpose of the reverse product. Or if we take the product of two things and transpose it, that's the same thing as taking the reverse product of the transposes of either of those two matrices. So given that, we can replace this right here with a times a vector v transpose-- and we're multiplying this vector times av times this vector right here. And that is going to be equal to the zero vector. Now, what is this? If I'm taking some vector's transpose, and let's say this is a vector. Remember, even though I have a matrix vector product right here, when I multiply a matrix times this vector, it will result in another vector. So this is a vector, and this is a vector right here. And if I take some vector and I multiply its transpose times that vector-- we've seen this before. That is the same thing as y dot y. These two statements are identical. So this thing right here is the same thing as av dot av. And so what does the right-hand side equal? The right-hand side is going to be equal to 0. Actually let me just make a correction up here. When I take v transpose times the zero vector, v transpose is going to have k elements. And then the zero vector is also going to have k elements. And when I take this product that's like dotting it. You're taking the dot product of v and 0. So this is a dot product of v with the zero vector which is equal to zero, the scalar zero. So this right here's the scalar zero. I want to make sure I clarify that. It wouldn't make sense otherwise. So the right-hand side, when I multiply the zero vector times the transpose of v, gets just the number zero. No vector zero there. So this av dot av is going to be equal to 0. Or we could say that the magnitude, or the length, of av squared is equal to 0. Or that tells us that av has to be equal to 0. The only vector whose length is 0, is the zero vector. So av-- let me switch colors. Using that a little bit too much. So we know that av must be equal to 0, to the zero vector. This must be equal to the zero vector since its length is 0. Now, we started off with saying v is a member of the null space of a transpose A. v can be any member of the null space of a transpose A. But then from that assumption, it turns out that V also has to be a member of the null space of A. That av is equal to 0. Let's write that down. If v is a member of the null space of a transpose A, then v is a member of the null space of a. Now, our null space of A, because A's columns are linearly independent, it only contains one vector. It only contains the zero vector. So, if this guy's a member of the null space of A transpose A, and he has to be a member of the null space of A, there's only one thing he can be. There's only one entry there. So then v has to be equal to the zero vector. Or another way to say that is, any v that's in our null space of a transpose A has to be the zero vector. Or the null space of a transpose A is equal to the null space of a which is equal to just the zero factor sitting there. Now, what does that do for us? That tells us that the only solution to a transpose A times some vector x equal to zero, this says that the only solution is the zero vector is equal to the zero vector. Right? Because the null space of a transpose A is the same as the null space of a. And that just has the zero vector in it. The null space is just the solution to this. So if the only solution to the null space is this, that means that the columns of a transpose A are linearly independent. You could, essentially, write all of the linear combinations of the columns by the weights of the entries of x. We actually did that at the beginning. It's the same argument we used up here. So if all of their columns are linearly independent, and I said it over here, a transpose A has linearly independent columns, and it's a square matrix, that was from the definition of it. So we now know that A transpose A if I were to put it-- let me do this way. That tells me that the reduced row echelon form of a transpose A is going to be equal to the k by k identity matrix which tells me that a transpose A is invertible. Which is a pretty neat result. I started with the matrix that has linearly independent columns. So it wasn't just any matrix. It wasn't just any run of the mill matrix. It did have linearly independent columns, but it might have weird dimensions. It's not necessarily a square matrix. But I could construct a square matrix. a transpose A with it. And we now know that it also has linearly independent columns. It's a square matrix. And therefore it is invertible.