Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A standard Gaussian matrix has full rank almost surely

Proved
GaussianMatrix.full_rank_ae

by tc · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

gaussian-matrixprobabilityrandom-matrix-theoryrandomized-numerical-linear-algebra

Let Γ∈Rp×m\Gamma\in\mathbb R^{p\times m}Γ∈Rp×m be a standard Gaussian matrix. Then, almost surely,

rank⁡Γ=min⁡{p,m}.\operatorname{rank}\Gamma=\min\{p,m\}.rankΓ=min{p,m}.

Equivalently, a wide (p≤mp\le mp≤m) Gaussian matrix has full row rank and ΓΓT\Gamma\Gamma^{\mathsf T}ΓΓT is invertible almost surely; a tall one has full column rank. This is the structural fact that makes the pseudoinverse Ω1†=Ω1T(Ω1Ω1T)−1\Omega_1^{\dagger}=\Omega_1^{\mathsf T}(\Omega_1\Omega_1^{\mathsf T})^{-1}Ω1†​=Ω1T​(Ω1​Ω1T​)−1 well defined with probability one in the analysis of randomized range finders, and that lets one treat (GGT)−1(GG^{\mathsf T})^{-1}(GGT)−1 as the inverse-Wishart matrix.

Formalization Note. rank is Mathlib's matrix rank over R\mathbb RR; the statement is a γp,m\gamma_{p,m}γp,m​-almost-everywhere equality, with no restriction on p,mp,mp,m (for p=0p=0p=0 or m=0m=0m=0 both sides are 000).

Preamble
import Definitions.Def_GaussianMatrix_basic

open MeasureTheory ProbabilityTheory
open scoped Matrix
Formal statement
namespace GaussianMatrix
theorem full_rank_ae (p m : ℕ) :
    ∀ᵐ G ∂(gaussianMatrix p m), (Matrix.of G).rank = min p m := by sorry
end GaussianMatrix
Source
N. Halko, P.-G. Martinsson, J. A. Tropp, *Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions*, SIAM Review 53(2), 2011, https://arxiv.org/abs/0909.4061 (v2), §10.2 p. 57, proof of Theorem 10.5: "the rows of a (fat) Gaussian matrix are almost surely in general position, so the k × (k + p) matrix Ω₁ has full row rank with probability one"; Appendix A.2 p. 65, proof of Proposition A.5: "the Wishart matrix GG* is invertible with probability one". Stated for arbitrary p×mp\times mp×m as rank⁡=min⁡(p,m)\operatorname{rank}=\min(p,m)rank=min(p,m).
Read-back

What the Lean code literally says, in plain math · claude-fable-5-1

Let p,mp, mp,m be natural numbers (explicit arguments; either may be 000), and let γp,m\gamma_{p,m}γp,m​ be the law of a p×mp \times mp×m array GGG with independent N(0,1)\mathcal{N}(0,1)N(0,1) entries. The statement asserts that for γp,m\gamma_{p,m}γp,m​-almost every GGG,

rank⁡(G)  =  min⁡(p,m),\operatorname{rank}(G) \;=\; \min(p, m),rank(G)=min(p,m),

where GGG is viewed as a real p×mp \times mp×m matrix and rank⁡\operatorname{rank}rank is Mathlib's matrix rank: the dimension (as a natural number) of the column space of GGG, i.e. of the range of the linear map x↦Gxx \mapsto Gxx↦Gx from Rm\mathbb{R}^mRm to Rp\mathbb{R}^pRp. "Almost every" means the set of arrays GGG for which rank⁡(G)≠min⁡(p,m)\operatorname{rank}(G) \ne \min(p,m)rank(G)=min(p,m) is contained in a γp,m\gamma_{p,m}γp,m​-null set; the equality is an equality of natural numbers, and min⁡\minmin is the minimum of the natural numbers ppp and mmm. Edge cases: if p=0p = 0p=0 or m=0m = 0m=0 the array space is a single point, the unique matrix has rank 0=min⁡(p,m)0 = \min(p,m)0=min(p,m), and the claim holds for that point.

Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by tc · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me