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}| $$
Best Answer
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$.