Paths must cross in Lindström-Gessel-Viennot on the lattice The following question (which I am going to answer myself) serves
to close a little gap in some combinatorial proofs that use the
Lindström--Gessel--Viennot lemma. Namely, I will show a little lemma,
which is mostly used tacitly. Roughly speaking, the lemma says that if $p$ and
$p^{\prime}$ are two lattice paths (using north and east steps only) in
$\mathbb{Z}^{2}$ such that the starting point of $p^{\prime}$ lies weakly
northwest of the starting point of $p$ but the ending point of $p$ lies weakly
northwest of the ending point of $p^{\prime}$, then $p$ and $p^{\prime}$ must
have a point in common. (I shall state this formally in Lemma 1 below.) See
also Proposition 2 for how this result gets used. The lemma may appear rather
intuitive (it is similar to the fact that the game of Hex cannot end in a
draw), but the
short geometric arguments would be a pain to formalize, so I will prove it combinatorially.
Basic definitions and Lemma 1
The lattice shall mean the (infinite) directed graph whose vertices are all
pairs of integers (that is, its vertex set is $\mathbb{Z}^{2}$), and whose
arcs are
\begin{align*}
\left(  i,j\right)   &  \rightarrow\left(  i,j+1\right)  \qquad\text{for all
}\left(  i,j\right)  \in\mathbb{Z}^2 \text{,} \qquad \text{and}\\
\left(  i,j\right)   &  \rightarrow\left(  i+1,j\right)  \qquad\text{for all
}\left(  i,j\right)  \in\mathbb{Z}^2 \text{.}
\end{align*}
The arcs of the first kind are called north-steps, whereas the arcs
of the second kind are called east-steps. The vertices of the lattice
will just be called vertices. We draw the lattice as the usual
integer lattice in the Cartesian plane.
For each vertex $v=\left(  i,j\right)  $, we set $\operatorname*{x}\left(
v\right)  =i$ and $\operatorname*{y}\left(  v\right)  =j$. We refer to
$\operatorname*{x}\left(  v\right)  $ as the x-coordinate of $v$, and
to $\operatorname*{y}\left(  v\right)  $ as the y-coordinate of $v$.
A path will simply mean a (directed) path in the lattice. 

Lemma 1. Let $A$, $B$, $A^{\prime}$ and $B^{\prime}$ be four vertices such
  that
  \begin{align*}
\operatorname*{x}\left(  A^{\prime}\right)    & \leq\operatorname*{x}\left(
A\right)  ,\qquad\operatorname*{y}\left(  A^{\prime}\right)  \geq
\operatorname*{y}\left(  A\right)  ,\\
\operatorname*{x}\left(  B^{\prime}\right)    & \leq\operatorname*{x}\left(
B\right)  ,\qquad\operatorname*{y}\left(  B^{\prime}\right)  \geq
\operatorname*{y}\left(  B\right)  .
\end{align*}
  Let $p$ be a path from $A$ to $B^{\prime}$. Let $p^{\prime}$ be a path from
  $A^{\prime}$ to $B$. Then, $p$ and $p^{\prime}$ have a vertex in common.

See Fig. 1 for an illustration of Lemma 1.


  Fig. 1: Lemma 1.

Non-intersecting lattice paths and Proposition 2
Now, fix a nonnegative integer $k$. Let $\left[  k\right]  $ be the set
$\left\{  1,2,\ldots,k\right\}  $. Let $\mathfrak{S}_{k}$ be the group of all
permutations of $\left[  k\right]  $.
A $k$-vertex shall mean a $k$-tuple of vertices. If $\mathbf{v}
=\left(  A_{1},A_{2},\ldots,A_{k}\right)  $ is a $k$-vertex, and if $\sigma
\in\mathfrak{S}_{k}$, then $\sigma\left(  \mathbf{v}\right)  $ denotes the
$k$-vertex $\left(  A_{\sigma\left(  1\right)  },A_{\sigma\left(  2\right)
},\ldots,A_{\sigma\left(  k\right)  }\right)  $.
If $\left(  A_{1},A_{2},\ldots,A_{k}\right)  $ and $\left(  B_{1},B_{2}
,\ldots,B_{k}\right)  $ are two $k$-vertices, then a NILP from
$\left(  A_{1},A_{2},\ldots,A_{k}\right)  $ to $\left(  B_{1},B_{2}
,\ldots,B_{k}\right)  $ shall mean a $k$-tuple $\left(  p_{1},p_{2}
,\ldots,p_{k}\right)  $ of paths such that


*

*each $p_{i}$ is a path from $A_{i}$ to $B_{i}$;

*no two of the paths $p_{1},p_{2},\ldots,p_{k}$ have a vertex in common.
("NILP" stands for "non-intersecting lattice paths", but note that the paths must
neither cross nor touch.)
See Fig. 2 for an example of a NILP (with $k = 3$).


  Fig. 2: a NILP with $k = 3$.

If $\mathbf{u}$ and $\mathbf{v}$ are two $k$-vertices, then $N\left(
\mathbf{u},\mathbf{v}\right)  $ denotes the set of all NILPs from $\mathbf{u}$
to $\mathbf{v}$.
A pair $\left(  \mathbf{u},\mathbf{v}\right)  $ of two $k$-vertices
$\mathbf{u}$ and $\mathbf{v}$ is said to be nonpermutable if and only
if every $\sigma\in\mathfrak{S}_{k}$ satisfying $\sigma\neq\operatorname*{id}$
satisfies $N\left(  \mathbf{u},\sigma\left(  \mathbf{v}\right)  \right)
=\varnothing$. Note that we are not requiring that $N\left(  \mathbf{u}
,\mathbf{v}\right)  \neq\varnothing$ here.

Proposition 2. Let $\mathbf{u}=\left(  A_{1},A_{2},\ldots,A_{k}\right)  $
  and $\mathbf{v}=\left(  B_{1},B_{2},\ldots,B_{k}\right)  $ be two $k$-vertices
  such that
  \begin{align*}
