The (almost really) Complete Works of Lewis Carroll

being a new and brief Method for computing their arithmetical values

By the Rev. C. L. Dodgson, M.A., Student of Christ Church, Oxford. Communicated by the Rev. Bartholomew Price, M.A., F.R.S. Received May 15, 1866.

If it be proposed to solve a set of n simultaneous linear equations, not being all homogeneous, involving n unknowns, or to test their compatibility when all are homogeneous, by the method of determinants, in these, as well as in other cases of common occurrence, it is necessary to compute the arithmetical values of one or more determinants—such, for example, as $$\left|\begin{array}{rrr}1,& 3,& -2\\ 2,& 1,& 4\\ 3,& 5,& -1\end{array}\right|.$$

Now the only method, so far as I am aware, that has been hitherto employed for such a purpose, is that of multiplying each term of the first row or column by the determinant of its complemental minor, and affecting the products with the signs + and − alternately, the determinants required in the process being, in their turn, broken up in the same manner until determinants are finally arrived at sufficiently small for mental computation.

This process, in the above instance, would run thus:—

$$\left|\begin{array}{rrr}1,& 3,& -2\\ 2,& 1,& 4\\ 3,& 5,& -1\end{array}\right|=1\times \left|\begin{array}{rr}1,& 4\\ 5,& -1\end{array}\right|-2\times \left|\begin{array}{rr}3,& -2\\ 5,& -1\end{array}\right|+3\times \left|\begin{array}{rr}3,& -2\\ 1,& 4\\ \end{array}\right|=-21-14+42=7\text{.}$$

But such a process, when the block consists of 16, 25, or more terms, is so tedious that the old method of elimination is much to be preferred for solving simultaneous equations; so that the new method, excepting for equations containing 2 or 3 unknowns, is practically useless.

The new method of computation, which I now proceed to explain, and for which “Condensation” appears to be an appropriate name, will be found, I believe, to be far shorter and simpler than any hitherto employed.

In the following remarks I shall use the word “Block” to denote any number of terms arranged in rows and columns, and “interior of a block” to denote the block which remains when the first and last rows and columns are erased.

The process of “Condensation” is exhibited in the following rules, in which the given block is supposed to consist of n rows and n columns:—

(1) Arrange the given block, if necessary, so that no ciphers occur in its interior. This may be done either by transposing rows or columns, or by adding to certain rows the several terms of other rows multiplied by certain multipliers.

(2) Compute the determinant of every minor consisting of four adjacent terms. These values will constitute a second block, consisting of $\overline{n-1}$ rows and $\overline{n-1}$ columns.

(3) Condense this second block in the same manner, dividing each term, when found, by the corresponding term in the interior of the first block.

(4) Repeat this process as often as may be necessary (observing that in condensing any block of the series, the rth for example, the terms so found must be divided by the corresponding terms in the interior of the $\overline{r-1}$th block), until the block is condensed to a single term, which will be the required value.

As an instance of the foregoing rules, let us take the block $$\left|\begin{array}{rrrr}-2& -1& -1& -4\\ -1& -2& -1& -6\\ -1& -1& 2& 4\\ 2& 1& -3& -8\end{array}\right|.$$

By rule (2) this is condensed into $\left|\begin{array}{rrr}3& -1& 2\\ -1& -5& 8\\ 1& 1& -4\end{array}\right|$; this, again, by rule (3), is condensed into $\left|\begin{array}{rr}8& -2\\ -4& 6\end{array}\right|$; and this, by rule (4), into −8, which is the required value.

The simplest method of working this rule appears to be to arrange the series of blocks one under another, as here exhibited; it will then be found very easy to pick out the divisors required in rules (3) and (4).

$$\left|\begin{array}{rrrr}-2& -1& -1& -4\\ -1& -2& -1& -6\\ -1& -1& 2& 4\\ 2& 1& -3& -8\end{array}\right|$$

$$\left|\begin{array}{rrr}3& -1& 2\\ -1& -5& 8\\ 1& 1& -4\end{array}\right|$$

$$\left|\begin{array}{rr}8& -2\\ -4& 6\end{array}\right|$$

$$-8\text{.}$$

This process cannot be continued when ciphers occur in the interior of any one of the blocks, since infinite values would be introduced by employing them as divisors. When they occur in the given block itself, it may be rearranged as has been already mentioned; but this cannot be done when they occur in any one of the derived blocks; in such a case the given block must be rearranged as circumstances require, and the operation commenced anew.

The best way of doing this is as follows:—

