Solutions to Homework 8 for MATH 128A.

MATH 128A: Homework 8 Solutions

In this homework, we study the following incidence geometry \(\mathcal M_{\mathbb Z^2}\). The points are elements of \(\mathbb Z^2\), i.e. ordered pairs \((k,\ell )\), where \(k,\ell \in \mathbb Z\). The lines are the horizontal and vertical edges

\[ \{(k,\ell ),(k+1,\ell )\} \qquad \text {and}\qquad \{(k,\ell ),(k,\ell +1)\}, \]

where \(k,\ell \in \mathbb Z\). Two points are called adjacent if they lie on one common line.

(40 points) Examples of transformations of the square grid.
(a)
(7 points) For \((a,b)\in \mathbb Z^2\), define \(T_{(a,b)}:\mathbb Z^2\to \mathbb Z^2\) by
\[ T_{(a,b)}(k,\ell )=(k+a,\ell +b). \]
Show that \(T_{(a,b)}\) is a transformation of \(\mathcal M_{\mathbb Z^2}\).
(b)
(7 points) Show that the inverse of a translation is a translation. More precisely, show that
\[ T_{(a,b)}^{-1}=T_{(-a,-b)}. \]
(c)
(7 points) Define
\[ R_x(k,\ell )=(-k,\ell ), \qquad R_y(k,\ell )=(k,-\ell ). \]
Show that \(R_x\) and \(R_y\) are transformations of \(\mathcal M_{\mathbb Z^2}\).
(d)
(6 points) Show that each of the transformations
\[ \operatorname {id},\qquad R_x,\qquad R_y,\qquad R_x\circ R_y \]
is its own inverse.
(e)
(7 points) Define \(S(k,\ell )=(\ell ,k)\). Show that \(S\) is a transformation of \(\mathcal M_{\mathbb Z^2}\).
(f)
(6 points) Show that \(S\) is its own inverse, i.e.
\[ S^{-1}=S. \]
Solution:

(a) First, \(T_{(a,b)}\) is a bijection. Indeed, for every \((k,\ell )\in \mathbb Z^2\),

\[ T_{(-a,-b)}(T_{(a,b)}(k,\ell )) = T_{(-a,-b)}(k+a,\ell +b) = (k,\ell ), \]
and similarly
\[ T_{(a,b)}(T_{(-a,-b)}(k,\ell )) = T_{(a,b)}(k-a,\ell -b) = (k,\ell ). \]
Therefore \(T_{(a,b)}\) is a bijection, with inverse \(T_{(-a,-b)}\).

We now show that \(T_{(a,b)}\) sends lines to lines. If

\[ L=\{(k,\ell ),(k+1,\ell )\} \]
is a horizontal line, then
\[ T_{(a,b)}(L) = \{(k+a,\ell +b),(k+1+a,\ell +b)\}, \]
which is again a horizontal line. If
\[ L=\{(k,\ell ),(k,\ell +1)\} \]
is a vertical line, then
\[ T_{(a,b)}(L) = \{(k+a,\ell +b),(k+a,\ell +1+b)\}, \]
which is again a vertical line. Therefore \(T_{(a,b)}\) is a transformation.

(b) See previous question.

(c) We first consider \(R_x\). The map \(R_x(k,\ell )=(-k,\ell )\) is a bijection. Indeed, for every \((k,\ell )\in \mathbb Z^2\),

\[ R_x(R_x(k,\ell )) = R_x(-k,\ell ) = (k,\ell ). \]
Therefore \(R_x^{-1}=R_x\), so \(R_x\) is a bijection.

If

\[ L=\{(k,\ell ),(k+1,\ell )\}, \]
then
\[ R_x(L) = \{(-k,\ell ),(-k-1,\ell )\} = \{(-k-1,\ell ),(-k,\ell )\}, \]
which is a horizontal line. If
\[ L=\{(k,\ell ),(k,\ell +1)\}, \]
then
\[ R_x(L) = \{(-k,\ell ),(-k,\ell +1)\}, \]
which is a vertical line. Therefore \(R_x\) is a transformation.

