Xenharmonic Wiki

Defactoring: Difference between revisions

← Older editNewer edit →
VisualWikitext
Cmloegcmluin (talk | contribs)
autopatrolled, emailconfirmed
5,160 edits
Cmloegcmluin (talk | contribs)
autopatrolled, emailconfirmed
5,160 edits
Line 582: Line 582:


<math>\left[ \begin{array} {rrr}
<math>\left[ \begin{array} {rrr}
6 & 5 & -4 \\
6 & 5 & -4 \\
4 & -4 & 1 \\
4 & -4 & 1 \\
\end{array} \right]</math>
\end{array} \right]</math>


Line 591: Line 589:


<math>\left[ \begin{array} {rrr}
<math>\left[ \begin{array} {rrr}
6 & 4 \\
6 & 4 \\
5 & -4 \\
5 & -4 \\
-4 & 1 \\
-4 & 1 \\
\end{array} \right]</math>
\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.
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}
<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
6 & 4 \\
6 & 4 \\
5 & -4 \\
5 & -4 \\
-4 & 1 \\
-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
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array} \right] \end{array} </math>
Alright. So our first goal is to get the top-left matrix into HNF. Let's subtract the 2nd row from the 1st row — that will get us a 1 in the top-left entry, which is what we want if we can.


<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
1 & 8 \\
5 & -4 \\
-4 & 1 \\
\end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
\end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
1 & -1 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\hline
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array} \right] \end{array} </math>


Now let's subtract the 1st row from the 2nd row 5 times. That'll get us a 0 below that first pivot, which is what we need.
<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
1 & 8 \\
0 & -44 \\
-4 & 1 \\
\end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
1 & -1 & 0 \\
-5 & 6 & 0 \\
0 & 0 & 1 \\
\hline
1 & 0 & 0 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1 \\
\end{array} \right] \end{array} </math>
Now let's add the 1st row to the 3rd row 4 times. That'll allow us to achieve all 0's below the first pivot.
<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
1 & 8 \\
0 & -44 \\
0 & 33 \\
\end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
1 & -1 & 0 \\
-5 & 6 & 0 \\
4 & -4 & 1 \\
\hline
\hline
1 & 0 & 0 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1 \\
\end{array} \right] \end{array} </math>
Now let's add the 3rd row to the 2nd row. We can see that if we do that, we'll simplify their relationship. If it's not clear now, it'll be clear in the next step.
<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
1 & 8 \\
0 & -11 \\
0 & 33 \\
\end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
1 & -1 & 0 \\
-1 & 2 & 1 \\
4 & -4 & 1 \\
\hline
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array} \right] \end{array} </math>
So now we can add the 2nd row to the 3rd row 3 times, and that'll get the entry below the 2nd pivot to be 0.
<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
1 & 8 \\
0 & -11 \\
0 & 0 \\
\end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
1 & -1 & 0 \\
-1 & 2 & 1 \\
1 & 2 & 4 \\
\hline
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array} \right] \end{array} </math>
We can flip the signs of the second row, because we need pivots to be positive.
<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
1 & 8 \\
0 & 11 \\
0 & 0 \\
\end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
1 & -1 & 0 \\
1 & -2 & -1 \\
1 & 2 & 4 \\
\hline
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array} \right] \end{array} </math>
And we've completed the first step! The original matrix is now in HNF. So the next step is to take the other matrix we've been working on — the unimodular one from the Hermite decomposition — and invert it. Again, since we're in a transposed state, we're going to do the by-hand inversion technique, but to the bottom using elementary column operations rather than to the right using elementary row operations.
For our first step, let's add the 1st column to the 2nd column. That will get us a 0 in the top-center entry. Remember, we're trying to get the top-right matrix to look like an identity matrix.
<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
1 & 8 \\
0 & 11 \\
0 & 0 \\
\end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
1 & 0 & 0 \\
1 & -1 & -1 \\
1 & 3 & 4 \\
\hline
1 & 1 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array} \right] \end{array} </math>
Now let's add the new 2nd column back to the 1st column. This will get the entry in the center-left to be 0.
<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
1 & 8 \\
0 & 11 \\
0 & 0 \\
\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 & -1 \\
4 & 3 & 4 \\
\hline
2 & 1 & 0 \\
1 & 1 & 0 \\
0 & 0 & 1 \\
\end{array} \right] \end{array} </math>
Now let's subtract the 2nd column from the 3rd column. This is sweet because it gets the center-right entry to be 0 as well as the bottom-right entry to be 1. A twofer! Plus it gives us our first column which has all zeros except for one row, which gives us the power to affect the entry in that row of other columns without messing up any of the other rows of those columns.
<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
1 & 8 \\
0 & 11 \\
0 & 0 \\
\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 \\
4 & 3 & 1 \\
\hline
2 & 1 & -1 \\
1 & 1 & -1 \\
0 & 0 & 1 \\
\end{array} \right] \end{array} </math>


