A n x n matrix A is invertible if there exists a matrix A-1 such that AA-1 = A-1A = I. This is only a conceivable operation when A is a square matrix.
A-1 exists only when the dimension of the column space of A, or the rank of the A, is equal to n. That is, it only exists when the columns of A form a basis for Rn.
The algorithm described in
How to find the inverse of a matrix will always find the inverse if it exists.