[proofplan] We first use Matsumoto's theorem for the symmetric group to show that the element attached to a reduced expression is well-defined, because the defining braid relations exactly identify any two reduced expressions of the same permutation. We then prove the elementary multiplication rule for multiplying a standard element $T_w$ on the right by a generator $T_i$. This rule gives spanning by induction on the length of arbitrary generator words. For [linear independence](/page/Linear%20Independence), we construct the standard right-regular module with basis indexed by $S_n$, verify directly that the defining Hecke relations act on it, regard the action as a homomorphism into the opposite endomorphism algebra, and evaluate a putative linear relation at the identity basis vector. [/proofplan]

[step:Use Matsumoto's theorem to make $T_w$ independent of the reduced expression]Let $w\in S_n$, and suppose \begin{align*} w=s_{i_1}\cdots s_{i_\ell}=s_{j_1}\cdots s_{j_\ell} \end{align*} are two reduced expressions. The pair $(S_n,\{s_1,\dots,s_{n-1}\})$ is the type $A_{n-1}$ Coxeter system: the only defining braid relations among the simple reflections are the commutation relations for non-adjacent generators and the length-three braid relations for adjacent generators. By Matsumoto's theorem for Coxeter systems, applied to this Coxeter system, the word $s_{i_1}\cdots s_{i_\ell}$ can be transformed into the word $s_{j_1}\cdots s_{j_\ell}$ by a finite sequence of braid moves \begin{align*} s_is_j=s_js_i \quad\text{for } |i-j|>1 \end{align*} and \begin{align*} s_is_{i+1}s_i=s_{i+1}s_is_{i+1}. \end{align*} The defining relations of $H_q(S_n)$ impose the corresponding equalities \begin{align*} T_iT_j=T_jT_i \quad\text{for } |i-j|>1 \end{align*} and \begin{align*} T_iT_{i+1}T_i=T_{i+1}T_iT_{i+1}. \end{align*} Therefore each braid move preserves the product in $H_q(S_n)$, and hence \begin{align*} T_{i_1}\cdots T_{i_\ell}=T_{j_1}\cdots T_{j_\ell}. \end{align*} Thus $T_w$ is well-defined.[/step]

[guided]We must first justify that the notation $T_w$ does not depend on a hidden choice. The definition chooses a reduced expression for $w$, so the possible obstruction is that two reduced expressions might give different products in the algebra. The required Coxeter-theoretic input is Matsumoto's theorem for the symmetric group. The relevant Coxeter system is $(S_n,\{s_1,\dots,s_{n-1}\})$, whose defining braid relations are exactly the type $A$ commutation relations for non-adjacent generators and the length-three braid relations for adjacent generators. Matsumoto's theorem says that any two reduced expressions of a fixed permutation in these simple reflections are connected by a finite chain of these braid moves. In type $A$, these braid moves are exactly \begin{align*} s_is_j=s_js_i \quad\text{when } |i-j|>1 \end{align*} and \begin{align*} s_is_{i+1}s_i=s_{i+1}s_is_{i+1}. \end{align*} The algebra $H_q(S_n)$ was defined by imposing the corresponding relations among the generators $T_i$: \begin{align*} T_iT_j=T_jT_i \quad\text{when } |i-j|>1 \end{align*} and \begin{align*} T_iT_{i+1}T_i=T_{i+1}T_iT_{i+1}. \end{align*} Now let \begin{align*} w=s_{i_1}\cdots s_{i_\ell}=s_{j_1}\cdots s_{j_\ell} \end{align*} be two reduced expressions. Matsumoto's theorem gives a finite sequence of reduced words connecting the first word to the second, and each adjacent pair in the sequence differs by one of the two braid moves above. Replacing $s$ by $T$ in that move gives an equality in $H_q(S_n)$ by the defining relations. Hence the product in $H_q(S_n)$ is unchanged at every step in the sequence, and therefore \begin{align*} T_{i_1}\cdots T_{i_\ell}=T_{j_1}\cdots T_{j_\ell}. \end{align*} This proves that $T_w$ is a well-defined element of $H_q(S_n)$.[/guided]

[step:Compute right multiplication by one generator] Let $w\in S_n$ and let $1\le i\le n-1$. If $\ell(ws_i)=\ell(w)+1$, then a reduced expression for $w$ followed by $s_i$ is a reduced expression for $ws_i$, so \begin{align*} T_wT_i=T_{ws_i}. \end{align*} If $\ell(ws_i)=\ell(w)-1$, then $w=(ws_i)s_i$ and $\ell(w)=\ell(ws_i)+1$. The previous case applied to $ws_i$ gives \begin{align*} T_w=T_{ws_i}T_i. \end{align*} Thus, using the quadratic relation, \begin{align*} T_wT_i=T_{ws_i}T_i^2. \end{align*} Substituting $T_i^2=(q-1)T_i+q$ gives \begin{align*} T_wT_i=(q-1)T_{ws_i}T_i+qT_{ws_i}. \end{align*} Since $T_{ws_i}T_i=T_w$, this becomes \begin{align*} T_wT_i=(q-1)T_w+qT_{ws_i}. \end{align*} [/step]

[step:Reduce every generator word to a linear combination of standard elements] Let $\mathcal S=\{s_1,\dots,s_{n-1}\}$ and let $\mathcal T=\{T_1,\dots,T_{n-1}\}$. We prove by induction on $m\in\mathbb N\cup\{0\}$ that every product \begin{align*} T_{i_1}\cdots T_{i_m} \end{align*} with $1\le i_k\le n-1$ for each $k$ lies in the $R$-submodule of $H_q(S_n)$ spanned by $\{T_w:w\in S_n\}$. For $m=0$, the empty product is the identity element of $H_q(S_n)$, and this is $T_e$, where $e\in S_n$ is the identity permutation. Assume the assertion holds for products of length $m-1$, and consider a product \begin{align*} T_{i_1}\cdots T_{i_m}. \end{align*} By the induction hypothesis, there exist coefficients $a_w\in R$, indexed by $w\in S_n$, such that \begin{align*} T_{i_1}\cdots T_{i_{m-1}}=\sum_{w\in S_n}a_wT_w. \end{align*} Multiplying on the right by $T_{i_m}$ gives \begin{align*} T_{i_1}\cdots T_{i_m}=\sum_{w\in S_n}a_wT_wT_{i_m}. \end{align*} The multiplication rule from the previous step expresses each factor $T_wT_{i_m}$ as either $T_{ws_{i_m}}$ or $(q-1)T_w+qT_{ws_{i_m}}$. Hence the product is an $R$-linear combination of elements $T_u$ with $u\in S_n$. Since $H_q(S_n)$ is generated as an $R$-algebra by $T_1,\dots,T_{n-1}$, these products span $H_q(S_n)$ as an $R$-module. Therefore $\{T_w:w\in S_n\}$ spans $H_q(S_n)$. [/step]

[step:Build the standard module indexed by permutations] Let $M$ be the free $R$-module with basis \begin{align*} \{m_w:w\in S_n\}. \end{align*} For each $1\le i\le n-1$, define an $R$-[linear map](/page/Linear%20Map) \begin{align*} U_i:M&\to M \end{align*} on basis vectors by \begin{align*} U_i(m_w)=m_{ws_i} \end{align*} if $\ell(ws_i)=\ell(w)+1$, and by \begin{align*} U_i(m_w)=(q-1)m_w+qm_{ws_i} \end{align*} if $\ell(ws_i)=\ell(w)-1$. We verify the quadratic relation. If $\ell(ws_i)=\ell(w)+1$, then $\ell(ws_is_i)=\ell(w)=\ell(ws_i)-1$, so \begin{align*} U_i^2(m_w)=U_i(m_{ws_i}). \end{align*} By the decreasing case in the definition of $U_i$, \begin{align*} U_i^2(m_w)=(q-1)m_{ws_i}+qm_w. \end{align*} Since $U_i(m_w)=m_{ws_i}$, this is \begin{align*} U_i^2(m_w)=(q-1)U_i(m_w)+qm_w. \end{align*} If $\ell(ws_i)=\ell(w)-1$, then $U_i(m_w)=(q-1)m_w+qm_{ws_i}$. Applying $U_i$ and using $\ell(ws_is_i)=\ell(w)=\ell(ws_i)+1$ gives \begin{align*} U_i^2(m_w)=(q-1)U_i(m_w)+qU_i(m_{ws_i}). \end{align*} Since $U_i(m_{ws_i})=m_w$, we obtain \begin{align*} U_i^2(m_w)=(q-1)U_i(m_w)+qm_w. \end{align*} Thus \begin{align*} U_i^2=(q-1)U_i+q\operatorname{id}_M. \end{align*} We next verify the braid relations. For $|i-j|>1$, set $a=s_i$ and $b=s_j$. The adjacent transpositions $a$ and $b$ commute, and the rank two parabolic subgroup $W_{i,j}:=\langle a,b\rangle$ has elements $1,a,b,ab$. We use the standard parabolic coset lemma for Coxeter groups: every right coset of a standard parabolic subgroup has a unique minimal-length representative $x$, and that representative satisfies $\ell(xv)=\ell(x)+\ell(v)$ for every element $v$ of the parabolic subgroup. Thus, on each right coset $xW_{i,j}$, the formulas for $U_i$ and $U_j$ on the span of $m_x,m_{xa},m_{xb},m_{xab}$ reduce to the four-element calculation in $W_{i,j}$. The calculation is: both $U_iU_j$ and $U_jU_i$ send $m_x$ to $m_{xab}$, send $m_{xa}$ to $(q-1)m_{xab}+qm_{xb}$, send $m_{xb}$ to $(q-1)m_{xab}+qm_{xa}$, and send $m_{xab}$ to $(q-1)^2m_{xab}+q(q-1)m_{xa}+q(q-1)m_{xb}+q^2m_x$. Hence $U_iU_j=U_jU_i$ on that coset. Since the right cosets partition $S_n$, we have \begin{align*} U_iU_j=U_jU_i. \end{align*} For $1\le i\le n-2$, set $a=s_i$, $b=s_{i+1}$, and $W_i:=\langle a,b\rangle\cong S_3$. By the same standard parabolic coset lemma, each right coset $xW_i$ has a unique minimal-length representative $x$. Then every element of the coset has the form $xv$ with $v\in W_i$, and \begin{align*} \ell(xv)=\ell(x)+\ell(v). \end{align*} Thus the action of $U_i$ and $U_{i+1}$ on the span of the six basis vectors $m_x,m_{xa},m_{xb},m_{xab},m_{xba},m_{xaba}$ is the ordinary six-element calculation in $S_3$, with the fixed prefix $x$ attached. A direct computation from the defining formulas gives the following common values for $U_iU_{i+1}U_i$ and $U_{i+1}U_iU_{i+1}$: $m_x$ is sent to $m_{xaba}$; $m_{xa}$ is sent to $(q-1)m_{xaba}+qm_{xba}$; $m_{xb}$ is sent to $(q-1)m_{xaba}+qm_{xab}$; $m_{xab}$ is sent to $(q-1)^2m_{xaba}+q(q-1)m_{xab}+q(q-1)m_{xba}+q^2m_{xb}$; $m_{xba}$ is sent to $(q-1)^2m_{xaba}+q(q-1)m_{xab}+q(q-1)m_{xba}+q^2m_{xa}$; and $m_{xaba}$ is sent to $q^3m_x+((q-1)^3+q(q-1))m_{xaba}+q(q-1)^2m_{xab}+q(q-1)^2m_{xba}+q^2(q-1)m_{xa}+q^2(q-1)m_{xb}$. Hence \begin{align*} U_iU_{i+1}U_i=U_{i+1}U_iU_{i+1}. \end{align*} Thus the endomorphisms $U_1,\dots,U_{n-1}$ satisfy all defining relations of $H_q(S_n)$ when composed as right multiplication operators. Let $\operatorname{End}_R(M)^{\operatorname{op}}$ denote the opposite $R$-algebra of $\operatorname{End}_R(M)$. By the universal property of the presented algebra, there is an $R$-algebra homomorphism \begin{align*} \Phi:H_q(S_n)\to \operatorname{End}_R(M)^{\operatorname{op}} \end{align*} such that $\Phi(T_i)=U_i$ for every $1\le i\le n-1$. [/step]

[step:Evaluate at the identity vector to prove linear independence] For $w\in S_n$, let \begin{align*} w=s_{i_1}\cdots s_{i_\ell} \end{align*} be a reduced expression. For each $0\le k\le \ell$, define \begin{align*} w_k:=s_{i_1}\cdots s_{i_k}, \end{align*} with $w_0=e$. Since the expression is reduced, we have \begin{align*} \ell(w_k)=k \end{align*} for every $0\le k\le \ell$. Therefore \begin{align*} \ell(w_{k-1}s_{i_k})=\ell(w_k)=\ell(w_{k-1})+1 \end{align*} for every $1\le k\le \ell$. By the increasing case in the definition of $U_{i_k}$, \begin{align*} U_{i_k}(m_{w_{k-1}})=m_{w_k}. \end{align*} Because $\Phi$ takes values in $\operatorname{End}_R(M)^{\operatorname{op}}$, the product $\Phi(T_{i_1}\cdots T_{i_\ell})$ is the underlying endomorphism $U_{i_\ell}\circ\cdots\circ U_{i_1}$, so it applies $U_{i_1}$ first, then $U_{i_2}$, and so on. Inducting on $k$ gives \begin{align*} \Phi(T_w)(m_e)=m_w. \end{align*} Suppose that a finite $R$-linear relation holds in $H_q(S_n)$: \begin{align*} \sum_{w\in S_n}a_wT_w=0, \end{align*} where $a_w\in R$ for every $w\in S_n$. Applying $\Phi$ and evaluating at $m_e$ gives \begin{align*} 0=\sum_{w\in S_n}a_w\Phi(T_w)(m_e). \end{align*} Using $\Phi(T_w)(m_e)=m_w$, this becomes \begin{align*} 0=\sum_{w\in S_n}a_wm_w. \end{align*} The vectors $\{m_w:w\in S_n\}$ form an $R$-basis of the free module $M$, so each coefficient satisfies $a_w=0$. Hence $\{T_w:w\in S_n\}$ is $R$-linearly independent. Together with the spanning result, this proves that $\{T_w:w\in S_n\}$ is an $R$-basis of $H_q(S_n)$. [/step]