NP-hard problems in linear algebra and real analysis I am curious about NP-hard problems in linear algebra and real analysis. An example in linear algebra would be the calculation of the permanent.
I would thus like to collect in this thread a list of problems specifically in real analysis and linear algebra which are proven to be NP-hard. References to articles or books on this subject would also be helpful.
Any help will be greatly appreciated.
 A: The tensor product has a way of making easy problems into (NP-)hard problems. Rank of a 2-tensor (matrix)? Easy. Rank of a 3-tensor? NP-hard. Spectral norm of a matrix? Easy. Spectral norm of a 3-tensor? NP-hard. Etc. There is a nice article by Hillar and Lim about this.
As a direct corollary of the above fact, many natural linear algebra problems that come up in quantum information theory are NP-hard:


*

*Determining whether or not a quantum state is entangled

*Computing pretty much any entanglement monotone (squashed entanglement, entanglement cost, relative entropy of entanglement, and so on)

*Holevo capacity of a quantum channel

*Minimum entropy of a quantum channel

*Plenty of other problems are even "harder" than NP-hard (see this survey article)
These problems can sometimes be rephrased in a way that doesn't use the tensor product at all even. For example, the problem of determining whether or not a linear map is positive is NP-hard. That is, given a linear map $\Phi$ that sends matrices to matrices, determine whether or not $\Phi(X)$ is positive semidefinite whenever $X$ is positive semidefinite.
A: Here is one such result.

Stephen A. Vavasis.
  "On the complexity of nonnegative matrix factorization."
  2007. (arXiv abstract link)
"In this report, we define an exact version of NMF [nonnegative matrix factorization]. Then we establish several results about exact NMF: (1) that it is equivalent to a problem in polyhedral combinatorics; (2) that it is NP-hard; and (3) that a polynomial-time local search heuristic exists."

There is now quite a bit known about this important problem, e.g.,

Arora, Sanjeev, et al. "Computing a nonnegative matrix factorization--provably." Proceedings of the 44th Symposium on Theory of Computing. ACM, 2012. (ACM link)

Incidentally, NMF played a role in the Netflix Prize problem:

Gábor Takács, et al.  Matrix factorization and neighbor based algorithms for the Netflix prize problem. In: Proceedings of the 2008 ACM Conference on Recommender Systems, Lausanne, Switzerland, 267-274, 2008. (ACM link)

A: You may want to look at the work of Arora, Barak, Ragavendra, Steurer etc relating details of graph spectra to expansion of small sets and to the Unique Games Conjecture.  Sample references are:
Ragavendra–Steurer, Ragavendra–Steurer–Tetali,Arora–Barak–Steurer.
A: Given a symmetric matrix do determine it whether it is copositive is NP-Hard.