\operatorname*{x}\left(  A_{1}\right)   &  \geq\operatorname*{x}\left(
A_{2}\right)  \geq\cdots\geq\operatorname*{x}\left(  A_{k}\right)  ;\\
\operatorname*{y}\left(  A_{1}\right)   &  \leq\operatorname*{y}\left(
A_{2}\right)  \leq\cdots\leq\operatorname*{y}\left(  A_{k}\right)  ;\\
\operatorname*{x}\left(  B_{1}\right)   &  \geq\operatorname*{x}\left(
B_{2}\right)  \geq\cdots\geq\operatorname*{x}\left(  B_{k}\right)  ;\\
\operatorname*{y}\left(  B_{1}\right)   &  \leq\operatorname*{y}\left(
B_{2}\right)  \leq\cdots\leq\operatorname*{y}\left(  B_{k}\right)  .
\end{align*}
  Then, the pair $\left(  \mathbf{u},\mathbf{v}\right)  $ is nonpermutable.

Note that the situation of Proposition 2 is illustrated on Fig. 2.
What is this for?
Here is why Proposition 2 is useful. Let $R$ be a commutative ring. Assume
that for each arc $a$ of the lattice, some element $\omega_{a}\in R$ is given.
We call this element $\omega_{a}$ the weight of $a$. If $p$ is any path,
then we let $\omega\left(  p\right)  $ be the product of the weights
$\omega_{a}$ over all arcs $a$ of $p$. If $\mathbf{p}=\left(  p_{1}
,p_{2},\ldots,p_{k}\right)  $ is a NILP from a $k$-vertex $\mathbf{u}$ to a
$k$-vertex $\mathbf{v}$, then we define the weight $\omega\left(
\mathbf{p}\right)  $ of this NILP $\mathbf{p}$ to be the product $\prod
_{i=1}^{k}\omega\left(  p_{i}\right)  $.
If $A$ and $B$ are two vertices, then $N\left(  A,B\right)  $ shall denote the
set of all paths from $A$ to $B$.
Now, recall that the lattice (as a directed graph) is acyclic. Hence, the
Lindström--Gessel--Viennot lemma yields:

Theorem 3. Let $\mathbf{u}=\left(  A_{1},A_{2},\ldots,A_{k}\right)  $ and
  $\mathbf{v}=\left(  B_{1},B_{2},\ldots,B_{k}\right)  $ be two $k$-vertices.
  Then,
  \begin{align*}
 \det\left(  \left(  \sum_{p\in N\left(  A_{i},B_{j}\right)  }\omega\left(
p\right)  \right)  _{1\leq i\leq k,\ 1\leq j\leq k}\right) 
& =\sum_{\sigma\in\mathfrak{S}_{k}}\left(  -1\right)  ^{\sigma}\sum
_{\mathbf{p}\in N\left(  \mathbf{u},\sigma\left(  \mathbf{v}\right)  \right)
}\omega\left(  \mathbf{p}\right)  .
\end{align*}
  (Here, $\left(  -1\right)  ^{\sigma}$ denotes the sign of the permutation
  $\sigma$.)

If a pair $\left(  \mathbf{u},\mathbf{v}\right)  $ of two $k$-vertices is
nonpermutable, then the sum on the right hand side of Theorem 3 can be
simplified, as only one of its terms (if any) is nonzero. This, and
Proposition 2, leads to the following fact:

Corollary 4. Let $\mathbf{u}=\left(  A_{1},A_{2},\ldots,A_{k}\right)  $
  and $\mathbf{v}=\left(  B_{1},B_{2},\ldots,B_{k}\right)  $ be two $k$-vertices
  such that
  \begin{align*}
\operatorname*{x}\left(  A_{1}\right)   &  \geq\operatorname*{x}\left(
A_{2}\right)  \geq\cdots\geq\operatorname*{x}\left(  A_{k}\right)  ;\\
\operatorname*{y}\left(  A_{1}\right)   &  \leq\operatorname*{y}\left(
A_{2}\right)  \leq\cdots\leq\operatorname*{y}\left(  A_{k}\right)  ;\\
\operatorname*{x}\left(  B_{1}\right)   &  \geq\operatorname*{x}\left(
B_{2}\right)  \geq\cdots\geq\operatorname*{x}\left(  B_{k}\right)  ;\\
\operatorname*{y}\left(  B_{1}\right)   &  \leq\operatorname*{y}\left(
B_{2}\right)  \leq\cdots\leq\operatorname*{y}\left(  B_{k}\right)  .
\end{align*}
  Then,
  \begin{align*}
\det\left(  \left(  \sum_{p\in N\left(  A_{i},B_{j}\right)  }\omega\left(
p\right)  \right)  _{1\leq i\leq k,\ 1\leq j\leq k}\right)  =\sum
_{\mathbf{p}\in N\left(  \mathbf{u},\mathbf{v}\right)  }\omega\left(
\mathbf{p}\right)  .
\end{align*}

When people apply the Lindström--Gessel--Viennot lemma to the lattice
and don't get an alternating sum like in Theorem 3, they are usually
applying Corollary 4. For example, this is what is being done in the
classical
proof of the Jacobi--Trudi identities using Lindström--Gessel--Viennot.
 A: So here are proofs of Lemma 1, Proposition 2 and Corollary 4. I will not prove Theorem 3, since it is the classical Lindström--Gessel--Viennot lemma and has various proofs easily accessible (see, e.g., its Wikipedia page or the proof of Theorem 1 in Ira Gessel and X. G. Viennot, Determinants, Paths, and Plane Partitions).
