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
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
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Semidefinite Programming Relaxations for Semialgebraic Problems 2: A Feasible Solution of the SDPs (7.7) Certifies That M Is Copositive, and the Test Is at Least as Strong as M = P + NResearch Paper

A real symmetric matrix is copositive when its quadratic form is nonnegative on the nonnegative orthant. Copositive matrices appear wherever a quadratic objective meets sign constraints: standard quadratic programs over the simplex, linear complementarity problems, and conic reformulations of combinatorial problems such as the stability number of a graph.…

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

The Primal-Dual Active Set Strategy as a Semismooth Newton Method II: Global Convergence and Monotonicity for M-MatricesResearch Paper

Obstacle problems, contact problems and box-constrained quadratic programs share one finite-dimensional core: the linear complementarity problem "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". After discretization by finite differences or piecewise linear finite elements, the matrix AAA is typically an M-matrix,…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryGraph Theory·Captain: mikedeng1

The Geometry of Graphs and Some of Its Algorithmic Applications 4: The m-Cube Has Isometric Dimension mResearch Paper

A finite graph has distances defined by the lengths of its shortest paths. Representing those distances inside a normed vector space lets geometric language describe a combinatorial object, but the number of coordinates required can depend sharply on the graph. The isometric dimension asks for the smallest dimension of any real normed space that preserves…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Strongly Regular Generalized Equations IV: Strong Second-Order Sufficiency and Linearly Independent Binding Gradients Make the KKT Generalized Equation Strongly RegularResearch Paper

A nonlinear program is rarely solved once. Its data are estimated, rounded, or varied on purpose in a parametric study, and an algorithm such as sequential quadratic programming replaces it at every iteration by a nearby linearised problem. Both uses need the same fact: near a solution, the Karush–Kuhn–Tucker (KKT) system should have exactly one solution…

9 thms3 active usersReviewed
🏆Completed
Number Theory·Captain: mikedeng1

Factoring Polynomials with Rational Coefficients I: A Reduced Lattice Basis Satisfies |b_j|² ≤ 2^{n−1}·max|x_i|² for Any t Linearly Independent Lattice VectorsResearch Paper

A lattice in Rn\mathbb R^nRn is the set of integer combinations of nnn linearly independent vectors. Many problems in algorithmic number theory, cryptography and integer programming reduce to finding a short nonzero vector of a lattice, or a few short independent ones. Finding the shortest vector exactly is hard, but in 1982 A. K. Lenstra, H. W. Lenstra, Jr. and…

8 thms3 active usersReviewed
🏆Completed
Machine LearningMarkov ChainReinforcement Learning·Captain: mikedeng1

Learning to Predict by the Methods of Temporal Differences: Linear TD(0) Converges in Expected Value to the Ideal Predictions on Absorbing Markov ChainsResearch Paper

Temporal-difference (TD) methods learn to predict an eventual outcome from the differences between successive predictions rather than from the difference between each prediction and the final outcome. Sutton's 1988 paper Learning to predict by the methods of temporal differences introduced the TD(λ\lambdaλ) family and gave the first convergence proof for a TD…

24 thms3 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers VII: Factor Model Fitting — the ADMM X-Update in Closed Form, Entry by EntryTextbook

Alternating direction methods are used when one part of an optimization problem is easy to minimize and another part has a simple projection. Chapter 9 of Boyd, Parikh, Chu, Peleato and Eckstein (2011) examines this idea with nonconvex constraints. Its examples include sparse vectors, Boolean vectors and low-rank matrices. The chapter says explicitly that…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

On the Abstract Properties of Linear Dependence 4: Orthogonal Subspaces Have Dual MatroidsResearch Paper

Hassler Whitney introduced matroids in On the Abstract Properties of Linear Dependence (Amer. J. Math. 57, 1935, doi:10.2307/2371182) to capture what linear dependence among the columns of a matrix and the circuit structure of a graph have in common. One of the central constructions of the paper is duality. For graphs, duality exists only for planar graphs…

12 thms3 active usersReviewed
🏆Completed
Mathematical Physics·Captain: LG

Varying Constants I: Dimensional Analysis, Natural Units and the Buckingham π TheoremResearch Paper

