Defactoring: Difference between revisions

Line 305:

==== by hand ====

In an effort to demystify the effects of column Hermite defactoring, ~~we will here~~ walk though an example manually~~. It's a silly example, but suppose we have the mapping {{vector|{{map|6 5 4}} {{map|4 -4 1}}}}. Spoiler alert: it is 11-enfactored~~.

In an effort to demystify the effects of column Hermite defactoring, let's walk though an example manually.

~~This is pretty long so I've put it in a collapsible section. Just click "expand" if you're interested~~:

First we need to learn how to perform its two building blocks by hand:

# Hermite decomposition

# inversion

~~### mw-collapsed~~

After we know how to do these two things individually, we'll learn how to tweak them and assemble them together in order to perform a complete column Hermite defactoring.

~~<div class="mw-collapsible">~~

Fortunately, both of these two processes can be done using a technique you may already be familiar with if you've learned how to calculate the null-space of a mapping by hand (as demonstrated [[User:Cmloegcmluin/RTT_How-To#null-space|here]]):

# augmenting your matrix with an identity matrix

~~To work through DCF by hand, we first need to know how to do a couple of its building blocks by hand: Hermite decomposition~~, ~~and inversion. Both~~ of these processes can be done using a technique you may be familiar with ~~already~~ if you've ~~calculated~~ the null-space of a mapping by hand (as demonstrated [[User:Cmloegcmluin/RTT_How-To#null-space|here]]): augmenting your matrix with an identity matrix~~, then~~ performing elementary row or column operations until a desired state is achieved.

# performing elementary row or column operations until a desired state is achieved

===== Hermite decomposition by hand =====

Line 569:

Line 571:

===== putting it all together =====

In the Wolfram Language algorithm described above, the input matrix is first transposed and then Hermite decomposed. In fact, this is due to a limitation of the built-in <code>HermiteDecomposition[]</code> function in Wolfram Language. The HNF is well understood both in its more common and default row-style as well as a column-style, so it might be expected for Wolfram Language to provide an option for the <code>HermiteDecomposition[]</code> function to perform it by columns. ~~The~~ transposition our code does is a workaround for this lack.

In the Wolfram Language algorithm described above, the input matrix is first transposed and then Hermite decomposed. In fact, this is due to a limitation of the built-in <code>HermiteDecomposition[]</code> function in Wolfram Language. The HNF is well understood both in its more common and default row-style as well as a column-style, so it might be expected for Wolfram Language to provide an option for the <code>HermiteDecomposition[]</code> function to perform it by columns. Alas, it does not. So the transposition our code does is a workaround for this lack.

When doing a column-style Hermite decomposition by hand, we have two options~~. The first option is to mimic what~~ we're doing in the code: transpose the matrix, and then do a Hermite decomposition as demonstrated above~~. The second option would be~~ to ~~augment~~ the matrix to the bottom ~~(instead of to the right)~~, then use elementary column operations instead of elementary row operations (such that it looks more similar to the process for computing the null-space by hand). Here, we'll be demonstrating the first option, because we might as well follow the same approach as the code unless we have a compelling reason not to, and we don't: if we rotate everything 90 degrees like this, we have to learn to recognize the ###

When doing a column-style Hermite decomposition by hand, we have two options:

# Mimic this workaround that we're doing in the code: transpose the matrix, and then do a Hermite decomposition as demonstrated above: augment to the right and perform row operations;

# Augment the matrix to the ''bottom'', and then use elementary column operations instead of elementary row operations (such that it looks more similar to the process for computing the null-space by hand).

~~Because column-style~~ Hermite decomposition is

Here, we'll be demonstrating the process using the first option, because we might as well follow the same approach as the code unless we have a compelling reason not to. And we don't! If we were to follow the second option — rotating everything 90 degrees — we'd have to rewire our brains to recognize matrices in HNF but rotated 90 degrees, which is certainly harder than just transposing a matrix 90 degrees and then treating it the same way with respect to the complexities of Hermite decomposition as we've already become accustomed to.

~~By hand~~, ~~because we know what we~~'~~re doing~~, we do it ~~a bit more simply.~~

So, while it's a silly example, let's suppose we want to defactor the mapping {{vector|{{map|6 5 4}} {{map|4 -4 1}}}}. Spoiler alert: it is 11-enfactored:

<math>\~~begin{array} {l}~~ \begin{array} {r}

<math>\left[ \begin{array} {rrr}

6 & 5 & -4 \\

4 & -4 & 1 \\

\~~hline~~

\end{array} \right]</math>

Our first step is to transpose it:

<math>\left[ \begin{array} {rrr}

6 & 4 \\

5 & -4 \\

-4 & 1 \\

\end{array} \right]</math>

And now we're going to augment it to the right, so we can do the first step of the Hermite decomposition. But we're actually going to go a bit further. We're going to go ahead and augment it to the right and also augment the augmenting matrix to the bottom, because that's where we're going to perform the next step, which is the inversion. We learned inversion using augmentation to the right, but remember: everything we're doing here is transposed! So augmenting to the bottom is the correct thing to do there. When we're all done we'll transpose one more time to undo it.

<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}

6 & 4 \\

5 & -4 \\

-4 & 1 \\

\end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}

1 & 0 & 0 \\

0 & 1 & 0 \\

0 & 0 & 1 \\

\hline

\~~end{array} & \rule[-16mm]{0.375mm}{20mm} & \begin{array} {r} \\ \\~~

1 & 0 & 0 \\

0 & 1 & 0 \\

0 & 0 & 1 \\

\end{array} \end{array}</math>

\end{array} \right] \end{array} </math>

