¿Cuadrados mágicos de siameses tienen valores propios reales, simétrica alrededor de cero?

Question

No hay un método estándar para la construcción de cuadrados mágicos de tamaño impar, conocido como el Los siameses de la construcción. Voy a escribir $S_m$ $m \times m$ Siamés de la plaza. Por ejemplo, aquí es $S_5$.

17    24     1     8    15
23     5     7    14    16
 4     6    13    20    22
10    12    19    21     3
11    18    25     2     9

Como se puede ver, esta matriz no es simétrica! Tiene un vector propio, el de todos aquellos vector, cuyo correspondiente autovalor es $\frac{m^3+m}{2}$, y no hay ninguna razón obvia de sus otros autovalores debe tener agradable de la estructura. Sin embargo, la experimentación sugiere:

(1) Todos los autovalores de a $S_m$ son reales.

(2) Si $\lambda$ es un autovalor de a $S_m$ otros de $\frac{m^3+m}{2}$, $-\lambda$ es así.

¿Alguien puede explicar por qué?

Comentario En caso de que alguien es curioso cómo he encontrado esto, me estoy enseñando a MATLAB y se llegó a la tarea de enumerar los polinomios característicos de los cuadrados mágicos como una forma más o menos aleatoria de tareas que conlleva el aprendizaje de algunos conceptos básicos de estructuras de control y algunas herramientas matemáticas. Esta pieza de MATLAB documentación que describe algunas de las formas alternativas de pensar acerca de los Siameses de la construcción, que pueden ser relevantes.

Answer 1

Respuesta parcial (explicando pero no demostrando por qué de la no-trivial autovalores vienen en pares con signos opuestos).

No debería ser demasiado difícil de probar que la construcción se produce una matriz con la propiedad de que puede girar 180 grados da "un entrywise complementarios cuadrado mágico", es decir, la suma de $A=S_m$ y su copia con rotación $\tilde{A}$ es la matriz con todas las entradas igual a $m^2+1$.

En otras palabras $$ A_{i,j}=m^2+1-A_{m+1-i,m+1-j} $$ para todos los $i,j$. Deje $B=(A-\tilde{A})/2$. De ello se desprende que la fila y la columna de sumas de $B$ son todos cero, y que $$B_{i,j}=-B_{m+1-i,m+1-j}\qquad(*)$$ for all $i,j$. When $m=5$ tenemos $$ B=\left( \begin{array}{ccccc} 4 & 11 & -12 & -5 & 2 \\ 10 & -8 & -6 & 1 & 3 \\ -9 & -7 & 0 & 7 & 9 \\ -3 & -1 & 6 & 8 & -10 \\ -2 & 5 & 12 & -11 & -4 \\ \end{array} \right). $$

Si $u=(x_1,\ldots,x_m)$ es un autovector de a $B$ pertenecientes al autovalor $\lambda$, entonces es fácil mostrar que $\tilde{u}=(x_m,x_{m-1},\ldots,x_1)$ es un autovector de a $B$ pertenecientes al autovalor $-\lambda$. Es decir, la suposición es que para todos los $i$ hemos $$ \sum_j B_{i,j}x_j=\lambda x_i. $$ Tomando $(*)$ en cuenta que esto implica que $$ \sum_j B_{i,j}x_{m+1-j}=-\sum_j B_{m+1-i,m+1-j}x_{m+1-j}=-\lambda x_{m+1-i} $$ como se requiere.

Claramente $B$ viajes con todos los queridos matriz $\mathbf{1}$ (los productos son cero en cualquier dirección, como la fila y columna de sumas de $B$ desaparecen). Así que si $B$ es diagonalizable, entonces simultáneamente es diagonalizable con $\mathbf{1}$. Podemos tomar ventaja de la conocida autovalores de a $\mathbf{1}$: la de todos aquellos vector se extiende por el 1-dimensional espacio propio con $\lambda=m$, y su complemento ortogonal $V$ (el cero subespacio suma de $\Bbb{R}^m$) es el $(m-1)$-dimensional espacio propio pertenecientes a $\lambda=0$.

