Constructing a POVM to discriminate $m$ quantum states. What if they're linearly dependent? I've come across this problem in Nielsen & Chuang's Quantum Information book (problem 2.64)
Suppose Bob is given a quantum state chosen from a set $|ψ_1 \rangle, . . . , |ψ_m\rangle$
of linearly independent states. Construct a POVM $\{E_1, E_2, . . ., E_{m+1}\}$ such that
if outcome $E_i$ occurs, $1 ≤ i ≤ m$, then Bob knows with certainty that he was
given the state $|ψ_i\rangle$. (The POVM must be such that $\langle ψ_i|E_i|ψ_i \rangle > 0$ for each $i$.)
This is my proposed solution:
Denote by $|\phi_i\rangle$ the (unique? I guess it doesn't matter) vector orthogonal to the subspace spanned by $\{ | \psi_j \rangle \}_{j \neq i}$ and define 
$$E_i = \sum_{i\neq j} | \phi_j \rangle \langle\phi_j |$$
Then $\langle \psi_j | E_i | \psi_j\rangle = 0$ by construction, and $\langle \psi_i | E_i | \psi_i\rangle > 0$. The last operator is defined to satisfy completeness:
$$E_{m+1} = \mathbb{I} - \sum_{j=1}^m E_j.$$
So, when get gets outcome $i$, he knows it can't have been any of the other $\psi_j$'s, so it must have been $\psi_i$ for sure. If he gets outcome $m+1$, he doesn't know anything. Is this correct? 
What happens if now we introduce another vector to the set: $\psi \rangle = a |ψ_1 \rangle + b |ψ_2 \rangle$, i.e. drop the linear independence condition (just on a simple example here). How would that affect the $E_j$'s, is it still possible to construct a POVM like that?
 A: A crucial hypothesis is missed in your construction. 
Each $\phi_i$ must also satisfy $\phi_i \not \perp \psi_i$, otherwise $\langle \psi_i |E_i \psi_i\rangle >0$ is false.
This point provides an answer to your last question as well. 
If $\psi$ is an added further vector, linearly dependent on the vectors $\psi_i$, the construction you made cannot be re-proposed as the constraint I pointed out cannot be satisfied. Indeed, even if the correspondingly added normalized vector $\phi$ is orthogonal to all $\psi_i$, it is (evidently) impossible that $\phi \not \perp \psi = \sum_{i=1}^n c_i \psi_i$.
A: The implicit context of this exercise is some Hilbert space $H$ of dimension at least $m$. Let $W$ be the ($m$-dimensional) subspace of $H$ spanned by the set $\{|\psi_1\rangle, ..., |\psi_m\rangle\}$ and let, for each $i=1,...,m$, $V_i$ be the ($m-1$ dimensional) subspace of $W$ spanned by the set $\{|\psi_{j}\rangle \mid j \neq i\}$. 
From elementary Hilbert space theory we know that each of the vectors $|\psi_i\rangle$ can be split up into a sum $|\psi_i\rangle = |v_i\rangle + |o_i\rangle$, where $|v_i\rangle \in V_i$ and $|o_i\rangle \in V_i^\perp \cap W$ ($|v_i\rangle$ is the orthogonal projection of $|\psi_i\rangle$ onto $V_i$ and $|o_i\rangle = |\psi_i\rangle - |v_i\rangle)$. Note that $|o_i\rangle \neq 0$ for each $i$, as $|\psi_i \rangle$ by the assumption of linear independence does not belong to $V_i$.
Now let $E_i=\frac{|o_i\rangle\langle o_i|}{m+1}$, for $i=1,...,m$, and let $E_{m+1} = I - \sum_{j=1}^m E_j$. Then it's an easy check that set of operators $\{E_1, ...,E_{m+1}\}$ satisfies the requirements for a POVM (the factors $\frac{1}{m+1}$ are to make sure that $E_{m+1}$ stays positive). Furthermore, for $1\leq i, k \leq m$ with $i\neq k$, we have $\langle\psi_k|E_i|\psi_k\rangle = 0$, and 
$$\langle\psi_i|E_i|\psi_i\rangle = \frac{1}{m+1}\big( \langle v_i|o_i\rangle + \langle o_i|v_i\rangle + 2\langle o_i|o_i\rangle \big) = \frac{2}{m+1}\langle o_i|o_i\rangle>0,$$ as wanted.
