# Find a lower bound

Let $M$ be an $N\times N$ symmetric real matrix, and let $J$ be a permutation of the integers from 1 to $N$, with the following properties:

1. $J:\{1,...,N\}\rightarrow\{1,...,N\}$ is one-to-one.
2. $J$ is its own inverse: $J(J(i))=i$.
3. $J$ has at most one fixed point, that is, there's at most one value of $i$ such that $J(i)=i$. Explicitly, if $N$ is odd, there is exactly one fixed point, and if $J$ is even, there are none.

A permutation with these properties establishes a pairing between the integers from 1 to $N$, where $i$ is paired with $J(i)$ (except if $N$ is odd, in which case the fixed point is not paired). Therefore we will call $J$ a pairing. (*)

Given a matrix $M$, we go through all possible pairings $J$ to find the maximum of

$$\frac{\sum_{ij}M_{ij}M_{J(i)J(j)}}{\sum_{ij}M_{ij}^2}.$$

This way we define a function:

$$F(M)=\max_J\frac{\sum_{ij}M_{ij}M_{J(i)J(j)}}{\sum_{ij}M_{ij}^2}.$$

The question is: Is there a lower bound to $F(M)$, over all symmetric real $N\times N$ matrices $M$, with the constraint $\sum_{ij}M_{ij}^2 > 0$ to avoid singularities?

I suspect that $F(M)\geq 0$ (**), but I don't have a proof. Perhaps there is a tighter lower bound.

(*) I am asking here if there is a standard name for this type of permutation.

(**) For $N=2$ this is false, see the answer by @O.L. What happens for $N>2$?

-

Not really an answer, rather a reformulation and an observation.

Any such permutation $S$ can be considered as an $N\times N$ matrix with one $1$ and $N-1$ zeros in each raw and each column. Note that $S^{-1}=S^T$. The number of fixed points coincides with $\mathrm{Tr}\,S$. You are also asking for $S$ to be an involution ($J^{2}=1$), which means that $J=J^T$.

Given a real symmetric matrix $M$ and an involutive permutation $J$, the expression $$E_J(M)=\frac{\sum_{i,j}M_{ij}M_{J(i)J(j)}}{\sum_{i,j}M_{ij}^2}$$ can be rewritten as $$E_J(M)=\frac{\mathrm{Tr}\,MJMJ}{\mathrm{Tr}\,M^2}=\frac{\mathrm{Tr}\left(MJ\right)^2}{\mathrm{Tr}\,M^2}.$$

Let us now consider the case $N=2$ where there is only one permutation $J=\left(\begin{array}{cc} 0 & 1 \\ 1 & 0\end{array}\right)$ with necessary properties. Now taking for example $M=\left(\begin{array}{cc} 1 & 0 \\ 0 & -1\end{array}\right)$ we find $\max_J E_J(M)=-1$. This seems to contradict your hypothesis $F(M)\geq 0$. Similar examples can be constructed for any $N$.

Important addendum. I think the lower bound for $F(M)$ is precisely $-1$. Let us prove this for even $N=2n$.

Since $J^2=1$, the eigenvalues of $J$ can only be $\pm1$. Further, since the corresponding permutation has no fixed points, $J$ can be brought to the form $J=O^T\left(\begin{array}{cc} \mathbf{1}_n & 0 \\ 0 & -\mathbf{1}_n\end{array}\right) O$ by a real orthogonal transformation. Let us now compute the quantity \begin{align} \mathrm{Tr}\,MJMJ=\mathrm{Tr}\left\{MO^T\left(\begin{array}{cc} \mathbf{1}_n & 0 \\ 0 & -\mathbf{1}_n\end{array}\right)OMO^T\left(\begin{array}{cc} \mathbf{1}_n & 0 \\ 0 & -\mathbf{1}_n\end{array}\right)O\right\}=\\= \mathrm{Tr}\left\{\left(\begin{array}{cc} A & B \\ B^T & D\end{array}\right)\left(\begin{array}{cc} \mathbf{1}_n & 0 \\ 0 & -\mathbf{1}_n\end{array}\right)\left(\begin{array}{cc} A & B \\ B^T & D\end{array}\right)\left(\begin{array}{cc} \mathbf{1}_n & 0 \\ 0 & -\mathbf{1}_n\end{array}\right)\right\},\tag{1}\end{align} where $\left(\begin{array}{cc} A & B \\ B^T & D\end{array}\right)$ denotes real symmetric matrix $OMO^T$ written in block form. Real matrices $A$, $B$, $D$ can be made arbitrary by the appropriate choice of $M$ (of course, under obvious constraints $A=A^T$, $D=D^T$).

Now let us continue the computation in (1): $$\mathrm{Tr}\,MJMJ=\mathrm{Tr}\left(A^2+D^2-BB^T-B^TB\right).$$ Also using that $$\mathrm{Tr}\,M^2=\mathrm{Tr}\left(OMO^T\right)^2=\mathrm{Tr}\left(A^2+D^2+BB^T+B^TB\right),$$ we find that $$\frac{\mathrm{Tr}\,MJMJ}{\mathrm{Tr}\,M^2}+1=\frac{2\mathrm{Tr}\left(A^2+D^2\right)}{\mathrm{Tr}\left(A^2+D^2+BB^T+B^TB\right)}\geq 0.$$ The equality is certainly attained if $A=D=\mathbf{0}_n$. $\blacksquare$

-
+1 Good observation. – becko Apr 26 '13 at 0:19
Are you sure this holds for higher $N$? $N=2$ is special in that there's only one permutation $J$ with necessary properties. With $N=3$ there are 3, and with $N=7$ there are 105. How can I check those cases too and see if the lower bound is still negative? – becko Apr 26 '13 at 0:35
Yes, I've just added above the proof for even $N$, which also provides a constructive way to find the minimizing matrix $M$. – Start wearing purple Apr 26 '13 at 0:56
Although now I'm starting to get confused. What is your procedure? To fix $M$, then to maximize something over $J$'s but then to vary $M$ to minimize $F(M)$? I don't understand. What I have written is minimization over $M$'s for fixed $J$. – Start wearing purple Apr 26 '13 at 1:07
Given some fixed $M$, $F(M)$ denotes the maximum over $J$. We want to minimize $F(M)$. Using the notation $E_J(M)$ that you introduced in the first part of your answer, what we want is $\min_M \max_J E_J(M)$ – becko Apr 26 '13 at 1:51