\documentstyle[12pt,fullpage]{article} \begin{document} \centerline{\bf Noncommutative Lagrange Theorem and Inversion Polynomials} \vspace{.5in} \centerline{Igor Pak, Alexander Postnikov, Vladimir Retakh} \vspace{.75in} This is a part of a handwritten manuscript of the same authors. To read it is enough to be familiar with basic definitions, properties and notations of the theory of quasideterminants of noncommutative matrices. (See the paper by I.M. Gelfand and V.S. Retakh, ``A theory of noncommutative determinants and characteristic functions of graphs,'' Funct. Anal. Appl., 26 (1992), 1--20; Publ. LACIM. UQAM, Montreal. 14, 1--26; or \noindent D. Krob and B. Leclerc, ``Minor identities for quasideterminants and quantum determinants,'' preprint LITP 93.46 Paris, 1993; or I.M. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V.S. Retakh, J.-Y. Thibon, ``Noncommutative symmetric functions,'' DIMACS Technical Reports 94--28, 1994.) \pagebreak \vspace{-.5in} Chapter III. \vspace{.5in} \centerline{Noncommutative Lagrange Theorem} \vspace{.4in} \centerline{Section 3.1. \underline{Algebraic Proof}.} \vspace{.15in} \noindent 3.1.1. Let $a_0, a_1, a_2, \dots$ be non commuting formal variables and $R$ be a ring of formal series generated by these variables. \underline{Theorem 3.1.} A functional equation in $R$ \vspace{.1in} \hspace{2in}$f=a_0+a_1f+a_2f^2+a_3f^3+\cdots$ \hfill (3.1.1) \vspace{.1in} \noindent has a unique solution $f\in R$ and \begin{enumerate} \item[a)] $f=|A|_{11}^{-1}\, a_0$ \noindent where \hspace{1.5in} $ A=\pmatrix{ 1-a_1 & -a_2 & -a_3 & \ldots\cr -a_0 & 1-a_1 & -a_2 & \ldots\cr 0 & -a_0 & 1-a_1 & \ldots\cr 0 & 0 & -a_0 & \ldots\cr \vdots&\vdots&\vdots&\ddots} $ \hfill (3.1.2) \noindent is an infinite matrix and \item[b)] $f=P\cdot Q^{-1}$ \noindent where $$ P=a_0+\sum_{i_1+i_2+\cdots+i_{l+1}=l} a_{i_1} a_{i_2} \dots a_{i_{l+1}} $$ $$ Q=1+\sum_{i_1+i_2+\cdots+i_l=l} a_{i_1} a_{i_2} \dots a_{i_l} $$ Here $l\geq 1,\ i_k\geq 0,\ k=1, 2, 3, \dots$. \end{enumerate} \vspace{.15in} \noindent \underline{Proof}. Set $\deg(a_{i_1} \dots a_{i_l})=i_1+\cdots+i_l$. Let $$ f=f_0+f_1+f_2+\cdots $$ be an expansion $f$ into homogeneous components: $\deg f_i=i$. Then (3.1.1) gives us $$ f_0 = a_0,\quad f_1=a_1f_0, \quad f_2=a_1f_1+a_2f_0^2, $$ $$ f_3=a_1f_2+a_2(f_0f_1+f_1f_0)+a_3f_0^3, \dots $$ So, every $f_{i+1}$ can be written in a unique way via $f_0,\dots, f_i$. It follows that (3.1.1) has a unique solution. To prove a), we need the following: \vspace{.15in} \noindent \underline{Lemma 3.1.2}. Let $A$ be matrix (3.1.2). Then $$ |A|_{1j}=(|A|_{11} \cdot a_0^{-1})^{j}a_0. $$ \vspace{.15in} \noindent{\underline{Proof}}. From the ``homological relations'' for quasideterminants one has $$ |A|_{1j} \cdot |A^{11}|_{2j}^{-1} = -|A|_{11} \cdot |A^{1j}|_{21}^{-1}. $$ Note that $$ |A^{11}|_{2j} = |A|_{1j-1}, \quad |A^{1j}|_{21}=-a_0. $$ So $$ |A|_{1j}=|A|_{11}a_0^{-1} |A|_{1j-1}. $$ By induction we obtain $$ |A|_{1j}=(|A|_{11}a_0^{-1})^j a_0. $$ Let us prove that $f=|A|_{11}^{-1}\cdot a_0$ satisfies (3.1.1). By the definition of quasideterminant $$ |A|_{11}=1-a_1-a_2|A^{11}|_{22}^{-1} a_0 -a_3 |A^{11}|_{23}^{-1} a_0 - \dots . $$ So by Lemma 3.1.2 $$ |A|_{11}=1-a_1-a_2|A|_{11}^{-1}a_0-a_3(|A|_{11}^{-1}a_0)^2-\cdots $$ Multiplying by $f=|A|_{11}^{-1}a_0$ from the right we obtain $$ a_0=f-a_1f-a_2f^2-a_3f^3-\dots $$ and a) is proved. To prove b) we need the following useful \vspace{.15in} \noindent \underline{Proposition 3.1.3}. Let $B=(b_{ij}),\ \ 1\leq i,\ j\leq n.$ Let $E_n$ be the unit $n\times n$ matrix. Then $$ |E_n-B|_{ji}^{-1}=\delta_{ij}+\sum_{l\geq0}\, \sum_{1\leq k_1,\dots,k_l\leq n} b_{ik_1} b_{k_1k_2} \cdot \dots \cdot b_{k_lj}. $$ where $\delta_{ij}$ is the Kronecker delta. \vspace{.15in} \noindent \underline{Proof}. Use the expansion $$(E_n-B)_{ji}^{-1}=E_n+B+B^2+B^3+\cdots $$ Let us return to our proof. We will need one more \vspace{.15in} \noindent \underline{Lemma 3.1.4}. Let $$ C=\pmatrix{ X & Y\cr Z & T} $$ where $X, Y, Z, T$ are $k\times k,\ k \times n,\ n\times k$, and $n\times n$-matrices respectively. Suppose that $$ Z= \pmatrix{ 0&\ldots& 0 & -\alpha\cr 0&\ldots&0&0\cr \vdots&\ddots&\vdots&\vdots\cr 0&\ldots&0&0} $$ Then, $$ |T|_{11}^{-1}\alpha =|C|_{kk+1}^{-1} \cdot |C|_{kk}. $$ \vspace{.15in} \noindent \underline{Proof}. According to the ``homological relations'' $$ |C|_{k k+1} \cdot |C^{k\, k}|_{k+1\, k+1}^{-1}=-|C|_{k\, k} \cdot |C^{k\, k+1}|_{k+1\, k}^{-1}. $$ Note that $$ |C^{k\, k}|_{k+1\, k+1}=|T|_{11},\quad |C^{k\, k+1}|_{k+1\, k} =-\alpha. $$ So $$ |T|_{11}^{-1}\alpha =|C|_{k\, k+1}^{-1} \cdot |C|_{k\, k}. $$ Let us return to matrix (3.1.2) and let $A_{(n)}$ be its $n\times n$-submatrix $$ A_{(n)}=\pmatrix{ 1-a_1 & -a_2 & \ldots &-a_{n-1}& -a_n\cr -a_0 & 1-a_1 & \ldots& -a_{n-2}&-a_{n-1}\cr 0 & -a_0 & \ldots& -a_{n-3}&-a_{n-2}\cr \vdots&\vdots&\ddots&\vdots&\vdots\cr 0 & 0 & \ldots&-a_0 & 1-a_1} $$ It follows from Lemma 3.1.4 that $$ |A_{(n)}|_{11}^{-1} a_0 =|A_{(n+k)}|_{k\, k+1}^{-1} \cdot |A_{(n+K)}|_{k\, k}. $$ Set $$ P_{n,k}=|A_{(n+k)}|_{k\, k+1}^{-1};\quad Q= A_{(n,k)}|_{k\, k}^{-1}. $$ It is evident that $$ f=|A|_{11}^{-1} \cdot a_0 =\lim_{n\rightarrow \infty} |A_{(n)}|^{-1} a_0 =P_k \cdot Q_k^{-1} $$ where $$ P_k=\lim_{n\rightarrow\infty} P_{n,k} =|A|_{k\, k+1}^{-1},\quad Q_k=\lim_{n\rightarrow\infty} Q_{n,k} =|A|_{k\, k}^{-1}. $$ By Proposition 3.1.3 $$ P_k=a_0+\sum_{l>0}\, \sum_{i_1+i_2+\dots+i_{l+1}=l} a_{i_1} a_{i_2} \dots a_{i_{l+1}} $$ where the sum is taken over all sequences $(i_1, \dots, i_{l+1})$ of nonnegative integers such that for any $1\leq r\leq l+1$ $$ i_1+i_2+\dots +i_r -r \geq -k+1 $$ By the same proposition $$ Q_k=1+\sum_{l>0} \, \sum_{i_1+i_2+\dots+i_l=l} a_{i_1} a_{i_2} \dots a_{i_l} $$ where the sum is taken over all sets $(i_1, \dots, i_{l+1})$ of nonnegative integers, such that for any $1\leq r\leq l$ $$ i_1+i_2+\dots+i_r -r \geq -k+1. $$ As $k\rightarrow +\infty$ then $\ P_k\rightarrow P,\ Q_k\rightarrow Q$. Hence $f=PQ^{-1}$. The theorem is proven. \vspace{.2in} \noindent 3.1.2. \underline{$q$-Analog of Lagrange Theorem}. In this subsection we will obtain the Gessel's $q$-analog of commutative Lagrange Theorem. Let $\varphi = \varphi(z,q)$ be a function of two variables. Set $$ \varphi^{(n)} (z,q) =\varphi(zq^{n-1}, q) \varphi (zq^{n-2}, q) \cdot \dots \cdot \varphi(z,q), $$ $$ \varphi_{(n)} (z,q) =\varphi (z,q) \varphi (zq^{-1}, q) \cdot \dots \cdot \varphi(zq^{-n+1}, q) $$ \vspace{.15in} \noindent \underline{Theorem 3.1.5.} (cf. [Gessel]). Let $z$ be a formal variable and $q, g_0, g_1, g_2, \dots$ be formal parameters commuting with $z$ (they need not commute each other). Let $G$ be a ring of formal series generated by $g_i,\ i\geq 0$. Then a functional equation in $G$ \vspace{.1in} $ \displaystyle \hspace{.5in} F(z,q)=zq(g_0+g_1 F(z,q) +g_2F^{(2)} (z,q) + g_3 F^{(3)} (z,q) + \dots, $ \hfill (3.1.3) \vspace{.1in} \noindent has a unique solution $F(z,q)$ and \begin{enumerate} \item[a)] $F(z,q)=|\widetilde{A}|_{11}^{-1}$, where $$ \widetilde{A}=\pmatrix{ 1-g_1qz & -g_2q^3z^2 & -g_3q^6z^3 & \ldots & -g_nq^{{n+1} \choose {2}} z^n& \ldots\cr -g_0 & 1-g_1q^2z & -g_2q^5z^2 & \ldots & -g_{n-1}q^{{n \choose 2} +n-1} z^{n-1}&\ldots\cr 0 & -g_0 & 1-g_1q^3z & \ldots & -g_{n-2} q^{{{n-1}\choose{2}} +2(n-2)} z^{n-2}&\ldots\cr 0 & 0 & -g_0 & \ldots& -g_{n-3}q^{{{n-2}\choose{2}}+3(n-3)}z^{n-3} & \ldots\cr \vdots & \vdots& \vdots& \ddots& \ddots&\ddots} $$ \item[b)] $$ F(z,q)=\frac{\displaystyle z\cdot \sum_{n\geq0} q^{{n+2}\choose{z}} z^n \cdot \left[t^n\right] g_{(n+1)} \left(q^{-1}t, q\right)} {\displaystyle \sum_{n\geq0} q^{{n+1}\choose 2} z^n \cdot \left[ t^n\right] g_{(n)} \left(q^{-1}t, q\right)} $$ where $$ g(\xi,q)=g_0+g_1\xi + g_2\xi^2 + \dots $$ and $$ \left[t^n\right] \cdot \left(\sum_{n\geq 0} \varphi_n t^n\right):=\varphi_n. $$ \end{enumerate} \vspace{.15in} \noindent \underline{Proof}. We show that Theorem 3.1.5 follows from noncommutative Lagrange Theorem 3.1.1. Let $x,y$ be $q$-commuting variables, i.e. $xy=qyx$. Set $z=yx$. In the notations of Theorem 3.1.1 we set $$ a_i=g_ix^iy,\quad i=0, 1, 2, \dots $$ and suppose that $g_i$ commute with $x$ and $y$. Let $F=f\cdot xq$. Note that $F$ is a function of $z$ and $q$. It follows from the representation of $f$ as $PQ^{-1}$ and the formulas for the formal series $P$ and $Q$. From the obvious identity $$ x\varphi(z,q)=\varphi(zq,q)x $$ it follows that $$ f^n=\left(F\cdot (xq)^{-1}\right)^{n}=(xq)^{-n+1} F^{(n)} (xq)^{-1} $$ Let us set $f=F\cdot(xq)^{-1}$ and $a_i=q_ix^ly$ in functional equation (3.1.1): $$ F\cdot (xq)^{-1}=g_0y+g_1 xy F\cdot (xq)^{-1} +g_2x^2 y\left( F\cdot (xq^{-1})\right)^2 +\dots $$ So $$ F=qz(g_0+g_1F+g_2F^{(2)}+\dots) $$ and we get formula (3.1.3). Let us prove a). By Theorem 3.1.1 $F=fxq=|A|_{11}^{-1} g_0 yxq=|A|_{11}^{-1} g_0zq$, where the matrix $A$ is as follows: $$ A=\pmatrix{ 1-g_1xy & -g_2x^2y & -g_3x^3y & \ldots\cr -g_0y & 1-g_1xy & -g_2x^2y & \ldots\cr 0 & -g_0y & 1-g_1xy & \ldots\cr 0 & 0 & -g_0 & \ldots\cr \vdots&\vdots&\vdots&\ddots} $$ Multiply $j$-th column in $A$ by $y^{j-1}$ from the right and $i$-th row in $A$ by $y^{1-i}$ from the left for all $i,j\ge 2$. We get the matrix $\widetilde{A}$. Note that $|A|_{11}=|\widetilde{A}|_{11}$. Hence $F=|{\ddot{\widetilde{A}}}|_{11}^{-1} g_0 zq$ and a) is proven. Now prove b). By Theorem~3.1.1 we have $$ F=fxq=P\cdot Q^{-1} xq, $$ where $$ \begin{array}{rcl} P&=&{\displaystyle a_0+\sum_{l\geq1}\, \sum_{i_1+i_2+\dots+ i_{l+1}=l} a_{i_1}a_{i_2} \dots a_{i_{l+1}}=}\\ &=&{\displaystyle g_0y+\sum_{l\geq1}\, \sum_{i_1+i_2+\dots+ i_{l+1}=l} (g_{i_1}x^{i_1}y) \dots (g_{i_{l+1}} x^{i_{l+1}} y)=}\\ &=&{\displaystyle g_0y+\sum_{l\geq1}\, \sum_{i_1+i_2+ \dots+i_{l+1}=l} x^ly^{l+1}q^{-(i_2+2i_3+\dots+li_{l+1})} g_{i_1}g_{i_2}\dots g_{i_{l+1}}=}\\ &=&{\displaystyle \left\{ qg_0z+\sum_{l\geq1}\, \sum_{i_1+i_2+\dots+i_{l+1}=l} x^{l+1} y^{l+1} q^{-(i_1+2i_2+\dots+(l+1)i_{l+1})} \cdot g_{i_1} g_{i_2} \dots g_{i_{l+1}} \right\} (qx)^{-1}=}\\ &=&{\displaystyle \left\{qg_0z+\sum_{l\geq1}\, \sum_{i_1+i_2+\dots+i_{l+1}=l} (yx)^{l+1} q^{{l+2}\choose 2} q^{-i_1} g_{i_1} \cdot q^{-2i_2} g_{i_2} \dots q^{-(l+1)i_{l+1}} g_{i_{l+1}} \right\}(qx)^{-1}=}\\ &=&{\displaystyle z \cdot \left\{\sum_{l\geq1} z^l q^{{l+2}\choose2} \left[ t^l\right] g_{(l+1)} (y^{-1}t, q) \right\} (qx)^{-1}} \end{array} $$ and $$ \begin{array}{rcl} Q&=&{\displaystyle 1+\sum_{l\geq1} \sum_{i_1+i_2+\dots+i_l=l} a_{i_1} a_{i_2} \cdots a_{i_l}=}\\ &=&{\displaystyle 1+\sum_{l\geq1} \sum_{i_1+i_2+\dots+i_l=l} (g_{i_1}x^{i_1}y)\cdots (g_{i_l}x^{i_l}y)=}\\ &=&{\displaystyle 1+\sum_{l\geq1} \sum_{i_1+i_2+\dots+i_l=l} x^ly^lg^{-(i_2+2i_3+\cdots+(l-1)i_l)}\cdot g_{i_1}g_{i_2}\dots g_{i_l}=}\\ &=&{\displaystyle x\left\{ 1+\sum_{l\geq1} \sum_{i_1+i_2+\dots+i_l=l} x^ly^lg^{-(i_2+2i_3+\cdots+(l-1)i_l)}\cdot g_{i_1}g_{i_2} \dots g_{i_l} \right\} x^{-1}=}\\ &=&{\displaystyle x\left\{ 1+\sum_{l\geq1} \sum_{i_1+i_2+\dots+i_l=l} z^lq^{{l+1}\choose 2} q^{-i_1}g_{i_1} q^{-i_2}g_{i_2}\dots q^{-li_l}g_{i_l} \right\}x^{-1}=}\\ &=&{\displaystyle x\left\{\sum_{l\geq0} z^lq^{{l+1}\choose 2}\left[t^l\right]g_{(l)} (q^{-1}t, q)\right\}x^{-1}.} \end{array} $$ We get the following Gessel's formula for $F=PQ^{-1}\cdot xq$. $$ F=\frac{\displaystyle z\sum_{l\geq0} q^{{l+2}\choose 2} z^l\left[t^l\right] g_{(l+1)}(q^{-1}z, q)} {\displaystyle \sum_{l\geq0} q^{{l+1}\choose 2} z^l\left[t^l\right] g_{(l)} (q^{-1}z, q)}. $$ \vspace{0.4in} \vbox{\hbox to\hsize{\hfil Section 3.2. \underline{Combinatorial Proof of Noncommutative}\hfil} \hbox to\hsize{\hfil\underline{Lagrange Theorem} (following [Gessel])\hfil}} \vspace{.15in} \noindent 3.2.1. Let $S=\{ b_{-1}, b_0, b_1, \dots, b_u, \dots \}$ and let $S^*$ be the free monoid generated by $b_i\in S$. For any word $w=b_{i_1} b_{i_2} \dots b_{i_l}$ in $S^*$ define its height $\upsilon(w)=i_1+i_2+\dots+i_l$. Then $\upsilon: S^*\rightarrow {\bf Z}_+$ will be a semi-group homomorphism. A word $v\in S^*$ is called a left factor of $w$ if $w=v\cdot u$ for some $u\in S^*$. Consider $$ R=\left\{w\in S^*\mid \upsilon(w)=0 {\rm\ and\ }\upsilon(v)\geq 0 {\rm\ for\ every\ left\ factor\ } v {\rm\ of\ }w\right\}. $$ Then $R$ is a submonoid in $S^*$. Set $F=Rb_{-1}$. \vspace{.15in} \noindent \underline{Proposition 3.2.1.} Let $w$ be a word $w\in F$. Suppose that $w$ starts with $b_{j-1}$, $j\le 0$. Then the word $w$ can be uniquely decomposed as $w=b_{j-1}w_1\dots w_j$, where $w_i\in F$ for $i=1, \dots, j$. Hence $$ F=\coprod_{j=0}^\infty b_{j-1} F^j $$ Let $G_k=\{w\in S^*, \upsilon(w)=k\},\ k\in {\bf Z}$. \vspace{.15in} \noindent\underline{Proposition 3.2.2.} Any $w\in G_k$ has a unique decomposition $w=uv$, where $u\in F,\ v\in G_{k+1}$. Let us show that both these propositions imply Lagrange Theorem. Set $$ (missing\ equation?) $$ where the sum is considered in the semi-group ring of monoid $S^*$. From Proposition 3.2.1 it follows that \vspace{.1in} \hspace{2in} $\displaystyle f=\sum_{j=0}^{\infty} b_{j-1} f^j $ \hfill (3.2.1) \vspace{.1in} \noindent and Proposition 3.2.2 implies \vspace{.1in} \hspace{1.75in} $\displaystyle f\cdot g_{k+1}=g_k,\ k\in {\bf Z}$. \hfill (3.2.2) \vspace{.1in} Consider the following almost upper triangular infinite matrix \vspace{.6in} \hfill (3.2.3) \vspace{-.75in} $$ B=\pmatrix{ b_0 & b_1 & b_2 & \ldots\cr b_{-1} & b_{0} & b_1 & \ldots\cr 0 & b_{-1} & b_0 & \ldots\cr 0 & 0 & b_{-1} & \ldots\cr \vdots & \vdots & \vdots & \ddots} $$ Then \vspace{.1in} \hspace{.5in} $\displaystyle |E-B|_{11}\cdot b_{-1}=\sum_{i=0}^{\infty}|B^i|_{11}\cdot b_{-1} = \left( \sum_{w\in R}w\right) b_{-1}=f$ \hfill (3.2.4) \vspace{.1in} \noindent Here $E$ is an infinite unite matrix. Setting $a_j=b_{j+1},\ j=0,1,2,\dots$ and combining (3.2.1) and (3.2.4) we get Theorem 3.1.1.a). It is easy to see that for $a_j=b_{j+1}$ we have $g_0=Q,\ g_1=P$ in notations of Theorem 3.1.1. It proves b) by (3.2.2). Moreover (3.2.2) gives a generalization of Theorem~3.1.1.b). \vspace{.15in} \noindent \underline{Proof of Proposition 3.2.1}. Let us fix a word $w=a_{i_1}a_{i_2} \dots a_{i_l}\in F$. Set $j=i_1+1$. Consider all left factors $w_m=a_{i_1}a_{i_2}\dots a_{i_m},\ 1\leq m\leq l$ of the word $w$. Then $v(w_1)=v(a_{i_1})=i_1,\ v(w_l)=-1$. Consider the set of indices $2\leq m_1, \dots, m_j\leq m$ such that $\upsilon(w_{m_k}=i_1-k,\ 1\leq k\leq j$ and $\upsilon(w_r)>\upsilon(w_{m_k}),\ 1\leq r\leq m_k$. It is easy to see that this set is correctly defined.. Let $w_{m_k}=w_{m_{k-1}} \cdot u_k,\ 1\leq k\leq j$. By definition, $u_k \in F_k$ for $1\leq k\leq j$. Then $w=a_{j-1} u_1 u_2 \dots u_j$ is the decomposition we need. Its uniqueness follows directly from the uniqueness of the set $(m_k),\ 1\leq k\leq j$. \vspace{.15in} \noindent \underline{Proof of Proposition 3.2.2}. Let us fix a word $w=a_{i_1}a_{i_2}\dots a_{i_k}\in G_k$ and consider its left factors $w_m=a_{i_1}a_{i_2}\cdot \dots \cdot a_{i_m},\ 0\leq m\leq l$. Then $\upsilon(w_0)=0,\ \upsilon(w_l)=\upsilon(w)=k<0$. Then there exists a unique $r,\ 1\leq r\leq 1$ such that $\upsilon(w_r)=-1,\ \upsilon(w_s)\geq 0,\ 0\leq s