Let $$ \mathbf{B} = \left[\begin{array}{cc} 0 & 1 \\ 1 & -3 \\ 0 & 0 \end{array}\right]. $$
My task at hand is to all left-inverse matrices of $\mathbf{B}$, without using the Moore-Penrose pseudoinverse.
My attempt so far is the following:
I would like to solve the equation $\mathbf{X}\mathbf{B}=\mathbf{I}$ i.e
$$
\left[\begin{array}{lll}
x_1 & x_2 & x_3 \\
x_4 & x_5 & x_6
\end{array}\right]\left[\begin{array}{cc}
0 & 1 \\
1 & -3 \\
0 & 0
\end{array}\right] =\left[\begin{array}{ll}
1 & 0 \\
0 & 1
\end{array}\right]
$$
I do this by solving the system
$$ [\mathbf{B}^{\top}|\mathbf{I}] = \left[\begin{array}{ccc|cc} 0 & 1 & 0 & 1 & 0 \\ 1 & -3 & 0 & 0 & 1 \end{array}\right] $$
By doing rowoperations I get the following RREF $$ \left[\begin{array}{lll|ll} 1 & 0 & 0 & 3 & 1 \\ 0 & 1 & 0 & 1 & 0 \end{array}\right] $$
Hence $x_1 = 3, x_2=1, x_3 = s, x_4=1, x_5=0, x_6=t$ where $s$ and $t$ are free variables i.e there are infinitely many solutions and all left-inverses can be described by the matrix
$$ \left[\begin{array}{lll} 3 & 1 & s \\ 1 & 0 & t \end{array}\right] $$
Is this correct?
Yes. It is totally correct.
A non-square matrix has always a side-inverse (in this case a left-inverse) if it has full rank. However, the side-inverse does not have to be unique.
Actually I think that a side-invertible non-square matrix has always several side-inverses (maybe an infinite number). The proof of this can be an interesting exercise to do.
Edit: my intuition was wrong. Thanks to the comment below, we know that a matrix has several left inverses if it has more rows than columns, and it has zero left inverses if it has more columns than rows.