Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Linear algebra

332 missions · 207 completed

Missions

Open125Completed207All332
🏆Completed
Numerical AnalysisProbabilityRandom Matrix Theory·Captain: mikedeng1

An Introduction to Matrix Concentration Inequalities II: A Random Row-and-Column Submatrix Z = PBR Satisfies E‖Z‖² ≤ 3(p/d)(r/n)‖B‖² Plus Logarithmic Row, Column and Entry TermsTextbook

Large matrices are often reduced by retaining only some rows or columns. The reduced matrix is cheaper to store and apply, but its spectral norm can be distorted by a single unusually large row, column, or entry. A useful estimate must show both the average effect of sampling and the cost of these local concentrations. In §5.2 of Tropp's monograph, matrix…

11 thms3 active usersReviewed
🏆Completed
CombinatoricsProbabilityRandom Matrix Theory·Captain: mikedeng1

An Introduction to Matrix Concentration Inequalities I: A Matrix Gaussian Series Satisfies v(Z) ≤ E‖Z‖² ≤ 2v(Z)(1 + log(d₁ + d₂))Textbook

Random matrices arise when observations, signs, or model coefficients fluctuate. Their spectral norm measures the largest amplification they can cause to a vector. A bound on that norm can turn entrywise randomness into a statement about the behavior of an entire linear operator. Tropp's chapter develops a common framework for Gaussian and Rademacher sums…

8 thms3 active usersReviewed
🏆Completed
Mathematical PhysicsQuantum Information·Captain: mikedeng1

Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians 1: Lieb–Robinson Bound ‖[A(t),B]‖ ≤ (2/√η)‖A‖‖B‖(e^{ζ|t|√(8η)}−1)Σ_{x∈X}e^{−μ dist(x,Y)} Under Small CommutatorsResearch Paper

A local quantum system is built from degrees of freedom placed at sites of a lattice. Its Hamiltonian may contain many terms, each acting on a small group of sites. Even though a term is local, time evolution can spread an observable beyond its original support. A Lieb–Robinson bound limits the size of a commutator between the evolved observable and one…

9 thms3 active usersReviewed
OptimizationQuantum Information·Captain: mikedeng1

The Sum-of-Squares Hierarchy on the Sphere, and Applications in Quantum Information Theory II: The Dual of the ℓ-th DPS Cone Is the Set of M for Which ‖y‖^{2(ℓ−1)}·p_M Is a Real Sum of SquaresResearch Paper

Deciding whether a bipartite quantum state is entangled is a basic computational problem of quantum information theory, and it is NP-hard in general (Gurvits 2003). The most widely used family of tests is the DPS hierarchy of Doherty, Parrilo and Spedalieri (DPS 2002, DPS 2004): a sequence of semidefinite programs, indexed by an integer level ℓ≥1\ell\ge1ℓ≥1,…

9 thms3 active usersReviewed
Numerical AnalysisProbabilityTheoretical Computer Science·Captain: mikedeng1

Low Rank Approximation and Regression in Input Sparsity Time 1: A Sparse Embedding Matrix with O((r/ε)⁴ log²(r/ε)) Rows Is a (1 ± ε) Subspace Embedding for a Rank-r Matrix with Probability 9/10Research Paper

Many matrix algorithms spend most of their time reading their input. A matrix with few nonzero entries should admit routines whose cost scales with that number, rather than with the product of its dimensions. Clarkson and Woodruff study random maps that compress a matrix before a regression or low rank approximation calculation while retaining the geometric…

9 thms3 active usersReviewed
🏆Completed
Numerical AnalysisQuantum Information·Captain: mikedeng1

Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision I: A Truncated Odd Chebyshev Series Is 2ε-Close to 1/x on [−1, −1/κ] ∪ [1/κ, 1]Research Paper

The quantum linear systems problem asks, given a sparse Hermitian N×NN \times NN×N matrix AAA with condition number κ\kappaκ and a procedure preparing a state ∣b⟩|b\rangle∣b⟩, to prepare a state close to A−1∣b⟩/∥A−1∣b⟩∥A^{-1}|b\rangle / \|A^{-1}|b\rangle\|A−1∣b⟩/∥A−1∣b⟩∥. Harrow, Hassidim and Lloyd (2009) gave a quantum algorithm whose running time is polynomial in log⁡N\log NlogN and κ\kappaκ but grows like …

