6 ms·

How Lewis Carroll computed determinants

98 points by alberto_ol 3y ago

vivegi 3y 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 3y 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 3y 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 3y ago
TIL Lewis Caroll was also a mathematician.
- thundermuffin 3y 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-secret-ingredient-math https://www.npr.org/2010/03/13/124632317/the-mad-hatters-sec...
  - tmtvl 3y 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.
  - thumbuddy 3y 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 3y 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." - - -
ivansavz 3y 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?
- shreyshnaccount 3y ago
  The 3b1b video on the topic does an amazing job
  - thaumasiotes 3y 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?
    - kordlessagain 3y ago
      https://www.youtube.com/watch?v=Ip3X9LOh2dk https://www.youtube.com/watch?v=Ip3X9LOh2dk
      - thaumasiotes 3y ago
        Sorry, you're linking me to the same video that I just pointed out doesn't even mention this topic?
        kordlessagain 3y ago
        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.
diracs_stache 3y ago
I like the cofactors method as it helps me track signs by relating i to the column and row positions
- mkl 3y ago
  At O(n!) it's not very sensible beyond about 4×4 though (unless your matrix has a lot of zeros).
thumbuddy 3y 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 3y 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
  - hgsgm 3y 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.)
- ajkjk 3y 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 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 3y 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.

98 points by alberto_ol 3y 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 3y 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 3y 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 3y ago

TIL Lewis Caroll was also a mathematician.

thundermuffin 3y 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-secret-ingredient-math https://www.npr.org/2010/03/13/124632317/the-mad-hatters-sec...
- tmtvl 3y 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.
- thumbuddy 3y 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 3y 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." - - -

ivansavz 3y 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?

shreyshnaccount 3y ago
The 3b1b video on the topic does an amazing job
- thaumasiotes 3y 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?
  - kordlessagain 3y ago
    https://www.youtube.com/watch?v=Ip3X9LOh2dk https://www.youtube.com/watch?v=Ip3X9LOh2dk
    - thaumasiotes 3y ago
      Sorry, you're linking me to the same video that I just pointed out doesn't even mention this topic?
      - kordlessagain 3y ago
        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.

diracs_stache 3y ago

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

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

thumbuddy 3y 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 3y 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
- hgsgm 3y 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.)
ajkjk 3y 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 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 3y 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.