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 wide Gaussian matrix has full row rank almost surely
Statement
Assume Countable Choice for the finite-dimensional Gaussian probability law. Let , , and let have iid standard real Gaussian or normalized complex Gaussian entries. Then almost surely.
Facts & Assumptions
Given: Countable Choice for the finite Gaussian law, and a finite matrix with the density and independence specified in Standard real and normalized complex Gaussian matrix laws.
Matrix entries have the stated product density, so each row is absolutely continuous with respect to finite-dimensional real-coordinate Lebesgue measure (Standard real and normalized complex Gaussian matrix laws).
Orthogonal or unitary changes of coordinates preserve this Gaussian law (Orthogonal and unitary invariance of Gaussian matrix blocks).
For a nonnegative product-measurable function, the product integral equals either iterated integral (Tonelli's theorem for nonnegative measurable functions on a sigma-finite product).
Under Countable Choice, finite-dimensional Lebesgue measure is countably subadditive (Assuming countable choice, is a sigma-algebra containing every elementary set and is a complete measure extending elementary volume).
Countable Choice supplies the Lebesgue measure used for the density (The Axiom of Countable Choice ()).
Proof
A fixed proper real or complex linear subspace has probability zero for one Gaussian row: choose an orthogonal/unitary coordinate change sending into , use [F2], and integrate the density over this coordinate subspace. It is Lebesgue-null: inside each bounded box it lies in a coordinate hyperplane coverable by a box of width and bounded remaining sides, whose volume tends to zero with ; [F4] makes that hyperplane null, and countable subadditivity covers the whole hyperplane.
Induct on the number of revealed rows. The first row is nonzero almost surely by step 1.1 applied to the zero subspace. The dependence event for rows is measurable because it is the common zero set of the finitely many minors. If the first rows are independent, their span is proper since ; for each fixed such tuple, step 1.1 makes the section of the event that row lies in their span null. The exceptional dependent tuples are null by induction. Applying [F3] to the nonnegative indicator of dependence gives probability zero for the first rows to be dependent. The induction is finite and concludes at .
Outside this null event, the rows are linearly independent, hence the row rank equals .
Depends on
- Standard real and normalized complex Gaussian matrix laws
- Orthogonal and unitary invariance of Gaussian matrix blocks
- Tonelli's theorem for nonnegative measurable functions on a sigma-finite product
- Assuming countable choice, $\mathcal{L}(\mathbb{R}^n)$ is a sigma-algebra containing every elementary set and $\lambda_n$ is a complete measure extending elementary volume
- The Axiom of Countable Choice ($\mathrm{AC}_\omega$)
Used by
- Exact range recovery on a rank-k matrix Example
- Affine second-moment bounds for normalized complex Gaussian block products Lemma
- Direct expected spectral bound for the normalized complex range finder Lemma
- Exact Frobenius moments of wide Gaussian pseudoinverses Lemma
- Expected spectral error of the real Gaussian range finder Theorem
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.
Sources
- Halko, Martinsson, and Tropp, Finding Structure with Randomness, §10.2 (standard reference, not scraped)
- Martinsson and Tropp, Randomized Numerical Linear Algebra: Foundations & Algorithms, §11.4.2 (standard reference, not scraped)