5 ms·

>“Mathematicians basically know everything there is to know about matrices. It’s one of the few subjects of math that’s thoroughly well understood,” said Jared

by sva_ 6y ago

>“Mathematicians basically know everything there is to know about matrices. It’s one of the few subjects of math that’s thoroughly well understood,” said Jared Weinstein of Boston University. I'm genuinely curious how such a statement can be made. I've recently been wondering about if it were possible to prove that one's theorems are exhaustive about a 'space' of possible theorems in an axiomatic system (or some subset thereof, since I'd assume such a space might be infinite (perhaps)). How can we know that there aren't some really surprising properties of matrices that we've previously been unaware of? As far as I can see, we can merely make a statement about that it fits well together with other (limited) findings we've made so far?

bollu 6y ago
It's more that in linear algebra, we have "the nicest theorems we can hope for", so there's no "nasty surprises" lurking around. This is qualitatively different from pretty much all other algebraic structures one studies, where there is some amount of nastiness which we attempt to control.
- Koshkin 6y ago
  Indeed, “linear” and “nice” are almost synonymous in mathematics and, especially, in its applications. (For example, the entire differential calculus is based on the idea of approximating arbitrary “nice” functions with linear maps.)
  - eru 6y ago
    There's also lots of clever tricks to make things more linear. There's things like linear approximations. Or, my favourite, picking a clever semi-ring in which your problem is linear. See eg the analysis of Google's BBR TCP variant. Eg https://labs.xjtudlc.com/labs/wldmt1/papers/Traffic%20management%20congestion%20control,%20router%20mechanisms%20and%20pricing/BH00.pdf https://labs.xjtudlc.com/labs/wldmt1/papers/Traffic%20manage... Or 'Linear regression over the max-plus semiring:algorithms and applications' (https://arxiv.org/pdf/1712.03499.pdf https://arxiv.org/pdf/1712.03499.pdf)
Koshkin 6y ago
The sense in which this is true is similar to what they mean when they say that a car engine mechanic “knows everything there is to know about car engines.” Sure, conceivably you could do with a car engine something that it is not designed for and which would be beyond what the mechanic would know or expect, or you could (unlikely) invent a new material (a “number” system for matrix elements) which would lead to results that are hard to predict in advance, but the “engine science” itself would hardly benefit from such things...
- deleted 6y ago
  [deleted]
nvusuvu 6y ago
Just this year I read that a new insight about eigenvalues/eigenvectors had just been discovered, shocking the math world that a new insight from linear algebra could be discovered.
- andrepd 6y ago
  Can you share it?
  - kmm 6y ago
    Here is a write-up by Terry Tao. This doesn't disprove the premise that linear algebra is more or less solved. Although the result was unknown and a little surprising, once formulated the proof was relatively straightforward, and does not imply any major or minor upsets in the field. https://terrytao.wordpress.com/2019/08/13/eigenvectors-from-eigenvalues/ https://terrytao.wordpress.com/2019/08/13/eigenvectors-from-...
  - jwmerrill 6y ago
    I bet it was “Eigenvectors from Eigenvalues” * https://www.quantamagazine.org/neutrinos-lead-to-unexpected-discovery-in-basic-math-20191113/ https://www.quantamagazine.org/neutrinos-lead-to-unexpected-... * https://terrytao.wordpress.com/2019/08/13/eigenvectors-from-eigenvalues/ https://terrytao.wordpress.com/2019/08/13/eigenvectors-from-... * https://arxiv.org/abs/1908.03795 https://arxiv.org/abs/1908.03795
- QuesnayJr 6y ago
  It actually turned out that the result was old, and had been rediscovered multiple times: https://terrytao.wordpress.com/2019/12/03/eigenvectors-from-eigenvalues-a-survey-of-a-basic-identity-in-linear-algebra/ https://terrytao.wordpress.com/2019/12/03/eigenvectors-from-...
mrfox321 6y ago
To your last question, Godel's incompleteness theorem prevents use from proving everything about linear algebra. So there might be surprising statements that are true but can never be proved to be true given the axioms.
- contravariant 6y ago
  Be careful with your phrasing there. The axioms for the real numbers [1] are complete and consistent (within ZFC). Hence I'm almost sure the axioms for each of the finite dimensional vector spaces will also be complete and consistent. Part of the reason is that you can't define the integers within the context of the real numbers. [1]: https://math.stackexchange.com/questions/362837/are-real-numbers-axioms-a-consistent-or-complete-system https://math.stackexchange.com/questions/362837/are-real-num...
