¿Por qué los cuadrados mágicos siameses tienen valores propios reales, simétricos alrededor de cero?

Existe un método estándar para construir cuadrados mágicos de tamaño impar, conocido como construcción siamesa . Escribiré S metro Para el metro × metro Plaza siamesa. Por ejemplo, aquí está 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 puede ver, ¡esta matriz ciertamente no es simétrica! Tiene un vector propio obvio, el vector de todos unos, cuyo valor propio correspondiente es metro 3 + metro 2 , y no hay una razón obvia por la que sus otros valores propios deban tener una buena estructura. No obstante, la experimentación sugiere:

(1) Todos los valores propios de S metro Son reales.

(2) Si λ es un valor propio de S metro otro que metro 3 + metro 2 , entonces λ es también

¿Alguien puede explicar por qué?

Comentario En caso de que alguien tenga curiosidad sobre cómo encontré esto, estoy aprendiendo MATLAB y se me ocurrió la tarea de enumerar los polinomios característicos de los cuadrados mágicos como una tarea más o menos aleatoria que implicaría aprender algunas estructuras de control básicas y algunas herramientas matemáticas. Esta pieza de documentación de MATLAB describe algunas formas alternativas de pensar sobre la construcción siamesa, que pueden ser relevantes.

¿Puede dar los otros vectores propios y valores propios para metro = 3 y metro = 5 ? Sería interesante ver si tienen alguna estructura.
El metro = 3 los valores propios son 15 , ± 2 6 Alpha da los vectores propios
Parece que invertir el orden de los componentes invierte el signo del valor propio. Me parece que esto está relacionado con el hecho de que si restas ( metro 2 + 1 ) / 2 (=la entrada del medio) de todas las entradas de la matriz, obtienes una matriz que se niega, si la rotas 180 grados.
¿Se sabe cuándo una matriz no simétrica doblemente estocástica tiene todos sus valores propios reales?
Según este artículo: sciencedirect.com/science/article/pii/S0024379508005338 la ecuación (23) implica que el polinomio característico para metro = 5 , después de factorizar el valor propio mágico, tiene la forma X 4 + β X 2 + γ = 0 . Desafortunadamente, no está claro si β , γ puede ser cualquier cosa.
Un comentario experimental, en el pdf de documentación de Matlab, matrices A , B , METRO , tan lejos cuando norte es primo, el factor no trivial del polinomio característico para los tres es irreducible, y para compuesto norte , la partición es la misma para los tres, excepto que una mayor reducción los hace parecer un poco diferentes.

Respuestas (4)

Respuesta parcial (que explica pero no prueba por qué los valores propios no triviales vienen en pares con signos opuestos).

No debería ser demasiado difícil demostrar que la construcción produce una matriz con la propiedad de que al girarla 180 grados da "un cuadrado mágico complementario de entrada", es decir, la suma de A = S metro y su copia rotada A ~ es la matriz con todas las entradas iguales a metro 2 + 1 .

En otras palabras

A i , j = metro 2 + 1 A metro + 1 i , metro + 1 j
para todos i , j . Dejar B = ( A A ~ ) / 2 . De ello se deduce que las sumas de filas y columnas de B son todos cero, y que
B i , j = B metro + 1 i , metro + 1 j ( )
para todos i , j . Cuando metro = 5 tenemos
B = ( 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 ) .

Si tu = ( X 1 , , X metro ) es un vector propio de B perteneciente al valor propio λ , entonces es fácil demostrar que tu ~ = ( X metro , X metro 1 , , X 1 ) es un vector propio de B perteneciente al valor propio λ . A saber, la suposición es que para todos i tenemos

j B i , j X j = λ X i .
Tomando ( ) en cuenta esto implica que
j B i , j X metro + 1 j = j B metro + 1 i , metro + 1 j X metro + 1 j = λ X metro + 1 i
según sea necesario.

Claramente B conmuta con la matriz de todos unos 1 (los productos son cero en cualquier dirección, porque las sumas de filas y columnas de B desaparecer). Así que si B es diagonalizable, entonces es simultáneamente diagonalizable con 1 . Podemos aprovechar los valores propios conocidos de 1 : el vector de todos unos abarca el espacio propio unidimensional con λ = metro , y su complemento ortogonal V (el subespacio de suma cero de R metro ) es el ( metro 1 ) -espacio propio dimensional perteneciente a λ = 0 .

El vector de todos unos pertenece al valor propio 0 de B , por lo que todos los vectores propios de B pertenecientes a valores propios distintos de cero están en V . Esto es importante porque

A = metro 2 + 1 2 1 + B .
Si tu pertenece al valor propio λ 0 de B , entonces 1 tu = 0 y por lo tanto A tu = λ tu . Entonces los valores propios distintos de cero de B son también valores propios de A y sigue la demanda.

Desaparecido:

  1. ¿Por qué los valores propios de B todo real y distinto (de modo que 0 tiene multiplicidad uno, y que B es diagonalizable)?
  2. Demuestre que la construcción siamesa implica ( ) .
