Open problems

980 registered problems.

OP-00066 Partially resolved

Is the matrix multiplication exponent two?

NA · arithmetic complexity · matrix multiplication · OpenProblemsInNLA

OP-00067 Open

Border rank of the 3×3 matrix product

AG · border rank · matrix multiplication · OpenProblemsInNLA · tensor rank

OP-00068 Open

Strassen's asymptotic rank conjecture for tight tensors

AG · asymptotic rank · matrix multiplication · OpenProblemsInNLA · tensor rank

OP-00069 Open

Knuth–Stolarsky lower bound for addition chains

NT · addition chains · exponentiation · OpenProblemsInNLA

OP-00070 Open

An explicit rational Valiant-rigid matrix family

CO · circuit lower bounds · matrix rigidity · OpenProblemsInNLA

OP-00071 Open

Audenaert's two-row Schatten norm-compression conjecture

FA · block matrices · norm inequalities · OpenProblemsInNLA · Schatten norms

OP-00072 Partially resolved

Minimum number of orthogonal conjugations for diagonal pinching

FA · OpenProblemsInNLA · orthogonal matrices · pinching

OP-00073 Open

Chollet's permanent inequality for Hadamard products

FA · Hadamard product · OpenProblemsInNLA · permanents

OP-00074 Open

Lieb's permanental dominance conjecture

FA · generalized matrix functions · immanants · OpenProblemsInNLA · permanents

OP-00076 Lean verified

Counting real Hadamard matrices

CO · Hadamard matrices · OpenProblemsInNLA · sign matrices

OP-00077 Lean verified

Is the ideal GMRES bound sharp for every Jordan block?

NA · GMRES · Jordan blocks · Krylov subspace methods · OpenProblemsInNLA

OP-00078 Lean verified

Exponential smoothed tail bounds for partial pivoting

NA · Gaussian elimination · growth factors · OpenProblemsInNLA · smoothed analysis

OP-00079 Lean verified

Exact extremizers for partial pivoting on orthogonal matrices

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

OP-00080 Lean verified

A sharp subset bound for worst-case normal GMRES

NA · GMRES · normal matrices · OpenProblemsInNLA · polynomial approximation

OP-00081 Lean verified

Monotonic optimal backward error along LSMR

NA · backward errors · least-squares problems · LSMR · OpenProblemsInNLA

OP-00082 Lean verified

The exact four-step amplification of restarted Anderson acceleration

NA · Anderson acceleration · convergence factors · fixed-point iterations · OpenProblemsInNLA

OP-00083 Lean verified

Sharp inverse norm bound from upper bounds on matrix entries

NA · diagonally dominant matrices · matrix inverses · OpenProblemsInNLA

OP-00084 Lean verified

Uniqueness of the right inverse minimizing an induced p-to-2 norm

NA · generalized inverses · induced norms · OpenProblemsInNLA

OP-00085 Lean verified

Where a symmetric stochastic matrix can be spectrally unique

NA · doubly stochastic matrices · inverse eigenvalue problems · OpenProblemsInNLA

OP-00086 Lean verified

Johnson's derivative-realizability conjecture

NA · critical points · inverse eigenvalue problems · nonnegative matrices · OpenProblemsInNLA

OP-00087 Lean verified

Polynomial-size vertex test for inverse M-matrix intervals

NA · interval matrices · inverse M-matrices · OpenProblemsInNLA

OP-00088 Lean verified

Number of components of a real interval eigenvalue set

NA · interval matrices · OpenProblemsInNLA · real eigenvalues

OP-00089 Lean verified

Strict interlacing across block Lanczos iterations

NA · block Lanczos methods · eigenvalue interlacing · OpenProblemsInNLA · Ritz values

OP-00090 Lean verified

Local Hölder continuity of the joint spectral radius

DS · Hölder continuity · joint spectral radius · OpenProblemsInNLA

OP-00091 Lean verified

A pointwise Lipschitz lower bound for the joint spectral radius

DS · joint spectral radius · OpenProblemsInNLA · perturbation bounds

OP-00092 Lean verified

Uniform polynomial bounds for products at joint spectral radius one

DS · joint spectral radius · matrix products · OpenProblemsInNLA

