Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Standard Gaussian matrices: law, Frobenius and spectral norms, smallest singular value, pseudoinverse

Definition
GaussianMatrix_basic

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

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

This bundle fixes the shared vocabulary of the Gaussian Random Matrices mission series (namespace GaussianMatrix).

The Gaussian matrix law. For p,m∈Np,m\in\mathbb Np,m∈N, γp,m\gamma_{p,m}γp,m​ denotes the law of a p×mp\times mp×m matrix whose pmpmpm entries are independent standard normal N(0,1)\mathcal N(0,1)N(0,1) random variables. It is realized as the product measure ⨂i<p⨂j<mN(0,1)\bigotimes_{i<p}\bigotimes_{j<m}\mathcal N(0,1)⨂i<p​⨂j<m​N(0,1) on the function space Rp→Rm→R\mathbb R^{p}\to\mathbb R^{m}\to\mathbb RRp→Rm→R; a sample GGG is turned into a matrix by the identity map of(G)∈Rp×m\mathrm{of}(G)\in\mathbb R^{p\times m}of(G)∈Rp×m. It is a probability measure (instance provided).

Norms. For a real matrix AAA,

∥A∥F2=∑i,jAij2,∥A∥F=∥A∥F2,∥A∥=max⁡∥x∥2=1∥Ax∥2,\|A\|_F^2=\sum_{i,j}A_{ij}^2,\qquad \|A\|_F=\sqrt{\|A\|_F^2},\qquad \|A\|=\max_{\|x\|_2=1}\|Ax\|_2 ,∥A∥F2​=i,j∑​Aij2​,∥A∥F​=∥A∥F2​​,∥A∥=∥x∥2​=1max​∥Ax∥2​,

where ∥A∥\|A\|∥A∥ (the spectral norm, i.e. the largest singular value) is Mathlib's ℓ2→ℓ2\ell_2\to\ell_2ℓ2​→ℓ2​ operator norm (Matrix.Norms.L2Operator).

Smallest singular value. For a (tall) matrix A∈RN×nA\in\mathbb R^{N\times n}A∈RN×n,

σmin⁡(A)=inf⁡{∥Ax∥2:x∈Rn, ∥x∥2=1},\sigma_{\min}(A)=\inf\{\|Ax\|_2 : x\in\mathbb R^{n},\ \|x\|_2=1\},σmin​(A)=inf{∥Ax∥2​:x∈Rn, ∥x∥2​=1},

so that σmin⁡(A)\sigma_{\min}(A)σmin​(A) is the nnn-th singular value when N≥nN\ge nN≥n, and 000 when N<nN<nN<n. For a wide matrix GGG the usual σmin⁡(G)\sigma_{\min}(G)σmin​(G) is σmin⁡(GT)\sigma_{\min}(G^{\mathsf T})σmin​(GT).

Pseudoinverse of a full-row-rank matrix. For G∈Rm×nG\in\mathbb R^{m\times n}G∈Rm×n,

G†=GT(GGT)−1,G^{\dagger}=G^{\mathsf T}(GG^{\mathsf T})^{-1},G†=GT(GGT)−1,

which is the Moore–Penrose pseudoinverse whenever GGTGG^{\mathsf T}GGT is invertible (i.e. GGG has full row rank).

These are the objects appearing in the Gaussian moment identities of Halko–Martinsson–Tropp and Tropp–Webber and in Gordon's theorem on extreme singular values.

Formalization Note. Mathlib's matrix inverse is total: (GGT)−1=0(GG^{\mathsf T})^{-1}=0(GGT)−1=0 when GGTGG^{\mathsf T}GGT is singular, so G†=0G^{\dagger}=0G†=0 on that null set. The infimum defining σmin⁡\sigma_{\min}σmin​ is over the unit sphere of Rn\mathbb R^nRn; for n=0n=0n=0 the sphere is empty and the real-valued infimum is 000 by Lean's convention. Sample spaces are function types rather than Matrix types because Mathlib equips the former, not the latter, with the product σ\sigmaσ-algebra.

Definition code
import Mathlib

