0
$\begingroup$

Let $u,v,x \in \mathbb R^d$ be three unit vectors. I found a very complicated proof that $(v^Tx)^2-(u^Tx)^2 \leq 1-(u^Tv)^2$. That is $\lVert uu^T-vv^T\rVert^2_2 = 1-(u^Tv)^2$, or that $f(v,x)\leq f(v,u)+f(u,x)$ where $f(v,u)=1-(v^Tu)^2$ is the squared sine of the angle between $u$ and $v$.

Is there a one-liner proof?

Say, using the (spherical?) law of cosines or the Haversine formula? Induced norm for positive semi-definite matrices?

Edit: Thank you all for the quick answers. I am confused by the counter examples. I tried to cite Lemma 27 in a paper (I think from STOC'15): https://arxiv.org/abs/1606.05225 The eigenvalue of $||uu^T-vv^T||_2$ seems to be correct by How to find the eigenvalues of $xx^T-yy^T$

Edit 2: I assumed that all the conjectures in the question are equivalent but maybe I was wrong. I took the Schur Decomposition $USU^T$ of $uu^T-vv^T$ to get $\max_{||x||=1} ||(uu^T-vv^T)x||^2=||USU^Tx||^2=S_{1,1}^2$ and assumed it is the same $\max_{||x||=1} |x^T(uu^T-vv^T)x|^2=|x^TUSU^Tx|=S_{1,1}^2$. Then I noticed that $|x^T(uu^T-vv^T)x|^2=|(x^Tu)^2-(v^Tx)|$. Not sure what went wrong.

Summary: As GH from Mo noted below, I forgot a squared root in the right hand side and the statement is wrong. Hope to get your help also in the fixed version here

Improve this question
$\endgroup$
3
  • $\begingroup$ An equivalent formulation: $\langle v, x\rangle^2 + \langle u, v\rangle^2 \le \langle u, u\rangle^2 + \langle u, x\rangle^2$. $\endgroup$
    – LSpice
    Commented Jan 29, 2022 at 23:32
  • 1
    $\begingroup$ Just to check something: The claim is that the square of the sine ($f$) satisfies the triangle inequality. But for very tiny angles between $u, v, w$ then the sine of those angles is roughly Euclidean distance, and the square of Euclidean distance violates the triangle inequality. So it's surprising that this equation would hold for tiny angles. Have you checked cases like $u = (0, \epsilon, \sqrt{1 - \epsilon^2})$, $v = (0, 0, 1)$, and $x = (0,-\epsilon, \sqrt{1 - \epsilon^2})$ ? Some quick algebra indicates this might be problematic when $\epsilon$ is tiny, but I may be getting confused. $\endgroup$
    – Martin M. W.
    Commented Jan 29, 2022 at 23:33
  • 2
    $\begingroup$ Indeed, with @MartinM.W.'s example, I find that $(1 - \langle u, v\rangle^2) - (\langle v, x\rangle^2 - \langle u, x\rangle^2)$ equals $2\epsilon^2(2\epsilon^2 - 1)$, which, for $\epsilon = 1/2$ (to pick a random example), gives $-1/4$, contrary to your conjecture. $\endgroup$
    – LSpice
    Commented Jan 29, 2022 at 23:39

1 Answer 1

Reset to default
3
$\begingroup$

The inequality as stated is false, but it is true that $$\langle v,x\rangle^2+\langle v,u\rangle^2\leq 1+|\langle x,u\rangle|.$$ Moreover, the right-hand side is optimal in the sense that it is the maximum of the left-hand side over the unit vectors $v$. More generally, if $u_1,\dots,u_R$ are any vectors in a Hilbert space, then $$\max_{\langle v,v\rangle=1}\sum_{r=1}^R|\langle v,u_r\rangle|^2$$ equals the largest eigenvalue of the Gram matrix $(\langle u_s,u_t\rangle)_{1\leq s,t\leq R}$. For details, see these notes on the Bombieri-Halász-Montgomery inequality.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks! Do you agree with the original equality $||uu^T-vv^T||^2_2=1-(u^Tv)^2$? If yes, can we use a similar technique to prove it? $\endgroup$
    – Dan Feldman
    Commented Jan 30, 2022 at 0:07
  • $\begingroup$ @QueenMath - Do you mean $\|uu^T - vv^T\|_2^2 = 2 - 2(u^Tv)^2$? That equality follows immediately from the definition of the Frobenius norm (by subscript $2$, do you mean the Frobenius norm, aka the Schatten 2-norm?). $\endgroup$
    – Nathaniel Johnston
    Commented Jan 30, 2022 at 0:14
  • $\begingroup$ @QueenMath Please ask separate questions in a separate post. I answered your question. Your conjecture is false. I fixed it and generalized it to an arbitrary number of vectors. $\endgroup$
    – GH from MO
    Commented Jan 30, 2022 at 0:15
  • $\begingroup$ ||A||_2 in my question is the largest eigenvalue of a matrix, $\max_x ||Ax||_2/||x||$ where $A=uu^T-vv^T$ is a matrix. Not the Frobenius norm (sum of squared entries) of $A$. $\endgroup$
    – Dan Feldman
    Commented Jan 30, 2022 at 0:17
  • 1
    $\begingroup$ @QueenMath Your question (as in the title) was about an inequality that is false. This means that whatever complicated proof you had, it was incorrect. Now your identity has little to do with your inequality. Your confusion seems to be two-fold. First, you seem to confuse the Frobenius norm and the $L^2$-norm of a matrix. In your previous remark, you talk about the $L^2$-norm of $A$. The square of this norm is the maximum of $\|A x\|^2=x^TA^TAx$ over the unit vectors $x$, and it has little to do with the maximum of $(v^Tx)^2-(u^Tx)^2$ over the unit vectors $x$. $\endgroup$
    – GH from MO
    Commented Jan 30, 2022 at 0:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .