First get a non-zero entry in the upper lefthand corner by swapping to rows if necessary. If that entry is $a_{11}\ne 0$, multiply the first row by $a_{11}^{-1}$ to get a $1$ in the upper lefthand corner. Now use operation (2) to get $0$’s in the rest of the first column.
Now get a non-zero entry in the $a_{22}$ position, the second entry in the second row, by swapping the second row with one of the lower rows if necessary, and multiply the (possibly new) second row by $a_{22}^{-1}$ to get a $1$ in the $a_{22}$ position. Then use operation (2) to get $0$’s in the rest of the second column; notice that since $a_{21}$, the first element in the second row, is $0$, this will not affect anything in the first column.
At this point your matrix looks like this:
$$\begin{bmatrix}
1&0&a_{13}&\dots&a_{1n}\\
0&1&a_{23}&\dots&a_{2n}\\
0&0&a_{33}&\dots&a_{3n}\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
0&0&a_{n3}&\dots&a_{nn}
\end{bmatrix}$$
Continue in the same fashion: get a non-zero entry in the $a_{33}$ position by swapping row $3$ with a lower row if necessary, multiply row $3$ by a suitable constant to make $a_{33}=1$, and use operation (2) to $0$ out the rest of the third column.
If at any point the necessary operation is impossible, your original matrix was not invertible.
Every invertible matrix is equivalent via row operations to the identity matrix, and the identity matrix is only similar to itself.
This also gives a counterexample to the permutation question; the identity matrix is not similar to a non-identity permutation matrix.
Best Answer
What you described are elementary operations.
To swap row $1$ and row $3$, pre-multiply the matrix $\begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0\end{bmatrix}$ (we swap row $1$ and row $3$ of the identity matrix).
To multiply row $2$ by $c$, pre-multiply the matrix $\begin{bmatrix} 1 & 0 & 0 \\ 0 & c & 0 \\ 0 & 0 & 1\end{bmatrix}$ (we multiply $c$ to the second row of the identity matrix).
You might like to check out elementary matrices.