On a proof of the basis for the Weyl algebra The Weyl algebra is
$$
A=k\langle x,y\rangle/\langle yx-xy-1\rangle
$$
where $k$ is a field, $k\langle x,y\rangle$ is the free algebra, and $yx-xy-1$ is the defining relation. A basis for $A$ is $\{ x^i y^j|i,j\geq0\}$. What I am concerned about here is how to prove that elements of this set are linearly independent. Can we reason by contradiction that if $\sum c_{ij}x^i y^j=0$, then (after rewriting $\sum c_{ij}x^i y^j=\sum f_j(x)y^j$), $f_j(x)=0,\forall j$, thus $c_{ij}=0,\forall i,j$.
This is a bit weird, I feel.
Another related question is about the $q$-Weyl algebra
$$
B=k\langle x,y\rangle/\langle xx^{-1}-1,x^{-1}x-1,yy^{-1}-1,y^{-1}y-1,yx-qxy \rangle
$$
where $q\in k$. How to show that that a basis for $B$ is $\{x^i y^j|i,j\in \mathbb{Z}\}$? Can someone give me some hints on these two problems? Thank you very much!
 A: You can use Poincaré-Birkhoff-Witt, but it's not necessary. Simply observe that the Weyl algebra acts on $k[x]$ (by multiplication by $x$ and differentiation w.r.t. $x$), and all of the basis elements you describe act linearly independently (edit: in characteristic $0$!). The proof for the $q$-Weyl algebra should be similar except that $y$ acts by $q$-differentiation.
Edit: The above proof doesn't work in positive characteristic since there we have the pesky extra relation $\left( \frac{d}{dx} \right)^p = 0$. Here's one that does: it is a folk observation (see Stanley's Differential Posets for details) that the Weyl algebra acts on the free $k$-module $Y$ spanned by the set of Young diagrams as follows:


*

*$x$ acts by sending a diagram $\lambda$ to the set of all diagrams obtained by adding a box to $\lambda$ (such that the result is still a Young diagram),

*$y$ acts by sending a diagram $\lambda$ to the set of all diagrams obtained by removing a box from $\lambda$ (such that the result is still a Young diagram).


(The proof that this defines a representation of the Weyl algebra is left as a pleasant exercise.) 
Now suppose that there is a nontrivial linear dependence of the form
$$\sum_n c_n x^{i_n} y^{j_n} = 0.$$
Let $J = \text{max}_n(j_n)$, let $I = \text{max}_{j_n=J}(i_n)$, and consider the action of the LHS on the Young diagram $\lambda_{J+1} = (111...)$ consisting of $J+1$ boxes in a single row. Among the terms in
$$\sum_n c_n x^{i_n} y^{j_n} \lambda_{J+1}$$
the only ones which consist of a single column come from the terms $x^{i_n} y^{j_n}$ with $j_n = J$, and of these the tallest one comes from $x^I y^J$ and has a nonzero coefficient. Hence this sum is nonzero; contradiction. 
A: You just have to find a representation of the algebra (as Qiaochu discussed). A simple way of doing this is to consider the Weyl algebra acting on the (commutative) polynomial ring $k[u,v]$. Regarding this as a vector space over $k$ with basis $u^iv^j$ ($i,j\ge0$), you can define $x,y$ as linear operators on $k[u,v]$,
$$
\begin{align}
&x(u^iv^j)=u^{i+1}v^j,\\
&y(u^iv^j)=iu^{i-1}v^j+u^iv^{j+1}.
\end{align}
$$
You can check that $xy-yx=1$, so $k\langle x,y\rangle$ is a representation of the Weyl algebra. Also, if $\sum_{ij}c_{ij}x^iy^j=0$, then applying this to $1\in k[u,v]$ gives $\sum_{ij}c_{ij}u^iv^j$, so $c_{ij}=0$.
Note: All I did here was to look at the multiplication rules $x\cdot x^iy^j=x^{i+1}y^j$ and $y\cdot x^iy^j=ix^{i-1}y^j+x^iy^{j+1}$, then replace these by operations on $u^iv^j$.
The same thing works for the q-Weyl algebra. Consider $V=k[u,v,u^{-1},v^{-1}]$ as a vector space over $k$ with basis $u^iv^j$ ($i,j\in\mathbb{Z}$). Define $x,y$ acting on $V$ as
$$
\begin{align}
&x(u^iv^j)=u^{i+1}v^j,\\
&y(u^iv^j)=q^iu^iv^{j+1}.
\end{align}
$$
Then, $x,y$ are invertible linear operators with $yx=qxy$, so $k\langle x,y\rangle$ is a representation of the q-Weyl algebra. As before, if $\sum_{ij}c_{ij}x^iy^j=0$ then applying this to $1\in V$ gives $\sum_{ij}c_{ij}u^iv^j=0$, and $c_{ij}=0$.
A: One simple way to do this is to use Bergman's Diamond Lemma, and it works over any commutative ring $k$.
If we order monomials in the free algebra $k\langle x,y\rangle$ first by degree and then lexicographically, for example, then the relation $$yx-xy-1$$ gives a 'rewriting rule' of the form $$yx \leadsto xy + 1.$$ It is immediate that there are no ambiguities (in the sense of Bergman) so that it follows at once that the classes of the monomials in $k\langle x,y\rangle$ which do not contain $yx$ as a subword form a basis of the quotient $A_1=k\langle x,y\rangle/(yx-xy-1)$. This is precisely what you want.
Exactly the same reasoning gives you the quantum case (but now there will be overlapping ambiguities: for example, $xx^{-1}x$... but a little check shows they are all resolvable.)
If you intend to do this kind of things, you must learn about the Diamond Lemma. :)
