# $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?

• Don't you mean to include "for all $B$ and $C$" in the statement you call $\mathcal P_1$? – hmakholm left over Monica Dec 14 '16 at 14:31
• you are right. my apologies. – user394255 Dec 14 '16 at 14:34

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.

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.

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

• How do you go from the second line to the third? – Ben Grossmann Dec 14 '16 at 14:30
• @Omnomnomnom, the columns of AB are the image under $A$ of the columns of $B$. – Martín-Blas Pérez Pinilla Dec 14 '16 at 14:32
• @Omnomnomnom: Let $B$ range over column matrices in particular? – hmakholm left over Monica Dec 14 '16 at 14:32
• @HenningMakholm but $B$ is said to be an $n \times n$ matrix in the question – Ben Grossmann Dec 14 '16 at 14:33
• @Martín-BlasPérezPinilla that statement amounts to a non-trivial observation, I think – Ben Grossmann Dec 14 '16 at 14:34

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

• "Proving a contrapositive" is almost the same as a proof by contradiction. – Mees de Vries Dec 14 '16 at 14:30