6 thms3 active usersReviewed
🏆Completed
Control TheoryDynamical Systems·Captain: mikedeng1

Lyapunov Equations, Energy Functionals, and Model Order Reduction of Bilinear and Stochastic Systems 1: States Reached from 0 Stay in Im P and Ker Q Gives Zero Output, for Gramians P, Q ≥ 0 of (3.6)Research Paper

Balanced truncation is the standard method for reducing the state dimension of a linear control system while keeping its input–output behaviour: states that are both hard to reach and hard to observe are discarded. Its justification rests on two Gramians, the solutions PPP and QQQ of a pair of Lyapunov equations, whose quadratic forms measure how much input…

8 thms3 active usersReviewed
🏆Completed
AlgebraCombinatoricsDiscrete Geometry·Captain: mikedeng1

Generalising the Scattered Property of Subspaces 2: If h + 1 Divides r and n ≥ h + 1, Maximum h-Scattered 𝔽_q-Subspaces of V(r, qⁿ) of Dimension rn/(h + 1) ExistResearch Paper

A scattered subspace is an Fq\mathbb F_qFq​-subspace UUU of an Fqn\mathbb F_{q^n}Fqn​-vector space VVV that meets every one-dimensional Fqn\mathbb F_{q^n}Fqn​-subspace of VVV in an Fq\mathbb F_qFq​-subspace of dimension at most one. Scattered subspaces produce scattered linear sets in projective spaces over finite fields, and through them two-intersection sets, two-weight codes,…

10 thms3 active usersReviewed
🏆Completed
Complexity TheoryGraph TheoryOptimization+1·Captain: mikedeng1

Most Tensor Problems Are NP-Hard 5: The Stability Number Is Read Off the Largest Eigenvalue of an Explicit Symmetric 3-TensorResearch Paper

For a real symmetric matrix, the largest eigenvalue is the maximum of the quadratic form x⊤Ax\mathbf x^\top A\mathbf xx⊤Ax on the unit sphere, and it is computable to any accuracy in polynomial time. Tensor eigenvalues, introduced independently by Lim (2005) and Qi (2005), extend this picture to higher order: they are the stationary values of the cubic form …

8 thms3 active usersReviewed
🏆Completed
Complexity TheoryGraph TheoryOptimization+1·Captain: mikedeng1

Most Tensor Problems Are NP-Hard 3: The Clique Number Is the Unique l for Which an Explicit Graph Tensor Has Spectral Norm 1Research Paper

The spectral norm of a matrix, its largest singular value, is computable in polynomial time to any accuracy. Its analogue for 3-tensors appears in the analysis of multilinear systems, in the best rank-1 approximation of a data array, in quantum information (the geometric measure of entanglement), and in the injective norm of tensor products. Hillar and Lim, …

11 thms3 active usersReviewed
🏆Completed
ProbabilityRandom Matrix Theory·Captain: mikedeng1

User-Friendly Tail Bounds for Sums of Random Matrices II: Matrix Gaussian and Rademacher Series Have Subgaussian Tails with Variance Parameter ‖Σ A_k²‖Research Paper

A matrix Gaussian series ∑kγkAk\sum_k \gamma_k A_k∑k​γk​Ak​, a sum of fixed self-adjoint matrices each multiplied by an independent standard normal variable, is the simplest sum of independent random matrices. It already appears in the analysis of random designs, in compressed sensing, in randomized numerical linear algebra and in quantum information, wherever one needs…

8 thms3 active usersReviewed
🏆Completed
ProbabilityRandom Matrix Theory·Captain: mikedeng1

User-Friendly Tail Bounds for Sums of Random Matrices I: The Master Tail Bound — the Largest Eigenvalue of an Independent Sum Is Controlled by the Sum of the Matrix Cumulant Generating FunctionsResearch Paper

Sums of independent random matrices appear wherever a large matrix is built from random pieces: sample covariance matrices in statistics, random sparsification and sampling in numerical linear algebra, random graphs and their Laplacians, and compressed sensing. The basic question is how far the largest eigenvalue of such a sum can stray above its typical…