Similarly, \(R_y(k,\ell )=(k,-\ell )\) is a bijection. It sends horizontal lines to horizontal lines and vertical lines to vertical lines:

\[ \{(k,\ell ),(k+1,\ell )\} \longmapsto \{(k,-\ell ),(k+1,-\ell )\}, \]
and
\[ \{(k,\ell ),(k,\ell +1)\} \longmapsto \{(k,-\ell ),(k,-\ell -1)\}. \]
Therefore \(R_y\) is also a transformation.

(d) See previous question.

(e) The map

\[ S(k,\ell )=(\ell ,k) \]
is a bijection. Indeed, for every \((k,\ell )\in \mathbb Z^2\),
\[ S(S(k,\ell )) = S(\ell ,k) = (k,\ell ). \]
Therefore \(S^{-1}=S\), so \(S\) is a bijection.

If

\[ L=\{(k,\ell ),(k+1,\ell )\} \]
is horizontal, then
\[ S(L)=\{(\ell ,k),(\ell ,k+1)\}, \]
which is vertical. If
\[ L=\{(k,\ell ),(k,\ell +1)\} \]
is vertical, then
\[ S(L)=\{(\ell ,k),(\ell +1,k)\}, \]
which is horizontal. Hence \(S\) sends lines to lines. Therefore \(S\) is a transformation.

(f) See previous question.

(35 points) Normalizing a transformation.

Let \(F\) be a transformation of \(\mathcal M_{\mathbb Z^2}\).

(a)
(7 points) Let \(p\in \mathbb Z^2\). Show that \(F\) sends the four points adjacent to \(p\) to the four points adjacent to \(F(p)\).
(b)
(7 points) Show that, by composing \(F\) on the left with a translation, we may assume that
\[ F(0,0)=(0,0). \]
(c)
(7 points) Now assume that \(F(0,0)=(0,0)\). Show that \(F(1,0)\) must be one of
\[ (1,0),\quad (-1,0),\quad (0,1),\quad (0,-1). \]
(d)
(7 points) Show that, by composing \(F\) on the left with transformations chosen from
\[ \operatorname {id},\quad R_x,\quad R_y,\quad R_x\circ R_y,\quad S,\quad R_x\circ S,\quad R_y\circ S,\quad R_x\circ R_y\circ S, \]
we may assume that
\[ F(0,0)=(0,0) \qquad \text {and}\qquad F(1,0)=(1,0). \]
(e)
(7 points) Now assume that \(F(0,0)=(0,0)\) and \(F(1,0)=(1,0)\). Show that
\[ F(0,1)=(0,1) \qquad \text {or}\qquad F(0,1)=(0,-1). \]
Then explain why, by composing with \(R_y\) if necessary, we may assume that
\[ F(0,0)=(0,0),\qquad F(1,0)=(1,0),\qquad F(0,1)=(0,1). \]
Solution:

(a) Let \(p\in \mathbb Z^2\). If \(q\) is adjacent to \(p\), then \(\{p,q\}\) is a line. Since \(F\) is a transformation,

\[ F(\{p,q\})=\{F(p),F(q)\} \]
is a line. Therefore \(F(q)\) is adjacent to \(F(p)\).

The point \(p\) has exactly four adjacent points. Since \(F\) is injective, the images of these four points are four distinct adjacent points of \(F(p)\). But \(F(p)\) also has exactly four adjacent points. Therefore \(F\) sends the four points adjacent to \(p\) exactly to the four points adjacent to \(F(p)\).

We will also use the following consequence. If two points \(p,q\) have \(r\) common adjacent points, then \(F(p)\) and \(F(q)\) also have \(r\) common adjacent points. Indeed, by the previous paragraph, \(F\) sends the set of neighbors of \(p\) bijectively to the set of neighbors of \(F(p)\), and similarly for \(q\).

(b) Suppose