/-!
# Standard Gaussian matrices: basic definitions

Shared vocabulary for the "Gaussian Random Matrices" mission series.

* `GaussianMatrix.gaussianMatrix p m` — the law of a `p × m` matrix with independent
  standard normal entries, as the product measure on `Fin p → Fin m → ℝ`. A sample `G` is
  viewed as a matrix via `Matrix.of G`.
* `GaussianMatrix.frobSq`, `frobNorm` — squared Frobenius norm `∑ᵢⱼ Aᵢⱼ²` and its square root.
* `GaussianMatrix.specNorm` — the spectral norm (largest singular value), i.e. Mathlib's
  `ℓ₂ → ℓ₂` operator norm `Matrix.Norms.L2Operator`.
* `GaussianMatrix.sMin` — the smallest singular value of a tall `N × n` matrix,
  `inf { ‖A x‖₂ : ‖x‖₂ = 1 }` (for a wide matrix apply it to the transpose).
* `GaussianMatrix.pinvR` — `Gᵀ (G Gᵀ)⁻¹`, the Moore–Penrose pseudoinverse of a matrix with
  full row rank (Mathlib's `⁻¹` is total, returning `0` on a singular input).
-/

open MeasureTheory ProbabilityTheory
open scoped Matrix Matrix.Norms.L2Operator

namespace GaussianMatrix

/-- The law of a `p × m` standard Gaussian matrix: independent `N(0,1)` entries, as a product
measure on `Fin p → Fin m → ℝ`. `Matrix.of G` is the matrix view of a sample `G`. -/
noncomputable def gaussianMatrix (p m : ℕ) : Measure (Fin p → Fin m → ℝ) :=
  Measure.pi fun _ : Fin p => Measure.pi fun _ : Fin m => gaussianReal 0 1

instance gaussianMatrix_isProbabilityMeasure (p m : ℕ) :
    IsProbabilityMeasure (gaussianMatrix p m) := by
  unfold gaussianMatrix; infer_instance

/-- Squared Frobenius norm `‖A‖_F² = ∑ᵢ ∑ⱼ Aᵢⱼ²`. -/
def frobSq {m n : Type*} [Fintype m] [Fintype n] (A : Matrix m n ℝ) : ℝ :=
  ∑ i, ∑ j, A i j ^ 2

/-- Frobenius norm `‖A‖_F = √(∑ᵢⱼ Aᵢⱼ²)`. -/
noncomputable def frobNorm {m n : Type*} [Fintype m] [Fintype n] (A : Matrix m n ℝ) : ℝ :=
  Real.sqrt (frobSq A)

/-- Spectral norm `‖A‖ = max_{‖x‖₂ = 1} ‖A x‖₂` (largest singular value): Mathlib's
`ℓ₂ → ℓ₂` operator norm of a real matrix. -/
noncomputable def specNorm {m n : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n]
    (A : Matrix m n ℝ) : ℝ := ‖A‖

/-- Smallest singular value of a tall matrix `A : Matrix N n`:
`σ_min(A) = inf { ‖A x‖₂ : x ∈ ℝⁿ, ‖x‖₂ = 1 }` (equal to `0` when `n = 0`, by the real
convention `inf ∅ = 0`). For a wide matrix use `sMin Aᵀ`. -/
noncomputable def sMin {N n : Type*} [Fintype N] [Fintype n] (A : Matrix N n ℝ) : ℝ :=
  ⨅ x : {x : n → ℝ // x ⬝ᵥ x = 1}, Real.sqrt ((A *ᵥ x.1) ⬝ᵥ (A *ᵥ x.1))

/-- Right pseudoinverse `G† = Gᵀ (G Gᵀ)⁻¹` of a matrix `G : Matrix m n`; it is the Moore–Penrose
pseudoinverse whenever `G Gᵀ` is invertible (full row rank), and `0` otherwise. -/
noncomputable def pinvR {m n : Type*} [Fintype m] [Fintype n] [DecidableEq m]
    (G : Matrix m n ℝ) : Matrix n m ℝ :=
  Gᵀ * (G * Gᵀ)⁻¹

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.1 p. 55 (standard Gaussian matrix, rotational invariance) and §A.2 p. 64–65 (pseudoinverse G†G^\daggerG†, ∥G†∥F2=tr⁡(GG∗)−1\|G^\dagger\|_F^2=\operatorname{tr}(GG^*)^{-1}∥G†∥F2​=tr(GG∗)−1); R. Vershynin, *Introduction to the non-asymptotic analysis of random matrices*, Chapter 5 of Compressed Sensing: Theory and Applications (Y. Eldar, G. Kutyniok, eds.), Cambridge University Press, 2012, https://arxiv.org/abs/1011.3027 (v7), §5.1 p. 2 (singular values smin⁡(A)=inf⁡∥x∥2=1∥Ax∥2s_{\min}(A)=\inf_{\|x\|_2=1}\|Ax\|_2smin​(A)=inf∥x∥2​=1​∥Ax∥2​, smax⁡(A)=∥A∥s_{\max}(A)=\|A\|smax​(A)=∥A∥).
Read-back

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

This bundle introduces six pieces of vocabulary; nothing is proved beyond one typeclass fact.

Gaussian matrix law. For natural numbers p,mp, mp,m (either may be 000), γp,m\gamma_{p,m}γp,m​ (written gaussianMatrix p m) is a measure on the space of functions {0,…,p−1}→{0,…,m−1}→R\{0,\dots,p-1\} \to \{0,\dots,m-1\} \to \mathbb{R}{0,…,p−1}→{0,…,m−1}→R, i.e. on real p×mp \times mp×m arrays G=(Gij)G = (G_{ij})G=(Gij​) indexed by i∈{0,…,p−1}i \in \{0,\dots,p-1\}i∈{0,…,p−1}, j∈{0,…,m−1}j \in \{0,\dots,m-1\}j∈{0,…,m−1}. It is the product measure

γp,m  =  ⨂i=0p−1  ⨂j=0m−1N(0,1),\gamma_{p,m} \;=\; \bigotimes_{i=0}^{p-1}\;\bigotimes_{j=0}^{m-1} \mathcal{N}(0,1),γp,m​=i=0⨂p−1​j=0⨂m−1​N(0,1),

where N(0,1)\mathcal{N}(0,1)N(0,1) is Mathlib's Gaussian measure on R\mathbb{R}R with mean 000 and variance 111. The sigma-algebra is the product (coordinatewise Borel) sigma-algebra. The bundle also records that γp,m\gamma_{p,m}γp,m​ is a probability measure. An array GGG is identified with a matrix p×mp \times mp×m via the type-level bijection Matrix.of (and back via its inverse); this bijection does not change the underlying data. Edge case: if p=0p = 0p=0 or m=0m = 0m=0, the underlying space has exactly one point (the empty array) and γp,m\gamma_{p,m}γp,m​ is the unit point mass on it.

Squared Frobenius norm. For finite index types m,nm, nm,n and a real matrix A∈Rm×nA \in \mathbb{R}^{m \times n}A∈Rm×n,

frobSq⁡(A)  =  ∥A∥F2  =  ∑i∈m∑j∈nAij2∈R.\operatorname{frobSq}(A) \;=\; \|A\|_F^2 \;=\; \sum_{i \in m} \sum_{j \in n} A_{ij}^2 \in \mathbb{R}.frobSq(A)=∥A∥F2​=i∈m∑​j∈n∑​Aij2​∈R.

If mmm or nnn is empty this is the empty sum, 000.

Frobenius norm. frobNorm⁡(A)=frobSq⁡(A)\operatorname{frobNorm}(A) = \sqrt{\operatorname{frobSq}(A)}frobNorm(A)=frobSq(A)​, using Mathlib's real square root (which returns 000 on negative input; the argument here is a sum of squares, so this never bites).

Spectral norm. For finite index types m,nm, nm,n with decidable equality and A∈Rm×nA \in \mathbb{R}^{m \times n}A∈Rm×n, specNorm⁡(A)=∥A∥\operatorname{specNorm}(A) = \|A\|specNorm(A)=∥A∥ where ∥⋅∥\|\cdot\|∥⋅∥ is Mathlib's ℓ2→ℓ2\ell^2 \to \ell^2ℓ2→ℓ2 operator norm on matrices (the scoped instance Matrix.Norms.L2Operator): the operator norm of AAA regarded as a linear map from Euclidean Rn\mathbb{R}^nRn to Euclidean Rm\mathbb{R}^mRm, i.e. sup⁡∥x∥2≤1∥Ax∥2\sup_{\|x\|_2 \le 1} \|Ax\|_2sup∥x∥2​≤1​∥Ax∥2​, which is the largest singular value of AAA. It is 000 when mmm or nnn is empty.

Smallest singular value (tall convention). For finite index types N,nN, nN,n and A∈RN×nA \in \mathbb{R}^{N \times n}A∈RN×n,

sMin⁡(A)  =  inf⁡x∈Rnx⋅x=1(Ax)⋅(Ax)  =  inf⁡∥x∥2=1∥Ax∥2,\operatorname{sMin}(A) \;=\; \inf_{\substack{x \in \mathbb{R}^{n} \\ x \cdot x = 1}} \sqrt{(Ax)\cdot(Ax)} \;=\; \inf_{\|x\|_2 = 1} \|Ax\|_2 ,sMin(A)=x∈Rnx⋅x=1​inf​(Ax)⋅(Ax)​=∥x∥2​=1inf​∥Ax∥2​,

where x⋅y=∑ixiyix \cdot y = \sum_i x_i y_ix⋅y=∑i​xi​yi​ is the dot product and AxAxAx the matrix–vector product. The infimum is Lean's real infimum over the subtype of vectors xxx with x⋅x=1x \cdot x = 1x⋅x=1: when nnn is empty, the only vector is 000 and 0⋅0=0≠10 \cdot 0 = 0 \ne 10⋅0=0=1, so the index set is empty and, by the convention inf⁡∅=0\inf \varnothing = 0inf∅=0 in R\mathbb{R}R, sMin⁡(A)=0\operatorname{sMin}(A) = 0sMin(A)=0. When nnn is nonempty the set of values is nonempty and bounded below by 000, so this is the genuine infimum. When NNN is empty (and nnn is not), every AxAxAx is the empty vector, so sMin⁡(A)=0\operatorname{sMin}(A) = 0sMin(A)=0. No decidable-equality assumptions are needed. (The docstring says to apply this to ATA^{\mathsf T}AT for wide matrices; the definition itself does nothing special for wide inputs.)

Right pseudoinverse. For finite index types m,nm, nm,n with decidable equality on mmm and G∈Rm×nG \in \mathbb{R}^{m \times n}G∈Rm×n,

pinvR⁡(G)  =  GT (GGT)−1∈Rn×m,\operatorname{pinvR}(G) \;=\; G^{\mathsf T}\,(G G^{\mathsf T})^{-1} \in \mathbb{R}^{n \times m},pinvR(G)=GT(GGT)−1∈Rn×m,

where −1{}^{-1}−1 is Mathlib's total matrix inverse on square matrices: it equals the true inverse when det⁡(GGT)≠0\det(GG^{\mathsf T}) \ne 0det(GGT)=0 and is the zero matrix otherwise. Hence pinvR⁡(G)=0\operatorname{pinvR}(G) = 0pinvR(G)=0 whenever GGTGG^{\mathsf T}GGT is singular (in particular whenever GGG does not have full row rank, e.g. when nnn is nonempty but G=0G = 0G=0, or when m>nm > nm>n). Edge cases: if mmm is empty, GGTGG^{\mathsf T}GGT is the 0×00 \times 00×0 matrix, whose determinant is 111 and whose inverse is the (empty) identity, and pinvR⁡(G)\operatorname{pinvR}(G)pinvR(G) is the unique n×0n \times 0n×0 matrix; if nnn is empty, pinvR⁡(G)\operatorname{pinvR}(G)pinvR(G) is the unique 0×m0 \times m0×m matrix.

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

  • Endorsed by mikedeng1 · Nov 8, 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