TheoremStatement: 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.

Exact rank is locally constant at full-rank matrices and discontinuous at nonmaximal-rank matrices

Statement

Let $m, n \in N$ with $m \geq 1$ and $n \geq 1$ , let $A \in M_{m \times n} (R)$ , let $k : = \min (m, n)$ , and let $∥ \cdot ∥_{2}$ be the spectral norm.

Locally constant at full rank. If $rank A = k$ and $σ_{k}$ is the smallest singular value of $A$ (which is positive), then every $B \in M_{m \times n} (R)$ with $∥ B - A ∥_{2} < σ_{k}$ satisfies $rank B = k$ .
Discontinuous at nonmaximal rank. If $rank A = r < k$ , then for every $ε > 0$ there is $B \in M_{m \times n} (R)$ with $∥ B - A ∥_{2} < ε$ and $rank B = r + 1$ .

Facts & Assumptions

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

[L1]

There is a singular value decomposition $A = U Σ V^{T}$ with orthogonal $U, V$ and diagonal $Σ$ ; likewise every matrix $B \in M_{m \times n} (R)$ admits one (Every linear map between finite-dimensional real or complex inner product spaces admits a singular value decomposition).

[L2]

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).

[L3]

The spectral norm of a matrix equals its largest singular value, and $∥ M y ∥_{2} \leq ∥ M ∥_{2} ∥ y ∥_{2}$ for every vector $y$ (Spectral and Frobenius norms are unitarily invariant, are given by singular values, and satisfy the sharp rank comparison).

Proof

technique · direct

1.1L2

If $rank A = k$ , then by [L2] there are exactly $k$ positive singular values, so the smallest one, $σ_{k}$ , is positive.

1.2L1algebra

Full-column-rank lower bound. Suppose $n \leq m$ and $B \in M_{m \times n} (R)$ has singular values $τ_{1} \geq \dots \geq τ_{n}$ . Writing a unit vector $x$ in the right-singular basis of the decomposition from [L1] gives $∥ B x ∥_{2}^{2} = \sum_{j < n} τ_{j}^{2} ∣ (V^{T} x)_{j} ∣^{2} \geq τ_{n}^{2}$ , attained at the last right-singular vector. Hence $τ_{n} = \min_{∥ x ∥_{2} = 1} ∥ B x ∥_{2}$ .

1.3L1givenalgebra

Suppose $rank A = r < k$ ; then both $r < m$ and $r < n$ , so the decomposition of [L1] has a left singular vector $u_{r + 1} \in R^{m}$ and a right singular vector $v_{r + 1} \in R^{n}$ beyond the positive singular values.

1.4L1L2algebraconstruct

For $ε > 0$ put $B_{ε} : = A + ε u_{r + 1} v_{r + 1}^{T}$ . Then $B_{ε} = U (Σ + ε e_{r + 1} e_{r + 1}^{T}) V^{T}$ is a singular value decomposition of $B_{ε}$ with positive singular values $σ_{1}, \dots, σ_{r}, ε$ , so by [L2] $rank B_{ε} = r + 1$ .

2.1step 1.2L2L3algebra

Assume first that $rank A = k$ and $n \leq m$ . Applying step 1.2 to $A$ gives $∥ A x ∥_{2} \geq σ_{k}$ for every unit vector $x$ , and [L3] gives $∥ E x ∥_{2} \leq ∥ E ∥_{2}$ for $E : = B - A$ ; so $∥ B x ∥_{2} = ∥ A x + E x ∥_{2} \geq ∥ A x ∥_{2} - ∥ E x ∥_{2} \geq σ_{k} - ∥ E ∥_{2}$ . If $∥ E ∥_{2} < σ_{k}$ , then $∥ B x ∥_{2} > 0$ for every unit vector $x$ , so step 1.2 applied to $B$ gives its smallest singular value $τ_{n} > 0$ . Therefore [L2] gives $rank B = n = k$ .

2.2step 1.4L3algebra

Fix $ε > 0$ and set $η : = ε / 2$ . Step 1.4 gives $rank B_{η} = r + 1$ . By [L3], the spectral norm of $η u_{r + 1} v_{r + 1}^{T}$ is $η$ times the largest singular value of the rank-one matrix $u_{r + 1} v_{r + 1}^{T}$ , whose only positive singular value is $1$ ; hence $∥ B_{η} - A ∥_{2} = η < ε$ . This proves the discontinuity claim.

3.1L1L3step 2.1algebra

Assume next that $rank A = k$ and $m < n$ . Then $A^{T}$ has full column rank $m$ and the same positive singular values as $A$ by [L1], so its smallest singular value is again $σ_{k}$ . The same transpose relation holds for $B^{T}$ , and [L3] gives $∥ B^{T} - A^{T} ∥_{2} = ∥ B - A ∥_{2}$ . Applying step 2.1 to $A^{T}$ and $B^{T}$ yields $rank B^{T} = m$ , hence $rank B = m = k$ .

4.1step 2.1step 3.1

Steps 2.1 and 3.1 prove the local-constancy claim.

5.1step 4.1step 2.2∎

Claim 1 is step 4.1 and claim 2 is step 2.2.

Depends on

Used by

Numerical rank relative to a declared norm, scale, and tolerance Definition

Dependency tree · two levels

16 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)