We consider the concept of "the permutationaily invariant (PI) part of a density matrix," which has proven very useful for both efficient quantum state estimation and entanglement characterization of N-qubit systems.We show here that the concept is, in fact, basis dependent but that this basis dependence makes it an even more powerful concept than has been appreciated so far.By considering the PI part ρPI of a general (mixed) N-qubit state ρ, we obtain (i) strong bounds on quantitative nonseparability measures, (ii) a whole hierarchy of multipartite separability criteria (one of which entails a sufficient criterion for genuine N-partite entanglement) that can be experimentally determined by just 2N+l measurement settings, (iii) a definition of an efficiently measurable degree of separability, which can be used for quantifying a novel aspect of decoherence of N qubits, and (iv) an explicit example that shows there are, for increasing N, genuinely N-partite entangled states lying closer and closer to the maximally mixed state.Moreover, we show that if the PI part of a state is k nonseparable, then so is the actual state.We further argue to add as requirement on any multipartite entanglement measure E that it satisfy E(ρ)≥E(ρPI), even though the operation that maps ρ-→ ρPI is not local.