Ideas de encontrar contraejemplos?

Question

Las preguntas son de un ejercicio en Gibert Strang del Álgebra Lineal.

Construcción $2$ $2$ matrices tales que los autovalores de a $AB$ no son los productos de los autovalores de a$A$$B$, y los valores propios de a $A+B$ no son la suma de los individuales de los autovalores.

Es obvio que cualquiera de las $A$ o $B$ NO diagonal de la matriz.

Aquí está mi pregunta:

Cómo debo enfoque de la construcción? Cualquier heurística?

---

Añadió:

Este parece ser un lugar "estúpido", pregunta. Ensayo y error con MATLAB puede conducir a los resultados. Sin embargo, me gustaría ir un poco más allá. "Ensayo y error" puede ser visto como una especie de método para contraejemplo encontrar. Mi segunda pregunta es más "estúpido" y muy vaga:

Puede venir para arriba con una "idea general" para la construcción de contraejemplos en matemáticas?

Answer 1

Encontrar contraejemplos es algo de un oscuro arte; he visto, literalmente, no hay matemática de la escritura de cualquier tipo que explícitamente se describe cómo se puede ir sobre hacer esto, aunque es muy importante la habilidad matemática. Aquí están algunas ideas fuera de la parte superior de mi cabeza.

No subestime la prueba y el error. En general es fácil de hacer, y es a menudo muy esclarecedor. No tienes excusa para no hacerlo, especialmente si usted tiene un CAS. (Conceptual explicaciones están sobrevalorados en situaciones como esta. A veces, un enunciado es falso sólo porque no tiene ninguna razón para ser verdad, y si tu intuición te dice lo contrario, la actualización de su intuición.)

A veces a ciegas la construcción de un contraejemplo de las obras. En ciertas situaciones, usted puede mirar la lista de propiedades de un contraejemplo para satisfacer las necesidades y escribe un ejemplo que satisface la primera propiedad, modificarlo para satisfacer la segunda, etc. y básicamente no habrá ningún obstáculo para hacer esto. Esto también es generalmente fácil de hacer, cuando funciona.

Familiarizarse con pequeños ejemplos, y saber la manera de construir grandes. (Esto es extraordinariamente importante, y a mí me parece que son relativamente pocos los estudiantes nunca se molestan en hacerlo.) A veces la prueba y el error es difícil, porque no está claro cómo construir un ejemplo al azar para comprobar. Para matrices es bastante sencillo, pero para otros tipos de objetos (tales como grupos) puede ser menos.

Así que si usted quiere encontrar un contraejemplo en teoría de grupos, por ejemplo, usted debe familiarizarse con la clasificación de los grupos de la pequeña orden, y usted también debe saber modos de construir la más grande, complicada grupos (como $S_n, \text{GL}_n(\mathbb{F}_p)$, semidirect productos, etc.).

Asegúrese de que sus ejemplos de alguna forma de escape de la complejidad de los objetos en cuestión: en cuanto a la abelian grupos para construir un contraejemplo a una declaración acerca de los grupos de trabajo, pero si no, debería empezar a mirar más allá.

Tratar de demostrar que no existen contraejemplos. Esto a menudo puede ser útil. Si hay algunas hipótesis que parecen necesitar para hacer una simple prueba de trabajo, mira los ejemplos que violan esa suposición. Si no sabes ni por donde empezar, vaya de nuevo a prueba y error hasta que usted tiene una mejor sensación de cómo los objetos en cuestión se comportan.

(Avanzado:) familiarizarse con el estándar de contraejemplos. Algunos campos de las matemáticas, tales como la topología general, han conocido contraejemplos que sería difícil llegar a su propia, por lo que la mayoría del tiempo estás mejor aprendizaje de lo que están tratando de llegar con su propio. Estándar de contraejemplos, o de las ideas detrás de ellos, a menudo puede ser modificado o combinados para dar contraejemplos a otras declaraciones.

Answer 2

Menos filosóficamente, creo que Strang del ejercicio no es un "bien planteado", una en la que parece suponer que debe haber algún tipo de "canónica" de la orden en el conjunto de valores propios de una matriz, ¿no?