\[ F(0,0)=(a,b). \]
Define
\[ G:=T_{(-a,-b)}\circ F. \]
Since translations are transformations and the composition of transformations is a transformation, \(G\) is a transformation. Moreover,
\[ G(0,0) = T_{(-a,-b)}(F(0,0)) = T_{(-a,-b)}(a,b) = (0,0). \]
Thus, by composing \(F\) on the left with a translation, we may assume that
\[ F(0,0)=(0,0). \]

(c) Assume

\[ F(0,0)=(0,0). \]
Since \((1,0)\) is adjacent to \((0,0)\), part (a) implies that \(F(1,0)\) is adjacent to \(F(0,0)=(0,0)\). The four points adjacent to \((0,0)\) are
\[ (1,0),\quad (-1,0),\quad (0,1),\quad (0,-1). \]
Therefore
\[ F(1,0)\in \{(1,0),(-1,0),(0,1),(0,-1)\}. \]

(d) By part (b), after composing on the left with a translation, we may assume that

\[ F(0,0)=(0,0). \]
By part (c),
\[ F(1,0)\in \{(1,0),(-1,0),(0,1),(0,-1)\}. \]
We now compose on the left with one of the listed transformations, all of which fix \((0,0)\), to send \(F(1,0)\) to \((1,0)\).

If \(F(1,0)=(1,0)\), use \(\operatorname {id}\). If \(F(1,0)=(-1,0)\), use \(R_x\). If \(F(1,0)=(0,1)\), use \(S\). If \(F(1,0)=(0,-1)\), use \(R_x\circ S\), since

\[ (R_x\circ S)(0,-1)=R_x(-1,0)=(1,0). \]
Therefore, after composing \(F\) on the left with transformations from the given list, we may assume that
\[ F(0,0)=(0,0) \qquad \text {and}\qquad F(1,0)=(1,0). \]

(e) Assume

\[ F(0,0)=(0,0), \qquad F(1,0)=(1,0). \]
Since \((0,1)\) is adjacent to \((0,0)\), part (a) implies that \(F(0,1)\) is adjacent to \((0,0)\). Hence
\[ F(0,1)\in \{(1,0),(-1,0),(0,1),(0,-1)\}. \]
Since \(F(1,0)=(1,0)\) and \(F\) is injective, we cannot have
\[ F(0,1)=(1,0). \]

We now rule out \(F(0,1)=(-1,0)\). The points \((1,0)\) and \((0,1)\) have two common adjacent points:

\[ (0,0) \qquad \text {and}\qquad (1,1). \]
By part (a), \(F(1,0)\) and \(F(0,1)\) must also have two common adjacent points. But if \(F(0,1)=(-1,0)\), then \(F(1,0)=(1,0)\), and the points \((1,0)\) and \((-1,0)\) have only one common adjacent point, namely \((0,0)\). This is impossible.

Therefore

\[ F(0,1)=(0,1) \qquad \text {or}\qquad F(0,1)=(0,-1). \]
If \(F(0,1)=(0,1)\), we do nothing. If \(F(0,1)=(0,-1)\), we compose on the left with \(R_y\). Since
\[ R_y(0,0)=(0,0), \qquad R_y(1,0)=(1,0), \qquad R_y(0,-1)=(0,1), \]
we may assume
\[ F(0,0)=(0,0), \qquad F(1,0)=(1,0), \qquad F(0,1)=(0,1). \]
(25 points) The normalized transformation fixes part of the grid.

Let \(F\) be a transformation of \(\mathcal M_{\mathbb Z^2}\). Assume that

\[ F(0,0)=(0,0), \qquad F(1,0)=(1,0), \qquad F(0,1)=(0,1). \]
(a)
(8 points) Show that \(F(1,1)=(1,1)\).
(b)
(8 points) Show that \(F(-1,0)=(-1,0)\) and \(F(0,-1)=(0,-1)\).
(c)
(9 points) Show, by induction, that
\[ F(k,0)=(k,0) \]
for every integer \(k\geq 0\).
Solution:

