Open problems

980 registered problems.

OP-00217 Solution claimed

Forsythe's conjecture beyond restart length two

NA · conjugate gradient methods · Krylov subspace methods · OpenProblemsInNLA

OP-00218 Solution claimed

The square-root upper bound for Gaussian partial-pivoting growth

NA · Gaussian elimination · growth factors · OpenProblemsInNLA · random matrices

OP-00219 Solution claimed

A cubic-time Schur algorithm using logarithmic precision

NA · floating-point arithmetic · OpenProblemsInNLA · randomized algorithms · Schur decompositions

OP-00220 Solution claimed

Conditioning of a random Krylov compression of a cyclic shift

NA · circulant matrices · eigenvector condition numbers · Krylov subspaces · OpenProblemsInNLA

OP-00221 Solution claimed

Near-quadratic solution cost at a prescribed backward error

NA · backward errors · linear systems · OpenProblemsInNLA · randomized algorithms

OP-00222 Solution claimed

Sharp growth for unequal lower and upper bandwidths

NA · banded matrices · Gaussian elimination · growth factors · OpenProblemsInNLA

OP-00223 Solution claimed

Sharp growth for cyclic tridiagonal matrices

NA · Gaussian elimination · growth factors · OpenProblemsInNLA · tridiagonal matrices

OP-00224 Solution claimed

Exact small-order growth factors for rook pivoting

NA · Gaussian elimination · growth factors · OpenProblemsInNLA · rook pivoting

OP-00225 Solution claimed

Sharp row-deletion singular-value limit for spherical random matrices

NA · Kaczmarz methods · OpenProblemsInNLA · random matrices · smallest singular values

OP-00226 Solution claimed

Optimal uniform row-deletion singular-value constant

NA · corrupted linear systems · Kaczmarz methods · OpenProblemsInNLA · smallest singular values

OP-00227 Solution claimed

Sharp stability bounds for perturbed Fourier interpolation

NA · Lebesgue constants · nonuniform Fourier matrices · OpenProblemsInNLA · trigonometric interpolation

OP-00228 Solution claimed

Find a near-largest nonnormal eigenvalue using few matrix-vector products

NA · eigenvalue algorithms · nonnormal matrices · OpenProblemsInNLA · query complexity

OP-00229 Solution claimed

Spectral-gap-independent constants for randomized block polynomial interpolation

NA · block Lanczos methods · matrix polynomials · OpenProblemsInNLA · random matrices

OP-00230 Solution claimed

Multiplication overhead of cubic sign compositions

NA · matrix sign function · OpenProblemsInNLA · polynomial approximation · polynomial compositions

OP-00231 Solution claimed

A uniform disk bound for wave-kernel Padé approximants

NA · backward error analysis · matrix functions · OpenProblemsInNLA · Padé approximants

OP-00232 Solution claimed

NP-hardness of unrestricted static output-feedback stabilization

OC · Hurwitz matrices · NP-hardness · OpenProblemsInNLA · static output feedback

OP-00233 Solution claimed

Uniqueness of positive definite solutions of two-letter word equations in order two

NA · nonlinear matrix equations · OpenProblemsInNLA · positive definite matrices · word equations

OP-00234 Solution claimed

Complete Crouzeix conjecture

FA · matrix polynomials · numerical ranges · OpenProblemsInNLA · spectral sets

OP-00235 Solution claimed

A dimension-independent polynomial norm bound from super-identical pseudospectra

NA · matrix polynomials · OpenProblemsInNLA · pseudospectra · singular values

OP-00236 Solution claimed

Preservation of real H-matrix structure by Newton square-root iterates

NA · H-matrices · matrix square roots · Newton iterations · OpenProblemsInNLA

OP-00237 Solution claimed

Clustered singular-value gaps in randomized block Krylov approximation

NA · Krylov subspace methods · low-rank approximations · OpenProblemsInNLA · singular value gaps

OP-00238 Solution claimed

Sharp joint rank and accuracy dependence for strong ℓₚ subspace coresets

NA · coresets · low-rank approximations · OpenProblemsInNLA · subspace approximation

OP-00239 Lean verified

Sensitivity-dependent row sampling for ℓₚ embeddings when p exceeds two

NA · OpenProblemsInNLA · row sampling · sensitivity sampling · subspace embeddings

OP-00240 Solution claimed

Concave-function transfer of spectral low-rank error

NA · low-rank approximations · matrix functions · Nyström approximations · OpenProblemsInNLA

OP-00241 Solution claimed

Concave-function transfer of Frobenius low-rank error

