%----------------------------------------------------------------------------
% HANPAPER_no     = 45
% HANPAPER_type   = divers 
% PUBPAPER_author = D. Foata, G.-N. Han
% PUBPAPER_title  = A basis for the right quantum algebra \\
%                      and the ``$1=q$" principle
% PUBPAPER_journal= ???? 
% PUBPAPER_volume = ?? 
% PUBPAPER_year   = 2006 
% PUBPAPER_pages  = 9 
% MAKEPAPER_output= ps pdf 
% MAKEPAPER_4up   = "-W18cm -H33cm -m30 -b-90"
%----------------------------------------------------------------------------



% Find "DEF"
% Find "BODY"
\input amstex
\input amsppt.sty 

% FORMAT <<<

%! \font\tenbboard=msbm10
%! \font\sevenbb=msbm7
%! \def\bboard#1{\hbox{\tenbboard #1}}
%! \font\tengoth=eufm10
%! \def\goth#1{\hbox{\tengoth #1}}


\catcode`\@=12


\def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
   \vfill\hrule}\vrule}}

\def\cqfd{\penalty 500 \hbox{\qed}\par\smallskip}

\def\rem#1|{\par\medskip{{\it #1}\pointir}}

\def\decale#1{\smallbreak
               \noindent\hskip 28pt\llap{\rm #1}\
                \ignorespaces}

\def\decaledecale#1{\smallbreak
                     \noindent\hskip 34pt\llap{\rm #1}\
                            \ignorespaces}

\def\vspace[#1]{\noalign{\vskip#1}}

%%%%%%% grille %%%%%
\def\Grille{\setbox13=\vbox to 5mm{\hrule width 110mm\vfill}
\setbox13=\vbox{\offinterlineskip
   \copy13\copy13\copy13\copy13\copy13\copy13\copy13\copy13
   \copy13\copy13\copy13\copy13\box13\hrule width 110mm}
\setbox14=\hbox to 5mm{\vrule height 65mm\hfill}
\setbox14=\hbox{\copy14\copy14\copy14\copy14\copy14\copy14
   \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14
   \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14\box14}
\ht14=0pt\dp14=0pt\wd14=0pt
\setbox13=\vbox to 0pt{\vss\box13\offinterlineskip\box14}
\wd13=0pt\box13}

\def\grille{\noalign{\nointerlineskip\Grille\nointerlineskip}}

%������������������������������������������������������������������

\def\fleche(#1,#2)\dir(#3,#4)\long#5{%
\noalign{\nointerlineskip\leftput(#1,#2){\vector(#3,#4){#5}}\nointerlineskip
}}

%������������������������������������������������������������������

\def\diagram#1{\def\normalbaselines{\baselineskip=0pt\lineskip=5pt}
\matrix{#1}}

\def\hfl#1#2#3{\smash{\mathop{\hbox to#3{\rightarrowfill}}\limits
^{\scriptstyle#1}_{\scriptstyle#2}}}

\def\gfl#1#2#3{\smash{\mathop{\hbox to#3{\leftarrowfill}}\limits
^{\scriptstyle#1}_{\scriptstyle#2}}}

\def\vfl#1#2#3{\llap{$\scriptstyle #1$}
\left\downarrow\vbox to#3{}\right.\rlap{$\scriptstyle #2$}}

%������������������������������������������������������������������


 \message{`lline' & `vector' macros from LaTeX}
 \catcode`@=11
\def\{{\relax\ifmmode\lbrace\else$\lbrace$\fi}
\def\}{\relax\ifmmode\rbrace\else$\rbrace$\fi}
\def\newcount{\alloc@0\count\countdef\insc@unt}
\def\newdimen{\alloc@1\dimen\dimendef\insc@unt}
\def\newwrite{\alloc@7\write\chardef\sixt@@n}

\newwrite\@unused
\newcount\@tempcnta
\newcount\@tempcntb
\newdimen\@tempdima
\newdimen\@tempdimb
\newbox\@tempboxa

\def\@spaces{\space\space\space\space}
\def\@whilenoop#1{}
\def\@whiledim#1\do #2{\ifdim #1\relax#2\@iwhiledim{#1\relax#2}\fi}
\def\@iwhiledim#1{\ifdim #1\let\@nextwhile=\@iwhiledim
        \else\let\@nextwhile=\@whilenoop\fi\@nextwhile{#1}}
\def\@badlinearg{\@latexerr{Bad \string\line\space or \string\vector
   \space argument}}
\def\@latexerr#1#2{\begingroup
\edef\@tempc{#2}\expandafter\errhelp\expandafter{\@tempc}%
%% error help message pieces.
\def\@eha{Your command was ignored.
^^JType \space I <command> <return> \space to replace it
  with another command,^^Jor \space <return> \space to continue without it.}
\def\@ehb{You've lost some text. \space \@ehc}
\def\@ehc{Try typing \space <return>
  \space to proceed.^^JIf that doesn't work, type \space X <return> \space
to
  quit.}
\def\@ehd{You're in trouble here.  \space\@ehc}

\typeout{LaTeX error. \space See LaTeX manual for explanation.^^J
 \space\@spaces\@spaces\@spaces Type \space H <return> \space for
 immediate help.}\errmessage{#1}\endgroup}
\def\typeout#1{{\let\protect\string\immediate\write\@unused{#1}}}

% line & circle fonts
\font\tenln    = line10
\font\tenlnw   = linew10
%\font\tencirc  = circle10
%\font\tencircw = circlew10


\newdimen\@wholewidth
\newdimen\@halfwidth
\newdimen\unitlength

\unitlength =1pt

%\newbox\@picbox
%\newdimen\@picht

\def\thinlines{\let\@linefnt\tenln \let\@circlefnt\tencirc
  \@wholewidth\fontdimen8\tenln \@halfwidth .5\@wholewidth}
\def\thicklines{\let\@linefnt\tenlnw \let\@circlefnt\tencircw
  \@wholewidth\fontdimen8\tenlnw \@halfwidth .5\@wholewidth}

\def\linethickness#1{\@wholewidth #1\relax \@halfwidth .5\@wholewidth}



\newif\if@negarg

\def\lline(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vline
  \else \ifnum\@yarg =0 \@hline \else \@sline\fi
\fi}

\def\@sline{\ifnum\@xarg< 0 \@negargtrue \@xarg -\@xarg \@yyarg -\@yarg
  \else \@negargfalse \@yyarg \@yarg \fi
\ifnum \@yyarg >0 \@tempcnta\@yyarg \else \@tempcnta -\@yyarg \fi
\ifnum\@tempcnta>6 \@badlinearg\@tempcnta0 \fi
\setbox\@linechar\hbox{\@linefnt\@getlinechar(\@xarg,\@yyarg)}%
\ifnum \@yarg >0 \let\@upordown\raise \@clnht\z@
   \else\let\@upordown\lower \@clnht \ht\@linechar\fi
\@clnwd=\wd\@linechar
\if@negarg \hskip -\wd\@linechar \def\@tempa{\hskip -2\wd\@linechar}\else
     \let\@tempa\relax \fi
\@whiledim \@clnwd <\@linelen \do
  {\@upordown\@clnht\copy\@linechar
   \@tempa
   \advance\@clnht \ht\@linechar
   \advance\@clnwd \wd\@linechar}%
\advance\@clnht -\ht\@linechar
\advance\@clnwd -\wd\@linechar
\@tempdima\@linelen\advance\@tempdima -\@clnwd
\@tempdimb\@tempdima\advance\@tempdimb -\wd\@linechar
\if@negarg \hskip -\@tempdimb \else \hskip \@tempdimb \fi
\multiply\@tempdima \@m
\@tempcnta \@tempdima \@tempdima \wd\@linechar \divide\@tempcnta \@tempdima
\@tempdima \ht\@linechar \multiply\@tempdima \@tempcnta
\divide\@tempdima \@m
\advance\@clnht \@tempdima
\ifdim \@linelen <\wd\@linechar
   \hskip \wd\@linechar
  \else\@upordown\@clnht\copy\@linechar\fi}

%\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
%\vrule \@height \@halfwidth \@depth \@halfwidth \@width
%\@linelen \ifnum \@xarg <0 \hskip -\@linelen \fi}


\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
\vrule height \@halfwidth depth \@halfwidth width \@linelen
\ifnum \@xarg <0 \hskip -\@linelen \fi}

\def\@getlinechar(#1,#2){\@tempcnta#1\relax\multiply\@tempcnta 8
\advance\@tempcnta -9 \ifnum #2>0 \advance\@tempcnta #2\relax\else
\advance\@tempcnta -#2\relax\advance\@tempcnta 64 \fi
\char\@tempcnta}

\def\vector(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vvector
  \else \ifnum\@yarg =0 \@hvector \else \@svector\fi
\fi}

\def\@hvector{\@hline\hbox to 0pt{\@linefnt
\ifnum \@xarg <0 \@getlarrow(1,0)\hss\else
    \hss\@getrarrow(1,0)\fi}}

\def\@vvector{\ifnum \@yarg <0 \@downvector \else \@upvector \fi}

\def\@svector{\@sline
\@tempcnta\@yarg \ifnum\@tempcnta <0 \@tempcnta=-\@tempcnta\fi
\ifnum\@tempcnta <5
  \hskip -\wd\@linechar
  \@upordown\@clnht \hbox{\@linefnt  \if@negarg
  \@getlarrow(\@xarg,\@yyarg) \else \@getrarrow(\@xarg,\@yyarg) \fi}%
\else\@badlinearg\fi}

\def\@getlarrow(#1,#2){\ifnum #2 =\z@ \@tempcnta='33\else
\@tempcnta=#1\relax\multiply\@tempcnta \sixt@@n \advance\@tempcnta
-9 \@tempcntb=#2\relax\multiply\@tempcntb \tw@
\ifnum \@tempcntb >0 \advance\@tempcnta \@tempcntb\relax
\else\advance\@tempcnta -\@tempcntb\advance\@tempcnta 64
\fi\fi\char\@tempcnta}

\def\@getrarrow(#1,#2){\@tempcntb=#2\relax
\ifnum\@tempcntb < 0 \@tempcntb=-\@tempcntb\relax\fi
\ifcase \@tempcntb\relax \@tempcnta='55 \or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -6 \else \ifnum #1=3 \@tempcnta=49
\else\@tempcnta=58 \fi\fi\or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -3 \else \@tempcnta=51\fi\or
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta -\tw@ \else
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta 7 \fi\ifnum #2<0 \advance\@tempcnta 64 \fi
\char\@tempcnta}



\def\@vline{\ifnum \@yarg <0 \@downline \else \@upline\fi}


\def\@upline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \@linelen depth \z@\hss}}

\def\@downline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \z@ depth \@linelen \hss}}

\def\@upvector{\@upline\setbox\@tempboxa\hbox{\@linefnt\char'66}\raise
     \@linelen \hbox to\z@{\lower \ht\@tempboxa\box\@tempboxa\hss}}

\def\@downvector{\@downline\lower \@linelen
      \hbox to \z@{\@linefnt\char'77\hss}}

%INITIALIZATION
\thinlines

\newcount\@xarg
\newcount\@yarg
\newcount\@yyarg
\newcount\@multicnt
\newdimen\@xdim
\newdimen\@ydim
\newbox\@linechar
\newdimen\@linelen
\newdimen\@clnwd
\newdimen\@clnht
\newdimen\@dashdim
\newbox\@dashbox
\newcount\@dashcnt
 \catcode`@=12