Me explico, digamos que $\lambda_X, \mu_X$ son los autovalores de a $X$ $X$ $2\times 2$ matriz. Entonces, ¿cuál es el significado de la pregunta por el producto? Por ejemplo:

$$ \lambda_{AB} \neq \lambda_A \lambda_B \ ,\qquad \text{o} \qquad \lambda_{AB} \neq \lambda_A \mu_B \ , \qquad\text{o ambos?} $$

De todos modos, suponiendo que la pregunta tiene algo de sentido, a continuación, el siguiente paso podría ser la siguiente: $A$ $B$ no puede ser diagonal de las matrices, como usted dice, a la derecha. Pero puede ser diagonalizable, mientras ellos están tan en diferentes bases. De lo contrario, los autovalores de a $AB$ $A + B$ sería sin duda todavía ser "los productos" y "las" sumas de los de $A$$B$.

Así, se podría empezar con una sencilla matriz tales como

$$ A = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} $$

con evidente autovalores $1,-1$, y hacer un cambio de base con ella. Por ejemplo, con la base $\left\{ (1,1), (1,-1) \right\}$. Usted obtener

$$ B= \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} $$

con los mismos autovalores como $A$. Ahora, si calcular

$$ AB = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} \qquad \text{y} \qquad A + B = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \ . $$

Los autovalores de a$AB$$i,-i$, y los de $A+B$$\sqrt{2}, -\sqrt{2}$, que ciertamente no son, respectivamente, "los productos", o "el" es la suma de los de $A$$B$.

Answer 3

Mi favorito enfoque en la búsqueda de contraejemplos cuando no estoy lo suficientemente familiarizado con el objeto matemático $M$ es un enfoque de arriba hacia abajo.

Empezar con el caso más general, ejemplo de $M$, y la de encontrar la condición de que todos los contraejemplos de M tiene que violar, a continuación, elegir uno concreto contraejemplo de este conjunto de contraejemplos:

Para este ejemplo, aquí, $M$ "de las matrices $A$, $B$ que satisfacen la propiedad indicada en el OP"

Por ejemplo, considere las matrices:

$$A=\begin{pmatrix}a&b\\c&d\end{pmatrix}, B=\begin{pmatrix}e&f\\g&h\end{pmatrix}$$

Entonces $$A+B=\begin{pmatrix}a+e&b+f\\c+g&d+h\end{pmatrix}, AB=\begin{pmatrix}ae+bg&af+bh\\ce+dg&cf+dh\end{pmatrix}$$

Ahora la característica ecuaciones son (ya sean directos de computación o el uso de la propiedad para n=2 matrices, el $cp_A(x)=x^2-\text{tr}(A)+\det(A)$)

$$cp_A(x)=x^2-x(a+d)+(ad-bc)=0\\ cp_B(x)=x^2-x(e+h)+(eh-fg)=0\\ cp_{A+B}(x)=x^2-x(a+e+d+h)+((a+e)(d+h)-(b+f)(c+g))=0\\ cp_{AB}(x)=x^2-x(ae+bg+cf+dg)+((ae+bg)(cf+dh)-(af+bh)(ce+dg))=0$$

Por lo tanto, la fórmula cuadrática dijo que los autovalores son

$$ x_A=\frac{(a+d)\pm\sqrt{(a+d)^2-4(ad-bc)}}{2}\\ x_B=\frac{(e+h)\pm\sqrt{(e+h)^2-4(eh-fg)}}{2}\\ x_{A+B}=\frac{(a+e+d+h)\pm\sqrt{(a+e+d+h)^2-4((a+e)(d+h)-(b+f)(c+g))}}{2}\\ x_{AB}=\frac{(ae+bg+cf+dg)\pm\sqrt{(ae+bg+cf+dg)^2-4((ae+bg)(cf+dh)-(af+bh)(ce+dg))}}{2}$$

Esto se ve muy desordenado por lo tanto vamos a simplemente usando las huellas y los determinantes (Nota: sólo es factible para n=2)

