Upper bound for sum of squares given mean of elements

Question

I need upper and lower bounds as tight as possible for the following expression of the elements of a $n$ x $n$ matrix: $$ \sum_{i,j}\rho_{ij}^2-\frac{2}{n}\sum_i(\sum_j\rho_{ij})^2+\frac{(\sum\rho_{ij})^2}{n^2} $$

Assuming that $\rho_{i,i}=1$, that $0\leq \rho_{ij}=\rho_{ji}\leq 1$ and that i know the average of matrix entries $\mu=\frac{\sum_{i,j}\rho_{ij}}{n^2}$.

I don't know the individual elements $\rho_{ij}$.

Basically I'm tring to derive bounds (as a function of the average of the $\rho_{ij})$ for the trace of the matrix $(P(I_n-\textbf{1}/n))^2$ where $\textbf{1}$ is a nxn matrix of all ones, and $I_n$ is the identity matrix, and P is a positive semidefinite matrix.

What I'm expecting is that as the average tends to $1/n$, the upper bound should tend to coincide with the lower bound, but I cannot express that bound as a function of $\mu$ in a way that can prove this.

Answer 1

Let $m(\mu),M(\mu)$ be the $\min$ and the $\max$ as function of $\mu$. Note that $\mu\in[1/n,1]$ and $m(1/n)=M(1/n)=n-1$ and $m(1)=M(1)=0$. Yet, the curves associated to $m,M$ are very different; indeed, the curve for $m$ is decreasing and the curve for $M$ is as a parabola $y=-x^2$ with the top for $\mu \approx 0.6$.

EDIT. About the curve $m(\mu)$. The minimum is reached when the $(\rho_{ij})_{i<j}$ are equal to $\dfrac{\mu n-1}{n-1}$ and its value is $\dfrac{n^2(\mu-1)^2}{n-1}$.

The curve $M(\mu)$ is much more complicated. In particular, it is not derivable -there are many angular points (the left derivative is not equal to the right one). That follows is a conjecture based on experiments with Maple.

In the sequel, the $\rho_{ij}(\mu)$ realize $M(\mu)$ and $\mu$ increases from $1/n$ to $1$. Thus we begin with $\rho_{ij}=0$ and the sequence $\rho_{ij}(\mu)$ is non-decreasing (each component $(ij)$ is non-decreasing) as follows: only one $\rho_{ij}$ increases; when this $\rho_{ij}$ reaches $1$, it remains in $1$; after, another unique $\rho_{ij}$ increases until $1$, and so on. We stop when all the $\rho_{ij}$ are $1$. Thus it remains to see what is the ordering of the $\rho_{ij}$ (about the departure), that is not obvious...Indeed, the big problem is that the $\rho_{ij}$ do not play the same role!! -in other words, the studied expression is not symmetric in the $\rho_{ij}$.

For $n=4$, Maple uses this ordering: $\begin{pmatrix}*&1&3&5\\*&*&6&4\\*&*&*&2\\*&*&*&*\end{pmatrix}$ and for $n=5$, this one: $\begin{pmatrix}*&1&3&5&8\\*&*&4&9&6\\*&*&*&7&10\\*&*&*&*&2\\*&*&*&*&*\end{pmatrix}$.