PropositionStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passaudited 2026-08-29

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.

In the spectral norm, numerical rank counts the singular values above the declared threshold

Statement

Let $m, n \in N$ with $m \geq 1$ and $n \geq 1$ , let $A \in M_{m \times n} (R)$ with singular values $σ_{1} \geq \dots \geq σ_{\min (m, n)} \geq 0$ , let $τ \geq 0$ , and let $∥ \cdot ∥_{2}$ be the spectral norm. Then

${rank}_{τ} (A) = # {j \in {1, \dots, \min (m, n)} : σ_{j} > τ},$

where ${rank}_{τ} (A)$ is the numerical rank of Numerical rank relative to a declared norm, scale, and tolerance. Consequently, if two tolerances $τ < τ^{'}$ have a singular value $σ_{j}$ with $τ < σ_{j} \leq τ^{'}$ , then ${rank}_{τ} (A) > {rank}_{τ^{'}} (A)$ : moving the threshold past a singular value changes the numerical rank.

Facts & Assumptions

Given: Natural numbers $m, n \geq 1$ , a matrix $A \in M_{m \times n} (R)$ with singular values $σ_{1} \geq \dots \geq σ_{\min (m, n)} \geq 0$ , and a tolerance $τ \geq 0$ .

[L1]

Numerical rank: ${rank}_{τ} (A) = \min {rank B : ∥ A - B ∥_{2} \leq τ}$ (Numerical rank relative to a declared norm, scale, and tolerance).

[L2]

Eckart–Young: for $0 \leq k < \dim R^{n} = n$ , the least spectral-norm distance from $A$ to the matrices of rank at most $k$ is $σ_{k + 1}$ , with the convention $σ_{k + 1} = 0$ when $k$ exceeds the number of positive singular values (The best rank-at-most-k approximation in operator norm is the rank-k truncation of a singular value decomposition).

[L3]

The rank of a matrix is the number of its positive singular values (The rank of a linear map is the number of its nonzero singular values).

Proof

technique · direct

1.1L2L3algebra

For $k \geq \min (m, n)$ the matrix $A$ itself has rank at most $\min (m, n) \leq k$ by [L3], so the distance to rank at most $k$ is $0$ ; with the convention of [L2] this agrees with $σ_{k + 1} = 0$ . For $0 \leq k < \min (m, n) \leq n$ , [L2] gives the distance $σ_{k + 1}$ . Hence for every $k \geq 0$ , $\min {∥ A - B ∥_{2} : rank B \leq k} = σ_{k + 1}$ .

1.2algebra

Let $q : = # {j \in {1, \dots, \min (m, n)} : σ_{j} > τ}$ . If $q < \min (m, n)$ then $σ_{q + 1} \leq τ$ while $σ_{q} > τ$ ; if $q = \min (m, n)$ then all singular values exceed $τ$ and $σ_{\min (m, n) + 1} : = 0 \leq τ$ . In both cases $\min {k \geq 0 : σ_{k + 1} \leq τ} = q$ , because every $k < q$ has $σ_{k + 1} \geq σ_{q} > τ$ .

2.1step 1.1L1algebra

By step 1.1, there exists a matrix $B$ with $rank B \leq k$ and $∥ A - B ∥_{2} \leq τ$ exactly when $σ_{k + 1} \leq τ$ . Therefore [L1] gives ${rank}_{τ} (A) = \min {k \geq 0 : σ_{k + 1} \leq τ}$ .

3.1step 2.1step 1.2

Steps 2.1 and 1.2 give ${rank}_{τ} (A) = q$ , which is the displayed formula.

4.1step 3.1algebra

If $τ < σ_{j} \leq τ^{'}$ then $j$ is counted at tolerance $τ$ but not at tolerance $τ^{'}$ , and no larger index is counted at $τ^{'}$ ; hence ${rank}_{τ} (A) > {rank}_{τ^{'}} (A)$ , the stated consequence.

5.1step 3.1step 4.1∎

Step 3.1 proves the formula and step 4.1 the consequence.

Depends on

Used by

The same matrix can have two different numerical ranks under two declared tolerances Counterexample

Dependency tree · two levels

9 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

David Bindel, CS 6210: Matrix Nearness Problems (standard reference, not scraped)