6 thms3 active usersReviewed
AnalysisProbabilityRandom Matrix Theory·Captain: mikedeng1

User-Friendly Tail Bounds for Sums of Random Matrices V: The Matrix Azuma Inequality for Adapted Sequences with Semidefinite Bounds on the Squared DifferencesResearch Paper

Sums of random matrices appear throughout numerical linear algebra, statistics, combinatorics and quantum information: randomized sketching and sparsification, covariance estimation, graph sparsifiers, and the analysis of random features all reduce to controlling the largest eigenvalue of a sum of random self-adjoint matrices. Scalar concentration…

10 thms3 active usersReviewed
Control TheoryDynamical SystemsGraph Theory·Captain: mikedeng1

Synchronization and Transient Stability in Power Networks and Nonuniform Kuramoto Oscillators 2: λ₂(L(P_ij cos φ_ij)) > λ_critical Gives Phase Cohesiveness and Exponential Frequency SynchronizationResearch Paper

Transient stability of a power grid asks whether the generators of the network return to synchronous operation after a large disturbance such as a fault or a line trip. In the classical network-reduced model the rotor angles obey second-order swing equations, and stability certificates usually come from energy functions evaluated numerically. Dörfler and…

14 thms3 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Spectral Sparsification of Graphs 3: Sparsifying the Contraction and Pulling It Back Approximates a Graph with Heavy Intra-Part Edges to Within (1+ε)(1+1/c)²Research Paper

