Let $g_1,\dots,g_n\in\mathbb{R}^n$, and denote by $g_{ij}$ the $j$-th coordinate of $g_i$.
1) Assume that $\|g_i\|=1$ and that $g_{ii}=0$ for all $i$. I need to find:
$\displaystyle{\min_{g_1,\dots,g_n}} \sum_{i=1}^n\sum_{j\neq i} g_{ij}\cdot g_{ji}$,
and for which vectors $g_1,\dots,g_n$ this minimum is achieved?
2) Adding on the above assumptions, we also assume that $\displaystyle{\sum_{i=1}^ng_i =0}$. Now what is the minimum and for which vectors this minimum is achieved?
My try on the problem: for the first question, I think the minimum is $-2\sqrt{n-1}$ which is achieved for example by $g_1 =\begin{pmatrix} 0 \\ 1/\sqrt{n-1}\\ \vdots \\ 1/\sqrt{n-1} \end{pmatrix}, g_2=\dots =g_n = \begin{pmatrix} -1 \\ 0\\ \vdots \\ 0 \end{pmatrix}$. But couldn't find a proof that this is actually the minimum.
For the second problem, my guess is that the minimum should be zero. Another way I tried to look at the problem is by Hadamard product. Denote by $\circ$ the Hadamard product of matrices, let $G$ be a matrix with rows $g_i$, then the sum would be equal to:
$\begin{pmatrix} 1 \dots 1 \end{pmatrix} (G \circ G^\top) \begin{pmatrix} 1 \\ \vdots \\ 1 \end{pmatrix}$
so it may be enough that the extra condition of the second question makes $G\circ G^\top$ positive semi definite. Showing that would prove that the minimum is zero.
Best Answer
Both answers are $-n$.
Proof $\,\,$ Write $G=(g_{ij})_{n\times n}$. Then we have
\begin{align} (G^TG)_{ii} &= \sum_{j=1}^n g^2_{ji}\\ (G^2)_{ii} &= \sum_{j=1}^n g_{ij} g_{ji}\\ (GG^T)_{ii} &= \sum_{j=1}^n g^2_{ij} \end{align}
Via the definition of trace, we have
\begin{align} \text{tr} (G^TG)+ \text{tr} (G^2) &= \frac{1}{2} \text{tr}(G^TG) + \text{tr}(G^2) + \frac{1}{2}\text{tr}(GG^T) \\&= \sum_{i=1}^n \sum_{j=1}^n \left(\frac{1}{2}g^2_{ji} + g_{ij} g_{ji} +\frac{1}{2}g^2_{ij}\right) \\ &= \frac{1}{2} \sum_{j=1}^n \sum_{i=1}^n (g_{ij} + g_{ji} )^2 \\ &\ge 0 \end{align} And the equality holds iff $g_{ij}=-g_{ji}$ , i.e. $G^T=-G$.
Q.E.D.
Then we come back to the original problem. Put $G=(g_{ij})_{n\times n}$.
Note that $g_{ii}=0$ and $\|g_i\|=1$, then from the definition of trace we know $$\sum_{i=1}^n\sum_{j\neq i} g_{ij}\cdot g_{ji}= \text{tr}(G^2)$$ $$\text{tr}(G^TG)=\sum_{i=1}^n \|g_i\| =n$$
Thus via the lemma we have $$\sum_{i=1}^n\sum_{j\neq i} g_{ij}\cdot g_{ji} = \text{tr}(G^2)\ge -n$$
For $n$ being odd, define $g_{ij}$ by
$$ g_{ij} = \begin{cases} (-1)^{i+j}\frac{1}{\sqrt{n-1}} & \mbox{if } i<j \\ -g_{ji} & \mbox{if } i>j\\ 0 & \mbox{if } i=j \end{cases} $$
For example when $n=3$ we define $G$ by $\begin{pmatrix} 0 & -\frac{1}{\sqrt 2} & +\frac{1}{\sqrt 2} \\ +\frac{1}{\sqrt 2} & 0 & -\frac{1}{\sqrt 2} \\ -\frac{1}{\sqrt 2} & +\frac{1}{\sqrt 2} & 0 \end{pmatrix}$.
For $n \equiv 0 \mod 4$, we define $G$ by
$$ g_{ij} = \begin{cases} (-1)^{i+j} \sqrt\frac{2}{n} & \mbox{if } i\le \frac{n}{2} \mbox{ and } j > \frac{n}{2} \\ -g_{ji} & \mbox{if } i > \frac{n}{2} \mbox{ and } j \le \frac{n}{2}\\ 0 & \mbox{other cases} \end{cases} $$
For $n \equiv 2 \mod 4$, we define $G$ by
$$ g_{ij} = \begin{cases} (-1)^{i+j} \sqrt\frac{2}{{n-2}} & \mbox{if } i\le \frac{n}{2} \mbox{ , } j > \frac{n}{2} \mbox{ and } i > j-\frac{n}{2} \\ -g_{{j-\frac{n}{2}},{i+\frac{n}{2}}} & \mbox{if } i\le \frac{n}{2} \mbox{ , } j > \frac{n}{2} \mbox{ and } i< j-\frac{n}{2} \\ -g_{ji} & \mbox{if } i > \frac{n}{2} \mbox{ and } j \le \frac{n}{2}\\ 0 & \mbox{other cases} \end{cases} $$
For example when $n=4$ we define $G$ by $\begin{pmatrix} 0 & 0 & +\frac{1}{\sqrt 2} & -\frac{1}{\sqrt 2} \\ 0 & 0 & -\frac{1}{\sqrt 2} & +\frac{1}{\sqrt 2} \\ -\frac{1}{\sqrt 2} & +\frac{1}{\sqrt 2} & 0 & 0 \\ +\frac{1}{\sqrt 2} & -\frac{1}{\sqrt 2} & 0 & 0 \\ \end{pmatrix}$,
and when $n=6$ we define $G$ by $\begin{pmatrix} 0 & 0 & 0 & 0 & +\frac{1}{\sqrt 2} & -\frac{1}{\sqrt 2} \\ 0 & 0 & 0 & -\frac{1}{\sqrt 2} & 0 & +\frac{1}{\sqrt 2} \\ 0 & 0 & 0 & +\frac{1}{\sqrt 2} & -\frac{1}{\sqrt 2} & 0 \\ 0 & +\frac{1}{\sqrt 2} & -\frac{1}{\sqrt 2} & 0 & 0 & 0 \\ -\frac{1}{\sqrt 2} & 0 & +\frac{1}{\sqrt 2} & 0 & 0 & 0 \\ +\frac{1}{\sqrt 2} & -\frac{1}{\sqrt 2} & 0 & 0 & 0 & 0 \\ \end{pmatrix}$.
Note that the construction satisfies both 1 and 2. Thus for $n\ge 3$, the minimums are always $-n$.