La de todos aquellos vector pertenece al autovalor $0$$B$, por lo que todos los vectores propios de a $B$ perteneciente a distinto de cero autovalores son en $V$. Esto es importante porque $$ A=\frac{m^2+1}2\mathbf{1}+B. $$ Si $u$ pertenece al autovalor $\lambda\neq0$$B$, $\mathbf{1}u=0$ e lo $Au=\lambda u$. De modo que el cero no autovalores de a $B$ también son los autovalores de a $A$ y la demanda de la siguiente manera.

Falta:

1. ¿Por qué son los autovalores de a $B$ reales y distintas (de modo que $0$ tiene multiplicidad uno, y que $B$ es diagonalizable)?
2. Demostrar que el Siamés construcción implica $(*)$.

Answer 2

Aquí están algunos de los resultados parciales.

Este documento establece que cada cuadrado mágico $\mathbf A\in\mathbb N^{n\times n}$ (es decir, sus entradas satisfacer $a_{i,j}+a_{n-i+1,n-j+1}=n^2+1$) es representable como un rango-$1$ corrección de un sesgo-centrosimétrico matriz $\mathbf Z$ (es decir, $\mathbf Z=-\mathbf J\mathbf Z\mathbf J$ donde $\mathbf J$ es el cambio de la matriz, o la matriz de identidad con sus columnas se invierte). En otras palabras, la matriz que se obtiene al restar $\frac{n^2+1}{2}$ de todas las entradas de $\mathbf A$ es sesgar-centrosimétrico. Esto es importante ya que los autovalores de a $\mathbf A$, aparte de la magia autovalor $\frac{n^3+n}{2}$, son los mismos que los autovalores de a $\mathbf Z$, que ahora ha $0$ como un valor propio.

Ahora podemos usar los resultados de este trabajo, que dice que si $\lambda$ es un autovalor de a$\mathbf Z$, $-\bar{\lambda}$ debe ser también un autovalor, con la misma multiplicidad algebraica.

Por lo tanto, la tarea restante es para demostrar que todos los autovalores de un Siamés cuadrado mágico son necesariamente reales.

---

Una tentadora resultado: Pressman, en este documento, muestra el resultado más fuerte que si $\lambda$ es un autovalor de a$\mathbf Z$, $-\lambda$ también es un autovalor. No parece ser un criterio en el papel para decir cuando un sesgo-centrosimétrico matriz tiene todos sus autovalores reales, pero todavía no he descubierto cómo se aplican a este caso.

Answer 3

Esta solución se deriva de la comprensión de las construcciones de los cuadrados mágicos algoritmo, voy a hablar sólo de extraño caso, se trata de una aproximación heurística, considere la posibilidad de:

n = 7;    % Must be odd
[I,J] = ndgrid(1:n);
A = mod(I+J+(n-3)/2,n);
B = mod(I+2*J-2,n);
M = n*A + B + 1
magic(n) 

Si usted ve las matrices que se están construyendo, $A$ $B$ que inturn generar el cuadrado mágico $M$m tienen una estructura especial. Por ejemplo, cuando $n= 7$, esto es, su estructura,

A =

 4     5     6     0     1     2     3
 5     6     0     1     2     3     4
 6     0     1     2     3     4     5
 0     1     2     3     4     5     6
 1     2     3     4     5     6     0
 2     3     4     5     6     0     1
 3     4     5     6     0     1     2

B =

 1     3     5     0     2     4     6
 2     4     6     1     3     5     0
 3     5     0     2     4     6     1
 4     6     1     3     5     0     2
 5     0     2     4     6     1     3
 6     1     3     5     0     2     4
 0     2     4     6     1     3     5

