The authors of classical and quantum computation discuss the notion of garbage removal in the context of measurement operator, a slight generalization of the so-called projective measurement, that is familiar to people who have taken a basic course in quantum mechanics and seen for instance the Stern-Gerlach experiment. The generalization basically says that once the measurement is made, the state of the system will be projected onto some subspace , but the measurement outcome conditioned on this projection can still be random, that is, the operator is described by a double sum of projective subspace and conditional classical outcomes.
The section 12.3 on garbage removal seems written pretty casually. To use the same notation as in the book, the operator is given by , where is the projection onto the subspace , which form an orthogonal decomposition of , -qubit space. is the classical operator. The way we use is to first append a vector of to the state vector , to obtain , then . Here is called garbage, because it’s the last letter of the alphabet. The authors claim that only when can one find a garbage-free unitary operator such that . The idea is to let be a permutation operator (which is unitary) that takes to . But I don’t see why in the general case one couldn’t let , be some unitary operator that does just that. Of course this is no longer a permutation matrix, but so what?