How Lewis Carroll computed determinants(johndcook.com)
johndcook.com
How Lewis Carroll computed determinants
https://www.johndcook.com/blog/2023/07/10/lewis-carroll-determinants/
38 comments
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?
> 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
Emphasis on discovered
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.)
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.
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.
> 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.
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.
oh yeah, the name escaped me earlier but, of course, it is cofactor expansion.
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.
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.
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?
I can't help with a geometrical intuition, but it's interesting to work through what happens with a matrix of 9 scalars.
For condensation purposes, we view our 3x3 matrix as a 2x2 matrix instead:
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.
[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.
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.)
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.)
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
https://arxiv.org/pdf/1607.05352.pdf
The 3b1b video on the topic does an amazing job
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?
Sorry, you're linking me to the same video that I just pointed out doesn't even mention this topic?
In the video, it mentions that the determinant of a 3x3 matrix represents the volume of the parallelepiped formed by transforming the unit cube aligned with the basis vectors. It explains that the determinant gives the factor by which volumes are scaled, just as determinants in 2D represent the scaling of areas. The video also mentions that a determinant of 0 indicates that all of space is squished onto something with 0 volume, like a flat plane, line, or single point.
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.
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.
> In the video, it mentions that the determinant of a 3x3 matrix represents the volume of the parallelepiped formed by transforming the unit cube aligned with the basis vectors. It explains that the determinant gives the factor by which volumes are scaled, just as determinants in 2D represent the scaling of areas.
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
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.
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.
To clarify I only meant the geometric intuition
TIL Lewis Caroll was also a mathematician.
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...
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...
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."
- - -
- - -
"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."
- - -
How so?
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.
I second the recommendation for The Annotated Alice, even if many references fly over my head as I'm not much of a mathemagician.
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.
I'll add to the list: Dolph Lundgren won a Fulbright to MIT and has a masters in chemical engineering.
>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.
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.
Did you do this research on the other folks mentioned, or just the woman?
Edit 3: TL;DR - in many ways, it's Lamarr's part of the invention that is still in use today. The implementation produced by Antheil (and Mackowen) was basically rejected by the military as being impractical for their applications (it involved pneumatics, though there are disputes about the reasons for disinterest, at least at first, by the military). People who had worked on related ideas earlier, and even concurrently, had tried things like "wobbling" the signal, or moving in frequencies in other ways. AFAIK, the truly novel art and most important idea here, is "prearranged sequence of frequencies", a very "digital" (i.e. "discrete") and "programmatic", essentially, idea for the time. This was even before the Colossus computers and ~concurrent with creation of devices like the "Enigma" machines ... having forms of "programmability", more "digital" types of operation, etc. I don't think it's easy to be certain of many aspects of what exactly happened, but I do think crediting Lamarr for this invention is very clearly warranted, based on my knowledge of events.
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..."
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..."
And Tony Hoare was a "Classics and Philosophy" major.
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.
[deleted]
I like the cofactors method as it helps me track signs by relating i to the column and row positions
At O(n!) it's not very sensible beyond about 4×4 though (unless your matrix has a lot of zeros).
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.
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.
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.