**Setting:**  

Suppose $\{u\_i\}\_{i=1}^n \subset R^d$ is a collection of unit vectors such that $u\_i^Tu\_j < 0$ for all $i\neq j$, and $w$ is a unit vector such that $u\_i^T w> 0$ for all $i=1,\dotsc,n$. Let $a \in R^d$ be a unit vector.


**Goal:**  

We want to show that the following hold or to find a counter-example.


$$\sum\_{i=1}^n \lvert u\_i^T a\rvert u\_i^T w < 1$$


We can prove this statement for the case of $n=2$, but we were not able to prove it for $n>2$.


Any suggestions?


**Update:**  

We used **Echo**'s approach from the comment. It worked for the first iteration (when the local maximum is an interior point) from the stationarity condition of the gradient. However, we got stuck at the second iteration (when one of the constraints was active). So now we have a stationarity condition on the projected gradient. We couldn't solve this. Any help would be appreciated.



Prove/disprove a linear algebra inequality
Notation:
$[n] = \{1,\dotsc,n\}$.
For symmetric $n \times n$ matrices $A,B$, $A \succ B$ and $A \succeq B$ means that $A-B$ is positive definite / positive semidefinite.
For a symmetric matrix $A$, $\lambda\_{\min}(A)$ and $\lambda\_{\max}(A)$ denote its minimal and maximal eigenvalues.


Claim:
If $n \ge 2$, and $u\_1, \dotsc, u\_n, w, a \in \mathbb{R}^d$ are unit vectors such that $u\_j^T u\_k < 0$ for every $j \neq k$, and $u\_j^T w > 0$ for every $j$, then $\sum\_j |u\_j^T a| (u\_j^T w) < 1$.


Proof:
If $u\_j^T a = 0$ for every $j$, or $u\_j^T w = 0$ for every $j$, then this is trivial.
Otherwise we can replace $a$ by a scalar multiple of its orthogonal projection onto $\sum\_j \mathbb{R} u\_j$, and the same for $w$.
So we assume that $a, w \in \sum\_j \mathbb{R} u\_j$, and we can then also assume that $\mathbb{R}^d = \sum\_j \mathbb{R} u\_j$.
We prove by induction on $n$.


