  We consider the concept of "the permutationally 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 $\rho^{{\rm PI}}$ of a general (mixed) $N$-qubit state
$\rho$, we obtain: (i) strong bounds on quantitative nonseparability measures,
(ii) a whole hierarchy of multi-partite separability criteria (one of which
entails a sufficient criterion for genuine $N$-partite entanglement) that can
be experimentally determined by just $2N+1$ 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
multi-partite entanglement measure $E$ that it satisfy $E(\rho)\geq
E(\rho^{{\rm PI}})$, even though the operation that maps
$\rho\rightarrow\rho^{{\rm PI}}$ is not local.
