nLab Dodgson condensation

Idea

Dodgson condensation is a method of calculating the determinant of $n\times n$-matrix by means of a determinant of $(n-1)\times(n-1)$-matrix whose entries are $2\times 2$-minors of the original entry and divided by certain correction. This gives an algorithm for computing determinants of order $n$ in cubic time in $n$.

It is related to cluster algebras and so called T-system. Its underlying “Lewis Caroll” identity (also called Desnanot-Jacobi relation) is, as shown by Gelfand et al., a special case of Sylvester identity?. Desnanot-Jacobi relation is sometimes extended to octahedron recurrence.

Literature

• wikipedia

The method is from

• C. Dodgson, Condensation of determinants, Proc. R. Soc. Lond. 15 (1866) 150–155

Extra terms cancel thanks to appearance of some alternating sign matrix alluded to in

• Andrew N. W. Hone, Dodgson condensation, alternating signs and square ice, Phil. Trans. R. Soc. A (2006) 364, 3183–3198 doi

On relation to octahedron recurrence

• David E. Speyer, Perfect matchings and the octahedron recurrence, J. Algebr. Comb. (2007) 25:309–348 doi

• Israel Gelfand, Sergei Gelfand, Vladimir Retakh, Robert Lee Wilson, Quasideterminants, Advances in Mathematics 193 (2005) 56–141 doi

• Doron Zeilberger, Dodgson’s determinant-evaluation rule proved by two-timing men and women, Electron. J. Comb. 4 (2), art. R22 doihttps://doi.org/10.37236/1337)

• MathOverflow: geometric-interpretation-of-the-desnanot-jacobi-identity

Robinson–Schensted–Knuth correspondence satisfies the octahedron recurrence. In the following article this is established with a point of view that RSK correspondence is a tropicalization? of Dodgson condensation rule,

• V.I. Danilov, G. A. Koshevoy, The octahedron recurrence and RSK-correspondence, Sém. Lothar. Combin. 54A (2005/07) Art. B54An, 16 pp. (electronic) published pdf arXiv:math.CO/0703414

category: algebra