Talk:Generator preimage: Difference between revisions

Line 17:

:* 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 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'

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

@@ Line 17: / Line 17: @@
 :* 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 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>
-:* 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)