# Linear surjection proof

1. Apr 16, 2015

### diracdelta

1. The problem statement, all variables and given/known data
Let be linear surjection. Prove that then n>=m.

2. Relevant equations
Definition(surjection):

3. The attempt at a solution
Lets assume opposite, n<=m. If that is the case, then for some y from R^m, there is no belonging x from R^n, what is in contradiction with definition where its said for every y.

Is this ok? If no, why?

Thanks! Domagoj

2. Apr 16, 2015

### Staff: Mentor

The opposite would be n < m.
Why is there no x in Rn for that y in Rm? You need to do more than just say the words.

3. Apr 16, 2015

### diracdelta

Ok.

Can one x map to more then one y?

4. Apr 16, 2015

### Staff: Mentor

A is a linear transformation. Can A(x) map to y1 and y2, where y1 ≠ y2

5. Apr 16, 2015

### diracdelta

No.
Edit; That is actually what I've been trying to say in first post.

6. Apr 16, 2015

### Fredrik

Staff Emeritus
This is a good proof strategy, or at least it will be when you replace "n<=m" with "n<m". But you have to explain how you know that what you're saying in the second sentence is true.

By definition of "map", no. Note that this has nothing to do with surjectivity or even injectivity. It's just the definition of "map" (="function").

7. Apr 16, 2015

### diracdelta

@Fredrik
Ok.
Lets assume the opposite, n<m. I know from definition of surjection that for every y there has to be x such as f(x)=y.
But since n<m, there exists some element y that wont be mapped. Which is contradiction and not surjective.

8. Apr 16, 2015

### Staff: Mentor

Again (as in my post #2) why? Why does it follow that if n < m, then some x element won't be paired with that y?

9. Apr 19, 2015

### diracdelta

I would say it like this;
If n <m that means that dimension of domain is lower then dimension of codomain. But definition of surjection , Image of (domain) = codomain.
but dim (domain) = n < dim(codomain)=m, -> contradiction

10. Apr 20, 2015

### Fredrik

Staff Emeritus
It's true that the statements $n<m$ and $A(\mathbb R^n)=\mathbb R^m$ can't both be true, but you can't just say this. You have to prove it.