# Given a set of unitary matrices, can one find a vector whose images under these unitary matrices span the underlying Hilbert space?

Given a set of (linearly independent) $$d\times d$$ complex unitary matrices $$\{U_i\}_{i=1}^n \subseteq M_d$$ with $$n\geq d$$, does there exist a vector $$v\in \mathbb{C}^d$$ such that $$\text{span} \{U_1v, U_2v, \ldots , U_nv\} = \mathbb{C}^d ?$$

The motivation for this question comes from the theory of mixed unitary quantum channels. A quantum channel $$\Phi: M_d \rightarrow M_d$$ is a completely positive and trace preserving linear map. Any such map admits a Kraus representation of the form $$\Phi (X) = \sum_{i=1}^k A_i X A_i^*$$, where $$\{A_i \}_{i=1}^k \subseteq M_d$$ and $$\sum_{i=1}^k A_i^* A_i = \mathbb{I}_d$$. We say that a quantum channel is mixed unitary if it can be expressed as a convex combination of unitary conjugations: $$\Phi (X) = \sum_{i=1}^n p_i U_i X U_i^*$$. Our aim then is to look for a rank one input projector $$X = vv^*$$ for some $$v\in \mathbb{C}^d$$ such that the output $$\Phi (vv^*) = \sum_{i=1}^n p_i (U_i v) (U_i v)^*$$ has full rank. This is possible only if $$n\geq d$$. To avoid trivial counterexamples, we can also assume that $$\{ U_i\}_{i=1}^n \subseteq M_d$$ is linearly independent.

Follow-up question: Since it has been shown below that the question can be answered in the negative for $$d\geq 4$$, the natural way of progression would be to ask if one can provide a classification of all the sets of (linearly independent) unitary matrices $$\{U_i\}_{i=1}^n \subseteq M_d$$ which allow for the existence of $$v\in \mathbb{C}^d$$ such that $$\text{span}\{U_1v, U_2v, \ldots ,U_nv\}=\mathbb{C}^d.$$ One can also try to answer this question for (linearly independent) sets of arbitrary complex matrices: $$\{ A_i \}_{i=1}^k \subseteq M_d$$.

• The answer is obviously no, if $U_k = e^{it_k}\,I$ with distinct $t_k$. So, would you like these matrices to be linearly independent, for example? – amsmath Mar 1 at 3:03
• @amsmath Yes I've now added this additional assumption in the question. Thanks for pointing this out! – mathwizard Mar 1 at 3:09
• Proof for $d=2$: Assume the two standard basis vectors do not work as $v$. Then $U_1 = [u,v]$ and $U_2 = [su,tv]$ with $s,t\in\mathbb C$, $|s|=|t|=1$. Now, choose a vector $x$ with non-zero entries. Then$$\alpha U_1x + \beta U_2x = \alpha(x_1u + x_2v) + \beta(x_1 su + x_2 tv) = (\alpha + s\beta)x_1u + (\alpha + t\beta)x_2v.$$ Since $u\perp v$, this implies $\alpha + s\beta = \alpha + t\beta = 0$, which is only possible for $(\alpha,\beta)\neq (0,0)$ if $s=t$. But then $U_2 = tU_1$, contradiction! – amsmath Mar 1 at 3:59
• Does it matter that $M_d$ is a $d^2$-dimensional space, yet you're using as few as $d$ matrices? It seems like there is a high chance of a set of $d$ LI matrices not yielding $d$ LI images for any $v$. – Kevin P. Barry Mar 10 at 1:49
• @KevinP.Barry Yes, I think so too. That is why I've included the number $n\geq d$ itself as a parameter when I ask for a classification of sets of matrices $\{A_i\}_{i=1}^n$ which allow the desired vector to exist. If $n$ is close to $d$, then we should expect that our requirement imposes severe constraints on the sets of allowed matrices. If $n> d^2-d$ for instance, the answer by Daniel below shows that the desired vector exists irrespective of what kind of matrices are present in the set! – mathwizard Mar 10 at 2:12

For $$d\geq 4$$ the answer is no. To see why, let $$k=d-2$$, so that $$k\geq 2$$.