Uzan's review Varying Constants, Gravitation and Cosmology (Living Rev. Relativity 14 (2011) 2) is about testing whether the fundamental constants of physics change in space or time. Before any experiment can be read, §2.1 of the review settles which constants it even makes sense to ask about. Two claims from that section carry the whole programme:

9 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Applied Combinatorics V: Linear Recurrence Equations and the Advancement OperatorTextbook

Linear recurrences with constant coefficients are among the first tools of enumerative combinatorics and the analysis of algorithms: the Fibonacci numbers, the number of binary strings avoiding a pattern, the running time of a divide-and-conquer loop and the number of tilings of a strip all satisfy relations of the form …

6 thms3 active usersReviewed
🏆Completed
Numerical AnalysisProbabilityRandom Matrix Theory·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix IV: Sample Bound for Hutchinson's Trace EstimatorResearch Paper

Many computations need the trace of a matrix AAA that is never formed explicitly and can only be applied to vectors: the trace of a matrix function such as trace(A−1)\mathrm{trace}(A^{-1})trace(A−1) or log⁡det⁡A=trace(log⁡A)\log\det A = \mathrm{trace}(\log A)logdetA=trace(logA) in statistics and lattice QCD, the Frobenius norm ∥B∥F2=trace(BTB)\|B\|_F^2 = \mathrm{trace}(B^TB)∥B∥F2​=trace(BTB) of an operator, or the number of triangles of a graph. The…

7 thms3 active usersReviewed
🏆Completed
Numerical AnalysisProbabilityRandom Matrix Theory·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix II: Exact Rank of a Projection Matrix from the Gaussian Trace EstimatorResearch Paper

Many matrices in scientific computing are available only implicitly: one can multiply a vector by AAA, for instance by solving a linear system or applying a matrix function, but the entries of AAA are never formed. Quantities such as the trace must then be estimated from a small number of matrix–vector products. Randomized trace estimators do exactly this: draw…

7 thms3 active usersReviewed
🏆Completed
Control TheoryDynamical SystemsGraph Theory·Captain: mikedeng1

On Controllability of Delayed Boolean Control Networks: Trajectory Controllability Avoiding Forbidden Trajectories Iff the Reduced Transition-Count Matrix Is IrreducibleResearch Paper

Boolean networks model gene regulatory networks by giving each gene an on/off value and updating all values synchronously by logical rules (Kauffman, 1969). Adding external Boolean inputs gives Boolean control networks (BCNs), in which a designer (a drug, an intervention) chooses the inputs over time. The basic control-theoretic question is controllability:…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Approximating Clique-Width and Branch-Width: Well-Linked Sets Certify Clique-WidthResearch Paper

Clique-width is a graph parameter introduced by Courcelle and Olariu (Discrete Appl. Math. 101 (2000)) that measures how far a graph is from being built by a few labelled operations. Every problem expressible in monadic second-order logic with quantification over vertices and vertex sets (MSO1_11​) can be solved in linear time on graphs given together with a…

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

Sparse Approximate Solutions to Linear Systems 2: An Exact Cover by 3-Sets Exists iff Its Incidence System Has a 1/2-Approximate Solution with at Most m/3 NonzerosResearch Paper

Many problems in signal processing, statistics and function interpolation ask for a solution of a linear system Ax≈bAx\approx bAx≈b that uses as few columns of AAA as possible: a sparse approximate solution. Natarajan's 1995 paper Sparse Approximate Solutions to Linear Systems (SIAM J. Comput. 24(2):227–234) was motivated by radial basis interpolation, where each…

6 thms3 active usersReviewed
🏆Completed
Control TheoryConvex OptimizationNumerical Analysis+2·Captain: mikedeng1

Robust Solutions to Least-Squares Problems with Uncertain Data IV: A Semidefinite Upper Bound on the Linear-Fractional Worst-Case Residual, Exact for Full PerturbationsResearch Paper

Least-squares fitting is a standard tool in estimation, identification and data analysis, and its data AAA, bbb are rarely known exactly. El Ghaoui and Lebret (SIAM J. Matrix Anal. Appl. 18(4), 1997) proposed to choose xxx to minimize the worst-case residual over a set of admissible data perturbations. Earlier missions of this series treat unstructured…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOperations Research+1·Captain: mikedeng1

