Let $\{v_i\}_{i=1}^m \in \mathbb C^n$ be vectors of norm $1$ so that $F = \max_{i \neq j} \vert v_i^\dagger v_j\vert$ is small. Is it possible to show that $$\lambda_\max(S) = 1 + O(1)mF^2$$ where $$S = \sum_{i=1}^m v_i^\dagger v_i$$ For $F$ close to $1$ it is not too hard to show that $\lambda_\max(S) \leq 1 + mF$, but I am hoping to show that as $F$ gets small the bound can be tightened. To show the $1 + mF$ bound, one simply applies Cauchy-Schwarz once, but the regime where Cauchy-Schwarz is tight is the same regime where $F$ is close to $1$. When $F$ is small the application of Cauchy-Schwarz is not tight and so there should be a way to do better...
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I assume $v_i$ are linearly independent and I believe you wanted to write
$$S = \sum_{i=1}^m v_i v_i^\dagger $$
Let $x$ be an eigenvector of $S$ for a nonzero eigenvalue, so that $Sx = \lambda x, \lambda \neq 0$. Therefore, necessarily $x \in \operatorname{Im} S$. Let $$ x = \sum_{i=1}^m \alpha_i v_i $$ for some $\alpha_i$. So,
$$Sx = \sum_{i=1}^m v_i v_i^\dagger x = \sum_{i=1}^m v_i \left( \sum_{j=1}^m \alpha_j v_i^\dagger v_j \right) = \lambda \sum_{i=1}^m \alpha_i v_i $$
So, for all $i$ we have $$\lambda \alpha_i = \sum_{j=1}^m \alpha_j v_i^\dagger v_j$$
Select $i$ such that $|\alpha_i| = \max_j |\alpha_j|$. Therefore, $$ \begin{align*} | \lambda | | \alpha_i | &\leq \sum_{j=1}^m | \alpha_j | | v_i^\dagger v_j | \\ &= | \alpha_i | + \sum_{j \neq i} |\alpha_j| | v_i^\dagger v_j | \\ &\leq | \alpha_i | \left( 1+ (m-1) F \right) \end{align*}$$
So, we improved the bound as $|\lambda| \leq 1+ (m-1) F$.
We can also show that this bound is the tightest possible by constructing $S$ such that $\lambda = 1+ (m-1) F$. Note that equality occurs if $\alpha_i = \alpha_j$ and $F = v_i^\dagger v_j$ for all $i\neq j$. We can select $m$ linearly independent vectors of norm 1 such that $F = v_i^\dagger v_j$ for all $i\neq j$ for arbitrary $|F|<1$. In this case if $\alpha_i = 1, \forall i$, then $x$ is an eigenvector of $S$. So, we have equality. By the way, for $m=2$ we always have equality for any $v_1,v_2$ since $x=v_1+v_2$ is an eigenvector of $S$ with $\lambda = 1 + v_1^\dagger v_2$.
