Exact column-pivoted QR of a real or complex rank-r matrix has an invertible leading triangular block and zero trailing block

After $k$ pivot steps, the first $k$ pivoted columns span the same subspace as the first $k$ columns of $QR$, and the next pivot diagonal entry $r_{kk}$ is the norm of the residual of the chosen column after projection onto that span. Hence $r_{kk}\mathrm{\ne }0$ exactly when some remaining column still has a nonzero residual, that is, still lies outside the span of the first $k$ chosen columns.

For $k<r$, the chosen columns cannot already span every column of $A$, because then all columns would lie in a $k$-dimensional span and [L4] would give rank at most $k<r$. Therefore some remaining column has nonzero residual, and by the greedy rule step 1.1 gives $r_{kk}\mathrm{\ne }0$. Thus the first $r$ diagonal entries of $R$ are nonzero.

After $r$ pivot columns have been chosen, [L4] says no further independent column exists. Hence every remaining column lies in the span of the first $r$ chosen columns, so every remaining residual is zero. Step 1.1 then forces every entry below and on the diagonal in the trailing block to be zero, giving $R=\left(\begin{array}{cc}{R}_{11}& R_{12}\\ 0& 0\end{array}\right)\mathrm{.}$ The block $R_{11}$ is upper triangular with nonzero diagonal by step 2.1, so it is invertible.

Steps 2.1 and 3.1 prove the claim.