Assume throughout that

\[ F(0,0)=(0,0), \qquad F(1,0)=(1,0), \qquad F(0,1)=(0,1). \]

(a) The point \((1,1)\) is adjacent to both \((1,0)\) and \((0,1)\). Therefore \(F(1,1)\) is adjacent to both

\[ F(1,0)=(1,0) \qquad \text {and}\qquad F(0,1)=(0,1). \]
The common adjacent points of \((1,0)\) and \((0,1)\) are exactly
\[ (0,0) \qquad \text {and}\qquad (1,1). \]
Hence
\[ F(1,1)=(0,0) \qquad \text {or}\qquad F(1,1)=(1,1). \]
Since \(F(0,0)=(0,0)\) and \(F\) is injective, we cannot have \(F(1,1)=(0,0)\). Therefore
\[ F(1,1)=(1,1). \]

(b) By Problem 2(a), \(F\) sends the four neighbors of \((0,0)\) to the four neighbors of \((0,0)\). Since

\[ F(1,0)=(1,0) \qquad \text {and}\qquad F(0,1)=(0,1), \]
the remaining two neighbors must be sent to the remaining two neighbors:
\[ F(\{(-1,0),(0,-1)\})=\{(-1,0),(0,-1)\}. \]
Thus either
\[ F(-1,0)=(-1,0),\quad F(0,-1)=(0,-1), \]
or
\[ F(-1,0)=(0,-1),\quad F(0,-1)=(-1,0). \]

We rule out the second possibility. The points \((1,0)\) and \((0,-1)\) have two common adjacent points:

\[ (0,0) \qquad \text {and}\qquad (1,-1). \]
Therefore their images must also have two common adjacent points. If \(F(0,-1)=(-1,0)\), then the images would be
\[ F(1,0)=(1,0) \qquad \text {and}\qquad F(0,-1)=(-1,0). \]
But \((1,0)\) and \((-1,0)\) have only one common adjacent point, namely \((0,0)\). This is impossible.

Therefore

\[ F(-1,0)=(-1,0) \qquad \text {and}\qquad F(0,-1)=(0,-1). \]

(c) We prove by induction that

\[ F(k,0)=(k,0) \]
for every integer \(k\geq 0\).

The base cases \(k=0\) and \(k=1\) hold by assumption.

Assume that \(n\geq 1\), and suppose that

\[ F(k,0)=(k,0) \]
for every \(0\leq k\leq n\). We prove that
\[ F(n+1,0)=(n+1,0). \]
Since \((n+1,0)\) is adjacent to \((n,0)\), its image \(F(n+1,0)\) is adjacent to
\[ F(n,0)=(n,0). \]
Hence
\[ F(n+1,0)\in \{(n-1,0),(n+1,0),(n,1),(n,-1)\}. \]

The first possibility is impossible, because \(F(n-1,0)=(n-1,0)\) by the induction hypothesis and \(F\) is injective.

We now rule out the possibilities \((n,1)\) and \((n,-1)\). The original points

\[ (n-1,0) \qquad \text {and}\qquad (n+1,0) \]
have exactly one common adjacent point, namely \((n,0)\). Therefore their images must also have exactly one common adjacent point.

If

\[ F(n+1,0)=(n,1), \]
then the two image points
\[ F(n-1,0)=(n-1,0) \qquad \text {and}\qquad F(n+1,0)=(n,1) \]
have two common adjacent points:
\[ (n,0) \qquad \text {and}\qquad (n-1,1). \]
This is impossible.

Similarly, if

\[ F(n+1,0)=(n,-1), \]
then the two image points
\[ (n-1,0) \qquad \text {and}\qquad (n,-1) \]
have two common adjacent points:
\[ (n,0) \qquad \text {and}\qquad (n-1,-1). \]
This is also impossible.

Therefore the only remaining possibility is

\[ F(n+1,0)=(n+1,0). \]
By induction,
\[ F(k,0)=(k,0) \]
for every \(k\geq 0\).