[Edu-sig] Algebra + Python

[Lloyd Hugh Allen]

In response to the message

"""
	Message: 1
	From: "Daniel Ajoy" <dajoy@softhome.net>
	To: edu-sig@python.org
	Date: Mon, 7 May 2001 18:14:44 -0500
	Subject: RE: [Edu-sig] Algebra + Python
	
	On 7 May 01, at 12:01, edu-sig-request@python.org wrote:
	
	> A simple way to compute the determinant is to add the signed 
	> products of all permutations of matrix elements, choosing one 
	> from each row (a total of row! possibilities).  ciphers.py is
	> in charge of returning a list of all those possibilities 
	
	Does that work for matrices 4x4 ? I ask because it didn't
	work for me.
"""

[very long. sorry. this is why we iterate when we program, so that the
computer can do the boring stuff for us.]

There are few "tricks" for finding determinants > 3x3. You have to go
back to the why of how the tricks work. Let's start with a 1x1:

[a]

The determinant of that matrix is <a>. It retains whatever sign the
element had had.

=====
Easy enough. Go on to a 2x2:

a  b

c  d

which can be represented as [ [ a , b] [ c , d ] ], if you're a
programmer type person and prefer your data one-dimensional.

Start in the top row. Put your finger on "a", and block out the row
(that is, the element "b") and the column (that is, the element "c").
You are left with the trivial submatrix [d], which has determinant of
<d>. This gives us the first part of the determinant, which is a*d (the
thing that we had our finger on, times the determinant of the
corresponding submatrix).

Now put your finger on the next element in the top row, b. Ignore
everything else in its row and in its column. You are left with the
trivial submatrix [c], which has determinant of [c]. This gives us the
second part of the determinant, b*c.

Go back through your list of parts of the determinant, and alternate the
signs on them. In this case, we have a*d - b*c.

=====
Next, for a 3x3:

a  b  c

d  e  f

g  h  i

Start in the top row. Put your finger on "a", and block out the row and
the column of "a". You are left with submatrix [ [ e , f] [ h , i ] ].
The first part of the determinant will be <a> * det ( [ [ e , f ] [ h ,
i ] ] ), which is

a ( ei - hf )  #taking the 2x2 determinant of the submatrix; the sign of
a is                #unchanged because a is in column 0.

aei - ahf      #using the distributive property

Now go to "b". Blocking out the row and column of "b" leaves the
submatrix 
[ [ d , f ] [ g , i ] ]. Because this is the second element we have
played with, we need to change the sign of b, and then we will multiply
that by the determinant of the submatrix.

-b ( di - gf )      #the sign of b is opposite because b is in column 1

-bdi + bgf     #using the distributive property

Similarly, we get the elements c * det [[d,e][g,h]]

c ( dh - eg )

cdh - ceg

When you string those together, you get the familiar "diagonal" cheating
method of finding the det of a 3x3.

The procedure above, though, generalizes to n x n. Sorry to be verbose.

Determinants are cool because the determinant of a 2x2 gives the area of
a parallelogram with one vertex at the origin and two points identified
by the rows or columns; or of a 3x3, the volume of a solid with parallel
faces with vertices identified similarly; or of a 4x4, the
hypervolume...

and because if the determinant is zero, you know better than to look for
an inverse (which might otherwise be time-consuming). (not that finding
the determinant of a large matrix is terribly fast).

Now to turn all of that into code. Now I know how I'm teaching recursion
this summer.