Lewis Carroll and the red hot potato: a graph theoretic approach to a linear algebraic identity

DOI10.1016/J.DISC.2020.112160MaRDI QIDQ2219953zbMATH OpenOpenAlexFDO

Authors Melanie Fraser

Publication date 21 January 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.00068

zbMATH Keywords

graph algorithmsmatrix tree theoremdeterminantal identitiesspanning forestssigned involutionsdodgson polynomials

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05)

Abstract: The Lewis Carroll Identity expresses the determinant of a matrix in terms of subdeterminants obtained by deleting one row and column or a pair of rows and columns. Using the matrix tree theorem, we can convert this into an equivalent identity involving sums over pairs of forests. Unlike the Lewis Carroll Identity, the Forest Identity involves no minus signs. In 2011, Vlasev and Yeats suggested that such a Forest Identity could be proven using edge transfers similar to Zeilberger's 1997 matrix proof. However, until now, such an algorithm has not yet been developed. In this paper, we provide this edge transfer algorithm and a bijective proof for both the Lewis Carroll Identity and Forest Identity. This bijection is implemented by the Red Hot Potato algorithm, so called because the way edges get tossed back and forth between the two forests is reminiscent of the children's game of hot potato.

Recommendations

• A condensed condensation proof of a determinant evaluation conjectured by Greg Kuperberg and Jim Propp
• scientific article; zbMATH DE number 7731172
• scientific article; zbMATH DE number 825150
• Chiò's and Dodgson's determinantal identities
• A four-vertex, quadratic, spanning forest polynomial identity

Cites work

• A Combinatorial Proof of the All Minors Matrix Tree Theorem
• A four-vertex, quadratic, spanning forest polynomial identity
• Dodgon's determinant-evaluation rule proved by TWO-TIMING MEN and WOMEN
• Dodgson polynomial identities
• Method for constructing bijections for classical partition identities
• Quantum field theory over \(\mathbb F_q\)
• Spanning forest polynomials and the transcendental weight of Feynman graphs

Cited in

(1)

• scientific article; zbMATH DE number 7731172 (Why is no real title available?)

This page was built for publication: Lewis Carroll and the red hot potato: a graph theoretic approach to a linear algebraic identity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2219953)