The SlugMath Wiki is under heavy development!

From SlugmathWiki

Title	2D hop and skip
Purpose	Introduce the reduction algorithm for two by two integer matrices.

Each student in the class is paired with a partner (or triple). The instructions of the activity are as follows:

• This game is played on a grid, i.e., $\ZZ^2$. You begin at $(0,0)$.
• You are allowed to move along the grid in two ways:
  • You can "hop" by moving along the vector $(7,11)$, i.e., moving $7$ units right and $11$ units up. You can also "hop backwards" by moving $7$ units left and $11$ units down.
  • You can "skip" by moving along the vector $(5,8)$, i.e., moving $5$ units right and $8$ units up. You can also "skip backwards" by moving $5$ units left and $8$ units down.
• The object of the game is to reach both points $(1,0)$ and $(0,1)$, by hopping and skipping from the origin.

Students are given a few minutes to work on this game, without interruption and without shouting out the answer!

Discussion

After playing the game for a few minutes, students are invited to discuss how they solved it. In particular, the following items should be discussed:

• Can the game be won?
• How do "compound moves" (call them "jumps" or "leaps", for example) help to solve the game?
• What solutions were found? How many hops and how many skips did it take?
• Is there a unique way to win the game?

Transition to the Reduction algorithm

One may play this game, by reducing the $x$ coordinate first. We begin with the hop and skip:

• $H = (7,11)$ and $S = (5,8)$.
• To reduce the $x$ coordinate, define a jump to be $J = H - S = (2,3)$.
• Now, consider the pair of moves $S = (5,8)$ and $J = (2,3)$.
• Again, one may reduce the $x$ coordinate, by defining a "leap" by $L = S - 2 J = (1,2)$.
• Now, consider the pair of moves $J = (2,3)$ and $L = (1,2)$.
• Define a "bound" by $B = J - L = (1,1)$.
• Define a "step" by $L - B = (0,1)$. This was one of our goals.
• Observe that $(1,1) - (0,1) = (1,0)$; this was another one of our goals.

The determinant

Suppose that $(a,b)$ and $(c,d)$ is a "pair of moves", i.e., a pair of vectors in $\ZZ^2$. The determinant is defined to be $\Delta = ad - bc$. The crucial properties of the determinant are the following:

• If we switch $(a,b)$ and $(c,d)$, the determinant changes only in sign:

$$cb - ad = - (ad - bc).$$

• If we replace $(a,b)$ by $(a \pm c, b \pm d)$, the determinant does not change:

$$(a \pm c) d - (b \pm d) c = (ad - bc) \pm cd \mp cd = ad - bc.$$

This "reduction via compound moves" may be formalized as follows:

1. Begin with two vectors $U = (a,b)$ and $V = (c,d)$ in $\ZZ^2$.
2. Assume that $ad - bc = \pm 1$. This implies that $GCD(a,c) = 1$.
3. Switching $U$ and $V$ in sign, and with eachother, if necessary, so that $a \geq c \geq 0$.
4. If $a = c$, then $a = 1$ and $c = 1$, since $GCD(a,c) = 1$. In this case, go to step 7.
5. If $a > c$, replace the pair $U,V$ with the pair $U - V, V$.
6. Return to step 3. Observe that the determinant does not change (up to sign) after this replacement.
7. If $a = 1$ and $c = 1$, the subtract $U$ from $V$.
8. This yields compound moves of the form $(1,b)$ and $(0,d)$. $d = \pm 1$, by the determinant condition.
9. Repeatedly subtracting $(0,1)$ from $(1,b)$ yields $(1,0)$.