Matriz de descomposición en cuadrados entero positivo matrices

Question

Este es un intento de establecer una analogía con los números primos. Vamos a considerar sólo las matrices cuadradas con entero positivo entradas. Cuáles de ellos son 'prime' y de cómo se descompone dicha matriz en general?

Para ilustrar, no es un producto de dos generales de $2 \times 2$ matrices:

$$AB=\left[ \begin{matrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} \right] \left[ \begin{matrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{matrix} \right]=\left[ \begin{matrix} a_{11} b_{11}+a_{12} b_{21} & a_{11} b_{12}+a_{12} b_{22} \\ a_{21} b_{11}+a_{22} b_{21} & a_{21} b_{12}+a_{22} b_{22} \end{matrix} \right]$$

El intercambio de $a$ $b$ obtenemos la expresión para el otro producto $BA$.

Ahora, si permitimos que cero, negativo y/o racional entradas de nosotros probablemente puede descomponer cualquier matriz en un número infinito de formas.

Sin embargo, si nos limitamos:

$$a_{jk},~b_{jk} \in \mathbb{N}$$

El problema se convierte en bien definido.

Existe un algoritmo para descomponer un arbitrario cuadrado de un número entero positivo de la matriz en un producto de varios entero positivo matrices de las mismas dimensiones?

Hay un conjunto de matrices que pueden'be ser descompuesto, como los números primos (o irreductible polinomios, por ejemplo). La más trivial es uno (recuerde, el cero no están permitidas las entradas):

$$\left[ \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right]$$

No existen números naturales $a_{11},b_{11},a_{12},b_{21}$, tal que:

$$a_{11} b_{11}+a_{12} b_{21}=1$$

La misma se extiende a cualquier dimensión de $d$. Cualquier 'compuesto' $d \times d$ matriz tendrán todas las entradas de $\geq d$. Por lo tanto, para las matrices cuadradas se pueden nombrar varios más 'primos':

$$\left[ \begin{matrix} 2 & 1 \\ 1 & 1 \end{matrix} \right],~~~\left[ \begin{matrix} 1 & 2 \\ 1 & 1 \end{matrix} \right],~~~\left[ \begin{matrix} 1 & 1 \\ 2 & 1 \end{matrix} \right],~~~\left[ \begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix} \right],~~~\left[ \begin{matrix} 2 & 2 \\ 1 & 1 \end{matrix} \right],~~~\left[ \begin{matrix} 1 & 1 \\ 2 & 2 \end{matrix} \right], \dots$$

Y en general, cualquier matriz que tiene al menos una entrada igual a $1$.

Tiene sentido, que la mayoría de las entradas en 'compuesto' matrices será grande, ya que son la multiplicación y la adición de números naturales. Por ejemplo:

$$\left[ \begin{matrix} 1 & 2 & 4 \\ 3 & 3 & 1 \\ 3 & 4 & 4 \end{matrix} \right] \left[ \begin{matrix} 2 & 5 & 5 \\ 4 & 5 & 5 \\ 5 & 1 & 4 \end{matrix} \right]=\left[ \begin{matrix} 30 & 19 & 31 \\ 23 & 31 & 34 \\ 42 & 39 & 51 \end{matrix} \right]$$

$$\left[ \begin{matrix} 2 & 5 & 5 \\ 4 & 5 & 5 \\ 5 & 1 & 4 \end{matrix} \right] \left[ \begin{matrix} 1 & 2 & 4 \\ 3 & 3 & 1 \\ 3 & 4 & 4 \end{matrix} \right] =\left[ \begin{matrix} 32 & 39 & 33 \\ 34 & 43 & 41 \\ 20 & 29 & 37 \end{matrix} \right]$$

Si no hay ningún algoritmo de descomposición para este caso existe, es por lo menos posible reconocer una matriz que no puede ser descompuesto de acuerdo a las reglas anteriores?

