An inequality on some pairs of orthogonal vectors

Question

Let $n,k\geq 1$. Suppose that $a_1, \ldots, a_n\in \mathbb{R}^k$, $b_1, \ldots, b_n\in \mathbb{R}^k$ and $a_i^T b_i = 0$ for $i=1,\dots, n$. Is it true that $$ \sum_{i=1}^n \|a_i\|_2^2 + \sum_{i=1}^n \|b_i\|_2^2 \geq \frac3n \sum_{i,j=1}^n | a_i^T b_j | $$

---

A matrix reformulation of the problem: Let $A$ be a matrix, we have (e.g. see here) $\|A\|_{(1)} = \frac 12 \min_{A=U^TV} (\|U\|_F^2 + \|V\|_F^2)$ where $\|A\|_{(1)}$ is the sum of singular values of $A$ (known as the trace/nuclear norm). Now, the above problem could be stated as follows

Let $A = [a_{ij}]$ be an $n \times n$ matrix with zero diagonal. Is it true $$ \|A\|_{(1)} \geq \frac12\frac{3}{n} \sum_{i,j}|a_{ij}| $$

Answer 1

We shall prove the inequality \begin{equation*} \sum_{i=1}^n|a_i|^2+\sum_{i=1}^n|b_i|^2\ge\frac Cn \sum_{i,j=1}^n|a_ib_j| \tag{0} \end{equation*} with $C:=4/\sqrt3=2.309\dots$. We use the notations $|a|:=\|a\|_2$ and $ab:=a^Tb$. Without loss of generality, the $a_i$ and $b_j$'s are nonzero vectors.

For two nonzero vectors $a$ and $b$, let $d(a,b)\in[0,\pi/2]$ denote the angle between the straight lines carrying the vectors $a$ and $b$. The function $d$ is a pseudometric, since the big circles are the geodesic lines on the 2D sphere.

For $i,j$ in $[n]:=\{1,\dots,n\}$, let then $$d_{ij}:=d(a_i,b_j)=\arccos c_{ij},\quad c_{ij}:=\frac{|a_ib_j|}{|a_i|\,|b_j|},$$ so that $d_{ij}\in[0,\pi/2]$ is the angle between the straight lines carrying the vectors $a_i$ and $b_j$.

Take any $i,j,k$ in $[n]:=\{1,\dots,n\}$. Since $a_ib_i=0$ and $d$ is a pseudometric, \begin{equation*} |d_{ki}-\pi/2|=|d_{ki}-d_{ii}|\le d(a_i,a_k)=:t \end{equation*} and hence \begin{equation*} |a_kb_i|\le|a_k|\,|b_i|\sin t. \tag{1} \end{equation*} Moreover, again because $d$ is a pseudometric, \begin{equation*} t\le d_{ij}+d_{kj}. \tag{2} \end{equation*}

If $d_{ij}+d_{kj}\ge\pi/2$, then $d_{kj}\in[\pi/2-d_{ij},\pi/2]\subseteq[0,\pi/2]$ and hence $c_{ij}^2+c_{kj}^2\le\cos^2 d_{ij}+\cos^2(\pi/2-d_{ij})=1\le5/4$, so that \begin{equation*} c_{ki}^2+c_{ij}^2+c_{kj}^2\le9/4. \tag{3} \end{equation*} If $d_{ij}+d_{kj}<\pi/2$, then (2) implies $\sin t\le\sin(d_{ij}+d_{kj})$. So, by (1), \begin{equation*} c_{ki}\le c_{kj}\sqrt{1-c_{ij}^2}+c_{ij}\sqrt{1-c_{kj}^2}. \end{equation*} Now the Cauchy--Schwarz inequality yields \begin{equation*} c_{ki}^2\le(c_{kj}^2+c_{ij}^2)(2-c_{kj}^2-c_{ij}^2). \end{equation*} The latter inequality together with the conditions that $c_{ki}^2,c_{kj}^2,c_{ij}^2$ are in $[0,1]$ implies (3). Thus, (3) holds for any $i,j,k$.

