Лемма Линдстрема – Гесселя – Венно. - Lindström–Gessel–Viennot lemma

В математике Лемма Линдстрема – Гесселя – Венно. обеспечивает способ подсчета количества кортежей непересекающихся решетчатые дорожки. Это было доказано Гесселем-Вьеннотом в 1985 году на основе предыдущей работы Линдстрема, опубликованной в 1973 году.

Заявление

Позволять грамм - локально конечный ориентированный ациклический график. Это означает, что каждая вершина имеет конечные степень, и это грамм не содержит направленных циклов. Рассмотрим базовые вершины ${\displaystyle A=\{a_{1},\ldots ,a_{n}\}}$ и конечные вершины ${\displaystyle B=\{b_{1},\ldots ,b_{n}\}}$, а также присвоить вес ${\displaystyle \omega _{e}}$ к каждому направленному краю е. Предполагается, что эти веса ребер принадлежат некоторым коммутативное кольцо. Для каждого направленного пути п между двумя вершинами, пусть ${\displaystyle \omega (P)}$ быть произведением весов ребер пути. Для любых двух вершин а и б, записывать е(а,б) на сумму ${\displaystyle e(a,b)=\sum _{P:a\to b}\omega (P)}$ по всем путям от а к б. Это хорошо определено, если между любыми двумя точками есть только конечное число путей; но даже в общем случае это может быть четко определено при некоторых обстоятельствах (например, все веса ребер являются попарно различными формальными неопределенными величинами, и ${\displaystyle e(a,b)}$ рассматривается как формальный степенной ряд). Если присвоить каждому ребру вес 1, то е(а,б) подсчитывает количество путей от а к б.

С этой настройкой напишите

${\displaystyle M={\begin{pmatrix}e(a_{1},b_{1})&e(a_{1},b_{2})&\cdots &e(a_{1},b_{n})\\e(a_{2},b_{1})&e(a_{2},b_{2})&\cdots &e(a_{2},b_{n})\\\vdots &\vdots &\ddots &\vdots \\e(a_{n},b_{1})&e(a_{n},b_{2})&\cdots &e(a_{n},b_{n})\end{pmatrix}}}$.

An п-набор непересекающихся путей из А к B означает п-температура (п₁, ..., п_п) путей в грамм со следующими свойствами:

• Существует перестановка ${\displaystyle \sigma }$ из ${\displaystyle \left\{1,2,...,n\right\}}$ так что для каждого я, тропинка п_я это путь от ${\displaystyle a_{i}}$ к ${\displaystyle b_{\sigma (i)}}$.
• В любое время ${\displaystyle i\neq j}$, пути п_я и п_j не имеют двух общих вершин (даже конечных точек).

Учитывая такой п-температура (п₁, ..., п_п), обозначим через ${\displaystyle \sigma (P)}$ перестановка ${\displaystyle \sigma }$ из первого условия.

В Лемма Линдстрема – Гесселя – Венно. затем заявляет, что определитель M подписанная сумма по всем п- пары п = (п₁, ..., п_п) из непересекающийся пути от А к B:

${\displaystyle \det(M)=\sum _{(P_{1},\ldots ,P_{n})\colon A\to B}\mathrm {sign} (\sigma (P))\prod _{i=1}^{n}\omega (P_{i}).}$

То есть определитель M считает веса всех п-наборы непересекающихся путей, начинающиеся в А и заканчивая B, каждая из которых имеет знак соответствующей перестановки ${\displaystyle (1,2,\ldots ,n)}$, данный ${\displaystyle P_{i}}$ принимая ${\displaystyle a_{i}}$ к ${\displaystyle b_{\sigma (i)}}$.

В частности, если единственная возможная перестановка - это тождество (т.е. каждый п-набор непересекающихся путей из А к B берет а_я к б_я для каждого я) и мы берем веса равными 1, тогда det (M) - это в точности количество непересекающихся п-наборы путей, начинающиеся с А и заканчивая B.

Доказательство

Чтобы доказать лемму Линдстрема – Гесселя – Виенно, сначала введем некоторые обозначения.

An п-дорожка из ппара ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ вершин грамм для ппара ${\displaystyle (b_{1},b_{2},\ldots ,b_{n})}$ вершин грамм будет означать ппара ${\displaystyle (P_{1},P_{2},\ldots ,P_{n})}$ путей в грамм, с каждым ${\displaystyle P_{i}}$ ведущий из ${\displaystyle a_{i}}$ к ${\displaystyle b_{i}}$. Этот п-path будет называться непересекающийся на всякий случай пути п_я и п_j не имеет двух общих вершин (включая конечные точки) всякий раз, когда ${\displaystyle i\neq j}$. В противном случае он будет называться запутанный.