Answer 1

Es una extraña pregunta... Vamos a $A\in M(N)$ s.t. $A=PQ$ donde $P,Q\in M(N)$ son aleatorios. Me calcular "el" Smith normal de descomposición de $A$: $A=UDV$ donde $U,V\in GL(\mathbb{Z})$ $D$ es una diagonal en $M(\mathbb{Z})$. Durante cada prueba de Arce, considero que la matriz $UD=[C_1,\cdots,C_n]$ donde $(C_i)_i$ son sus columnas; curiosamente,

(P) para cada $i$, $C_i\geq 0$ o $C_i\geq 0$. Es cierto para cualesquiera matrices $A$ ?

EDIT. Responder a @ eres En Mi Ojo . Yo conjeturó que la propiedad (P) anterior y, para cada $i,j$, $a_{i,j}\geq n$ caracterizar la descomponible matrices $A\in M(N)$. Por desgracia, la matriz $A=\begin{pmatrix}10&13\\9&5\end{pmatrix}\in M(N)$ satisface (P), pero es indecomposable.

Comentario 1. Si $A=UV$ es descomponible, hay muchas otras descomposiciones: $A=(UP)(P^TV)$ donde $P$ es cualquier permutación.

Observación 2. Se puede considerar que la permanente de la función; si $A=UV$, $per(A)> per(U)per(V)$ y, en particular,$per(U)<\dfrac{per(A)}{n!}$. Si buscamos una descomposición final de la $A$ arriba, a continuación, obtenemos $\det(U)\in\{\pm 67,\pm 1\}$$per(U)\leq 83$.

Answer 2

Ahora entiendo que un algoritmo para el caso general, es raro. Buscando en la web, sólo he encontrado varios artículos, preocupados por entero positivo de la matriz de descomposición en binario de las matrices.

---

Traté de considerar un caso particular, que parece ser la más simple:

$$C=\left[ \begin{matrix} 2 & c_b \\ c_a & c \end{matrix} \right]$$

Donde $c_a,c_b,c \in \mathbb{N}$ - arbitraria de números naturales. Esta matriz es, obviamente, 'primer' o puede ser descompuesto en dos 'prime' de las matrices.

$$\left[ \begin{matrix} 2 & c_b \\ c_a & c \end{matrix} \right]=\left[ \begin{matrix} 1 & 1 \\ a_{1} & a_{2} \end{matrix} \right] \left[ \begin{matrix} 1 & b_{1} \\ 1 & b_{2} \end{matrix} \right]$$

$$\begin{cases} a_1+a_2=c_a \\ b_1+b_2=c_b \\ a_1b_1+a_2b_2=c \end{cases}$$

De nuevo $a_1,b_1,a_2,b_2 \in \mathbb{N}$. A partir de la cual podemos obtener inmediatamente la condición más importante para $C$ 'compuesto':

$$\max(c_a,c_b)\leq c<c_ac_b$$

La igualdad en la izquierda sólo es posible en los casos triviales de $a_1=a_2=1$ o $b_1=b_2=1$, que no voy a tener en cuenta.

Si estas condiciones no se mantienen, a continuación, $C$ 'prime'. Lo que nos da nuevos ejemplos de 'prime' de las matrices:

$$\left[ \begin{matrix} 2 & 5 \\ 7 & 39 \end{matrix} \right],~~~\left[ \begin{matrix} 2 & 15 \\ 8 & 11 \end{matrix} \right],~~~\dots$$

---

Otra propiedad es la siguiente - si nos simultáneamente permutar $a_k$$b_k$, $C$ no cambia. Lo que significa, que si $C$ es compuesto, tiene al menos dos factorizations:

