Subset selection for matrices is the task of extracting a column sub-matrix from a given n-by-m matrix B with m>n such that the pseudoinverse of the sampled matrix has as small Frobenius or spectral norm as possible. A more general problem of subset selection for matrices that allows a block is chosen at the beginning is also considered. We present new approximation bounds as well as deterministic greedy selection algorithms for this problem. The main tools we introduce to obtain our results are (1) the use of the method of interlacing families of polynomials, and (2) the analysis of smallest zeros of certain expected characteristic polynomials by using the barrier function.