Учитывая п-дорожка ${\displaystyle P=(P_{1},P_{2},\ldots ,P_{n})}$, то масса ${\displaystyle \omega (P)}$ этого п-path определяется как продукт ${\displaystyle \omega (P_{1})\omega (P_{2})\cdots \omega (P_{n})}$.

А скрученный п-дорожка из ппара ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ вершин грамм для ппара ${\displaystyle (b_{1},b_{2},\ldots ,b_{n})}$ вершин грамм будет означать п-путь от ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ к ${\displaystyle \left(b_{\sigma (1)},b_{\sigma (2)},\ldots ,b_{\sigma (n)}\right)}$ для некоторой перестановки ${\displaystyle \sigma }$ в симметричная группа ${\displaystyle S_{n}}$. Эта перестановка ${\displaystyle \sigma }$ будет называться крутить этого скрученного п-путь, и обозначается ${\displaystyle \sigma (P)}$ (куда п это п-дорожка). Это, конечно, обобщает обозначения ${\displaystyle \sigma (P)}$ введен ранее.

Напоминая определение M, мы можем расширить det M в виде подписанной суммы перестановок; таким образом, мы получаем

${\displaystyle {\begin{array}{rcl}\det M&=&\sum _{\sigma \in S_{n}}\mathrm {sign} (\sigma )\prod _{i=1}^{n}e(a_{i},b_{\sigma (i)})\\&=&\sum _{\sigma \in S_{n}}\mathrm {sign} (\sigma )\prod _{i=1}^{n}\sum _{P_{i}:a_{i}\to b_{\sigma (i)}}\omega (P_{i})\\&=&\sum _{\sigma \in S_{n}}\mathrm {sign} (\sigma )\sum \{\omega (P):P~{\text{an}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{\sigma (1)},b_{\sigma (2)},\ldots ,b_{\sigma (n)}\right)\}\\&=&\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{a twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&=&\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{a non-intersecting twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&&+\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{an entangled twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&=&\sum _{(P_{1},\ldots ,P_{n})\colon A\to B}\mathrm {sign} (\sigma (P))\omega (P)\\&&+\underbrace {\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{an entangled twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{1},b_{2},...,b_{n}\right)\}} _{=0?}\\\end{array}}}$

Это остается показывать что сумма ${\displaystyle \mathrm {sign} (\sigma (P))\omega (P)}$ над всем запутанным скрученным п-путь пропадает. Позволять ${\displaystyle {\mathcal {E}}}$ обозначим множество запутанных скрученных п-путь. Чтобы установить это, построим инволюция${\displaystyle f:{\mathcal {E}}\longrightarrow {\mathcal {E}}}$ со свойствами ${\displaystyle \omega (f(P))=\omega (P)}$ и ${\displaystyle \mathrm {sign} (\sigma (f(P)))=-\mathrm {sign} (\sigma (P))}$ для всех ${\displaystyle P\in {\mathcal {E}}}$. При такой инволюции остаточный член в приведенной выше сумме сводится к

${\displaystyle {\begin{array}{rcl}\sum _{P\in {\mathcal {E}}}\mathrm {sign} (\sigma (P))\omega (P)&=&{\frac {1}{2}}\left(\sum _{P\in {\mathcal {E}}}\mathrm {sign} (\sigma (P))\omega (P)+\sum _{P\in {\mathcal {E}}}\mathrm {sign} (\sigma (f(P)))\omega (f(P))\right)\\&=&{\frac {1}{2}}\left(\sum _{P\in {\mathcal {E}}}\mathrm {sign} (\sigma (P))\omega (P)+\sum _{P\in {\mathcal {E}}}-\mathrm {sign} (\sigma (P))\omega (P)\right)\\&=&0\\\end{array}}}$

Построение инволюции: идея определения инволюции ${\displaystyle f}$ состоит в том, чтобы выбрать два пересекающихся пути внутри запутанного пути и поменять их хвостами после точки пересечения. Обычно существует несколько пар пересекающихся путей, которые также могут пересекаться несколько раз; следовательно, необходимо сделать осторожный выбор. Позволять ${\displaystyle P=\left(P_{1},P_{2},...,P_{n}\right)}$ быть запутанным скрученным п-дорожка. потом ${\displaystyle f(P)}$ определяется следующим образом. С ${\displaystyle P}$ запутано, существует минимальная ${\displaystyle i<j}$ в ${\displaystyle \{1,2,\ldots ,n\}}$ такой, что ${\displaystyle P_{i}}$ и ${\displaystyle P_{j}}$ имеют общую вершину. выбирать ${\displaystyle i_{P}<j_{P}}$ быть наименьшим из таких показателей. Общая вершина не обязательно является конечной точкой этих путей. Обобщая эту информацию, мы имеем

${\displaystyle {\begin{array}{rcl}P_{i}&\equiv &a_{i}=u_{0}\to u_{1}\to u_{2}\ldots u_{\alpha -1}\to \overbrace {\mathbf {u} _{\alpha }\to u_{\alpha +1}\ldots \to u_{r}=b_{\sigma (i)}} ^{\mathrm {tail} ~i}\\P_{j}&\equiv &a_{j}=v_{0}\to v_{1}\to v_{2}\ldots v_{\beta -1}\to \underbrace {\mathbf {v} _{\beta }\to v_{\beta +1}\ldots \to v_{s}=b_{\sigma (j)}} _{\mathrm {tail} ~j}\\\end{array}}}$

куда ${\displaystyle i=i_{P}}$, ${\displaystyle j=j_{P}}$, ${\displaystyle \sigma =\sigma (P)}$ и ${\displaystyle \alpha }$-я вершина вдоль ${\displaystyle P_{i}}$ совпадает с ${\displaystyle \beta }$-я вершина вдоль ${\displaystyle P_{i}}$. выбирать ${\displaystyle \alpha _{P},\beta _{P}}$ быть минимально возможными такими позициями, конкретно ${\displaystyle \alpha _{P}:=\min\{\alpha \mid \exists {\beta :~}u_{\alpha }=v_{\beta }\}}$ и ${\displaystyle \beta _{P}:=\min\{\beta \mid u_{\alpha _{P}}=v_{\beta }\}}$. Теперь установите ${\displaystyle f(P)}$ совпадать с ${\displaystyle P}$ кроме компонентов ${\displaystyle i}$ и ${\displaystyle j}$, которые заменяются на

${\displaystyle {\begin{array}{rcl}P'_{i}&\equiv &a_{i}=u_{0}\to u_{1}\to u_{2}\ldots u_{\alpha -1}\to \overbrace {v_{\beta _{P}}\to v_{\beta _{P}+1}\ldots \to v_{s}=b_{\sigma (j)}} ^{\mathrm {tail} ~j}\\P'_{j}&\equiv &a_{j}=v_{0}\to v_{1}\to v_{2}\ldots v_{\beta -1}\to \underbrace {u_{\alpha _{P}}\to u_{\alpha _{P}+1}\ldots \to u_{r}=b_{\sigma (i)}} _{\mathrm {tail} ~i}\\\end{array}}}$

Сразу видно, что ${\displaystyle f(P)}$ это запутанный скрученный п-дорожка. Пройдя по этапам построения, легко увидеть, что ${\displaystyle i_{f(P)}=i_{P}}$, ${\displaystyle j_{f(P)}=j_{P}}$ и, кроме того, что ${\displaystyle \alpha _{f(P)}=\alpha _{P}}$ и ${\displaystyle \beta _{f(P)}=\beta _{P}}$, так что применяя ${\displaystyle f}$ снова к ${\displaystyle f(P)}$ включает в себя замену хвостов ${\displaystyle f(P)_{i},f(P)_{j}}$ и оставив остальные компоненты нетронутыми. Следовательно ${\displaystyle f(f(P))=P}$. Таким образом ${\displaystyle f}$ инволюция. Осталось продемонстрировать желаемые свойства антисимметрии:

Из конструкции видно, что ${\displaystyle \sigma (f(P))}$ совпадает с ${\displaystyle \sigma =\sigma (P)}$ за исключением того, что он меняет местами ${\displaystyle \sigma (i)}$ и ${\displaystyle \sigma (j)}$, давая ${\displaystyle \sigma (f(P))=-\sigma (P)}$. Чтобы показать это ${\displaystyle \omega (f(P))=\omega (P)}$ мы сначала вычисляем, обращаясь к замене хвоста

${\displaystyle {\begin{array}{rcl}\omega (P'_{i})\omega (P'_{j})&=&\left(\prod _{t=0}^{\alpha -1}\omega (u_{t},u_{t+1})\cdot \prod _{t=\beta }^{s-1}\omega (v_{t},v_{t+1})\right)\cdot \left(\prod _{t=0}^{\beta -1}\omega (v_{t},v_{t+1})\cdot \prod _{t=\alpha }^{r-1}\omega (u_{t},u_{t+1})\right)\\&=&\prod _{t=0}^{r-1}\omega (u_{t},u_{t+1})\cdot \prod _{t=0}^{s-1}\omega (v_{t},v_{t+1})\\&=&\omega (P_{i})\omega (P_{j}).\\\end{array}}}$

Следовательно ${\displaystyle \omega (f(P))=\prod _{k=1}^{n}\omega (f(P)_{k})=\prod _{k=1,~k\neq i,j}^{n}\omega (P_{k})\cdot \omega (P'_{i})\omega (P'_{j})=\prod _{k=1,~k\neq i,j}^{n}\omega (P_{k})\cdot \omega (P_{i})\omega (P_{j})=\prod _{k=1}^{n}\omega (P_{k})=\omega (P)}$.

Таким образом, мы нашли инволюцию с желаемыми свойствами и завершили доказательство леммы Линдстрема-Гесселя-Венно.

Замечание. Аргументы, аналогичные приведенному выше, появляются в нескольких источниках с вариациями относительно выбора того, какой хвост переключать. Версия с j наименьший (не равно я), а не наибольшее, появляется в ссылке Gessel-Viennot 1989 (доказательство теоремы 1).

Приложения

Полиномы Шура

Лемма Линдстрема – Гесселя – Венно может быть использована для доказательства эквивалентности следующих двух различных определений Полиномы Шура. Учитывая раздел ${\displaystyle \lambda =\lambda _{1}+\cdots +\lambda _{r}}$ из п, многочлен Шура ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{n})}$ можно определить как:

• ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{n})=\sum _{T}w(T),}$

где сумма берется по всем полустандартным таблицам Юнга Т формы λ, а вес таблицы Т определяется как моном, полученный произведением Икс_я индексируется записями я из Т. Например, вес таблицыявляется ${\displaystyle x_{1}x_{3}x_{4}^{3}x_{5}x_{6}x_{7}}$.

• ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{n})=\det \left((h_{\lambda _{i}+j-i})_{i,j}^{r\times r}\right),}$

куда час_я являются полные однородные симметрические многочлены (с час_я понимается как 0, если я отрицательный). Например, для разбиения (3,2,2,1) соответствующий определитель равен

${\displaystyle s_{(3,2,2,1)}={\begin{vmatrix}h_{3}&h_{4}&h_{5}&h_{6}\\h_{1}&h_{2}&h_{3}&h_{4}\\1&h_{1}&h_{2}&h_{3}\\0&0&1&h_{1}\end{vmatrix}}.}$

Чтобы доказать эквивалентность, для любого разбиения λ как и выше, считается р отправные точки ${\displaystyle a_{i}=(r+1-i,1)}$ и р конечные точки ${\displaystyle b_{i}=(\lambda _{i}+r+1-i,n)}$, как точки решетки ${\displaystyle \mathbb {Z} ^{2}}$, который приобретает структуру ориентированного графа, утверждая, что единственные разрешенные направления идут один вправо или один вверх; вес, связанный с любым горизонтальным краем на высоте я является Икс_я, а вес, связанный с вертикальным ребром, равен 1. С этим определением р-наборы путей из А к B в точности полустандартные таблицы Юнга формы λ, а вес такого р-набор - соответствующее слагаемое в первом определении полиномов Шура. Например, с таблицей, получаем соответствующий 4пара

