# Modern developments in finite-dimensional linear algebra

Are there any major fundamental results in finite-dimensional linear algebra discovered after early XX century? Fundamental in the sense of non-numerical (numerical results, of course, are still interesting and important); and major in the sense of something on the scale of SVD or Jordan normal form.

(EDIT) As several commenters observed, using Jordan normal form as a benchmark sets the bar way too high. Let's try lowering it to Weyl's inequality.

-
Does the computational complexity of matrix multiplication (for arbitrary fields) count as "numerical"? If not, the critical exponent has moved as recently as last year. – Felipe Voloch Feb 27 '13 at 20:13
@Felipe, does a small movement in the critical exponent count as "major"? Jordan normal form is setting the bar rather high.... – Gerry Myerson Feb 27 '13 at 23:25
@Gerry: major enough to get published in JAMS. – Abdelmalek Abdesselam Feb 27 '13 at 23:28
I'm fond of Weyl's question from 1912: given the spectra $\lambda,\mu$ of two Hermitian matrices, what can you say about the spectrum $\nu$ of the sum? which Weyl gave the first inequalities on. The full list of inequalities was conjectured in the 1960s, proven in the late 1990s, and only cut down to the minimal list this century. I won't put this as an "answer" because seriously, Jordan normal form! – Allen Knutson Feb 28 '13 at 2:06
Here's our survey article on that result: arxiv.org/abs/math/0009048 – Allen Knutson Feb 28 '13 at 4:08

Definitely, some items on the top of my list are:

1. Random matrix theory --- both asymptotic and non asymptotic; including things like semi-circular law, circular law, and so on. Check out Terry Tao's blog for very nice summaries.
2. The resolution of Horn's conjecture (see this nice summary article by R. Bhatia, which also mentions several other nice connections)
3. Randomised linear algebra and progress on fast solutions to linear systems (see e.g., the very readable summary in N. Vishnoi's web book)
4. Advances in quantum information theory? Though I don't know how much of that I would push into just linear algebra
5. Not advances in linear algebra itself, but the gigantic success of basic linear algebra in new areas (machine learning, information retrieval, etc., e.g., Google's PageRank method).
-
While I admit that 'non-numerical' is a bit of a vague criteriion; I would still think that almost linear time solution is not 'non-numerical', in the sense it was I believe intended. – user9072 Feb 28 '13 at 14:40

I would say the theory of quivers and in particular Gabriel's theorem on finite representation type and its extensions to tame type. Representations of quivers are essentially linear algebra problems in a different language. For instance Jordan canonical form is the description of indecomposable reps of a quiver with one vertex and a loop. In general things like the classification of two endomorphisms of vector spaces, matrix pencils and the n-subspace problem are all problems in the rep theory of quivers. The intro to the book of Gabriel-Roiter says more.

Added. A quiver is a directed multigraph, often assumed finite in this context. A representation of a quiver Q is an assignment of a vector space to each vertex and a linear transformation to each edge from the vector space at its source to the vector space if its target. Isomorphisms are isomorphisms of vertex spaces making commuting squares with the edge linear transformations. There is a fairly straightforward notion of direct sum and hence indecomposable rep. Finite rep type means finitely many isoclasses of indecomposables, tame type essentially means indecomposables come in 1-parameter families (plus finitely many exceptions) if you fix the dimensions of the vertex spaces. Wild means its representation theory contains that of all finite dinensional (and hence all finitely generated) algebras. In particular the first order theory is undecidable. Only finite, tame and wild occur.

-
Hmm. Are there any applications of quivers in linear algebra other than Jordan's form? After brief googling, it seems to me that quivers are used in all branches of mathematics, except for LA. – Timur Feb 28 '13 at 3:39
Subspace problems of the form 'classify all ways to embed n subspaces in a vector space' can be studied using quivers. The four subspace problem is studied in a nice paper of Gelfand and Ponomarev 'Problems of linear algebra and classification of quadruples of subspaces...'. – George Melvin Feb 28 '13 at 3:53
Timur, the representation of quivers is linear algebra. – Mariano Suárez-Alvarez Feb 28 '13 at 4:29

Just putting the references asked for by Timur:

-

Since you lowered the level to Weyl's Inequalities (1912), it is worth mentionning the improvements of these inequalities made by Ky Fan, Lidskii and others. They culminated in a much involved conjecture by A. Horn (1961), eventually proved by Knutson & Tao on the turn of the century.

-

This is a borderline suggestion, both in terms of how "major" it is and timing (does 1931 count as "early" 20th century?), but there is the Gershgorin circle theorem.

-

Also a borderline suggestion since it is rather multilinear than just linear: Recent progress on low rank tensor approximation for all kinds of different applications within mathematics. A list of applications from this preprint includes

• approximation of multidimensional integrals
• electronic structure calculations
• solving stochastic or parameter dependent PDEs
• approximating Green's functions in high dimensions
• solving Boltzmann-type equations or high-dimensional Schrödinger equations
• rational approximation problems
• computational finance
• multivariate regression and machine learning.
-

From Wikipedia: "The linear-programming problem was first shown to be solvable in polynomial time by Leonid Khachiyan in 1979, but a larger theoretical and practical breakthrough in the field came in 1984 when Narendra Karmarkar introduced a new interior-point method for solving linear-programming problems."

-
Both the ellipsoid and the interior point method look to me (note: I'm by no means an expert on this) like analysis-flavored algorithms built specifically for $\mathbb R$ rather than the setting of a general ordered field (or even really closed field); I wouldn't necessarily call them linear algebra for these reasons... – darij grinberg Feb 28 '13 at 5:03
I would not say that the ellipsoid method is "build for $\mathbf R$". It has a definitely arithmetic flavor. Indeed, to get a lower bound for the volume of ellipsoids, one uses crucially the (trivial but overwhemlingly important) fact that the absolute value of a nonzero integer is at least $1$. – ACL Feb 28 '13 at 13:24
While I admit that 'non-numerical' is a bit of a vague criteriion; I would still think that this is not 'non-numerical', in the sense it was I believe intended. – user9072 Feb 28 '13 at 14:39