OP-00093 Lean verified

Realizing arbitrary polynomial growth exponents by finite matrix families

DS · growth rates · joint spectral radius · matrix products · OpenProblemsInNLA

OP-00094 Lean verified

Degree coverage with seven matrix multiplications

NA · matrix multiplication · matrix polynomials · OpenProblemsInNLA

OP-00095 Lean verified

Imaginary-part rank in a limiting Green-function matrix equation

NA · Green's functions · nonlinear matrix equations · OpenProblemsInNLA · quadratic eigenvalue problems

OP-00096 Lean verified

The uniform expansion threshold for Toeplitz symbols with higher-order zeros

NA · eigenvalue asymptotics · OpenProblemsInNLA · Toeplitz matrices

OP-00097 Lean verified

Polynomial conditioning of the cubic C1 spline Schrödinger Toeplitz family

NA · block Toeplitz matrices · condition numbers · isogeometric analysis · OpenProblemsInNLA

OP-00098 Lean verified

Sharp additive triangle constant for an odd number of contractions

FA · contractions · OpenProblemsInNLA · triangle inequalities

OP-00099 Lean verified

A universal block-norm characterization of essentially Hermitian matrices

FA · block matrices · numerical ranges · OpenProblemsInNLA

OP-00100 Lean verified

Thompson-type domination for the arithmetic symmetric modulus

FA · OpenProblemsInNLA · symmetric moduli · triangle inequalities · unitary orbits

OP-00101 Lean verified

The triangle conjecture for the maximal symmetric modulus

FA · OpenProblemsInNLA · spectral order · symmetric moduli · triangle inequalities

OP-00102 Lean verified

Nobori's spectral-middle-factor commutator conjecture

FA · Böttcher–Wenzel inequality · commutators · norm inequalities · OpenProblemsInNLA

OP-00103 Lean verified

A q-permanent inequality for subset-preserving permutations

FA · OpenProblemsInNLA · permanents · q-permanents

OP-00104 Lean verified

Freewan–Hayajneh inequality for sums of weighted geometric means

FA · matrix geometric means · OpenProblemsInNLA · unitarily invariant norms

OP-00105 Lean verified

Lemos–Soares singular-value log-majorization

FA · log-majorization · matrix geometric means · OpenProblemsInNLA · singular values

OP-00106 Lean verified

Corrected generalized geometric-mean product conjecture

FA · eigenvalues · log-majorization · matrix geometric means · OpenProblemsInNLA

OP-00107 Lean verified

Concave unitary-orbit subadditivity without monotonicity

FA · concave functions · matrix subadditivity · OpenProblemsInNLA · unitary orbits

OP-00108 Lean verified

Constant one in the logarithmic commutator inequality

FA · commutators · matrix logarithms · OpenProblemsInNLA

OP-00109 Lean verified

Modulus-order determinant comparison with an arbitrary base power

FA · determinantal inequalities · OpenProblemsInNLA · positive definite matrices

OP-00110 Lean verified

The Rowland–Wu polynomial identity for Sinkhorn limits

NA · matrix scaling · OpenProblemsInNLA · Sinkhorn limits

OP-00111 Lean verified

Full nonnegative rank of the quadratic correlation matrix

NA · extended formulations · nonnegative rank · OpenProblemsInNLA · unique-disjointness matrices

OP-00112 Lean verified

The nonnegative rank of the nine-point distance matrix

NA · Euclidean distance matrices · nonnegative rank · OpenProblemsInNLA

OP-00113 Lean verified

Connectedness of minimal positive semidefinite factorization orbits

NA · matrix factorizations · OpenProblemsInNLA · positive semidefinite rank

OP-00114 Lean verified

Rational factors for rational completely positive boundary matrices

NA · completely positive matrices · OpenProblemsInNLA · rational factorizations

OP-00115 Lean verified

Polynomial trace-error factor after exactly the target rank of pivots

NA · low-rank approximations · OpenProblemsInNLA · pivoted Cholesky factorizations

OP-00116 Lean verified

Improve the randomized LU squared-error factor to 2^k

NA · low-rank approximations · OpenProblemsInNLA · pivoted LU factorizations