1

I've been looking at ways of determining if a functions is one-to-one or onto. I have a clear sense of this when looking at functions in $\mathbb Z \rightarrow \mathbb Z$ or any other one-dimensional explicit function. However, I'm having a hard time doing so when I fall into: $\mathbb Z^2 \rightarrow \mathbb Z$ or perhaps $\mathbb Z^2 \rightarrow \mathbb Z^2$. I'm looking for a clean way of doing this using the definition: $f(a)=f(b) \rightarrow a=b$. For example, if I were to take the determinant of $f(a,b) = (3m+7n,2m+5n)$, I would get 1 and would suggest that the function is in fact 1-1. But how about finding if it is onto?

Dimitri
  • 1,287
  • 1
    If your going to use a linear algebra approach,the dimension of the image will answer your question. If the dimension of the image is the same as the dimension of the target space the linear map is onto. – Wintermute Nov 06 '13 at 21:12
  • In your specific example, why not invert the transformation and check whether it carries $\mathbb{Z}^2$ into itself? In other words, the inverse has integral coefficients, so it's indeed onto. But more general than this? I don't know. – Will Nelson Nov 06 '13 at 21:15
  • @mtiano what about in the case of $\mathbb Z^2 \rightarrow \mathbb Z$. In the case of $f(a,b) = 2a+3b$, how would one approach this? I don't see a way of using linear algebra to solve this. – Dimitri Nov 06 '13 at 21:29
  • @mtiano The linear algebra approach only works for vector spaces, not modules, in which Dimitri seems to be interested. – Will Nelson Nov 07 '13 at 17:56
  • I guess there are numerous ways of going about this and finding the more efficient way is what I'm interested in for any given problem. I seem to be confusing a lot of concepts sometimes. – Dimitri Nov 08 '13 at 02:28
  • 1
    Dimitri, don't let a little confusion discourage you. It's happened to all of us. New neural connections are being formed all the time, even when you're frustrated. If you keep at it, one day soon, you'll be amazed how much easier and clearer it all seems. – Will Nelson Nov 08 '13 at 05:49

1 Answers1

1

One could certainly write a lot about methods to prove a map is onto. It very much depends on your domain of interest and there have to be thousands of different tricks out there. I'll only point out that for linear maps $f:\mathbb{Z}^2\to\mathbb{Z}^2$, the map is onto iff its determinant is $\pm 1$. Only in this case will you end up with integer coefficients in the inverse matrix.

Also, if $f:\mathbb{Z}^2\to\mathbb{Z}$ is linear, so $f(x,y) = ax+by$, then $f$ is surjective iff $\mathrm{gcd}(a,b) = 1$. This is a nothing more than a restatement of Bézout's identity.

Will Nelson
  • 5,161
  • If the determinant is 1 then how do we determine if it's one-to-one? The Pivots after reducing? – Dimitri Nov 08 '13 at 03:35
  • If the determinant of the linear map $f:\mathbb{Z}^2\to\mathbb{Z}^2$ is non-zero, it's 1-1, because it's invertible when thought of as $f:\mathbb{R}^2\to\mathbb{R}^2$. It's also onto as $f:\mathbb{R}^2\to\mathbb{R}^2$, but non-zero determinant does not guarantee $f:\mathbb{Z}^2\to\mathbb{Z}^2$ is onto. Why? Because when you invert the matrix, you might end up with non-integer entries. Example: $f(x,y) = (2x, 3y)$. $det(f)=6$, so it's one-to-one, but its inverse has non-integers, so $f:\mathbb{Z}^2\to\mathbb{Z}^2$ is not onto. When $det(f)=\pm 1$, $f:\mathbb{Z}^2\to\mathbb{Z}^2$ is also onto – Will Nelson Nov 08 '13 at 04:07