[proofplan]
We proceed by induction on $k$. The base case $k = 0$ is immediate since $X^{(0)} = I$. For the inductive step, we use the simultaneous iteration relation $AX^{(k)} = X^{(k+1)}R^{(k+1)}$ to identify a QR factorisation of $A^{(k)}$, then show that the QR iteration update $A^{(k+1)} = R^{(k+1)}Q^{(k+1)}$ coincides with $(X^{(k+1)})^\top A X^{(k+1)}$.
[/proofplan]
[step:Verify the base case $k = 0$]
At $k = 0$, simultaneous iteration starts with $X^{(0)} = I$, so
\begin{align*}
(X^{(0)})^\top A X^{(0)} = I^\top A I = A = A^{(0)},
\end{align*}
which matches the QR iteration initialisation $A^{(0)} = A$.
[/step]
[step:Identify the QR factorisation of $A^{(k)}$ from the simultaneous iteration step]
Assume $(X^{(k)})^\top A X^{(k)} = A^{(k)}$ as the induction hypothesis. The simultaneous iteration algorithm computes the QR factorisation
\begin{align*}
AX^{(k)} = X^{(k+1)} \hat{R},
\end{align*}
where $X^{(k+1)}$ has orthonormal columns and $\hat{R}$ is upper triangular. Define
\begin{align*}
Q := (X^{(k)})^\top X^{(k+1)}, \qquad R := \hat{R}.
\end{align*}
Since both $X^{(k)}$ and $X^{(k+1)}$ have orthonormal columns (and are square when $p = n$; for the basic QR iteration, $X^{(0)} = I \in \mathbb{R}^{n \times n}$), the matrix $Q$ is orthogonal:
\begin{align*}
Q^\top Q = (X^{(k+1)})^\top X^{(k)} (X^{(k)})^\top X^{(k+1)} = (X^{(k+1)})^\top X^{(k+1)} = I.
\end{align*}
We verify that $A^{(k)} = QR$. Left-multiplying $AX^{(k)} = X^{(k+1)}\hat{R}$ by $(X^{(k)})^\top$:
\begin{align*}
(X^{(k)})^\top A X^{(k)} = (X^{(k)})^\top X^{(k+1)} \hat{R} = QR.
\end{align*}
By the induction hypothesis, $(X^{(k)})^\top A X^{(k)} = A^{(k)}$, so $A^{(k)} = QR$ is a QR factorisation.
[guided]
The connection between simultaneous iteration and QR iteration hinges on this observation: the orthogonal factor $Q$ in the QR decomposition of $A^{(k)}$ is not an arbitrary orthogonal matrix — it is the *change-of-basis matrix* $(X^{(k)})^\top X^{(k+1)}$ between consecutive iterate frames. The upper triangular factor $R$ is the same $\hat{R}$ produced by the simultaneous iteration's QR step.
Why does this work? Both algorithms perform the same algebraic operation viewed from different coordinate systems. Simultaneous iteration works in the original basis and explicitly tracks $X^{(k)}$. QR iteration works in the frame of $X^{(k)}$ (via the similarity $A^{(k)} = (X^{(k)})^\top A X^{(k)}$) and never sees $X^{(k)}$ directly.
[/guided]
[/step]
[step:Complete the induction by computing $A^{(k+1)} = RQ$]
The basic QR iteration defines $A^{(k+1)} = RQ$ (writing the factors in reverse order). We compute:
\begin{align*}
A^{(k+1)} = RQ = \hat{R} \cdot (X^{(k)})^\top X^{(k+1)}.
\end{align*}
From $AX^{(k)} = X^{(k+1)}\hat{R}$, left-multiplying by $(X^{(k+1)})^\top$:
\begin{align*}
(X^{(k+1)})^\top A X^{(k)} = (X^{(k+1)})^\top X^{(k+1)} \hat{R} = \hat{R}.
\end{align*}
Therefore
\begin{align*}
A^{(k+1)} &= RQ = (X^{(k+1)})^\top A X^{(k)} \cdot (X^{(k)})^\top X^{(k+1)} \\
&= (X^{(k+1)})^\top A \bigl(X^{(k)} (X^{(k)})^\top\bigr) X^{(k+1)}.
\end{align*}
Since $X^{(k)}$ is a square orthogonal matrix (both algorithms start with $X^{(0)} = I \in \mathbb{R}^{n \times n}$ and preserve orthonormality), $X^{(k)}(X^{(k)})^\top = I$. Thus
\begin{align*}
A^{(k+1)} = (X^{(k+1)})^\top A X^{(k+1)},
\end{align*}
completing the induction.
[guided]
The critical step is the insertion of $X^{(k)}(X^{(k)})^\top = I$ in the middle. This identity holds because $X^{(k)} \in \mathbb{R}^{n \times n}$ is orthogonal (the simultaneous iteration with $X^{(0)} = I$ produces square orthogonal matrices at every step). Without this, the product $X^{(k)}(X^{(k)})^\top$ would be a projection rather than the identity, and the factorisation would fail.
The result establishes that the QR iteration — which is computationally cheaper because it only manipulates $n \times n$ matrices without explicitly tracking the basis $X^{(k)}$ — produces the same sequence of projected matrices as simultaneous iteration. In particular, the convergence theory for simultaneous iteration (the [Technical Convergence Lemma](/theorems/1410) and the [Convergence of Simultaneous Iteration](/theorems/1411)) transfers directly to the QR iteration: the diagonal entries of $A^{(k)}$ converge to the eigenvalues of $A$.
[/guided]
[/step]