Proof of Lemma 1
We shall first give a combinatorial proof of Lemma 1 that is completely rigorous and self-contained but rather dull and long. Then, we will sketch a second proof that relies on geometric intuition, as well as a third proof that serves as a sort of compromise between the first two (it is combinatorial and simpler than the first one, though formalizing it would be more laborious).
First proof of Lemma 1.
If $q$ is any path, then the length $\ell\left(  q\right)  $ of $q$ is
defined to be the number of arcs of $q$.
We shall now prove Lemma 1 by strong induction on $\ell\left(  p\right)
+\ell\left(  p^{\prime}\right)  $:
Induction step: Fix a nonnegative integer $N$. Assume (as the induction
hypothesis) that Lemma 1 holds whenever $\ell\left(  p\right)  +\ell\left(
p^{\prime}\right)  <N$. We must now prove that Lemma 1 holds when $\ell\left(
p\right)  +\ell\left(  p^{\prime}\right)  =N$.
So let $A$, $B$, $A^{\prime}$, $B^{\prime}$, $p$ and $p^{\prime}$ be as in
Lemma 1, and let us assume that $\ell\left(  p\right)  +\ell\left(  p^{\prime
}\right)  =N$. We must prove that $p$ and $p^{\prime}$ have a vertex in common.
Assume the contrary. Thus, $p$ and $p^{\prime}$ have no vertex in common.
The vertex $A$ belongs to the path $p$, and thus does not belong to the path
$p^{\prime}$ (since $p$ and $p^{\prime}$ have no vertex in common). Similarly,
the vertex $A^{\prime}$ does not belong to the path $p$.
Recall that each arc of the lattice is either an east-step or a north-step.
Thus, the x-coordinates of the vertices of a path are always weakly
increasing, and so are the y-coordinates. Hence, the existence of a path $p$
from $A$ to $B^{\prime}$ shows that $\operatorname{x}\left(  A\right)
\leq\operatorname{x}\left(  B^{\prime}\right)  $ and $\operatorname{y}
\left(  A\right)  \leq\operatorname{y}\left(  B^{\prime}\right)  $.
Similarly, the existence of a path $p^{\prime}$ from $A^{\prime}$ to $B$
yields $\operatorname{x}\left(  A^{\prime}\right)  \leq\operatorname{x}
\left(  B\right)  $ and $\operatorname{y}\left(  A^{\prime}\right)
\leq\operatorname{y}\left(  B\right)  $.
Next, we claim that $\ell\left(  p\right)  \neq0$.
[Proof: Assume the contrary. Thus, $\ell\left(  p\right)  =0$. Hence,
the path $p$ has no steps. Therefore, $A=B^{\prime}$ (since $p$ is a path from
$A$ to $B^{\prime}$). Hence, $\operatorname{y}\left(  A\right)
=\operatorname{y}\left(  B^{\prime}\right)  \geq\operatorname{y}\left(
B\right)  $, so that $\operatorname{y}\left(  A^{\prime}\right)
\geq\operatorname{y}\left(  A\right)  \geq\operatorname{y}\left(  B\right)
$. Combining this with $\operatorname{y}\left(  A^{\prime}\right)
\leq\operatorname{y}\left(  B\right)  $, we obtain $\operatorname{y}\left(
A^{\prime}\right)  =\operatorname{y}\left(  B\right)  $. Combining
$\operatorname{y}\left(  A^{\prime}\right)  \geq\operatorname{y}\left(
A\right)  $ with $\operatorname{y}\left(  A^{\prime}\right)
=\operatorname{y}\left(  B\right)  \leq\operatorname{y}\left(  A\right)  $,
we obtain $\operatorname{y}\left(  A^{\prime}\right)  =\operatorname{y}
\left(  A\right)  $. Thus, $\operatorname{y}\left(  A\right)
=\operatorname{y}\left(  A^{\prime}\right)  =\operatorname{y}\left(  B\right)  $.
Therefore, the vertex $A$ lies on the horizontal line that contains
$A^{\prime}$ and $B$. Furthermore, this vertex $A$ must lie on the line
segment between $A^{\prime}$ and $B$ (since $\operatorname{x}\left(
A^{\prime}\right)  \leq\operatorname{x}\left(  \underbrace{A}_{=B^{\prime}
}\right)  =\operatorname{x}\left(  B^{\prime}\right)  \leq\operatorname{x}
\left(  B\right)  $).
Recall again that the y-coordinates of the vertices of a path are always weakly
increasing. Moreover, they increase strictly whenever the path makes a
north-step. Hence, if the path $p^{\prime}$ would have any north-step, then we
would have $\operatorname{y}\left(  A^{\prime}\right)  <\operatorname{y}
\left(  B\right)  $ (since $p^{\prime}$ is a path from $A^{\prime}$ to $B$).
But this would contradict $\operatorname{y}\left(  A^{\prime}\right)
\geq\operatorname{y}\left(  B\right)  $. Hence, the path $p^{\prime}$ has no
north-step. Thus, $p^{\prime}$ consists entirely of east-steps. Hence,
$p^{\prime}$ contains every vertex on the line segment between $A^{\prime}$
and $B$. Therefore, $p^{\prime}$ contains the vertex $A$ (since the vertex $A$
lies on the line segment between $A^{\prime}$ and $B$). This contradicts the
fact that $A$ does not belong to the path $p^{\prime}$. This contradiction
shows that our assumption was false; hence, $\ell\left(  p\right)  \neq0$ is proven.]
Furthermore, we claim that $\ell\left(  p^{\prime}\right)  \neq0$.
[Proof: Assume the contrary. Thus, $\ell\left(  p^{\prime}\right)
=0$. Hence, the path $p^{\prime}$ has no steps. Therefore, $A^{\prime}=B$
(since $p^{\prime}$ is a path from $A^{\prime}$ to $B$). Hence,
$\operatorname{x}\left(  A^{\prime}\right)  =\operatorname{x}\left(
B\right)  \geq\operatorname{x}\left(  B^{\prime}\right)  $, so that
$\operatorname{x}\left(  A\right)  \geq\operatorname{x}\left(  A^{\prime
}\right)  \geq\operatorname{x}\left(  B^{\prime}\right)  $. Combining this
with $\operatorname{x}\left(  A\right)  \leq\operatorname{x}\left(
B^{\prime}\right)  $, we obtain $\operatorname{x}\left(  A\right)
=\operatorname{x}\left(  B^{\prime}\right)  $. Combining $\operatorname{x}
\left(  A\right)  \geq\operatorname{x}\left(  A^{\prime}\right)  $ with
$\operatorname{x}\left(  A^{\prime}\right)  \geq\operatorname{x}\left(
B^{\prime}\right)  =\operatorname{x}\left(  A\right)  $, we obtain
$\operatorname{x}\left(  A\right)  =\operatorname{x}\left(  A^{\prime
}\right)  $. Thus, $\operatorname{x}\left(  A^{\prime}\right)
=\operatorname{x}\left(  A\right)  =\operatorname{x}\left(  B^{\prime
}\right)  $. Therefore, the vertex $A^{\prime}$ lies on the vertical line that
contains $A$ and $B^{\prime}$. Furthermore, this vertex $A^{\prime}$ must lie
on the line segment between $A$ and $B^{\prime}$ (since $\operatorname{y}
\left(  A^{\prime}\right)  \geq\operatorname{y}\left(  A\right)  $ and
$\operatorname{y}\left(  \underbrace{A^{\prime}}_{=B}\right)
=\operatorname{y}\left(  B\right)  \leq\operatorname{y}\left(  B^{\prime
}\right)  $).
Recall again that the x-coordinates of the vertices of a path are always weakly
increasing. Moreover, they increase strictly whenever the path makes an
east-step. Hence, if the path $p$ would have any east-step, then we would have
$\operatorname{x}\left(  A\right)  <\operatorname{x}\left(  B^{\prime
}\right)  $ (since $p$ is a path from $A$ to $B^{\prime}$). But this would
contradict $\operatorname{x}\left(  A\right)  =\operatorname{x}\left(
B^{\prime}\right)  $. Hence, the path $p$ has no east-step. Thus, $p$ consists
entirely of north-steps. Hence, $p$ contains every vertex on the line segment
between $A$ and $B^{\prime}$. Therefore, $p$ contains the vertex $A^{\prime}$
(since the vertex $A^{\prime}$ lies on the line segment between $A$ and
$B^{\prime}$). This contradicts the fact that $A^{\prime}$ does not belong to
the path $p$. This contradiction shows that our assumption was false; hence,
$\ell\left(  p^{\prime}\right)  \neq0$ is proven.]
Let $P$ be the second vertex of the path $p$. (This is well-defined, since
$\ell\left(  p\right)  \neq0$.) Hence, $P$ lies on a path from $A$ to
$B^{\prime}$ (namely, on the path $p$). Therefore, $\operatorname{x}\left(
A\right)  \leq\operatorname{x}\left(  P\right)  \leq\operatorname{x}\left(
B^{\prime}\right)  $ (since the x-coordinates of the vertices of a path are
always weakly increasing) and $\operatorname{y}\left(  A\right)
\leq\operatorname{y}\left(  P\right)  \leq\operatorname{y}\left(  B^{\prime
}\right)  $ (since the y-coordinates of the vertices of a path are always weakly
increasing). Let $r$ be the path from $P$ to $B^{\prime}$ obtained by removing
the first arc from $p$. Thus, $r$ is a subpath of $p$. Hence, the paths $r$
and $p^{\prime}$ have no vertex in common (since $p$ and $p^{\prime}$ have no
vertex in common). Also, $\ell\left(  r\right)  =\ell\left(  p\right)
-1<\ell\left(  p\right)  $ and thus $\underbrace{\ell\left(  r\right)
}_{<\ell\left(  p\right)  }+\ell\left(  p^{\prime}\right)  <\ell\left(
p\right)  +\ell\left(  p^{\prime}\right)  =N$.
Moreover, $\operatorname{x}\left(  A^{\prime}\right)  \leq\operatorname{x}
\left(  A\right)  \leq\operatorname{x}\left(  P\right)  $. If we had
$\operatorname{y}\left(  A^{\prime}\right)  \geq\operatorname{y}\left(
P\right)  $, then we could apply Lemma 1 to $P$ and $r$ instead of $A$ and $p$
(by the induction hypothesis, since $\ell\left(  r\right)  +\ell\left(
p^{\prime}\right)  <N$). We thus would conclude that the paths $r$ and
$p^{\prime}$ have a vertex in common; this would contradict the fact that the
paths $r$ and $p^{\prime}$ have no vertex in common. Hence, we cannot have
$\operatorname{y}\left(  A^{\prime}\right)  \geq\operatorname{y}\left(
P\right)  $. Thus, $\operatorname{y}\left(  A^{\prime}\right)
<\operatorname{y}\left(  P\right)  $. Hence, $\operatorname{y}\left(
A^{\prime}\right)  \leq\operatorname{y}\left(  P\right)  -1$ (since
$\operatorname{y}\left(  A^{\prime}\right)  $ and $\operatorname{y}\left(
P\right)  $ are integers).
But $P$ is the next vertex after $A$ on the path $p$. Hence, there is an arc
from $A$ to $P$. If this arc was an east-step, then we would have
$\operatorname{y}\left(  P\right)  =\operatorname{y}\left(  A\right)  $,
which would contradict $\operatorname{y}\left(  A\right)  \leq
\operatorname{y}\left(  A^{\prime}\right)  <\operatorname{y}\left(
P\right)  $. Hence, this arc cannot be an east-step. Thus, this arc must be a
north-step. Therefore, $\operatorname{y}\left(  P\right)  =\operatorname{y}
\left(  A\right)  +1$ and $\operatorname{x}\left(  P\right)
=\operatorname{x}\left(  A\right)  $. Combining $\operatorname{y}\left(
A^{\prime}\right)  \leq\operatorname{y}\left(  P\right)  -1=\operatorname{y}
\left(  A\right)  $ (since $\operatorname{y}\left(  P\right)
=\operatorname{y}\left(  A\right)  +1$) with $\operatorname{y}\left(
A^{\prime}\right)  \geq\operatorname{y}\left(  A\right)  $, we obtain
$\operatorname{y}\left(  A^{\prime}\right)  =\operatorname{y}\left(
A\right)  $.
Let $P^{\prime}$ be the second vertex on the path $p^{\prime}$. (This is
well-defined, since $\ell\left(  p^{\prime}\right)  \neq0$.) Hence,
$P^{\prime}$ lies on a path from $A^{\prime}$ to $B$ (namely, on the path
$p^{\prime}$). Therefore, $\operatorname{x}\left(  A^{\prime}\right)
\leq\operatorname{x}\left(  P^{\prime}\right)  \leq\operatorname{x}\left(
B\right)  $ (since the x-coordinates of the vertices of a path are always weakly
increasing) and $\operatorname{y}\left(  A^{\prime}\right)  \leq
\operatorname{y}\left(  P^{\prime}\right)  \leq\operatorname{y}\left(
B\right)  $ (since the y-coordinates of the vertices of a path are always weakly
increasing). Let $r^{\prime}$ be the path from $P^{\prime}$ to $B$ obtained by
removing the first arc from $p^{\prime}$. Thus, $r^{\prime}$ is a subpath of
$p^{\prime}$. Hence, the paths $p$ and $r^{\prime}$ have no vertex in common
(since $p$ and $p^{\prime}$ have no vertex in common). Also, $\ell\left(
r^{\prime}\right)  =\ell\left(  p^{\prime}\right)  -1<\ell\left(  p^{\prime
}\right)  $ and thus $\ell\left(  p\right)  +\underbrace{\ell\left(
r^{\prime}\right)  }_{<\ell\left(  p^{\prime}\right)  }<\ell\left(  p\right)
+\ell\left(  p^{\prime}\right)  =N$.
Moreover, $\operatorname{y}\left(  P^{\prime}\right)  \geq\operatorname{y}
\left(  A^{\prime}\right)  \geq\operatorname{y}\left(  A\right)  $. If we had
$\operatorname{x}\left(  P^{\prime}\right)  \leq\operatorname{x}\left(
A\right)  $, then we could apply Lemma 1 to $P^{\prime}$ and $r^{\prime}$
instead of $A^{\prime}$ and $p^{\prime}$ (by the induction hypothesis, since
$\ell\left(  p\right)  +\ell\left(  r^{\prime}\right)  <N$). We thus would
conclude that the paths $p$ and $r^{\prime}$ have a vertex in common; this
would contradict the fact that the paths $p$ and $r^{\prime}$ have no vertex
in common. Hence, we cannot have $\operatorname{x}\left(  P^{\prime}\right)
\leq\operatorname{x}\left(  A\right)  $. Thus, $\operatorname{x}\left(
P^{\prime}\right)  >\operatorname{x}\left(  A\right)  $. Hence,
$\operatorname{x}\left(  P^{\prime}\right)  \geq\operatorname{x}\left(
A\right)  +1$ (since $\operatorname{x}\left(  P^{\prime}\right)  $ and
$\operatorname{x}\left(  A\right)  $ are integers).
But $P^{\prime}$ is the next vertex after $A^{\prime}$ on the path $p^{\prime
}$. Hence, there is an arc from $A^{\prime}$ to $P^{\prime}$. If this arc was
a north-step, then we would have $\operatorname{x}\left(  P^{\prime}\right)
=\operatorname{x}\left(  A^{\prime}\right)  $, which would contradict
$\operatorname{x}\left(  A^{\prime}\right)  \leq\operatorname{x}\left(
A\right)  <\operatorname{x}\left(  P^{\prime}\right)  $. Hence, this arc
cannot be a north-step. Thus, this arc must be an east-step. Therefore,
$\operatorname{y}\left(  P^{\prime}\right)  =\operatorname{y}\left(
A^{\prime}\right)  $ and $\operatorname{x}\left(  P^{\prime}\right)
=\operatorname{x}\left(  A^{\prime}\right)  +1$. Hence, $\operatorname{x}
\left(  A^{\prime}\right)  +1=\operatorname{x}\left(  P^{\prime}\right)
\geq\operatorname{x}\left(  A\right)  +1$, so that $\operatorname{x}\left(
A^{\prime}\right)  \geq\operatorname{x}\left(  A\right)  $. Combining this
with $\operatorname{x}\left(  A^{\prime}\right)  \leq\operatorname{x}\left(
A\right)  $, we obtain $\operatorname{x}\left(  A^{\prime}\right)
=\operatorname{x}\left(  A\right)  $.
Now, the vertices $A$ and $A^{\prime}$ have the same x-coordinate (since
$\operatorname{x}\left(  A^{\prime}\right)  =\operatorname{x}\left(
A\right)  $) and the same y-coordinate (since $\operatorname{y}\left(
A^{\prime}\right)  =\operatorname{y}\left(  A\right)  $). Hence, these two
vertices are equal. In other words, $A=A^{\prime}$. Hence, the vertex $A$
belongs to the path $p^{\prime}$ (since the vertex $A^{\prime}$ belongs to the
path $p^{\prime}$). This contradicts the fact that the vertex $A$ does not
belong to the path $p^{\prime}$. This contradiction shows that our assumption
was false. Hence, we have shown that $p$ and $p^{\prime}$ have a vertex in common.
Now, forget that we fixed $A$, $B$, $A^{\prime}$, $B^{\prime}$, $p$ and
$p^{\prime}$. We thus have proven that if $A$, $B$, $A^{\prime}$, $B^{\prime}
$, $p$ and $p^{\prime}$ are as in Lemma 1, and if $\ell\left(  p\right)
+\ell\left(  p^{\prime}\right)  =N$, then $p$ and $p^{\prime}$ have a vertex
in common. In other words, Lemma 1 holds when $\ell\left(  p\right)
+\ell\left(  p^{\prime}\right)  =N$. This completes the induction step. Hence,
Lemma 1 is proven.
Second proof of Lemma 1 (sketched). Recall that each arc of the lattice is
either an east-step or a north-step. Thus, the x-coordinates of the vertices
of a path are always weakly increasing, and so are the y-coordinates. Hence,
the existence of a path $p$ from $A$ to $B^{\prime}$ shows that
$\operatorname{x}\left(  A\right)  \leq\operatorname{x}\left(  B^{\prime
}\right)  $ and $\operatorname{y}\left(  A\right)  \leq\operatorname{y}
\left(  B^{\prime}\right)  $. Similarly, the existence of $p^{\prime}$ yields
$\operatorname{x}\left(  A^{\prime}\right)  \leq\operatorname{x}\left(
B\right)  $ and $\operatorname{y}\left(  A^{\prime}\right)  \leq
\operatorname{y}\left(  B\right)  $.
Thus,
\begin{align*}
\operatorname{x}\left(  A^{\prime}\right)   &  \leq\operatorname{x}\left(
A\right)  \leq\operatorname{x}\left(  B^{\prime}\right)  \leq
\operatorname{x}\left(  B\right)  \qquad\text{and}\\
\operatorname{y}\left(  A\right)   &  \leq\operatorname{y}\left(  A^{\prime
}\right)  \leq\operatorname{y}\left(  B\right)  \leq\operatorname{y}\left(
B^{\prime}\right)  .
\end{align*}
Now, consider the rectangle (drawn in black on Fig. 3) whose four sides are given by the equations
\begin{align*}
x=\operatorname{x}\left(  A^{\prime}\right)  ,\qquad y=\operatorname{y}
\left(  A\right)  ,\qquad x=\operatorname{x}\left(  B\right)  ,\qquad
y=\operatorname{y}\left(  B^{\prime}\right)  ,
\end{align*}
respectively (all in Cartesian coordinates). Then, the path $p$ joins two
opposite sides of this rectangle (namely, the second and the fourth), whereas
the path $p^{\prime}$ joins the other two sides of this rectangle; moreover,
both paths stay fully within the rectangle (due to $\operatorname{x}\left(
A^{\prime}\right)  \leq\operatorname{x}\left(  A\right)  \leq
\operatorname{x}\left(  B^{\prime}\right)  \leq\operatorname{x}\left(
B\right)  $ and $\operatorname{y}\left(  A\right)  \leq\operatorname{y}
\left(  A^{\prime}\right)  \leq\operatorname{y}\left(  B\right)
\leq\operatorname{y}\left(  B^{\prime}\right)  $). Hence, it is geometrically
obvious that $p$ and $p^{\prime}$ must meet; in other words, $p$ and
$p^{\prime}$ have a vertex in common. This proves Lemma 1 (if you trust this
geometric shortcut).


