We show by induction that the th column of is empty except for a non-zero entry in the th coordinate. Recall that is unitary if and only if its columns are an orthonormal basis of . Denote the columns of by . Then clearly is empty except for its first entry (because is diagonal). Now suppose this holds up to . Then, since for , and , we must have , and thus is also as described.