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](http://en.wikipedia.org/wiki/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.



NP-hard problems in linear algebra and real analysis
Here is one such result.



> 
> Stephen A. Vavasis.
>  "On the complexity of nonnegative matrix factorization."
>  2007. ([arXiv abstract link](http://arxiv.org/abs/0708.4149))
> 
> 
> "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](http://dl.acm.org/citation.cfm?id=2213994))
> 
> 
> 


Incidentally, NMF played a role in [the Netflix Prize problem](http://www.netflixprize.com/):



> 
> 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](http://dl.acm.org/citation.cfm?id=1454049))
> 
> 
> 


