Encuentra un límite inferior

Question

Deje $M$ $N\times N$ simétrica real de la matriz, y deje $J$ ser una permutación de los enteros de 1 a $N$, con las siguientes propiedades:

1. $J:\{1,...,N\}\rightarrow\{1,...,N\}$ es uno-a-uno.
2. $J$ es su propia inversa: $J(J(i))=i$.
3. $J$ tiene más de un punto fijo, es decir, hay más de un valor de $i$ tal que $J(i)=i$. Explícitamente, si $N$ es impar, no es exactamente un punto fijo, y si $J$ es aún, no hay ninguno.

Una permutación con estas propiedades se establece una vinculación entre los enteros de 1 a $N$ donde $i$ está vinculado con $J(i)$ (excepto si $N$ es impar, en cuyo caso el punto fijo no vinculado). Por lo tanto, vamos a llamar a $J$ un emparejamiento. (*)

Dada una matriz $M$, podemos ir a través de todos los posibles emparejamientos $J$ encontrar el máximo de

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

De esta manera podemos definir una función:

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

La pregunta es: ¿existe un límite inferior a $F(M)$, sobre todos los simétrica real $N\times N$ matrices $M$, con la restricción de $\sum_{ij}M_{ij}^2 > 0$ para evitar singularidades?

Sospecho que $F(M)\geq 0$ (**), pero no tengo una prueba. Tal vez hay una mayor límite inferior.

(*) Yo estoy pidiendo aquí si hay un nombre estándar para este tipo de permutación.

(**) Por $N=2$ esto es falso, ver la respuesta de @O. L. Lo que sucede, por $N>2$?

Answer 1

No es realmente una respuesta, sino una reformulación y una observación.

UPD: La respuesta está en el anexo

Cualquier permutación $S$ puede ser considerado como una $N\times N$ matriz con un $1$ $N-1$ ceros en cada una de las primas y de cada columna. Tenga en cuenta que $S^{-1}=S^T$. El número de puntos fijos coincide con $\mathrm{Tr}\,S$. Usted también están pidiendo $S$ es una involución ($J^{2}=1$), lo que significa que $J=J^T$.

Dado un real simétrica matriz $M$ y un involutiva permutación $J$, la expresión $$ E_J(M)=\frac{\sum_{i,j}M_{ij}M_{J(i)J(j)}}{\sum_{i,j}M_{ij}^2}$$ puede escribirse como $$ E_J(M)=\frac{\mathrm{Tr}\,MJMJ}{\mathrm{Tr}\,M^2}=\frac{\mathrm{Tr}\left(MJ\right)^2}{\mathrm{Tr}\,M^2}.$$

Veamos ahora el caso de $N=2$ donde sólo hay una permutación $J=\left(\begin{array}{cc} 0 & 1 \\ 1 & 0\end{array}\right)$ con las propiedades necesarias. Ahora tomando por ejemplo $M=\left(\begin{array}{cc} 1 & 0 \\ 0 & -1\end{array}\right)$ nos encontramos con $\max_J E_J(M)=-1$. Esto parece contradecir la hipótesis $F(M)\geq 0$. Ejemplos similares pueden ser construidos para cualquier $N$.

---

Importante adición. Creo que el límite inferior de $F(M)$ es, precisamente,$-1$. Vamos a demostrar esto para, incluso,$N=2n$.

Desde $J^2=1$, los autovalores de a $J$ sólo puede ser $\pm1$. Además, puesto que la permutación no tiene puntos fijos, $J$ puede ser traído a la forma $J=O^T\left(\begin{array}{cc} \mathbf{1}_n & 0 \\ 0 & -\mathbf{1}_n\end{array}\right) O$ a través de una verdadera transformación ortogonal. Vamos ahora a calcular la cantidad \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} donde $\left(\begin{array}{cc} A & B \\ B^T & D\end{array}\right)$ denota real simétrica matriz $OMO^T$ escrito en forma de bloque. Real de las matrices $A$, $B$, $D$ puede ser hecho arbitrario por la adecuada selección de $M$ (de curso, en virtud de la evidente limitación $A=A^T$, $D=D^T$).

Ahora vamos a continuar con el cálculo en (1): $$\mathrm{Tr}\,MJMJ=\mathrm{Tr}\left(A^2+D^2-BB^T-B^TB\right).$$ También el uso que $$\mathrm{Tr}\,M^2=\mathrm{Tr}\left(OMO^T\right)^2=\mathrm{Tr}\left(A^2+D^2+BB^T+B^TB\right),$$ nos encontramos con que $$\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.$$ La igualdad es, sin duda, tendrá si $A=D=\mathbf{0}_n$. $\blacksquare$