  Subset selection for matrices is the task of extracting a column sub-matrix
from a given matrix $B\in\mathbb{R}^{n\times m}$ with $m>n$ such that the
pseudoinverse of the sampled matrix has as small Frobenius or spectral norm as
possible. In this paper, we consider a more general problem of subset selection
for matrices that allows a block to be fixed at the beginning. Under this
setting, we provide a deterministic method for selecting a column sub-matrix
from $B$. We also present a bound for both the Frobenius and spectral norms of
the pseudoinverse of the sampled matrix, showing that the bound is
asymptotically optimal. The main technology for proving this result is the
interlacing families of polynomials developed by Marcus, Spielman, and
Srivastava. This idea also results in a deterministic greedy selection
algorithm that produces the sub-matrix promised by our result.