% macros supplementaires (J.D.)

\newbox\tbox
\newbox\tboxa

%\def\picbox(#1,#2,#3)#4{\setbox\tbox=\hbox{#4}%
%     \ht\tbox=#1 \wd\tbox=#2 \dp\tbox=#3 \box\tbox}

\def\leftzer#1{\setbox\tbox=\hbox to 0pt{#1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\rightzer#1{\setbox\tbox=\hbox to 0pt{\hss #1}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\centerzer#1{\setbox\tbox=\hbox to 0pt{\hss #1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

% sytaxe: \image(hauteur totale reservee, distance
%    verticale de l'origine par rapport au bas de
%    la place reservee){materiel a inserer}
% L'origine est toujours centre horizontalement
%
\def\image(#1,#2)#3{\vbox to #1{\offinterlineskip
    \vss #3 \vskip #2}}

% \leftput place le materiel avec son point de reference
%    en #1,#2 unites \unitlength
% De meme pour \centerput et \rightput

\def\leftput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\leftzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\rightput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\rightzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\centerput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\centerzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\unitlength=1mm

\let\cput=\centerput

\def\put(#1,#2)#3{\noalign{\nointerlineskip
                               \centerput(#1,#2){$#3$}
                                \nointerlineskip}}
%%%%%%%% endofgrille
%>>>

% DEF <<<

\def\cal#1{\Cal#1} 
\def\bboard{\Bbb} 

\font\sevenbboard=msbm7
\font\tengoth=eufm10
\font\sevengoth=eufm7

\def\setA{{\bboard A}}
\def\setAA{\hbox{\sevenbboard A}}
\def\setZ{{\bboard Z}}
\def\calC{{\cal C}}
\def\calB{{\cal B}}
\def\calA{{\cal A}}
\def\calI{{\cal I}}
\def\Sym{\hbox{\tengoth S}}
\def\SSym{\hbox{\sevengoth S}}
\def\modI{\pmod{\calI}}
\def\modIq{\pmod{\calI_q}}
%
\def\Ferm{\mathop{\text{\rm Ferm}}\nolimits}
\def\Bos{\mathop{\text{\rm Bos}}\nolimits}
\def\Univ{\mathop{\text{\rm Univ}}\nolimits}
%
\def\des{\mathop{\text{\rm des}}}
\def\ddes{\mathop{\text{\rm ddes}}}
\def\dr{\mathop{\text{\rm dr}}}
\def\rd{\mathop{\text{\rm rd}}}
\def\rr{\mathop{\text{\rm rr}}}
\def\bfs{\mathop{\text{\bf s}}}
\def\id{\mathop{\text{\rm id}}}
\def\Id{\mathop{\text{\rm Id}}}
\def\len{{\ell}}
\def\inv{\mathop{\text{\rm inv}}\nolimits}
\def\imv{\mathop{\text{\rm imv}}\nolimits}
%
\def\bw#1#2{\bigl(\smallmatrix{#1\cr#2\cr}\bigr)}
\def\sbw#1#2{\bigl[\smallmatrix{#1\cr#2\cr}\bigr]}
\def\bww#1#2#3#4#5#6{\bigl[\sbw{#1#2}{#4#5} \bw{#3}{#6} \bigr]}
\def\wbw#1#2#3#4#5#6{\bigl[\bw{#1}{#4} \sbw{#2#3}{#5#6} \bigr]}
%
\def\egale#1{\smash{\;\displaystyle\mathop{=}^#1\;}}
\def\direction{\mathop{\rm dir}\nolimits}
\def\DIR{\mathop{\hbox{\eightrm DIR}}\nolimits}
\def\can{\mathop{\rm can}\nolimits}

\def\smallmatrix#1{\vcenter{\offinterlineskip
     \halign{\vrule height 4pt depth 2pt width 0pt
      \hfil$\scriptstyle##$\hfil&&\kern
       3pt\hfil$\scriptstyle##$\hfil \crcr#1\crcr}}}


\catcode`\@=11
\def\matrice#1{\null \,\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\  \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}\,}

\def\pmatrice#1{\left(\null\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\thinspace  \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}\right)}

\def\bmatrice#1{\left[\null\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\thinspace  \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}\right]}

\catcode`\@=12


\frenchspacing

\def\thReduction{3}
\def\eqOldSumE{E1}
\def\eqNewSumE{E2}

%Ref
\def\RefBe{Be78}
\def\RefEP{EP06}
\def\RefFH{FH05}
\def\RefGLZ{GLZ05}
\def\RefKa{Ka95}
\def\RefKP{KP06}
\def\RefLT{LT06}
\def\RefLoI{Lo83}
\def\RefLoII{Lo02}
\def\RefMa{Ma15}
\def\RefPW{PW91}
\def\RefRTI{RT02}
\def\RefRTII{RT05}

%Ref
\def\RefBe{1}
\def\RefEP{2}
\def\RefFH{3}
\def\RefGLZ{4}
\def\RefHL{5}
\def\RefKa{6}
\def\RefKP{7}
\def\RefLT{8}
\def\RefLoI{9}
\def\RefLoII{10}
\def\RefMa{11}
\def\RefPW{12}
\def\RefRTI{13}
\def\RefRTII{14}


% >>>

%----------------------------------------------------------------------
% BODY
%----------------------------------------------------------------------

% ENTETE <<<
\topmatter
\title A basis for the right quantum algebra
and the ``$1=q$" principle
\endtitle

\author Dominique Foata and Guo-Niu Han\endauthor

\address Institut Lothaire, 1 rue Murner, F-67000 Strasbourg, France \endaddress
\email foata\@math.u-strasbg.fr \endemail

\address I.R.M.A. UMR 7501, Universit\'e Louis Pasteur et CNRS, 
7 rue Ren\'e-Descartes, F-67084 Strasbourg, France \endaddress
\email guoniu\@math.u-strasbg.fr \endemail

%  Math Subject Classifications
\subjclass Primary 05A19, 05A30, 16W35, 17B37\endsubjclass

\date January 10, 2006\enddate

\keywords Right quantum algebra, quantum MacMahon Master theorem\endkeywords

\abstract
\quad
We construct a basis for the right quantum algebra introduced
by Garoufalidis, L\^e and Zeilberger and give a method
making it possible to go from an algebra subject to
commutation relations (without the variable~$q$) to the
right quantum algebra by means of an appropriate
weight-function. As a consequence, a strong quantum
MacMahon Master Theorem is derived. Besides, the algebra of
biwords is systematically in use.
\endabstract

\endtopmatter

\document
% >>>

\head 1. Introduction\endhead % <<<
In their search for a {\it natural $q$-analogue} of the
MacMahon Master Theorem Garoufalidis {\it et al.} [\RefGLZ]
have introduced the {\it right quantum algebra}~${\cal R}_q$
defined to be the associative algebra over a commutative
ring~$K$, generated by $r^2$ elements
$X_{xa}$ $(1\le x,a\le r)$ ($r\ge 2$) subject to the following
commutation relations:
$$
\vbox{\hfil$\eqalign{
X_{yb} X_{xa} - X_{xa} X_{yb}
&= q^{-1}X_{xb}
X_{ya}-qX_{ya} X_{xb},\cr
{X}_{ya} X_{xa}&=q^{-1} X_{xa}
X_{ya},\cr}\quad
\eqalign{
&\hbox{($x>y$, $a>b$)}; \cr
&(x>y,\ \hbox{all }a); \cr
}$\hfil
}
$$
with $q$ being an invertible element in~$K$.
The right quantum algebra in the case $r=2$ has already
been studied by Rodr\'\i guez-Romo and Taft [\RefRTI], 
who set up an explicit basis for it. On the other
hand, a basis for the {\it full quantum} algebra has been duly
constructed (see [\RefPW, Theorem 3.5.1, p. 38]) for an
arbitrary $r\ge 2$. It then seems natural to do the same with
the right quantum algebra for each $r\ge 2$. This is the
first goal of the paper.

In fact, the paper originated from a discussion with
Doron Zeilberger, when he explained to the first author how
he verified the quantum MacMahon Master identity for each
fixed~$r$ by computer code. His computer program uses the
fact, as he is perfectly aware, that the set of {\it irreducible
biwords}---which will be introduced in the sequel---{\it
generates} the right quantum algebra. For a better
understanding of his joint paper [\RefGLZ] and also for
deriving  the ``$1=q$" principle, it seems
essential to see whether the set of irreducible biwords has
the further property of being a {\it basis}, and it does.
Thanks to this result, a {\it strong quantum
MacMahon Master Theorem} can be subsequently derived.

\medskip
When manipulating the above relations, the visible part of the
commutations is made within the subcripts of the
$X_{xa}$'s, written as such. It is then important to magnify
them by having an adequate notation. To that end we replace
each
$$X_{xa}\hbox{ by the
{\it biletter} }\textstyle{x\choose a},
$$
so that, in further computations,
products $X_{x_1,a_1}X_{x_2,a_2}\cdots X_{x_\ell,a_\ell}$
become {\it biwords}
${x_1 x_2 \cdots x_\ell\choose a_1 a_2 \cdots a_\ell}$,
objects that have been efficiently used
in combinatorial contexts [\RefLoI, \RefLoII].
Accordingly, the commutation rules for the right
quantum algebra can be written as:
$$\eqalign{\textstyle
{yx\choose ba}-{xy\choose ab}&=
\textstyle  q^{-1}{xy\choose ba}-q{yx\choose ab}
\kern1.75cm (x>y,\, a>b);\cr
\textstyle{yx\choose aa}
&= \textstyle q^{-1}{xy\choose
aa}
\kern3cm (x>y,\; {\text{all}\ }a).\cr }
$$

We shall use the following notations.
The positive integer $r$ will be kept fixed throughout
and $\setA$ will designate the {\it alphabet}
$\{1,2,\ldots,r\}$. A {\it biword} on~$\setA$  is
a $2\times n$ matrix~$\alpha={x_1\cdots x_n\choose
a_1\cdots a_n}$ ($n\geq 0$), whose entries are in
$\setA$, the first (resp. second) row being called
the {\it top word} (resp. {\it bottom word\/}) of the
biword~$\alpha$. The number $n$ is the {\it length} of
$\alpha$; we write $\len(\alpha)=n$. The biword~$\alpha$
can also be viewed as a {\it word} of {\it biletters}
${x_1\choose a_1}\cdots{x_n\choose a_n}$, those biletters
$x_i\choose a_i$ being pairs of integers written vertically
with $x_i,a_i\in \setA$ for all $i=1,\ldots,n$. The {\it
product} of two biwords is their concatenation.

Let ${\bboard B}$ denote the set of biletters and $\calB$
the set of all biwords.
Let $\alpha\in \calB$ such that
$\len(\alpha)\geq 2$
and $1\leq i\leq
\len(\alpha)-1$ be a positive integer. The biword~$\alpha$
can be factorized as
$\alpha=\beta\bw{xy}{ab}\gamma$,  where
$x,y,a,b\in \setA$ and $\beta,\gamma\in \calB$ with
$\len(\beta)=i-1$. Say that $\alpha$ has a {\it double
descent} at position $i$ if $x>y$ and $a\geq b$. Notice the
discrepancy in the inequalities on the top word and the
bottom one. A biword~$\alpha$ without any double descent is
said to be {\it irreducible}. The set of all irreducible
biwords is denoted by ${\cal B}_{\text{irr}}$.

Let $\bboard Z$ be the ring of all integers and
${\bboard Z}[q,q^{-1}]$ the ring of the
polynomials in the variables~$q$, $q^{-1}$ subject to
the rule $qq^{-1}=1$ with integral coefficients. The set
$\calA={\bboard Z}\langle\!\langle \calB\rangle\!\rangle$
of the formal sums $\sum_{\alpha} c(\alpha)
\alpha$, where $\alpha\in\calB$ and $c(\alpha)\in\setZ$,
together with the above biword multiplication,
the free addition and the free scalar product
forms an algebra over $\setZ$, called the {\it free biword
large $\setZ$-algebra}. The formal sums
$\sum_\alpha c(\alpha)\alpha$ will be called {\it
expressions}. An expression $\sum_\alpha c(\alpha)
\alpha$ is said to be  {\it irreducible} if $c(\alpha)=\nobreak 0$ for
all $\alpha\not\in\calB_{\text{irr}}$. The set of all
irreducible expressions is denoted by
${\cal A}_{\text{irr}}$.

Similarly, 
let $\calA_q={\bboard Z}[q,q^{-1}]
\langle\!\langle\calB\rangle\!\rangle$
denote the large ${\bboard Z}[q,q^{-1}]$-algebra of the
formal sums $\sum_\alpha c(\alpha)\alpha$, where
$c(\alpha)\in {\bboard Z}[q,q^{-1}]$ for all $\alpha\in {\cal B}$.
Following Bergman's method [\RefBe] we introduce two {\it
reduction systems}
$(S)$ and
$(S_q)$ as being the sets of pairs
$(\alpha,[\alpha])\in {\cal B}\times {\cal A}$ and
$(\alpha,[\alpha]_q)\in {\cal B}\times {\cal A}_q$,
respectively, defined by
$$
\eqalign{\textstyle
\bigl({xy\choose ab}, {xy\brack ab}\bigr)&\hbox{ with }
\textstyle{xy\brack ab}=  {yx\choose ba} + {yx\choose ab} -
{xy\choose ba}
\kern1.5cm (x>y,\, a>b);\cr
\textstyle\bigl({xy\choose aa},{xy\brack aa}\bigr)
&\hbox{ with }\textstyle {xy\brack aa}= {yx\choose aa}
\kern3.66cm (x>y,\; {\text{all}\ }a).\cr }\leqno(S)
$$
\vskip-5pt
$$
\eqalign{\textstyle
\bigl({xy\choose ab}, {xy\brack ab}_q\bigr)&\hbox{ with }
\textstyle{xy\brack ab}_q=  {yx\choose ba} + q{yx\choose
ab} - q^{-1}{xy\choose ba}
\quad (x>y,\, a>b);\cr
\textstyle\bigl({xy\choose aa},{xy\brack aa}_q\bigr)
&\hbox{ with }\textstyle {xy\brack aa}_q= q{yx\choose
aa}
\kern3cm (x>y,\; {\text{all}\ }a).\cr }\leqno(S_q)
$$
Notice that the equations ${xy\choose
ab}-{xy\brack ab}_q=0$, ${xy\choose aa}-{xy\brack aa}_q=0$
are simple rewritings of the commutation rules of the right
quantum algebra
and that
$(S)$ is deduced from
$(S_q)$ by letting $q=1$.

Let 
$\calI$ (resp.~$\calI_q$) be the two-sided ideal
of~$\calA$ (resp. of~$\calA_q$) generated by the elements
$\gamma-[\gamma]$ (resp. $\gamma-[\gamma]_q$) such
that $(\gamma,[\gamma])\in (S)$ (resp.
$\gamma-[\gamma]_q\in (S_q)$). The quotient algebras
${\cal R}={\cal A}/\calI$ and ${\cal R}_q={\cal A}_q/\calI_q$ are
called the {\it $1$-right quantum algebra} and the {\it
$q$-right quantum algebra}, respectively.

In Section~2 we define a $\setZ$-linear mapping $E\mapsto [E]$
of~$\cal A$ onto the ${\bboard Z}$-module~${\cal A}_{\text
irr}$ of the irreducible expressions, called {\it
reduction}. Using Bergman's ``Diamond Lem\-ma" [\RefBe] this
reduction will serve to obtain a model for the algebra~$\cal
R$, as stated in the next theorem.

\goodbreak
\proclaim{Theorem 1} A set of representatives in~$\cal A$ 
for~$\cal R$ is given
by the ${\bboard Z}$-module~${\cal A}_{\text{irr}}$. The
algebra~$\cal R$ may be identified with the ${\bboard
Z}$-module~${\cal A}_{\text{irr}}$, the multiplication being
given by $E\times F=[E\times F]$ for any two irreducible
expressions $E$, $F$. With this identification ${\cal
B}_{\text{irr}}$ is a basis for~${\cal R}$.
\endproclaim

Four statistics counting various kinds of {\it inversions} will
be needed. If $\alpha=\bw uv=\bw{x_1x_2\ldots
x_n}{a_1a_2\ldots a_n}$ is a biword, let
$$
\eqalignno{
\inv u &=\#\{(i,j) \mid 1\leq i< j\leq n, x_i>x_j \}; \cr
\imv v &=\#\{(i,j) \mid 1\leq i< j\leq n, a_i\geq a_j \}; \cr
\inv^- (\alpha) &=\inv v-\inv u; \cr
\inv^+ (\alpha) &=\imv v+\inv u. \cr
}
$$
The first (resp. second) statistic ``inv" (resp. ``imv") is the usual number
of inversions (resp. of {\it large} inversions) of a word.
Notice that ``$\inv^-$" may be negative.
The weight function~$\phi$ defined for each biword~$\alpha$
by $\phi(\alpha)=q^{\inv^-(\alpha)}\alpha$ can be extended
to all of~${\cal A}_q$ by linearity.
Clearly it is
a  $\setZ[q,q^{-1}]$-module isomorphism
of~${\cal A}_q$ onto itself. The second result of the paper
is stated next.

\proclaim{Theorem 2} The
$\setZ[q,q^{-1}]$-module isomorphism $\phi$ of $\calA_q$ onto
itself
induces a
${\bboard Z}[q,q^{-1}]$-module isomorphism
$\overline \phi$ of
$\calA_q/\calI$
onto $\calA_q/\calI_q$. In particular,~${\cal R}_q$ has the same
basis as~$\cal R$.
\endproclaim

Now, a {\it circuit} is defined to be a biword whose top word
is a rearrangement of the letters of its bottom word.  The
set of all circuits is denoted by~$\calC$. It is clearly a
submonoid of~$\calB$. An expression
$E=\sum_\alpha c(\alpha)\alpha$ is said to be {\it circular}
if  $c(\alpha) =0$ for all $\alpha\not\in\calC$. Clearly, the
sum and the product of two circular expressions is a circular
expression, so that the set of circular expressions in~${\cal
A}$ (resp. in~${\cal A}_q$) is a subalgebra of~${\cal
A}$ (resp. of~${\cal A}_q$), which
will be denoted by 
$\calA^{\text{cir}}$ (resp. by~$\calA_q^{\text{cir}}$).

\proclaim{Theorem 3} The restriction of the 
${\bboard Z}[q,q^{-1}]$-module
isomorphism~$\overline\phi$ of Theorem~$2$ to
$\calA_q^{\text{cir}}/\calI$ is a
${\bboard Z}[q,q^{-1}]$-algebra isomorphism onto
$\calA_q^{\text{cir}}/\calI_q$.
\endproclaim
%
\vskip.1cm

\def\fleche(#1,#2)\dir(#3,#4)\long#5{%
{\leftput(#1,#2){\vector(#3,#4){#5}}}}

$$\hbox{\vbox{\offinterlineskip
\def\Acir{{\cal A}^{\text{cir}}_q}
\medskip
\centerput(0,0){$\Acir$}
\fleche(8,0)\dir(1,0)\long{17}
\centerput(32,0){$\Acir$}
\centerput(16,2){$\phi$}
\centerput(16,-3){\sevenrm module-iso}
\centerput(-3,-8){\sevenrm can}
\fleche(0,-3)\dir(0,-1)\long{11}
\centerput(0,-18){$\Acir/{\cal I}$}
\fleche(8,-17)\dir(1,0)\long{17}
\centerput(32,-18){$\Acir/{\cal I}_q$}
\centerput(16,-15){$\overline \phi$}
\centerput(16,-20){\sevenrm algebra-iso}
\fleche(32,-3)\dir(0,-1)\long{11}
\centerput(29,-8){\sevenrm can}
\vskip 1.5cm
}\hskip6cm
\vbox{\offinterlineskip
\medskip
\centerput(0,0){${\cal A}_q$}
\fleche(8,0)\dir(1,0)\long{17}
\centerput(32,0){${\cal A}_q$}
\centerput(16,2){$\phi$}
\centerput(16,-3){\sevenrm module-iso}
\centerput(-3,-8){\sevenrm can}
\fleche(0,-3)\dir(0,-1)\long{11}
\centerput(0,-18){${\cal A}_q/{\cal I}$}
\fleche(8,-17)\dir(1,0)\long{17}
\centerput(32,-18){${\cal A}_q/{\cal I}_q$}
\centerput(16,-15){$\overline \phi$}
\centerput(16,-20){\sevenrm module-iso}
\fleche(32,-3)\dir(0,-1)\long{11}
\centerput(29,-8){\sevenrm can}
\centerput(-15,-8){$\lhook\joinrel\longrightarrow$}
\vskip 1.5cm
}}\hskip3cm
$$
\vskip 0.7cm
%

Accordingly, each identity holding in
$\calA_q^{\text{cir}}/\calI$
has an equivalent counterpart in
$\calA_q^{\text{cir}}/\calI_q$.
This is the
``$1=q$" principle. An illustration of this principle is given
by the $q$MM Theorem derived by Garoufalidis et al. ({\it
op. cit.}). Those authors have introduced the
$q$-{\it Fermion} as being the sum
$$
\Ferm(q)
=\sum_{J\subset \setAA}
(-1)^{|J|} \sum_{\sigma\in {\SSym}_J}
(-q)^{-\inv \sigma}
\pmatrice  {\sigma (i_1)&\sigma (i_2)&\cdots&\sigma (i_l)\cr
i_1&i_2&\cdots&i_l\cr},\
$$
where ${\Sym}_J$ is the
permutation group acting on the set~$J=\{i_1<i_2<\cdots <i_l\}$,
and the $q$-{\it Boson} as the sum
$$
\Bos(q)=\sum_w  q^{\inv w}\pmatrice {
\overline w\cr w\cr}
$$
over all words $w$ from the free monoid $\setA^*$
generated by $\setA$,
where $\overline w$ stands for the nondecreasing rearrangement of
the word~$w$. The $q$-Fermion and $q$-Boson belong
to~${\cal A}_q$. Garoufalidis {\it et al.} have
proved ([\RefGLZ],  see also [\RefFH] for another proof)
the following 
identity
$$
\Ferm(q)\times \Bos(q) \equiv 1 \pmod{\calI_q}.
$$
This identity  may {\it a priori\/} be  regarded as
a {\it $q$-version of the MacMahon Master Theorem}, as it
reduces to the classical MacMahon's identity
[\RefMa, p.~93--98], when
$q=1$ and the biletters are supposed to commute.
%
By the ``$1=q$" principle (Theorem 3), we obtain
the following result, which shows that the variable~$q$ is in fact
superfluous.

\proclaim{Corollary 4} The identity
$\Ferm(q)\times \Bos(q)\equiv 1\modIq$
holds
if and only if
$\Ferm(1)\times \Bos(1)\equiv 1\modI$
holds.
\endproclaim

When applying Theorem 1 to the quantum MacMahon Master
Theorem, we obtain the following result, which can be
regarded as a {\it strong quantum MacMahon Master Theorem}.

\proclaim{Corollary 5}
The following identity holds:
$$[\Ferm(1)\times \Bos(1)] = 1.$$
\endproclaim

The proof of Theorem~1, given in Section~2, is based on
Bergman's ``Diamond Lemma" ([\RefBe], Theorem~1.2). It
consists of verifying that the conditions required by the
``Diamond Lemma" hold in the present situation. Theorems~2
and~3 are proved in Section~3 and Corollaries 4 and~5
in the last section.
% >>>

\head 2. The Reduction Process\endhead % <<<
\def\Airr{{\cal A}_{\text{irr}}}
\def\Birr{{\cal B}_{\text{irr}}}

For applying Bergman's ``Diamond Lemma" [\RefBe] we need
have a so-called {\it reduction system} that satisfies two
conditions: (1) the {\it descending chain condition} holds;
(2) its {\it ambiguities are resolvable}. Those terms will be
explained shortly. Let ${\bboard Z}\langle{\cal B}\rangle$ be
the subalgebra of~$\cal A$ of all
sums $\sum_\alpha c(\alpha)\alpha$ $(\alpha\in {\cal B})$,
where only a finite number of the $c(\alpha)$'s are
non-zero. The elements of ${\bboard Z}\langle{\cal
B}\rangle$ will be called {\it finite} expressions.
The reduction system for ${\bboard
Z}\langle{\cal B}\rangle$ is simply the set~$(S)$ of pairs
$(\alpha,[\alpha])\in {\cal B}\times {\bboard
Z}\langle{\cal B}\rangle$, already
described in section~1. By means of this reduction system we
introduce the {\it reduction} itself as being the mapping
$E\mapsto [E]$ of
${\bboard
Z}\langle{\cal B}\rangle$ onto the set ${\bboard
Z}\langle\Birr\rangle$ of the {\it finite}
irreducible expressions, defined by the following axioms:

(C1) The reduction is linear, i.e. for $E_1, E_2\in{\bboard
Z}\langle{\cal B}\rangle$,
$$[c_1 E_1+c _2 E_2]=c_1 [E_1]+c_ 2[E_2].$$

(C2) 
$[E]=E$ for every $E\in{\bboard
Z}\langle\Birr\rangle$.
\smallskip

(C3) For $\bw{xy}{ab}\not\in\Birr$, i.e. $x>y$ and $a\geq
b$, then
$$
\leqalignno{
\textstyle  {xy\brack ab} &=
\textstyle  {yx\choose ba} + {yx\choose ab} - {xy\choose
ba}, \hbox{\quad \rm if
$a>b$;}
&\hbox{\qquad\rm (C3.1)}\cr
  \textstyle{xy\brack aa} &=
 \textstyle {yx\choose aa},\hfill \hbox{\quad\rm if $a=b$.}
&\hbox{\qquad\rm (C3.2)}\cr
}
$$

(C4) Let $\alpha\not\in \Birr$ be a reducible biword.
For each factorization
$\alpha=\beta\bw{xy}{ab}\gamma$, where
$x,y,a,b\in \setA$ and $\beta\bw{x}{a}\in\Birr$
and $\gamma\in \calB$ we have
$$
[\alpha]=\bigl[\beta\times \sbw{xy}{ab}\times \gamma\bigr].
$$

Although the reduction is recursively defined, it is
well defined. Every time Condition (C3) is applied,
the running biword $\alpha$ is transformed into either three
new biwords (C3.1), or a new biword (C3.2). The important
property is the fact that the statistic $\inv^+$ of each of
the new biwords is {\it strictly less} than $\inv^+(\alpha)$.
Thus, after {\it finitely} many successive applications of (C3),
an irreducible expression is derived. When the
biword~$\alpha$ has more than one double descent,
Condition (C4) says that Condition (C3) must be applied at
the first double descent position. Consequently, the final
irreducible expression is unique.

\goodbreak
There are several other ways to map each expression
onto an irreducible expression, using relations (C3.1)
and~(C3.2). The reduction defined above is only one of those
mappings. The important feature is the fact such a mapping
involves {\it finitely} many applications of relations~(C3.1)
and~(C3.2). Following Bergman we say that Condition~(1)
({\it the descending chain condition}) holds for the pair
$({\bboard
Z}\langle{\cal B}\rangle,S)$.

Now an expression~$E$ is said to be
{\it reduction-unique under~$S$} if the irreducible
expression derived from~$E$ does not depend on {\it where}
the applications of (C3.1) and (C3.2) take place. More formally,
each expression  is reduction-unique
under~$S$ if for every biword~$\alpha$ and every
factorization
$\alpha=\beta\alpha'\gamma$ $(\beta, \alpha',\gamma\in
{\cal B})$ we have
$$
[\alpha]=[\beta[\alpha']\gamma].\kern2cm
\leqno\hbox{(Reduction-unique)}
$$

Now examine the second condition required by the ``Diamond
Lemma." There is an {\it
ambiguity} in~$S$ if there are two pairs
$(\alpha,[\alpha])$ and
$(\alpha',[\alpha'])$ in~$S$ such that
$\alpha=\beta\gamma$,
$\alpha'=\gamma\delta$ for some nonempty biwords
$\beta,\gamma,\delta\in {\cal B}$. This ambiguity is said to
be {\it resolvable} if $[[\alpha]\delta]=[\beta[\alpha']]$, i.e.
$[[\beta\gamma]\delta]=[\beta[\gamma\delta]]$. In our
case this means that $\beta={x\choose a}$,
$\gamma={y\choose b}$, $\delta={z\choose c}$ with $x>y>z$
and $a\ge b\ge c$. Using the first three integers instead of
the letters $x,y,z,a,b,c$ there are four cases to be studied:
\smallskip

(i) $\beta={3\choose 3}$, $\gamma={2\choose 2}$,
$\delta ={1\choose 1}$;\qquad

(ii) $\beta={3\choose 2}$, $\gamma={2\choose 2}$,
$\delta ={1\choose 1}$;\qquad

(iii) $\beta={3\choose 2}$, $\gamma={2\choose 1}$,
$\delta ={1\choose 1}$;\quad

(iv) $\beta={3\choose 1}$, $\gamma={2\choose 1}$,
$\delta ={1\choose 1}$.
\bigskip

Accordingly, the ambiguities in~$S$ are {\it resolvable} if
the following four identities hold:
$$\leqalignno{%\noalign{\vskip-3pt}
\textstyle [{32\brack 32}{1\choose 1}]
&=\textstyle[{3\choose 3}{21\brack 21}];&(2.1)\cr
\textstyle [{32\brack 22}{1\choose 1}]
&=\textstyle[{3\choose 2}{21\brack 21}];&(2.2)\cr
\textstyle [{32\brack 21}{1\choose 1}]
&=\textstyle[{3\choose 2}{21\brack 11}];&(2.3)\cr
\textstyle [{32\brack 11}{1\choose 1}]
&=\textstyle[{3\choose 1}{21\brack 11}].&(2.4)\cr
}
$$
Let us prove (2.1), the other three identities 
being handled in a similar manner.
\goodbreak
{\it Proof} of (2.1).\quad
For an easy reading of the coming calculations we have added
subscripts $A$, $B$, \dots~, $J$ to certain brackets, which
should help spot the subscripted brackets in the various
equations. The left-hand side is evaluated as follows:
$$
\eqalignno{  
\bww321321   &= \bww231231_A
+\bww231321_B -\bww321231_C;\cr
\bww231231_A &= \wbw231231
= \wbw213213_D +\wbw213231_I -\wbw231213_J;\cr
\bww231321_B &= \wbw231321
= \wbw213312_E +\wbw213321_F -\wbw231312;\cr
-\bww321231_C &= -\wbw321231
= -\wbw312213_G -\wbw312231 +\wbw321213_H;\cr
\wbw213213_D &= \bww213213
= \bww123123 +\bww123213
-\bww213123;\cr
\wbw213312_E &= \bww213312
= \bww123132 +\bww123312 -\bww213132;\cr
\wbw213321_F &= \bww213321
= \bww123231 +\bww123321 -\bww213231_I;\cr
-\wbw312213_G &= -\bww312213
= -\bww132123 -\bww132213 +\bww312123;\cr
\wbw321213_H &= \bww321213
= \bww231123 +\bww231213_J
-\bww321123.\cr 
\noalign{\hbox{The sum of the above nine equalities yields:}}
\bww321321 &=
-\bw{231}{312}-\bw{312}{231}+\bw{123}{123}
+\bw{123}{213}-\bw{213}{123}\cr
&\qquad{}+\bw{123}{132}+\bw{123}{312}-\bw{213}{132}
+\bw{123}{231}+\bw{123}{321}\cr
&\qquad{}-\bw{132}{123}-\bw{132}{213}+\bw{312}{123}
+\bw{231}{123}-\bw{321}{123}.\cr
\noalign{\hbox{As for the right-hand side we have:}}
\wbw321321   &= \wbw312312_A +\wbw312321_B
-\wbw321312_C;\cr
\bww312312_A &= \bww132132_D + \bww132312_I
- \bww312132_J ;\cr
\bww312321_B &= \bww132231_E + \bww132321_F
- \bww312231 ;\cr
-\bww321312_C &= -\bww231132_G- \bww231312
+ \bww321132_H ;\cr
\wbw132132_D &= \wbw123123 + \wbw123132
-\wbw132123 ;\cr
\wbw132231_E &= \wbw123213 + \wbw123231
- \wbw132213   ;\cr
\wbw132321_F &=\wbw123312  +\wbw123321
-\wbw132312_I  ;\cr
-\wbw231132_G &=-\wbw213123  -\wbw213132
+\wbw231123  ;\cr 
\wbw321132_H &=\wbw312123  +\wbw312132_J
-\wbw321123.  \cr 
\noalign{\hbox{The sum of the above nine equalities yields:}}
\wbw321321 &= 
-\bw{312}{231}-\bw{231}{312}+\bw{123}{123}+\bw{123}{132}-\bw{132}{123}\cr
&\qquad {}+\bw{123}{213}+\bw{123}{231}-\bw{132}{213}+\bw{123}{312}+\bw{123}{321}\cr
&\qquad {}-\bw{213}{123}-\bw{213}{132}+\bw{231}{123}+\bw{312}{123}-\bw{321}{123}\cr
&= \bww321321 \ \hbox{(left-hand side)}.\qed\cr
} 
$$

\medskip
Let ${\cal I}'$ be the two-sided ideal of ${\bboard
Z}\langle{\cal B}\rangle$ generated by the elements
$\gamma-[\gamma]$ such that $(\gamma,[\gamma])\in
(S)$ and let ${\cal R}'$ be the quotient ${\bboard
Z}\langle{\cal B}\rangle/{\cal I}'$. The pair $({\bboard Z}\langle{\cal
B}\rangle,S)$ having the
descending chain condition and the ambiguities being
resolvable, Bergman's ``Diamond Lemma" implies the following
theorem.


\proclaim{Theorem 6}
\hskip -4pt A set of representatives in~${\bboard
Z}\langle{\cal B}\rangle$ for~${\cal R}'$ is given
by the ${\bboard Z}$-module~${\bboard Z}\langle\Birr\!\rangle\!$. 
%
The algebra~${\cal R}'$ may be identified with~${\bboard
Z}\langle\Birr\rangle$, the multiplication being
given by $E\times F=[E\times F]$ for any two
finite irreducible expressions $E$, $F$. With this
identification ${\cal B}_{\text{irr}}$ is a basis for~${\cal
R}'$.
\endproclaim

