Lindström Nonintersecting Paths

Theory

Given a set of sources S and a set of sinks T in a directed acyclic graph, let M be the path matrix where M_i,j represents the total number of paths from S_i to T_j.

According to the lemma, the determinant of the path matrix M is equal to the sum of the signed weights of all non-intersecting path families. Specifically, for a 2x2 matrix, this is the number of disjoint identity families (where S₁ goes to T₁ and S₂ goes to T₂) minus the number of disjoint swapped families (where S₁ goes to T₂ and S₂ goes to T₁).

Experiment

In this interactive module, you can explore the Lindström-Gessel-Viennot lemma in a grid-like directed acyclic graph where paths can only move right and up.

1. Use the Terminals control to change the configuration of the sink nodes. You can select "Swapped sinks" to reverse the roles of identity and swapped path families, or "Shared sink" which naturally collapses the Determinant to zero.
2. Use the Obstacle control and select "Center" to place a block in the center of the grid, limiting the available paths and reducing the total disjoint families.
3. Compare the resulting Determinant and Signed family count observable results.

Worked Example

Consider the default configuration with "Separated" terminals and "None" as the obstacle. We want to find the number of paths between the sources S_1 = (0,0), S_2 = (0,1) and sinks T_1 = (3,1), T_2 = (3,2).

1. For S_1 → T_1, we move 3 units right and 1 unit up. This can be done in C(4, 1) = 4 ways. So, M_(11) = 4.
2. For S_1 → T_2, we move 3 units right and 2 units up. This is C(5, 2) = 10 ways. So, M_(12) = 10.
3. For S_2 → T_1, we move 3 units right and 0 units up. There is exactly C(3, 0) = 1 way. So, M_(21) = 1.
4. For S_2 → T_2, we move 3 units right and 1 unit up. This is C(4, 1) = 4 ways. So, M_(22) = 4.

The path matrix M is:

M = [ 4, 10 ]
    [ 1,  4 ]

Det(M) = (4 * 4) - (10 * 1) = 16 - 10 = 6

We can independently verify this by counting disjoint identity families. There are 6 disjoint identity families and 0 disjoint swapped families. The signed sum is exactly 6 - 0 = 6.

Limitations

This module only considers a simple right-up grid graph without edge weights or cycles. The Lindström-Gessel-Viennot lemma applies more generally to weighted directed acyclic graphs and arbitrary sizes of sets S and T. In the case of intersecting paths, the intersections cancel each other out in the determinant summation, which is what the theorem relies upon.

References

For a detailed proof and explanation of the lemma, please see the following resource:

• Trinity College Dublin Mathematics: The Lindström-Gessel-Viennot Lemma