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!)



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.

  • $\begingroup$ This is a great problem in linear algebra! I have a paper from Berkeley and Stanford about this lower bound, I also suspect that one day we will reach $O(n^2)$. $\endgroup$
    – Integral
    Jan 27 '15 at 23:32

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.


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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.