Uno puede comprobar que a es simétrica indefinida de la matriz, una matriz es simétrica indefinida si es simétrica y tiene su parte positiva y negativa de los autovalores. Simétrica indefinido matrices son una clase importante de las matrices derivadas en muchas aplicaciones. Observar también que esto es debido al hecho de que está siendo construido por la adición de replicar las filas y columnas con los números de 1 a n ( $I$ $J$ ) además de algunos de desplazamiento (ver. symmertic indefinido de soluciones).

Ahora considere la suma, $M = nA + (B + 1)$, mientras que $(B+1)$ no es simétrica indefinido, el primer término comienza a dominar como se añaden sucesivamente por ejemplo,

eig(3*A + B + 1) =  
  91.0000 + 0.0000i
  24.2980 + 0.0000i
  12.1490 + 1.3399i
  12.1490 - 1.3399i
 -24.2980 + 0.0000i
 -12.1490 + 1.3399i
 -12.1490 - 1.3399i

eig(4*A + B + 1) = 
   112.0000
   32.3220
   16.8439
   15.4781
  -32.3220
  -16.8439
  -15.4781

eig(M) =
  175.0000
  -56.4848
  -31.0882
  -25.3967
   56.4848
   25.3967
   31.0882

haciendo $M \approx nA$ y su valor propio de la estructura comienza a parecerse a la de $A$ que es un simétrica indefinida de la matriz con la no dominante de la diagonal y por lo tanto M positivos y negativos real de los autovalores.

También podemos intentar usar otros enfoques, para demostrar que los valores propios se producen en el par de valores positivos y negativos, se puede proceder como sigue: el uso de una potencia de iteración del método o algo similar podemos encontrar el mayor autovalor decir $\lambda_1$, el uso de la traza de la matriz, $M$ entonces puede demostrarse que Traza($M$) = $\lambda_1$, por lo tanto, debido a la simetría, el otro autovalores debe ocurrir en pares de valores positivos y negativos cancelación de todos, pero uno que es el más grande. Para obtener más información también se puede utilizar LDL descomposición que se utilizan para resolver ecuaciones de indefinido sistemas lineales. Espero que esto le ayudará a desarrollar una matemática rigurosa de la solución.

Answer 4

sólo haciendo las matrices como en la valoración crítica de David del segundo enlace por uno Cleve Moler. No me deja hacer $n=105,$ pero me hizo llegar $n=35.$

Dan algunas matrices, $A, B, 1, M.$ Aquí el numeral $1$ corresponde a la matriz con todas las entradas $1,$ llamé a ese $C$ por debajo. $$ 0 \leq a_{ij} \leq n-1, \; \; \; a_{ij} \equiv i + j + \frac{n-3}{2} \pmod n, $$ $$ 0 \leq b_{ij} \leq n-1, \; \; \; b_{ij} \equiv i + 2j -2 \pmod n, $$ $$ c_{ij} = 1, $$ $$ M = nA + B + C. $$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

3:

parisize = 4000000, primelimit = 500509
?  a = [   2,    0,    1;    0,    1,    2;    1,    2,    0]
%1 = 
[2 0 1]

[0 1 2]

[1 2 0]

? b = [    1,    0,    2;    2,    1,    0;    0,    2,    1]
%2 = 
[1 0 2]

[2 1 0]

[0 2 1]

? c = [    1,    1,    1;    1,    1,    1;    1,    1,    1]
%3 = 
[1 1 1]

[1 1 1]

[1 1 1]

? m = 3 * a + b + c
%4 = 
[8 1 6]

[3 5 7]

[4 9 2]

? factor(charpoly(a))
%5 = 
[x - 3 1]

[x^2 - 3 1]

? factor(charpoly(b))
%6 = 
[x - 3 1]

[x^2 + 3 1]

? factor(charpoly(m))
%7 = 
[x - 15 1]

[x^2 - 24 1]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    5:
    a:
[3 4 0 1 2]

[4 0 1 2 3]

