Defactoring: Difference between revisions

Line 287:

<nowiki>hermiteUnimodular[m_]:=Transpose[First[HermiteDecomposition[Transpose[m]]]]

~~columnEchelonDefactor~~[m_]:=Take[Inverse[hermiteUnimodular[m]],MatrixRank[m]]</nowiki>

columnHermiteDefactor[m_]:=Take[Inverse[hermiteUnimodular[m]],MatrixRank[m]]</nowiki>

So this implementation begins by ~~transposing~~ the matrix~~, so that when it then performs the~~ Hermite ~~Decomposition,~~ it ~~is doing~~ a column decomposition. ~~We then take~~ the unimodular matrix ~~from~~ the ~~decomposition using~~ <code>First[]</code>~~, and~~ <code>Transpose[]</code> it to in effect undo the transposition we did at the beginning.

So this implementation begins by finding the unimodular matrix from a column Hermite decomposition. To make it a column Hermite decomposition, we first transpose the matrix. The decomposition in Wolfram returns two items - the unimodular matrix, and the input matrix in Hermite normal form, in that order — and in this case we actually want the unimodular matrix. So we take that with <code>First[]</code>. Then we <code>Transpose[]</code> it to in effect undo the transposition we did at the beginning.

The next step is to invert that matrix, which is doable because it is unimodular; a key property of unimodular matrices is that they are always invertible, and because their determinant is ±1, if they contain all integer entries, their inverse will also contain all integer entries (which it does, and we need it to).

Finally we take only the top <span><math>r</math></span> rows of this, where <span><math>r</math></span> is the rank of the original matrix. That's found with <code>MatrixRank[m]</code>.

==== why it works ====

The basic idea is that the column Hermite decomposition leaves any common row factor the mapping might have had in the HNF part, while preserving in the unimodular part everything that's still meaningful about how the mapping works. So that's why we throw the column HNF away and keep the unimodular part. The rest of the algorithm is basically just "undoing" stuff so we get back to the structure of the matrix that we input.

So inverting is one of those "undo" type operations. To understand why, we have to understand the nature of this decomposition. What the Hermite decomposition does is return a unimodular matrix U and a Hermite normal form matrix H such that if you left-multiply your original matrix A by the unimodular matrix U you get the normal form matrix H, or in other words, UA = H. So, think of it this way. If A is what we input, and we want something sort of like A, but U is what we've taken, and U is multiplied with A in this equality to get H, where H is also kind of like A, then probably what we really want is something like U, but inverted.

Finally, we take only the top <span><math>r</math></span> rows, which again is an "undo" type operation. Here what we're undoing is that we had to graduate from a rectangle to a square temporarily, storing our important information in the form of this invertible square unimodular matrix temporarily, so we could invert it while keeping it integer, but now we need to get it back into the same type of rectangular shape as we put in. So that's what this part is for.<ref>There is probably some special meaning or information in the rows you throw away here, but we're not sure what it might be.</ref>

==== by hand ====

Line 296:

Line 308:

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

### mw-collapsed

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

In the Wolfram Language algorithm described above, the matrix is first transposed and then Hermite decomposed. By hand, we do it a bit more simply.

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

6 & 5 & -4 \\

4 & -4 & 1 \\

\hline

1 & 0 & 0 \\

0 & 1 & 0 \\

0 & 0 & 1 \\

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

1 & 0 & 0 \\

0 & 1 & 0 \\

0 & 0 & 1 \\

\end{array} \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

</div>

@@ Line 287: / Line 287: @@
   <nowiki>hermiteUnimodular[m_]:=Transpose[First[HermiteDecomposition[Transpose[m]]]]
-columnEchelonDefactor[m_]:=Take[Inverse[hermiteUnimodular[m]],MatrixRank[m]]</nowiki>
+columnHermiteDefactor[m_]:=Take[Inverse[hermiteUnimodular[m]],MatrixRank[m]]</nowiki>
-So this implementation begins by transposing the matrix, so that when it then performs the Hermite Decomposition, it is doing a column decomposition. We then take the unimodular matrix from the decomposition using <code>First[]</code>, and <code>Transpose[]</code> it to in effect undo the transposition we did at the beginning.
+So this implementation begins by finding the unimodular matrix from a column Hermite decomposition. To make it a column Hermite decomposition, we first transpose the matrix. The decomposition in Wolfram returns two items - the unimodular matrix, and the input matrix in Hermite normal form, in that order — and in this case we actually want the unimodular matrix. So we take that with <code>First[]</code>. Then we <code>Transpose[]</code> it to in effect undo the transposition we did at the beginning.
+The next step is to invert that matrix, which is doable because it is unimodular; a key property of unimodular matrices is that they are always invertible, and because their determinant is ±1, if they contain all integer entries, their inverse will also contain all integer entries (which it does, and we need it to).
+Finally we take only the top <span><math>r</math></span> rows of this, where <span><math>r</math></span> is the rank of the original matrix. That's found with <code>MatrixRank[m]</code>.
+==== why it works ====
+The basic idea is that the column Hermite decomposition leaves any common row factor the mapping might have had in the HNF part, while preserving in the unimodular part everything that's still meaningful about how the mapping works. So that's why we throw the column HNF away and keep the unimodular part. The rest of the algorithm is basically just "undoing" stuff so we get back to the structure of the matrix that we input.
+So inverting is one of those "undo" type operations. To understand why, we have to understand the nature of this decomposition. What the Hermite decomposition does is return a unimodular matrix U and a Hermite normal form matrix H such that if you left-multiply your original matrix A by the unimodular matrix U you get the normal form matrix H, or in other words, UA = H. So, think of it this way. If A is what we input, and we want something sort of like A, but U is what we've taken, and U is multiplied with A in this equality to get H, where H is also kind of like A, then probably what we really want is something like U, but inverted.
+Finally, we take only the top <span><math>r</math></span> rows, which again is an "undo" type operation. Here what we're undoing is that we had to graduate from a rectangle to a square temporarily, storing our important information in the form of this invertible square unimodular matrix temporarily, so we could invert it while keeping it integer, but now we need to get it back into the same type of rectangular shape as we put in. So that's what this part is for.<ref>There is probably some special meaning or information in the rows you throw away here, but we're not sure what it might be.</ref>
 ==== by hand ====
@@ Line 296: / Line 308: @@
 This is pretty long so I've put it in a collapsible section. Just click "expand" if you're interested:
-<div class="mw-collapsible mw-collapsed">
+### mw-collapsed
+<div class="mw-collapsible">
+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
+In the Wolfram Language algorithm described above, the matrix is first transposed and then Hermite decomposed. By hand, we do it a bit more simply.
+<math>\begin{array} {l} \begin{array} {r}
+& 5 & -4 \\
+& -4 & 1 \\
+\hline
+& 0 & 0 \\
+& 1 & 0 \\
+& 0 & 1 \\
+\end{array} & \rule[-16mm]{0.375mm}{20mm} & \begin{array} {r} \\ \\
+& 0 & 0 \\
+& 1 & 0 \\
+& 0 & 1 \\
+\end{array} \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
 </div>