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

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

Suppose we have a square array \(A\) whose top and bottom rows are called \(T\) and \(B\), and whose left and right columns are \(L\) and \(R\). We define the following additional arrays. \(A_{TL}, A_{TR}, A_{BL}, A_{BR},\) and \(A_{TBLR}\), to be the arrays gotten by removing 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+2\) by \(n+2\) array then the next four are \(n+1\) by \(n+1\) array and the last is an \(n\) by \(n\) array.

Then the following equation holds:

\[Det(A_{TBLR}) \times Det(A) = Det(A_{TL}) \times Det(A_{BR}) - Det(A_{TR}) \times Det(A_{BL})\]

What this means is that the determinant of the array \(A\) can be written as products of determinants of arrays one size smaller divided by the determinant of \(n\) array two sizes smaller \((A)\).

And what good is all this?

We define the determinant of any \(0\) by \(0\) array to be \(1\), and a one by one array, which consists of a number, is its own determinant. Our two by two block consists of four one by one arrays, (\(a, b, c\) and \(d\)) in each of its corners \( \begin{pmatrix} a & b \\ c & d \end{pmatrix} \)

Applying this theorem to this case, \(A_{TL}\) is \(d\), \(A_{TR}\) is \(c\), \(A_{BR}\) is \(a\) and \(A_{BL}\) is \(b\). \(A\) is nothing at all, which we define to have determinant \(1\).

So Lewis Carroll’s theorem for \(2\) by \(2\) arrays says that the determinant of A, which is \(ad-bc\), can be written as the same thing divided by 1. This is something we have already observed.

Now suppose we started with a three by three array:

\[ \begin{pmatrix} a & b & e \\ c & d & f \\ g & h & i \\ \end{pmatrix} \]

This array has four two by two sub-arrays with adjacent rows and columns, one meeting each corner and these are \(A_{TL}\), \(A_{TR}\), \(A_{BR}\) and \(A_{BL}\). The theorem tells us that the determinant of the array is given by the product of the determinants of the top left and bottom right of these arrays, minus the product of the determinants of the top right and bottom left of them, all divided by the middle element which is d. Here are, starting from the top left and going to clockwise around are \(A_{BR}\), \(A_{BL}\), \(A_{TL}\), and \(A_{TR}\).

\[ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} b & e \\ d & f \end{pmatrix} \] \[ \begin{pmatrix} c & d \\ g & h \end{pmatrix} \begin{pmatrix} d & f \\ h & i \end{pmatrix} \]

Computing each of the determinants of these as done above for the entries in its upper left upper corner, gives us a two by two array whose elements are the two by two determinants of these four arrays. The first great thing here is that all four can be computed merely by copying the computation for the first one, one to the right and then both down.

In this case \(A\) is the middle element of the original array, \(d\) while \(A_{TL}\), \(A_{TR}\), \(A_{BR}\) and \(A_{BL}\) are the four \(2\) by \(2\) arrays immediately above, in clockwise order starting with the one on the upper left.

If we write these four resulting \(2\) by \(2\) determinants as

\[ \begin{vmatrix} d_{11} & d_{12} \\ d_{21} & d_{22} \end{vmatrix} \]

We can compute the \(3\) by \(3\) determinant by Lewis Carroll’s method to be \(\frac{d_{11}d_{22}-d_{12}d_{21}}{d}\).

What is even better, we can set things up so that we can compute the two by two determinant of this array divided by \(d\), using the same instruction used to compute these \(d_{ij}\)’s only copied one place to the right and down four places. By Lewis Carroll’s Theorem the result is the three by three determinant of our original three by three array.

What is even better than that, if we had started with a larger initial square array, say \(n\) by \(n\), copying appropriately first gives us rise to an \(n-1\) by \(n-1\) array of \(2\) by \(2\) determinants, more copying produces from this an \(n-2\) by \(n-2\) array of \(3\) by \(3\) determinants, and so on until we get a single \(1\) by \(1\) array whose entry is the \(n\) by \(n\) determinant of the original array. (We also produce rows of junk between these as well)

We will soon see what the one instruction you have to enter is, and how this can be set up.

There are two other good things about this. First, once it is set up for any size, you can change your initial array any way you want, and the spreadsheet will immediately give you the determinant of the new array.

Second, using Cramer’s rule, you can use the same approach to instantly solve systems of \(n\) by \(n\) linear equations, again with the ability to change the equations arbitrarily and getting the solutions immediately. (We will discuss this later, perhaps.)