[0 1 2 3 4]

[1 2 3 4 0]

[2 3 4 0 1]


b: 
[1 3 0 2 4]

[2 4 1 3 0]

[3 0 2 4 1]

[4 1 3 0 2]

[0 2 4 1 3]

     m = 5 * a + b + c
    %4 = 
    [17 24 1 8 15]

    [23 5 7 14 16]

    [4 6 13 20 22]

    [10 12 19 21 3]

    [11 18 25 2 9]

    ? factor(charpoly(a))
    %5 = 
    [x - 10 1]

    [x^4 - 25*x^2 + 125 1]

    ? factor(charpoly(b))
    %6 = 
    [x - 10 1]

    [x^4 - 125 1]

    ? factor(charpoly(m))
    %7 = 
    [x - 65 1]

    [x^4 - 625*x^2 + 78000 1]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

7:
? factor(charpoly(a))
%5 = 
[x - 21 1]

[x^6 - 98*x^4 + 2401*x^2 - 16807 1]

? factor(charpoly(b))
%6 = 
[x - 21 1]

[x^6 - 16807 1]

? factor(charpoly(m))
%7 = 
[x - 175 1]

[x^6 - 4802*x^4 + 5764801*x^2 - 1988873152 1]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

9:

? factor(charpoly(a) ) 
%7 = 
[x - 36 1]

[x^2 - 27 1]

[x^6 - 243*x^4 + 13122*x^2 - 177147 1]

? factor(charpoly(b) ) 
%8 = 
[x - 36 1]

[x^2 + 27 1]

[x^6 + 177147 1]

? factor(charpoly(m) ) 
%9 = 
[x - 369 1]

[x^2 - 2160 1]

[x^6 - 19683*x^4 + 86093442*x^2 - 94143001680 1]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

11:

? factor(charpoly(a))
%5 = 
[x - 55 1]

[x^10 - 605*x^8 + 102487*x^6 - 7086244*x^4 + 214358881*x^2 - 2357947691 1]

? factor(charpoly(b))
%6 = 
[x - 55 1]

[x^10 + 2357947691 1]

? factor(charpoly(m))
%7 = 
[x - 671 1]

[x^10 - 73205*x^8 + 1500512167*x^6 - 12553713506884*x^4 + 45949729863572161*x^2 - 61159090446056598600 1]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

13:

? 
? factor(charpoly(a))
%5 = 
[x - 78 1]

[x^12 - 1183*x^10 + 399854*x^8 - 57921708*x^6 + 4078653605*x^4 - 137858491849*x^2 + 1792160394037 1]

? factor(charpoly(b))
%6 = 
[x - 78 1]

[x^12 - 1792160394037 1]

? factor(charpoly(m))
%7 = 
[x - 1105 1]

[x^12 - 199927*x^10 + 11420230094*x^8 - 279577021469772*x^6 + 3327083045915899205*x^4 - 19004963774880799438801*x^2 + 41753905413411324206651760 1]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

15:

? factor(charpoly(a))
%5 = 
[x - 105 1]

[x^2 - 75 1]

[x^4 - 225*x^2 + 10125 1]

[x^8 - 1800*x^6 + 708750*x^4 - 79734375*x^2 + 2562890625 1]

? factor(charpoly(b))
%6 = 
[x - 105 1]

[x^2 + 75 1]

[x^4 - 10125 1]

[x^4 + 50625 2]

? factor(charpoly(m))
%7 = 
[x - 1695 1]

[x^2 - 16800 1]

[x^4 - 50625*x^2 + 512568000 1]

[x^8 - 405000*x^6 + 35880570000*x^4 - 908244868359375*x^2 + 6568148865600000000 1]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

21:
? factor( charpoly(a))
%9 = 
[x - 210 1]

[x^2 - 147 1]

[x^6 - 882*x^4 + 194481*x^2 - 12252303 1]

