How Lewis Carroll computed determinants
johndcook.com
johndcook.com
Emphasis on discovered
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.
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.
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.
Regarding the division aspect, the video doesn't explicitly mention it. However, the concept of subtracting the product of certain elements from the product of other elements in the determinant formula can be understood as a form of division operation. This subtraction or difference in scaling factors is what contributes to the computation of the determinant and reflects the volume change or scaling of the parallelepiped.
It is true that it doesn't answer all the questions one might have about the problem, but it does answer some of them and is likely the video mentioned earlier, which unfortunately wasn't linked by either of you. So, I linked to it so we'd have it here.
Yes, we all already know that. It is explicitly present as assumed background knowledge in the original question that ivan_ah asked:
>>> How does condensation compute the volume of a parallelepiped from the individual areas of parallelogram?
The question is how the area of the parallelogram defined by the two vectors
[e f]
[h i]
[a b c]
[d e f]
[g h i]
and the 3b1b video not only doesn't address this, or mention that condensation is a thing you can do, it actively discourages you from calculating determinants by any method.
[a b c]
[d e f]
[g h i]
For condensation purposes, we view our 3x3 matrix as a 2x2 matrix instead:
[A B]
[D E]
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.
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.)
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...
- - -
"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."
- - -
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.
It's an interesting enough story, IMO, to try to clarify this to the degree possible (or, at least, degree I can from my understanding):
First, Lamarr very much was an inventor. She was creative and continuously proposed, and in some cases produced, inventions.
Concerning frequency-hopping signals, she is the origin of the idea in the late 1930s in an arc that would produce a working method. She had several key insights and motivations that underlie her significant role in developing the idea into an actual "invention" (something with a practical demonstrated method of implementation):
1) She was aware, from direct interaction with Axis weapons manufacturers in the late 1930s, that they were devoting significant effort to intercepting and jamming Allied signals, including / in particular signals used to control weapons
2) She realized that having a prearranged sequence of frequencies, that a transmitter and receiver hopped between, should be workable / within reach
3) And, as regards motivation and commitment to ideas like this, in general - she was grateful to have been accepted in the US after fleeing Austria ... and not merely accepted, but have the career opportunity in Hollywood that she was building (though she was still angered there by being treated often as a "pretty face" rather than skilled / talented person / actress), and had an extremely strong drive to contribute to the war effort.
Her general knowledge of the practice and mathematics of frequencies, "carriers", signals, etc. contributed to her continued pursuit of the idea. She knew the base of it was solid, and I think she astutely judged that there ought to be some practical way of implementing it with technology available at the time in approximately the relevant footprint for some of the applications of most interest.
As for the basis of the practical device, that idea came from George Antheil. Antheil and an engineer at CIT (Samuel Mackowen) were then able, to create an entirely workable system and submit for and be granted a patent, which did include Lamarr (under her married name, and, actually did not include Mackowen - there's some interest in this as well, but, I guess he served as more of a consultant than originator of anything of enough note). Her key insights formed the basis for the work, although it seems likely she didn't contribute much to the practical implementation.
Finally, it should be noted that, as with many inventions, she was hardly the first person to play around with these sorts of ideas. Several others had experimented with the idea or related ideas, going back even 35+ years. But, she and her co-inventors came up with the abstract implementation (+ practical demonstration) / "blueprint" underlying a vast array of modern communications technologies.
Refs:
https://www.researchgate.net/profile/Tony-Rothman/publicatio...
https://www.scientificamerican.com/article/hedy-lamarr-not-j...
https://www.aps.org/publications/apsnews/201106/physicshisto...
https://scienceandfilm.org/articles/2889/bombshell-interview...
Edit: added / corrected a bit of info on "Samuel Mackowen"
Edit 2: "It's not Hedy, it's Hedley..."
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.