Talk:Generator preimage: Difference between revisions

← Older edit

VisualWikitext

@@ 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)
+:: Thanks as always Sintel. I haven't taken the time to add this to the main page because I haven't understood it fully myself yet. But you are welcome to do so. --[[User:Cmloegcmluin|Cmloegcmluin]] ([[User talk:Cmloegcmluin|talk]]) 19:05, 20 January 2022 (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>
+-[[User:Sintel|Sintel]] ([[User talk:Sintel|talk]]) 18:51, 18 December 2021 (UTC)
+: Love it! I've added my interpretation of this to the main page. Feel free to tweak if you see necessary. --[[User:Cmloegcmluin|Cmloegcmluin]] ([[User talk:Cmloegcmluin|talk]]) 19:05, 20 January 2022 (UTC)