[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.
[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]
[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]
