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
Quantum Information·Captain: mikedeng1

Improvements in Quantum SDP-Solving with Applications 1: A Unitary Preparing a Purification of a Subnormalized Density Operator ϱ Gives an Exact (1, w+a+1, 0)-Block-Encoding of ϱResearch Paper

Quantum algorithms for semidefinite programming need a way to use an input matrix inside a quantum circuit. In the quantum state input model, an oracle prepares a purification of a density operator. In the quantum operator input model, a unitary instead exposes that operator as a block of a larger unitary. The two kinds of access serve different…

8 thms3 active usersReviewed
🏆Completed
Control TheoryConvex OptimizationOptimization·Captain: mikedeng1

Quadratic Matrix Inequalities with Applications to Data-Based Control II: Matrix Finsler's Lemma — Z⁰ᵣ(N) ⊆ Zᵣ(M) iff M − αN ⪰ 0 for Some α ≥ 0Research Paper

Finsler's lemma (P. Finsler, 1937) states that for symmetric matrices M,N∈SnM,N\in\mathbb S^nM,N∈Sn, the quadratic form x⊤Mxx^\top Mxx⊤Mx is positive on every nonzero xxx with x⊤Nx=0x^\top Nx=0x⊤Nx=0 if and only if M−αN>0M-\alpha N>0M−αN>0 for some real α\alphaα. Together with the S-lemma of Yakubovich it is one of the basic tools for converting a statement about all vectors satisfying a quadratic…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOptimization·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 1: Gauss–Seidel Splitting of the HB and NAG Transforms Has ρ(E(α, G)) ≤ 1/√(1 + 2α) If 0 < α ≤ 2/√κ(A)Research Paper

Accelerated first-order methods, the heavy-ball method of Polyak and Nesterov's accelerated gradient (NAG) method, reach an error ε\varepsilonε on a μ\muμ-strongly convex, LLL-smooth problem in O(κlog⁡(1/ε))O(\sqrt{\kappa}\log(1/\varepsilon))O(κ​log(1/ε)) gradient steps, κ=L/μ\kappa=L/\muκ=L/μ, against O(κlog⁡(1/ε))O(\kappa\log(1/\varepsilon))O(κlog(1/ε)) for plain gradient descent. A long line of work has tried to explain…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsOptimizationTheoretical Computer Science·Captain: mikedeng1

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature II: Column-Subset Selection Has Total Curvature at Most 1 − 1/κ(A)²Research Paper

The column-subset selection problem (CSSP) asks for kkk columns of a real matrix AAA whose span approximates all of AAA as well as possible in squared Frobenius norm. It is a basic primitive of low-rank approximation, feature selection and numerical linear algebra, studied both for its exact complexity and for approximation algorithms (see Boutsidis, Drineas and…

11 thms3 active usersReviewed
🏆Completed
Algebraic TopologyCombinatorics·Captain: mikedeng1

Isoperimetric Inequalities in Simplicial Complexes 1: For a Finite d-Complex with a Complete Skeleton, the Spectral Gap Is at Most the Cheeger Constant, λ(X) ≤ h(X)Research Paper

For a finite graph, the Cheeger constant measures how hard it is to cut the vertex set into two pieces, and the spectral gap of the graph Laplacian measures how fast random walks mix. The two Cheeger inequalities (Dodziuk 1984; Alon and Milman 1985; Alon 1986) bound each quantity by a function of the other, and they underlie the theory of expander graphs,…

10 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Optimization-Based Algorithms for Tensor Decompositions: Canonical Polyadic Decomposition, Decomposition in Rank-(Lr, Lr, 1) Terms, and a New Generalization 1: Block Structure of the Gramian JᴴJResearch Paper

Tensor decompositions express a multiway array as a sum of simple terms. The canonical polyadic decomposition (CPD) writes an NNN-th order tensor T∈CI1×⋯×IN\mathcal T\in\mathbb C^{I_1\times\cdots\times I_N}T∈CI1​×⋯×IN​ as a sum of RRR outer products of vectors; block term decompositions replace each rank-one term by a term of higher multilinear rank. These models are used in signal…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization 3: Hankel-Matrix SDP Lower Bounds for Minimizing a Power Sum Subject to Fixed Lower Power SumsResearch Paper

Many polynomial optimization problems are invariant under permuting the variables: the objective and the constraints are symmetric polynomials. Lasserre's moment–sum-of-squares hierarchy solves such problems by a sequence of semidefinite programs whose size grows quickly with the number of variables and the degree, and symmetry is the main tool for…

6 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Phase Recovery, MaxCut and Complex Semidefinite Programming 1: For Injective A, Nonzero b and Solvable |Ax| = b, PhaseCutMod Is Tight Whenever PhaseLift IsResearch Paper

Phase recovery (also called phase retrieval) asks to reconstruct a complex signal from the magnitudes of linear measurements of it, the phases being lost. It arises wherever detectors record intensities only: X-ray crystallography, diffraction imaging, astronomy and optics, where a sensor measures ∣⟨ai,x⟩∣2|\langle a_i, x\rangle|^2∣⟨ai​,x⟩∣2 and not ⟨ai,x⟩\langle a_i, x\rangle⟨ai​,x⟩. The…

9 thms3 active usersReviewed
🏆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
🏆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
🏆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
🏆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
PreviousPage 4 of 9Next

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