Therefore, \begin{equation*} \frac94\,n^3\ge\sum_{i,j,k\in[n]}(c_{ki}^2+c_{ij}^2+c_{kj}^2) =3n\sum_{i,j\in[n]}c_{ij}^2, \end{equation*} so that \begin{equation*} \sum_{i,j\in[n]}c_{ij}^2\le\frac34\,n^2, \end{equation*} which further implies \begin{align*} \sum_{i,j\in[n]}|a_ib_j|&=\sum_{i,j\in[n]}c_{ij}|a_i|\,|b_j| \\ &\le\sqrt{\sum_{i,j\in[n]}c_{ij}^2} \sqrt{\sum_{i,j\in[n]}|a_i|^2\,|b_j|^2} \\ &=\sqrt{\sum_{i,j\in[n]}c_{ij}^2} \sqrt{\sum_{i\in[n]}|a_i|^2}\,\sqrt{\sum_{j\in[n]}|b_j|^2} \\ &\le\sqrt{\frac34\,n^2}\times\frac12\,\Big(\sum_{i\in[n]}|a_i|^2+\sum_{j\in[n]}|b_j|^2\Big), \end{align*} so that we do have (0) with $C=4/\sqrt3$.

Answer 2

I guess it is time to post the proof for the constant $\pi$ in the $k=2$ case to avoid any further controversy there. It won't hurt because it is rather clear what its boundaries are, so nobody will get stuck with a dead end idea (which might happen if I post the $1+\sqrt 3$ argument in higher dimension).

