The magic of matrix multiplication
3.01K subscribers
SUBSCRIBED
We prove the crucial result that matrix multiplication is associative. Along the way we review summation notation and get practice with indices and ranges.
00:00
hello everyone I'm norm operator in this
00:03
lecture we're going to be looking at the
00:04
magic of matrix multiplication in
00:06
particular we want to prove that matrix
00:09
multiplication is associative so here is
00:12
the theorem if a is an M by n matrix and
00:15
B is an N by P matrix and C is a P by Q
00:20
matrix then a B times C equals a times B
00:31
C in other words your social of law of
00:34
multiplication halls
00:36
okay so let's review what matrix
00:41
multiplication is or another way of
00:43
saying it so I remind you that if we
00:46
have two matrices a and it may be like
00:50
this okay
00:52
then you can multiply them if this
00:53
dimension is equal to that dimension and
00:55
then you're gonna get another matrix
00:57
whose whose height is the same as the
01:01
height of a and whose width is the same
01:04
as the width of B okay so this is M by n
01:09
say and this is n by P then these two
01:12
numbers are the same so you can multiply
01:14
them and then the result will be M by P
01:18
and the IJ entry of this thing okay the
01:23
IJ entry let's call this matrix C okay
01:27
then the IJ entry of C is the product of
01:33
the I row of a which may be is over here
01:40
there's the I throw x times the J column
01:51
of B I'll write like that so you can see
01:55
it's a row times a column okay so the J
01:58
column is may be somewhere over here
02:00
there's the Jade column of B so we
02:02
multiply this row times this column and
02:06
that's how we get this IJ entry in here
02:08
okay now we want to understand that
02:13
to Bradley so what we're gonna do is
02:15
we're gonna use a bit of summation
02:16
notation so let me just remind you about
02:19
that okay summation notation is a
02:21
convenient device for allowing us to
02:25
write sums relatively efficiently so for
02:29
example if we have say a 1 plus a 2 plus
02:32
all the way up to say a n then we could
02:35
write that as sum from I equals 1 to N
02:38
of a sub I and the I here is acting like
02:43
a kind of a dummy variable so we could
02:46
also replace the I with J would not make
02:48
any difference it's the same as the sum
02:50
from J equals 1 to N of a sub J all
02:55
right so I hope you're all familiar with
02:56
that and this summation notation satisfy
03:00
some nice properties let me just very
03:02
quickly sort of remind you what they
03:03
might be
03:04
so maybe sum from I equals 1 to N of a I
03:08
plus bi is the same as the sum from I
03:13
equals 1 to N of AI plus the sum from I
03:16
equals 1 to N of BI and another property
03:21
is that the summation I equals 1 to N of
03:23
lambda times AI equals lambda times the
03:27
sum I equals 1 to N of AI these are two
03:32
fundamental linear properties of
03:34
summation notation so now let's go back
03:38
to our matrices a B and C and so on and
03:40
so we'll suppose that we actually know
03:43
what the the entries of the matrix a are
03:47
so suppose that the IJ entry of the
03:51
matrix a is actually equal to a IJ
03:56
little a IJ okay and similarly that the
04:00
IJ entry of B is a little B bi J so we
04:05
have some explicit variables that
04:07
capture the entries of these matrices
04:09
okay then
04:12
we can restate what we said above in
04:15
terms of the IJ entry of the product a B
04:19
the IJ entry of that so we said that's
04:22
the product of the I throw of a and the
04:28
jth column of B so I need to remind you
04:32
that a was an M by n matrix and B is an
04:35
N by P matrix those are the dimensions
04:38
okay
04:39
so let's think about how we could write
04:41
that product of the eighth row of a with
04:45
the jth column of B that's a dot product
04:50
okay so a dot product is a sum okay so
04:54
it's a sum and it's a summa some other
04:57
index let's say K well it's going to be
05:01
summing over and different things
05:04
because the number of elements in a row
05:07
of a is n and the number of elements in
05:09
the column of B is also add those are
05:11
the two numbers after you saying and
05:12
we're taking this times this Plus this
05:14
times this plus system going all the way
05:15
across that row of a and that column of
05:18
B so there's actually n different
05:21
products in this calculation of this IJ
05:24
entry so I'm gonna write that as sum
05:27
from k equals 1 to n introducing a new
05:34
index variable K and in terms of that
05:38
that the 8th row of a consists of things
05:41
of the form a I K that's the case
05:46
element in the I throw of a and we're
05:48
going to multiply that by the case
05:50
element in the jth column of B how do we
05:54
describe that that's B K J let's have a
05:59
look at this this formulas actually
06:01
quite an important formula that we could
06:04
you know just in general write down
06:07
so I'll just write down if a is M by N
06:12
and B is n by P so the interpretation is
06:21
that this thing here is in the eighth
06:29
row of a while this thing here is in the
06:36
J column of B we're taking products of
06:44
corresponding things so that's gonna be
06:47
the crucial sort of algebraic way of
06:50
writing down the the formula for the
06:54
product of the matrices now we might
06:57
also just say you know what about the
07:00
indices I and J what range of values are
07:03
they ranging over in this story so where
07:09
I describes a row of a how many rows
07:15
does a have well it has m rows okay so
07:21
this I is an index that is running from
07:24
1 up to M inclusive and what about J
07:29
okay J is describing how many columns B
07:33
has that's that number P so the J index
07:43
is running from 1 up to P so this
07:48
information I'll put this box around
07:50
here so sort of part of the information
07:52
okay these three things are the things
07:55
that sort of describe matrix
07:56
multiplication there's the basic formula
07:58
for it in terms of the sizes of a and B
08:02
and the variables I and J are described
08:06
by these things here okay so now we want
08:11
to prove the theorem that we started
08:15
with this associative
08:17
la for a matrix multiplication we want
08:20
to prove that okay so let's let's do it
08:26
so proof of the theorem okay and maybe
08:36
we'll write down what the theorem is
08:38
again so a B times C equals a times B C
08:45
let's look at the left hand side okay
08:50
and let's look at a general entry of the
08:54
left hand side okay and what is the
08:57
dimensions of this thing going to be
08:59
what I remind you that a was M by N and
09:03
B was n by P and C was P by Q so this
09:09
whole thing is going to be M by Q so
09:14
both will be M by Q matrices the left
09:20
hand and the right hand side so let's
09:26
calculate the IJ entry of this big left
09:36
hand side product the IJ entry when I
09:39
write down what an expression for that
09:41
is okay so well remember this is right
09:52
up here this is how we we calculate the
09:56
IJ entry of a product but what's
09:59
involved here in this product is a
10:01
product of two matrices one of which is
10:04
already a product okay so let's write
10:08
this as a sum so a I might just remind
10:12
myself of what the dimensions are a
10:14
times B is going to be an M by P matrix
10:17
and C is going to be a P by Q matrix
10:21
that's the common P that allows us to
10:25
move by those two things okay so our
10:29
dummy variable or index is going to be
10:32
say K and it's going to run from 1 to P
10:36
and what we're going to do is we're
10:39
going to take the I'll write it this way
10:42
the I cave element of a B and multiply
10:48
it by the ke jaise element of C that's
10:56
exactly our basic formulas put a star
10:58
here okay by star okay
11:07
can we say what this is so this is the
11:09
sum from k equals 1 to P what is the I K
11:14
element of a B well that's a lot like
11:17
what's up here except instead of having
11:19
the IJ element it's the I case element
11:23
okay so let's write that down so that
11:26
that will be some we'll have to use a
11:32
different index because we were already
11:33
using K so let's use some different one
11:36
maybe L you haven't used Elliot okay so
11:39
maybe L going from 1 to what well it was
11:47
n if a is an M by N and B's it might be
11:51
it's gonna be 1 to N so what are we
11:55
summing we're summing the the element in
12:00
the eye elf
12:01
position okay so that's the 8th row of a
12:06
and multiply by the jate caught the Kate
12:10
column or be the case column of B so
12:13
it'll be times b lk that's the I K
12:19
element of the product a times B now
12:23
what about the C sub K J well we're
12:26
saying that C is say little and see KJ
12:30
so the KJ element of the matrix C is
12:33
little seeds
12:35
KJ now we can write this as the
12:45
following way this this entry see KJ
12:49
okay as far as this sum is concerned
12:52
here okay it's a constant so it can be
12:55
moved inside so what we can do is we can
12:59
write this as the sum from k equals 1 to
13:02
p the sum from l equals 1 to N of ail
13:07
BLK all that times C KJ okay good so
13:16
that's the left hand side okay and now
13:18
the right hand side the right hand side
13:21
is a times BC so we should find out what
13:24
the IJ element of that is so now but
13:31
they ever take a times B C and we
13:36
calculate the IJ element of that a is an
13:40
M by n B times C is an N by Q so in this
13:47
case the common dimension is n so our
13:51
new variable or W variable is going to
13:55
have to go from 1 to N well what should
13:58
we use for for that let's use I might
14:05
use L you might see the why in a second
14:09
so L is going to go from 1 to N that's
14:13
good because it's the same thing that we
14:15
had in the previous line the L was also
14:17
going from 1 to N ok so sum from l
14:20
equals 1 to n so then we have to take
14:22
the matrix entry of a in the position I
14:28
L and we have to multiply that by the
14:32
matrix entry of the product BC in the
14:35
position L J so that's again using our
14:42
basic formula right up here the star
14:45
okay let me say by star
14:49
okay but what is this so this is the sum
14:52
from l equals 1 to n the entry IL of a
14:58
is just little a IL and now we have to
15:02
write down the entry of the product BC
15:05
in the LJ spot
15:10
so BC is I remind you what the
15:13
dimensions are B was a n by P and C was
15:18
P by Q so the common number there is P
15:23
so we need a variable that goes from 1
15:26
to P what should we use how about using
15:30
K let's use K so sum from k equals 1 to
15:35
P of what well the LJ entry here it's
15:40
going to be the entry just right be l k
15:46
and then the product x ce que je so it's
15:53
all that that's again this basic
15:59
operation of how to multiply two
16:00
matrices how to get the LJ entry of this
16:03
product ok but now this is the same as L
16:08
equals 1 to N we can bring this constant
16:11
ail inside this sum and we get sum K
16:17
equals 1 to P a IL b lk c KJ and now
16:25
there's a kind of brackets like this now
16:33
we have to compare this expression with
16:36
this expression are they the same well
16:40
they are the same so if we call this
16:41
thing save 1 in this thing 2 then 1 & 2
16:48
agree for two reasons since first of all
16:54
as numbers ail times BL k times
17:02
EK j equals ail times b lk x ck j that's
17:08
just associate ivities of ordinary
17:12
multiplication of numbers and because if
17:16
you have a sum like this the double sum
17:21
K equals 1 to P L equals 1 to N of
17:30
something or other let's say X sub K L
17:33
then that's the same as a sum from l
17:36
equals 1 to n sum from k equals 1 to P
17:40
of X to the K L that's really just say
17:43
that if you don't have to mow a lawn and
17:46
you go in this direction that's the same
17:50
as mowing the lawn by going in this
17:52
direction so you can sum up in this
17:54
direction first and then in the other
17:56
direction they're all little sums or you
17:58
can sum downwards and going across the
18:00
other direction
18:02
that's exactly what we're using here to
18:04
be able to establish that this quantity
18:07
here in 1 & 2 are the same because the
18:10
sums order has been reversed but
18:13
otherwise they're the same and what's
18:15
inside was inside this thing here is
18:18
exactly the same as that so that gives
18:21
us a proof of the associative law of
18:25
matrix multiplication which is a very
18:27
important result and it is a little bit
18:29
technical but if you learn about
18:31
Maxwell's