A spectral sparsifier of a weighted graph GGG is a graph G~\widetilde GG on the same vertices, with few edges, whose Laplacian quadratic form is within a factor σ\sigmaσ of that of GGG on every vector. Spielman and Teng introduced the notion in their work on nearly-linear-time solvers for symmetric diagonally dominant linear systems (Spielman–Teng 2004; arXiv:0808.41…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues: If m > k(n − k), Extreme Optima of Affine EV_k Have λ_k = λ_{k+1} with Multiplicity ≥ n − τResearch Paper

Minimizing the sum of the kkk largest eigenvalues of a symmetric matrix that depends affinely on parameters is a basic problem of eigenvalue optimization (survey: A. S. Lewis and M. L. Overton, Eigenvalue optimization, Acta Numerica 5, 1996, doi:10.1017/S0962492900002646). Its objective is convex, and fkf_kfk​ is differentiable at BBB exactly when …

14 thms3 active usersReviewed
🏆Completed
Graph TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

Spectral Sparsification of Graphs 1: Sampling Each Edge of a High-Conductance Graph with Probability min(1, Υ/min(dᵢ, dⱼ)) Gives a (1+ε)-Spectral Approximation with Few EdgesResearch Paper

A spectral sparsifier of a graph is a much sparser weighted graph whose Laplacian quadratic form is within a factor σ\sigmaσ of the original on every vector. Spielman and Teng introduced the notion in Spectral Sparsification of Graphs as a strengthening of the cut sparsifiers of Benczúr and Karger: a spectral sparsifier preserves every cut, and in addition…

13 thms3 active usersReviewed
🏆Completed
Graph TheoryProbabilityRandom Matrix Theory+1·Captain: mikedeng1

Graph Sparsification by Effective Resistances 1: Sampling O(n log n/ε²) Edges by Effective Resistance Yields a (1±ε) Spectral Sparsifier with Probability 1/2Research Paper

Many graph algorithms run in time proportional to the number of edges. A sparsifier of a weighted graph GGG is a graph HHH on the same vertices with far fewer edges that approximates GGG for the purpose at hand, so that the algorithm can be run on HHH instead. Benczúr and Karger (1996) showed that every graph has a sparsifier with O(nlog⁡n/ε2)O(n\log n/\varepsilon^2)O(nlogn/ε2) edges…

9 thms3 active usersReviewed
🏆Completed
Markov ChainQuantum Information·Captain: mikedeng1

Search via Quantum Walk 2: Phase Estimation Repeated k Times on the Szegedy Walk W(P) Fixes |π⟩ and Reflects A + B ⊖ |π⟩ up to Error 2^{1−k}Research Paper

Many classical search algorithms are random walks: a Markov chain PPP on a finite state space XXX is run until it hits a marked state. Szegedy (2004) attached to every such chain a unitary quantum walk W(P)W(P)W(P), and Magniez, Nayak, Roland and Santha (SIAM J. Comput. 2011, arXiv:quant-ph/0608026) used it to search quadratically faster than the classical walk for…

11 thms3 active usersReviewed
Convex OptimizationMachine LearningStatistics·Captain: mikedeng1

Nuclear-Norm Penalization and Optimal Rates for Noisy Low-Rank Matrix Completion 2: If λ ≥ 3‖M‖∞ on a Linear Subspace, a Sharp Oracle Inequality with the Restricted Constant μ₅(A)Research Paper

Estimating a large matrix that is approximately low rank from a few noisy linear measurements is a basic problem of high-dimensional statistics. It covers matrix completion (recovering a ratings table from a small sample of entries), multi-task regression and quantum state tomography. The standard estimator penalizes the nuclear norm, the sum of the…

14 thms3 active usersReviewed
🏆Completed
Quantum Information·Captain: marwahaha

Exact Fourier certificates for complex Hadamard matrices of order sixOpen Problem

Character sums express phase constraints on complex Hadamard matrices. In dimension six these constraints also bear on how many mutually unbiased bases can coexist. The pinned manuscript supplies the research context.

33 thms3 active usersReviewed
🏆Completed
AnalysisFunctional Analysis·Captain: wurtle

The complete Crouzeix theorem: optimal similarity and a common positive boundary representationResearch Paper

For a square matrix AAA, the spectrum alone does not control the size of p(A)p(A)p(A): a nonzero nilpotent matrix has spectrum {0}\{0\}{0} yet ∥A∥>0\|A\|>0∥A∥>0. The numerical range W(A)={u∗Au: ∥u∥=1}W(A)=\{u^*Au:\ \|u\|=1\}W(A)={u∗Au: ∥u∥=1} is a compact convex set containing the spectrum (Toeplitz–Hausdorff), and it does retain enough information. Crouzeix's conjecture (2004) asserts that for every polynomial ppp,

10 thms3 active usersReviewed
🏆Completed
AnalysisFunctional Analysis·Captain: wurtle

A direct proof of the complete Crouzeix inequalityResearch Paper

For a square matrix AAA, the spectrum alone does not control the size of p(A)p(A)p(A): a nonzero nilpotent matrix has spectrum {0}\{0\}{0} yet ∥A∥>0\|A\|>0∥A∥>0. The numerical range W(A)={u∗Au: ∥u∥=1}W(A)=\{u^*Au:\ \|u\|=1\}W(A)={u∗Au: ∥u∥=1} is a compact convex set containing the spectrum (Toeplitz–Hausdorff), and it does retain enough information. Crouzeix's conjecture (2004) asserts that for every polynomial ppp,

47 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Flows and Decompositions of Games: Harmonic and Potential Games 4: Changing Only the Nonstrategic Component Makes the Pure Nash Equilibria Coincide with the Pareto Optimal ProfilesResearch Paper

A finite strategic game can be changed in ways that no player can detect strategically. Adding to player mmm's utility any function that does not depend on player mmm's own strategy leaves every unilateral comparison "is strategy aaa better for me than strategy bbb, given what the others do?" unchanged, so it leaves every best response and every pure Nash…

11 thms3 active usersReviewed
Numerical AnalysisOptimization·Captain: mikedeng1

The Primal-Dual Active Set Strategy as a Semismooth Newton Method IV: Global Convergence for Small Perturbations of M-MatricesResearch Paper

Obstacle problems, contact problems and control-constrained optimal control problems lead, after discretization, to complementarity systems of the form "find y≤ψy \le \psiy≤ψ and λ≥0\lambda \ge 0λ≥0 with Ay+λ=fAy + \lambda = fAy+λ=f and λi(yi−ψi)=0\lambda_i(y_i - \psi_i) = 0λi​(yi​−ψi​)=0". The primal-dual active set strategy solves such systems by guessing which constraints are active, solving one linear…

10 thms3 active usersReviewed
PreviousPage 6 of 14Next

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