Resolver la matriz entera tal que $R^gu=v$ dado $u$ y $v$

Question

Dado un número entero no negativo $n$ -vectores $u$ y $v$ ¿cómo se encuentran todos $n \times n$ matrices enteras no negativas $R$ y poderes $g$ tal que $R^gu=v$ ?

Answer 1

Todas las soluciones pueden encontrarse mediante un enfoque algorítmico exhaustivo. Nota:

$$ Ru=v=\left[ \begin {array}{ccc} R_{{1,1}}&R_{{1,2}}&...\\ ...&...&...\\ ...&R_{{n,n-1}}&R_{{n,n}} \end {array} \right]\left[ \begin {array}{c} u_{{1}}\\ ... \\ u_{{n}}\end {array} \right]=\left[ \begin {array}{c} v_{{1}}\\ ... \\ v_{{n}}\end {array} \right], $$ implica: $$\sum_{j=1}^{n}R_{i,j}u_j=v_i\,:\,i=1..n,\,\,\,\,\,\,\,\,\,\,(1)$$ por lo que el problema es equivalente a:

Encontrar todas las soluciones (no negativas) de $n$ ecuaciones diofatinas lineales independientes en $n$ variables, $R_{i,1}..R_{i,n}$ ( Manual de matemáticas discretas y combinatorias Rosen & Michaels).

Solución: se encuentra una solución particular utilizando el Algoritmo euclidiano (o alguna conjetura) y a partir de ahí se encuentran todas las soluciones de forma algorítmica.

Dicho esto:

• no existen soluciones a menos que $\text{gcd}(u_1,u_2,..,u_n)|v_i,\forall i$ . Prueba : $\text{gcd}(u_1,u_2,..,u_n)$ divide el lado izquierdo de la Ecuación (1) por lo que debe dividir el derecho.
• sólo soluciones no negativas (valores para $R_{i,j}$ ) están en voz alta por lo que, cuando $u_j>0 \,\,\forall j$ el número de soluciones de cada ecuación diofántica es finito y, por tanto, el número de soluciones matriciales distintas es finito. Prueba : la no negatividad limita los números desde abajo y el tamaño finito de $v_i$ los limita desde arriba.
• si $u_j=0$ para algunos $j$ entonces $R_{i,j}$ puede hacerse arbitraria $\forall j$ y, por tanto, si existe alguna solución, el número de soluciones matriciales distintas es infinito.

Ejemplo: n=2

Consideremos la ecuación lineal simple de Diofantina para el $n=2$ caso: $$ax+by=c\,:\, \text{gcd}(a,b)|c$$ si $x_0,y_0$ es una solución particular entonces todas las soluciones son de la forma: $$x=x_0+\frac{b}{\text{gcd}(a,b)}k,y=y_0-\frac{a}{\text{gcd}(a,b)}k\,:\,k\in\mathbb{Z}$$ Prueba: Subrayar las soluciones demuestra que son soluciones. Para demostrar que son las únicas soluciones cambia las variables a $x=X+x_0,y=Y+y_0$ para obtener: $\frac{a}{\text{gcd}(a,b)}X+\frac{b}{\text{gcd}(a,b)}Y=0$ entonces porque $\frac{b}{\text{gcd}(a,b)}\nmid\frac{a}{\text{gcd}(a,b)}$ tenemos $\frac{b}{\text{gcd}(a,b)}|X$ así que $X=k\frac{b}{\text{gcd}(a,b)},k\in \mathbb{Z}$ y de forma similar $Y=-k\frac{a}{\text{gcd}(a,b)},k\in \mathbb{Z}$ .

