Exact unitary equivalence of Householder bidiagonalization

For any nonzero active vector $z$, [F1] specifies $N=\mathrm{\parallel }z{\mathrm{\parallel }}_2$, $\varphi =z_1\mathrm{/}\mathrm{\mid }{z}_1\mathrm{\mid }$ if $z_1\mathrm{\ne }0$ and $\varphi =1$ otherwise, $\alpha =-\varphi N$, $v=z-\alpha e_1$, and $h=v\mathrm{/}\mathrm{\parallel }v{\mathrm{\parallel }}_2$. Since $\bar{\alpha }{z}_1=-N\mathrm{\mid }{z}_1\mathrm{\mid }$, direct expansion gives $v^{\ast }z=N^2+N\mathrm{\mid }{z}_1\mathrm{\mid }>0$ and $v^{\ast }v=2(N^2+N\mathrm{\mid }{z}_1\mathrm{\mid })$. Thus $v\mathrm{\ne }0$, $h^{\ast }h=1$, and $H=I-2h{h}^{\ast }$ satisfies $H^{\ast }=H$ and $Hz=z-2v(v^{\ast }z)\mathrm{/}(v^{\ast }v)=\alpha e_1$. It is unitary by [F2]. For $z=0$ the specified identity has the same zero-annihilation property. This verifies the actual negative-phase construction on both the column vector and the conjugate-transposed row vector.

At step $k$, the left reflector acts only on rows $k:M$. It therefore leaves all rows $1,\dots ,k-1$ unchanged and maps the active part of column $k$ to its first coordinate, making entries below $(k,k)$ zero. The right reflector acts only on columns $k+1:p$, so it preserves the zeros already made in column $k$ and maps the active part of row $k$ to its first coordinate, making entries beyond $(k,k+1)$ zero.

Inductively, before stage $k$, each earlier column $\mathrm{\ell }<k$ has zeros in rows $k:M$, so the left update preserves those zeros. Each earlier row $\mathrm{\ell }<k$ has zeros in columns $k+1:p$, so the right update preserves those zeros as well; neither update touches its earlier retained entries. Step 2.1 supplies the new column and row zeros. At the last stage, column $p$ also has zeros below row $p$. Induction therefore gives an upper bidiagonal leading $p\times p$ block and zero bottom $M-p$ rows. For $p=0$ the work matrix is already the empty tall matrix and both initialized factors are identities.

The update rules in [F1] maintain the invariant $C=U^{\ast }{C}_{0}V$, where $C_0$ is the initial tall-oriented matrix. Every factor is unitary by [F2], so the accumulated $U,V$ are unitary. Combining this invariant with step 3.1 gives the asserted tall reduction. In the wide case it applies to $A^{\ast }$, and taking adjoints gives $A=V\left[\begin{array}{cc}{B}^{\ast }& 0\end{array}\right]U^{\ast }$.