[x^12 - 7056*x^10 + 11668860*x^8 - 6689757438*x^6 + 1664205811884*x^4 - 183478690760211*x^2 + 7355827511386641 1]

? factor( charpoly(b))
%10 = 
[x - 210 1]

[x - 21 2]

[x + 21 2]

[x^2 - 21*x + 441 2]

[x^2 + 147 1]

[x^2 + 21*x + 441 2]

[x^6 - 12252303 1]

? factor( charpoly(m))
%11 = 
[x - 4641 1]

[x^2 - 64680 1]

[x^6 - 388962*x^4 + 37822859361*x^2 - 1051059451035132 1]

[x^12 - 3111696*x^10 + 2269371561660*x^8 - 573754546059690240*x^6 + 62945022637525450097340*x^4 - 3060402710940787304923125687*x^2 + 54108197115511006692907045070400 1]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

25:


? factor(charpoly(a))
%7 = 
[x - 300 1]

[x^4 - 625*x^2 + 78125 1]

[x^20 - 15625*x^18 + 68359375*x^16 - 130615234375*x^14 + 131225585937500*x^12 - 76389312744140625*x^10 + 27120113372802734375*x^8 - 5960464477539062500000*x^6 + 791624188423156738281250*x^4 - 58207660913467407226562500*x^2 + 1818989403545856475830078125 1]

? factor(charpoly(b))
%8 = 
[x - 300 1]

[x^4 - 78125 1]

[x^20 - 1818989403545856475830078125 1]

? factor(charpoly(m))
%9 = 
[x - 7825 1]

[x^4 - 390625*x^2 + 30517500000 1]

[x^20 - 9765625*x^18 + 26702880859375*x^16 - 31888484954833984375*x^14 + 20023435354232788085937500*x^12 - 7285052561201155185699462890625*x^10 + 1616484723854227922856807708740234375*x^8 - 222044604925031308084726333618164062500000*x^6 + 18431436932253575378126697614789009094238281250*x^4 - 847032947254300339068322500679641962051391601562500*x^2 + 16543612251060553497428173839580267667770385742187500000 1]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

35:

? factor( charpoly(a))
%5 = 
[x - 595 1]

[x^4 - 1225*x^2 + 300125 1]

[x^6 - 2450*x^4 + 1500625*x^2 - 262609375 1]

[x^24 - 58800*x^22 + 942392500*x^20 - 6430253156250*x^18 + 22590813918750000*x^16 - 45546375353896484375*x^14 + 56625598053505126953125*x^12 - 45323879544822393798828125*x^10 + 23792863499842512817382812500*x^8 - 8143807322924036556243896484375*x^6 + 1750204205365253470420837402343750*x^4 - 214400015157243550126552581787109375*x^2 + 11419131242070580387175083160400390625 1]

? factor( charpoly(b))
%6 = 
[x - 595 1]

[x^4 - 300125 1]

[x^4 + 1500625 2]

[x^6 - 262609375 1]

[x^8 - 1500625*x^4 + 2251875390625 2]

? factor( charpoly(m))
%7 = 
[x - 21455 1]

[x^4 - 1500625*x^2 + 450374778000 1]

[x^6 - 3001250*x^4 + 2251875390625*x^2 - 482768305881750000 1]

[x^24 - 72030000*x^22 + 1414177745312500*x^20 - 11820513337182128906250*x^18 + 50871697917821843261718750000*x^16 - 125641833194720435000514984130859375*x^14 + 191350382223376715547899626959845458984375*x^12 - 187620244496627071229425371028983150177001953125*x^10 + 120652249258767712686244839929865230231475830078125000*x^8 - 50588556607865112913542176134821560108671009540557861328125*x^6 + 13318325045557471063558895256155938430252362415194511413574218750*x^4 - 1998581152148968001166733191860870554971460885345004498958587646484375*x^2 + 130396558323632395895356353118015771568144032806708128677368164062500000000 1]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=