Fig. 3: illustration for the second and third proofs of Lemma 1, showing the rectangle and the extended paths $\widetilde{p}$ and $\widetilde{p^{\prime}}$.

Third proof of Lemma 1 (sketched). Proceed as in the Second proof above, up
until the "geometrically obvious" step. We are going to prove combinatorially
that $p$ and $p^{\prime}$ have a vertex in common.
Indeed, assume the contrary. Hence, the paths $p$ and $p^{\prime}$ have no
vertex in common.
We extend the path $p$ to a bidirectionally infinite path $\widetilde{p}$ by
vertical steps (i.e., arcs of the form $\left(  i,j\right)  \rightarrow\left(
i,j+1\right)  $) in both directions (so the path $\widetilde{p}$ first reaches
$A$ through infinitely many north-steps, then proceeds to $B^{\prime}$ along
$p$, and then leaves $B^{\prime}$ along infinitely many north-steps). (These new steps are the dashed red steps in Fig. 3.)
We extend the path $p^{\prime}$ to a bidirectionally infinite path
$\widetilde{p^{\prime}}$ by horizontal steps (i.e., arcs of the form $\left(
i,j\right)  \rightarrow\left(  i+1,j\right)  $) in both directions. (These new steps are the dashed blue steps in Fig. 3.)
The
resulting infinite paths $\widetilde{p}$ and $\widetilde{p^{\prime}}$ have no
vertex in common (indeed, the paths $p$ and $p^{\prime}$ stay within the
rectangle discussed above, and have no vertex in common; meanwhile, the new
steps we have added to them to obtain $\widetilde{p}$ and
$\widetilde{p^{\prime}}$ escape this rectangle normally in four different
directions, whence they intersect neither each other nor $p$ or $p^{\prime}$).
Recall that each arc of the lattice is either an east-step or a north-step.
Thus, if a vertex $C$ runs through a path, the value $\operatorname{x}\left(
C\right)  +\operatorname{y}\left(  C\right)  $ is incremented by $1$ with
each step. Hence, if $q$ is a bidirectionally infinite path, then, for each
$N\in\mathbb{Z}$, there is a unique vertex $C$ of $q$ satisfying
$\operatorname{x}\left(  C\right)  +\operatorname{y}\left(  C\right)  =N$.
Denote this vertex $C$ by $h_{N}\left(  q\right)  $. Thus, the vertices of $q$
are $\ldots,h_{-1}\left(  q\right)  ,h_{0}\left(  q\right)  ,h_{1}\left(
q\right)  ,\ldots$ in this order.
All sufficiently low $N\in\mathbb{Z}$ satisfy $\operatorname{x}\left(
h_{N}\left(  \widetilde{p^{\prime}}\right)  \right)  <\operatorname{x}\left(
h_{N}\left(  \widetilde{p}\right)  \right)  $, whereas all sufficiently high
$N\in\mathbb{Z}$ satisfy $\operatorname{x}\left(  h_{N}\left(
\widetilde{p^{\prime}}\right)  \right)  >\operatorname{x}\left(  h_{N}\left(
\widetilde{p}\right)  \right)  $. Hence, the set of all $N\in\mathbb{Z}$ that
satisfy $\operatorname{x}\left(  h_{N}\left(  \widetilde{p^{\prime}}\right)
\right)  <\operatorname{x}\left(  h_{N}\left(  \widetilde{p}\right)  \right)
$ is a nonempty set of integers that is bounded from above. Therefore, this
set has a maximum. Let $M$ be this maximum. Thus, $M\in\mathbb{Z}$ satisfies
$\operatorname{x}\left(  h_{M}\left(  \widetilde{p^{\prime}}\right)  \right)
<\operatorname{x}\left(  h_{M}\left(  \widetilde{p}\right)  \right)  $ but
$\operatorname{x}\left(  h_{M+1}\left(  \widetilde{p^{\prime}}\right)
\right)  \geq\operatorname{x}\left(  h_{M+1}\left(  \widetilde{p}\right)
\right)  $.
But the point $h_{M+1}\left(  \widetilde{p^{\prime}}\right)  $ is either the
eastern or the northern neighbor of $h_{M}\left(  \widetilde{p^{\prime}
}\right)  $; hence, $\operatorname{x}\left(  h_{M+1}\left(
\widetilde{p^{\prime}}\right)  \right)  \leq\operatorname{x}\left(
h_{M}\left(  \widetilde{p^{\prime}}\right)  \right)  +1$. Also, the point
$h_{M+1}\left(  \widetilde{p}\right)  $ is either the eastern or the northern
neighbor of $h_{M}\left(  \widetilde{p}\right)  $; thus, $\operatorname{x}
\left(  h_{M+1}\left(  \widetilde{p}\right)  \right)  \geq\operatorname{x}
\left(  h_{M}\left(  \widetilde{p}\right)  \right)  $. Hence,
\begin{align*}
\operatorname{x}\left(  h_{M+1}\left(  \widetilde{p^{\prime}}\right)
\right)  \leq\underbrace{\operatorname{x}\left(  h_{M}\left(
\widetilde{p^{\prime}}\right)  \right)  }_{<\operatorname{x}\left(
h_{M}\left(  \widetilde{p}\right)  \right)  }+1<\underbrace{\operatorname{x}
\left(  h_{M}\left(  \widetilde{p}\right)  \right)  }_{\leq\operatorname{x}
\left(  h_{M+1}\left(  \widetilde{p}\right)  \right)  }+1\leq\operatorname{x}
\left(  h_{M+1}\left(  \widetilde{p}\right)  \right)  +1.
\end{align*}
Therefore, $\operatorname{x}\left(  h_{M+1}\left(  \widetilde{p^{\prime}
}\right)  \right)  \leq\operatorname{x}\left(  h_{M+1}\left(  \widetilde{p}
\right)  \right)  $ (since both sides are integers). Combining this with
$\operatorname{x}\left(  h_{M+1}\left(  \widetilde{p^{\prime}}\right)
\right)  \geq\operatorname{x}\left(  h_{M+1}\left(  \widetilde{p}\right)
\right)  $, we obtain $\operatorname{x}\left(  h_{M+1}\left(
\widetilde{p^{\prime}}\right)  \right)  =\operatorname{x}\left(
h_{M+1}\left(  \widetilde{p}\right)  \right)  $. Hence, $h_{M+1}\left(
\widetilde{p^{\prime}}\right)  =h_{M+1}\left(  \widetilde{p}\right)  $ (since
$\operatorname{x}\left(  h_{M+1}\left(  \widetilde{p^{\prime}}\right)
\right)  -\operatorname{y}\left(  h_{M+1}\left(  \widetilde{p^{\prime}
}\right)  \right)  =M+1=\operatorname{x}\left(  h_{M+1}\left(  \widetilde{p}
\right)  \right)  -\operatorname{y}\left(  h_{M+1}\left(  \widetilde{p}
\right)  \right)  $ as well). Thus, the paths $\widetilde{p}$ and
$\widetilde{p^{\prime}}$ have a vertex in common (namely, $h_{M+1}\left(
\widetilde{p^{\prime}}\right)  =h_{M+1}\left(  \widetilde{p}\right)  $). This
contradicts the fact that they don't. This contradiction shows that
our assumption was false. Hence, the paths $p$ and $p^{\prime}$ have a vertex
in common. This proves Lemma 1 again.
Proof of Proposition 2
Proof of Proposition 2. Let $\sigma\in\mathfrak{S}_{k}$ be such that
$\sigma\neq\operatorname*{id}$. We shall show that $N\left(  \mathbf{u}
,\sigma\left(  \mathbf{v}\right)  \right)  =\varnothing$. Indeed, let
$\mathbf{p}\in N\left(  \mathbf{u},\sigma\left(  \mathbf{v}\right)  \right)  $.
The permutation $\sigma$ has at least one inversion (since $\sigma
\neq\operatorname*{id}$). In other words, there exist two elements $i$ and $j$
of $\left[  k\right]  $ such that $i<j$ and $\sigma\left(  i\right)
>\sigma\left(  j\right)  $. Consider such $i$ and $j$.
Write $\mathbf{p}$ in the form $\mathbf{p}=\left(  p_{1},p_{2},\ldots
,p_{k}\right)  $. Thus, $\left(  p_{1},p_{2},\ldots,p_{k}\right)  $ is a NILP
from $\mathbf{u}$ to $\sigma\left(  \mathbf{v}\right)  $ (since $\left(
p_{1},p_{2},\ldots,p_{k}\right)  =\mathbf{p}\in N\left(  \mathbf{u}
,\sigma\left(  \mathbf{v}\right)  \right)  $). In other words, $\left(  p_{1},p_{2},\ldots,p_{k}\right)  $ is a NILP from $\left(A_1, A_2, \ldots, A_k\right)$ to $\left(B_{\sigma\left(1\right)}, B_{\sigma\left(2\right)}, \ldots, B_{\sigma\left(k\right)}\right)$ (since $\mathbf{u} = \left(A_1, A_2, \ldots, A_k\right)$ and $\sigma\left(\mathbf{v}\right) = \sigma\left(B_1, B_2, \ldots, B_k\right) = \left(B_{\sigma\left(1\right)}, B_{\sigma\left(2\right)}, \ldots, B_{\sigma\left(k\right)}\right)$). By the definition of a NILP,
this implies that

