Correctness and Termination of Two-Level Elimination

If $b\mathrm{\ne }0$, then $h>0$ and direct multiplication gives $G^{\ast }G=I_2$ and $G(a,b{)}^T=(h,0{)}^T$. Thus the row operation is defined and left multiplication by its coordinate embedding preserves unitarity of $M$. If $b=0$, skipping the operation leaves the desired entry zero.

Inductively, before processing column $j$, columns $0,\dots ,j-1$ have zero entries below their diagonal positions. Each row pair used for column $j$ has indices at least $j$, so both entries in every earlier column are zero and the row operation preserves those zeros. Descending $r$ therefore makes column $j$ zero below its diagonal without undoing a zero already made in that column.

After the finite loops, $D=G_s\cdots G_{1}U$ is upper triangular and unitary. Its first column has only its first entry nonzero, which has modulus one. Orthogonality with every later column forces the first entry of each later column to be zero. Removing the first row and column leaves an upper-triangular unitary block; induction proves that $D$ is diagonal with unit-modulus diagonal entries.

Rearranging $D=G_s\cdots G_{1}U$ gives $U=G_1^{\ast }\cdots G_s^{\ast }D$ exactly. The finite loops have ${\sum }_{j=0}^{N-2}(N-j-1)=N(N-1)\mathrm{/}2$ iterations (zero for $N=1$), with at most one row elimination per iteration, so they terminate with at most that many eliminations and at most $N$ diagonal phases; the zero tests skip any already-zero entry. Under the convention that a matrix product acts on column states from right to left, the same identity orders the actions as $D$ first and then $G_s^{\ast },\dots ,G_1^{\ast }$.