We introduce a property of a matrix-valued linear map $\Phi$ that we call its ``non-m-positive dimension'' (or ``non-mP dimension'' for short), which measures how large a subspace can be if every quantum state supported on the subspace is non-positive under the action of $I_m \otimes \Phi$. Equivalently, the non-mP dimension of $\Phi$ tells us the maximal number of negative eigenvalues that the adjoint map $I_m \otimes \Phi^*$ can produce from a positive semidefinite input. We explore the basic properties of this quantity and show that it can be thought of as a measure of how good $\Phi$ is at detecting entanglement in quantum states. We derive non-trivial bounds for this quantity for some well-known positive maps of interest, including the transpose map, reduction map, Choi map, and Breuer--Hall map. We also extend some of our results to the case of higher Schmidt number as well as the multipartite case. In particular, we construct the largest possible multipartite subspace with the property that every state supported on that subspace has non-positive partial transpose across at least one bipartite cut, and we use our results to construct multipartite decomposable entanglement witnesses with the maximum number of negative eigenvalues.
 A. Yu. Kitaev ``Quantum computations: Algorithms and error correction'' Russian Mathematical Surveys 52, 1191-1249 (1997).
 K. R. Parthasarathy ``On the maximal dimension of a completely entangled subspace for finite level quantum systems'' Proceedings of the Indian Academy of Sciences (Mathematical Sciences) 114, 365-374 (2004).
 N. Johnston ``How to compute hard-to-compute matrix norms'' http://www.njohnston.ca/2016/01/how-to-compute-hard-to-compute-matrix-norms/ (2016).
 M. Horodeckiand P. Horodecki ``Reduction criterion of separability and limits for a class of distillation protocols'' Physical Review A 59, 4206-4216 (1999).
 W. Hall ``A new criterion for indecomposability of positive maps'' Journal of Physics A: Mathematical and General 39, 14119 (2006).
 R. Sengupta, Arvind, and A. I. Singh, ``Entanglement properties of positive operators with ranges in completely entangled subspaces'' Physical Review A 90, 062323 (2014).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.