NA · low-rank approximations · matrix functions · Nyström approximations · OpenProblemsInNLA

OP-00242 Solution claimed

Constant-loss nuclear-error transfer without matrix ordering

NA · low-rank approximations · matrix functions · OpenProblemsInNLA · operator monotone functions

OP-00243 Solution claimed

Relative-error threshold for extremal Gaussian trace bounds

NA · Gamma distributions · OpenProblemsInNLA · tail bounds · trace estimation

OP-00244 Solution claimed

Absolute-error threshold for extremal Gaussian trace bounds

NA · Gamma distributions · OpenProblemsInNLA · tail bounds · trace estimation

OP-00245 Solution claimed

Critical-point count for corank-one approximation with a fixed zero

AG · determinantal varieties · Euclidean distance degrees · low-rank approximations · OpenProblemsInNLA

OP-00246 Solution claimed

Pure relative error for approximation by a linear matrix family

NA · matrix-vector queries · OpenProblemsInNLA · query complexity · structured matrices

OP-00247 Solution claimed

Nonadaptive queries for finite-family matrix approximation

NA · matrix-vector queries · nonadaptive algorithms · OpenProblemsInNLA · query complexity

OP-00248 Solution claimed

A sum-of-squares representation for the Toeplitz commutator form

FA · Böttcher–Wenzel inequality · OpenProblemsInNLA · sums of squares · Toeplitz matrices

OP-00249 Solution claimed

Schatten norm complement involving Lin's positive definite quantity

FA · matrix geometric means · norm inequalities · OpenProblemsInNLA · Schatten norms

OP-00250 Solution claimed

Ghabries's determinant comparison for arbitrary nonnegative base powers

FA · determinantal inequalities · OpenProblemsInNLA · positive definite matrices

OP-00251 Solution claimed

Sharp parameter dependence for structured Gaussian operator norms

PR · OpenProblemsInNLA · operator norms · random matrices

OP-00252 Lean verified

The delta conjecture for minimum symmetric rank

CO · inverse eigenvalue problems · maximum nullity · minimum rank · OpenProblemsInNLA

OP-00253 Solution claimed

A chromatic lower bound for positive-semidefinite nullity with SAP

CO · Colin de Verdière parameters · graph colorings · OpenProblemsInNLA · strong Arnold property

OP-00254 Solution claimed

Trace-norm-small perturbations preserve Hermitian spectral distributions

NA · eigenvalue distributions · matrix sequences · non-Hermitian perturbations · OpenProblemsInNLA

OP-00255 Solution claimed

Deciding accurate evaluability of real polynomials

NA · decision procedures · OpenProblemsInNLA · polynomial evaluation · rounding errors

OP-00256 Solution claimed

Recognizing the maximum finite number of solutions

NA · absolute value equations · OpenProblemsInNLA · piecewise linear systems

OP-00257 Solution claimed

Hardness of the spectral-norm condition number

NA · absolute value equations · condition numbers · interval matrices · OpenProblemsInNLA

OP-00258 Solution claimed

Sharp sampling complexity for Walsh restricted isometries

FA · compressed sensing · OpenProblemsInNLA · restricted isometry property · Walsh matrices

OP-00259 Solution claimed

Exact solution hulls for inverse M-matrix intervals

NA · interval matrices · inverse M-matrices · linear systems · OpenProblemsInNLA

OP-00260 Solution claimed

Complexity of globally optimal nonnegative rank-two approximation

NA · low-rank approximations · nonnegative matrix factorizations · OpenProblemsInNLA

OP-00261 Solution claimed

The maximum cp-rank in order six

NA · completely positive matrices · cp-rank · OpenProblemsInNLA

OP-00262 Solution claimed

Infinitesimal rigidity detects unique size-two factors in the presence of zeros

NA · infinitesimal rigidity · OpenProblemsInNLA · positive semidefinite factorizations · positive semidefinite rank

OP-00263 Partially resolved

The maximum permanent on a positive-semidefinite unitary orbit

FA · OpenProblemsInNLA · permanents · positive semidefinite matrices · unitary orbits

OP-00264 Partially resolved

Exact determinant ranges of general tridiagonal interval matrices

NA · determinants · interval matrices · OpenProblemsInNLA · tridiagonal matrices

OP-00265 Partially resolved

Exact solution hulls for tridiagonal interval systems

NA · interval matrices · linear systems · OpenProblemsInNLA · tridiagonal matrices

OP-00266 Open

Bourin's crossed-Heinz inequality

FA · norm inequalities · OpenProblemsInNLA · unitarily invariant norms