Column-Pivoted QR Rank Decisions

Concept Overview

Column pivoting is a modification to the QR decomposition that rearranges the columns of the input matrix to process the most dominant directions first. At each step, it selects the column with the largest residual norm. This technique is highly effective for discovering the numerical rank of a matrix, as the diagonal entries of the resulting upper triangular matrix R reveal the significance of each successive basis vector.

Worked Example

Consider a matrix with columns c₀ = (1, 0, 0), c₁ = (1, ε, 0), and c₂ = (0, 0, 2), where ε = 0.1. We want to find its column-pivoted QR factorization.

The norms of the initial columns are ||c₀|| = 1, ||c₁|| ≈ 1.00498, and ||c₂|| = 2.

Step 1: The largest norm is ||c₂|| = 2. We pivot c₂ to be the first column (index 0). The first diagonal of R is R₀₀ = 2. The remaining columns c₀ and c₁ are already orthogonal to c₂, so their residual norms remain 1 and ≈ 1.00498.
Step 2: Between the remaining residuals, c₁ has the larger norm (≈ 1.00498). We pivot c₁ to be the second column (index 1). The second diagonal of R is R₁₁ ≈ 1.004987562112089. We orthogonalize c₀ against c₁. The projection of c₀ onto c₁ is (1 * 1) / (1² + 0.1²) * c₁. The residual is c₀ - c₁ / 1.01. The norm of this residual is approximately 0.09950371902099893.
Step 3: The only remaining column is c₀, which becomes the third column (index 2). Its norm is R₂₂ ≈ 0.09950371902099893.

The final pivot order is 2, 1, 0. The diagonal magnitudes of R are 2.0, 1.004987562112089, and 0.09950371902099893. If we set a rank threshold τ = 0.05, we estimate the rank by counting diagonals where |R_ii| > τ * |R₀₀|. Since 0.09950... <= 0.05 * 2.0 = 0.1, the estimated numerical rank is 2. The exact rank is 3 because ε > 0.

c0 = [1, 0, 0]^T
c1 = [1, 0.1, 0]^T
c2 = [0, 0, 2]^T

R diagonals:
R00 = 2.0
R11 ≈ 1.004987562112089
R22 ≈ 0.09950371902099893

Threshold test for tau = 0.05:
|R00| > 0.05 * 2.0 (2.0 > 0.1) -> True
|R11| > 0.05 * 2.0 (1.0049... > 0.1) -> True
|R22| > 0.05 * 2.0 (0.0995... > 0.1) -> False

Estimated Numerical Rank = 2
Exact Rank = 3

Experiment

You can interact with the column-pivoted QR factorization using the interactive module.

Set Small scale to "0.1".
Set Rank threshold to "0.05".
Observe that the Estimated numerical rank is 2, while the Exact rank is 3, because the third diagonal magnitude drops below the relative threshold.
Change Small scale to "1". The columns are now well-separated in magnitude, and the third diagonal is 0.7071067811865476, which is larger than 0.05 * 2.0. The estimated rank is now 3.
Change Small scale to "0" (with rank threshold "0.05"). The exact rank drops to 2, and the third diagonal magnitude becomes exactly 0.0. The numerical rank correctly estimates 2.

Limitations

Column-pivoted QR factorization is an excellent practical tool for rank estimation, but it does not promise strong Rank-Revealing QR (RRQR) guarantees for all possible matrices. While it works well in practice, there exist pathological matrices (like the Kahan matrix) where column pivoting fails to reveal the true numerical rank. Additionally, numerical rank is highly dependent on the chosen threshold τ; distinguishing between noise and actual signal requires domain knowledge. Numerical rank should not be confused with exact linear dependence, which only occurs when a residual is exactly zero algebraically.

References

For a detailed discussion on condition numbers and rank estimation using QR decomposition with column pivoting, see the LAPACK Users' Guide on Condition Numbers and Rank Estimation. It explains the limitations of QR with column pivoting and why more sophisticated methods (like SVD or specialized RRQR algorithms) are sometimes needed for guaranteed bounds.

Column-Pivoted QR Rank Decisions