Are there non-square matrices that are both left and right invertible? I am aware that invertible square matrices are left invertible and right invertible, and that the left and right inverses are equal. However, I was wondering whether exists a non square $m\times n$ matrice $A$, so that exist both:


*

*An $n\times m$ matrice $B$ so that $AB = I_m$

*An $n\times m$ matrice $C$ so that $CA = I_n$ 


I just couldn't think of an example nor of a proof that these two conditions provide that A is necessarily square.
 A: Suppose you have an $n\times m$ matrix $A$ with $n\neq m$.
If $n<m$ then  $rank(BA)\leq rank(A)\leq n$ and so $BA\neq I_m$ for all $B$.
If $m<n$ then $rank(AB)\leq rank(A)\leq m$ and so $AB\neq I_n$ for all $B$.
A: This question is a variation on the simpler question of whether $A \in \mathbb{R}^{m \times n}$ has a two-sided inverse, in the sense described in this answer, ie. a $B \in \mathbb{R}^{n \times m}$ satisfying $AB = I_{m}$ and $BA = I_{n}$.
Here we are asking if $A$ has both a right inverse $B \in \mathbb{R}^{n \times m}$ and a left inverse $C \in \mathbb{R}^{n \times m}$, without necessarily requiring $B$ and $C$ to be the same matrix (note $n \times m$ is the only possible dimension of any type of inverse of $A$ because any identity matrix must be square).
To show that this would require $m = n$ we can first use the following result from basic set theory :
Theorem 1
Given $f : A \rightarrow B$, if $\,\exists\;g, h : B \rightarrow A$ with $fg = i_{B}$ and $hf = i_{A}$ (ie $g, h$ are respectively right/left inverses of $f$), then $f$ is bijective and $g = h = f^{-1}$.
Proof
$b \in B \Rightarrow f(g(b)) = b \therefore f$ surjective. $f(a_{1}) = f(a_{2}) \Rightarrow (hf)(a_{1}) = (hf)(a_{2}) \Rightarrow a_{1} = a_{2} \therefore f$ injective, $\therefore f$ bijective, so $f^{-1}$ is well-defined as a function from $B \rightarrow A$.  Then $g = f^{-1}$, since $b \in B \Rightarrow (fg)(b) = b \Rightarrow (f^{-1}fg)(b) = f^{-1}(b) \Rightarrow g(b) = f^{-1}(b)$.  And $h = f^{-1}$, since $b \in B \Rightarrow (hf)(f^{-1}(b)) = f^{-1}(b) \Rightarrow (hff^{-1})(b) = f^{-1}(b)$, ie $h(b) = f^{-1}(b)$. $\tag*{QED}$
Secondly we use the following property of linear functions :
Theorem 2
A function $f : \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$ is linear (ie. $f(x + y) = f(x) + f(y)$, and $f(\lambda x) = \lambda f(x)$) iff it has the form $f(x) = Ax$ for some $A \in \mathbb{R}^{m \times n}$.
Proof
'$\Leftarrow$' follows from standard properties of matrix multiplication. For '$\Rightarrow$', choose $A = [f(e_{1}), \ldots, f(e_{n})]$ where $\{e_{i}\}$ is the standard basis for $\mathbb{R}^{n}$. $\tag*{QED}$

Then by Theorem (2), if $f$ is the linear function $\mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$ defined by matrix $A$, existence of the right inverse $B$ of $A$ would imply the linear function $g : \mathbb{R}^{m} \rightarrow \mathbb{R}^{n}$ corresponding to $B$ satisfies $fg =$ identity mapping on $\mathbb{R}^{m}$. And existence of the left inverse $C$ of $A$ would imply the linear function $h : \mathbb{R}^{m} \rightarrow \mathbb{R}^{n}$ corresponding to $C$ satisfies $hf =$ identity mapping on $\mathbb{R}^{n}$.
Then the conditions for Theorem (1) apply and thus $f : \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$ is a bijective linear function.
In particular $f$ is surjective, so every element of $\mathbb{R}^{m}$ has form :
$f(x_{1}e_{1} + \cdots + x_{n}e_{n}) = x_{1}f(e_{1}) + \cdots + x_{n}f(e_{n})$
for some $\{x_{i}\}$, so that $\{f(e_{i})\}$ is a spanning sequence for $\mathbb{R}^{m}$. But from linear algebra (eg. [1, pg 117, 40.7]) this spanning sequence, comprising $n$ elements, spans a subspace of dimension $\leq n$, and therefore $m \leq n$. This same argument applied to the bijective linear function $f^{-1} : \mathbb{R}^{m} \rightarrow \mathbb{R}^{n}$ implies $n \leq m$ (the inverse of a bijective linear function must be linear - eg. [1, pg 139, 47.3]). Thus we must have $m = n$.

References
[1] Thomas A. Whitelaw (1991), An Introduction To Linear Algebra, 2nd Edition, Blackie.