С другой стороны, матрица M это в точности матрица, написанная выше для D. Это показывает требуемую эквивалентность. (См. Также §4.5 в книге Сагана, или Первое доказательство теоремы 7.16.1 в EC2 Стэнли, или §3.3 в препринте Фулмека arXiv, или §9.13 в лекционных заметках Мартина, для небольших вариаций этого аргумента.)

Формула Коши – Бине

Можно также использовать лемму Линдстрема – Гесселя – Венно для доказательства Формула Коши – Бине, и в частности мультипликативность определителя.

Обобщения

Формула Таласки

Ацикличность грамм является существенным условием леммы Линдстрема – Гесселя – Виенно; он гарантирует (в разумных ситуациях), что суммы ${\displaystyle e(a,b)}$ определены корректно и переходят в доказательство (если грамм не ациклично, то ж может превратить самопересечение пути в пересечение двух различных путей, что нарушает аргумент, что ж инволюция). Тем не менее, статья Келли Таласка 2012 года устанавливает формулу, обобщающую лемму на произвольные орграфы. Суммы ${\displaystyle e(a,b)}$ заменяются формальными степенными рядами, и сумма по непересекающимся кортежам путей теперь становится суммой по совокупностям непересекающихся и несамопересекающихся путей и циклов, деленной на сумму по совокупности непересекающихся циклов. За подробностями отсылаем читателя к статье Таласки.

Смотрите также

• Теорема о матричном дереве

Рекомендации

• Гессель, Ира М.; Вьеннот, Ксавье Г. (1989), Детерминанты, пути и плоские разделы (PDF)
• Саган, Брюс Э. (2001), Симметричная группа, Springer
• Стэнли, Ричард П. (1999), Перечислительная комбинаторика, том 2, ЧАШКА
• Таласка, Келли (2012), Определители взвешенных матриц путей, arXiv:1202.3128v1
• Мартин, Джереми (2012), Конспект лекций по алгебраической комбинаторике (PDF)
• Фулмек, Маркус (2010), Рассмотрение определителей как непересекающихся решетчатых путей дает биективно классические детерминантные тождества., arXiv:1010.3860v1