Solución general algebraicamente agradable para el último paso de eliminación gaussiana a Smith Normal Form?

Question

Mi pregunta es un poco de preámbulo: se refiere a un bien conocido y resuelto el problema, pero estoy en busca de una solución con una particular y agradable propiedad.

$\newcommand{\matriz}[4]{\left( \begin{array}{cc} #1 & #2 \\ #3 & #4 \end{array} \right)} \DeclareMathOperator{\lcm}{lcm}$In using Guassian elimination to put a matrix into Smith normal form over $\mathbb{Z}$ (or, more generally, some PID), the last step is to make sure that successive diagonal entries divide each other. Solving this reduces to the following problem (with all matrices over $\mathbb{Z}$):

• dada una matriz diagonal $M = \left( \begin{array}{cc} a & 0 \\ 0 & b \end{array} \right)$, encontramos invertible matrices $L$, $R$ tal que $$ M = L \left( \begin{array}{cc} \gcd(a,b) & 0 \\ 0 & \lcm(a,b) \end{array} \right) R $$

Este es, por supuesto, bien conocido y no es difícil de hacer. Por ejemplo, usando el algoritmo de Euclides para encontrar $(x,y)$ tal que $ax + by = d = \gcd(a,b)$, se puede definir

$$ L = \left( \begin{array}{cc} a/d & -y \\ b/d & x \end{array} \right), \quad R = \left( \begin{array}{cc} 1-yb/d & yb/d \\ -1 & 1 \end{array} \right)$$ o, alternativamente, $$ L = \left( \begin{array}{cc} a/d & -1 \\ 1-xa/d & x \end{array} \right), \quad R = \left( \begin{array}{cc} 1-yb/d & b/d \\ -y & 1 \end{array} \right).$$

Sin embargo, en el caso especial donde $a$ divide $b$, sabemos que $M$ es ya tan deseado y así podríamos simplemente tome $L = R = I$. Mi pregunta es: ¿podemos encontrar un general algebraicas solución como la de arriba (es decir, algebraica de las definiciones de $L$, $R$ en términos de los números enteros $(x,y,a/d,b/d)$), pero con la propiedad adicional de que al $a$ divide $b$ (y así $x=1$, $y=0$, $a/d=1$), la solución de los rendimientos de $L = R = I$? Aproximadamente: podemos encontrar una solución algebraica que sólo hace algo no trivial si se necesita?

Answer 1

Sí. Sólo tenemos que venir para arriba con una secuencia de enteros de fila y columna de las operaciones que se reduce a la forma normal de Smith, y que es trivial en el caso especial donde los $a$ divide $b$. Aquí está una secuencia:

1. $\begin{bmatrix}a & 0 \\ 0 & b\end{bmatrix} = E_1 \begin{bmatrix}a & 0 \\ a & b\end{bmatrix}$ para algunos primaria matriz $E_1$.

2. $\begin{bmatrix}a & 0 \\ a & b\end{bmatrix} = \begin{bmatrix}r & s \\ d & b\end{bmatrix} M_2$ para algunos matriz $M_2$.
   (Tenga en cuenta que $r=d=a$, $s=0$, y $M_2$ es la matriz de identidad en el caso especial.)

3. $\begin{bmatrix}r & s \\ d & b\end{bmatrix} = E_3\begin{bmatrix}d & t \\ d & b\end{bmatrix}$ para algunos primaria matriz $E_3$.
   (Tenga en cuenta que esta operación de filas es trivial en el caso especial, con $t=0$.)

4. $\begin{bmatrix}d & t \\ d & b\end{bmatrix} = E_4\begin{bmatrix}d & t \\ 0 & m\end{bmatrix}$ para algunos primaria matriz $E_4$.
   (En el caso especial, $m=b$, y esta fila de la operación es la inversa de la operación de filas en el primer paso).

5. $\begin{bmatrix}d & t \\ 0 & m\end{bmatrix} = \begin{bmatrix}d & 0 \\ 0 & m\end{bmatrix}E_5$ para algunos primaria matriz $E_5$.
   (Tenga en cuenta que esta columna la operación es trivial en el caso especial, ya que $t=0$.)

La informática da $$ E_1 = \begin{bmatrix}1 & 0 \\ -1 & 1\end{bmatrix},\qquad M_2 = \begin{bmatrix}(a+by)/d & (b-bx)/d \\ -y & x\end{bmatrix},\qquad E_3 = \begin{bmatrix}1 & ax/d-1 \\ 0 & 1\end{bmatrix},\qquad $$ $$ E_4 = \begin{bmatrix}1 & 0 \\ 1 & 1\end{bmatrix},\qquad E_5 = \begin{bmatrix}1 & b(d-a)/d^2 \\ 0 & 1\end{bmatrix}. $$ Multiplicando $L=E_1E_3E_4$ $R=E_5M_2$ nos da $$ L \;=\; \begin{bmatrix}ax/d & ax/d-1 \\ 1-ax/d & 2-ax/d\end{bmatrix}, \qquad R \;=\; \begin{bmatrix}a(d+by)/d^2 & b(d-ax)/d^2 \\ -y & x\end{bmatrix}. $$ En el caso de que $x=1$, $y=0$, y $d=a$, tanto de estas matrices son la matriz de identidad.