Talk:Generator preimage: Difference between revisions

(7 intermediate revisions by 2 users not shown)

Line 10:

: Here's how it works:

:* We want to find u such that V*u = [0,..0,1,0,..,0] ~~for~~ the i-th index

:* We want to find u such that V*u = [0, ..., 0, 1, 0, ..., 0] where the 1 is on the i-th index.

:* Let's split up the problem:

:** V[i]*u = 1

:** V[no_i]*u = [0,0,...,0] (where V[no i] is V with the i-th row deleted)

:** V[no_i]*u = [0, 0, ..., 0] (where V[no i] is V with the i-th row deleted)

:* First calculate S. this is a kernel/comma basis for V[no_i].

:* The vector we want to find is in the rowspace of S. (aka it is a linear combination of its rows.) This is because ~~V*u = [0,..0,1,0,..,0] so~~ V[no i]*u = [0, 0, ... ,0] <~~br>~~=> u is in the kernel of V[no_i].

:* The vector we want to find is in the rowspace of S. (aka it is a linear combination of its rows.) This is because V[no i]*u = [0, 0, ... , 0] <=> u is in the kernel of V[no_i].

:* By calculating R = V[i] * S, we are basically calculating the number of steps V[i] maps each comma of S to.

:* ~~build~~ the block matrix [R | S] (prepending R to S)

:* Build the block matrix [R | S] (prepending R to S)

:* if we do some row operations or [R | S], it stays valid. ~~say~~ we multiply it by an arbitrary unimodular matrix U: [R' | S'] = U*[R | S] = [U*R | U*S] ~~this~~ is true because R = V[i]*S, so U*R = U*V[i]*S = V[i]*U*S => R' = V[i]*S'

:* If we do some row operations on [R | S], it stays valid. Say we multiply it by an arbitrary unimodular matrix U: [R' | S'] = U*[R | S] = [U*R | U*S] This is true because R = V[i]*S, so U*R = U*V[i]*S = V[i]*U*S => R' = V[i]*S'

:* ~~since~~ we want V[i]*u = 1, we want to find some U so that R' = [1,0,..,0]~~, this~~ is exactly what the HNF does

:* Since we want V[i]*u = 1, we want to find some U so that R' = [1,0,..,0]. This is exactly what the HNF does. The first row of S' is then the vector u we are after.

: 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)

:-[[User:~~Sintel~~|~~Sintel~~]] ([[User talk:~~Sintel~~|talk]]) 00: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)

@@ Line 10: / Line 10: @@
 : Here's how it works:
-:* We want to find u such that V*u = [0,..0,1,0,..,0] for the i-th index
+:* We want to find u such that V*u = [0, ..., 0, 1, 0, ..., 0] where the 1 is on the i-th index.
 :* Let's split up the problem:
 :** V[i]*u = 1
-:** V[no_i]*u = [0,0,...,0]   (where V[no i] is V with the i-th row deleted)
+:** V[no_i]*u = [0, 0, ..., 0]   (where V[no i] is V with the i-th row deleted)
 :* First calculate S. this is a kernel/comma basis for V[no_i].
-:* The vector we want to find is in the rowspace of S. (aka it is a linear combination of its rows.) <br>This is because V*u = [0,..0,1,0,..,0] so V[no i]*u = [0, 0, ... ,0] <br>=> u is in the kernel of V[no_i].
+:* The vector we want to find is in the rowspace of S. (aka it is a linear combination of its rows.) <br>This is because V[no i]*u = [0, 0, ... , 0] <=> u is in the kernel of V[no_i].
 :* By calculating R = V[i] * S, we are basically calculating the number of steps V[i] maps each comma of S to.
-:* build the block matrix [R | S] (prepending R to S)
+:* Build the block matrix [R | S] (prepending R to S)
-:* if we do some row operations or [R | S], it stays valid. say we multiply it by an arbitrary unimodular matrix U:<br>[R' | S'] = U*[R | S] = [U*R | U*S]<br>this is true because R = V[i]*S, so U*R = U*V[i]*S = V[i]*U*S<br>=> R' = V[i]*S'<br>
+:* If we do some row operations on [R | S], it stays valid. Say we multiply it by an arbitrary unimodular matrix U:<br>[R' | S'] = U*[R | S] = [U*R | U*S]<br>This is true because R = V[i]*S, so U*R = U*V[i]*S = V[i]*U*S<br>=> R' = V[i]*S'<br>
-:* since we want V[i]*u = 1, we want to find some U so that R' = [1,0,..,0], this is exactly what the HNF does
+:* Since we want V[i]*u = 1, we want to find some U so that R' = [1,0,..,0]. This is exactly what the HNF does. The first row of S' is then the vector u we are after.
+: 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)
-:-[[User:Sintel|Sintel]] ([[User talk:Sintel|talk]]) 00: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)