How Lewis Carroll computed determinants

https://www.johndcook.com/blog/2023/07/10/lewis-carroll-determinants/

by alberto_ol • 3 years ago

98 36 3 years ago

vivegi• 3 years ago

That is a nice method to compute determinants of matrices. I wish they taught this method when I was in high school.

As John D Cook points out, the fact that the core 2x2 matmul operations that can be done in parallel is a big benefit for doing this in software or hardware.

1letterunixname• 3 years ago

I don't see how this is cheaper by efficient mechanical computation or cognitively easier for humans than Laplace expansion. Also, we were taught to use decomposition to grab eigenvectors and the det. It was pretty easy to verify correctness because of my handy HP 48G had an RPN CAS and a "spreadsheet" matrix editor.

gjm11• 3 years ago

Unless the matrices are rather small, this is much more efficient than Laplace expansion.

To compute the determinant of an n-by-n matrix with Laplace expansion, you compute n determinants of matrices one size smaller. So if we write D(n) for the cost of computing the determinant of an n-by-n matrix, we have D(n) ~= n D(n-1), which means that D(n) is of order n!.

To compute the determinant of an n-by-n matrix with Dodgson's condensation algorithm, you compute (n-1)^2 2-by-2 determinants, and then repeat with n reduced by 1, and so on until you get to a 1x1 matrix. That is, we have D(n) ~= n^2 + D(n-1), which means that D(n) is of order n^3.

For n of moderate size, n^3 is much smaller than n!.

Of course, unless n is very small you don't want to be computing determinants by hand anyway; you should use a computer, and shouldn't use either of these algorithms.

Still, for hand computation I would consider the Dodgson algorithm an excellent choice ... if it weren't for the possibility of having to divide by zero. You can work around that but then it's no longer so true that the algorithm is simple and requires little bookkeeping.

eulgro• 3 years ago

TIL Lewis Caroll was also a mathematician.

thundermuffin• 3 years ago

Not only was he a mathematician, but Alice is considered partially a commentary on the state of mathematics at the time! [0] It's one of my (irrational) pet peeves that modern audiences often try to explain his books as some kind of Victorian era equivalent to a Cheech and Chong movie about drugs when there's so much more hidden away in the pages. These two books are my favorite books ever, and I'd give an arm and a leg if I could ever get my hands on an original copy, haha.

I highly recommend The Annotated Alice for anyone interested in Alice's Adventures in Wonderland and Through the Looking Glass, because it makes a couple of fun, curious reads even curiouser! ;)

[0] https://www.npr.org/2010/03/13/124632317/the-mad-hatters-sec...

tmtvl• 3 years ago

I second the recommendation for The Annotated Alice, even if many references fly over my head as I'm not much of a mathemagician.

thumbuddy2• 3 years ago

That makes a lot of sense actually. Thanks for sharing this anecdote. Sometimes brilliant people get buried because of their eccentricities and it deters from the meaning of their life's work.

heresie-dabord• 3 years ago

Dodgson/Carroll was a witty writer. This is so good a passage that it has influenced modern English:

- - -

"I'VE been to a day-school, too," said Alice, "you needn't be so proud as all that."

"With extras?" asked the Mock Turtle a little anxiously.

"Yes,' said Alice, "we learned French and music."

"And washing?' said the Mock Turtle.

"Certainly not!" said Alice indignantly.

"Ah! then yours wasn't a really good school," said the Mock Turtle in a tone of great relief. "Now at OURS they had at the end of the bill, 'French, music, AND WASHING--extra.'"

"You couldn't have wanted it much," said Alice, "living at the bottom of the sea."

"I couldn't afford to learn it." said the Mock Turtle with a sigh. "I only took the regular course."

"What was that?" inquired Alice.

"Reeling and Writhing, of course, to begin with," the Mock Turtle replied, "and then the different branches of Arithmetic-- Ambition, Distraction, Uglification, and Derision."

"I never heard of 'Uglification'," Alice ventured to say. "What is it?"

The Gryphon lifted up both its paws in surprise. "What! Never heard of uglifying!" it exclaimed. "You know what to beautify is, I suppose?"

"Yes," said Alice doubtfully, "it means--to--make--anything--prettier."

"Well, then," the Gryphon went on, "if you don"t know what to uglify is, you ARE a simpleton."

- - -

inopinatus• 3 years ago

You may be further intrigued to hear that Hedy Lamarr invented frequency-hopping spread spectrum, Felix Hausdorff was a playwright, Neil Young has multiple patents relating to model train control, Isaac Newton is frequently credited with the invention of the catflap, Brian May holds a PhD in astrophysics, and don't even get me started on Leonardo da Vinci.

scrps• 3 years ago

I'll add to the list: Dolph Lundgren won a Fulbright to MIT and has a masters in chemical engineering.

dlkf• 3 years ago

Da Vinci was a renaissance man?

peanutcrisis• 3 years ago

And Tony Hoare was a "Classics and Philosophy" major.

spidersenses• 3 years ago

Hedy Lamarr invented frequency-hopping spread spectrum

Even after reading her biography, I'm still not convinced that she actually invented, or even worked on the technology. I find it much more likely that she either funded the patenting process, and in this way got her name on the application, or that the "co"-inventor put her name on it out of admiration, thereby securing interest in the patent thanks to Lamarr's fame.

