Determinants II (with Permutations)
3.01K subscribers
SUBSCRIBED
We connect the inductive definition of the determinant of a square n by n matrix to an alternate formulation involving a sum of products, corresponding to permutations of the set {1,2, ..., n}. A crucial but subtle feature of this formula is the role of the sign of a permutation.
00:00
hello everyone I'm no burger today I
00:03
going to carry on talking about
00:04
determinants and I want to connect this
00:08
important object with permutations so
00:12
kind of a connection between linear
00:14
algebra and what we call Group theory in
00:16
mathematics so I'm not going to be able
00:18
to cover all of this exactly logically
00:21
coherent because there's some critical
00:24
facts that I can I can tell you what
00:27
they are about proving them requires a
00:29
kind of an excursion into into algebra
00:31
and I don't have time to do that but I
00:34
still want you two to see a certain
00:36
alternate formula for a determinant so
00:39
let me remind you that if a is n by n
00:46
matrix then the determinant of a which
00:53
also we sometimes write just without
00:55
brackets and sometimes we write it with
00:57
so but absolute values around hey this
00:59
is a number it's a number associated to
01:05
the matrix defined recursively or
01:09
inductively as follows first of all we
01:19
define the determinant of a one by one
01:24
matrix a just to be equal to a and then
01:28
we say that if in general a is equal to
01:34
say entries little a I J and if we also
01:41
denote by capital a IJ the N minus 1 by
01:46
n minus 1 sub matrix obtained by
01:55
removing the 8th row and the J DH column
02:05
then here's our formula for the
02:10
determinant a determinate a equals a
02:12
1 times the determinant of a sub 1 1
02:17
then minus a 1/2 times the determinant
02:21
of a 1 2 and then plus and then minus
02:24
and so on all the way up to minus 1 to
02:27
the there's end of them all together and
02:30
plus 1 last time I wrote n should n plus
02:33
1 n plus 1 times a 1 n times the
02:39
determinant of capital a 1 n so that's
02:45
our inductive formula ok
02:51
so let's let me illustrate this again
02:54
just to make sure we're all on the same
02:55
page I'm going to do it with a 3 by 3
02:59
matrix but now with the entries a little
03:01
bit more organized not a B's and C's but
03:04
rather a IJ's so let's suppose that a is
03:07
a 3 by 3 matrix a11 a12 a13 a21 a.22 a23
03:17
a31 a32 a33 ok so then how do we
03:26
calculate the determinant from this
03:28
formula so the determinant of a equals
03:31
so first of all a 1 1 times the 2 by 2
03:37
determinant and I'm going to write that
03:38
with square brackets well this sort of
03:40
sub matrix in this case sub matrix this
03:43
one right here okay the entries are a.22
03:47
a23 a32 a33 and then minus a12 any 1/2
03:58
times the sub matrix obtained by
04:00
eliminating the row and column through a
04:02
1/2 that's the matrix a 2 1 a 2 3 a 3 1
04:07
and a 3 3 and then finally plus a 1 3
04:11
times the 2x2 matrix a 2 1 a 2 2 a 3 1
04:18
and a 3 2 okay now each of these
04:25
2 by 2 determinants we can calculate so
04:30
this first one will be a to 2 times a 3
04:34
3 minus a maybe 2-3 times a 3 2 okay and
04:41
then minus a 1 2 times a 2 1 a 3 3 minus
04:46
a 3 1 a 2 3 and then finally plus a 1 3
04:51
8 times a 2 1 a 3 2 minus a 3 1 a that's
05:01
a 2 2 like this ok let's expand this out
05:05
we know that we can get six terms a 1 1
05:08
a 2 2 a 3 3 minus a 1 1 a 2 3 a 3 2 then
05:16
plus a 1 2 a might write the positive 1
05:20
a 3 1 a 2 3 minus a 1 2 a 2 1 a 3 3 plus
05:31
a13 a21 a 3 2 and minus a 1 3 a 3 1 a 2
05:38
2 2 great so that is the determinant of
05:44
this general 3x3 matrix
05:46
and I've written it in this way because
05:48
I want to now connect this with
05:51
permutation so there's another way of
05:52
thinking about this this quantity and it
05:57
relates to really rooks on a chess board
06:00
so let me remind you that if you have a
06:02
chess board okay let make movie I know 4
06:06
by 4 chessboard there it is there and
06:09
there's typically you know black and
06:11
white squares black black you know
06:13
something like this fine and and I
06:18
remind you that a rook let's say you
06:20
look something like this okay rook is a
06:25
chess piece which can take either in the
06:28
horizontal or in the vertical direction
06:32
so our rook that's supposed to be a
06:34
rocket
06:35
rook is a chess piece that can take
06:37
horizontally or vertically and what's
06:41
kind of interesting is a a placement of
06:46
rooks on a chess board so that none of
06:50
them are able to take each other okay
06:53
so let's consider positionings of n
07:06
rooks on an N by n chess board so that
07:16
none can take any other so example here
07:25
if I want to complete this story here
07:28
maybe I could put another rook over here
07:30
okay those two rooks are not taking each
07:32
other and then maybe I could put another
07:34
rook down here in the corner that one's
07:36
not taking anything to previous ones and
07:38
then I could put the fourth rook over
07:41
here okay
07:42
so those four rooks are happily situated
07:45
they're all kind of peacefully oriented
07:48
none is able to take each other now how
07:51
many such positionings are there there
07:56
are n factorial such rook positionings
08:05
why is that well if we say go from row
08:09
to row going from one row to another
08:18
there's n choices for the first row no
08:28
but if we look just concentrating on
08:29
this first row there'll be n possible
08:31
places for the rook in that row and then
08:35
in the second row then n minus 1 choices
08:42
in the second row because we're not
08:47
allowed to
08:48
the rook in the same column that's
08:51
already been occupied by the rook in the
08:53
first row and then well then n minus 2
08:58
etc down to 1 in the last row so in the
09:06
4 by 4 you have 4 choices in the first
09:09
row three choices in the second row then
09:12
you'll only have two choices in the
09:15
third row and then finally in the fourth
09:17
row only one choice so it'll be all
09:19
together 4 times 3 times 2 times 1
09:22
that's 24 or 4 factorial different ways
09:25
of positioning the rooks
09:29
now these 24 or in general n factorial
09:36
rook positions are intimately connected
09:39
with determinants and have a look at
09:43
what we obtained in the 3 by 3 case ok
09:46
so if we go back to this formula here
09:48
and maybe I will see if I can maybe draw
09:53
some chess boards here so maybe here's a
09:54
little chess board it'll only be a small
09:56
because it'll be three by three there's
09:58
a three by three this first term right
10:02
here okay this first term corresponds to
10:06
three positions remember how we're so
10:10
organizing the the matrix entries okay
10:12
that's this is the one one entry this is
10:16
the to two entry
10:17
this is the three three of you so this
10:19
first term that I've underlined
10:21
corresponds to a rook positioning where
10:23
the three rooks are along the diagonal
10:25
how about the second one maybe in green
10:28
the second one here okay a 1 1 so that's
10:32
put it there a 1 1 a 2 3 that's over
10:37
there and a 3 2 okay that's another
10:41
possible positioning of the 3 rooks on
10:44
this 3x3 chess board and then maybe this
10:49
next one maybe yellow
10:50
okay a 1 2 so that would be that one
10:53
there and then a 3 1 that's I guess down
10:56
here and then a 2 3 that's over here
10:59
that's another
11:00
yeah and the other three correspond to I
11:03
want me just actually complete that a 1
11:05
2 2 1 3 3 a 1 2 that's that one there
11:09
and then a 2 1 and then a 3 3 that's
11:14
that one there and how about this one
11:16
here a 1 3 1 3 then 2 1 and then 3 2
11:23
here's another one
11:24
and finally blue this one here a 1 3
11:29
that's that one there a 3 1 that's over
11:33
there and a tube - yeah those are the
11:37
six possible positionings and they
11:40
exactly correspond to the terms of this
11:45
determinant once we've expanded it all
11:46
out in terms of the entries well there's
11:50
one more piece of information which is
11:53
actually the most subtle aspect of this
11:54
entire story which is that these six
11:57
terms come with plus and minus signs the
12:01
coefficients are always either plus 1 or
12:03
minus 1 at half of them are plus 1 and
12:06
the other half are minus 1 so to
12:10
completely describe this situation we
12:13
really have to sort of say what the the
12:18
sign is ok so let me let me tell you
12:27
what the general sort of theorem is and
12:29
what's actually involved to describe
12:31
this this story so there's a theorem
12:35
which connects the theory of
12:37
determinants with with group theory and
12:39
it is that if a is an N by n matrix a
12:43
with entries little a IJ ok is is an n
12:51
by n matrix then here is an alternate
12:57
formula for the determinant of a the
13:01
determinant of a is the sum okay over PI
13:06
I'm going to write I'll explain the
13:08
second permutations of n
13:12
okay proof tales event and then
13:15
something which we'll call sine of PI
13:20
that's going to be either plus or minus
13:23
what that's the the critical sine of
13:25
each of the terms and then the terms all
13:27
look like this so there'll be an a 1 PI
13:33
1 and then a 2 pi 2 all the way up to a
13:40
n PI n okay where sine of Pi which is
13:57
either plus or minus one is the sine of
14:04
permutation but what is the permutation
14:11
part it's a it's a map if you like it
14:14
from the set 1 to n to 1 to n which is a
14:22
bijection that it is on it's a
14:25
one-to-one mapping you can boys you've
14:29
got any girls here matching up the boys
14:32
with the girls in exactly a one-to-one
14:34
the way so each boy gets a girl and vice
14:36
versa now I have to complete the story I
14:40
have to tell you what the sign is
14:43
so here the sine of pi is minus 1 to the
14:56
site K where K transpositions get you
15:11
from PI to the identity ok I have to
15:18
explain this
15:19
even though to explain completely with
15:22
you know take me far afield but I want
15:24
to at least give you an idea so that
15:26
let's say we are in a in the 3 by 3 case
15:32
okay so example so suppose that we have
15:36
N equals 3 and here is a permutation so
15:39
how could I describe a permutation I
15:41
could describe it by what it does to the
15:45
3 elements its mapping the three
15:46
elements to yeah the three elements and
15:49
suppose that one gets sent to two and
15:51
two gets sent to three and three gets
15:53
sent to one so you know you've got one
16:01
two three and maybe these these things
16:07
were mapping things and so at the end of
16:10
that the thing in the first spot goes
16:12
into the second spot the thing in the
16:14
second spot goes into the third spot
16:16
like this and the thing in the third
16:18
spot goes in the first spot maybe that's
16:20
one way of describing it okay
16:22
no suppose that we wanted to get back to
16:26
the original position but we are only
16:30
allowed to make swaps between pairs of
16:35
objects okay that's what a transposition
16:38
is is a swap between a pair of objects
16:42
how many swaps do we need to get back to
16:47
where we started but we're only allowed
16:50
to sort of move two of them at any time
16:52
by interchanging any - okay so let's
16:54
let's let's try let's interchange the
16:56
one and the three okay that's a swamp or
17:01
transposition
17:03
it's interchange the 1 and the 3 but
17:07
it's still not in the correct order to
17:10
finish it I would need to swamp these
17:11
guys if I did that okay I'm going to now
17:15
get them back in the right order so I
17:17
made two swamps what does that tell me
17:22
it tells me that the sign of this
17:25
particular permutation pi is minus 1 to
17:28
the 2 - because there's two swamps ok
17:36
and that is plus one
17:39
now if we go back up here to our 3x3 so
17:47
I write you the permutation is like 2 3
17:50
1
17:50
so we're which of these six terms is 2 3
17:56
1 where 1 is associated to 2 2 is
18:01
associated to 3 and 3 is associate 1
18:12
it's exactly this one here see this this
18:19
term corresponds to the permutation that
18:21
one gets sent to to to get sent to 3 and
18:25
3 gets sent to 1
18:28
so this permutation that I just circled
18:31
corresponds to this permutation and we
18:36
can also describe it in terms of our
18:39
chessboard that happens to be the 1 2 &
18:43
3 so that's that's that one there and
18:45
the 2 3 entry that's that one there and
18:48
the 3 1 entry that's that one there
18:52
now how many you know swaps do you need
18:59
to get this thing back in the identity
19:02
so you could do it with rooks if you
19:05
like you got three rooks like this and
19:07
you can swap let's say swap the rows or
19:11
the columns of any rooks suppose we
19:14
decide to swap the rows the rows here
19:19
okay so we're going to swap them and
19:24
swap the rows and now we're going to
19:28
swap these rows okay look at that
19:36
this is the kind of geometrical
19:39
interpretation of what I was doing up
19:41
theater so what we have then is this
19:45
idea that every permutation has
19:48
associated to it a number which is
19:51
either
19:52
from minus one and that number is minus
19:55
one to the number of swaps that you need
19:58
to sort of get back to the identity from
20:00
whatever permutation you've you've
20:03
considered now there is a difficulty
20:09
here or it's a theoretical extra piece
20:12
of information that you need to know
20:14
that I haven't proved to you that's a
20:16
little bit challenging to prove so so an
20:18
extra requirement to this entire story
20:25
we need to prove that the sign of a
20:32
permutation is well-defined
20:40
what's that mean well it means that you
20:43
know let's say we've done a permutation
20:46
and then I come along and I start
20:47
swapping to two at a time back in takes
20:51
me 27 swaps and say it's a big thing
20:53
27 swaps to to get back to the identity
20:58
so then I would calculate that the sign
21:01
of this big permutation is minus 1
21:03
because it's minus 1 to the 27 but now
21:06
you become a long to the same
21:07
permutation and get back to the identity
21:09
maybe in a more efficient way maybe it
21:11
will take you only 11 swaps that you can
21:14
somehow you know get back to where you
21:16
started with Levis Watts swamps because
21:18
you're more clever then you would also
21:20
calculate that the sign is minus 1 to
21:22
the 11 which is also might as well so we
21:24
were in agreement so the theoretical
21:27
requirement is to prove that the sine of
21:29
pi is actually well-defined and
21:34
unfortunately in most every linear
21:37
algebra course ok the algebraic
21:40
sophistication is not there to prove
21:42
this and probably we don't have enough
21:44
time to draw inclination to prove it
21:46
either but you should know that this is
21:48
a key kind of algebraic aspect which
21:52
underlies the theory of determinants to
21:55
may be often put under the carpet but
21:58
it's actually a critical a critical
22:00
issue is the issue of these signs and
22:03
they're how they behave and first of all
22:06
that they're well-defined okay so having
22:10
said all that that's great but still
22:12
let's come back to our our theorem still
22:15
this then is a it's a very nice so a
22:20
fact that you can appreciate and I think
22:25
you can perhaps see why at least at some
22:29
level this is reasonable because when we
22:32
were you know doing this original
22:37
determinant definition okay like in this
22:40
3 by 3 case what we were doing is we
22:44
were starting with a 1 1 that's the
22:46
first term right there a 1 1 and then we
22:49
were multiplying it by the determinant
22:51
of this 2 by 2 block opposite it now if
22:55
you know if you know that this
22:57
determinant of this 2 by 2 block
22:59
consists of a lot of terms each of one
23:03
which consists of a product of elements
23:06
one in each row and column like maybe
23:08
this one times this one okay or maybe
23:13
maybe this one times this one then when
23:17
we take those sums of terms and we
23:19
multiplied by a 1 1 we're going to get
23:22
exactly the same kind of thing in other
23:24
words we're going from a 2 by 2 rook
23:27
configuration or rook configurations to
23:30
a bunch of 3 by 3 book configurations by
23:33
taking the 2 by 2 root configurations
23:35
and adding a third rook which is in
23:37
position 1 1 that corresponds is that
23:40
first term and when we do the second
23:43
term well it's like we're doing the same
23:45
kind of thing but now we're starting
23:46
with this thing here putting our rook
23:48
there and then looking at these other
23:50
four things which is a little bit harder
23:52
to draw okay because it's a kind of a
23:55
block thing it's these four things there
23:58
and you're considering rook positions
24:02
there to get a total position the for
24:05
the entire 3x3 so this formula that I
24:10
defined the determinant originally for
24:13
is is pretty cool
24:17
mostly connected with this permutation
24:21
formula here except that you know the
24:26
the role of the sign is is it's not so
24:29
clear it needs to be more carefully
24:31
analyzed to depend it all down but I
24:34
think you can at least see that it's
24:36
kind of reasonable okay what are some
24:40
consequences of this in terms of you
24:42
know calculating determinants or
24:44
something like that well let's say we
24:46
have a diagonal matrix okay so suppose a
24:56
is the diagonal matrix four three one
25:01
seven and otherwise it's all zeros
25:03
happens to be a four by four
25:08
what is this determinant going to be
25:13
well
25:14
then determinant of a if you remember
25:18
this previous formula the one I've just
25:20
shown you the one with the sum over all
25:23
permutations this determinant is a bunch
25:31
of terms with coefficients plus or minus
25:34
one each corresponding to a a position
25:38
of rooks on the four by four board that
25:42
don't touch each other and those
25:45
products are going to be nonzero
25:49
precisely when the rooks are all on
25:52
positions where there are numbers which
25:54
are not zero in other words if we take
25:56
this particular say rook configuration
25:58
that one that one that one and what else
26:04
maybe that and that one there okay
26:06
that's a real configuration but it has a
26:08
zero in it test actually two zeroes in
26:10
so if we take the product of those four
26:12
entries we get 0 times 3 times 0 times 7
26:14
that's obviously 0 it's not going to
26:16
contribute anything to this sum designed
26:21
sum involved in the determinant right so
26:24
that rook position doesn't contribute
26:26
and in this case there's only one rook
26:28
position that could
26:30
there's only one way of placing the
26:33
rooks on the 4x4 board so that every
26:37
rook is covering something that's
26:38
nonzero and here it is right here if you
26:41
choose that position in that row that
26:43
position in that row that position in
26:45
that row in that position in that realm
26:48
and that corresponds to the permutation
26:50
you know 1 goes to 2 1 2 goes to 2 3
26:54
goes to 3 and 4 goes to 4 so the sign of
26:58
that permutation is plus 1 because
27:04
there's no swaps needed to get it back
27:06
to the identity it is already the
27:07
identity and so the determinant a in
27:10
this case will just be that big sum just
27:14
reduces to a single sum a 1 1 times a 2
27:18
2 times a 3 3 times a 4 for all the
27:23
other 23 terms because there's 4
27:26
factorial terms all together in this 4x4
27:28
in general will be 0 and in this case we
27:32
just getting the product of the diagonal
27:34
elements it's 4 times 3 times 1/5 times
27:38
7