Into the Woods: A graph theoretic proof of the Dodgson/Muir identity

2021/10/03 by Melanie Fraser, Fraser, Melanie
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2110.01026

openalex publication_date 2021/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Dodgson/Muir Identity is an identity on determinants of matrix minors that generalizes the Dodgson Identity. Using the matrix tree theorem, we create an equivalent forest identity on ordered sets of k forests. We then prove the generalized Forest Identity, and by extension the Dodgson/Muir Identity, using an edge-swapping involution. This algorithm is a generalization of the Red Hot Potato algorithm, developed by the author in 2021 to prove the Dodgson Identity.

Citations

• How to encode a tree

Related

• Lewis Carroll and the Red Hot Potato: a graph theoretic approach to a\n linear algebraic identity
• A four-vertex, quadratic, spanning forest polynomial identity
• A Mathematical Proof of Dodgson's Algorithm
• A combinatorial identity with applications to forest graphs
• Taylor Expansion Proof of the Matrix Tree Theorem - Part II