Probando que todas las variables son iguales

Question

Me llegó a través de un rompecabezas últimamente.

Deje $A$ ser una matriz de tamaño $(2n+1)$ por $(2n+1)$. La diagonal de $A$ es todo ceros. Cada entrada de $A$ es $+1$ o $-1$. Cada fila de $A$ suma cero. En otras palabras, cada fila tiene $n$ de $+1$ e $n$ de $-1$.

Ahora tenemos que demostrar que el sistema de ecuaciones $$ Un (x_1, \dots, x_{2n+1})^T = (0, \dots, 0)^T $$ puede siempre reducirse a $x_1=x_2=\dots=x_{2n+1}$.

Esto es bastante fácil ver por $n=1$. Para $n=2$, se puede demostrar esto mediante el análisis de casos. (O simplemente escribir un fragmento de código para comprobar y asegurar todos los posibles $A$). Pero yo no era capaz de generalizar esta arbitraria $n$.

Answer 1

Basado en la forma de $A$, la condición de $A(x_1,\dots,x_{2n+1})^T=0$ se traduce en:

Si usted toma cualquier número de $x_1,\ldots,x_{2n+1}$, luego el resto de la $2n$ números puede ser reducido a la mitad a haber sumas iguales.

Esto es claramente invariante en la multiplicación o adición de una misma constante a todos los $x_i$'s.

(1) Suponga que todos los $x_i$'s son enteros. Si $S$ denota $x_1 + \cdots + x_{2n+1}$, a continuación, $S-x_i$ es, incluso, para cada $i$, ya que es la suma de dos sumas iguales. Por lo tanto, todos los $x_i$'s tienen la misma paridad.

Si todos los $x_i$'s son, incluso, dividir todo por $2$. Este (estrictamente) disminuye los valores absolutos de todos los $x_i$'s. (excepto para los ceros)

Si todos los $x_i$'s son impares, a continuación, realice $x \mapsto (x-1)/2$. Este (estrictamente) disminuye los valores absolutos de $x_i$'s, salvo para los ceros y los negativos. Si sólo ceros o negativos permanecen, sólo voltear el signo y continuar.

Finalmente, uno se pondrá $(0,0,\ldots,0)$, lo que significa que si usted realice los pasos hacia atrás, en un principio debería haber sido $x_1 = \dots = x_{2n+1}$.

(2) Asumir todas las $x_i$'s son racionales. Luego, se multiplica por un número entero para hacer todas las $x_i$'s entero y vaya al paso (1).

(3) Finalmente, desde la $A$ es una matriz racional de las entradas, el espacio de la solución $Ax=0$ tendría una base racional. Por lo tanto, sólo necesitamos considerar las soluciones racionales. Así que todo es hecho en (2).

Answer 2

Es realmente un buen problema que solía ser presentado con pequeñas rocas y masas.

Lo que usted necesita hacer es mostrar que el tamaño del núcleo es 1, de modo que la matriz es de rango n-1. para que usted tome un menor $D$ de ese tamaño y demostrar que es invertible.

Y ahora que uso un truco sencillo: calcular $|D|$ en un campo diferente (aquí tomamos $\frac{\mathbb{Z}}{2\mathbb{Z}}$). Esto funciona debido a que el determinante es invariante a través de un cambio de campo (combinaciones lineales de cada columna)

Al hacerlo, todos los $\pm 1$ se convierte en 1 y calculando el determinante es fácil. mostrando que el determinante es no nulo no hacer el truco. el núcleo es de tamaño 1 y la solución es la que se encuentra.