For the proof of Theorem~1 we use the following argument.
For each $n\ge 0$ let ${\cal A}^{(n)}$ be the $n$-th {\it
degree homogeneous subspace} of~$\cal A$ consisting of all
expressions $\sum_\alpha c(\alpha)\alpha$ such that
$\ell(\alpha)=0$ if $\ell(\alpha)\not=n$ ([\RefKa], I.6).
As the starting
alphabet~$\bboard A$ is finite, all expressions
in~${\cal A}^{(n)}$ are {\it finite} sums, so that
${\cal A}^{(n)}\subset {\bboard Z}\langle{\cal B}\rangle$ for
all~$n$. Now, let each expression~$E$ from~$\cal A$ be
written as a sum
$$
E=\sum_{n\ge 0} E^{(n)}\quad
\hbox{with } E^{(n)}\in {\cal A}^{(n)}.
$$
As both ideals $\cal I$ and ${\cal I}'$ are generated by
expressions from the second degree homogeneous
space~${\cal A}^{(2)}$, we have
$E\equiv 0\pmod{{\cal I}}$ if and only if for every
$n\ge 0$ we have $E^{(n)}\equiv 0\pmod{{\cal I}'}$.
In particular,
$[E^{(n)}]$ also belongs to ${\cal A}^{(n)}$. Theorem~1
follows from Theorem~6 by taking the definition
$$
[E]=\sum_{n\ge 0}[ E^{(n)}].
$$

% >>> 

\head 3. The ``$1=q$" principle\endhead % <<<
Let $E$ be an expression in $\calA_q$.
Theorem 2 is equivalent to saying that
the identity $E\in\calI$ holds
if and only if $\phi(E) \in\calI_q$ holds.
First we prove the ``only if" part.
Because $\phi$ is linear, it suffices
to consider all linear generators of $\calI$, which have the following
form:
$$\displaylines{\noalign{\vskip-5pt}
\textstyle E_1=\alpha{rs\choose i\,i}\beta -  \alpha{s\,r\choose
i\,i}\beta\cr
\noalign{\vskip-5pt}
\noalign{\hbox{and}}
\textstyle E_2=\alpha{rs\choose ij}\beta - \alpha{sr\choose ji} \beta-
 \alpha{sr\choose ij}\beta + \alpha{rs\choose ji}\beta,\cr}$$
where $\alpha, \beta$ are biwords and $r$, $s$, $i$, $j$
integers such that $r<s$, $i<j$.
Let $k=\inv^-(\alpha{rs\choose ij}\beta)$,
then
$$\displaylines{\noalign{\vskip -5pt}
\textstyle \inv^-(\alpha{sr\choose ji}\beta)=k,\quad
\inv^-(\alpha{sr\choose ij}\beta)=k-1,\quad
\inv^-(\alpha{rs\choose ji}\beta)=k+1,\cr
\noalign{\hbox{so that}}
\textstyle \phi(E_2)=q^k\Bigl(
\alpha{rs\choose ij}\beta - \alpha{sr\choose ji} \beta-
 q^{-1}\alpha{sr\choose ij}\beta +q \alpha{rs\choose ji}\beta
\Bigr)\in\calI_q.\cr}
$$
In the same way $\phi(E_1)\in\calI_q$.
The ``if" part can be proved in the same manner.\qed
\medskip

For Theorem 3 it suffices to prove the identity
$\phi(EF)=\phi(E)\phi(F)$
for any two circular expressions $E$ and $F$. As $\phi$ is
linear, it suffices to do it when $E=\bw uv$,
$F=\bw {u'}{v'}$ are two circuits. Let $\inv(u,u')$ denote
the number of pairs
$(x,y)$ such that $x$ (resp.~$y$) is a letter of~$u$ (resp.
of~$u'$) and $x>y$. As $\bw {uu'}{vv'}$ is a circuit, we have
$$
\eqalignno{
\inv uu'&=\inv u + \inv u' + \inv(u,u') ; \cr
\inv vv'&=\inv v + \inv v' + \inv(v,v') ; \cr
\inv(u,u')&= \inv(v,v') ; \cr
\noalign{\hbox{so that}}
\inv^- (EF) &= \inv vv' -\inv uu' \cr
&= \inv v + \inv v' -\inv u - \inv u'\cr
&=\inv^-(E)+\inv^-(F). \qed\cr
}
$$
% >>>

\head 4. The quantum MacMahon Master Theorem\endhead %<<<

For proving Corollary 4 we apply Theorem 3
to $\Ferm(1)\times\Bos(1)$.
As $\Ferm(1)$ and $\Bos(1)$ are both circular expressions, the relation
$$
\displaylines{
\Ferm(1)\times \Bos(1)\equiv 1\modI\cr
\noalign{\hbox{is equivalent to}}
\phi(\Ferm(1))\times \phi(\Bos(1))\equiv 1\modIq.\cr
}$$
Finally, it is straightforward to verify
$$\Ferm(q)=\phi(\Ferm(1))
\quad{\text{and}}\quad\Bos(q)=\phi(\Bos(1)).
\qed$$ 

\medskip
Now to prove Corollary~5 we start with Garoufalidis {\it et
al.}'s result (for $q=1$), which says that
$\Ferm(1)\times \Bos(1)\equiv 1\modI$.
But by Theorem~1 we have
$E\equiv F \modI$ if and only if $[E]=[F]$. Hence
$[\Ferm(1)\times \Bos(1)]= [1]=1$.
\qed
%>>>

\head 5. Concluding Remarks\endhead % <<<
It is worth noticing that Rodr\'\i guez and Taft have introduced two explicit
left quantum groups for $r=2$ in [\RefRTI] and [\RefRTII]. As mentioned in the
introduction, the former one has been extended to an arbitrary dimension
$r\geq 2$ by Garoufalidis {\it et al.} [\RefGLZ] and been given an explicit 
basis in the present paper, while the latter one has been recently {\it
modeled after} ${\text{SL}}_q(r)$ by Lauve and Taft [\RefLT] also for
each $r\geq 2$.

We should like to thank Doron Zeilberger and Stavros Garoufalidis for
several fruitful discussions. We are
grateful to Christian Kassel, who gave us the references to
the book by Parshall and Wang [\RefPW], the two papers by
Rodr\'\i guez and Taft [\RefRTI, \RefRTII] and the fundamental
paper by Bergman [\RefBe]. Finally, we have greatly benefited
from Jean-Pierre Jouanolou's ever-lasting mathematical
expertise. 

Since the paper has been submitted for publication, several works
about the quantum MacMahon Master Theorem have been completed. 
Hai and Lorenz [\RefHL] have derived the identity using Koszul complex 
techniques.
Konvalinka and Pak [\RefKP] have worked out a several basis 
($q_{ij}$)-analogue of the quantum MacMahon Master Theorem and extended the 
``$1=q$" principle developed in our paper to a ``$1=q_{ij}$" case.
Etingof and Pak [\RefEP] have derived an extension taking up again
the Koszul duality to obtain a new identity having several 
enumerative applications.

\bigskip
{\it Acknowledgements}. The authors should like to thank the two
referees for their careful readings and their knowledgeable remarks.
 
% >>>

% REFERENCES <<<
% \vfill\eject
% \vglue 1.cm

\refstyle{C}
\Refs


\ref\key \RefBe
\by George M. Bergman
\paper The Diamond Lemma for Ring Theory
\jour Adv. Math.
\vol 29
\yr 1978
\pages 178--218
\endref

\ref\key \RefEP
\by Pavel Etingof and Igor Pak
\paper An algebraic extension of the MacMahon Master Theorem 
\jour Proc. Amer. Math. Soc. 
\yr to appear 
\endref

\ref\key \RefFH
\by Dominique Foata and Guo-Niu Han
\paper A new proof of the
Garoufalidis-L\^e-Zeilberger Quantum MacMahon Master
Theorem
\jour J. of Algebra
\vol 307
\yr 2007
\pages 424-431
\endref

\ref\key \RefGLZ
\by S. Garoufalidis, T. TQ L\^e, D. Zeilberger
\paper The quantum MacMahon Master Theorem
\jour Proc. Natl. Acad. of Sci. USA
\vol 103
\yr 2006
\pages 13928-13931
\endref

\ref\key \RefHL
\by Phung Ho Hai and Martin Lorenz
\paper Koszul algebras and the quantum MacMahon Master Theorem
\jour Bull. London Math. Soc. 
\yr to appear 
\endref

\ref\key \RefKa
\by C. Kassel
\book Quantum groups
\publ Graduate texts in math., vol.
{\bf 155}, Springer-Verlag, New York
\yr 1995
\endref

\ref\key \RefKP
\by Matjaz Konvalinka and Igor Pak
\paper Non-commutative extensions of the MacMahon Master Theorem 
\jour Adv. in Math. 
\yr to appear 
\endref

\ref\key \RefLT
\by A. Lauve and E.J. Taft
\paper A class of left quantum groups 
modeled after ${\text{SL}}_q(r)$
\jour J. of Pure and Applied Algebra
\yr 2007
\vol 208
\pages 797-803
\endref

\ref\key \RefLoI
\by M. Lothaire
\book Combinatorics on
Words
\publ Addison-Wesley, London, (Encyclopedia
of Math. and its Appl., {\bf 17})
\yr 1983
\endref

\ref \key \RefLoII
\by M. Lothaire
\book Algebraic Combinatorics on Words
\publ Cambridge Univ. Press, (Encyclopedia of Math. and its Appl.,
{\bf 90})
\yr 2002
\endref

\ref\key \RefMa
\by P. A. MacMahon
\book Combinatory Analysis, $1$
\publ Cambridge Univ. Press, (reprinted by
Chelsea Publ. Co., New York, {1960}) % HAN oldstyle TODO
\yr 1915
\endref

\ref\key \RefPW
\by B. Parshall, J.-P. Wang
\book Quantum linear groups
\publ Memoirs Amer. Math. Soc. {\bf 89} 
\yr 1991
\endref

\ref\key \RefRTI
\by Suemi Rodr\'\i guez-Romo, Earl Taft
\paper Some
quantum-like Hopf algebras which remain noncommutative
when $q=1$
\jour Lett. Math. Phys.
\vol 61
\yr 2002
\pages 41--50
\endref

\ref\key \RefRTII
\by Suemi Rodr\'\i guez-Romo, Earl Taft
\paper A left
quantum group
\jour J. Algebra
\vol 286
\yr 2005
\pages 154--160
\endref


\endRefs

\enddocument
% >>>


% vim: fmr=<<<,>>> foldmethod=marker
% vim: set sw=2: set ts=2: set cindent
