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

DOI10.1016/J.DISC.2020.112160zbMATH Open1455.05044arXiv1804.00068OpenAlexW3090127463MaRDI QIDQ2219953FDOQ2219953

Authors: Melanie Fraser Edit this on Wikidata

Publication date: 21 January 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

graph algorithmsmatrix tree theoremdeterminantal identitiesspanning forestssigned involutionsdodgson polynomials

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• Title not available (Why is that?)

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)