Defactoring algorithms: Difference between revisions

Line 290:

==== By hand ====

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

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

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

#Hermite decomposition

# Hermite decomposition

# inversion

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.

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

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 nullspace of a mapping by hand (as demonstrated [[~~Douglas_Blumeyer~~%~~27s_RTT_How-To~~#Nullspace~~|here~~]]):

Fortunately, both of these two processes can be done using a technique you may already be familiar with if you have learned how to calculate the nullspace of a mapping by hand (as demonstrated in [[Dave Keenan %26 Douglas Blumeyer%27s guide to RTT: exploring temperaments #Nullspace]]):

#augmenting your matrix with an identity matrix

# augmenting your matrix with an identity matrix

# performing elementary row or column operations until a desired state is achieved<ref>For convenience, here is a summary of the three different techniques and their targets:<br>

*nullspace: augment to the bottom, go until you get columns with all zeros.

* nullspace: augment to the bottom, go until you get columns with all zeros.

*Hermite: augment to the right, go until echelon form.

* Hermite: augment to the right, go until echelon form.

*inverse: augment to the right, go until identity matrix.

* inverse: augment to the right, go until identity matrix.

</ref>

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

Let's do a Hermite decomposition example first. We begin with the mapping for the temperament 12&26bbb, which looks like {{rket|{{map|12 19 28}} {{map|26 43 60}}}}, or as a matrix:

{{Databox|Hermite decomposition tutorial|

Let us do a Hermite decomposition example first. We begin with the mapping for the temperament 12 & 26bbb, which looks like {{rket| {{map| 12 19 28 }} {{map| 26 43 60 }} }}, or as a matrix:

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

Line 333:

Line 334:

Now we begin applying elementary row operations until the part on the left is in Hermite Normal Form. If you need to review the definition of HNF and its constraints, you can find more detail [[matrix echelon forms#HNF|here]]. The quick and dirty is:

#all pivots > 0

# all pivots > 0

# all entries in pivot columns below the pivots = 0

# all entries in pivot columns below the pivots {{=}} 0

#all entries in pivot columns above the pivots ≥ 0 and strictly less than the pivot

# all entries in pivot columns above the pivots ≥ 0 and strictly less than the pivot

One special thing about computing the HNF is that we're not allowed to use all elementary operations; in particular we're not allowed to multiply (or divide) rows. Our main technique, then, will be adding or subtract rows from each other. This, of course, includes adding or subtracting ''multiples'' of rows from each other, because doing so is equivalent to performing those additions or subtractions one at a time (note that adding or subtracting ''multiples'' of rows from each other is significantly different than simply ''multiplying'' a row by itself).<ref>The fact that you're not allowed to multiply or divide is equivalent to the fact that at every step along the way, the augmented matrix remains unimodular.</ref>

Line 402:

Line 403:

#'''all pivots > 0?''' Check. The 1st row's pivot is 2 and the 2nd row's pivot is 11.

#'''all entries in pivot columns below the pivots = 0'''? Check. This only applies to one entry — the bottom right one, below the 1st row's pivot — but it is indeed 0.

#'''all entries in pivot columns below the pivots {{=}} 0'''? Check. This only applies to one entry — the bottom right one, below the 1st row's pivot — but it is indeed 0.

#'''all entries in pivot columns above the pivots ≥ 0 and strictly less than the pivot'''? Check. Again, this only applies to one entry — the center top one, above the 2nd row's pivot of 11 — but it is 5, and 5 is indeed non-negative and < 11.

Line 435:

Line 436:

26 & 43 & 60 \\

\end{array} \right] & = & \left[ \begin{array} {r}

\end{array} \right] & {{=}} & \left[ \begin{array} {r}

2 & 5 & 4 \\

Line 443:

Line 444:

And that's all there is to the Hermite decomposition.

}}

===== Inversion by hand =====

{{Databox|Inversion tutorial|

Now let's take a look at how to do inversion by hand. The first thing to note is that this process only works for rectangular matrices. So you will not be using on non-trivial mappings or comma bases directly. But, as you know, there is a useful application for this process on the unimodular matrix which is the other result of the Hermite decomposition than the HNF, and unimodular matrices are always square.

Line 558:

Line 561:

\end{array} </math>

~~I chose this~~ matrix specifically to demonstrate the importance of the unimodularity of the other matrix produced by the Hermite decomposition. A unimodular matrix is defined by having a determinant of ±1. And what does this have to do with inverses? Well, take a look at the determinant of our original matrix here, {{rket|{{map|3 -2 4}} {{map|1 0 2}} {{map|0 1 0}}}}. It's 2. The determinant of an invertible matrix will tell you what the LCM of all the denominators in the inverse will be.<ref>If you're familiar with the formula for the Moore-Penrose inverse of rectangular matrices, you may recognize this fact as akin to how you multiply the outside of the pseudoinverse by the reciprocal of the determinant of the matrix.</ref><ref>This may also shed some light on the fact that the only square matrices that are not invertible are those with determinants equal to 0.</ref> And so, the fact that the other matrix produced by the Hermite decomposition is unimodular means that not only is it invertible, if it has only integer terms (which it will, being involved in HNF), then its inverse will also have only integer terms. And this is important because the inverse of a Hermite unimodular matrix is just one step away from the defactored form of an input matrix.

This matrix is chosen specifically to demonstrate the importance of the unimodularity of the other matrix produced by the Hermite decomposition. A unimodular matrix is defined by having a determinant of ±1. And what does this have to do with inverses? Well, take a look at the determinant of our original matrix here, {{rket|{{map|3 -2 4}} {{map|1 0 2}} {{map|0 1 0}}}}. It's 2. The determinant of an invertible matrix will tell you what the LCM of all the denominators in the inverse will be.<ref>If you're familiar with the formula for the Moore-Penrose inverse of rectangular matrices, you may recognize this fact as akin to how you multiply the outside of the pseudoinverse by the reciprocal of the determinant of the matrix.</ref><ref>This may also shed some light on the fact that the only square matrices that are not invertible are those with determinants equal to 0.</ref> And so, the fact that the other matrix produced by the Hermite decomposition is unimodular means that not only is it invertible, if it has only integer terms (which it will, being involved in HNF), then its inverse will also have only integer terms. And this is important because the inverse of a Hermite unimodular matrix is just one step away from the defactored form of an input matrix.

}}

===== Putting it all together =====

{{Databox|Defactoring tutorial|

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.

Line 833:

Line 837:

The pivots are 1 and 11, so that 11 tells us that we had a common factor of 11<ref>In the doubly-enfactored case of {{rket|{{map|17 16 -4}} {{map|4 -4 1}}}}, i.e. with a common factor of 33 = 3 × 11, the two pivots of the HNF are 3 and 11, putting each of them on display separately.</ref><ref>It's interesting to observe that while the 11-enfactoring can be observed in the original matrix as a linear combination of 2 of the 1st row with -3 of the 2nd row, i.e. 2{{map|6 5 -4}} + -3{{map|4 -4 1}} = {{map|0 22 -11}}, the linear combination of ''columns'', i.e. slicing the original {{rket|{{map|6 5 -4}} {{map|4 -4 1}}}} mapping the other direction like {{rbra|{{vector|6 4}} {{vector|5 -4}} {{vector|-4 1}}}}, that leads to the revelation of this 11 is completely different: -1{{vector|6 4}} + 2{{vector|5 -4}} + 1{{vector|-4 1}} = {{vector|0 11}}.</ref>. 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.

}}

== Development ==

@@ Line 290: / Line 290: @@
 ==== By hand ====
-In an effort to demystify the effects of column Hermite defactoring, let's walk though an example manually.
+In an effort to demystify the effects of column Hermite defactoring, let us walk though an example manually.
 First we need to learn how to perform its two building blocks by hand:
-#Hermite decomposition
+# Hermite decomposition
 # inversion
-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.
+After we know how to do these two things individually, we will learn how to tweak them and assemble them together in order to perform a complete column Hermite defactoring.
-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 nullspace of a mapping by hand (as demonstrated [[Douglas_Blumeyer%27s_RTT_How-To#Nullspace|here]]):
+Fortunately, both of these two processes can be done using a technique you may already be familiar with if you have learned how to calculate the nullspace of a mapping by hand (as demonstrated in [[Dave Keenan %26 Douglas Blumeyer%27s guide to RTT: exploring temperaments #Nullspace]]):
-#augmenting your matrix with an identity matrix
+# augmenting your matrix with an identity matrix
 # performing elementary row or column operations until a desired state is achieved<ref>For convenience, here is a summary of the three different techniques and their targets:<br>
-*nullspace: augment to the bottom, go until you get columns with all zeros.
+* nullspace: augment to the bottom, go until you get columns with all zeros.
-*Hermite: augment to the right, go until echelon form.
+* Hermite: augment to the right, go until echelon form.
-*inverse: augment to the right, go until identity matrix.
+* inverse: augment to the right, go until identity matrix.
 </ref>
 ===== Hermite decomposition by hand =====
-Let's do a Hermite decomposition example first. We begin with the mapping for the temperament 12&26bbb, which looks like {{rket|{{map|12 19 28}} {{map|26 43 60}}}}, or as a matrix:
+{{Databox|Hermite decomposition tutorial|
+Let us do a Hermite decomposition example first. We begin with the mapping for the temperament 12 & 26bbb, which looks like {{rket| {{map| 12 19 28 }} {{map| 26 43 60 }} }}, or as a matrix:
 <math>\left[ \begin{array} {rrr}
@@ Line 333: / Line 334: @@
 Now we begin applying elementary row operations until the part on the left is in Hermite Normal Form. If you need to review the definition of HNF and its constraints, you can find more detail [[matrix echelon forms#HNF|here]]. The quick and dirty is:
-#all pivots > 0
+# all pivots > 0
-# all entries in pivot columns below the pivots = 0
+# all entries in pivot columns below the pivots {{=}} 0
-#all entries in pivot columns above the pivots ≥ 0 and strictly less than the pivot
+# all entries in pivot columns above the pivots ≥ 0 and strictly less than the pivot
 One special thing about computing the HNF is that we're not allowed to use all elementary operations; in particular we're not allowed to multiply (or divide) rows. Our main technique, then, will be adding or subtract rows from each other. This, of course, includes adding or subtracting ''multiples'' of rows from each other, because doing so is equivalent to performing those additions or subtractions one at a time (note that adding or subtracting ''multiples'' of rows from each other is significantly different than simply ''multiplying'' a row by itself).<ref>The fact that you're not allowed to multiply or divide is equivalent to the fact that at every step along the way, the augmented matrix remains unimodular.</ref>
@@ Line 402: / Line 403: @@
 #'''all pivots > 0?''' Check. The 1st row's pivot is 2 and the 2nd row's pivot is 11.
-#'''all entries in pivot columns below the pivots = 0'''? Check. This only applies to one entry — the bottom right one, below the 1st row's pivot — but it is indeed 0.
+#'''all entries in pivot columns below the pivots {{=}} 0'''? Check. This only applies to one entry — the bottom right one, below the 1st row's pivot — but it is indeed 0.
 #'''all entries in pivot columns above the pivots ≥ 0 and strictly less than the pivot'''? Check. Again, this only applies to one entry — the center top one, above the 2nd row's pivot of 11 — but it is 5, and 5 is indeed non-negative and < 11.
@@ Line 435: / Line 436: @@
 & 43 & 60 \\
-\end{array} \right] & = & \left[ \begin{array} {r}
+\end{array} \right] & {{=}} & \left[ \begin{array} {r}
 & 5 & 4 \\
@@ Line 443: / Line 444: @@
 And that's all there is to the Hermite decomposition.
+}}
 ===== Inversion by hand =====
+{{Databox|Inversion tutorial|
 Now let's take a look at how to do inversion by hand. The first thing to note is that this process only works for rectangular matrices. So you will not be using on non-trivial mappings or comma bases directly. But, as you know, there is a useful application for this process on the unimodular matrix which is the other result of the Hermite decomposition than the HNF, and unimodular matrices are always square.
@@ Line 558: / Line 561: @@
 \end{array} </math>
-I chose this matrix specifically to demonstrate the importance of the unimodularity of the other matrix produced by the Hermite decomposition. A unimodular matrix is defined by having a determinant of ±1. And what does this have to do with inverses? Well, take a look at the determinant of our original matrix here, {{rket|{{map|3 -2 4}} {{map|1 0 2}} {{map|0 1 0}}}}. It's 2. The determinant of an invertible matrix will tell you what the LCM of all the denominators in the inverse will be.<ref>If you're familiar with the formula for the Moore-Penrose inverse of rectangular matrices, you may recognize this fact as akin to how you multiply the outside of the pseudoinverse by the reciprocal of the determinant of the matrix.</ref><ref>This may also shed some light on the fact that the only square matrices that are not invertible are those with determinants equal to 0.</ref> And so, the fact that the other matrix produced by the Hermite decomposition is unimodular means that not only is it invertible, if it has only integer terms (which it will, being involved in HNF), then its inverse will also have only integer terms. And this is important because the inverse of a Hermite unimodular matrix is just one step away from the defactored form of an input matrix.
+This matrix is chosen specifically to demonstrate the importance of the unimodularity of the other matrix produced by the Hermite decomposition. A unimodular matrix is defined by having a determinant of ±1. And what does this have to do with inverses? Well, take a look at the determinant of our original matrix here, {{rket|{{map|3 -2 4}} {{map|1 0 2}} {{map|0 1 0}}}}. It's 2. The determinant of an invertible matrix will tell you what the LCM of all the denominators in the inverse will be.<ref>If you're familiar with the formula for the Moore-Penrose inverse of rectangular matrices, you may recognize this fact as akin to how you multiply the outside of the pseudoinverse by the reciprocal of the determinant of the matrix.</ref><ref>This may also shed some light on the fact that the only square matrices that are not invertible are those with determinants equal to 0.</ref> And so, the fact that the other matrix produced by the Hermite decomposition is unimodular means that not only is it invertible, if it has only integer terms (which it will, being involved in HNF), then its inverse will also have only integer terms. And this is important because the inverse of a Hermite unimodular matrix is just one step away from the defactored form of an input matrix.
+}}
 ===== Putting it all together =====
+{{Databox|Defactoring tutorial|
 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.
@@ Line 833: / Line 837: @@
 The pivots are 1 and 11, so that 11 tells us that we had a common factor of 11<ref>In the doubly-enfactored case of {{rket|{{map|17 16 -4}} {{map|4 -4 1}}}}, i.e. with a common factor of 33 = 3 × 11, the two pivots of the HNF are 3 and 11, putting each of them on display separately.</ref><ref>It's interesting to observe that while the 11-enfactoring can be observed in the original matrix as a linear combination of 2 of the 1st row with -3 of the 2nd row, i.e. 2{{map|6 5 -4}} + -3{{map|4 -4 1}} = {{map|0 22 -11}}, the linear combination of ''columns'', i.e. slicing the original {{rket|{{map|6 5 -4}} {{map|4 -4 1}}}} mapping the other direction like {{rbra|{{vector|6 4}} {{vector|5 -4}} {{vector|-4 1}}}}, that leads to the revelation of this 11 is completely different: -1{{vector|6 4}} + 2{{vector|5 -4}} + 1{{vector|-4 1}} = {{vector|0 11}}.</ref>. 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.
+}}
 == Development ==