Suppose a cipher to occur in the hth row and kth column of one of the derived blocks (reckoning both row and column from the nearest corner of the block); find the term in the hth row and kth column of the given block (reckoning from the corresponding corner), and transpose rows or columns cyclically until it is left in an outside row or column. When the necessary alterations have been made in the derived blocks, it will be found that the cipher now occurs in an outside row or column, and therefore need no longer be used as a divisor.

The advantage of cyclical transposition is, that most of the terms in the new blocks will have been computed already, and need only be copied; in no case will it be necessary to compute more than one new row or column for each block of the series.

In the following instance it will be seen that in the first series of blocks a cipher occurs in the interior of the third. We therefore abandon the process at that point and begin again, rearranging the given block by transferring the top row to the bottom; and the cipher, when it occurs, is now found in an exterior row. It will be observed that in each block of the new series, there is only one new row to be computed; the other rows are simply copied from the work already done.

$$\left|\begin{array}{rrrrr}2& -1& 2& 1& -3\\ 1& 2& 1& -1& 2\\ 1& -1& -2& -1& -1\\ 2& 1& -1& -2& -1\\ 1& -2& -1& -1& 2\end{array}\right|\left|\begin{array}{rrrrr}1& 2& 1& -1& 2\\ 1& -1& -2& -1& -1\\ 2& 1& -1& -2& -1\\ 1& -2& -1& -1& 2\\ 2& -1& 2& 1& -3\end{array}\right|$$

$$\left|\begin{array}{rrrr}5& -5& -3& -1\\ -3& -3& -3& 3\\ 3& 3& 3& -1\\ -5& -3& -1& -5\end{array}\right|\left|\begin{array}{rrrr}-3& -3& -3& 3\\ 3& 3& 3& -1\\ -5& -3& -1& -5\\ 3& -5& 1& 1\end{array}\right|$$

$$\left|\begin{array}{rrr}-30& 6& -12\\ 0& 0& 6\\ 6& -6& 8\end{array}\right|\left|\begin{array}{rrr}0& 0& 6\\ 6& -6& 8\\ -17& 8& -4\end{array}\right|$$

$$\phantom{\left|\begin{array}{rr}0& 12\\ 18& 40\end{array}\right|}\left|\begin{array}{rr}0& 12\\ 18& 40\end{array}\right|$$

$$\phantom{36.}36\text{.}$$

The fact that, whenever ciphers occur in the interior of a derived block, it is necessary to recommence the operation, may be thought a great obstacle to the use of this method; but I believe it will be found in practice that, even though this should occur several times in the course of one operation, the whole amount of labour will still be much less than that involved in the old process of computation.

I now proceed to give a proof of the validity of this process, deduced from a well-known theorem in determinants; and in doing so, I shall use the word “adjugate” in the following sense:—if there be a square block, and if a new block be formed, such that each of its terms is the determinant of the complemental minor of the corresponding term of the first block, the second block is said to be adjugate to the first.

The theorem referred to is the following:—

“If the determinant of a block = R, the determinant of any minor of the mth degree of the adjugate block is the product of $R^{m-1}$ and the coefficient which, in R, multiplies the determinant of the corresponding minor.”

Let us first take a block of 9 terms, $$\left|\begin{array}{rrr}{a}_{1,1}& a_{1,2}& a_{1,3}\\ a_{2,1}& a_{2,2}& a_{2,3}\\ a_{3,1}& a_{3,2}& a_{3,3}\end{array}\right|=R\text{;}$$ and let ${\alpha }_{1,1}$ represent the determinant of the complemental minor of $a_{1,1}$, and so on.

If we “condense” this, by the method already given, we get the block $\left\{\begin{array}{rr}{\alpha }_{3,3}& {\alpha }_{3,1}\\ {\alpha }_{1,3}& {\alpha }_{1,1}\end{array}\right\}$, and, by the theorem above cited, the determinant of this, viz. $$\left|\begin{array}{rr}{\alpha }_{3,3}& {\alpha }_{3,1}\\ {\alpha }_{1,3}& {\alpha }_{1,1}\end{array}\right|=R\times a_{2,2}\text{.}$$

Hence $R=\frac{\left|\begin{array}{rr}{\alpha }_{3,3}& {\alpha }_{3,1}\\ {\alpha }_{1,3}& {\alpha }_{1,1}\end{array}\right|}{a_{2,2}}$, which proves the rule.

Secondly, let us take a block of 16 terms:

