1
$\begingroup$

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?

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

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.

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy