"Logic Problem " from Artin's Algebra This question is from Artin's Algebra:



I wen this way: $A$ is $m\times n$ matrix, if $m<n$ then $A$ does not have left inverse, so we can concentrate on $m\ge n$ case. If we take the case $$\begin{bmatrix}1&0\\0&1\\0&0 \end{bmatrix}\begin{bmatrix}x_1\\x_2\\ \end{bmatrix}=\begin{bmatrix}3\\2\\5 \end{bmatrix}$$ then $\begin{bmatrix}1&0&1\\0&1&1\\ \end{bmatrix}$ is a left inverse of $A=\begin{bmatrix}1&0\\0&1\\0&0 \end{bmatrix}$ and by $X=LB$, we get $\begin{bmatrix}x_1\\x_2 \end{bmatrix}=\begin{bmatrix}8\\7 \end{bmatrix}$, which does not solve the system! Is this kind of problem, the author is talking about? I don't know what does the sequence of steps made above show. 
 A: As Malcolm points out in the comments, the "problem" is that what you've shown is that if there is an $X$ such that $AX = B$, then $X$ must be equal to $LB$.  However, there may be no such $X$, in which case the statement is vacuous.
Suppose now that $A$ has a right inverse $R$.  Letting $X_0 = RB$, then we have
$$
AX_0 = ARB = B
$$
so $X_0$ is a solution to the equation $AX = B$.  Thus in the first case we were able to show that, if a solution exists, it must be unique, and in the second case we showed that a solution exists.
We can explain this phenomenon in terms of injectivity and surjectivity.  Given sets $X$ and $Y$ and a function $f: X \to Y$, $f$ is injective iff $f$ has a left inverse, i.e., a function $\DeclareMathOperator{\img}{img} \DeclareMathOperator{\id}{id} g: \img(f) \to X$ such that $g \circ f = \id_X$, the identity map.  Moreover, this $g$ must be unique: given $y \in \img(f)$, since $f$ is injective there is a unique $x \in X$ with $f(x) = y$, so we are forced to set $g(y) = x$.  Given $y \in Y$, if the equation $f(x) = y$ has a solution, then that solution must be unique, since just as above we must have $x = g(y)$.  However, $f$ need not be surjective, so it's possible that a given choice of $y$ will have no solutions.
Similarly, $f$ is surjective iff $f$ has a right inverse, i.e., a function $h: Y \to X$ such that $f \circ h = \id_Y$.  Now the equation $f(x) = y$ has a solution for every choice of $y \in Y$: given $y \in Y$, take $x = h(y)$.  However, now the solution need not be unique, since there could be many choices for the definition of the right inverse $h$.  Given $y \in Y$, one can take any $x$ in the preimage $f^{-1}(y)$ and set $h(y) = x$.
A: Suppose $A$ is an $m\times n$ matrix with $m\geq n$. If $L$ is a right inverse in addition to already being a left inverse of $A$, then $A$ serves as a left inverse to $L$, a $n\times m$ matrix with $n\leq m$. The only way this can happen is if $n=m$, so $A$ is square.
Alternatively, if $L$ is also a right inverse, the equation $Ax=b$ always has a solution as outlined in the problem formulation. In particular the linear map $A: \mathbb{R}^n\rightarrow \mathbb{R}^m$ is surjective. Since $m\geq n$, this is only possible if $m=n$.
This can be viewed as a consequence of the fact that if $m>n$ the map $L : \mathbb{R}^m\rightarrow \mathbb{R}^n$ can not be injective, which prohibits the implication $LAx=Lb\Rightarrow Ax=b$, as any two elements of $\mathbb{R}^m$ that differ by an element in the kernel of $L$ become identified.
