# Numerical Linear Algebra problem (QR factorization with column pivoting)

For matrices that might be rank deficient it is common to incorporate pivoting in Householder QR factorization of A $\in$ $\Re^{mxn}$ (m $\geq$ n). Let $A^{(k)}$ denote the matrix at the start of the kth stage of the reduction (thus $A^{(1)}$ = A) and let $a_{j}^{(k)}$ denote the jth column of $A^{(k)}$. The column pivoting strategy excanges columns at the start of the kth stage to ensure that
||$a_{k}^{(k)}$(k : m)||$_{2}$ = $\max_{\substack{j \geq k}}$ ||$a_{j}^{(k)}$ (k : m)||$_{2}$

In other words, this strategy maximizes the 2-norm of the active part of the pivot column over all potential pivot columns.

a) Show that the R factor produced by QR factorization with column pivoting satisfies $r_{kk}^{2}$ $\geq$ $\sum_{i=k}^{j}$$r_{ij}^{2}$ , j = k + 1 : n, k = 1 : n.

b) What can be deduced about the ordering of the |$r_{ii}$| ?

c) If A has rank r < n, what is the form of R ?

Any help for the first question (a)?