- abjKT26nO8 6y ago
  That's not what Gödel's first theorem says. What Gödel's theorem tells us about linear algebra is that either it's inconsistent, or there are statements which are true for some models of linear algebra, but false for others. In fact, we do know that any statement in linear algebra that is true[1], is provable. That's because vector spaces are first-order structures, so that's covered by Godel's completeness theorem[2]. [1]: I.e. it's true for all models of linear algebra. [2]: https://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_theorem https://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_th...
  - openasocket 6y ago
    What about the moral matrix problem? Given a finite set of matrices with integer entries, determine if you can multiply them in some order, possibly with repetition, to get the zero matrix. It's proven undecidable for "a set of six or more 3 × 3 matrices, or a set of two 15 × 15 matrices" at least according to wikipedia. https://en.wikipedia.org/wiki/List_of_undecidable_problems https://en.wikipedia.org/wiki/List_of_undecidable_problems . Is that because it incorporates the integers or something?
    - 6y ago
QuesnayJr 6y ago
Most axiomatic system have an infinite number of theorems. I would say that a theory is "known" if there is an algorithm to decide which statements follow from the theory. An example is plane geometry, which has an algorithm due to Tarski. (The algorithm is pretty slow, though -- doubly exponential. Maybe a better criterion is a polynomial-time algorithm, though I don't know of a system that has such.) Practically, questions about matrices are easy. (Matrices over the real and complex numbers can probably be reduced to the same Tarski algorithm, actually.) If you can reduce a question to a linear algebra question, you're probably going to solve it. There are open questions in linear algebra if you force the entries to be integers, for example, but odds are you don't have one of those.
FartyMcFarter 6y ago
Isn't the complexity of computing the permanent of a matrix a big, and impactful open problem? On wikipedia: https://en.wikipedia.org/wiki/Computing_the_permanent https://en.wikipedia.org/wiki/Computing_the_permanent Scott Aaronson has written about it: https://www.scottaaronson.com/blog/?p=2925 https://www.scottaaronson.com/blog/?p=2925
BurningFrog 6y ago
I interpret it as there are no unanswered questions in the field. Sure, some new interesting question may arise tomorrow.
cosmic_ape 6y ago
This is of course just a hyperbole, especially in its original context. For one thing, people routinely use representation theory to study groups of matrices. That is, represent the group of matrices by other matrices, acting on other spaces. If matrices were this elementary "thoroughly understood" object, one presumably wouldn't have needed to do that. The real power of the representation theory is not that its matrices, but the notion of irreducibility. This allows you to decompose a complex action into simpler blocks and understand it that way.

by sva_ 6y ago

bollu 6y ago

It's more that in linear algebra, we have "the nicest theorems we can hope for", so there's no "nasty surprises" lurking around. This is qualitatively different from pretty much all other algebraic structures one studies, where there is some amount of nastiness which we attempt to control.

Koshkin 6y ago
Indeed, “linear” and “nice” are almost synonymous in mathematics and, especially, in its applications. (For example, the entire differential calculus is based on the idea of approximating arbitrary “nice” functions with linear maps.)
- eru 6y ago
  There's also lots of clever tricks to make things more linear. There's things like linear approximations. Or, my favourite, picking a clever semi-ring in which your problem is linear. See eg the analysis of Google's BBR TCP variant. Eg https://labs.xjtudlc.com/labs/wldmt1/papers/Traffic%20management%20congestion%20control,%20router%20mechanisms%20and%20pricing/BH00.pdf https://labs.xjtudlc.com/labs/wldmt1/papers/Traffic%20manage... Or 'Linear regression over the max-plus semiring:algorithms and applications' (https://arxiv.org/pdf/1712.03499.pdf https://arxiv.org/pdf/1712.03499.pdf)

Koshkin 6y ago

The sense in which this is true is similar to what they mean when they say that a car engine mechanic “knows everything there is to know about car engines.” Sure, conceivably you could do with a car engine something that it is not designed for and which would be beyond what the mechanic would know or expect, or you could (unlikely) invent a new material (a “number” system for matrix elements) which would lead to results that are hard to predict in advance, but the “engine science” itself would hardly benefit from such things...

deleted 6y ago
[deleted]

nvusuvu 6y ago

Just this year I read that a new insight about eigenvalues/eigenvectors had just been discovered, shocking the math world that a new insight from linear algebra could be discovered.

andrepd 6y ago
Can you share it?
- kmm 6y ago
  Here is a write-up by Terry Tao. This doesn't disprove the premise that linear algebra is more or less solved. Although the result was unknown and a little surprising, once formulated the proof was relatively straightforward, and does not imply any major or minor upsets in the field. https://terrytao.wordpress.com/2019/08/13/eigenvectors-from-eigenvalues/ https://terrytao.wordpress.com/2019/08/13/eigenvectors-from-...
- jwmerrill 6y ago
  I bet it was “Eigenvectors from Eigenvalues” * https://www.quantamagazine.org/neutrinos-lead-to-unexpected-discovery-in-basic-math-20191113/ https://www.quantamagazine.org/neutrinos-lead-to-unexpected-... * https://terrytao.wordpress.com/2019/08/13/eigenvectors-from-eigenvalues/ https://terrytao.wordpress.com/2019/08/13/eigenvectors-from-... * https://arxiv.org/abs/1908.03795 https://arxiv.org/abs/1908.03795
QuesnayJr 6y ago
It actually turned out that the result was old, and had been rediscovered multiple times: https://terrytao.wordpress.com/2019/12/03/eigenvectors-from-eigenvalues-a-survey-of-a-basic-identity-in-linear-algebra/ https://terrytao.wordpress.com/2019/12/03/eigenvectors-from-...

mrfox321 6y ago

To your last question, Godel's incompleteness theorem prevents use from proving everything about linear algebra. So there might be surprising statements that are true but can never be proved to be true given the axioms.

contravariant 6y ago
Be careful with your phrasing there. The axioms for the real numbers [1] are complete and consistent (within ZFC). Hence I'm almost sure the axioms for each of the finite dimensional vector spaces will also be complete and consistent. Part of the reason is that you can't define the integers within the context of the real numbers. [1]: https://math.stackexchange.com/questions/362837/are-real-numbers-axioms-a-consistent-or-complete-system https://math.stackexchange.com/questions/362837/are-real-num...
abjKT26nO8 6y ago
That's not what Gödel's first theorem says. What Gödel's theorem tells us about linear algebra is that either it's inconsistent, or there are statements which are true for some models of linear algebra, but false for others. In fact, we do know that any statement in linear algebra that is true[1], is provable. That's because vector spaces are first-order structures, so that's covered by Godel's completeness theorem[2]. [1]: I.e. it's true for all models of linear algebra. [2]: https://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_theorem https://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_th...
- openasocket 6y ago
  What about the moral matrix problem? Given a finite set of matrices with integer entries, determine if you can multiply them in some order, possibly with repetition, to get the zero matrix. It's proven undecidable for "a set of six or more 3 × 3 matrices, or a set of two 15 × 15 matrices" at least according to wikipedia. https://en.wikipedia.org/wiki/List_of_undecidable_problems https://en.wikipedia.org/wiki/List_of_undecidable_problems . Is that because it incorporates the integers or something?
  - 6y ago

QuesnayJr 6y ago

Most axiomatic system have an infinite number of theorems. I would say that a theory is "known" if there is an algorithm to decide which statements follow from the theory. An example is plane geometry, which has an algorithm due to Tarski. (The algorithm is pretty slow, though -- doubly exponential. Maybe a better criterion is a polynomial-time algorithm, though I don't know of a system that has such.) Practically, questions about matrices are easy. (Matrices over the real and complex numbers can probably be reduced to the same Tarski algorithm, actually.) If you can reduce a question to a linear algebra question, you're probably going to solve it. There are open questions in linear algebra if you force the entries to be integers, for example, but odds are you don't have one of those.

FartyMcFarter 6y ago

Isn't the complexity of computing the permanent of a matrix a big, and impactful open problem? On wikipedia: https://en.wikipedia.org/wiki/Computing_the_permanent https://en.wikipedia.org/wiki/Computing_the_permanent Scott Aaronson has written about it: https://www.scottaaronson.com/blog/?p=2925 https://www.scottaaronson.com/blog/?p=2925

BurningFrog 6y ago

I interpret it as there are no unanswered questions in the field. Sure, some new interesting question may arise tomorrow.

cosmic_ape 6y ago

This is of course just a hyperbole, especially in its original context. For one thing, people routinely use representation theory to study groups of matrices. That is, represent the group of matrices by other matrices, acting on other spaces. If matrices were this elementary "thoroughly understood" object, one presumably wouldn't have needed to do that. The real power of the representation theory is not that its matrices, but the notion of irreducibility. This allows you to decompose a complex action into simpler blocks and understand it that way.