Let be a Coxeter group with a generating set
Definition 1. The Hecke algebra of denoted is generated by elements over the ring such that multiplication satisfies
where the order is Bruhat. It is trivial to verify that the Hecke algebra is unital with unit
Proposition 2. If then is invertible with inverse
It follows that all elements of the form with are invertible, so the Hecke algebra is a division algebra. Moreover it is a *-algebra with involution defined by
It turns out that there is a basis of where
with and which can be proven to uniquely exist for elements which are called the Kazhdan-Lusztig polynomials.
 Björner, Anders and Francesco Brenti. Combinatorics of Coxeter Groups. Vol. 231. Graduate Texts in Mathematics. Springer. 2005.