$AB = AC$ implies $B = C$ for all $B$ and $C$ implies A invertible without proof by contradiction.

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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