Talk:Generator preimage: Difference between revisions

@@ Line 22: / Line 22: @@
 : I have left out some details and matrix transposes. Hopefully this helps clear things up.
 :-[[User:Sintel|Sintel]] ([[User talk:Sintel|talk]]) 00:51, 18 December 2021 (UTC)
+== Simpler algorithm ==
+The algorithm given in the text is needlessly complex. I will give a simpler one here:
+Given a saturated mapping matrix M, calculate the Smith normal form:
+<math>
+D = LMR
+</math>
+where D is rectangular diagonal and L, R are unimodular. The transversals can be found as the columns of X:
+<math>
+X = R D^{\mathsf T} L
+</math>
+It works because we have:
+<math>
+D = LMR \\
+\Rightarrow M = L^{-1}DR^{-1}
+</math>
+Because L and R are invertible in <math>\mathbb{Z}</math>, by the definition of the Smith normal form. We want to solve:
+<math>
+MX = I \\
+\Rightarrow L^{-1}DR^{-1}X = I \\
+\Rightarrow DR^{-1}X = L
+</math>
+Now the upper left submatrix of <math>D^{\mathsf T}D</math> is identity iff M is saturated, so:
+<math>
+\Rightarrow R^{-1}X = D^{\mathsf T} L \\
+\Rightarrow X = R D^{\mathsf T} L \quad \text{qed.}
+</math>