sorenjan• 3 years ago

Dexter Holland, the singer in The Offspring, has a PhD in molecular biology. Rowan Atkinson got a MSc in Electrical Engineering and started a doctorate.

ivan_ah• 3 years ago

Does anyone have a geometrical intuition about how this works? Maybe just for 3d case? How does condensation compute the volume of a parallelepiped from the individual areas of parallelogram? And what does the division do?

shreyshnaccount2• 3 years ago

The 3b1b video on the topic does an amazing job

thaumasiotes4• 3 years ago

Does it? Does such a video even exist? I searched for "3b1b matrix determinant condensation" and ended up wasting ten minutes of my life on a video ("The determinant | Chapter 6, Essence of Linear Algebra") that doesn't address the topic in any way. What video were you talking about?

thaumasiotes4• 3 years ago

I can't help with a geometrical intuition, but it's interesting to work through what happens with a matrix of 9 scalars.

    [a b c]
    [d e f]
    [g h i]

The determinant of course has six terms. (aei - ahf - bdi + bgf + cdh - cge)

For condensation purposes, we view our 3x3 matrix as a 2x2 matrix instead:

    [A B]
    [D E]

where each element A, B, D, and E is really a 2x2 matrix. These matrices overlap; the second column of A is the first column of B, and the second row of B is the first row of E. This overlapping is probably related to the need to remove information during the process.

We then take the determinant AE - DB of our 2x2 matrix. If we look back up at the original 3x3 scalar matrix, the only element common to all four of these matrices-of-convenience is e, and that's what we use to "normalize" the determinant back down. The determinant of the original matrix is (|A||E| - |D||B|)/e.

The product of two 2x2 determinants has four terms, so the sum we compute has eight instead of six, but two of them, which just happen to be the two terms with no factor of e, cancel out.

scythe• 3 years ago

Geometric intuition is going to be difficult, but I bet there's a relatively elegant algebraic argument that uses some index-twiddling symmetries. There's a one-page inductive proof (with four pages of introduction) on arXiv:

https://arxiv.org/pdf/1607.05352.pdf

ajkjk3• 3 years ago

As it sounds like you're aware, if a 3x3 matrix is considered as three vectors that form a parallelogram, the 2x2 minors form three vectors in the bivector space ∧^2 R^2 that represent the area vectors for the three faces of that parallelogram.

Here's a hand-wavy version in a sort of pseudo-notation: if the matrix is M = (a,b,c), then the first step of condensation forms (a∧b, b∧c). Confusingly, you drop the last row and column of the minor matrix, the one that wraps around to the start. Then you compute (ab ∧ bc) / b, which if you squint looks like it cancels the b out and leaves (a∧b∧c).

I guess if you didn't know anything about vectors and their multiplication (or lack of it) you might assume that (abc) = (ab * bc / b), and the way this algorithm works is basically "oh actually multiplication does kinda work on vectors, if you're really careful to not erase any information".

But there's clearly a missing 'piece' that explains exactly what is going on. I'm pretty sure there is a way to make it rigorous but I haven't thought about in a while. (I have an ongoing silly project to make sense of all the weird formulas of exterior algebra, cf https://alexkritchevsky.com/2018/10/09/exterior-2.html ... but I haven't worked on it in a while and haven't looked closely at Dodgson Condensation yet.)

diracs_stache• 3 years ago

I like the cofactors method as it helps me track signs by relating i to the column and row positions

mkl• 3 years ago

At O(n!) it's not very sensible beyond about 4×4 though (unless your matrix has a lot of zeros).

thumbuddy2• 3 years ago

Not trying to cheapen anything about this article, but I'm very sure this is how I was taught to calculate them in several schools. Have any of you been taught otherwise?

nwoli• 3 years ago

Charles Dodgson, better known by his pen name Lewis Carroll, discovered a method of calculating determinants now known variously as the method of contractants

Emphasis on discovered

hgsgm2• 3 years ago

It's linear algebra. There are many slightly different ways to do any computation in linear algebra. (This is the essence of the fuss among mathphobes about Common Core, when people complain about kids learning different algorithms for arithmetic.)

ajkjk3• 3 years ago

Most people do not learn this version.

This algorithm produces a bunch of intermediate matrices of (n-1)x(n-1) size, (n-2)x(n-2), etc. (See https://en.wikipedia.org/wiki/Dodgson_condensation also, which is honestly more useful than this article.)

The usual manual algorithm is something like "go along the top row, and for each value multiply it by the determinant of the minor created by removing that row and column, times an alternating sign". It involves smaller determinants but never produces a 'smaller intermediate matrix'. It's also, as far as I can tell, a lot less work than the Dodgson method.

FooBarBizBazz• 3 years ago

The usual manual algorithm is something like "go along the top row, and for each value multiply it by the determinant of the minor created by removing that row and column, times an alternating sign".

Cofactor expansion, aka Laplace expansion. ("Cofactor" is probably a better name, since everything else is also named after Laplace, or Gauss, or Euler.)

It's also, as far as I can tell, a lot less work than the Dodgson method.

That's the interesting thing. It isn't! The article discusses the asymptotics at the end.

How Lewis Carroll computed determinants

Related Stories