Talk:Lindström–Gessel–Viennot lemma

Proof corrected

When editing the proof of the LGV lemma, please keep the following two subtleties in mind:

• The $a={\frac {1}{2}}(a+a)$ trick is not available over an arbitrary commutative ring. Cancelling addends is the way to go here (I wouldn't go into further details on the Wikipedia, but if necessary this can be deduced from first principles -- e.g., introduce a total order on ${\mathcal {E}}$ and split the sum into the addends with $f(P)>P$ and those with $f(P)<P$).

• I don't know a correct way of constructing the involution by picking the lexicographically smallest pair $(i,j)$ such that the paths $P_{i}$ and $P_{j}$ intersect. The solution to Exercise 13 in Mark Wildon's lecture notes on symmetric functions ( http://www.ma.rhul.ac.uk/~uvah099/Maths/Sym/SymFuncs2020.pdf ) shows how this gives a non-involution for `n` = 3 (independently of which intersection of $P_{i}$ and $P_{j}$ we choose).

The proof requires carefulness indeed, and both of the errors above appear in multiple textbooks. Let's make the Wikipedia better than that. -- Darij (talk) 11:28, 7 June 2021 (UTC)