# Prove that the following function is onto and one-to-one

$$f:\Bbb Z^2\to\Bbb Z^2:{n\brack m}\mapsto\begin{bmatrix}3&2\\4&3\end{bmatrix}{n\brack m}$$

it is onto because:

\left\{\begin{align*}&m = 9d - 4s\\ &n = 6d + 3s\end{align*}\right. (after solving the system of equations)

onto because m and n are integers

one-to-one because:

\left\{\begin{align*}&3n + 2m = 3p + 2q\\ &4n + 3m = 4p + 3q\end{align*}\right.

which is equal to $L_2 - L_1$ and $L_1 - 2L_2$:

\left\{\begin{align*}&n = p\\ &n + m = p + q\end{align*}\right.

equal to:

\left\{\begin{align*}&n = p\\ &m = q\end{align*}\right.

I have to solve the system of equations for both (to prove it is onto and one-to-one) if I understood correctly?

-
Still not taking up my suggestion about learning how to format mathematics? f(n/m) = (3 4) (4 3) (n/m) is unreadable. –  Gerry Myerson Nov 7 '12 at 0:51
i don't know how to write the matrix bracket –  Gladstone Asder Nov 7 '12 at 0:52
Then learn how --- I suggested links --- or write it out in words. –  Gerry Myerson Nov 7 '12 at 0:53
ok i just fixed it –  Gladstone Asder Nov 7 '12 at 0:54
Still unreadable. z^2 > z^2 ??? –  Gerry Myerson Nov 7 '12 at 0:54

Yours can be interpreted as linear transformation/homomorphism, from $\Bbb Z^2$ to itself.

Injectivity and surjectivity then boil down to the matrix being invertible or not, and the value of it's determinant. We have $$\begin{vmatrix}3&2\\4&3\end{vmatrix}=3\cdot 3 -4\cdot 2 =9-8=1$$

Since the determinant is $1$, the function is invertible (which means it is one-one and onto), and it's inverse matrix $$\left(\begin{matrix}3&-4\\-2&3\end{matrix}\right)$$ will also send integers to integers, which is indeed what we want.

-
oh we can just do that? but did i make any mistake? –  Gladstone Asder Nov 7 '12 at 1:23
@GladstoneAsder As far as I can tell, your solution is OK. –  Pedro Tamaroff Nov 7 '12 at 3:05

Let $f \colon X \to Y$, then:

1. $f$ is onto (surjective) if and only if for every $y \in Y$, there exists some $x \in X$ such that $y = f(x)$.

2. $f$ is one-to-one (injective) if and only if $$f(a) \neq f(b) \implies a \neq b$$ for every $a, b \in X$

Claim: $f$ is surjective.

Proof:

Observe that we have a matrix with $\textrm{Det}(M)=1$, then we know (from linear algebra) $M$ is invertible.

Let $$M = \begin{pmatrix} 3 & 2 \\ 4 & 3 \end{pmatrix}.$$

Then $$M^{-1} = \begin{pmatrix} 3 & -2 \\ -4 & 3 \end{pmatrix}.$$

Since $f(n,m) = (3n + 2m, 4n + 3m)$ and $f^{-1}(r,s) = (3r -2s, -4r + 3s)$, we know the map is surjective since for every $(r,s) \in \mathbb{Z}^{2}$, it is always true that $(r,s) = f(f^{-1}(r,s))$.

Lemma: Let $f \colon X \to Y$ such that $f^{-1}(f(x)) = x$ for every $x \in X$, then $f$ is injective.

Claim: $f$ is injective.

Proof:

Follows immediately from the above lemma, since it is easily verified that $f$ is left-invertible.

-
Did i make any mistake? Because i just want to know if I am doing it right. –  Gladstone Asder Nov 7 '12 at 1:03
I can't say if you made a mistake, since I'm not entirely sure where your reasoning was going. But the easiest way to prove this is by making use of the fact that the matrix is invertible (since its determinant is unity) and therefore $f$ is invertible on both right and left and therefore surjective and injective. –  Charles Boyd Nov 7 '12 at 1:35
There is, in particular, no need to solve a system of equations. That isn't the right approach here. –  Charles Boyd Nov 7 '12 at 1:36
@CharlesBoyd Why do you claim that? The approach is spotless. –  Pedro Tamaroff Nov 7 '12 at 3:06
By "not the right approach" I simply mean "not the easiest approach". The proof of $f$ being a bijection follows directly from the matrix $M$ being invertible. –  Charles Boyd Nov 7 '12 at 3:19