17.5 The Alice in Wonderland Method for Evaluating Determinants on a Spreadsheet

As you may not remember, Lewis Carroll, the author of Alice in Wonderland, was a mathematician, and the method uses his celebrated theorem on determinants. It goes as follows:

Suppose we have a square array A, and two additional rows, called T and B, and two columns L and R. We define the following additional arrays. ATL, ATR, ABL, ABR, and ATBLR, to be the arrays gotten by adding row T at the top of A and column L to its left, row T at the top and column R on the right, row B on the bottom and column L on the left, B on the bottom and R on the right, and finally, T at the top, B at the bottom, L on the left and R on the right.

If A is an n by n array then the next four are n + 1 by n + 1 array and the last is an n + 2 by n + 2 array.

Then the following equation holds:

Det (ATBLR)*Det(A) = Det(ATL)*Det(ABR) - Det(ATR)*Det(ABL)

We define the determinant of the 0 by 0 array to be 1. The determinant of a one by one array is its lone entry. The content of this equation, when applied to the array in which A is 0 by 0, T is (a, b), B is (c, d), the vertical entries of L are a and c and those of R are b and d, is the formula that the two by two determinant of the array with rows (a, b) and (c, d), multiplied by 1 (the determinant of a 0 by 0) is a c - bd, which is what the right hand side is here.

(The first entry of T is in the left row and its last entry is in the right row, so that if, as on the right here you don't have a right or left row, then the corresponding entry to T is missing. The same thing happens with all the others. Thus ATL is a, ATR is b, and so on, here).

And what good is all this?

If we apply this statement for A a zero by zero array, we can produce the determinants of 2 by 2 adjacent subarrays of the array we apply it to from the one by ones and the zero by zero. The original array can be considered the array whose elements are determinants of the one by one subarrays of the array we started with.

If we apply the same formula again to the array of 2 by 2 determinants produced at first, we produce an array of 3 by 3 determinants of adjacent rows and columns, and applied to these we get an array of 4 by 4 determinants of adjacent subarrays of the original array, and so on, and eventually we get the determinant of the entire array.

Now the really wonderful thing is this: to do everything just mentioned, we need only make one entry in the spreadsheet, and copy and it will do everything just discussed.

Huh?

Suppose we have a four by four array, and we locate it in positions A6 B6 C6 D6 to A9 B9 C9 D9.

Then put a 1 (to represent a 0 by 0 determinant,) in position B3 and fill down from B3 to B5 and across to D3 to D6, putting 1's in all these places.

Now here is the key step. Put = (A6*B7 – A7*B6)/B3 into A10, and fill down to A18 and across to C10 to C18.

Then the determinant of your original array will appear in A18, unless along the way you divided by 0.

And then what?

If you divide by 0 along the way, (possible because each step involves dividing by something) you can modify the elements of your array by tiny amounts until this no longer happens. Then you will have your answer.

When do you divide by 0?

This happens if any of the elements of your original array, in positions B7 B8 C7 or C8 are 0 or if the two by two determinant created in B11 is 0.

(There is a systematic way to avoid dividing by 0, that works for almost every array of size up to around ten by ten, whose entries are integers. You can create an array whose element in the ith row and jth column is =x * ln(i + j) where x is 10-8, and add it term by term to the original array, and apply the method just described to the sum array. Only by some sort of miracle will you end up dividing by 0, and you can vary x to eliminate its effect on the answer. It is described in the last section below)

Exercises:

17.7 Set up a spreadsheet for evaluating determinants of three by three arrays whose middle element is non-zero by this approach.

17.8 Get it to work so that it instantly supplies the answer as you change the array.

17.9 Add 10^-8 to the middle entry so that the method always works even when that entry is chosen to be 0. (you have to separate the entry data for the middle position, which could be 0 from the middle position you use here, which should have something like 10^-8 added to the former.)

Is this method really useful?

Well, you can set it up in a few minutes, and once it is set up, you can change your given array and find the changed determinant immediately. This allows you to check any calculation of a determinant almost instantly. Believe me, this will save you lots of time, if you ever have to evaluate determinants.

But why should I want to evaluate determinants?

We have seen that the magnitude of a determinant gives the area or volume or analogue in higher dimension of the figure that given array describes. You may someday want to find such things. But there are several other uses that are even more important.

Such as?

We will describe the first now and just mention the second.

First, determinants can be used to solve systems of linear equations. We can and will show how to implement this on a spreadsheet and use the method of the previous section to solve up to ten equations in ten unknowns with very little more work than that of finding the determinant.

Second, determinants can be used to find eigenvalues and eigenvectors of arrays, quickly and conveniently.

What the devil are those?

One thing at a time. If you have patience, we will eventually get to these, but not now.