TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

Componentwise relative perturbations of bidiagonal matrices control every singular value relatively

Statement

Let $n \geq 1$ , and let $B, \tilde{B} \in F^{n \times n}$ be upper bidiagonal, $F = R$ or $C$ , with $0 \leq ϵ < 1$ . Suppose each corresponding nonzero diagonal or superdiagonal entry is multiplied by a scalar whose modulus lies in $[1 - ϵ, 1 + ϵ]$ , and every zero entry remains zero. Put $q = (1 + ϵ) / (1 - ϵ)$ . Then $B$ and $\tilde{B}$ have the same number of zero singular values, and for each positive singular value in descending order, $q^{- 2 n} σ_{i} (B) \leq σ_{i} (\tilde{B}) \leq q^{2 n} σ_{i} (B) .$

This is a relative perturbation theorem. A computed bidiagonal SVD inherits it only when a separate backward-error analysis verifies this componentwise relative assumption; an absolute normwise perturbation estimate by itself is not that verification.

Facts & Assumptions

Given: Two upper bidiagonal matrices satisfying the componentwise relative hypothesis and $q = (1 + ϵ) / (1 - ϵ)$ .

[F1]

Singular values contract under left and right multiplication: both $σ_{i} (X Y) \leq σ_{i} (X) ∥ Y ∥_{2}$ and $σ_{i} (Z X) \leq ∥ Z ∥_{2} σ_{i} (X)$ hold for compatible matrices in their stated index ranges.

[F2]

For diagonal $D = diag (d_{i})$ , $∥ D x ∥_{2}^{2} = \sum_{i} ∣ d_{i} ∣^{2} ∣ x_{i} ∣^{2} \leq (\max_{i} ∣ d_{i} ∣)^{2} ∥ x ∥_{2}^{2}$ , with equality on a coordinate vector attaining the maximum; hence $∥ D ∥_{2} = \max_{i} ∣ d_{i} ∣$ .

[F3]

The rank of a linear map is the number of its nonzero singular values: a square matrix has as many zero singular values as its dimension minus its rank.

Proof

1.1givenconstruct

Write the diagonal ratios as $s_{i} = {\tilde{d}}_{i} / d_{i}$ when $d_{i} \neq 0$ , and put $s_{i} = 1$ when $d_{i} = 0$ . Write the superdiagonal ratios as $t_{i} = {\tilde{e}}_{i} / e_{i}$ when $e_{i} \neq 0$ , and put $t_{i} = 1$ when $e_{i} = 0$ . Set $r_{1} = 1$ , $ℓ_{i} = s_{i} / r_{i}$ , and, for $i < n$ , set $r_{i + 1} = r_{i} t_{i} / s_{i}$ . Then $L = diag (ℓ_{i})$ and $R = diag (r_{i})$ are invertible and entrywise multiplication gives $\tilde{B} = L B R$ , including at zero entries because both matrices preserve each zero.

2.1step 1.1F2inductionalgebra

Since $∣ s_{i} ∣, ∣ t_{i} ∣ \in [1 - ϵ, 1 + ϵ]$ , each ratio $∣ t_{i} / s_{i} ∣$ lies in $[q^{- 1}, q]$ . Induction gives $q^{- (i - 1)} \leq ∣ r_{i} ∣ \leq q^{i - 1}$ . From $ℓ_{i} = s_{i} / r_{i}$ and $q (1 - ϵ) = 1 + ϵ$ , both $∣ ℓ_{i} ∣$ and $∣ ℓ_{i} ∣^{- 1}$ are at most $q^{n}$ ; the same bound holds for $∣ r_{i} ∣$ and $∣ r_{i} ∣^{- 1}$ . By [F2], $∥ L ∥_{2}, ∥ L^{- 1} ∥_{2}, ∥ R ∥_{2}, ∥ R^{- 1} ∥_{2} \leq q^{n}$ .

3.1step 1.1step 2.1F1F3algebra

First apply the right-multiplication inequality in [F1] to $(L B) R$ , then the left-multiplication inequality to $L B$ : $σ_{i} (\tilde{B}) \leq ∥ R ∥_{2} σ_{i} (L B) \leq ∥ R ∥_{2} ∥ L ∥_{2} σ_{i} (B) \leq q^{2 n} σ_{i} (B)$ . Applying the same two inequalities to $B = L^{- 1} \tilde{B} R^{- 1}$ gives the reverse bound. Since $L, R$ are invertible, multiplication by them preserves rank; [F3] then shows the zero singular values agree.

4.1step 3.1∎

Step 3.1 proves both inequalities and the zero-value assertion.

Depends on

Used by

Absolute error can erase a tiny singular value while relative error preserves it Example

Dependency tree · two levels

6 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

James Demmel and W. Kahan, Accurate Singular Values of Bidiagonal Matrices, Corollary 2 (standard reference, not scraped)
Lecture Notes on Matrix Computations, §3.2.2 (standard reference, not scraped)