By this answer every complex $$k\times k$$ matrix can be written as a linear combination of four unitary matrices. As a consequence, we see that the unitary group $$\mathscr U(k)$$ spans $$M_k(\mathbb C)$$, so it is certainly possible to find a linear independent set formed by $$k^2$$ unitary $$k\times k$$ matrices, say $$\{U_i\}_{1\leq i\leq k^2}$$. Now consider the linearly independent set $$\{I_2\oplus U_i:1\leq i\leq k^2\}\subseteq \mathscr U(k+2) = \mathscr U(d), \tag 1$$ where $$I_2$$ is the $$2\times 2$$ identity matrix.

Given any $$x=(x_1, x_2, \ldots , x_{k+2})\in \mathbb C^{k+2} = \mathbb C^d,$$ notice that every vector of the form $$(I_2\oplus U_i)x$$ is orthogonal to $$y: = (\overline{x_2}, -\overline{x_1}, 0, 0, \cdots , 0)$$ so the set $$\{(I_2\oplus U_i)(x):1\leq i\leq k^2\}$$ cannot span $$\mathbb C^d$$.

As pointed out by @amsmath, if $$x_1=x_2=0$$, we need to argue instead that the vectors $$(I_2\oplus U_i)x$$ have vanishing first two coordinates, hence cannot span $$\mathbb C^d$$ either.

Since $$k\geq 2$$, we have that $$k^2 \geq k+2 = d,$$ so the set in (1) is a linearly independent set with (precisely $$k^2$$, and hence) at least $$d$$ unitary $$d\times d$$ matrices, but there is no vector $$x$$ such that the images of $$x$$ under our matrices span $$\mathbb C^d$$.

There is a simple necessary and sufficient condition for the absence of such $$v$$.

Let $$A_1,\ldots,A_n$$ be linearly independent $$d\times d$$ matrices. Define the completely positive map $$T(X)=\sum_{i=1}^nA_iXA_i^*$$.

Now, let $$u=\sum_{i=1}^de_i\otimes e_i$$, where $$e_1,\ldots,e_d$$ stands for the canonical basis of $$\mathbb{C}^d$$.

It is not hard to prove that for every $$A,B\in M_{d\times d}$$, $$tr(A\otimes B\ uu^*)=tr(AB^t).$$

Thus, we have the following equivalent conditions:

1. $$tr(T(vv^*)ww^*)=0$$
2. $$tr((T(vv^*)\otimes \overline{w}w^t) uu^*)=0$$
3. $$tr((vv^*\otimes \overline{w}w^t)B)=0$$, where $$B$$ is the non-normalized state $$B=T^*(\cdot)\otimes id (uu^*)$$.

Since $$A_1,\ldots,A_n$$ are linearly independent, $$\operatorname{rank}{B}=n$$.

So the absence of such $$v$$ is equivalent to the fact that for every $$v\in\mathbb{C}^d$$ there is a vector $$w\in \mathbb{C}^d\setminus\{\vec{0}\}$$ such that $$v\otimes w\in \ker(B)$$.

In particular, it implies that $$\operatorname{rank}(B)\leq d^2-d$$, since there are at least $$d$$ linearly independent product vectors in its kernel.

Therefore, if the number of matrices above, $$n$$, is greater than $$d^2-d$$ then there exists such $$v$$.

• Very interesting! But, if I understand your answer correctly, the condition $n\leq d^2 -d$ is just a necessary one implied by the absence of such a $v$. I mean this is not sufficient right because even if $n\leq d^2 - d$, such a vector $v$ might exist for some special sets of matrices $\{A_i \}_{i=1}^n$. This is where the follow-up question above becomes important: For which such sets of matrices does the desired vector $v$ exist? – mathwizard Mar 10 at 2:06

Here is an example of a set of $$d$$ unitary matrices $$\{U_i \}_{i=1}^d \subseteq M_d$$ for which the desired vector exists.

For each $$i\in \{1,2,\ldots ,d \}$$, we define $$U_i$$ to be the unitary shift matrix: $$U_i e_k = e_{k+i}$$, where the index addition happens modulo $$d$$ and $$\{e_k \}_{k=1}^d$$ is the standard basis of $$\mathbb{C}^d$$. Then, it should be clear that if we choose $$v=e_1$$ for instance, the set $$\{U_i v \}_{i=1}^d$$ is precisely the standard basis of $$\mathbb{C}^d$$ and hence spans $$\mathbb{C}^d$$.