Las matrices invertibles de números naturales son permutaciones ... ¿por qué?

Question

He escuchado la siguiente declaración varias veces y tengo la sospecha de que existe un sencillo y elegante a prueba de este hecho, lo que yo simplemente no estoy viendo.

Pregunta: ¿por Qué es cierto que una invertible la matriz de nxn con entero no negativo entradas, cuya inversa también ha entero no negativo entradas, es necesariamente una matriz de permutación?

La razón por la que estoy interesado en esto tiene que ver con categorification. Hay una importante 2-categoría 2-categoría de Kapranov–Voevodsky 2-espacios vectoriales, que en la encarnación ha de objetos dada por los números naturales y 1-morfismos de n a m son matrices de mxn de espacios vectoriales. La composición es como la habitual composición de la matriz, pero con la suma y el producto tensor de espacios vectoriales. El 2-morfismos son las matrices de los lineales de los mapas.

Esta realidad implica que la única equivalencias en este 2-categoría de "permutación de matrices", es decir, aquellas matrices de espacios vectoriales que el aspecto de las matrices de permutación, pero donde cada "1" es reemplazado por un 1-dimensional espacio vectorial.

Es fácil ver la razón por la que el hecho implica esto. Dada una matriz de espacios vectoriales, puede aplicar "dim" para obtener una matriz de enteros no negativos. Dimensión respeta tensor del producto y de la suma directa y por lo que esta asociación es compatible con la composición en 2-Vect. Por lo tanto, si una matriz de espacios vectoriales es débilmente invertible, entonces su matriz de dimensiones también es invertible, y por otra parte tanto de esta matriz y su inversa positivos interger entradas. Por lo tanto, por el hecho, la matriz de dimesnions debe ser una matriz de permutación.

Pero ¿por qué el anterior verdad?

Answer 1

Prueba: la condición de que$M$ tenga entradas enteras no negativas significa que asigna el monoide$\mathbb{Z}_{\geq 0}^n$ a sí mismo. La condición de que$M^{-1}$ es igualmente significa que$M$ es un automorfismo de este monoide.

Los elementos básicos$(0,0,\ldots,0,1,0,\ldots, 0)$ en$\mathbb{Z}_{\geq 0}^n$ son los únicos elementos que no se pueden escribir como$u+v$ para algunos% cero% #% y$u$ en$v$. Esta descripción deja en claro que cualquier automorfismo de$\mathbb{Z}_{\geq 0}^n$ debe permutar esta base. Entonces$\mathbb{Z}_{\geq 0}^n$ es una matriz de permutación.

Answer 2

Esta es una sencilla consecuencia de la Perron-Frobenius teorema, pero voy a desribe una prueba sin el uso de ese teorema.

Un no-negativo de la matriz es la que da el positivo orthant en el positivo orthant. Ya sea integral o no, si la función inversa también es positivo, se deduce que el lineal mapa es una homeomorphism de la positiva orthant a sí mismo. La imagen de la orthant en el espacio proyectivo es una $n-1$-simplex; la inducida por el mapa es un proyectiva mapa que permutes los vértices, o en otras palabras, cualquier matriz es una matriz de permutación veces al positivo de la diagonal de la matriz. El único punto positivo de la unidad en $\mathbb Z$ es 1, por lo que es una matriz de permutación.

Answer 3

Supongamos que$A$ y$B=A^{-1}$ tienen todos los coeficientes en$\mathbb N$. Entonces, lo mismo es cierto para la matriz simétrica$AA^t$ y su inversa$B^t B$. Dado que estas matrices tienen la forma$AA^t=I+a$ y$B^tB=I+b$ con$a$ y$b$ que tienen coeficientes en$\mathbb N$ y$I$ que denotan la matriz de identidad, obtenga$a=b=0$ considerando el producto$(I+a)(I+b)=I+a+b+ab$.

La matriz$A$ es, por lo tanto, una matriz ortogonal con coeficientes en$\mathbb N$, lo que implica que es una matriz de permutación.

Answer 4

Aquí es particularmente simpleminded prueba (que es probablemente la misma como algunos de los otros). Supongamos que $A$ e $B$ se $n \times n$ matrices con los no-negativo entradas y que $AB=D$ es una matriz diagonal. Para cada entrada distinto de cero $a_{ij} \gt 0$ de % de $A$ tenemos $b_{j \ell}=0$ para todos los $\ell \ne i$ desde $d_{i \ell} = 0$. Asimismo, para cada una de las $b_{ji} \gt 0$ tenemos $a_{kj}=0$ para todos los $k \ne i.$

Ahora supongamos que $D$ es invertible, entonces cada fila de a tiene una entrada distinto de cero. Ahora vamos a ver que es el único no-cero de la entrada de su fila y su columna. Para cada una de las $i$ hay algo de $j$ con $a_{ij} \gt 0.$ Entonces $b_{ji} \gt 0$ desde nada en su fila. Desde $d_{mi}=0$ para $m \ne i$, $a_{ij}$ es el único no-cero de la entrada en su columna. Y puesto que no hay dos filas de $B$ son dependientes, para cada $k \ne j$ hay un $m \ne i$ con $b_{km} \gt 0.$ Desde $d_{im}=0$ se sigue que $a_{ik}=0$ hecho $a_{ij}$ es el único no-cero de la entrada de su fila y columna. Del mismo modo, $b_{ji} \gt 0$ es el único no-cero de la entrada de su fila y columna.

Por lo tanto la no-cero entradas de $A$ son las mismas que las de una matriz de permutación $P$ y los de $B$ son los mismos que los de $P^t=P^{-1}$. Si estos no negativa de matrices son matrices de enteros con $AB=I$, entonces el no-cero todas las entradas son $1$ lo $A=P.$