Let $G = (u\_j^T u\_k)\_{j,k \in [n]} \succeq 0$ be the Gram matrix of $(u\_j)\_{j=1}^n$, and let $M = I-G$.
Then $M\_{j,j} = 0$ for every $j$, and $M\_{j,k} > 0$ for $j \neq k$.
Using the Perron-Frobenius theorem (<https://en.wikipedia.org/wiki/Perron-Frobenius_theorem>) for $\epsilon I + M$ with $\epsilon > 0$, we get that its maximal eigenvalue $\epsilon + \lambda\_{\max}(M)$ has multiplicity $1$, and it has a corresponding eigenvector in $\mathbb{R}\_{>0}^n$, and $\epsilon + \lambda\_{\min}(M) \ge -(\epsilon + \lambda\_{\max}(M))$.
Taking $\epsilon \to 0$, we get $\lambda\_{\min}(M) \ge -\lambda\_{\max}(M)$.
So $\lambda\_{\max}(G) + \lambda\_{\min}(G) \le 2$, and we also see that the eigenvalue $\lambda\_{\min}(G)$ of $G$ has multiplicity $1$.
We could also use the same argument for $(u\_1,\dotsc,u\_n, -w)$ instead of $(u\_1,\dotsc,u\_n)$, and get an $(n+1) \times (n+1)$ Gram matrix $G' \succeq 0$, where $\lambda\_{\min}(G') = 0$ has multiplicity $1$, so $\operatorname{rank}(u\_1,\dotsc, u\_n) = \operatorname{rank}(G') = n$.
So $u\_1, \dotsc, u\_n$ are linearly independent (so $d = n$), and thus $G \succ 0$ and $0 < \lambda\_{\min}(G)$ and $\lambda\_{\max}(G) < 2$, so $-I \prec M \prec I$.
We cannot have $\lambda\_{\min}(G) = \lambda\_{\max}(G) = 1$, because then $M = 0$.
So $\lambda\_{\min}(G) \in (0,1)$.
Note that $G^{-1} = (I-M)^{-1} = I+M+M^2+\dotsm$ (this converges, because $-I \prec M \prec I$), so $(G^{-1})\_{j,k} > 0$ for every $j,k$.
So by the Perron-Frobenius theorem, $G^{-1}$ has a unique unit length eigenvector in $\mathbb{R}\_{>0}^n$, and the corresponding eigenvalue is $\lambda\_{\max}(G^{-1})$ (this will be used later).


We fix linearly independent unit vectors $(u\_j)\_{j \in [n]}$, and choose unit vectors $a, w$ in $\mathbb{R}^d$ so that $S = \sum\_j |u\_j^T a| (u\_j^T w)$ is maximal, only requiring $u\_j^T w \ge 0$ for every $j$.
If $u\_j^T w = 0$ or $u\_j^T a = 0$ for some $j$, then we are done by induction.
So let $u\_j^T w > 0$ and $u\_j^T a \neq 0$ for every $j$.
Then $S > 0$.
Let $a = \sum\_j \alpha\_j u\_j$ and $w = \sum\_j \beta\_j u\_j$.
Then $1 = \|a\|^2 = \alpha^T G \alpha$, $1 = \|w\|^2 = \beta^T G \beta$, and $u\_j^T a = (G \alpha)\_j \neq 0$ and $u\_j^T w = (G \beta)\_j > 0$.
Let $D$ be the diagonal matrix such that $D\_{j,j} = \operatorname{sgn}(u\_j^T a) = \operatorname{sgn}((G \alpha)\_j)$ for every $j$.
Then $S = \sum\_j (G \alpha)\_j D\_{j,j} (G \beta)\_j = \alpha^T G D G \beta$.
Because $(\alpha, \beta)$ give a local maximum for $S$, the differential of the map $\mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}^3$, $(\alpha, \beta) \mapsto (\alpha^T G \alpha, \beta^T G \beta, \alpha^T G D G \beta)$ does not have full rank at our $(\alpha, \beta)$.
So there is an $(A, B, C) \in \mathbb{R}^3 \setminus \{0\}$ such that
$$
2 A G \alpha + C G D G \beta = 2 B G \beta + C G D G \alpha = 0.
$$
Then $0 = \alpha^T (2 A G \alpha + C G D G \beta) = 2 A + C S$ and $0 = \beta^T (2 B G \beta + C G D G \alpha) = 2 B + C S$, so $A = B = -\frac{C}{2} S$, where $C \neq 0$.
So $GDG \beta = S G \alpha$ and $GDG \alpha = S G \beta$.
So if $x\_0 = G \alpha$ and $y\_0 = G \beta$, then $(x\_0,y\_0)$ satisfies $1 = x\_0^T G^{-1} x\_0 = y\_0^T G^{-1} y\_0$, $GD x\_0 = S y\_0$, $GD y\_0 = S x\_0$.
The idea is to study the pairs $(x,y)$ that satisfy these equations, because these could maybe also give the same maximal $S$, so in some cases we could vary $(\alpha, \beta)$ even if $S$ is already maximal.
Note that $(x\_0, y\_0)$, $(-x\_0, -y\_0)$, $(y\_0, x\_0)$, $(-y\_0, -x\_0)$ all satisfy these equations
Idea: If $(x,y)$ is on the ellipse centered at $0$ going through these four points, then it should also satisfy these equations.
In detail:
Let $p = x\_0+y\_0$, $q = x\_0-y\_0$, $P = p^T G^{-1} p$, $Q = q^T G^{-1} q$.
Then $GD p = S p$, $GD q = -Sq$ (so $p,q$ are eigenvectors of $GD$), $p^T G^{-1} q = 0$, $P, Q \ge 0$ and $P + Q = 4$.
Let us take $x = sp + tq$ and $y = sp - tq$ for $s, t \in \mathbb{R}$.
Then $GD x = S y$ and $GD y = S x$ hold, and $x^T G^{-1} x^T = y^T G^{-1} y^T = P s^2 + Q t^2$, so we need this to be $1$.
Then $GDy=Sx$, so $x^T D y = S x^T G^{-1} x = S$.
So if $P s^2 + Q t^2 = 1$, then $(x,y) = (sp + tq, sp - tq)$ gives the same maximal $S$.


If $p = 0$ or $q = 0$ (so $a = \pm w$):
Then $D = (\operatorname{sgn}(u\_j^T a))\_{j=1}^n = \pm I$ and $G y\_0 = S y\_0$, so $G^{-1} y\_0 = S^{-1} y\_0$.
Here $(y\_0)\_j = u\_j^T w > 0$ for every $j$, so $y\_0$ is a Perron-Frobenius eigenvector for $G^{-1}$, thus $S^{-1} = \lambda\_{\max}(G^{-1})$, so $S = \lambda\_{\min}(G) < 1$.


Now let $p,q \neq 0$.
Then $P, Q > 0$, so we get an ellipse.
For $s = t = \frac{1}{2}$ we get $(x,y) = (x\_0, y\_0)$, for $s = t = -\frac{1}{2}$ we get $(x,y) = (-x\_0, -y\_0)$.
So moving along the ellipse, we can get from $(a,w)$ to $(-a, -w)$, without changing $S$.
So there will be a first point where some $u\_j^T a$ or $u\_j^T w$ becomes $0$, and then we are done by induction.


