A compact Francis bulge chase preserves Hessenberg form and the initial direction

Write $\mathcal{P}(j)$ for the assertions that columns $k<j$ of $H_j$ are upper Hessenberg and every nonzero entry below the first subdiagonal of $H_j$ lies in a row $i\le \min (n,j+r+1)$. For the base $j=1$, $P_0$ changes only the first $r+1$ rows and columns. If $i>r+2$ and $k\le r+1$, then $i>k+1$, so [F1] gives $(H_0{)}_{i,k}=0$; right multiplication within the first $r+1$ columns and left multiplication within the first $r+1$ rows cannot create entries there. For $k>r+1$, the row $i>r+2$ is untouched and $(H_0{)}_{i,k}=0$ whenever $i>k+1$. Hence all below-subdiagonal entries of $H_1$ lie in rows $i\le \min (n,r+2)$, which is $\mathcal{P}(1)$.

Suppose $\mathcal{P}(j)$ holds. By hypothesis, the chosen $P_j$ aligns the active vector, including when $P_j$ is the identity. Such choices exist by [F3] for a nonzero vector and by the identity for a zero vector. The below-subdiagonal entries of column $j$ can occur only in rows $j+2,\dots ,\min (n,j+r+1)$, all inside $I_j$. Left multiplication by $P_j^{\ast }$ maps the active column segment to a multiple of its first coordinate; here [F2] identifies $P_j^{\ast }$ with the reflector $P_j$. The rows beyond $I_j$ already vanish there by $\mathcal{P}(j)$. Since right multiplication acts only on columns in $I_j$, column $j$ is unchanged by it and is now Hessenberg. If $k<j$, every entry in rows $I_j$ of column $k$ was zero because $i\ge j+1>k+1$; the left update preserves these zeros and the right update does not touch column $k$. Thus columns $k\le j$ are Hessenberg after this step.

The left update changes only rows at most $j+r+1$. In the columns in $I_j$, any entry below the first subdiagonal in a row greater than $j+r+2$ is zero before the right update: it lies below the Hessenberg band, and its row exceeds the support bound in $\mathcal{P}(j)$. The right update mixes only columns in $I_j$, so those entries remain zero. In columns outside $I_j$, the right update makes no change; rows outside the left support are unchanged, and every below-subdiagonal entry in a row greater than $j+r+2$ was already zero by $\mathcal{P}(j)$. Therefore every below-subdiagonal entry of $H_{j+1}$ lies in a row $i\le \min (n,j+r+2)$, proving $\mathcal{P}(j+1)$.

If $n\le 2$, every $n\times n$ matrix is upper Hessenberg. If $n\ge 3$, the loop ends at $j=n-2$; steps 1.2 and 2.1 show that columns $1$ through $n-2$ are Hessenberg, while the last two columns cannot contain entries below their first subdiagonal by dimension. Hence $H_{J+1}$ is upper Hessenberg. By [F2], $P_{0}x=\alpha e_1$ implies $P_0{e}_1=x\mathrm{/}\alpha$. Each later $P_j$ is supported on indices beginning at $j+1\ge 2$, so $P_j{e}_1=e_1$. Therefore $Q{e}_1=P_0{e}_1=x\mathrm{/}\alpha$.