*

*$p_{i}$ is a path from $A_{i}$ to $B_{\sigma\left(  i\right)  }$;


*$p_{j}$ is a path from $A_{j}$ to $B_{\sigma\left(  j\right)  }$;


*the paths $p_{i}$ and $p_{j}$ have no vertex in common (since $i\neq j$).
One of the assumptions of Proposition 2 was $\operatorname{x}\left(
A_{1}\right)  \geq\operatorname{x}\left(  A_{2}\right)  \geq\cdots
\geq\operatorname{x}\left(  A_{k}\right)  $; hence, $\operatorname{x}\left(
A_{i}\right)  \geq\operatorname{x}\left(  A_{j}\right)  $ (since $i<j$), and
thus $\operatorname{x}\left(  A_{j}\right)  \leq\operatorname{x}\left(
A_{i}\right)  $. Similarly, the second assumption of Proposition 2 yields $\operatorname{y}\left(  A_{j}\right)  \geq\operatorname{y}\left(
A_{i}\right)  $.
Also, the third assumption of Proposition 2 says $\operatorname{x}\left(  B_{1}\right)   \geq\operatorname{x}\left(
B_{2}\right)  \geq\cdots\geq\operatorname{x}\left(  B_{k}\right)$; hence,
$\operatorname{x}\left(  B_{\sigma\left(  j\right)
}\right)  \geq\operatorname{x}\left(  B_{\sigma\left(  i\right)  }\right)  $ (since $\sigma\left(  j\right)  <\sigma\left(  i\right)  $),
so that
$\operatorname{x}\left(  B_{\sigma\left(  i\right)
}\right)  \leq\operatorname{x}\left(  B_{\sigma\left(  j\right)  }\right)  $.
Similarly, the fourth assumption of Proposition 2 yields $\operatorname{y}\left(  B_{\sigma\left(  i\right)  }\right)
\geq\operatorname{y}\left(  B_{\sigma\left(  j\right)  }\right)  $. Hence,
Lemma 1 (applied to $A=A_{i}$, $B=B_{\sigma\left(  j\right)  }$, $A^{\prime
}=A_{j}$, $B^{\prime}=B_{\sigma\left(  i\right)  }$, $p=p_{i}$ and $p^{\prime
}=p_{j}$) shows that $p_{i}$ and $p_{j}$ have a vertex in common. This
contradicts the fact that the paths $p_{i}$ and $p_{j}$ have no vertex in common.
Now, forget that we fixed $\mathbf{p}$. Thus, we have found a contradiction
for each $\mathbf{p}\in N\left(  \mathbf{u},\sigma\left(  \mathbf{v}\right)
\right)  $. Hence, there exists no $\mathbf{p}\in N\left(  \mathbf{u}
,\sigma\left(  \mathbf{v}\right)  \right)  $. In other words, $N\left(
\mathbf{u},\sigma\left(  \mathbf{v}\right)  \right)  =\varnothing$.
Now, forget that we fixed $\sigma$. Thus, we have shown that every $\sigma
\in\mathfrak{S}_{k}$ satisfying $\sigma\neq\operatorname*{id}$ satisfies
$N\left(  \mathbf{u},\sigma\left(  \mathbf{v}\right)  \right)  =\varnothing$.
In other words, the pair $\left(  \mathbf{u},\mathbf{v}\right)  $ is
nonpermutable (by the definition of "nonpermutable"). This proves Proposition 2.
Proof of Corollary 4
We can finally derive Corollary 4 from Theorem 3:
Proof of Corollary 4. Proposition 2 shows that the pair $\left(
\mathbf{u},\mathbf{v}\right)  $ is nonpermutable. In other words, every
$\sigma\in\mathfrak{S}_{k}$ satisfying $\sigma\neq\operatorname*{id}$
satisfies $N\left(  \mathbf{u},\sigma\left(  \mathbf{v}\right)  \right)
=\varnothing$. Hence, every $\sigma\in\mathfrak{S}_{k}$ satisfying $\sigma
\neq\operatorname*{id}$ satisfies
\begin{align*}
\sum_{\mathbf{p}\in N\left(  \mathbf{u},\sigma\left(  \mathbf{v}\right)
\right)  }\omega\left(  \mathbf{p}\right)  =\sum_{\mathbf{p}\in\varnothing
}\omega\left(  \mathbf{p}\right)  =\left(  \text{empty sum}\right)  =0.
\label{1} \tag{1}
\end{align*}
But Theorem 3 yields
\begin{align*}
&  \det\left(  \left(  \sum_{p\in N\left(  A_{i},B_{j}\right)  }\omega\left(
p\right)  \right)  _{1\leq i\leq k,\ 1\leq j\leq k}\right)  \\
&  =\sum_{\sigma\in\mathfrak{S}_{k}}\left(  -1\right)  ^{\sigma}
\sum_{\mathbf{p}\in N\left(  \mathbf{u},\sigma\left(  \mathbf{v}\right)
\right)  }\omega\left(  \mathbf{p}\right)  \\
&  =\underbrace{\left(  -1\right)  ^{\operatorname*{id}}}_{=1}\underbrace{\sum
_{\mathbf{p}\in N\left(  \mathbf{u},\operatorname*{id}\left(  \mathbf{v}
\right)  \right)  }}_{\substack{=\sum_{\mathbf{p}\in N\left(  \mathbf{u}
,\mathbf{v}\right)  }\\\text{(since }\operatorname*{id}\left(  \mathbf{v}
\right)  =\mathbf{v}\text{)}}}\omega\left(  \mathbf{p}\right)  +\sum
_{\substack{\sigma\in\mathfrak{S}_{k};\\\sigma\neq\operatorname*{id}}}\left(
-1\right)  ^{\sigma}\underbrace{\sum_{\mathbf{p}\in N\left(  \mathbf{u}
,\sigma\left(  \mathbf{v}\right)  \right)  }\omega\left(  \mathbf{p}\right)
}_{\substack{=0\\\text{(by \eqref{1}, since }\sigma\neq\operatorname*{id}\text{)}}}\\
& \qquad \left( \text{here, we have split off the addend for } \sigma = \operatorname{id} \text{ from the sum }\right) \\
&  =\sum_{\mathbf{p}\in N\left(  \mathbf{u},\mathbf{v}\right)  }\omega\left(
\mathbf{p}\right)  +\underbrace{\sum_{\substack{\sigma\in\mathfrak{S}
_{k};\\\sigma\neq\operatorname*{id}}}\left(  -1\right)  ^{\sigma}0}_{=0}
=\sum_{\mathbf{p}\in N\left(  \mathbf{u},\mathbf{v}\right)  }\omega\left(
\mathbf{p}\right)  .
\end{align*}
This proves Corollary 4.
