Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.
share|cite|improve this question
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
up vote 1 down vote accepted

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.