Ecuación ( ) por sí sola no garantiza que los valores propios de B seria real Encontrar contraejemplos no es difícil.
Propiedad ( ) sostiene Claramente se cumple para la columna del medio (que es una progresión aritmética), y luego podemos alejarnos de esa columna simétricamente a lo largo de cualquier par apropiado de diagonales ascendentes. Las entradas disminuyen en uno hacia la izquierda y aumentan en uno hacia la derecha, por lo que ( ) se mantiene en todas las posiciones.
hay un enlace en la pregunta de David a un breve pdf, con una construcción dada, páginas 7-9. Hice eso, bastante fácil, y vertí las matrices A , B , METRO especificado en gp-pari. Por el momento, todo lo que escribí a continuación son los polinomios característicos, todos factorizados en un solo (conocido) lineal multiplicado por un montón de cosas en las que todos los exponentes son pares, así que, real o no, el ± la simetría está incorporada.
Si j es la matriz con 1s a lo largo de la diagonal SW-NE y ceros en otros lugares (por lo que tu ~ = j tu ), entonces A ~ = j A j . Debería reescribir todo en términos de j , pero aquí son la 1:30 am, así que ya no puedo pensar con claridad. Espero que alguien solucione esto mientras duermo.
Por ejemplo j = j 1 , entonces B = j B j = j B j 1 . Por lo tanto B es similar a su negativo, y la simetría de sus valores propios es automática. También j viaja con B 2 , que puede resultar interesante. Por ejemplo, mis pruebas me dieron la impresión de que para cualquier matriz real C con la propiedad j C j = C todos los valores propios son reales o imaginarios puros.

Aquí hay algunos resultados parciales.

Este artículo establece que todo cuadrado mágico regular A norte norte × norte (es decir, sus entradas satisfacen a i , j + a norte i + 1 , norte j + 1 = norte 2 + 1 ) es representable como un rango- 1 corrección de una matriz sesgada centrosimétrica Z (eso es, Z = j Z j , dónde j es la matriz de intercambio, o la matriz identidad con sus columnas invertidas). En otras palabras, la matriz que obtienes cuando restas norte 2 + 1 2 de todas las entradas de A es sesgada-centrosimétrica. Esto es importante ya que los valores propios de A , además del valor propio mágico norte 3 + norte 2 , son iguales a los valores propios de Z , que ahora tiene 0 como valor propio.

Ahora podemos usar los resultados de este documento , que dice que si λ es un valor propio de Z , entonces λ ¯ también debe ser un valor propio, con la misma multiplicidad algebraica.

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


Un resultado tentador: Pressman, en este artículo , muestra el resultado más fuerte que si λ es un valor propio de Z , entonces λ es también un valor propio. Parece haber un criterio en el documento para decir cuándo una matriz centrosimétrica oblicua tiene todos sus valores propios reales, pero aún no he descubierto cómo aplicarlo a este caso.

(Efectivamente, esto es lo mismo que la respuesta de Jyrki).

Esta solución se deriva de la comprensión de las construcciones del algoritmo del cuadrado mágico, discutiré solo para casos extraños, es un enfoque heurístico, considere:

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 ves las matrices que se están construyendo, A y B que a su vez generan el cuadrado mágico METRO m tienen una estructura muy especial. Por ejemplo cuando norte = 7 , esta es su estructura,

un =

 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

Se puede verificar que A es una matriz indefinida simétrica, una matriz es indefinida simétrica si es simétrica y tiene valores propios positivos y negativos. Las matrices indefinidas simétricas son una clase importante de matrices que surgen en muchas aplicaciones. Obsérvese también que esto se debe al hecho de que A se construye sumando filas y columnas replicadas con números del 1 al n ( I y j ) más algún desplazamiento (ver. soluciones indefinidas simétricas ).

Ahora considere la suma, METRO = norte A + ( B + 1 ) , mientras ( B + 1 ) no es indefinido simétrico, el primer término comienza a dominar a medida que se agrega A 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 METRO norte A y su estructura de valores propios comienza a parecerse a la de A que es una matriz indefinida simétrica con una diagonal no dominante y, por lo tanto, M tendrá valores propios reales tanto positivos como negativos.

También podemos intentar usar otros enfoques, para probar que los valores propios ocurren en un par de valores positivos y negativos, uno puede proceder de la siguiente manera: usando un método de iteración de potencia o algo similar, podemos encontrar el valor propio más grande, digamos λ 1 , utilizando la traza de la matriz, METRO entonces se puede demostrar que Trace( METRO ) = λ 1 , por lo tanto, debido a la simetría, los otros valores propios deben ocurrir en pares de valores positivos y negativos cancelando todos menos uno que es el más grande. Para obtener más información, también puede utilizar la descomposición de LDL , que se utiliza para resolver ecuaciones de sistemas lineales indefinidos. Espero que esto ayude a desarrollar una solución matemática rigurosa.

simplemente haciendo las matrices como en el informe en el segundo enlace de David por un tal Cleve Moler. no me dejaria hacer norte = 105 , pero conseguí norte = 35.

Dan algunas matrices, A , B , 1 , METRO . Aquí el número 1 se refiere a la matriz con todas las entradas 1 , yo llamé así C abajo.

0 a i j norte 1 , a i j i + j + norte 3 2 ( modificación norte ) ,
0 b i j norte 1 , b i j i + 2 j 2 ( modificación norte ) ,
C i j = 1 ,
METRO = norte A + 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]

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

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

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

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

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

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

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

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

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

¿Cuál fue el punto de votar negativamente esto? Hay más a seguir. Es solo el estilo de Will construir gradualmente una respuesta.
@Jyrki, gracias. Joonas había pedido valores propios específicos, esta es una forma breve de presentar esto, enfatizando todos los exponentes pares después del primer factor lineal, en las tres matrices.