Upper bound on smallest singular value with subset condition

Question

Let $v_1,v_2,v_3\in \mathbb{R}^2$ (view as column vectors), if we have $$\lambda_{\min}(v_iv_i^T+v_jv_j^T)\le 1,~\text{for all }i\not=j\in\{1,2,3\}.$$

Can we have an upper bound for $$\lambda_{\min}(v_1v_1^T+v_2v_2^T+v_3v_3^T).$$

I guess it will be upper bounded by $3$ but have not idea how to prove it. Any idea will be appreciate.

Answer 1

When $u_1 = [-\frac{\sqrt{2}}{2}, \ \frac{\sqrt{6}}{2}]^T, \ u_2 = [\frac{\sqrt{2}}{2}, \ \frac{\sqrt{6}}{2}]^T, \ u_3 = [\sqrt{2}, \ 0]^T$, we have $\lambda_{\min}(u_1u_1^T + u_2u_2^T) = \lambda_{\min}(u_1u_1^T + u_3u_3^T) = \lambda_{\min}(u_2u_2^T + u_3u_3^T) = 1$ and $\lambda_{\min}(u_1u_1^T + u_2u_2^T+u_3u_3^T) = 3$.

Next, let us prove that $\lambda_{\min}(u_1u_1^T + u_2u_2^T+u_3u_3^T)\le 3$.

If $\min(u_1^Tu_1, u_2^Tu_2, u_3^Tu_3)< 2$, WLOG, assume that $u_3^Tu_3 < 2$. Applying Weyl's inequality about perturbation, we have $\lambda_{\min}(u_1u_1^T + u_2u_2^T+u_3u_3^T) \le \lambda_{\min}(u_1u_1^T + u_2u_2^T) + u_3^Tu_3 < 3.$

In the following, assume that $u_1^Tu_1 \ge 2,\ u_2^Tu_2 \ge 2$ and $u_3^Tu_3 \ge 2$. WLOG, assume that $\lambda_{\min}(u_1u_1^T + u_3u_3^T) = 1$ and $\lambda_{\min}(u_2u_2^T + u_3u_3^T)= 1$ and $u_3 = [x, \ 0]^T$ (the reason is simple).

Let $u_1 = [a, \ b]^T, \ u_2 = [c, \ d]^T.$ We have $a^2+b^2\ge 2, \ c^2+d^2\ge 2$ and $x^2\ge 2$. We have $$\lambda_{\min}(u_1u_1^T + u_2u_2^T)\le 1 \Longrightarrow (a^2+b^2-1)(c^2+d^2-1) - a^2c^2 - b^2d^2 \le 2abcd, $$ $$\lambda_{\min}(u_1u_1^T + u_3u_3^T) = 1 \Longrightarrow (b^2-1)x^2 = a^2+b^2-1, $$ $$\lambda_{\min}(u_2u_2^T + u_3u_3^T)= 1 \Longrightarrow (d^2-1)x^2 = c^2+d^2 - 1. $$ We have $$\lambda_{\min}(u_1u_1^T + u_2u_2^T+u_3u_3^T) \le 3 \Longleftarrow (a^2+c^2+x^2-3)(b^2+d^2 - 3)-a^2b^2 - c^2d^2 \le 2abcd .$$ It suffices to prove that $(a^2+c^2+x^2-3)(b^2+d^2 - 3)-a^2b^2 - c^2d^2 \le 2abcd.$

If $b^2+d^2 \le 3$, clearly the inequality is true.

If $b^2+d^2 > 3$, noting that $(b^2+d^2-1)x^2 - 4 \ge 2x^2-4\ge 0$ and (simply applying the conditions above) \begin{align*} &(a^2+c^2+x^2-3)(b^2+d^2 - 3)-a^2b^2 - c^2d^2\\ =\ & (a^2+b^2-1)(c^2+d^2-1) - a^2c^2 - b^2d^2 - ((b^2+d^2-1)x^2 - 4)\\ \le\ & (a^2+b^2-1)(c^2+d^2-1) - a^2c^2 - b^2d^2\\ \le \ & 2abcd, \end{align*} the inequality is true.

Answer 2

The upper bound is $\geq 3$.

Take $v_1=[\sqrt{2},0]^T,v_2=Rot(v_1,2\pi/3),v_3=Rot(v_1,-2\pi/3)$. Then $\lambda_{\min}(v_1v_1^T+v_2v_2^T+v_3v_3^T)=3$.

EDIT. A partial converse for "the upper bound is indeed $3$".

If $v_j=[\alpha_j,\beta_j]^T$, then we put $z_j=\alpha_j+i\beta_j$. The $3$ constraints can be written

$\lambda_{min}(v_jv_j^T+v_kv_k^T)=1/2(|z_j^2|+|z_k^2|-|z_j^2+z_k^2|)\leq 1$.

The function to maximize can be written

$g=\lambda_{min}(v_1v_1^T+v_2v_2^T+v_3v_3^T)=1/2(|z_1^2|+|z_2^2|+|z_3^2|-|z_1^2+z_2^2+z_3^2|)$.

We change the complex $z_j^2$ into the complex $u_j=a_j+ib_j$. Finally, the $3$ constraints are

$\sqrt{a_j^2+b_j^2}+\sqrt{a_k^2+b_k^2}-\sqrt{(a_j+a_k)^2+(b_j+b_k)^2}\leq 2$

and the function to maximize is

$f(a_j,b_j)=2g=\sqrt{a_1^2+b_1^2}+\sqrt{a_2^2+b_2^2}+\sqrt{a_3^2+b_3^2}-\sqrt{(a_1+a_2+a_3)^2+(b_1+b_2+b_3)^2}$.

Numerical experiments, using the Maple's software "optimization", seem to show that $sup(f)=6$ and is reached only by any rotation of the figure described in the first part of my post (line 2).