$$ x_A=\frac{\text{tr}(A)\pm\sqrt{(\text{tr}(A))^2-4\det(A))}}{2}\\ x_B=\frac{\text{tr}(B)\pm\sqrt{(\text{tr}(B))^2-4\det(B))}}{2}\\ x_{A+B}=\frac{\text{tr}(a+B)\pm\sqrt{(\text{tr}(a+B))^2-4\det(a+B))}}{2}\\ x_{AB}=\frac{\text{tr}(AB)\pm\sqrt{(\text{tr}(AB))^2-4\det(AB))}}{2}$$

Llame a la squreroot términos de $x_A$ $x_B$ $s_A$ $s_B$ respectivamente, para reducir el desorden visual en el siguiente paso

Ahora calcular la suma y el producto de los autovalores

$$x_A+x_B=\frac{\text{tr}(A)+\text{tr}(B)\pm s_A\pm s_B}{2}\\ x_Ax_B=\frac{\text{tr}(A)\text{tr}(B)\pm \text{tr}(A)s_B\pm \text{tr}(B)s_A\pm s_As_B}{4}$$

Ahora desde $\text{tr}(A+B)=\text{tr}(A)+\text{tr}(B)$, comparando $x_A+x_B$ $x_{A+B}$ muestra que la traza de $A$ $B$ no es lo que hace que el contraejemplos a ser posible

Esto significa que los valores de a,d,e,h y las huellas de $A$ $B$ no afecta a si las matrices que se satisface la condición requerida por el contraejemplo. Por lo tanto podemos ponerlos todos a cero para salvarnos a nosotros mismos algunos problemas (por Lo que se acaba de empezar a recoger un contraejemplo de la serie de contraejemplos para $M$)

Así que nuestras ecuaciones se reduce a

$$ x_A=\frac{\pm\sqrt{-4\det(A))}}{2}\\ x_B=\frac{\pm\sqrt{-4\det(B))}}{2}\\ x_{A+B}=\frac{\pm\sqrt{-4\det(a+B))}}{2}\\ x_{AB}=\frac{\text{tr}(AB)\pm\sqrt{(\text{tr}(AB))^2-4\det(AB))}}{2}$$ $$x_A+x_B=\frac{\pm \sqrt{-4\det(A))}\pm \sqrt{-4\det(B))}}{2}\\ x_Ax_B=\frac{\pm \sqrt{-4\det(A))}\sqrt{-4\det(B))}}{4}$$ $$AB=\begin{pmatrix}bg&0\\0&cf\end{pmatrix}\\ A+B=\begin{pmatrix}0&b+f\\c+g&0\end{pmatrix}$$ $$A=\begin{pmatrix}0&b\\c&0\end{pmatrix}, B=\begin{pmatrix}0&f\\g&0\end{pmatrix}$$ Ahora considere la posibilidad de

$$\sqrt{(\text{tr}(AB))^2-4\det(AB))}=\sqrt{(bg+cf)^2-4bgcf}=\sqrt{(bg)^2+2bgcf+(cf)^2-4bgcf}=\sqrt{(bg-cf)^2}=\pm(bg-cf)$$

Dando así

$$ x_A=\pm\sqrt{bc}\\ x_B=\pm\sqrt{fg}\\ x_{A+B}=\pm\sqrt{bc+bg+fc+fg}\\ x_{AB}=\frac{(bg+cf)\pm(bg-cf)}{2}=\text{bg o cf}$$ $$x_A+x_B=\pm \sqrt{bc}\pm \sqrt{fg}\\ x_Ax_B=\pm \sqrt{bc}\sqrt{fg}$$

La resolución de la ecuación en términos de $x_A$ $x_B$

$$ x_A=\pm\sqrt{bc}\\ x_B=\pm\sqrt{fg}\\ x_{A+B}=\pm\sqrt{x_A^2+bg+fc+x_B^2}\\ x_{AB}=\frac{g}{c} x_A^2\text{ o }\frac{c}{g} x_B^2$$ $$x_A+x_B\\ x_Ax_B$$