$$\left|\begin{array}{ccc}{a}_{1,1}& \cdots & a_{1,4}\\ ⋮& & ⋮\\ a_{4,1}& \cdots & a_{4,4}\end{array}\right|=R\text{.}$$

If we “condense” this, we get a block of 9 terms; let us denote it by $\left\{\begin{array}{ccc}{b}_{1,1}& \cdots & b_{1,3}\\ ⋮& & ⋮\\ b_{3,1}& \cdots & b_{3,3}\end{array}\right\}$, in which $b_{1,1}=\left|\begin{array}{rr}{a}_{1,1}& a_{1,2}\\ a_{2,1}& a_{2,2}\end{array}\right|$, &c.

If we “condense” this block again, we get a block of 4 terms, each of which, by the preceding paragraph, is the determinant of 9 terms of the original block; that is to say, we get the block $\left\{\begin{array}{rr}{\alpha }_{4,4}& {\alpha }_{4,1}\\ {\alpha }_{1,4}& {\alpha }_{1,1}\end{array}\right\}$; but, by the theorem already quoted, $\left|\begin{array}{rr}{\alpha }_{4,4}& {\alpha }_{4,1}\\ {\alpha }_{1,4}& {\alpha }_{1,1}\end{array}\right|=R\times b_{2,2}$; therefore $R=\frac{\left|\begin{array}{rr}{\alpha }_{4,4}& {\alpha }_{4,1}\\ {\alpha }_{1,4}& {\alpha }_{1,1}\end{array}\right|}{b_{2,2}}$; that is, R may be obtained by “condensing” the block $\left\{\begin{array}{rr}{\alpha }_{4,4}& {\alpha }_{4,1}\\ {\alpha }_{1,4}& {\alpha }_{1,1}\end{array}\right\}$.

This proves the rule for a block of 16 terms; and similar proofs might be given for larger blocks.

I shall conclude by showing how this process may be applied to the solution of simultaneous linear equations.

If we take a block consisting of n rows and $\overline{n+1}$ columns, and “condense” it, we reduce it at last to 2 terms, the first of which is the determinant of the first n columns, the other of the last n columns.

Hence, if we take the n simultaneous equations, $$\begin{array}{c}{a}_{1,1}{x}_1+a_{1,2}{x}_2+\cdots +a_{1,n}{x}_n+a_{1,n+1}=0,\\ \cdots \\ a_{n,1}{x}_1+a_{n,2}{x}_2+\cdots +a_{n,n}{x}_n+a_{n,n+1}=0;\end{array}$$ and if we condense the whole block of coefficients and constants, viz. $$\left\{\begin{array}{ccc}{a}_{1,1}& \cdots & a_{1,n+1}\\ ⋮& & ⋮\\ a_{n,1}& \cdots & a_{n,n+1}\end{array}\right\}\text{,}$$ we reduce it at last to 2 terms: let us denote them by S, T, so that $S=\left|\begin{array}{ccc}{a}_{1,1}& \cdots & a_{1,n}\\ ⋮& & ⋮\\ a_{n,1}& \cdots & a_{n,n}\end{array}\right|$, and $T=\left|\begin{array}{ccc}{a}_{1,2}& \cdots & a_{1,n+1}\\ ⋮& & ⋮\\ a_{n,2}& \cdots & a_{n,n+1}\end{array}\right|$.

Now we know that $x_1=(-{)}^n\frac{T}{S}$, which may be written in the form $(-{)}^{n}S.x_1=T$.

Hence the 2 terms obtained by the process of condensation may be converted into an equation for $x_1$, by multiplying the first of them by $x_1$, affected with + or −, according as n is even or odd. The latter part of the rule may be simply expressed thus:—“place the signs + and − alternately over the several columns, beginning with the last, and the sign which occurs over the column containing $x_1$ is the sign with which $x_1$ is to be affected.”

When the value of $x_1$ has been thus found, it may be substituted in the first $\overline{n-1}$ equations, and the same operation repeated on the new block, which will now consist of $\overline{n-1}$ rows and n columns. But in calculating the second series of blocks, it will be found that most of the work has been already done; in fact, of the 2 determinants required in the new block, one has been already computed correctly, and the other so nearly so that it only requires the last column in each of the derived blocks to be corrected.

In the example given opposite, after writing + and − alternately over the columns, beginning with the last, we first condense the whole block, and thus obtain the 2 terms 36 and −72. Observing that the x-column has the sign − placed over it, we multiply the 36 by $-x$, and so form the equation $-36x=-72$, which gives $x=2$.