As Ivan observed, we need to estimate the integral $\langle (f\mu)*K,g\mu\rangle=\int_{\mathbb T}[(f \mu)*K]\,d(g \mu)$ where $\mu$ is the (let's say, normalized to $\mu(\mathbb T)=1$) counting measure of the set of directions of $a_i$, $f$ describes the lengths of $a_i$, $g$ describes the lengths of $b_i$, $\mathbb T=\mathbb R/\mathbb Z$ and $K(t)=|\sin 2\pi t|$. Since $K$ is real even, we can write $f=u+v$, $g=u-v$ and get $\langle (f\mu)*K,g\mu\rangle=\langle (u\mu)*K,u\mu\rangle-\langle (v\mu)*K,v\mu\rangle$. Now, going to the Fourier side and observing that $\widehat K(n)=\frac 1\pi\frac{1+\cos(\pi n)}{1-n^2}$ (i.e., $\widehat K(0)=\frac 2\pi$ and $\widehat K(n)\le 0$ for $n\ne 0$, $\sum_{n\ne 0}\widehat K(n)=-\frac 2\pi$), we get $$ \langle (u\mu)*K,u\mu\rangle=\sum_n \widehat K(n)|\widehat{(u\mu)}(n)|^2\le \frac 2\pi|\widehat{(u\mu)}(0)|^2\le \frac 2\pi\int_{\mathbb T} u^2\,d\mu $$ and $$ -\langle (v\mu)*K,v\mu\rangle=-\sum_n \widehat K(n)|\widehat{(v\mu)}(n)|^2\le \frac 2\pi\max_{n\ne 0}|\widehat{(v\mu)}(n)|^2\le \frac 2\pi\int_{\mathbb T} v^2\,d\mu\,, $$ so $$ \langle (f\mu)*K,g\mu\rangle\le \frac 2\pi\left[\int_{\mathbb T} u^2\,d\mu+ \int_{\mathbb T} v^2\,d\mu\right]=\frac 1\pi\left[\int_{\mathbb T} f^2\,d\mu+\int_{\mathbb T} g^2\,d\mu\right]\,, $$ which is equivalent to the original inequality with constant $\pi$ instead of $3$. The example showing that $\pi$ is sharp has already been mentioned.

Unfortunately, this simple argument seems rather hard to generalize to higher dimensions (though I may miss some trick). However, it may be possible to reduce the general case to the 2-dimensional one somehow (though I don't know how), in which case the above proof may become useful.

Answer 3

$\def\Tr{\mathrm{Tr}}\def\Mat{\mathrm{Mat}}$I've been thinking about this problem a bunch, and I think the correct bound is $$ \sum_{i,j} |A_{ij}| \leq \left( \cot \frac{\pi}{2n} \right)|A|_{(1)}. $$ As $n \to \infty$, we have $\cot \tfrac{\pi}{2n} \sim \tfrac{2n}{\pi}$, so this matches the $\pi$ bound that fedja proved for $k=2$. In particular, I will prove that this bound is correct for skew-symmetric $A$; almost all the work is not due to me but to a paper of Grzesik, Kral, Lovasz and Volec which was pointed out in a deleted answer by another user.

I'll write $\sigma_1(A) \geq \sigma_2(A) \geq \cdots$ for the singular values of $A$. Note that we have $$\sum |A_{ij}| = \max_{P \in \mathrm{Mat}_n(\pm 1)} \Tr(AP) $$ and $$|A|_{(1)} = \max_{Q \in O(n)} \Tr(AQ). $$ Here $P$ is ranging over $\pm 1$ matrices, and $Q$ is ranging over the orthogonal group.

We may replace the orthogonal group by its convex hull without changing the max. The convex hull of $O(n)$ is the set of matrices of operator norm $\leq 1$; call that $B_1$. So $$|A|_{(1)} = \max_{R \in B_1} \Tr(AR). $$

As a warm up, let's consider the best inequality we can prove of the form $\sum |A_{ij}| \leq C |A|_{(1)}$ without imposing that the diagonal is $0$. The answer is that the best is $C = n$, and that is easy to prove by elementary means, but I want to demonstrate my approach instead. So we want to find a $C$ such that, for every $\pm 1$ matrix $P$ and for every matrix $A$, we have $\Tr(AP) \leq C \max_{R \in B_1} \Tr(AR)$. Since $B_1$ is convex, this is the same as asking for $C$ such that $P \in C B_1$. In other words, we want to bound $\sigma_1(P)$ for $P$ in $\Mat_n(\pm 1)$. It wouldn't be hard to obtain the bound $n$ from here, but we move on.

Let's leave the warm up and get to the real problem. What we actually want is that $\Tr(AP) \leq C \max_{R \in B_1} \Tr(AR)$ for $A$ having zero diagonal. Thus, we only need $\pi(P)$ to lie in $\pi(C B_1)$, where $\pi$ is orthogonal projection onto matrices of diagonal $0$. In other words, we want $P$ to lie in $CB_1 + \Delta$ where $\Delta$ is the vector space of diagonal matrices. So we come to the following problem:

Problem 1: Find the best constant $C_1$ such that, for every $\pm 1$ matrix $P$, there is a diagonal matrix $D$ with $\sigma_1(P+D) \leq C_1$.

Unfortunately, it seems hard to even guess a rule for choosing the optimal $D$. For example, if $P$ is identically $1$, the best choice of $D$ is $-\frac{n}{2} \mathrm{Id}_n$.

Having no success here, I move on to the case of $A$ skew symmetric. We now can consider only skew symmetric $P$ (which are $0$ on the diagonal and $\pm 1$ off the diagonal.) For such a $P$, we now want to solve the problem:

Problem 2: Find the best constant $C_1$ such that, for every skew-symmetric $\pm 1$ matrix $P$, there is a symmetric matrix $H$ with $\sigma_1(P+H) \leq C_1$.

Fortunately, here I can make a little progress. It turns out that the symmetric matrix is irrelevant!

Lemma: Let $P$ be a skew symmetric matrix and $H$ a symmetric matrix. Then $\sigma_1(P+H) \geq \sigma_1(P)$.

Proof: Since $P$ is skew symmetric, it is diagonalizable over $\mathbb{C}$ with purely imaginary eigenvalues, and the largest such is $i \sigma_1(P)$. Let $v$ be an eigenvector with $P v = i \sigma_1 v$. Writing $\dagger$ for the conjugate transpose, normalize $v^{\dagger} v =1$. Then $\sigma_1(P+H) \geq | v^{\dagger} (P+H) v | = |i \sigma_1 + v^{\dagger} H v|$. But $v^{\dagger} H v$ is real, so $|i \sigma_1 + v^{\dagger} H v| \geq \sigma_1$. $\square$.

Thus, we have reduced to the problem:

Problem 3: Find the largest operator norm of any skew-symmetric $\pm 1$ matrix.

Another poster answered and then deleted his answer to point out that this problem is solved in Lemma 11 of Cycles of a given length in tournaments! (On reflection, I have removed this poster's name since they choose to self-delete, but I hope they will identify themselves and claim the credit; this is useful!) The largest operator norm is always achieved by the matrix which is $1$'s above the diagonal and $-1$'s below it. (As well as by the many other matrices which are conjugate to this one by signed permutation matrices.)

This matrix can be explicitly diagonalized: The eigenvectors are of the form $(1, \zeta, \zeta^2, \ldots, \zeta^{n-1})$ where $\zeta = \exp(\pi i (2j+1)/(2n))$. The corresponding eigenvalues are $i \cot \tfrac{(2j+1) \pi}{2n}$. In particular, the largest singular value is $\cot \tfrac{\pi}{2n}$, thus explaining my guess.

I am guessing this is optimal for Problem 1 as well as Problem 2, but this is based on a very weak intuition that skew symmetric choices are good, plus fedja's answer.

Answer 4

In the following we use the following notation: for $a, b \in \mathbb{R}^k$, $a\cdot b:=a^Tb$ and $|a|^2:=a\cdot a$

Let $n,k\geq 1$.

Define $C(n,k)$ to be the maximum value of $C$ s.t. the following inequality holds for all $a_1, \ldots, a_n\in \mathbb{R}^k$, $b_1, \ldots, b_n\in \mathbb{R}^k$ with $a_i^T b_i = 0$ for $i=1,\dots, n$: $$ \sum_{i=1}^n |a_i|^2 + \sum_{i=1}^n |b_i|^2 \geq \frac{C}{n} \sum_{i,j=1}^n | a_i^T b_j |. $$

Then,

$C(n,1) = 4$ for $n$ even and $4n^2/(n^2-1)\leq C(n,1)\leq 4$ for $n$ odd.

$C(n,2)\geq 2\sqrt{2}=2.83$ and $\lim_{n\rightarrow \infty} C(n,2)\leq \pi$ as also observed by fedja.

Iosif proves in his answer that $C(n,k)\geq 4/\sqrt {3}$ which I also prove by a different argument.

Proof:

$k=1$.

$$\sum_{i,j=1}^{n}|a_ib_j|=\sum_{i=1}^{n}|a_i|\sum_{j=1}^{n}|b_j|$$ $a_ib_i=0$ for all $1\leq i\leq n$ implies that if $A,B$ are the number of non-zero $a_i, b_i$ respectively then $A+B \leq n$. Hence by Cauchy-Schwartz

$$\sum_{i,j=1}^{n}|a_ib_j|\leq\sqrt{AB}\sqrt{\sum_{i=1}^{n}|a_i|^2\sum_{j=1}^{n}|b_j|^2}$$

$$\leq (1/4) (A+B)(\sum_{i=1}^{n}|a_i|^2+\sum_{j=1}^{n}|b_j|^2)\leq \frac{n}{4} (\sum_{i=1}^{n}|a_i|^2+\sum_{j=1}^{n}|b_j|^2).$$

Thus we have $$\sum_{i=1}^{n}|a_i|^2+\sum_{j=1}^{n}|b_j|^2 \geq \frac{4}{n}\sum_{i,j=1}^{n}|a_ib_j|.$$

This proves that $C(n,1)\geq 4$.

For the upper bound for $n$ even we can take the $a_i$'s to have $n/2$ 1's and the rest 0's, swapping 1 and 0 for the $b_i$'s hence satisfying $a_ib_i=0$. A quick calculation shows that $$n (\sum_{i=1}^{n}|a_i|^2+\sum_{j=1}^{n}|b_j|^2 )/\sum_{i,j=1}^{n}|a_ib_j| = 4$$ in this case and hence that $C(n,1)\geq 4$ in this case.

For $n$ odd we take the $a_i$'s to have $(n-1)/2$ 1's and the rest 0's and again a quick calculation gives $4n^2/(n^2-1)$ for the same estimate showing that $C(n,1)\geq 4n^2/(n^2-1)$ in this case.

For $k>1$ we need a few preliminaries:

Lemma

For vectors $a,b,c \in \mathbb{R}^k$ with $a \cdot b=0$, by changing the signs of $a$, $b$ and $c$ we can arrange that $b \cdot c\geq 0$ and $a \cdot c \geq 0$.

Proof Clearly we can arrange that $a \cdot b$, $b \cdot c$ and $a \cdot c$ all have the same sign. if the common sign is positive we are done otherwise just change the sign of $a$ and $b$. $\blacksquare$

Consider the expression $\sum_{i,j=1}^{n}|a_i \cdot b_j|$. Since $b_j\cdot a_j=0$ we can apply the lemma to the vectors $a_i$, $b_j$ and $a_j$ . Hence by changing signs we can guarantee that $b_j\cdot a_i \geq 0$ and $a_j\cdot a_i \geq 0$ which shows that $0\leq |\measuredangle a_i b_j| \leq \pi/2$ and $0\leq |\measuredangle a_i a_j| \leq \pi/2$.

By the triangle inequality for arc lengths we have $\pi \geq |\measuredangle a_i b_j|+|\measuredangle a_i a_j|\geq \pi/2$ and thus $\pi/2 \geq |\measuredangle a_i a_j|\geq \pi/2 -|\measuredangle a_i b_j|\geq 0 $ and since $\sin$ is monotonically increasing in the range $[0, \pi/2]$ we have $1\geq \sin(|\measuredangle a_i a_j|) \geq \sin(\pi/2 -|\measuredangle a_i b_j|)=\cos(|\measuredangle a_i b_j|) \geq 0$.

Thus $|a_i \cdot b_j|=|a_i||b_j||\cos(\measuredangle a_i b_j)|\leq |a_i||b_j||\sin(\measuredangle a_i a_j)|$ and this also holds for the original vectors $a_i$, $b_j$ and $a_j$.

So $\sum_{i,j=1}^{n}|a_i \cdot b_j|\leq \sum_{i,j=1}^{n}|a_i||b_j||\sin(\measuredangle a_i a_j)|\leq \sqrt{\frac{1}{2} \sum_{i,j=1}^{n}\sin^2(\measuredangle a_i a_j)}(\sum_{i=1}^{n}|a_i|^2 + \sum_{i=1}^n |b_i|^2)$ by Cauchy's inequality.

Hence we need to upper bound $\sum_{i,j=1}^{n}\sin^2(\measuredangle a_i a_j)=\sum_{i,j=1}^{n}u_{ij}^2$ with $u_{ij}:=\sin(\measuredangle a_i a_j)$

$k=2$

In this case since the points $a_i$ lie in the plane we can write $a_i=|a_i|(\cos(\theta_i),\sin(\theta_i)):=|a_i| r(\theta_i)$ giving $u_{ij}:=\sin(\theta_i-\theta_j)$.

Note that in this case we actually have an equality $\sum_{i,j=1}^{n}|a_i \cdot b_j|= \sum_{i,j=1}^{n}|a_i||b_j||\sin(\theta_i-\theta_j)|$.

Now consider the expression $R=\sum_{i,j=1}^{n}r(2\theta_i)\cdot r(2\theta_j)$. Clearly $R=|\sum_{i=1}^{n}r(2\theta_i)|^2.$ But also $R=\sum_{i,j=1}^{n}\cos(2(\theta_i-\theta_j))=\sum_{i,j=1}^{n}(1-2\sin^2(\theta_i-\theta_j))$

Therefore $$\sum_{i,j=1}^{n}\sin^2(\theta_i-\theta_j) = \sum_{i,j=1}^{n}1/2-R/2 =n^2/2-R/2.$$ Hence $$\sum_{i,j=1}^{n}\sin^2(\theta_i-\theta_j)\leq n^2/2$$ with equality iff $$\sum_{i=1}^{n}r(2\theta_i)=0$$ or where the centroid of the points $r(2\theta_i)$ is at the origin.

This gives $$\sum_{i,j=1}^{n}|a_i \cdot b_j|\leq \frac{1}{2}\sqrt{\sum_{i,j=1}^{n}\sin^2(\theta_i-\theta_j)}(\sum_{i=1}^{n}|a_i|^2 + \sum_{i=1}^n |b_i|^2)=\frac{n}{2\sqrt{2}}(\sum_{i=1}^{n}|a_i|^2 + \sum_{i=1}^n |b_i|^2)$$ implying that $C(n,2)\geq 2\sqrt{2}$.

For an upper bound we can take $a_i=r(\theta_i)$ to be uniformly distributed on the unit circle then noting as above that we have the equality $\sum_{i,j=1}^{n}|a_i \cdot b_j|= \sum_{i,j=1}^{n}|a_i||b_j||\sin(\theta_i-\theta_j)|=\sum_{i,j=1}^{n}|\sin(2\pi i/n-2\pi j/n)|$ and taking the limit as $n\rightarrow \infty$ this is equal to $$\frac{n^2}{4\pi^2}\int_0^{2\pi}\int_0^{2\pi}|\sin(x-y)|\,dx\,dy = \frac{n^2}{4\pi^2}8 \pi=\frac{2n^2}{\pi}.$$

Hence $\lim_{n\rightarrow \infty} C(n,2)\leq \pi$ as observed by fedja.

k>2

Here we simply observe that for any set of 3 points $\{a_i$, $a_j$, $a_k\}$, $u_{ij}^2+u_{jk}^2+u_{ki}^2$ is maximised when the points lie on a great circle with centroid at the origin. Therefore they form an equilateral triangle centred at the origin.

Hence $u_{ij}^2+u_{jk}^2+u_{ki}^2\leq 3\sin(2\pi/3)^2=3(\sqrt{3}/2)^2=9/4.$

Giving $\sum_{i,j=1}^{n} u_{ij}^2\leq 3n^2/4$ and $C(n,k)\geq 4/\sqrt {3}$ as proved by Iosif.