Okay. So if we now subtract the 3rd column from the 1st column 4 times, we can get the bottom-left entry to be a 0.
<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
1 & 8 \\
0 & 11 \\
0 & 0 \\
\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 & 3 & 1 \\
\hline
6 & 1 & -1 \\
5 & 1 & -1 \\
-4 & 0 & 1 \\
\end{array} \right] \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
And now we can subtract the 3rd column from the 2nd column 3 times, so we can get the bottom-center entry to be a 0.
 
<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
1 & 8 \\
0 & 11 \\
0 & 0 \\
\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
6 & 4 & -1 \\
5 & 4 & -1 \\
-4 & -3 & 1 \\
\end{array} \right] \end{array} </math>
 
As our last step to achieve an identity matrix in the top-right matrix, let's just flip the signs of the 2nd column:
 
<math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
1 & 8 \\
0 & 11 \\
0 & 0 \\
\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
6 & -4 & -1 \\
5 & -4 & -1 \\
-4 & 3 & 1 \\
\end{array} \right] \end{array} </math>
 
And so we've inverted the Hermite unimodular matrix. That's our result in the bottom-right matrix, isolated here:
 
<math>\left[ \begin{array} {rrr}
6 & -4 & -1 \\
5 & -4 & -1 \\
-4 & 3 & 1 \\
\end{array} \right]</math>
 
But we're not quite to our defactored result. We're very close though! All we've got to do now is take that result and transpose it, to get us out of the transposed state we've been in (in other words, flip every entry across the main diagonal, running from the top-left entry to the bottom-right entry):
 
<math>\left[ \begin{array} {rrr}
6 & 5 & -4 \\
-4 & -4 & 3 \\
-1 & -1 & 1 \\
\end{array} \right]</math>
 
And we take from this thing the top <span><math>r</math></span> rows, where <span><math>r</math></span> is the rank of the input matrix, which in this case is 2:
 
<math>\left[ \begin{array} {rrr}
6 & 5 & -4 \\
-4 & -4 & 3 \\
\end{array} \right]</math>
 
And that's all there is to defactoring!
 
Note that this is not yet the canonical form. Remember that to achieve canonical form, we still have to take this result and get it into HNF. We won't work through that here, though if you'd like to practice by-hand Hermite decomposition, this would be a perfect example to try it on! The result you should end up with is {{vector|{{map|2 1 -1}} {{map|0 2 -1}}}}.
 
But what have we accomplished here, really? You may well feel underwhelmed by this matrix's transformation from {{vector|{{map|6 5 -4}} {{map|4 -4 1}}}} to {{vector|{{map|6 5 -4}} {{map|-4 -4 3}}}}. It seems barely to have even changed!
 
Well, the difference becomes clearer when we compare the HNF of the original matrix, which is {{vector|{{map|2 9 -5}} {{map|0 22 -11}}}}, a clearly 11-enfactored mapping. One thing that's cool about performing this defactoring process by hand is that you can clearly see any common factor that you've removed as a result: all you have to do is look at the pivots of the HNF of the original matrix that you left behind, which in this case was:
 
<math>\left[ \begin{array} {rrr}
1 & 8 \\
0 & 11 \\
0 & 0 \\
\end{array} \right]</math>


</div>
The pivots are 1 and 11, so that 11 tells us that we had a common factor of 11. You could say that the HNF is useful for identifying common factors, but not for removing them. But if you leave them behind in the column-style HNF, the information that is retained in the unimodular matrix which is the other product of the Hermite decomposition, is enough to preserve everything important about the temperament, to get you back to where you started via an inverse and a trimming of extraneous rows.


== other details to report ==
== other details to report ==
Retrieved from "https://en.xen.wiki/w/Defactoring"