Can someone explain, or even prove the lemma? I've thought about it for about 3 hrs but no idea about the lemma.

\begin{align*} R_1 &=\left(\begin{array}{rrrr} -1 & 0 & 0 & 0\\ 2/3 & 1 & 0 & 0\\ 2/3 & 0 & 1 & 0\\ 2/3 & 0 & 0 & 1 \end{array}\right) &\qquad R_2&=\left(\begin{array}{rrrr} 1 & 2/3 & 0 & 0\\ 0 & -1 & 0 & 0\\ 0 & 2/3 & 1 & 0\\ 0 & 2/3 & 0 & 1 \end{array}\right)\\ R_3 &= \left(\begin{array}{rrrr} 1 & 0 & 2/3 & 0\\ 0 & 1 & 2/3 & 0\\ 0 & 0 & -1 & 0\\ 0 & 0 & 2/3 & 1 \end{array}\right), & R_4&=\left(\begin{array}{rrrr} 1 & 0 & 0 & 2/3\\ 0 & 1 & 0 &2/3\\ 0 & 0 & 1 & 2/3\\ 0 & 0 & 0 & -1 \end{array}\right). \end{align*}

Lemma. Let $M_1,M_2,\ldots,M_d$ be a sequence of the matrices $R_i$, where $2/3$ is replaced by $a$. Assume $M_i\neq M_{i+1}$, $i=1,2,\ldots,d-1$. Then each of the sixteen terms in the product matrix $M_1M_2\cdots M_d$ is a polynomial in $a$ with integer coefficients and lead coefficient $1$ or $-1$ (or else the $0$ polynomial). Moreover, if $M_1=R_i$ and $M_d=R_j$, then:

• The entry in the $i$th row and $j$th column of $M_1M_2\cdots M_d$ has degree $d-1$. Other entries in the $i$th row have degree less than $d-1$.
• The other three entries in the $j$th column have degree $d$. The entries not on the $i$th row and not on the $j$th column have degree less than $d$.
-
Have you tried induction? (Start with a matrix whose entries are all polynomials with $a$ with integer coefficients and leading coefficient $1$ or $-1$, etc., and see what happens when you multiply by one of the $R_i$.) – Théophile Mar 20 '12 at 3:43

What happens to any matrix $M$ when you multiply it by $R_j$? It keeps all the elements in columns $k\neq j$ intact, while for each element in column $j$ of $M$ it takes the sum of all other elements in the same row, multiplies it by $a$ and subtract the element.
Having this observation we can easily prove the statement by induction. Indeed, if $d=2$ and $M=R_iR_j$, then $M$ is obtained from $R_i$ by changing one column $j$: $M_{ij}=-a$, $M_{jj}=a^2-1$, and $M_{kj}=a^2+a$ for all other rows $k$. So, we see that $M_{ij}$ has degree $1=d-1$ while all other elements in column $j$ have degree $2=d$. Moreover, all other elements in row $i$ are either $0$ or $1$ (degree less than $1$), and all other elements not in row $i$ and not in column $j$ have degree less than $2=d$. Also, all coefficients are integer, and lead coefficients are either $-1$ or $1$.
So, suppose this is true for $M=M_1...M_d=R_i...R_j$, and we multiply it by $R_k$ where $k\neq j$: $M'=MR_k$. Then, once again, all the columns except column $k$ do not change. Also, note, that the degree of any element in $M$ in row $i$ is at most $d-1<(d+1)-1$, and the degree of any element in any other row is at most $d<d+1$. So, we only need to check column $k$. $M'_{sk}=aM_{sj}+\sum_{l\neq k,j}aM_{sl}-M_{sk}$. $M'_{ik}$ has degree $d$ because $M_{ij}$ has degree $d-1$ while all other elements in the row have degree less than $d-1$. For any other $s$, $M'_{sk}$ has degree $d+1$ because $M_{sj}$ has degree $d$ and all other elements in the row $s$ in $M$ have degree less than $d$. This also shows that the coefficients of polynomials in the new matrix are all integers, and leading coefficients are either $0$ or $1$.