The standard basis of the generic type-A Hecke algebra

Inversion length. Write $w=(a_1,\dots ,a_n)$ in one-line notation. Right multiplication by $s_i$ swaps the adjacent entries $a_i,a_{i+1}$. Every inversion involving a position outside $i,i+1$ has the same total contribution before and after this swap; only the pair $(i,i+1)$ changes. Thus $\mathrm{\ell }(w{s}_i)=\mathrm{\ell }(w)+1$ when $a_i<a_{i+1}$ and $\mathrm{\ell }(w{s}_i)=\mathrm{\ell }(w)-1$ when $a_i>a_{i+1}$. Each adjacent transposition changes inversion count by one, so every word for $w$ has length at least $\mathrm{\ell }(w)$. Conversely, a nonidentity permutation has an adjacent descent, since an increasing one-line permutation is the identity. Repeatedly swapping an adjacent descent decreases the inversion count by one until the identity is reached; reversing these swaps writes $w$ as a word of length $\mathrm{\ell }(w)$. Therefore inversion length is minimal word length. Every prefix of a reduced word is reduced, and each successive letter raises length by one.

Connectivity of reduced words. We prove by induction on $r=\mathrm{\ell }(w)$ that any two reduced words for $w$ are related by commuting moves and the adjacent braid moves. The assertion is immediate for $r=0$. For two reduced words with the same last letter $s_i$, remove it and apply induction to the reduced prefixes for $w{s}_i$. Otherwise their last letters $s_i,s_j$ are distinct right descents of $w$. If $\mathrm{\mid }i-j\mathrm{\mid }>1$, the descents occupy disjoint positions and remain descents after applying the other transposition. The common permutation $u:=w{s}_i{s}_j=w{s}_j{s}_i$ has length $r-2$. Choose a reduced word $p$ for $u$. Then $p{s}_j$ and $p{s}_i$ are reduced words for $w{s}_i$ and $w{s}_j$. By induction the prefixes of the original words connect to these, and appending their final letters reduces the comparison to $p{s}_j{s}_i$ versus $p{s}_i{s}_j$, which differ by a commutation. If $j=i+1$ (the case $i=j+1$ is symmetric), the entries of $w$ in positions $i,i+1,i+2$ are strictly decreasing. The common permutation $u:=w{s}_i{s}_j{s}_i=w{s}_j{s}_i{s}_j$ has length $r-3$. For a reduced word $p$ of $u$, $p{s}_i{s}_j$ and $p{s}_j{s}_i$ are reduced words for $w{s}_i$ and $w{s}_j$. Induction on their prefixes, followed by appending the last letters, reduces the comparison to $p{s}_i{s}_j{s}_i$ versus $p{s}_j{s}_i{s}_j$, which differ by the adjacent braid move.

The quadratic relation. Let $E:={⨁}_{w\in S_n}A{e}_w$. Define an $A$-linear operator ${\rho }_i$ by $e_w{\rho }_i=e_{w{s}_i}$ if $\mathrm{\ell }(w{s}_i)=\mathrm{\ell }(w)+1$, and $e_w{\rho }_i=(v-1)e_w+v{e}_{w{s}_i}$ if $\mathrm{\ell }(w{s}_i)=\mathrm{\ell }(w)-1$. If $i$ is an ascent, then $w{s}_i$ is a descent and $e_w{\rho }_i^2=(v-1)e_{w{s}_i}+v{e}_w=(v-1)e_w{\rho }_i+v{e}_w$. If $i$ is a descent, then $w{s}_i$ is an ascent, and $e_w{\rho }_i^2=(v-1)e_w{\rho }_i+v{e}_w$. Hence ${\rho }_i^2=(v-1){\rho }_i+v$.

Distant commutation. Suppose $\mathrm{\mid }i-j\mathrm{\mid }>1$. Swapping positions $i,i+1$ does not change the ascent/descent status in positions $j,j+1$, and conversely. Thus the two operators commute; the common values in the four cases are $\begin{array}{cl}\text{statuses at }w& e_w{\rho }_i{\rho }_j=e_w{\rho }_j{\rho }_i\\ \text{both ascents}& e_{w{s}_i{s}_j}\\ i\text{ ascent},j\text{ descent}& (v-1)e_{w{s}_i}+v{e}_{w{s}_i{s}_j}\\ i\text{ descent},j\text{ ascent}& (v-1)e_{w{s}_j}+v{e}_{w{s}_i{s}_j}\\ \text{both descents}& (v-1{)}^2{e}_w+v(v-1)(e_{w{s}_i}+e_{w{s}_j})+v^2{e}_{w{s}_i{s}_j}\mathrm{.}\end{array}$

