Lecture 27

IIT Kanpur July 201
20 followers
Oct 22, 2023
We have now seen that we can solve equations using Gaussian elimination.
In fact, we can write a computer program for solving large set of equations using Gaussian
eliminations without any knowledge of matrix algebra whatsoever.
However, if we can connect the operations of Gaussian elimination with matrix algebra,
we can go much deeper into Gaussian elimination process.
We can compare Gaussian elimination process with other techniques and most importantly
we can improve Gaussian elimination process.
In fact, we will see that in terms of matrix algebra, the operations of Gaussian elimination
can be seen as the elementary row operations in a matrix.
Elementary row operation in a matrix can be identified as a multiplication of a matrix
by an elementary matrix.
And in Gaussian elimination, we start from an equation Ax is equal to b, we go up to
ux equals b prime at the end of forward elimination.
We will see in this lecture that u is given by number of elementary matrices multiplied
by the original a matrix and same elementary matrices when multiplied with b, we get the
b prime a new column vector.
This understanding will be very important for our subsequent topics in linear algebra.
Elementary row operations in a matrix primarily means three types of operations, row swap,
scalar multiplication of a row, and summation of two or more rows.
A combination of such elementary operations creates complex operations as well.
Let us see an example.
Let us take a 3x3 matrix 2-1-3, 4-2-1, 3-1-2.
We convert this matrix into 4-2-1, 2-1-3, 3-1-2.
We can see clearly that the operation that we have done here is a row swap operation.
We have swapped rows 1 and 2.
Everything else remains same here.
Once again, we take the same matrix 2-1-3, 4-2-1, 3-1-2.
And we create a new matrix 4-2-6, 4-2-1, 3-1-2.
We can clearly see that what we did here is that we have multiplied row 1 by 2.
Everything else remains just the same.
Finally, we take the same matrix again 2-1-3, 4-2-1, 3-1-2.
And we convert this to 2-1-3, 6-1-2, 3-1-2.
Here you can see only row 2 is changed.
And how it is changed?
Row 2 in the new matrix is the row 1 plus row 2 of the old matrix.
So this is a row sum operation.
Now these simple operations can be shown as pre-multiplication with elementary matrix
E. And what does an elementary matrix mean?
An elementary matrix E comes from elementary row operation on an identity matrix I.
All of you know identity matrix.
Identity matrix is essentially a square diagonal matrix and it has 1 at its diagonal and all
other elements in this matrix are 0.
Now let us come back to these three basic operations that we have just seen.
The first one is row swap, second one is scalar multiplication, and third one is row sum.
Now how can I write this operation in terms of a multiplication of an elementary matrix
with the original matrix?
Here you can see that I can write this 4-2-1, 2-1-3, 3-1-2 as a product of 010100001 multiplied
by the original matrix 2-1-3, 4-2-1, 3-1-2.
If it is not very much clear to you, you can go back in lecture and see the rules of
matrix multiplication.
When I multiply the matrix A here that is 2-1-3, 4-2-1, 3-1-2 by 010, then in the product
the first matrix will be a linear combination of rows of this original matrix.
How that linear combination will be made?
The first row will be multiplied by 0, plus second row multiplied by 1, plus third row
multiplied by 0, which essentially means the second row of the original matrix here will
go as the first row here.
Similarly, you see that here 100 is multiplied when it is multiplied, it tells us that the
second row of the product will be given by 1 multiplied by first row of the original matrix,
plus 0 multiplied by second row of original matrix, plus 0 multiplied by third row of
original matrix, which essentially means the second row of the product will be same as
first row of the original matrix.
If it is not clear to you, you can perform an actual matrix multiplication and see what
happens.
Now you see that the matrix that we have used for pre-multiplication 0, 1, 0, 1, 0, 0, 0,
0, 1, this is an elementary matrix.
Why we call this an elementary matrix?
This is called elementary matrix because this matrix come from elementary row operation
of unit matrix.
Our unit matrix is 1, 0, 0, 0, 1, 0, 0, 0, 1.
If I swap row 1 and row 2 of the unit matrix, we get this matrix E. So, this matrix E comes
from elementary row operation of unit matrix and thus this is called an elementary matrix.
Also this particular matrix in this case is a permutation matrix.
This is also a permutation matrix.
You remember this permutation matrix will be important for us later.
A permutation matrix is very similar to an unit matrix.
In a permutation matrix, we have 1, 1 in every row and in every column and remaining elements
are 0.
So, a permutation matrix essentially comes from elementary operation of unit matrix.
So, not necessarily just elementary operation, this is the row swap or column swap of unit
matrix.
Now, let us come to the scalar multiplication.
In scalar multiplication, the top row here is multiplied by 2 and we can write this in
terms of pre-multiplication with elementary matrices 2, 0, 0, 0, 1, 0, 0, 0, 1 multiplied
by the original matrix.
So, you can see that the second row and third row it contains only 1 at the diagonal and
rest are 0.
So, the second row and third row of the product will not change at all.
The first row of the multiplier is 2, 0, 0 which means the product will be 2 multiplied
by top row, then 0 multiplied by second row plus 0 multiplied by third row which essentially
twice the first row.
Now this 2, 0, 0, 0, 1, 0, 0, 0, 1 this matrix is also an elementary matrix because this
matrix come from the multiplication of 2 to the unit matrix.
So, essentially this matrix comes from elementary operation over the unit matrix 1, 0, 0, 0,
1, 0, 0, 0, 1.
So, this is once again an elementary matrix.
Third is the row sum here you can see that the second row of my original matrix is replaced
by a sum of first row and second row.
Now I can write this as a pre-multiplication by a matrix 1, 0, 0, 1, 1, 0, 0, 0, 1.
This pre-multiplication will not change row 1 and row 3 because they are simply at the
diagonal 1 and otherwise it is 0.
But in case of second row I can see that this is 1, 1.
So, in the product the second row will be 1 multiplied by row 1 plus 1 multiplied by
row 2 plus 0 multiplied by row 3 which essentially means that the second row of the product will
be the first row and second row of the original matrix sum of them.
And you can clearly see that the matrix 1, 0, 0, 1, 1, 0, 0, 0, 1 which is the pre-multiplier
here that once again is an elementary matrix because this matrix come from the row sum
of elementary matrix.
In the elementary matrix if I sum row 1 and row 2 and replace row 2 by this sum then I
get 1, 0, 0, 1, 1, 0, 0, 0, 1.
So, this is coming from the unit matrix this is an elementary matrix.
So now it is clear that the elementary operation in a matrix is same as pre-multiplying the
matrix with elementary matrices.
And elementary matrices are coming from the elementary operation of unit matrix.
Let us now come back to the Gaussian elimination.
This is an example that you know 2, – 1, 3, 4, 2, – 1, 3, 1, 2 and then X1, X2, X3
are the unknown.
I have the column vector b 1, – 8 and 1.
We know that if we want to perform Gaussian elimination over it my goal is to bring 0
in place of 4 and then 0 in place of 3.
So let us take the first operation and let us bring 0 in place of 4.
How do you do it?
To do it we multiply the equation 1 in this case the row 1 by – 2 and then I add it
to equation 2 in this case the row 2 and this will be my new equation 2 means this will
be my new row 2.
How can I write this in terms of an elementary matrix multiplication?
Let us say I have an elementary matrix e 1 multiplied with the original system of equation
we have to multiply both side of course.
What could be the elementary matrix?
You see that the Gaussian elimination operation here the connection between the original matrix
and the elementary matrix is that the original matrix is transformed to this matrix via row
2 – 2 multiplied by row 1 plus row 2.
So nothing happens to row 1 that means my elementary matrix top row will be 1 0 0 nothing
happens to row 3.
So the third row is also 0 0 1.
Things happen to second row only.
Second row is replaced by – 2 multiplied by top row and the original second row which
means that the – 2 1 0 is my second row.
That means I have my e 1 1 0 0 – 2 1 0 0 0 1 I have to now multiply this e 1 to both
sides of the matrix.
So e 1 when I multiply with the column vector you can verify that this e 1 multiplied by
column vector 1 – 8 1 will be 1 – 10 1.
This is very easy to see because nothing will happen in row 1 and row 3 same as before
we are discussing for the A matrix here.
So when I am multiplying e 1 this is an elementary matrix I am multiplying with 1 – 8 1.
Because the top row of elementary matrix is 1 0 0 so nothing will happen to row 1.
Similarly third row is 0 0 1 nothing happens to row 3.
But the second row – 2 and 1 so – 2 of the top row plus 1 of second row that means
– 2 – 8 is – 10 and that is exactly what is happening on the right hand side of
my matrix equation.
We can go one step further and we can see that this e 1 does not look like an elementary
matrix because it looks like more complicated than an elementary matrix.
But this comes actually from a combination of three elementary operations.
So what are these elementary operations?
So in first operation what we do is that we multiply the first row here this 2 – 1 3
with – 2 we do not do anything in other rows.
Then comes second operation in second operation I add first row and second row.
Recall my first row is already multiplied by – 2.
Now I add them up and then in third operation I have to go back to the original first row.
So what I do is that I multiply the first row by – half I do not do anything to other
rows and I get 1 0 0 – 2 1 0 0 0 1.
So this is how although I am writing e 1 which does not look like an elementary matrix but
it is in itself hiding three elementary matrices.
Similarly I can go ahead and I can my next step in Gaussian elimination that I have to
take this 3 and I have to make it 0.
So let us say I want to multiply e 2 another elementary matrix but I have to multiply once
again both side.
And once I multiply you will see that this is something that we have discussed before.
The matrix that you will get through Gaussian elimination is 2 – 1 3 0 4 – 7 0 5 by
2 – 5 by 2.
This is the matrix that will come.
So this tells us what should be my e 2.
e 2 in this operation I want to make this 0 in place of this 3.
So what I do is that I do not make any changes in equation 1 and 3 or in row 1 and 3 of this
matrix.
Row 3 I replace by – 3 by 2 into row 1 that is equation 1 plus the original row 3.
So you see that my elementary matrix 2 here that is nothing happens in row 1 1 0 0 nothing
happens in row 2 0 1 0.
But the third one the original third is added by – 3 by 2 of us so – 3 by 2 0 1.
This is my e 2 this is how we can find the elementary matrices that we are using implicitly
in Gaussian elimination.
We have to go further now and my goal is of course to make this 5 by 2 0 in next phase
my 4 will be pivot and 5 by 2 will become 0.
We already know that and that is of course equivalent to multiplication by another elementary
matrix e 3.
When I multiply e 3 I get this and you remember that equation 3 in this case is given by equation
3 original multiplied by – 5 by 8 of equation 2 which means that my e 3 no change in 1 row
and no change in row 2 also so 1 0 0 0 1 0.
In row 3 I keep the row original row 3 and then I add with it – 5 by 8 of row 2.
So this is going to be my e 3.
So my original equation x equal to b which was 2 – 1 3 4 2 – 1 3 1 2 multiplied by
this column vector x 1 x 2 x 3 equals column vector 1 – 8 1.
And now I have come to e 3 e 2 e 1 multiplied by ax equals e 3 e 2 e 1 multiplied by b which
is equal to ux equals b prime and ux we can see here is an upper triangular matrix.
You see that below the diagonal we have all zeros so this is an upper triangular matrix.
So the fundamental idea of forward elimination is that we successively multiply by elementary
matrices such that at the end the matrix a that is there the original matrix in my ax
equals b system becomes an upper triangular matrix u.
So once again Gaussian elimination we can implement without any knowledge of matrices.
This idea that we now have we will use this for further discussion and going deeper into
Gaussian elimination.
Here for your exercise we have these 4 matrices which you have solved before.
What you can do now for the forward elimination part of these matrices you go back to your
solution and identify the elementary matrices that you have multiplied in each cases during
the forward elimination phase.
That is all for this lecture I will see you in next class.
