Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question

1 Answer 1

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

UPD: The answer is in the addendum

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$

share|improve this answer
    
+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$. –  O.L. 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$. –  O.L. 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.