Talk:Generator preimage - Revision history

Sintel: Sintel moved page Talk:Transversal generators to Talk:Generator preimage: Use more common term over transversal

2025-03-27T23:26:10Z

Sintel moved page Talk:Transversal generators to Talk:Generator preimage: Use more common term over transversal

← Older revision	Revision as of 23:26, 27 March 2025
(No difference)

Cmloegcmluin at 19:05, 20 January 2022

2022-01-20T19:05:13Z

← Older revision		Revision as of 19:05, 20 January 2022
Line 22:		Line 22:
	: I have left out some details and matrix transposes. Hopefully this helps clear things up.		: 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)		:-[[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 ==		== Simpler algorithm ==
Line 62:		Line 64:

	-[[User:Sintel\|Sintel]] ([[User talk:Sintel\|talk]]) 18:51, 18 December 2021 (UTC)		-[[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)

Sintel at 18:51, 18 December 2021

2021-12-18T18:51:38Z

← Older revision		Revision as of 18:51, 18 December 2021
Line 60:		Line 60:
	\Rightarrow X = R D^{\mathsf T} L \quad \text{qed.}		\Rightarrow X = R D^{\mathsf T} L \quad \text{qed.}
	</math>		</math>

			-[[User:Sintel\|Sintel]] ([[User talk:Sintel\|talk]]) 18:51, 18 December 2021 (UTC)

Sintel: simple algorithm

2021-12-18T18:51:19Z

simple algorithm

← Older revision		Revision as of 18:51, 18 December 2021
Line 22:		Line 22:
	: I have left out some details and matrix transposes. Hopefully this helps clear things up.		: 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)		:-[[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>

Sintel at 01:19, 18 December 2021

2021-12-18T01:19:08Z

← Older revision		Revision as of 01:19, 18 December 2021
Line 18:		Line 18:
	:* By calculating R = V[i] * S, we are basically calculating the number of steps V[i] maps each comma of S to.		:* 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] = [UR \| US]<br>This is true because R = V[i]S, so UR = UV[i]S = V[i]US<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] = [UR \| US]<br>This is true because R = V[i]S, so UR = UV[i]S = V[i]US<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. The first row of S' is then the vector u we are after.		:* 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.		: 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)		:-[[User:Sintel\|Sintel]] ([[User talk:Sintel\|talk]]) 00:51, 18 December 2021 (UTC)

Sintel at 01:08, 18 December 2021

2021-12-18T01:08:28Z

← Older revision		Revision as of 01:08, 18 December 2021
Line 19:		Line 19:
	:* 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] = [UR \| US]<br>This is true because R = V[i]S, so UR = UV[i]S = V[i]US<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] = [UR \| US]<br>This is true because R = V[i]S, so UR = UV[i]S = V[i]US<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. The first row of S' is then the vector u we are after.		:* 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.		: 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)		:-[[User:Sintel\|Sintel]] ([[User talk:Sintel\|talk]]) 00:51, 18 December 2021 (UTC)

Sintel at 01:08, 18 December 2021

2021-12-18T01:08:11Z

← Older revision		Revision as of 01:08, 18 December 2021
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].		:* 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.		:* 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] = [UR \| US]<br>~~this~~ is true because R = V[i]S, so UR = UV[i]S = V[i]US<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] = [UR \| US]<br>This is true because R = V[i]S, so UR = UV[i]S = V[i]US<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.		: 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)		:-[[User:Sintel\|Sintel]] ([[User talk:Sintel\|talk]]) 00:51, 18 December 2021 (UTC)

Sintel at 01:06, 18 December 2021

2021-12-18T01:06:27Z

Sintel at 00:51, 18 December 2021

2021-12-18T00:51:06Z

← Older revision		Revision as of 00:51, 18 December 2021
Line 8:		Line 8:

	--[[User:Cmloegcmluin\|Cmloegcmluin]] ([[User talk:Cmloegcmluin\|talk]]) 18:04, 6 October 2021 (UTC)		--[[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 Vu = [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] = [UR \| US]<br>this is true because R = V[i]S, so UR = UV[i]S = V[i]US<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)

Cmloegcmluin: unhyphenate "comma basis"

2021-11-12T20:19:03Z

unhyphenate "comma basis"

← Older revision		Revision as of 20:19, 12 November 2021
Line 5:		Line 5:
	I'm the person who added the "example" section as well as the "Wolfram Language implementation" there, so I understand ''how'' to do it, but I have no real idea why it works.		I'm the person who added the "example" section as well as the "Wolfram Language implementation" there, so I understand ''how'' to do it, but I have no real idea why it works.

	It's clear enough to me that the pseudoinverse step is how we convert the input mapping into generators. But then how do we "massage" those generators by combining them one at a time with the comma-basis, defactoring, dot-producting with the original row to get a thing we prepend before HNF'ing so that it has some effect on what remains when we grab that row back out...? It's quite tricksy.		It's clear enough to me that the pseudoinverse step is how we convert the input mapping into generators. But then how do we "massage" those generators by combining them one at a time with the comma basis, defactoring, dot-producting with the original row to get a thing we prepend before HNF'ing so that it has some effect on what remains when we grab that row back out...? It's quite tricksy.

	--[[User:Cmloegcmluin\|Cmloegcmluin]] ([[User talk:Cmloegcmluin\|talk]]) 18:04, 6 October 2021 (UTC)		--[[User:Cmloegcmluin\|Cmloegcmluin]] ([[User talk:Cmloegcmluin\|talk]]) 18:04, 6 October 2021 (UTC)

← Older revision		Revision as of 01:06, 18 December 2021
Line 10:		Line 10:

	: Here's how it works:		: 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:		:* Let's split up the problem:
	:** V[i]*u = 1		:** 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].		:* 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 ~~Vu = [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.		:* 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] = [UR \| US]<br>this is true because R = V[i]S, so UR = UV[i]S = V[i]US<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] = [UR \| US]<br>this is true because R = V[i]S, so UR = UV[i]S = V[i]US<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
			: 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)		:-[[User:Sintel\|Sintel]] ([[User talk:Sintel\|talk]]) 00:51, 18 December 2021 (UTC)