I think that the fact that you're not allowed to divide is equivalent to the fact that at every step along the way, the augmented matrix remains unimodular

@@ Line 305: / Line 305: @@
 ==== by hand ====
-In an effort to demystify the effects of column Hermite defactoring, we will here walk though an example manually. It's a silly example, but suppose we have the mapping {{vector|{{map|6 5 4}} {{map|4 -4 1}}}}. Spoiler alert: it is 11-enfactored.
+In an effort to demystify the effects of column Hermite defactoring, let's walk though an example manually.
-This is pretty long so I've put it in a collapsible section. Just click "expand" if you're interested:
+First we need to learn how to perform its two building blocks by hand:
+# Hermite decomposition
+# inversion
-### mw-collapsed
+After we know how to do these two things individually, we'll learn how to tweak them and assemble them together in order to perform a complete column Hermite defactoring.
-<div class="mw-collapsible">
+Fortunately, both of these two processes can be done using a technique you may already be familiar with if you've learned how to calculate the null-space of a mapping by hand (as demonstrated [[User:Cmloegcmluin/RTT_How-To#null-space|here]]):
+# augmenting your matrix with an identity matrix
-To work through DCF by hand, we first need to know how to do a couple of its building blocks by hand: Hermite decomposition, and inversion. Both of these processes can be done using a technique you may be familiar with already if you've calculated the null-space of a mapping by hand (as demonstrated [[User:Cmloegcmluin/RTT_How-To#null-space|here]]): augmenting your matrix with an identity matrix, then performing elementary row or column operations until a desired state is achieved.
+# performing elementary row or column operations until a desired state is achieved
 ===== Hermite decomposition by hand =====
@@ Line 569: / Line 571: @@
 ===== putting it all together =====
-In the Wolfram Language algorithm described above, the input matrix is first transposed and then Hermite decomposed. In fact, this is due to a limitation of the built-in <code>HermiteDecomposition[]</code> function in Wolfram Language. The HNF is well understood both in its more common and default row-style as well as a column-style, so it might be expected for Wolfram Language to provide an option for the <code>HermiteDecomposition[]</code> function to perform it by columns. The transposition our code does is a workaround for this lack.
+In the Wolfram Language algorithm described above, the input matrix is first transposed and then Hermite decomposed. In fact, this is due to a limitation of the built-in <code>HermiteDecomposition[]</code> function in Wolfram Language. The HNF is well understood both in its more common and default row-style as well as a column-style, so it might be expected for Wolfram Language to provide an option for the <code>HermiteDecomposition[]</code> function to perform it by columns. Alas, it does not. So the transposition our code does is a workaround for this lack.
-When doing a column-style Hermite decomposition by hand, we have two options. The first option is to mimic what we're doing in the code: transpose the matrix, and then do a Hermite decomposition as demonstrated above. The second option would be to augment the matrix to the bottom (instead of to the right), then use elementary column operations instead of elementary row operations (such that it looks more similar to the process for computing the null-space by hand). Here, we'll be demonstrating the first option, because we might as well follow the same approach as the code unless we have a compelling reason not to, and we don't: if we rotate everything 90 degrees like this, we have to learn to recognize the ###
+When doing a column-style Hermite decomposition by hand, we have two options:
+# Mimic this workaround that we're doing in the code: transpose the matrix, and then do a Hermite decomposition as demonstrated above: augment to the right and perform row operations;
+# Augment the matrix to the ''bottom'', and then use elementary column operations instead of elementary row operations (such that it looks more similar to the process for computing the null-space by hand).
-Because column-style Hermite decomposition is
+Here, we'll be demonstrating the process using the first option, because we might as well follow the same approach as the code unless we have a compelling reason not to. And we don't! If we were to follow the second option — rotating everything 90 degrees — we'd have to rewire our brains to recognize matrices in HNF but rotated 90 degrees, which is certainly harder than just transposing a matrix 90 degrees and then treating it the same way with respect to the complexities of Hermite decomposition as we've already become accustomed to.
-By hand, because we know what we're doing, we do it a bit more simply.
+So, while it's a silly example, let's suppose we want to defactor the mapping {{vector|{{map|6 5 4}} {{map|4 -4 1}}}}. Spoiler alert: it is 11-enfactored:
-<math>\begin{array} {l} \begin{array} {r}
+<math>\left[ \begin{array} {rrr}
 & 5 & -4 \\
 & -4 & 1 \\
-\hline
+\end{array} \right]</math>
+Our first step is to transpose it:
+<math>\left[ \begin{array} {rrr}
+& 4 \\
+& -4 \\
+-4 & 1 \\
+\end{array} \right]</math>
+And now we're going to augment it to the right, so we can do the first step of the Hermite decomposition. But we're actually going to go a bit further. We're going to go ahead and augment it to the right and also augment the augmenting matrix to the bottom, because that's where we're going to perform the next step, which is the inversion. We learned inversion using augmentation to the right, but remember: everything we're doing here is transposed! So augmenting to the bottom is the correct thing to do there. When we're all done we'll transpose one more time to undo it.
+<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
+& 4 \\
+& -4 \\
+-4 & 1 \\
+\end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
 & 0 & 0 \\
 & 1 & 0 \\
 & 0 & 1 \\
+\hline
-\end{array} & \rule[-16mm]{0.375mm}{20mm} & \begin{array} {r} \\ \\
 & 0 & 0 \\
 & 1 & 0 \\
 & 0 & 1 \\
-\end{array} \end{array}</math>
+\end{array} \right] \end{array} </math>
 I think that the fact that you're not allowed to divide is equivalent to the fact that at every step along the way, the augmented matrix remains unimodular