So I think I have this proof. Please let me know if it works:
1) The column vectors of a matrix Q are linearly independent
2) rref(Q) is the identity matrix
3) A matrix is invertible if and only if the rref of the matrix is the identity matrix
4) Therefore, Q is invertible
Please let me know if there are other, more elegant proofs.