Así, en orden de $M$ a ser verdad, que es

$$x_Ax_B\neq x_{AB}\\ x_A+x_B\neq x_{A+B}$$

usted tiene $$bg+fc\neq\pm2\sqrt{bc}\sqrt{fg}\\ fg\neq \frac{g^2b}{c}\text{ o }ac\neq 0$$

La ecuación anterior es indeterminado (4 incógnitas con 2 ecuaciones), así que vamos a simplificar asumiendo $f=g=1$ obtener

$a$b+c\neq 2\sqrt{bc}\\ b\neq c\text{ o }ac\neq 0$$

Así que hay un montón de opciones posibles aquí, vamos a elegir a $c=1$, por lo tanto,

$$b+1\neq 2\sqrt{b}\Rightarrow (b+1)^2\neq 4b \Rightarrow b\neq 1\text{ or }0$$

Así que vamos a elegir a $b=2$

Por lo tanto, UNA solución a $M$, que es el requerido contraejemplo es

$$A=\begin{pmatrix}0&2\\1&0\end{pmatrix}, B=\begin{pmatrix}0&1\\1&0\end{pmatrix}$$

$$A+B=\begin{pmatrix}0&3\\2&0\end{pmatrix}, AB=\begin{pmatrix}2&0\\0&1\end{pmatrix}$$

Aquí $A$ tiene los autovalores $\sqrt{2}$ y $-\sqrt{2}$, $B$ tiene los autovalores 1 y -1, mientras que $A+B$ tiene los autovalores $-\sqrt{6}$ $\sqrt{6}$ $AB$ tiene los autovalores 2 o 1. A continuación, es fácil comprobar que no sea posible de los productos o de las cantidades de los autovalores de a $A$ $B$ coincide con al menos uno de los en $A+B$ $AB$ (de hecho, resulta que esta particular contraejemplo, incluso la suma y productos de autovalores en sólo $A$ o $B$ no iguales a los de $A+B$ o $AB$ por lo que es una bastante roto (de ahí casi perfecto) contraejemplo.

Woa esto es MUCHO tiempo!

De todos modos aquí están los pros y los contras de la utilización de este método

Pros

1. Después del cálculo, no sólo obtendrá al menos un contraejemplo (siempre que no existe realmente uno como algunos de los problemas resulta que el contraejemplo conjunto está vacío), que también entender cómo, en el nivel fundamental, es un contraejemplo.
2. Este método garantiza no sólo para dar un contraejemplo, pero les da a TODOS los posibles contraejemplos (o parte de ella) que es posible para el problema (en otras palabras, el "conjunto solución de contraejemplos" para el problema dado). También dice que la restricción de los elementos que ha de satisfacer para ser un contraejemplo, así profundizar su comprensión sobre el objeto matemático en cuestión, de modo que cuando un problema similar surge, usted puede utilizar junto con prueba y error y otros métodos sugeridos por Qiaochu aproximadamente a trabajar en qué dirección debe ir a buscar el contraejemplo. La restricción se puede modificar ligeramente con el fin de encontrar nuevos contraejemplos a un problema o para explorar las propiedades de más exóticos objetos matemáticos, donde la habitual reglas no se aplican

Contras

3. Como se puede ver en esta respuesta, la exploración del "Espacio de Contraejemplos" es en general un muy tedioso e ineficiente, propenso a errores y tarea que requiere tiempo, por lo tanto, obviamente, esto no es recomendable en las condiciones de un examen (a menos que usted puede hacer álgebra rápidamente o conocer el objeto matemático lo suficientemente bien como para tomar atajos). Por lo tanto, es mejor para el tratamiento de este método como último recurso después de todo otro método falla, a menos que usted está interesado en la exploración del objeto matemático a fondo

4. Es fácil perderse, caso y, accidentalmente, a la izquierda de las matemáticas a la hora de explorar el espacio de contraejemplos, lo que resulta en el filosófico y, posiblemente, las cuestiones metafísicas como este