Hence the x-terms in the first four equations become respectively 2, 2, 4, and 2; adding these values to the constant terms in the same equations, we obtain a block of which we need only write down the last two columns, viz. $\left|\begin{array}{rr}2& 4\\ -1& -2\\ -1& -2\\ 2& 6\end{array}\right|$.

We then condense these into the column $\left|\begin{array}{r}0\\ 0\\ 2\end{array}\right|$, and, supplying from the second block of the first series the column $\left|\begin{array}{r}3\\ -1\\ -5\end{array}\right|$, we obtain $\left|\begin{array}{rr}3& 0\\ -1& 0\\ -5& 2\end{array}\right|$ as the last two columns of the second block of the new series; and proceeding thus we ultimately obtain the two terms 12, 12. Observing that the y-column has the sign + placed over it, we multiply the first 12 by $+y$, and so form the equation $12y=12$, which gives $y=1$. The values of z, u, and v are similarly found.

It will be seen that when once the given block has been successfully condensed, and the value of the first unknown obtained, there is no further danger of the operation being interrupted by the occurrence of ciphers.

$$\begin{array}{rrrrrrrrrr}-& & +& & -& & +& & -& +\\ x& +& 2y& +& z& -& u& +& 2v& +2& =0\\ x& -& y& -& 2z& -& u& -& v& -4& =0\\ 2x& +& y& -& z& -& 2u& -& v& -6& =0\\ x& -& 2y& -& z& -& u& +& 2v& +4& =0\\ 2x& -& y& +& 2z& +& u& -& 3v& -8& =0\end{array}$$

$$\left|\begin{array}{rrrrrr}1& 2& 1& -1& 2& 2\\ 1& -1& -2& -1& -1& -4\\ 2& 1& -1& -2& -1& -6\\ 1& -2& -1& -1& 2& 4\\ 2& -1& 2& 1& -3& -8\end{array}\right|\left|\begin{array}{rr}2& 4\\ -1& -2\\ -1& -2\\ 2& 6\end{array}\right|\left|\begin{array}{rr}2& 6\\ -1& -3\\ -1& -1\end{array}\right|\left|\begin{array}{rr}2& 5\\ -1& -1\end{array}\right|\left|\begin{array}{rr}2& 4\end{array}\right|\therefore -2v=4\dots v=-2$$

$$\left|\begin{array}{rrrrr}-3& -3& -3& 3& -6\\ 3& 3& 3& -1& 2\\ -5& -3& -1& -5& 8\\ 3& -5& 1& 1& -4\end{array}\right|\left|\begin{array}{rr}3& 0\\ -1& 0\\ -5& -2\end{array}\right|\left|\begin{array}{rr}3& 0\\ -1& -2\end{array}\right|\left|\begin{array}{rr}3& 3\end{array}\right|\therefore 3u=3\dots u=1$$

$$\left|\begin{array}{cccc}0& 0& 6& 0\\ 6& -6& 8& -2\\ -17& 8& -4& 6\end{array}\right|\left|\begin{array}{cc}6& 0\\ 8& -2\end{array}\right|\left|\begin{array}{cc}6& 6\end{array}\right|\therefore -6z=6\dots z=-1$$

$$\left|\begin{array}{ccc}0& 12& 12\\ 18& 40& -8\end{array}\right|\left|\begin{array}{cc}12& 12\end{array}\right|\therefore 12y=12\dots y=1$$

$$\left|\begin{array}{cc}36& -72\end{array}\right|\therefore -36x=-72\dots x=2$$

$$\begin{array}{rrrrrr}-& & +& & -& +\\ 5x& +& 2y& -& 3z& +3& =0\\ 3x& -& y& -& 2z& +7& =0\\ 2x& +& 3y& +& z& -12& =0\end{array}$$

$$\left|\begin{array}{rrrr}5& 2& -3& 3\\ 3& -1& -2& 7\\ 2& 3& 1& -12\end{array}\right|\left|\begin{array}{rr}-3& 8\\ -2& 10\end{array}\right|\left|\begin{array}{rr}-3& 12\end{array}\right|\therefore 3z=12\dots z=4$$

$$\left|\begin{array}{rrr}-11& -7& -15\\ 11& 5& 17\end{array}\right|\left|\begin{array}{rr}-7& -14\end{array}\right|\therefore -7y=-14\dots y=2$$

$$\left|\begin{array}{rr}-22& 22\end{array}\right|\therefore 22x=22\dots x=1$$

The Society then adjourned over the Whitsuntide Recess to Thursday, May 31.