1
$\begingroup$

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

  • 2
    Still not taking up my suggestion about learning how to format mathematics? f(n/m) = (3 4) (4 3) (n/m) is unreadable.2012-11-07
  • 0
    i don't know how to write the matrix bracket2012-11-07
  • 0
    Then learn how --- I suggested links --- or write it out in words.2012-11-07
  • 0
    ok i just fixed it2012-11-07
  • 0
    Still unreadable. z^2 > z^2 ???2012-11-07
  • 0
    well someone just stepped in2012-11-07
  • 0
    Look at this page: http://kogler.wordpress.com/2008/03/21/latex-multiline-equations-systems-and-matrices/2012-11-07
  • 0
    Gladstone, I *think* that I correctly interpreted your original post, but please check to be sure.2012-11-07
  • 0
    thanks, yeah just fixed the numbers thanks.2012-11-07
  • 0
    There's a section [in this tutorial](http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference) about how to do matrices.2012-11-07

2 Answers 2

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.

  • 0
    oh we can just do that? but did i make any mistake?2012-11-07
  • 0
    @GladstoneAsder As far as I can tell, your solution is OK.2012-11-07
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.

  • 0
    Did i make any mistake? Because i just want to know if I am doing it right.2012-11-07
  • 0
    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.2012-11-07
  • 0
    There is, in particular, no need to solve a system of equations. That isn't the right approach here.2012-11-07
  • 1
    @CharlesBoyd Why do you claim that? The approach is spotless.2012-11-07
  • 0
    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.2012-11-07