Are there open problems in Linear Algebra?

Question

I'm reading some stuff about algebraic K-theory, which can be regarded as a "generalization" of linear algebra, because we want to use the same tools like in linear algebra in module theory.

There are a lot of open problems and conjectures in K-theory, which are "sometimes" inspired by linear algebra.

So I just want to know:

What are open problems in "pure" linear algebra? (Pure means not numerical!)

Thanks

Answer 1

One of the biggest questions is one of the simplest to understand: what is the lowest bound for the operation count of matrix-matrix multiplication? Or, in other words,

Given two $n\times n$ matrices, what is the lowest bound of the exponent in the computational complexity of their product?

The conjecture could be made more bold:

Does there exist an algorithm that can compute the product of two $n \times n$ matrices with complexity $O(n^2)$?

Currently, the lowest known bound for the exponent is about $2.373$, obtained from an optimization on the Coppersmith-Winograd algorithm, which isn't actually used because it's only efficient for matrices that are so large that they're (currently) not encountered in practice.

Some folks (citation needed) suspect that for sufficiently large $n$, an algorithm exists that can compute the product in $O(n^2)$ operations.

Answer 2

This problem arises from control theory, but it is actually a linear algebra problem. Static Output Feedback Stabilization Problem: Given the matrices $A \in \mathbb{R}^{n \times n}$, $B \in \mathbb{R}^{n \times m}$ and $C \in \mathbb{R}^{p \times n}$ is there exist a matrix $K \in \mathbb{R}^{m \times p}$ such that real part of all eigenvalues of the matrix $A+BKC$ are negative.

Answer 3

The question for the existence of a vector space analog of the Fano plane is open for any prime power value of $q$:

Is there a set of $3$-dimensional subspaces of $\operatorname{GF}(q)^7$ such that every $2$-dimensional subspace is covered exactly once?

Update (in 2022): The problem is now open for 50 years. The oldest source for this problem dates back to 1972.

Further remark: While the original question was stated for finite fields $\operatorname{GF}(q)$, it may also be considered over arbitrary infinite base fields. I don't know about a single field where the question is answered.

Answer 4

What are open problems in "pure" linear algebra? (Pure means not numerical!)

Here is a list of problems in "pure" matrix theory/linear algebra:

1. The Hadamard conjecture, which asserts that a Hadamard matrix of order $4k$ exists for every positive integer $k$. Most matrix theorists regard this as the most important open problem in matrix theory.
2. If you ask Charlie Johnson (and I have), the most important open problem in matrix theory is the nonnegative inverse eigenvalue problem (see the survey written by Johnson, Marijuan, Paparella, and Pisonero: https://link.springer.com/chapter/10.1007/978-3-319-72449-2_10), which is to characterize the spectra of entrywise nonnegative matrices. More specifically, given a multiset of complex numbers $\Lambda = \{\lambda_1,\ldots,\lambda_n\}$, find necessary and sufficient conditions such that $\Lambda$ is the spectrum of an entrywise nonnegative matrix $A$.
3. There are several matrix-theoretic formulations of the Riemann hypothesis, most notably that involving random matrices and the Redheffer matrix.
4. The Jacobian conjecture (#16 on Smale's list or problems).
5. Crouzeix's conjecture (the most recent of the conjectures listed).