TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Strong RRQR block singular values compare to the full matrix spectrum

Statement

Let $A \in F^{m \times n}$ have full column rank, $m \geq n$ , and let the exact-arithmetic version of Strong rank-revealing QR with finite swaps and explicit statuses return success with full QR factorization $A Π = Q [\begin{array}{cc} R_{11} & R_{12} \\ 0 & R_{22} \end{array}],$ where $Q \in F^{m \times m}$ is unitary and the displayed $R$ is upper trapezoidal with $m$ rows. Let the target satisfy $0 \leq k < n$ and the factor satisfy $f \geq 1$ . For $1 \leq k < n$ , assume $R_{11} \in F^{k \times k}$ is nonsingular and put $X = R_{11}^{- 1} R_{12}$ . Put $g = (1 + f^{2} k (n - k))^{1 / 2}$ . Then $σ_{i} (R_{11}) \geq \frac{σ_{i} (A)}{g} (1 \leq i \leq k), σ_{j} (R_{22}) \leq g σ_{k + j} (A) (1 \leq j \leq n - k) .$ For $k = 0$ , the second comparison is the equality $R_{22} = Q^{*} A Π$ with $g = 1$ . These conclusions use the combined score in the algorithm; the bound on $X$ alone is not used as a substitute for control of $R_{22}$ . For a computed candidate $\hat{R}$ with the algorithm's verified certificate $(W, (b_{i j}), ε)$ , put $\tilde{A} = W \hat{R} Π^{*}$ . No full-column-rank assumption on $\tilde{A}$ is required beyond nonsingularity of ${\hat{R}}_{11}$ when $k > 0$ . Then the corresponding residual-adjusted bounds are $σ_{i} ({\hat{R}}_{11}) \geq \frac{σ_{i} (A) - ε}{g} (1 \leq i \leq k), σ_{j} ({\hat{R}}_{22}) \leq g (σ_{k + j} (A) + ε) (1 \leq j \leq n - k) .$ For $k = 0$ , these reduce to $σ_{j} (\hat{R}) \leq σ_{j} (A) + ε$ . Computed scores alone do not certify either conclusion.

Facts & Assumptions

Given: A full-column-rank matrix and a successful factorization returned by the finite-swap algorithm.

[F1]

In the exact-arithmetic version of Strong rank-revealing QR with finite swaps and explicit statuses, success means $∣ X_{i j} ∣^{2} + (ω_{i} γ_{j})^{2} \leq f^{2}$ for every $i, j$ , where $ω_{i} = ∥ e_{i}^{*} R_{11}^{- 1} ∥_{2}$ and $γ_{j} = ∥ R_{22} (:, j) ∥_{2}$ . The finite-precision branch tests computed scores and is not used here.

[F2]

Singular values contract under left and right multiplication: $σ_{i} (X Y) \leq σ_{i} (X) ∥ Y ∥_{2}$ for compatible matrices.

[F3]

Spectral and Frobenius norms are unitarily invariant, are given by singular values, and satisfy the sharp rank comparison: the spectral and Frobenius norms are unitarily invariant, $∥ M ∥_{2} = σ_{1} (M)$ , and $∥ M ∥_{2} \leq ∥ M ∥_{F}$ .

[F4]

Singular values are Lipschitz in the spectral norm bounds each singular-value change by the spectral norm of the perturbation.

Proof

1.1F1F2F3algebra

First, square unitary factors preserve every ordered singular value: [F3] gives $∥ T ∥_{2} = ∥ T^{*} ∥_{2} = 1$ for a positive-dimensional unitary $T$ , and applying both inequalities of [F2] to $P M T$ gives $σ_{i} (P M T) \leq σ_{i} (M)$ ; applying them to $M = P^{*} (P M T) T^{*}$ gives the reverse inequality. Thus if $k = 0$ , $R_{22} = Q^{*} A Π$ has the singular values of $A$ , proving that case. Assume henceforth $1 \leq k < n$ . Write $A_{0} = R_{11}$ , $C = R_{22}$ , and $X = A_{0}^{- 1} R_{12}$ . Summing the $k (n - k)$ inequalities in [F1] gives $∥ X ∥_{F}^{2} + ∥ A_{0}^{- 1} ∥_{F}^{2} ∥ C ∥_{F}^{2} \leq f^{2} k (n - k) .$ Indeed, $\sum_{i} ω_{i}^{2} = ∥ A_{0}^{- 1} ∥_{F}^{2}$ and $\sum_{j} γ_{j}^{2} = ∥ C ∥_{F}^{2}$ .

2.1step 1.1F1F3algebra

Since $A$ has full column rank and $k < n$ , $C$ has full column rank: if $C z = 0$ for nonzero $z$ , then $R (\binom{- A_{0}^{- 1} R_{12} z}{z}) = 0$ , contradicting full column rank of $R = Q^{*} A Π$ , since $Q$ and $Π$ are invertible. Thus $α = ∥ C ∥_{2} / σ_{k} (A_{0}) > 0$ . Since $σ_{k} (A_{0}) = 1 / ∥ A_{0}^{- 1} ∥_{2}$ , one has $α^{2} = ∥ C ∥_{2}^{2} ∥ A_{0}^{- 1} ∥_{2}^{2} \leq ∥ C ∥_{F}^{2} ∥ A_{0}^{- 1} ∥_{F}^{2}$ , so step 1.1 gives $∥ X ∥_{F}^{2} + α^{2} \leq f^{2} k (n - k)$ .

