Prove that there exists a $d \times d$ unitary matrix $U$ which cannot be decomposed as a product of fewer than $d-1$ two-level unitary matrices I'm trying to solve exercise 4.38 from Nielsen and Chuang, which asks to "Prove that there exists a $d \times d$ unitary matrix $U$ which cannot be decomposed as a product of fewer than $d-1$ two-level unitary matrices".
In this context, a two-level matrix is a matrix which acts nontrivially on at most two levels. In other words, we say that $A$ is a two-level matrix if it can be written as $A=\tilde A \oplus I$ for some $2\times2$ matrix $\tilde A$ (up to a rearrangement of the matrix components). This definition is found in section 4.5.1 in the 10th edition of the book.
If you find unitary matrices $U_{d-1}, U_{d-2}, \ldots, U_1$ such that the matrix $U_{d-1}U_{d-2}\ldots U_1U$ has a one in the top left-hand corner, all zeroes elsewhere in the first row and column, and the remaining $d-1 \times d-1$ submatrix (when you remove the first row and column) is not a two-level unitary, then the decomposition of $U$ must require more than $d-1$ two-level unitaries. That seems pretty clear, I'm just not sure where to go from here. Any hints/suggestions?
 A: Suppose $U$ is a $d\times d$ unitary matrix which can be decomposed using less than $d-1$ two-level unitaries.
We can think of each two-level unitary as an "edge" linking some pair of modes, interpreting each mode as a vertex. Let us then ask what kinds of configurations can be obtained using less than $d-1$ edges. In other words, what kinds of graphs are possible using less than $d-1$ edges.
As discussed in this math.SE post, any such graph must contain at least two connected components. This means that there must be at least two subsets of vertices/modes, call them $V_1$ and $V_2$, which are not connected by any edge.
Physically, we can understand this as saying that if less than $d-1$ two-level unitaries are used to decompose $U$, then there must be two subsets of modes on which $U$ acts independently.
Upon rearranging the order of the levels, this means that $U=U_1\oplus U_2$ for some unitaries $U_1,U_2$.
In other words, if $U$ can be built with less than $d-1$ two-level unitaries, then $U$ is block-diagonal in the computational basis. Clearly not every $U$ has this form. To name one example, the QFT matrix doesn't.
To also verify this numerically, here's a Mathematica snippet that combines together $d-2$ random two-level unitaries and shows the resulting matrix. Consistently with the reasoning above, we can notice that any resulting matrix has a block-diagonal form:
d = 5;
numberTwoLevelUnitaries = d - 2;
randomTwoLevelUnitaries = Table[RandomUnitary@2, numberTwoLevelUnitaries];
randomPositions = Table[RandomSample[Range@d, 2], numberTwoLevelUnitaries] // Echo;
embeddedRandomUnitaries = Table[
  With[{pos = posAndUnitary[[1]], u = posAndUnitary[[2]]},
    ArrayFlatten[{
      {u, 0}, {0, IdentityMatrix[d - 2]}
    }] // ReplacePart[IdentityMatrix@d,
      Table[
        {pos[[i]], pos[[j]]} -> #[[i, j]],
        {i, 2}, {j, 2}
      ] // Flatten[#, 1] &
    ] &
  ],
  {posAndUnitary, Thread@{randomPositions, randomTwoLevelUnitaries}}
];
overallUnitary = Dot @@ embeddedRandomUnitaries;
overallUnitary // MatrixForm // Chop