$$\left[ \begin{matrix} 2 & c_b \\ c_a & c \end{matrix} \right]=\left[ \begin{matrix} 1 & 1 \\ a_{1} & a_{2} \end{matrix} \right] \left[ \begin{matrix} 1 & b_{1} \\ 1 & b_{2} \end{matrix} \right]=\left[ \begin{matrix} 1 & 1 \\ a_{2} & a_{1} \end{matrix} \right] \left[ \begin{matrix} 1 & b_{2} \\ 1 & b_{1} \end{matrix} \right]$$

Por lo tanto, sin pérdida de generalidad, podemos establecer:

$$a_1 >a_2,~~~~\frac{c_a}{2}<a_1<c_a \tag{*}$$

El caso trivial $a_1=a_2$ da nilpotent matriz $C$, que no voy a considerar aquí.

Resolviendo el sistema de ecuaciones anterior para $b_1$, obtenemos:

$$b_1=\frac{c-c_b(c_a-a_1)}{2a_1-c_a} \tag{**}$$

$$c_a-\frac{c}{c_b}<a_1<c_a$$

El anterior significa que tanto los intervalos de $(\frac{c_a}{2},c_a)$ $(c_a-\frac{c}{c_b},c_a)$ debe contener al menos un número entero:

$$\frac{c_a}{2}>1,~~~\frac{c}{c_b}\geq 2$$

Con la condición de $(*)$ tenemos dos casos:

$$b_1>b_2,~~~\frac{c_b}{2}<b_1<c_b,~~~~c_b-\frac{c}{c_a}<b_1 \tag{1}$$

$$c>\frac{c_ac_b}{2},~~~~~\frac{c}{c_a} \geq 2,~~~~~\frac{c_b}{2}>1$$

$$b_1<b_2,~~~b_1<\frac{c_b}{2},~~~~b_1<c_b-\frac{c}{c_a} \tag{2}$$

$$c<\frac{c_ac_b}{2},~~~~~\frac{c_b}{2}>1$$

Las condiciones en las $c$ seguir a partir del reordenamiento de la desigualdad.

No parece haber ninguna condición adicional para el caso de $(2)$, pero no estoy seguro.

Como un ejemplo de una matriz compuesta:

$$C=\left[ \begin{matrix} 2 & 5 \\ 7 & 19 \end{matrix} \right]$$

Este es el caso de $(1)$ y todas las condiciones necesarias espera.

$$\frac{c_a}{2}=3.5,~~~~c_a-\frac{c}{c_b}=3.2 \rightarrow a_1 = 4,5,6$$

$$\frac{c_b}{2}=2.5,~~~~c_b-\frac{c}{c_a}=2\frac{4}{7} \rightarrow b_1 = 3,4$$

El uso de $(**)$ obtenemos:

$$a_1=4 \to b_1=4$$

$$a_1=5 \to b_1=3$$

Lo que nos da (creo) todas las soluciones:

$$\left[ \begin{matrix} 2 & 5 \\ 7 & 19 \end{matrix} \right]=\left[ \begin{matrix} 1 & 1 \\ 4 & 3 \end{matrix} \right] \left[ \begin{matrix} 1 & 4 \\ 1 & 1 \end{matrix} \right]=\left[ \begin{matrix} 1 & 1 \\ 3 & 4 \end{matrix} \right] \left[ \begin{matrix} 1 & 1 \\ 1 & 4 \end{matrix} \right]$$

$$\left[ \begin{matrix} 2 & 5 \\ 7 & 19 \end{matrix} \right]=\left[ \begin{matrix} 1 & 1 \\ 5 & 2 \end{matrix} \right] \left[ \begin{matrix} 1 & 3 \\ 2 & 1 \end{matrix} \right]=\left[ \begin{matrix} 1 & 1 \\ 2 & 5 \end{matrix} \right] \left[ \begin{matrix} 1 & 2 \\ 1 & 3 \end{matrix} \right]$$

---

Este caso fue considerado para ilustrar cómo iba a abordar este problema. Que es muy largo y complicado camino. Si alguien sabe una mejor y más rápida manera, le estaría agradecido.