Robust Solutions to Least-Squares Problems with Uncertain Data I: The Worst-Case Residual and Its Unique MinimizerResearch Paper

The least-squares (LS) problem min⁡x∥Ax−b∥\min_x \|Ax - b\|minx​∥Ax−b∥ assumes that the data A∈Rn×mA \in \mathbb{R}^{n\times m}A∈Rn×m, b∈Rnb \in \mathbb{R}^nb∈Rn are exact. In applications they rarely are: they come from measurements, from linearizations, or from models with neglected dynamics. A classical response is sensitivity analysis or regularization (Tikhonov), where a weight trades the size…

7 thms3 active usersReviewed
🏆Completed
Numerical AnalysisProbabilityRandom Matrix Theory·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix I: Sample Bound for the Gaussian Trace EstimatorResearch Paper

Many computations in scientific computing, statistics and machine learning need the trace of a matrix AAA that is never formed explicitly: AAA may be f(B)f(B)f(B) for a large sparse BBB, an inverse B−1B^{-1}B−1, or a product of operators, and the only access to it is the ability to compute products AzAzAz for chosen vectors zzz. Examples are log-determinant estimation in Gaussian…

9 thms3 active usersReviewed
🏆Completed
Machine LearningOptimizationStatistics·Captain: mikedeng1

Simultaneous Analysis of Lasso and Dantzig Selector I: Sparse Eigenvalue and Correlation Conditions Imply the Restricted Eigenvalue ConditionResearch Paper

In high-dimensional linear regression one observes y=Xβ∗+w∈Rny = X\beta^* + w \in \mathbb R^ny=Xβ∗+w∈Rn with a design matrix X∈Rn×MX\in\mathbb R^{n\times M}X∈Rn×M whose number of columns MMM may far exceed the sample size nnn. The two standard estimators of a sparse β∗\beta^*β∗, the Lasso (Tibshirani, 1996) and the Dantzig selector (Candès and Tao, 2007), both come with error bounds of order …

11 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Updating Quasi-Newton Matrices with Limited Storage: The Limited-Storage BFGS Method Reaches the Minimizer of a Strictly Convex Quadratic in at Most n StepsResearch Paper

Quasi-Newton methods minimize a smooth function fff on Rn\mathbb{R}^nRn by moving along dk=−Hkgkd_k = -H_k g_kdk​=−Hk​gk​, where gkg_kgk​ is the gradient and HkH_kHk​ is an approximation of the inverse Hessian built from observed gradient differences. The BFGS update is the most widely used way of building HkH_kHk​, but it stores a dense n×nn \times nn×n matrix, which is prohibitive for large nnn.

16 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Methods of Conjugate Gradients for Solving Linear Systems II: Each Conjugate Gradient Step Shortens the Error VectorResearch Paper

The conjugate gradient method (cg-method) of Hestenes and Stiefel is the standard iterative solver for linear systems Ax=kAx=kAx=k with a symmetric positive definite matrix AAA. It is used for the large sparse systems of finite-element and finite-difference discretizations, as the inner solver of Newton-type and interior-point methods in optimization, and as the…

9 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Methods of Conjugate Gradients for Solving Linear Systems I: Finite Termination of the Conjugate Gradient MethodResearch Paper

Solving a linear system Ax=kAx = kAx=k with a large symmetric positive definite matrix AAA is a basic task of scientific computing: it arises from discretized elliptic equations, least-squares problems and the Newton steps of optimization methods. In 1952 Magnus Hestenes and Eduard Stiefel published the conjugate gradient method (cg-method) (J. Res. Natl. Bur. Stand.…

11 thms3 active usersReviewed
🏆Completed
AlgebraComputational Complexity·Captain: mikedeng1

The sum-of-squares complexity of linear-algebraic principlesResearch Paper

A real matrix of rank greater than rrr cannot be a product of an n×rn\times rn×r matrix and an r×nr\times nr×n matrix. This elementary obstruction becomes a different question when the permitted certificate is a polynomial identity of bounded degree. Researchers studying algebraic proof complexity ask how much degree a specified certificate system needs to express such…

11 thms2 active usersReviewed
PreviousPage 5 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