I am not really sure how large you can make \(n\) and have this actually work. But \(n=5\) or \(n=6\) are definitely OK.

There is one problem however. This process involves a division. To handle three by three arrays we divided by the middle element of the array, which was \(d\) above. To handle four by fours, along the way we divide by each of the four middle elements of the original array, and then by the determinant of the array that these four elements form, any one of which might be \(0\). And dividing by \(0\) is a no no. This problem is easily handled as we shall see.

Ok, how can you do all this?

We will illustrate this by setting up a determinant finder for four by four arrays.

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

Then put \(1\) in position B3 and fill down from B3 to B5 and across to D3 to D5, putting \(1\)'s in all these places. These lines are here to represent the determinants of each trivial \(0\) by \(0\) array, which we will divide by.

Now here is the key step. Put =(A6*B7-A7*B6)/B3 into A10. Copy this into columns B and C, the result in C will be =(C6*D7-C7*D6)/D3. And then copy row 10 down to row 18.

What do you get?

A10 B10 C10 contain the first row of the array of \(2\) by \(2\) determinants of the original array.

A11 B11 C11 contain the second row of same.

A12 B12 C12 contain the third row of same.

Row 13 is junk.

A14 B14 contain the first row of the \(2\) by \(2\) array of \(3\) by \(3\) determinants of the original array.

A15 B15 contain the second row of same (the rest of rows 14 and 15 are junk).

Rows 16 and 17 are both junk.

A18 contains the four by four determinant of the original array, unless along the way you divided by 0 (all other entries in that row are junk).

If array entries A22 or B22 or A23 or B23 are \(0\), or their two by two matrix is \(0\), this spreadsheet will divide by \(0\), and you will get no evaluation. To fix this just replace the original entries that are \(0\) by numbers that are tiny and positive, (like \(10^{-10}\) when the entries are integers). If you also see to it that A22*B23 - B22*A23 is not \(0\), A18 will be the determinant of your \(4\) by \(4\) array.

Once the four central array entries are not zero, if you have A22*B23 - B22*A23 = 0, adding almost anything even smaller to any one of these four entries will make that combination non-zero and so A18 will be the determinant. Zeroes can be removed easily in a manner that cannot be seen in the answer, unless the determinant is actually \(0\).

Caution: if there is any dividing by \(0\) make all changes to eliminate same by changing the original array. Never make changes at later stages of the computation!

Here is what the spreadsheet output might look like. Entries on lines 6 to 9 can be modified and the determinant in A18 will be automatically calculated. If a non-number is used, the border of the cell will turn red and calculation will be aborted. Blue entries have to be non-zero.

A B C D
1 Determinant calculation
2
3 1 1 1
4 1 1 1
5 1 1 1
6
7
8
9
10
11
12
13
14
15
16
17
18

Exercises:

15.7 Set the same thing up for evaluating \(5\) by \(5\) determinants. (The differences are that the array of \(1\)’s at the top has to be \(4\) by \(4\) and your input data will be \(5\) by \(5\). You divide by the \(1\) at the top left for the upper left \(2\) by \(2\) determinant, and copy that into the first \(4\) columns. If the top left \(1\) is in B3, where will the \(5\) by \(5\) determinant be?

Cramer’s rule gives a formula for the solutions for the variables in a set of linear equations. It says that the determinant of the arrays gotten by substituting the constants in the equations for the column containing the coefficients of variable \(x\) in the equations, divided by the determinant of the original array of coefficients is the solution for \(x\).

Each of these determinants can be computed along with the determinant by this method, if you add the column of constants after the array of coefficients, and copy the array of coefficients after them. The arrays starting in the second column will be those involved in the numerators of Cramer’s rule, except for sign. This means that the solution to the linear equations will be appropriate ratios of the entries in the row containing the determinant, with appropriate signs. (The rows of \(1\)’s must be extended to the right and you must copy further to the right, as well.)

What do I do if this process causes a division by \(0\)?

This will happen only if A22 or A33 or A23 or A32 are \(0\) or of the determinant of the array with rows (A22 A23) and (A32 A33) is \(0\). You can check for this before you start and if any of these things occur add something tiny like \(10^{-10}\) to each \(0\); if none are \(0\) add \(10^{-10}\) to any one of them; if all are \(0\)’s add \(10^{-10}\) to three of them and \(-10^{-10}\) to the other. If one row or column of this \(2\) by \(2\) array is \(0 \, 0\) and the other row or column entries are identical, then add to one \(0\) and subtract the same thing from the other. This will always cause the procedure to avoid dividing by \(0\).