= QR decomposition by Givens rotations
{c}
{title2=$R=\Omega A,\quad Q=\Omega^T$}
Successive <Givens rotations> eliminate entries below the diagonal of a <matrix>. For an $m\times n$ <matrix> with $m\geq n$, process columns $k=1,\ldots,n$; within column $k$, rotate rows $k,j$ for each $j>k$ whose entry needs elimination. Apply each <Givens row-pair update> to columns $k,\ldots,n$. Both rows are zero in earlier columns, so these operations preserve earlier eliminations. No assumption of <full column rank> is needed to perform the eliminations.
For a concrete example, take
$$
A=\begin{pmatrix}3&0\\4&5\\0&2\end{pmatrix}.
$$
First use $G_1=G_{12}(3/5,4/5)$, then $G_2=G_{23}(3/\sqrt{13},2/\sqrt{13})$:
$$
G_1A=\begin{pmatrix}5&4\\0&3\\0&2\end{pmatrix},\qquad
R=G_2G_1A=\begin{pmatrix}5&4\\0&\sqrt{13}\\0&0\end{pmatrix}.
$$
The entry in position $(3,1)$ was already zero, so its elimination was skipped. The second <Givens rotation> combines the remaining pair $(3,2)^T$ in column two. This yields the full <QR decomposition>
$$
Q=G_1^TG_2^T=
\begin{pmatrix}
3/5&-12/(5\sqrt{13})&8/(5\sqrt{13})\\
4/5&9/(5\sqrt{13})&-6/(5\sqrt{13})\\
0&2/\sqrt{13}&3/\sqrt{13}
\end{pmatrix},\qquad A=QR.
$$
The first two columns of $Q$ and first two rows of $R$ give the reduced <QR decomposition>. Direct multiplication verifies both $QR=A$ and $Q^TQ=I$. For these displayed factors evaluated in binary64 <floating-point arithmetic>, the <Frobenius norms> $\|A-QR\|_F$ and $\|Q^TQ-I\|_F$ are both below $10^{-14}$; these measure reconstruction and loss of <orthogonality> separately.
\Image[/givens-qr-row-elimination.png]
{title=Two local <Givens row-pair updates> turn a $3\times2$ <matrix> into the rectangular $R$ of a <QR decomposition>}
More generally, if the chronological rotations are $G_1,\ldots,G_p$, then
$$
\Omega=G_p\cdots G_1,\qquad R=\Omega A,\qquad
Q=\Omega^T=G_1^T\cdots G_p^T.
$$
Each factor is an <orthogonal matrix>, so $Q$ is too. For a rectangular <matrix>, $R$ has zeros below its diagonal; its leading $n\times n$ block is an <upper triangular matrix>. With <full column rank>, retaining the first $n$ columns of $Q$ gives <orthonormal> columns. To impose a positive diagonal when necessary, flip matching columns of $Q$ and rows of $R$, preserving their product.
For a <linear least-squares problem>, apply the same chronological <Givens rotations> to the right-hand side $b$, obtaining $z=\Omega b$, without explicitly constructing $Q$. Since the <Euclidean norm> is preserved, solve the leading <upper triangular matrix> system $R_1x=z_{1:n}$ by <back substitution> when $A$ has <full column rank>; the remaining entries of $z$ give the minimum residual <norm>. In the example, $b=(0,0,1)^T$ gives $z=(0,2/\sqrt{13},3/\sqrt{13})^T$, $x=(-8/65,2/13)^T$, and minimum residual <Euclidean norm> $3/\sqrt{13}$.
The locality is useful for a <sparse matrix> or an existing <QR decomposition> needing an extra row: only two rows change at each step, and the new row can be eliminated against the stored <upper triangular matrix>. For an $n\times n$ factor, this extra-row procedure takes $n$ rotations and $O(n^2)$ arithmetic operations. Locality does not guarantee preservation of sparsity: mixing rows can create nonzeros wherever either row had one. For a fully populated $m\times n$ input, the straightforward elimination uses $\sum_{k=1}^n(m-k)$ rotations, each touching $n-k+1$ columns, giving $O(mn^2)$ work. Storage layout, zero patterns and implementation affect speed; this count alone establishes no universal advantage over other <QR decomposition> <algorithms>.
The <Euclidean norm> preservation explains the appeal for <numerical stability>: exact rotations do not amplify a perturbation's length. Rounded <coefficients> and <Givens row-pair updates> still introduce <roundoff error>. Small reconstruction and <orthogonality> residuals check the computed factors, while the <condition number> of the original problem still controls how accurately a <linear least-squares problem> determines its solution.
Back to article page
