Talk:Generator preimage: Difference between revisions

@@ Line 8: / Line 8: @@
 --[[User:Cmloegcmluin|Cmloegcmluin]] ([[User talk:Cmloegcmluin|talk]]) 18:04, 6 October 2021 (UTC)
+: Here's how it works:
+:* We want to find u such that V*u = [0,..0,1,0,..,0] for 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)
+:* 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].
+:* 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)
+:* 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
+:-[[User:Sintel|Sintel]] ([[User talk:Sintel|talk]]) 00:51, 18 December 2021 (UTC)