Here's one way to think about the problem: note that we necessarily have $m \leq n$ (why?). When $m = n$, this is a simple question of matrix inversion. When $m<n$, we may state that $A$ has some set of $m$ columns that are linearly independent.
Let $i_1,i_2,\dots,i_m$ be the (indices of the) columns of $A$ corresponding to a linearly independent set of columns (without repetition). Let $e_i$ be the $i$th standard basis vector.
Noting that $A e_i$ is the $i$th column of $A$, we note that
$$
A\pmatrix{e_{i_1}&e_{i_2}&\cdots & e_{i_m}}
$$
Gives us an $m \times m$ matrix with full rank. Since this is a square matrix with full rank, it is invertible.
Let $B$ be given by
$$
B = \pmatrix{e_{i_1}&e_{i_2}&\cdots & e_{i_m}} \left[ A\pmatrix{e_{i_1}&e_{i_2}&\cdots & e_{i_m}}\right]^{-1}
$$
Confirm that $AB = I_m$
Since $A$ is nonsingular, consider the following block factorization of $C$:
$$
C=\pmatrix{A&B^T\\B&0}
=
\pmatrix{I&0\\BA^{-1}&I}\pmatrix{A&0\\0&S}\pmatrix{I&A^{-1}B^T\\0&I},
$$
where $S:=-BA^{-1}B^T$. Since the triangular blocks are nonsingular, the matrix $C$ is nonsingular iff the Schur complement matrix $S$ is nonsingular.
Now if $A$ is SPD, it is easy to see that $S$ is SPD as well. First, the definiteness of $A$ implies that $A^{-1}$ is SPD. For a nonzero $x$, $B^Tx\neq 0$ since has $B$ has full row rank, and $$x^T(BA^{-1}B^T)x=(B^Tx)^TA^{-1}(B^Tx)>0.$$
Another way to see that $C$ is nonsingular if $A$ is SPD and $B$ has full row rank is as follows. Assume that $Cz=0$ for some nonzero $z=(x^T,y^T)^T$. Hence
$$\tag{1}
Ax+B^Ty=0, \quad Bx=0.
$$
None of the block components can be zero. If $x=0$ and $y\neq 0$ then $B^Ty=0$ which is impossible since $B$ has full row rank. If $x\neq 0$ and $y=0$ then $Ax=0$ which is impossible since $A$ is SPD. Hence both $x\neq 0$ and $y\neq 0$. Multiply the first equation in (1) with $x^T$ and the second with $y^T$ to get
$$
x^TAx+x^TB^Ty=0, \quad y^TBx=0.
$$
Since $x^TB^Ty=y^TBx=0$, we have $x^TAx=0$, which gives again a contradiction.
It is not sufficient that $A$ is nonsingular and $B$ of full rank for $S$ being nonsingular. Consider,
$$
A=\pmatrix{1 & 0 \\ 0 & -1},
\quad B=(1,1).
$$
It is easy to verify that $C$ is singular (actually $S=0$).
Best Answer
If a matrix $A$ has full rank the row reduced echelon form of $A$ will be the identity matrix.
We can find the inverse of $A$, multiplying I by the elementary row operations.
Note that if $E_1 E_2...E_k A= I$, then $A^{-1}= E_1 E_2...E_k I.$