Can a single-qubit state be nontrivially extended to a non-pure state? Consider a generic single-qubit state
$$\rho=\lambda_1\lvert \lambda_1\rangle\!\langle \lambda_1\rvert+\lambda_2\lvert \lambda_2\rangle\!\langle \lambda_2\rvert\in\mathcal H_S.$$
I am interested in understanding what are the possible extensions of $\rho$, that is, the states $\tilde\rho\in\mathcal H_{SE}$ such that 
$\operatorname{tr}_E(\tilde\rho)=\rho.$
If is relatively easy to find the general structure of extensions that are pure, but less so in the more general case of non-pure extensions.
In particular, is it possible to have a non-trivial extension of $\rho$ which is not a purification?
By non-trivial here I mean that it must also decrease the amount of uncertainty associated with $\rho$. This means no trivial extensions of the form $\tilde\rho=\rho\otimes\sigma$, and no extensions built by simply attaching a set of orthonormal states to the eigenvectors of $\rho$, that is, no extensions of the form $\tilde\rho=\sum_k \lambda_k \lvert\lambda_k\rangle\!\langle\lambda_k\rvert\otimes\sigma_k$ with $\lambda_k$ the eigenvalues of $\rho$.
 A: Sure. Just take any random purification with a large purifying space $\mathbb C^2\otimes C^d$, and trace the $\mathbb C^d$ component.
To give a randomly made up example,
$$
\rho = \left(\begin{matrix}
.25 & .20 & .10 & .05 \\
.20 & .25 & .00 & .05 \\
.10 & .00 & .25 & -.15 \\
.05 & .05 & -.15 & .25 
\end{matrix}\right)
$$
is a purification of the state
$$
\rho_A = \left(\begin{matrix}
.50 & .05 \\ .05 & .50
\end{matrix}\right)\ .
$$
That the example is not compatible with the special forms $\tilde\rho$ you give above can  be straightforwardly checked from the eigenvalues of $\rho$, which are incompatible with the forms $\tilde\rho$ you give above -- for  both those $\tilde\rho$, it holds that the eigenvalues of $\rho$ can be written as a sum of two  eigenvalues of $\tilde\rho$ each, which can be easily tested not to be the case.
To explain the last argument in more detail: 
Let $\tilde\rho=\sum \lambda_k |\lambda_k\rangle\langle\lambda_k|\otimes\sigma_k$ (which includes the first purification if all $\sigma_k$ are equal). Denote by $\mu_i(\sigma_k)$ the eigenvalues of $\sigma_k$. Then, the eigenvalues of $\tilde\rho$ are
$$
\tau_{i,k} = \lambda_k\,\mu_i(\sigma_k)\ .
$$
Thus, we have that
$$
\sum_i\tau_{i,k} = \lambda_k
$$
(as $\mathrm{tr}\,\sigma_k=1)$, i.e., each two (where "two" is the dimension of the purification) eigenvalues of $\tilde\rho$ add up to an eigenvalue $\lambda_k$ of $\rho$.

It can be easily checked that this property does not hold for the example.

Note that this richness of extensions is exactly a problem in computing the squashed entanglement, where one optimizes over (non-pure) extensions of arbitrary dimensions.
