Proving that $A$ is singular iff it's not injective How to prove that a square matrix $A$ is singular if and only if  $x\mapsto Ax$ is not injective?
We define the matrix $A$ to be singular if there doesn't exist matrix $A^{-1}$ such that $AA^{-1}=A^{-1}A=I$. Why does it imply that it can map multiple $x$'s to the same value $Ax$? And please don't use of the theorem that says singular matrices have a zero eigenvalue.
 A: Equivalently, we would like to show $A$ has an inverse if and only if it is injective. (This is the converse of your original equivalence.)
Suppose $A$ has an inverse. Then $Ax = y$ means $A^{-1} Ax = A^{-1}y$ so $x = A^{-1}y$; so the linear map $A$ is injective.
Suppose $A: \mathbb{F}^n \to \mathbb{F}^n$ is (linear and) injective. Let $\{ e_1, \dots, e_n \}$ be a basis for the vector space $\mathbb{F}^n$. I claim that $A$ is surjective; this is enough, because we can define $A^{-1}(e_i)$ to be the vector $v$ such that $A v = e_i$.
Indeed, $A e_1, \dots, A e_n$ are linearly independent (a dependence between them would be of the form $A(\alpha_1 e_1 + \dots + \alpha_n e_n) = 0$, so $\alpha_1 e_1 + \dots + \alpha_n e_n = 0$ by injectivity), and there are $n$ of them, so they span. Therefore they are a basis for $\mathbb{F}^n$.
A: if $A$ is singular, it means there exists at least vector $u$ for which $Au=0$.
Then you take an $x$ such that $Ax=y$ and you can observe that for any scalar $c$, you have $A(x+cu) = Ax + cAu = Ax$. Here, you proved that if $A$ is singular, then $x\mapsto Ax$ is not injective.
Now, if $x\mapsto Ax$ is not injective, it means there is at least an $x$ and a $y$ such that $x\ne y$ for which $Ax = Ay$. So, it means $A(x-y)=0$ and $x-y\ne 0$. So $A$ is singular.
A: Suppose that $A$ is singular. Basically, $A\mathbf{0}=\mathbf{0}$. Thus $\mathbf{0}$ is a root of $A\mathbf{x}=\mathbf{0}$. Since $A$ is singular, there is $\mathbf{y}$ such that $A\mathbf{y}=\mathbf{0}$ and $\mathbf{y}\ne \mathbf{0}$. (See here.)
Now suppose $A$ is not injective. then there is $\mathbf{x}$ and $\mathbf{y}$ such that $A\mathbf{x}=A\mathbf{y}$ and $\mathbf{x}\ne \mathbf{y}$. If $A$ is not singular, then there exists $A^{-1}$. Thus
$$
\mathbf{x}=I\mathbf{x}=(A^{-1}A)\mathbf{x}=A^{-1}(A\mathbf{x})=A^{-1}(A\mathbf{y})=(A^{-1}A)\mathbf{y}=I\mathbf{y}=\mathbf{y},
$$
which is a contradiction.
A: If $x \rightarrow Ax$ is not injective, then there exist two distinct values $x_1$, $x_2$ such that $A x_1 = A x_2$. If $A$ was not singular, then $A^{-1}A x_1 = A^{-1}A x_2$ i.e. $x_1 = x_2$.
This proves by contradiction that if $x\rightarrow A x$ is not injective, $A$ is singular.
I am still looking at the other direction.
A: We can also make everything a little more general. In particular:

Proposition 0. Let $K$ denote a field.
Then for all finite-dimensional $K$-modules $Y$ and $X$ satisfying $Y\stackrel{\mathrm{dim}}{=}X$ , every morphism $f:Y\leftarrow X$ that is at least one of {injective, surjective} is an isomorphism.

Proof sketch. Suppose $f$ is injective. Then we know that $f(X)\stackrel{\mathrm{dim}}{=}X$. Hence $f(X)\stackrel{\mathrm{dim}}{=}Y$ Since $Y$ is finite-dimensional, this implies that $f(X)=Y$. In other words, $f$ is surjective. Hence $f$ is an isomorphism.
Suppose $f$ is surjective. Then we can realize $f$ as a square matrix by choosing a basis for $Y$ and another basis for $X$. This matrix will be full-rank; and, hence, by the invertible matrix theorem, invertible. So $f$ is an isomorphism.
By the way, the theorem under question could reasonably be called the "Pigeonhole principle for linear transforms between finite-dimensional vector spaces" or some variant on that.
