Givens Rotations

When you need to compute the QR decomposition of a matrix, the textbook approach applies Householder reflections — transformations that zero an entire column below the diagonal in one shot. That works beautifully on dense matrices. But what if the matrix is sparse, with most entries already zero? A Householder reflection can accidentally destroy that sparsity.

Givens rotations offer a surgical alternative. Each rotation targets exactly one entry, sets it to zero, and leaves every other entry it was not meant to touch unchanged. The price is that you need more steps; the payoff is total control over what zeros get created and what structure is preserved.

The idea is older than computers. The mathematician Wallace Givens systematized it in 1954 for use on early digital machines, where rotating in a single plane was cheaper than forming a full reflection. Today the same trick is indispensable in streaming signal processing, adaptive filters, and the sparse solvers at the heart of GPS, structural engineering simulations, and large-scale optimization.

The demo below shows a $3 \times 3$ matrix. Click any off-diagonal entry to make it your target. Then press Apply rotation to watch a Givens rotation zero it exactly, while displaying the angle $\theta$ and the updated matrix.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="matrix-wrap">
  <div id="matrix" class="matrix"></div>
  <div class="arrow">&#8594;</div>
  <div id="result" class="matrix result-mat"></div>
</div>
<div class="status" id="status">{{status_pick}}</div>
<div class="btns">
  <button id="apply" type="button" disabled>{{btn_apply}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.matrix-wrap { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin: .5rem 0 .7rem; }
.matrix { display: grid; grid-template-columns: repeat(3, 56px); gap: 4px; }
.cell { width: 56px; height: 48px; display: flex; align-items: center; justify-content: center;
        font: 600 15px ui-monospace, monospace; border-radius: 7px; user-select: none; }
.fixed { background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; }
.target-cell { background: #c9ccd1; border: 1px solid #adb1b8; cursor: pointer; transition: background .1s; }
.target-cell:hover { background: #b8bdc4; }
.target-cell.selected { background: #1d3557; color: #fff; border-color: #14274a; }
.target-cell.zeroed { background: #c9ccd1; color: #888; cursor: default; }
.result-mat .cell { background: #eaf7ef; color: #0a5c30; border: 1px solid #b4dfc7; }
.result-mat .cell.changed { background: #0a7d33; color: #fff; border-color: #065c26; }
.result-mat .cell.zero-achieved { background: #264de4; color: #fff; border-color: #1a35a8; }
.arrow { font-size: 1.8rem; color: #888; line-height: 1; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .4; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice what does not change: entries that share neither the row nor the column of the rotation are completely untouched. That is the defining property — a Givens rotation acts on exactly two rows at a time. String enough of them together and you drive an entire matrix to upper-triangular form, one zero at a time.

How does the cost compare with rival methods?

• One rotation: applying a Givens rotation to an $n \times n$ matrix touches only two rows, so the work is $O(n)$ — just a pass over those rows updating each element with $c \cdot x \pm s \cdot y$.
• Full QR via Givens: zeroing all $\frac{n(n-1)}{2}$ sub-diagonal entries needs that many rotations, giving $O(n^3)$ total — the same asymptotic cost as Householder QR.
• But sparse matrices change everything. If an entry is already zero, you can skip its rotation entirely. In a matrix with $k$ non-zeros below the diagonal, only $k$ rotations are needed, costing $O(kn)$. When $k \ll n^2$, this is a dramatic win.
• Streaming and rank-one updates: when a new row arrives, a single sweep of $n$ rotations incorporates it into the existing QR factorization — no full restart. This is the foundation of recursive least squares and adaptive filters.
• Numerical stability: Givens rotations are orthogonal transformations, so they never amplify rounding errors. The condition number of the problem is preserved exactly, unlike normal-equation approaches that square it.

The tradeoff is pedagogical simplicity vs. bulk efficiency. For dense matrices Householder wins by constant factors; for sparse or streaming data Givens is the natural choice and often the only practical one.

"Zero one entry at a time with full control" turns out to be exactly what many real systems need:

• Sparse linear systems: structural finite-element models and power-flow networks have millions of variables but each equation touches only a handful. Sparse QR via Givens exploits that exactly, only performing rotations for non-zero entries.
• Adaptive signal processing: recursive least squares updates a QR factorization with each new sample. One sweep of Givens rotations appends the new row, keeping filters responsive in real time — used in echo cancellation, noise reduction, and radar tracking.
• GPS and navigation: Kalman filters for position estimation use QR-based square-root forms for numerical safety. Givens rotations are the standard update step.
• Computer graphics and robotics: orthogonalizing a rotation matrix that has drifted from orthogonality due to floating-point accumulation is a classic Givens application.
• Rank-revealing QR: by choosing the order of Givens rotations strategically you expose the numerical rank of a matrix — a fundamental operation in dimensionality reduction and compressed sensing.

See also how QR decomposition uses these building blocks at a higher level, and how dimensionality reduction exploits the resulting factorizations.

Givens rotations are proof that sometimes the most powerful tool is the most precise one. Where Householder reflections swing a sledgehammer, a Givens rotation makes a single, targeted cut — zero exactly one entry, touch exactly two rows, leave everything else alone.

That precision is not just elegant; it is efficient. In the sparse and streaming worlds that dominate modern computation, the ability to skip rotations for entries that are already zero, or to update a factorization with a single new sample, turns an $O(n^3)$ algorithm into something far leaner in practice. Wallace Givens gave us the idea in 1954; it is more relevant today than ever.