Adjacent braid relation. Let $j=i+1$ and write $(a,b,c)$ for the entries of $w$ in positions $i,i+1,i+2$. Put $E=e_w$, $E_i=e_{w{s}_i}$, $E_j=e_{w{s}_j}$, $E_{ij}=e_{w{s}_i{s}_j}$, $E_{ji}=e_{w{s}_j{s}_i}$, and $E_{iji}=e_{w{s}_i{s}_j{s}_i}=e_{w{s}_j{s}_i{s}_j}$. Applying the ascent/descent rule from step 2.2 to these three positions gives the same value for $e_w{\rho }_i{\rho }_j{\rho }_i$ and $e_w{\rho }_j{\rho }_i{\rho }_j$ in each of the six possible one-line order types: $\begin{array}{cl}\text{order of }(a,b,c)& e_w{\rho }_i{\rho }_j{\rho }_i=e_w{\rho }_j{\rho }_i{\rho }_j\\ a<b<c& E_{iji}\\ a<c<b& (v-1)E_{ij}+v{E}_{iji}\\ b<a<c& (v-1)E_{ji}+v{E}_{iji}\\ b<c<a& (v-1{)}^2{E}_j+v(v-1)(E+E_{ji})+v^2{E}_{iji}\\ c<a<b& (v-1{)}^2{E}_i+v(v-1)(E+E_{ij})+v^2{E}_{iji}\\ c<b<a& ((v-1{)}^3+v(v-1))E+v(v-1{)}^2(E_i+E_j)+v^2(v-1)(E_{ij}+E_{ji})+v^3{E}_{iji}\mathrm{.}\end{array}$ These cases exhaust the distinct entries $a,b,c$, so ${\rho }_i{\rho }_j{\rho }_i={\rho }_j{\rho }_i{\rho }_j$.

Steps 2.2, 3.1 and 3.2 verify the defining relations of $H_v(n)$, so $E$ is a right $H_v(n)$-module by $e_w(T_{i_1}\cdots T_{i_r}):=e_w{\rho }_{i_1}\cdots {\rho }_{i_r}$. If $i_1\cdots i_k$ is a reduced word for $w$, step 1.1 shows every prefix is reduced and every letter is an ascent at its prefix, hence $e_{\mathrm{i}\mathrm{d}}{T}_{i_1}\cdots T_{i_k}=e_w$. By step 2.1 any two reduced expressions for $w$ differ by commutations and adjacent braid moves, which hold in $H_v(n)$ by [F1]; consequently $T_w$ is independent of the reduced expression.

Independence. If ${\sum }_w{a}_w{T}_w=0$ in $H_v(n)$ with $a_w\in A$, applying the right action of step 4.1 to $e_{\mathrm{i}\mathrm{d}}$ gives ${\sum }_w{a}_w{e}_w=0$ in the free module $E$, so every $a_w=0$.

Multiplication rule and spanning. Let $u=w{s}_i$. If $\mathrm{\ell }(u{s}_i)=\mathrm{\ell }(u)+1$, a reduced word for $u$ followed by $i$ is reduced by step 1.1, so $T_u{T}_i=T_{u{s}_i}$. If $\mathrm{\ell }(u{s}_i)=\mathrm{\ell }(u)-1$, then $u=(u{s}_i)s_i$ is reduced, so the first case and the quadratic relation [F1] give $T_u{T}_i=T_{u{s}_i}{T}_i^2=(v-1)T_u+v{T}_{u{s}_i}$. Every monomial in the generators reduces by induction on its number of letters to an $A$-linear combination of the $T_w$, so they span.

By step 5.1 the $T_w$ are linearly independent, and by step 5.2 they span. Thus they form an $A$-basis, giving clause (1); the multiplication rule of step 5.2 proves clause (2). The proof uses only inversion-count arguments, the defining presentation and the displayed finite local cases; no choice principle is used.