$AB = AC$ implies $B = C$ for all $B$ and $C$ implies A invertible without proof by contradiction. So the statement is: Let $A,B,C$ be $n \times n$ matrices. If for all $B$ and $C$ $$\underbrace{AB = AC \Rightarrow B = C}_{\mathcal{P}_1},$$ then $$\underbrace{A \text{ is invertible}.}_{\mathcal{P}_2}$$ So I managed to show that if $\mathcal{P}_1$ and $\neg \mathcal{P}_2$ then $\mathcal{P}_1$ does not hold, hence a contradiction (this has already been featured on math.stackexchange). Is there a proof for $\mathcal{P}_1 \Rightarrow \mathcal{P}_2$ that does not make use of a proof by contradiction?
 A: $$AB = AC \implies B = C$$
$$AB = A0 = 0\implies B = 0$$
$$\ker A = \{0\}$$
$$A \text{ injective}$$
$$A \text{ bijective because the dim of space is finite.}$$
EDIT about second line $\implies$ third line: take $B$ = arbitrary column vector, column vector of zeros, column vector of zeros...
A: The map $X \mapsto AX$ is linear and by assumption injective. By the rank nullity theorem, it follows that the image $\{AX : X \in V\}$ of this map has full rank. Therefore, we have $\{AX : X \in V\} = V \ni I$, so for some $X \in V$ we have $AX = I$ and $A$ is invertible.
A: Sure.  Suppose that $AB = AC \implies B = C$.  Fix a non-zero vector $e$, and consider an arbitrary vector $x$.  We have
$$
A(xe^T) = A(0) \implies xe^T = 0
$$
However, $Axe^T = (Ax)e^T$.  So, the above allows us to deduce that $Ax = 0 \implies x = 0$.  So, $A$ has a trivial nullspace.  So, $A$ is invertible.
A: You can prove the contrapositive with relative ease. To prove the contrapositive, we assume that $A$ is not invertible. Now we must show that there exist $B \neq C$ such that $AB = AC$.
Since $A$ is not invertible, there is a non-zero vector $v$ such that $Av = 0$. Let $B = vv^{T}$ and $C = 0 $. Then $$0 = AC$$ and $$0 = (Av) = (Av)v^T = AB.$$
