1

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

Gladstone Asder
  • 1,051

2 Answers2

2

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.

Pedro
  • 122,002
1

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.

Charles Boyd
  • 672
  • Did i make any mistake? Because i just want to know if I am doing it right. – Gladstone Asder Nov 07 '12 at 01: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 07 '12 at 01:35
  • There is, in particular, no need to solve a system of equations. That isn't the right approach here. – Charles Boyd Nov 07 '12 at 01:36
  • 1
    @CharlesBoyd Why do you claim that? The approach is spotless. – Pedro Nov 07 '12 at 03: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 07 '12 at 03:19