= Solution
Each <QR decomposition> $A_k=Q_kR_k$ gives
$$
A_{k+1}=R_kQ_k=Q_k^TA_kQ_k.
$$
Induction therefore yields the first <Accumulated QR factorization identity>:
$$
\boxed{A_{k+1}=\overline Q_k^TA\overline Q_k},
\qquad
\overline Q_k=Q_0Q_1\cdots Q_k.
$$
We next prove the corresponding factorization of a <matrix power>. The case $k=0$ is just $A=Q_0R_0$. If
$$
A^{k+1}=\overline Q_k\overline R_k,
\qquad
\overline R_k=R_kR_{k-1}\cdots R_0,
$$
then the similarity formula above implies
$$
A\overline Q_k=\overline Q_kA_{k+1}.
$$
Consequently,
$$
\begin{aligned}
A^{k+2}
&=A\overline Q_k\overline R_k\\
&=\overline Q_kA_{k+1}\overline R_k\\
&=\overline Q_kQ_{k+1}R_{k+1}\overline R_k\\
&=\overline Q_{k+1}\overline R_{k+1}.
\end{aligned}
$$
The product $\overline Q_k$ is <orthogonal matrix>[orthogonal], and the product $\overline R_k$ is <triangular matrix>[upper triangular]. Hence
$$
\boxed{A^{k+1}=\overline Q_k\overline R_k}
$$
is a QR decomposition.
Back to article page
