noc20-ma54-lec03_Matrix Multiplication

IIT Kanpur July 201
20 followers
2 Video Views·Dec 3, 2023
Matrix Multiplication
[Music]
[Music]
so in the previous class we learned what
are called
matrix addition and a scalar
multiplication now we would like to look
at what is called matrix multiplication
which is very very important thing and
the crux of matrix theory so as I said
it is the clerk so it means that it has
to play an important role and we need to
give sufficient time to understand
matrix multiplication so let me try that
out let's try to understand matrix
multiplication so we have learned this
matrix multiplication in our school but
would like to proceed further and
understand it in a better way so given a
matrix a M cross F and a matrix B which
is say P cross Q of different sizes he
has into a IJ B as entry B IJ then we
can talk of a times B matrix
multiplication or matrix product
whatever you want to say if n is same as
P so n means number of columns of a
should be equal to number of rows of B
now why it has been defined this way
cannot be explained now but we look at
examples and see that why it plays such
an important role for us all right
because not just multiplying some things
but more than that so as I said we have
a matrix product only when M should be
equal to P so I can multiply so I have
matrix M cross n then if I want to
multiply then B has to be other size n
cross Q and the output of this matrix is
a matrix e which has m rows and q
columns
this n + n cancels out so you are left
out with M rows and Q columns so let us
look at examples to understand it so I
have take a is equal to 1 2 3 well let
me take the examples that I have taken
earlier I think so that there will be
clarity so 1 minus 1 2 0 0 1 and B is
equal to 3 4 5 minus 1 0 1 so this
matrix a is of size 3 cross 2 B is of
size 2 cross 3 so if I want to multiply
so a is 3 cross 2 B is 2 cross 3 so
these 2 and 2 will cancel out the
product a B will be of the size 3 cross
3 similarly here it turns out in this
example that B is 2 cross 3 and is 3
cross 2 so again these two will cancel
out I will get the product ba which is
of size 2 cross 2 so in general if I
want to look at a times B is defined in
this example so in the previous example
that is a is M cross M B is n cross Q
then a times B is defined and it is a
matrix of size n cross Q but when I want
to define B times a then B has Q columns
but a does not have Q columns so that is
not defined so matrix product there are
issues but in this example everything is
nice so let's take an example try to
understand them so what is the matrix
product a B here so a B that we learn
here is we have to multiply the first
entry a 1-1 with b11 plus
a one-two with b21 alright
so note here this one and this one they
cancel out in some sense and I have this
here the first the first and the first
year similarly 2 & 2 will cancel out
here I have got one here and one here
the next entry is going to be it is a 3
cross 3 matrix so one two entry so for
one two entry I need to look at a 1 1
into B 1 2 plus again a 1 2 into B 2 2
so again observe here that 2 and tool
gives me 1 2 entry here these 2 cancels
out this 1 and this 2 gives me the entry
1 2 and this one cancels out so here I
have left out to the 1 1 entry
similarly if I want to look at the 2 2
entry here so I have to have 2 here and
something here again this something has
to cancel out here and I should get to
here so this 2 and this 2 will give me 2
2 entry I also have a 2 2 again these 2
has to cancel out and this 2 should give
me these two to get me to to fine so
this is the way I am supposed to
multiply so I have a 1 into here another
entry here so these are the entry that I
am going to get so in general when I
write a B is a matrix C alright the
entry of C is C IJ then C IJ has to have
this property that AI has to be there
then B has to come with a J so that
these I and this J they give me IJ entry
and then the first entry first column
first row plus again a I to
b2j again I and J gives me IJ here this
one and this one they cancel out
similarly here two and two cancels out
and so on this is the matrix of size n
so I'll go till n AI n BN j this n n n
cancels out I am left out with IJ entry
alright so that's the way to understand
that the middle part they cancel out and
whatever is left out is outside so we
generally write it as summation AI K BK
j k is going from 1 to n this is the
summation sign that we have here this K
and K cancels out so I left off with I
gained J so K goes from 1 to N so K is 1
means 1 1 here 2 2 here and NN here fine
so let's go back to our matrix that we
gave here and let's compute the entry a
B of 1 1 a B of 1 1 is 1 times 3 plus
minus 1 times minus 1 which is 3 plus 1
which is 4 all right so let's proceed
and compute all of the entries now so
again let me write it a is 1 minus 1 2 0
0 1 B is 3 4 5 minus 1 0 1 so the matrix
product a B is
this one with three that is this three
plus minus 1 times minus 1 then 1 times
4 plus minus 1 times 0 then 1 times 5
plus minus 1 times 1 similarly the
entries here I would like you to check
that this is nothing but 3 plus 1 is 4 4
plus 0 is 4 5 minus 1 or 4 plus 0 3 plus
1 4 plus 0 5 minus 1 this is 2 into 3 is
6 then so 2 into 3 is 6 plus 0 then 2
into 4 8 plus 0 2 into 5 is 10 plus 0 0
into 3 is 0 plus minus 1 then I have 0
plus 0 and I have 0 plus 1 which is same
as 4 4 4 6 8 10 and minus 1 0 1 all
right
let me just clean it I think this is too
congested so this was 0 plus minus 1 0
plus 0 + 0 plus 1 fine so this is the
matrix product a B this we all know how
to compute it the way we have computed
it this is what we learnt on out of
school now I would like to understand
this matrix multiplication in a
different way so what is the different
way so let's try to see so I have my
matrix as the first row of the matrix as
1-1 or let me write this itself the
second row is to zero the third row of
this of a is 0-1
now if you look at this this is a matrix
of size 1 Row 2 column 1 Row 2 column 1
Row 2 column B is a matrix which is 2
cross 3 it means that I can talk off
this times B I can multiply these two so
multiplying these two basically means I
am looking at 2 1 minus 1 times this
matrix B which is 3 4 5 minus 1 0 1 this
is same as look at here 3 plus 1 4 + 0 5
plus minus 1 which is same as 4 4 4
which was nothing but the first row of a
B just match it with this the first row
of a be fine
similarly let us look at the second row
of a multiplied by B because this is 1
cross 2 B is 2 cross 3 so it might this
matrix multiplication makes sense so it
is 2 0 times 3 4 5 minus 1 0 1 so it is
nothing but I'm multiplying 0 to the
second row here 2 so T 6 8 and 10 check
that this is also equal to the second
row of a B similarly
I can talk of this is a 1 cross 2 matrix
again this is 2 cross 3 so I can again
multiply 0 1 times 3 4 5 minus 1 0 1
which is nothing but minus 1 0 1 which
is third row of a B so if I look at a B
what we are saying is a B has this
property which is which looks like this
times B this times B this times B so
here rows of B are being multiplied by
the entries 1 and minus 1 the first rows
of a
all right and therefore we had a of one
eye so I would like you to understand
here one thing that I am multiplying a B
when you multiply a B we learnt AV
multiplication using this idea that is a
IJ aik bkj and summation over K that was
the idea our idea was looking at a IJ
aik BK j k equal to 1 to n that was the
idea that we had but that is ok as well
calculation is concerned we need to
learn it but there's another way of
learning things here which says that I
can compute the first row of a B just by
multiplying the first row of a with B
all right if I want to compute the fifth
row of a B if I want to compute a fifth
row of a B I just have to look at the
fifth row of a and multiply it by me it
makes sense because a has a is one cause
so if a was M cross M then the fifth row
is nothing but one cross N and B is n
cross Q so this makes sense and this
gives me a matrix of size 1 Cross Q so
it gives me the 5th row of a times B
fine so I hope you have understood let's
see again once I am trying to do that
but when I want to compute a B I can
compute a B a times B entry wise the a11
entry times b1 1 plus a 1 2 into B 2 1
plus so on
so I can compute the 1 1 entry of a b12
entry of a be 1 3 entry of B B and so on
another way to compute is just compute
the first row of Av the second row of a
B the third row of a B and so on fine
so this is called the row method because
we are looking at the first row of a B
the second row of a B the third row of a
B so this was our row method of matrix
method or method
of matrix multiplication all right now
let's learn what is called the column
method of matrix multiplication so we'll
be looking at columns to multiply things
all right so again the same example I
have a as 1 minus 1 2 0 0 1 B is 3 4 5
minus 1 0 1 we already written what the
rows and columns are again look at a a
is 2 cross 3 look at the first column of
B the first column of B has size 2 cross
1 so sorry I wrote a wrongly it is a is
3 cross 2 and therefore this matrix
multiplication makes sense and it gives
me a matrix of size 1 so let's multiply
it out so I'm looking at a times B of
first row the first column so a is 1
minus 1 2 0 0 1 I want to multiply this
with the first column the first column
is 3 minus 1 so this is nothing but look
at it 3 times the first column 1 2 0
plus minus 1 times minus 1 0 1 which is
nothing but 3 plus 1 is 4 6 plus Z my 0
is 6 and 0 plus minus 1 is minus 1 so I
would like you to check that this was
the same thing in the as in the previous
example so let me write the previous
what was a B so that you can match it so
a B was 4 4 4 6 8 10
- 1:01 all right again let's write the
other way
a times B of the second column again I
have a 1 - 1 2 0 0 1
now the second column of B is 4 comma 0
so it is nothing but 4 times 1 - 0 plus
0 times minus 1 0 1 which is nothing but
4 8 0 Mathew that this is nothing but
look at a B the second column here it
was the first column alright similarly
if I look at the third column is 1 - 0 -
1 0 1 this times 5 comma 1 which is 5
times 1 - 0 plus 1 times minus 1 0 1
which is nothing but 5 minus 1 is 4 10
plus 0 is 10 0 plus 1 is 1 which is
nothing but the third column of a B
alright so we have learned this also
that I can in place of looking at
component wise multiplication of a B we
look at computing the rows we are also
now able to compute the columns just
multiplying the matrices and the entries
alright so let's take an example another
example to understand it better why do
we need such a thing suppose I have a
matrix a or lecture I have some matrix a
a B and C so the matrix a we know is 0
here 0 here 0 here there is some nonzero
entry here fine there is a 0 here
alright so let me make it also nonzero
first alright
here so you can see that this is an
upper triangular matrix matrix with a 1
1 0 I take another matrix which is again
upper triangular but I have something
here which is slightly different so this
is also upper triangular but here a 2 2
entry is 0 all right I want to multiply
these two matrices and see what do I get
fine so can I multiply matrix entry wise
you can multiply this the first row with
the first column look at 0 times a star
star times 0 and so on you can also
multiply it as 0 0 0 times a star this
star is your this one so say a here B
here and C here if I write I am
multiplying by a here then it will be 0
times a star a star 0 plus 0 times a
star star a star this will give me the
first column column which will be
nothing but 0 0 0 all right
so here I am writing a here all right
similarly so here I looked at this times
the whole matrix so I looked at if this
matrix is a this was B then I have
looked at a times the first column of B
if I compute a times the second column
of B it will be B times 0 0 0 plus 0
times a star a star 0 plus 0 times a
star a star a star which will again give
me 0 0 0 so if you multiply these two
matrix what you get here is 0 0 0 0 0 0
and something here fine
so this is the way sometimes it helps to
understand matrix multiplication what it
tells me that if I look at the matrix a
its first column was 0 so in my be the
first call row does not play a role so
what I'm saying is that if first column
of a is 0 then first row of B doesn't
play any role in a B all right
it is only the second entries second row
third row of B that plays the role fine
because whatever you put it gets
multiplied by 0 and you get only 0 as
such fine so this is the 2 as we learned
what is called the row method this is
the column method we'll come to some
more examples but now we will look at
another example another multiplication
alright what is called the so let's see
so let me write that first so again let
me write a as whatever a was for me a
was 1 minus 1 2 0 0 1 B was
three four five minus one zero one and
the matrix a B was four four four six
eight ten minus one zero one alright so
now I would like to look at so again so
here I looked at till now I was able to
talk of the first row which was one
minus one this was a metric of size 1
cross 2 B was 2 cross 3 so I could talk
of this which is again a matrix of size
1 Cross 3 I also looked at a which was 3
cross 2 and B was the column wise I
looked at so B was 2 cross 1 it gave me
a matrix of size I could talk off so a B
this so this was a be the first room
this is a be the first column I can also
talk off let us try to understand this
so here I talked in terms of rows here I
term in terms of columns now what about
the other way round something else so
look at columns of a the first column of
a if I look at this is a matrix of size
yeah
size 3 cross 1 if I look at B the first
row of B this is of size 1 cos 3 and
therefore this matrix multiplication so
a times this into B times sorry
first column and this should be in the
first row
you should have in the first row all
right so I can multiply these two here
multiplied these two what do I get let's
see so hey I am looking at the first
column 1 2 0 and I am looking at the
first row of this which is 3 4 5 what I
get is 3 4 5 2 times this is 2 into 3 is
6 8 10 x 0 get 0 0 0 all right so I
could talk of this I can also talk off
so this was corresponding to the first
column this was corresponding to the
first row of B now I would like to look
at second column which is again 3 cos 1
and corresponding row of B which is 1
Cross 3 so I look at a of 2 and B of
this so this matrix has entry minus 1 0
1 this has entry minus 1 0 1 so this
gives me 1 0 minus 1 this is 0 0 0 0
which 1 minus 1 0 1 if I multiply if I
add these two if I see if I add these
two what do I get is 3 plus 1 4 plus 0 5
minus 1 6 + 0 8 plus 0 10 + 0 0 plus
minus 1 0 plus 0 0 plus 1 which is
nothing but 4 4 4 6 8 10 minus 1 0 1
which is a B
so check that we see another way of
multiplying and you are getting to get
the same answer so what exactly we are
doing here is in this matrix
multiplication is we have written a as
the first column and the second column
this is the way we wrote first column
second column we wrote B as the first
row and the second row and we are saying
is that a B is nothing but a times so
first column of a into first row of B
plus second row times
sorry second column times the second row
so the important thing is here again
note that this two and two cancels out
this one and one is canceled out cancel
out so this is what is important that
you are able to multiply things to all
what I'm trying to say is that so let me
write it so there are ways of
multiplying matrices one was I can
compute a B IJ entry directly I can
compute a be using its rows I can
compute a be using its columns I can
also compute a be using sum of matrices
sum of matrix approach
so here approach means I am looking at a
columns of a times this and I'm looking
at K is equal to 1 to n so these are the
four ways in which we can do matrix
multiplication all right and I would
like you to learn this matrix
multiplication in the next class I will
take up some more examples to make you
understand this matrix multiplication
why I am trying to assess on matrix
multiplication is because of the
following aim of the whole course the
whole course that you are going to do is
in different ways trying to prove the
following idea so we are trying to prove
the following ideas that given a matrix
a which is M cross n I can write a as
what is called I can use a to write a as
L times u where L is lower triangular
and U is upper triangular
so E is a matrix which is M cross n then
I will have some issues I will cannot
talk about particular lower triangular I
will have to talk in terms of forms
lower triangular matrix and upward
traveler form but if a is a square
matrix then these two make sense
we'll need conditions what are called
regular conditions alright and they lead
to what is called Gauss elimination
method so this is nothing but the girls
elimination method for us so this is a
first thing that we are going to
understand is what is called writing the
matrix a as Lu decomposition L for lower
you for upper triangular decomposition
another thing we are going to learn is
writing a as B times C so a is your M
cross M B is going to be M cross R C is
going to be our CRO
and here are is nothing but the rank of
a matrix so we are decomposing the
matrix into ranks this is called rank
decomposition or rank factorization of a
matrix fine the next thing that we are
going to learn is writing a matrix a as
few times are so if a is M cross N and
as rank R so rank of is R then this Q
will be of the size n cross R this will
be R cross n and will turn out that so
this is called QR decomposition
decomposition the important thing is
that this matrix Q transpose Q which is
an R cross R matrix will be an identity
matrix all right so what we call
orthogonal matrices so we have got three
things that is the basic idea that we
have this part will lead to what are
called Gauss elimination method or as I
said this is rank factorization this
will also come from system of linear
equation for the QR decomposition we
will need to learn what are called inner
product spaces so that you can
understand what we are doing
orthogonalization and so on gram-schmidt
process then there are three more which
are related with what are called eigen
values eigen vectors and eigen vectors
that we can write as u P u transpose T
is upper triangular alright in certain
and U is unitary matrix
I haven't said what is a unitary matrix
till now so we will understand these
things as we go along but this eigen
values and eigen vectors is going to the
last chapter so for that we'll have to
understand everything there will be a
special case of this so here we need
that a is n cross n a square matrix
we'll look at things when we can make in
place of T upper triangular will have T
as a diagonal matrix and then the final
thing will be writing any matrix a M
cross n as some u D V transpose where u
and V are unitary and D is diagonal
alright so in place of D most of the
books they write Sigma here to
understand this is singular value
decomposition of the matrix so initially
we look at the first two examples that
is a equal to L Q Lu and the rank
factorization afterwards after that
we'll learn what are called vector
spaces and then things like that so
that's all for today but keep track that
we need to understand matrix
multiplication so that you can do all of
them
thank you
[Music]
[Music]
[Music]
