ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)verified 2026-10-22 (gpt-6.1-sol)

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.

A nontrivial three-column matrix with the nullspace property

Example

Let $A = (\begin{array}{ccc} 1 & - 1 & 0 \\ 1 & 0 & 1 \end{array}) \in M_{2 \times 3} (R)$ and $s = 1$ , using one-based coordinate labels $j = 1, 2, 3$ corresponding to library indices $j - 1$ . Then $\ker A = {λ (1, 1, - 1) : λ \in R}$ , $A$ satisfies the strict nullspace property of order $1$ , and every vector $x^{†} \in R^{3}$ with at most one nonzero coordinate is the unique minimizer of $\sum_{j = 1}^{3} ∣ z_{j} ∣$ subject to $A z = A x^{†}$ .

Example references

Strict nullspace property and coordinate conventions

Finite-dimensional one-norm

Exact recovery under the strict nullspace property

Facts & Assumptions

Given: The matrix $A = (\begin{array}{ccc} 1 & - 1 & 0 \\ 1 & 0 & 1 \end{array})$ and sparsity order $s = 1$ .

[F1]

The strict nullspace property: strict NSP requires $∥ h_{S} ∥_{1} < ∥ h_{S^{c}} ∥_{1}$ for each nonzero kernel vector and every $S$ with $∣ S ∣ \leq s$ .

[F2]

The $p$ -norms $∥ x ∥_{p}$ for rational $p \geq 1$ , and $∥ x ∥_{\infty}$ : the $ℓ_{1}$ norm is the sum of coordinate absolute values.

[F3]

Exact basis-pursuit recovery under the strict nullspace property: a matrix with strict NSP of order $s$ uniquely recovers every vector with at most $s$ nonzero coordinates by exact $ℓ_{1}$ minimization.

[F4]

Each $∥ \cdot ∥_{p}$ is a norm on $R^{n}$ , and the induced metrics are exactly $d_{1}$ , $d_{2}$ and $d_{\infty}$ of the published metric-spaces page: the defined $ℓ_{1}$ function is a norm on $R^{3}$ .

[F5]

The strict nullspace property: under its coordinate relabeling, $(A u)_{i} = \sum_{j = 1}^{n} A_{i j} u_{j}$ for each row $i$ .

Verification

1.1givenF5algebra

For $h = (u, v, w)$ , the row formula [F5] gives $A h = (u - v, u + w)$ , so $A h = 0$ exactly when $v = u$ and $w = - u$ . Hence $\ker A = {λ (1, 1, - 1) : λ \in R}$ .

2.1givenF1F2step 1.1algebra

Write a nonzero kernel vector as $h = λ (1, 1, - 1)$ with $λ \neq 0$ . If $S = \emptyset$ , then $∥ h_{S} ∥_{1} = 0 < 3 ∣ λ ∣ = ∥ h_{S^{c}} ∥_{1}$ . If $S$ is a singleton, then $∥ h_{S} ∥_{1} = ∣ λ ∣ < 2 ∣ λ ∣ = ∥ h_{S^{c}} ∥_{1}$ . These are all sets with $∣ S ∣ \leq 1$ , so [F1] holds.

3.1givenF2F3F4step 2.1∎

Applying [F3] with $s = 1$ now gives the claimed unique minimizer for every vector with at most one nonzero coordinate; [F2] identifies the objective formula as the $ℓ_{1}$ norm by [F4].

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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