3.1step 1.1step 2.1F2F3algebra

By step 1.1, $R = Q^{*} A Π$ has the same singular values as $A$ . Define $D_{1} = diag (A_{0}, C / α)$ and $W_{1} = [\begin{array}{cc} I_{k} & X \\ 0 & α I_{n - k} \end{array}]$ , so $R = D_{1} W_{1}$ . For vectors $x, y$ , $∥ W_{1} (x, y) ∥_{2}^{2} = ∥ x + X y ∥_{2}^{2} + α^{2} ∥ y ∥_{2}^{2}$ is bounded by the quadratic form of $M_{1} = [\begin{array}{cc} 1 & ∥ X ∥_{2} \\ ∥ X ∥_{2} & ∥ X ∥_{2}^{2} + α^{2} \end{array}]$ at $(∥ x ∥_{2}, ∥ y ∥_{2})$ . For scalars $u, v$ its quadratic form is $(u + ∥ X ∥_{2} v)^{2} + α^{2} v^{2} \geq 0$ , so it is positive semidefinite and its largest eigenvalue is at most its trace; thus $∥ W_{1} ∥_{2}^{2} \leq 1 + ∥ X ∥_{F}^{2} + α^{2} \leq g^{2}$ . Since $∥ C / α ∥_{2} = σ_{k} (A_{0})$ , the ordered first $k$ singular values of $D_{1}$ are those of $A_{0}$ . By [F2], $σ_{i} (R) \leq σ_{i} (D_{1}) ∥ W_{1} ∥_{2}$ , proving $σ_{i} (A_{0}) \geq σ_{i} (A) / g$ for $i \leq k$ .

3.2step 1.1step 2.1F2F3algebra

Define $D_{2} = diag (α A_{0}, C)$ and $W_{2} = [\begin{array}{cc} α I_{k} & - X \\ 0 & I_{n - k} \end{array}]$ , so $D_{2} = R W_{2}$ . For vectors $x, y$ , $∥ W_{2} (x, y) ∥_{2}^{2} = ∥ α x - X y ∥_{2}^{2} + ∥ y ∥_{2}^{2}$ is bounded by the quadratic form of $M_{2} = [\begin{array}{cc} α^{2} & α ∥ X ∥_{2} \\ α ∥ X ∥_{2} & ∥ X ∥_{2}^{2} + 1 \end{array}]$ at $(∥ x ∥_{2}, ∥ y ∥_{2})$ . Its determinant is $α^{2} > 0$ and its diagonal entries are positive, so it is positive semidefinite; its largest eigenvalue is at most its trace. Thus $∥ W_{2} ∥_{2}^{2} \leq 1 + ∥ X ∥_{F}^{2} + α^{2} \leq g^{2}$ . The smallest singular value of $α A_{0}$ is $∥ C ∥_{2}$ , so the first $k$ singular values of $D_{2}$ are those of $α A_{0}$ and its remaining $n - k$ singular values are those of $C$ . Therefore $σ_{j} (C) = σ_{k + j} (D_{2}) \leq σ_{k + j} (R) ∥ W_{2} ∥_{2} \leq g σ_{k + j} (A)$ by [F2] and step 1.1.

4.1step 1.1step 2.1step 3.1step 3.2F2F3F4algebra∎

The preceding block proof also applies to any upper trapezoidal $R$ whose $R_{11}$ is nonsingular and whose exact combined scores are at most $f$ , even when $R$ is rank deficient. If $C \neq 0$ , $α > 0$ and steps 2.1–3.2 apply without the full-column-rank argument. If $C = 0$ , write $R = diag (A_{0}, 0) [\begin{array}{cc} I & X \\ 0 & I \end{array}]$ . Directly $R = A_{0} [I X]$ with zero lower rows and $∥ [I X] ∥_{2}^{2} = 1 + ∥ X ∥_{2}^{2} \leq g^{2}$ . The product bound proves the first comparison, and the second is $0 \leq g σ_{k + j} (R)$ . Thus the certificate gives both comparisons with $A$ replaced by $\tilde{A}$ and blocks ${\hat{R}}_{11}, {\hat{R}}_{22}$ . Since $∥ A - \tilde{A} ∥_{2} \leq ε$ , [F4] gives $σ_{i} (\tilde{A}) \geq σ_{i} (A) - ε$ and $σ_{k + j} (\tilde{A}) \leq σ_{k + j} (A) + ε$ . Combining proves the computed bounds. The $k = 0$ case follows directly from unitary invariance and [F4].

Depends on

Used by

Strong-RRQR interpolative decomposition error and coefficient bounds Theorem

Dependency tree · two levels

15 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Ming Gu and Stanley C. Eisenstat, Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization, Theorem 3.2 (standard reference, not scraped)
Wen-Wei Lin, Lecture Notes of Matrix Computations, §3.2.2 (standard reference, not scraped)