Aplíquelo al siguiente ejemplo: $$ \left[ \begin {array}{cc} R_{{1,1}}&R_{{1,2}}\\ R_{ {2,1}}&R_{{2,2}}\end {array} \right] \left[ \begin {array}{c} 6\\ 9 \end {array} \right] =\left[ \begin {array}{c} 45\\ 51 \end {array} \right] $$ dividir por $\text{gcd}(6,9)=3$ para simplificar las cosas y obtener: $$2\,x+3\,y=15:(x,y)=(R_{1,1},R_{1,2})$$ $$2\,s+3\,t=17:(s,t)=(R_{2,1},R_{2,2})$$ La conjetura educada conduce a soluciones particulares: $$(x_0=-15,y_0=15),(s_0=-17,t_0=17)$$ las soluciones generales para la primera ecuación son: $$x=-15+3k,y=15-2k$$ sólo se dan soluciones positivas para $k=5,6,7$ que dan: $$(R_{1,1},R_{1,2}):(0,5),(3,3),(6,1)$$ un razonamiento similar conduce a: $$(R_{2,1},R_{2,2}):(1,5),(4,3),(7,1)$$ y, por tanto, las únicas matrices que resuelven el problema están formadas por todas las combinaciones de los vectores fila encontrados anteriormente, $9$ en total: $$ \left[ \begin {array}{cc} 0&5\\ 1&5\end {array} \right],\left[ \begin {array}{cc} 0&5\\ 4&3\end {array} \right],\left[ \begin {array}{cc} 0&5\\ 7&1\end {array} \right],\left[ \begin {array}{cc} 3&3\\ 1&5\end {array} \right],\left[ \begin {array}{cc} 3&3\\ 4&3\end {array} \right],\left[ \begin {array}{cc} 3&3\\ 7&1\end {array} \right],\left[ \begin {array}{cc} 6&1\\ 1&5\end {array} \right],\left[ \begin {array}{cc} 6&1\\ 4&3\end {array} \right],\left[ \begin {array}{cc} 6&1\\ 7&1\end {array} \right]. $$

Si $n>2$ se necesita un procedimiento iterativo para resolver las ecuaciones diofantinas (véase la referencia). Dada la equivalencia de este problema con un área de investigación tan estudiada, este es probablemente el mejor enfoque, si no el único.

Para ver si $R$ y $R^g, g>1$ , ambos resuelven la ecuación encuentran los vectores fila en el $g=1$ siguiendo el método descrito anteriormente y comprobar si hay algún cierre al elevar a una potencia, es decir, comprobar si alguna de las matrices permitidas elevadas a la potencia es también una de las soluciones encontradas como el conjunto de soluciones para el caso $g=1$ contiene todas las soluciones permitidas (como señala @ˈjuː.zɚ79365 en sus comentarios).

Pero hay que tener en cuenta una restricción importante. Si: $$Ru=R^gu=v,\,\,\,\,\,\,\,\,\,(2)$$ y multiplicando por $R^{g-1}$ da: $$R^gu=R^{2g-1}u,$$ que por $(2)$ implica: $$R^{2g-1}u=Ru=v,$$ y multiplicando por $R^{g-1}$ de nuevo mostrará que $R^{3g-2}u=v$ e.t.c, continuando este proceso muestra $(2)$ implica: $$\lim_{m \to \infty}R^{m(g-1)+1}u=v.$$ Ahora, en lugar de $(\ge0)$ supongamos que todos los elementos de $R$ son enteros positivos $\ge1$ . Entonces por la definición de multiplicación de matrices: $$(AB)_{i,j}=\sum_{k=1}A_{i,k}B_{k,j},$$ subir $R$ a potencias superiores será sumar y multiplicar enteros positivos $\ge1$ lo que significará elementos matriciales de $R^{m(g-1)+1}$ será creciente hasta el infinito a medida que $m\rightarrow \infty$ . Eventualmente para $m$ lo suficientemente grande: $$R^{m(g-1)+1}_{i,j}>\text{max}(v)\,\forall \,i,j,$$ y así cuando $R^{m(g-1)+1}$ se multiplica por $u$ un vector con elementos no negativos, es imposible que sea igual a $v$ . Esto conduce a una contradicción y, por tanto, se obtiene un teorema.

Teorema: Si $R$ es un positivo matriz entera, $u$ y $v$ son vectores enteros no negativos, $v$ no es el vector cero y: $$Ru=v,$$ entonces: $$R^gu\ne v\,\,:\,\,\forall\,g>1\in \mathbb{Z}.$$

Esto es muy restrictivo. Aunque no se extiende a todas las matrices no negativas, descarta cualquier solución en $R$ para $Ru=R^gu=v,g>1$ si cuando se eleva a una potencia suficientemente alta $R$ se convierte en una matriz positiva (tal matriz se conoce como "primitva"), ya que entonces podríamos aplicar simplemente el teorema.