Defactoring algorithms: Difference between revisions

(16 intermediate revisions by 6 users not shown)

Line 1:

{{Todo|inline=1| rework |text=Try explaining without wedgies outside historical notes.}}

This article discusses how to identify [[enfactoring]] in [[regular temperament]] [[mapping]]s and then [[defactoring|defactor]] it.

Line 183:

Line 185:

<math>\displaystyle (U^{-1})_{1:r}</math>

where hnf is the column-style Hermite normal form, and ~~{{nowrap|~~1:''r''}} is taking the first ''r'' rows.

where hnf is the column-style Hermite normal form, and 1:''r'' is taking the first ''r'' rows.

Here is an implementation in Python (with SciPy and SymPy):

Line 210:

Line 212:

So this implementation begins by finding the unimodular matrix from a column Hermite decomposition. Note that the <code>HermiteDecomposition[]</code> is only available in row-style, so we first transpose the matrix to convert it to column-style. 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 transpose it again 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)<ref group="note">Interesting tidbit regarding [[full-rank]] matrices and unimodular matrices: for square matrices, unimodularity implies full-rank, and while full-rank does not imply unimodularity, it does imply a non-zero determinant.</ref>.

Finally we take only the top ''r'' rows of this. That is found with <code>MatrixRank[m]</code>.

Line 236:

Line 238:

===== Proof of why column Hermite defactoring (and Pernet-Stein defactoring) work =====

The following proof is adapted primarily from Tom Price's thinking:

# The input matrix is an ~~m×n~~ matrix A.

# The input matrix is an ''m''×''n'' matrix A.

# It decomposes into a slightly bigger and square ~~{{nowrap|~~(''n'' &~~times~~; ''n'')}} unimodular matrix U and another ~~m×n~~ matrix which is not exactly A in HNF (because we only have to use unimodular operations so far as to get all the all-zero columns off to one side of A; we don't need to satisfy all of the conventional constraints of HNF), but we'll still call it H. The unimodular matrix is a transformation from A into H, so, {{nowrap|AU {{=}} H}}.

# It decomposes into a slightly bigger and square (''n''×''n'') unimodular matrix U and another ''m''×''n'' matrix which is not exactly A in HNF (because we only have to use unimodular operations so far as to get all the all-zero columns off to one side of A; we don't need to satisfy all of the conventional constraints of HNF), but we'll still call it H. The unimodular matrix is a transformation from A into H, so, {{nowrap|AU {{=}} H}}.

# If we were to actually slice off the all-zero cols we've isolated in H, we'd end up with a slightly smaller and square (~~m×m~~) matrix. So let's call this little square matrix S (this is our "[[Defactoring algorithms#Finding the greatest factor|greatest factor matrix]]", because its determinant is the greatest factor of A).

# If we were to actually slice off the all-zero cols we've isolated in H, we'd end up with a slightly smaller and square (''m''×''m'') matrix. So let's call this little square matrix S (this is our "[[Defactoring algorithms#Finding the greatest factor|greatest factor matrix]]", because its determinant is the greatest factor of A).

# We can left-multiply both sides of our equation by the inverse of S (S{{inv}}) and right-multiply both sides of our equation by the inverse of U (U{{inv}}) to get {{nowrap|S{{inv}}AUU{{inv}} {{=}} S{{inv}}HU{{inv}}}}. The U's cancel out on the left so we end up with {{nowrap|S{{inv}}A {{=}} S{{inv}}HU{{inv}}}}. At first glance we don't seem to have gained any further insight. But there's more we can do from here.

# Because H is just S with a bunch of 0 cols appended, S{{inv}}H is just the identity matrix with a bunch of zero columns appended, in other words it is a truncated identity matrix. We could call that T, and now we have {{nowrap|S{{inv}}A {{=}} TU{{inv}}}}.

# Multiplying U{{inv}} on the left by a truncated identity matrix is the same as truncating ~~U⁻¹~~. That's how we think of the output of column Hermite defactoring—our supposedly defactored matrix—so let's call that D. We now have {{nowrap|S{{inv}}A {{=}} D}}. (This is how we can see that the Pernet-Stein method of multiplying the input matrix by a transformation matrix that is a truncated and inversed column Hermite normal form of the input is equivalent to our column Hermite method, which takes the other route to the same result: inverting and truncating the unimodular result of the Hermite decomposition.)

# Multiplying U{{inv}} on the left by a truncated identity matrix is the same as truncating U{{inv}}. That's how we think of the output of column Hermite defactoring—our supposedly defactored matrix—so let's call that D. We now have {{nowrap|S{{inv}}A {{=}} D}}. (This is how we can see that the Pernet-Stein method of multiplying the input matrix by a transformation matrix that is a truncated and inversed column Hermite normal form of the input is equivalent to our column Hermite method, which takes the other route to the same result: inverting and truncating the unimodular result of the Hermite decomposition.)

# We need to prove now that D has three qualities:

:: a) It's defactored,

:: b) It still represents the same temperament (i.e. it has the same nullspace as A), and

:: c) It's integer.

:: c) It's an integer.

# Proving (a) is easy. It's defactored because U was unimodular. U's determinant was 1, and neither inverting it nor truncating it would change that. Alternatively, we can prove this by showing how on the other side of the equation, S{{inv}}A is surjective as a function on lattice points (in other words, there's no points in the tempered lattice that JI lattice points don't map to). We begin with the fact that H has the same image as A, because right-multiplication with a unimodular matrix such as U doesn't change the image. Then S has the same image as H, too, and therefore the same image as A, because removing the all-zero columns doesn't change the image either. Now that we've established this, we can assert that ~~S⁻¹A~~ is surjective by describing a lattice point x such that {{nowrap|y {{=}} S{{inv}}Ax}} for any given lattice point y. And because S and A have the same image, we know that {{nowrap|Sy {{=}} Ax}}, and therefore {{nowrap|y {{=}} S{{inv}}Ax}}.

# Proving (a) is easy. It's defactored because U was unimodular. U's determinant was 1, and neither inverting it nor truncating it would change that. Alternatively, we can prove this by showing how on the other side of the equation, S{{inv}}A is surjective as a function on lattice points (in other words, there's no points in the tempered lattice that JI lattice points don't map to). We begin with the fact that H has the same image as A, because right-multiplication with a unimodular matrix such as U doesn't change the image. Then S has the same image as H, too, and therefore the same image as A, because removing the all-zero columns doesn't change the image either. Now that we've established this, we can assert that S{{inv}}A is surjective by describing a lattice point ''x'' such that {{nowrap|''y'' {{=}} S{{inv}}A''x''}} for any given lattice point ''y''. And because S and A have the same image, we know that {{nowrap|S''y'' {{=}} A''x''}}, and therefore {{nowrap|''y'' {{=}} S{{inv}}A''x''}}.

# Proving (b) is even easier. Multiplying any matrix with an invertible matrix on the left keeps the nullspace the same. S{{inv}} is clearly invertible, being itself the inverse of S. A way to understand this is: a non-invertible matrix is the same as a singular matrix, i.e. one whose determinant is 0. So as long as you don't wipe things out by essentially multiplying by 0, the nullspace information is preserved, just scaled.

# Proving (c) is a bit trickier, because S{{inv}} is not necessarily an integer matrix. But can show that S{{inv}}A is an integer matrix by showing that it maps lattice points to lattice points. Suppose we have that same equation from the proof of (a), namely that {{nowrap|y {{=}} S{{inv}}Ax}}, where x is a lattice point. We want to show that y is a lattice point. Again, since A and S have the same image (when considered as functions on lattice points), there must be some lattice point z with {{nowrap|Sz {{=}} Ax}}. But we also know that Sy = Ax. Since S is invertible, and therefore injective, {{nowrap|y {{=}} z}}, so y is a lattice point.

# Proving (c) is a bit trickier, because S{{inv}} is not necessarily an integer matrix. But can show that S{{inv}}A is an integer matrix by showing that it maps lattice points to lattice points. Suppose we have that same equation from the proof of (a), namely that {{nowrap|''y'' {{=}} S{{inv}}A''x''}}, where ''x'' is a lattice point. We want to show that ''y'' is a lattice point. Again, since A and S have the same image (when considered as functions on lattice points), there must be some lattice point ''z'' with {{nowrap|S''z'' {{=}} A''x''}}. But we also know that {{nowrap|S''y'' {{=}} A''x''}}. Since S is invertible, and therefore injective, {{nowrap|''y'' {{=}} ''z''}}, so ''y'' is a lattice point.

===== Relationship with other defactoring methods =====

Line 278:

Line 280:

===== Relationship with EA =====

Another thought that might help congeal the notion of column Hermite defactoring for you is to use what you know about multimaps (AKA "wedgies"), in particular a) what they are, and b) how to defactor them. The answer to a) is that they are just the list of the largest possible minor determinants (or "largest-minors" for short) of rectangular matrices, or in other words, the closest thing rectangular matrices such as mappings have to a real determinant. And the answer to b) is that you simply divide out the GCD of the entries in this list of largest-minors. So if defactoring a list of largest-minors means dividing common factors out, then it should be little surprise that achieving a real determinant of ±1 is equivalent to defactoring, and thereby that leveraging the unimodularity of the other matrix produced by the Hermite decomposition should be valuable in this capacity.

==== By hand ====

Line 320:

Line 322:

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 &gt~~;&nbsp~~;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 &ge~~;&nbsp~~;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 group="note">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 339:

Line 341:

<math>

\left[ \begin{array} {ccc|cc}

0 & -11 & 4 & 13 & -6

0 & -11 & 4 & 13 & -6 \\

2 & 5 & 4 & -2 & 1 \\

\end{array} \right]

Line 369:

Line 371:

# '''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 507:

Line 509:

</math>

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 group="note">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 group="note">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 group="note">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 group="note">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.

}}

Line 782:

Line 784:

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

The pivots are 1 and 11, so that 11 tells us that we had a common factor of 11<ref group="note">In the doubly-enfactored case of {{rket|{{map|17 16 -4}} {{map|4 -4 1}}}}, i.e. with a common factor of {{nowrap|33 {{=}} 3 &~~times~~; 11}}, the two pivots of the HNF are 3 and 11, putting each of them on display separately.</ref><ref group="note">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.

The pivots are 1 and 11, so that 11 tells us that we had a common factor of 11<ref group="note">In the doubly-enfactored case of {{rket|{{map|17 16 -4}} {{map|4 -4 1}}}}, i.e. with a common factor of {{nowrap|33 {{=}} 3 × 11}}, the two pivots of the HNF are 3 and 11, putting each of them on display separately.</ref><ref group="note">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.

}}

Line 792:

Line 794:

<blockquote>''Since this is an invariant of the temperament, it would be a good thing to use to refer to it, but for the fact that it is opaque and does not immediately tell us how to define the temperament.''<ref group="note">[https://yahootuninggroupsultimatebackup.github.io/tuning-math/topicId_1545.html#1545 Yahoo! Tuning Group | ''Standardizing our wedge product'']</ref></blockquote>

Regarding any other advantages EA brought to the RTT table for beginners: they did not find any. The only minor advantage identified was how the largest-minors of the mapping which wedgies are a list of could also be read as a list of denominators of unit fractions of the tempered lattice which are capable of being generated by the associated combination of primes whose columns in the mapping were used in the calculation of the corresponding largest-minor (this idea is discussed in more detail [[~~Dave_Keenan_%26_Douglas_Blumeyer%27s_guide_to_EA_for_RTT~~#~~Multicomma_entries~~:~~_tempered_lattice_fractions_generated_by_prime_combinations~~|here]]). Furthermore, several disadvantages of EA were identified, the main one being that it is more challenging to learn and use, involving higher level mathematical concepts than LA.

Regarding any other advantages EA brought to the RTT table for beginners: they did not find any. The only minor advantage identified was how the largest-minors of the mapping which wedgies are a list of could also be read as a list of denominators of unit fractions of the tempered lattice which are capable of being generated by the associated combination of primes whose columns in the mapping were used in the calculation of the corresponding largest-minor (this idea is discussed in more detail [[Dave Keenan & Douglas Blumeyer's guide to EA for RTT#Multicomma entries: tempered lattice fractions generated by prime combinations|here]]). Furthermore, several disadvantages of EA were identified, the main one being that it is more challenging to learn and use, involving higher level mathematical concepts than LA.

Regarding the development of a canonical form for temperaments using only linear algebra, Dave and Douglas did manage to develop such a form, which is documented here: [[defactored Hermite form]]. It was Gene himself who first described this form (as the result of his "saturation" algorithm), so he either did not realize the full implications of his discovery, or it was simply not popularized and plugged in with the rest of the hive knowledge.

Line 812:

Line 814:

===== How it works =====

Originally Dave was inspired by what [[Paul Erlich]] wrote on [http://tonalsoft.com/enc/t/torsion.aspx the article for torsion on the Tonalsoft site]. The algorithm simply checks every possible combination of sums and differences of rows. You have to check all <~~span~~><~~math~~>~~\frac{3^r -~~ 1}{2}~~</math>~~ sums and differences where ~~<math>~~r~~</math>~~ is the rank of the mapping. For example, for a rank-3 mapping with rows {{vector|A B C}}, you would need to check

Originally Dave was inspired by what [[Paul Erlich]] wrote on [http://tonalsoft.com/enc/t/torsion.aspx the article for torsion on the Tonalsoft site]. The algorithm simply checks every possible combination of sums and differences of rows. You have to check all {{sfrac|3''r'' − 1|2}} sums and differences where ''r'' is the rank of the mapping. For example, for a rank-3 mapping with rows {{vector|A B C}}, you would need to check

* A

Line 853:

Line 855:

This is the furthest progress that was made on SAD defactor before efforts were shifted to column Hermite defactor. This implementation still exhibits problems 2 and 3; only problems 1 and 4 were solved here. Problem 3 started to be solved, but was not quite quashed.

{{Databox|~~Code~~|

{{Databox|Wolfram Language code for SAD defactoring|

<pre>

confirmEnfactoredRowReplaced[m_] := Module[{i, enfactoredRowReplaced},

Line 905:

Line 907:

[[Category:Math]]

[[Category:Pages with proofs]]

[[Category:Algorithms]]

@@ Line 1: / Line 1: @@
+{{Todo|inline=1| rework |text=Try explaining without wedgies outside historical notes.}}
 This article discusses how to identify [[enfactoring]] in [[regular temperament]] [[mapping]]s and then [[defactoring|defactor]] it.
@@ Line 183: / Line 185: @@
 <math>\displaystyle (U^{-1})_{1:r}</math>
-where hnf is the column-style Hermite normal form, and {{nowrap|1:''r''}} is taking the first ''r'' rows.
+where hnf is the column-style Hermite normal form, and 1:''r'' is taking the first ''r'' rows.
 Here is an implementation in Python (with SciPy and SymPy):
@@ Line 210: / Line 212: @@
 So this implementation begins by finding the unimodular matrix from a column Hermite decomposition. Note that the <code>HermiteDecomposition[]</code> is only available in row-style, so we first transpose the matrix to convert it to column-style. The decomposition in Wolfram returns two items&mdash;the unimodular matrix, and the input matrix in Hermite normal form, in that order&mdash;and in this case we actually want the unimodular matrix. So we take that with <code>First[]</code>. Then we transpose it again 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)<ref group="note">Interesting tidbit regarding [[full-rank]] matrices and unimodular matrices: for square matrices, unimodularity implies full-rank, and while full-rank does not imply unimodularity, it does imply a non-zero determinant.</ref>.
+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 &#177;1, if they contain all integer entries, their inverse will also contain all integer entries (which it does, and we need it to)<ref group="note">Interesting tidbit regarding [[full-rank]] matrices and unimodular matrices: for square matrices, unimodularity implies full-rank, and while full-rank does not imply unimodularity, it does imply a non-zero determinant.</ref>.
 Finally we take only the top ''r'' rows of this. That is found with <code>MatrixRank[m]</code>.
@@ Line 236: / Line 238: @@
 ===== Proof of why column Hermite defactoring (and Pernet-Stein defactoring) work =====
 The following proof is adapted primarily from Tom Price's thinking:
-# The input matrix is an m×n matrix A.
+# The input matrix is an ''m''&#215;''n'' matrix A.
-# It decomposes into a slightly bigger and square {{nowrap|(''n'' &times; ''n'')}} unimodular matrix U and another m×n matrix which is not exactly A in HNF (because we only have to use unimodular operations so far as to get all the all-zero columns off to one side of A; we don't need to satisfy all of the conventional constraints of HNF), but we'll still call it H. The unimodular matrix is a transformation from A into H, so, {{nowrap|AU {{=}} H}}.
+# It decomposes into a slightly bigger and square (''n''&#215;''n'') unimodular matrix U and another ''m''&#215;''n'' matrix which is not exactly A in HNF (because we only have to use unimodular operations so far as to get all the all-zero columns off to one side of A; we don't need to satisfy all of the conventional constraints of HNF), but we'll still call it H. The unimodular matrix is a transformation from A into H, so, {{nowrap|AU {{=}} H}}.
-# If we were to actually slice off the all-zero cols we've isolated in H, we'd end up with a slightly smaller and square (m×m) matrix. So let's call this little square matrix S (this is our "[[Defactoring algorithms#Finding the greatest factor|greatest factor matrix]]", because its determinant is the greatest factor of A).
+# If we were to actually slice off the all-zero cols we've isolated in H, we'd end up with a slightly smaller and square (''m''&#215;''m'') matrix. So let's call this little square matrix S (this is our "[[Defactoring algorithms#Finding the greatest factor|greatest factor matrix]]", because its determinant is the greatest factor of A).
 # We can left-multiply both sides of our equation by the inverse of S (S{{inv}}) and right-multiply both sides of our equation by the inverse of U (U{{inv}}) to get {{nowrap|S{{inv}}AUU{{inv}} {{=}} S{{inv}}HU{{inv}}}}. The U's cancel out on the left so we end up with {{nowrap|S{{inv}}A {{=}} S{{inv}}HU{{inv}}}}. At first glance we don't seem to have gained any further insight. But there's more we can do from here.
 # Because H is just S with a bunch of 0 cols appended, S{{inv}}H is just the identity matrix with a bunch of zero columns appended, in other words it is a truncated identity matrix. We could call that T, and now we have {{nowrap|S{{inv}}A {{=}} TU{{inv}}}}.
-# Multiplying U{{inv}} on the left by a truncated identity matrix is the same as truncating U⁻¹. That's how we think of the output of column Hermite defactoring&mdash;our supposedly defactored matrix&mdash;so let's call that D. We now have {{nowrap|S{{inv}}A {{=}} D}}. (This is how we can see that the Pernet-Stein method of multiplying the input matrix by a transformation matrix that is a truncated and inversed column Hermite normal form of the input is equivalent to our column Hermite method, which takes the other route to the same result: inverting and truncating the unimodular result of the Hermite decomposition.)
+# Multiplying U{{inv}} on the left by a truncated identity matrix is the same as truncating U{{inv}}. That's how we think of the output of column Hermite defactoring&mdash;our supposedly defactored matrix&mdash;so let's call that D. We now have {{nowrap|S{{inv}}A {{=}} D}}. (This is how we can see that the Pernet-Stein method of multiplying the input matrix by a transformation matrix that is a truncated and inversed column Hermite normal form of the input is equivalent to our column Hermite method, which takes the other route to the same result: inverting and truncating the unimodular result of the Hermite decomposition.)
 # We need to prove now that D has three qualities:
 :: a) It's defactored,
 :: b) It still represents the same temperament (i.e. it has the same nullspace as A), and
-:: c) It's integer.
+:: c) It's an integer.
-# Proving (a) is easy. It's defactored because U was unimodular. U's determinant was 1, and neither inverting it nor truncating it would change that. Alternatively, we can prove this by showing how on the other side of the equation, S{{inv}}A is surjective as a function on lattice points (in other words, there's no points in the tempered lattice that JI lattice points don't map to). We begin with the fact that H has the same image as A, because right-multiplication with a unimodular matrix such as U doesn't change the image. Then S has the same image as H, too, and therefore the same image as A, because removing the all-zero columns doesn't change the image either. Now that we've established this, we can assert that S⁻¹A is surjective by describing a lattice point x such that {{nowrap|y {{=}} S{{inv}}Ax}} for any given lattice point y. And because S and A have the same image, we know that {{nowrap|Sy {{=}} Ax}}, and therefore {{nowrap|y {{=}} S{{inv}}Ax}}.
+# Proving (a) is easy. It's defactored because U was unimodular. U's determinant was 1, and neither inverting it nor truncating it would change that. Alternatively, we can prove this by showing how on the other side of the equation, S{{inv}}A is surjective as a function on lattice points (in other words, there's no points in the tempered lattice that JI lattice points don't map to). We begin with the fact that H has the same image as A, because right-multiplication with a unimodular matrix such as U doesn't change the image. Then S has the same image as H, too, and therefore the same image as A, because removing the all-zero columns doesn't change the image either. Now that we've established this, we can assert that S{{inv}}A is surjective by describing a lattice point ''x'' such that {{nowrap|''y'' {{=}} S{{inv}}A''x''}} for any given lattice point ''y''. And because S and A have the same image, we know that {{nowrap|S''y'' {{=}} A''x''}}, and therefore {{nowrap|''y'' {{=}} S{{inv}}A''x''}}.
 # Proving (b) is even easier. Multiplying any matrix with an invertible matrix on the left keeps the nullspace the same. S{{inv}} is clearly invertible, being itself the inverse of S. A way to understand this is: a non-invertible matrix is the same as a singular matrix, i.e. one whose determinant is 0. So as long as you don't wipe things out by essentially multiplying by 0, the nullspace information is preserved, just scaled.
-# Proving (c) is a bit trickier, because S{{inv}} is not necessarily an integer matrix. But can show that S{{inv}}A is an integer matrix by showing that it maps lattice points to lattice points. Suppose we have that same equation from the proof of (a), namely that {{nowrap|y {{=}} S{{inv}}Ax}}, where x is a lattice point. We want to show that y is a lattice point. Again, since A and S have the same image (when considered as functions on lattice points), there must be some lattice point z with {{nowrap|Sz {{=}} Ax}}. But we also know that Sy = Ax. Since S is invertible, and therefore injective, {{nowrap|y {{=}} z}}, so y is a lattice point.
+# Proving (c) is a bit trickier, because S{{inv}} is not necessarily an integer matrix. But can show that S{{inv}}A is an integer matrix by showing that it maps lattice points to lattice points. Suppose we have that same equation from the proof of (a), namely that {{nowrap|''y'' {{=}} S{{inv}}A''x''}}, where ''x'' is a lattice point. We want to show that ''y'' is a lattice point. Again, since A and S have the same image (when considered as functions on lattice points), there must be some lattice point ''z'' with {{nowrap|S''z'' {{=}} A''x''}}. But we also know that {{nowrap|S''y'' {{=}} A''x''}}. Since S is invertible, and therefore injective, {{nowrap|''y'' {{=}} ''z''}}, so ''y'' is a lattice point.
 ===== Relationship with other defactoring methods =====
@@ Line 278: / Line 280: @@
 ===== Relationship with EA =====
-Another thought that might help congeal the notion of column Hermite defactoring for you is to use what you know about multimaps (AKA "wedgies"), in particular a) what they are, and b) how to defactor them. The answer to a) is that they are just the list of the largest possible minor determinants (or "largest-minors" for short) of rectangular matrices, or in other words, the closest thing rectangular matrices such as mappings have to a real determinant. And the answer to b) is that you simply divide out the GCD of the entries in this list of largest-minors. So if defactoring a list of largest-minors means dividing common factors out, then it should be little surprise that achieving a real determinant of ±1 is equivalent to defactoring, and thereby that leveraging the unimodularity of the other matrix produced by the Hermite decomposition should be valuable in this capacity.
+Another thought that might help congeal the notion of column Hermite defactoring for you is to use what you know about multimaps (AKA "wedgies"), in particular a) what they are, and b) how to defactor them. The answer to a) is that they are just the list of the largest possible minor determinants (or "largest-minors" for short) of rectangular matrices, or in other words, the closest thing rectangular matrices such as mappings have to a real determinant. And the answer to b) is that you simply divide out the GCD of the entries in this list of largest-minors. So if defactoring a list of largest-minors means dividing common factors out, then it should be little surprise that achieving a real determinant of &#177;1 is equivalent to defactoring, and thereby that leveraging the unimodularity of the other matrix produced by the Hermite decomposition should be valuable in this capacity.
 ==== By hand ====
@@ Line 320: / Line 322: @@
 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 &gt;&nbsp;0
+# All pivots &gt; 0
-# All entries in pivot columns below the pivots =&nbsp;0
+# All entries in pivot columns below the pivots {{=}} 0
-# All entries in pivot columns above the pivots &ge;&nbsp;0 and strictly less than the pivot
+# All entries in pivot columns above the pivots &ge; 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 group="note">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 339: / Line 341: @@
 <math>
 \left[ \begin{array} {ccc|cc}
-& -11 & 4  &  13 & -6
+& -11 & 4  &  13 & -6 \\
 & 5 & 4  &  -2 & 1 \\
 \end{array} \right]
@@ Line 369: / Line 371: @@
 # '''All pivots &gt; 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&mdash;the bottom right one, below the 1st row's pivot&mdash;but it is indeed 0.
+# '''All entries in pivot columns below the pivots {{=}} 0'''? Check. This only applies to one entry&mdash;the bottom right one, below the 1st row's pivot&mdash;but it is indeed 0.
 # '''All entries in pivot columns above the pivots &ge; 0 and strictly less than the pivot'''? Check. Again, this only applies to one entry&mdash;the center top one, above the 2nd row's pivot of 11&mdash;but it is 5, and 5 is indeed non-negative and &lt; 11.
@@ Line 507: / Line 509: @@
 </math>
-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 &#177;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 group="note">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 group="note">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 group="note">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 group="note">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.
 }}
@@ Line 782: / Line 784: @@
 \end{matrix} \right]</math>
-The pivots are 1 and 11, so that 11 tells us that we had a common factor of 11<ref group="note">In the doubly-enfactored case of {{rket|{{map|17 16 -4}} {{map|4 -4 1}}}}, i.e. with a common factor of {{nowrap|33 {{=}} 3 &times; 11}}, the two pivots of the HNF are 3 and 11, putting each of them on display separately.</ref><ref group="note">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: &minus;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.
+The pivots are 1 and 11, so that 11 tells us that we had a common factor of 11<ref group="note">In the doubly-enfactored case of {{rket|{{map|17 16 -4}} {{map|4 -4 1}}}}, i.e. with a common factor of {{nowrap|33 {{=}} 3 &#215; 11}}, the two pivots of the HNF are 3 and 11, putting each of them on display separately.</ref><ref group="note">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 &minus;3 of the 2nd row, i.e. 2{{map|6 5 -4}} + (&minus;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: (&minus;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.
 }}
@@ Line 792: / Line 794: @@
 <blockquote>''Since this is an invariant of the temperament, it would be a good thing to use to refer to it, but for the fact that it is opaque and does not immediately tell us how to define the temperament.''<ref group="note">[https://yahootuninggroupsultimatebackup.github.io/tuning-math/topicId_1545.html#1545 Yahoo! Tuning Group | ''Standardizing our wedge product'']</ref></blockquote>
-Regarding any other advantages EA brought to the RTT table for beginners: they did not find any. The only minor advantage identified was how the largest-minors of the mapping which wedgies are a list of could also be read as a list of denominators of unit fractions of the tempered lattice which are capable of being generated by the associated combination of primes whose columns in the mapping were used in the calculation of the corresponding largest-minor (this idea is discussed in more detail [[Dave_Keenan_%26_Douglas_Blumeyer%27s_guide_to_EA_for_RTT#Multicomma_entries:_tempered_lattice_fractions_generated_by_prime_combinations|here]]). Furthermore, several disadvantages of EA were identified, the main one being that it is more challenging to learn and use, involving higher level mathematical concepts than LA.
+Regarding any other advantages EA brought to the RTT table for beginners: they did not find any. The only minor advantage identified was how the largest-minors of the mapping which wedgies are a list of could also be read as a list of denominators of unit fractions of the tempered lattice which are capable of being generated by the associated combination of primes whose columns in the mapping were used in the calculation of the corresponding largest-minor (this idea is discussed in more detail [[Dave Keenan & Douglas Blumeyer's guide to EA for RTT#Multicomma entries: tempered lattice fractions generated by prime combinations|here]]). Furthermore, several disadvantages of EA were identified, the main one being that it is more challenging to learn and use, involving higher level mathematical concepts than LA.
 Regarding the development of a canonical form for temperaments using only linear algebra, Dave and Douglas did manage to develop such a form, which is documented here: [[defactored Hermite form]]. It was Gene himself who first described this form (as the result of his "saturation" algorithm), so he either did not realize the full implications of his discovery, or it was simply not popularized and plugged in with the rest of the hive knowledge.
@@ Line 812: / Line 814: @@
 ===== How it works =====
-Originally Dave was inspired by what [[Paul Erlich]] wrote on [http://tonalsoft.com/enc/t/torsion.aspx the article for torsion on the Tonalsoft site]. The algorithm simply checks every possible combination of sums and differences of rows. You have to check all <span><math>\frac{3^r - 1}{2}</math></span> sums and differences where <span><math>r</math></span> is the rank of the mapping. For example, for a rank-3 mapping with rows {{vector|A B C}}, you would need to check
+Originally Dave was inspired by what [[Paul Erlich]] wrote on [http://tonalsoft.com/enc/t/torsion.aspx the article for torsion on the Tonalsoft site]. The algorithm simply checks every possible combination of sums and differences of rows. You have to check all {{sfrac|3<sup>''r''</sup> &minus; 1|2}} sums and differences where ''r'' is the rank of the mapping. For example, for a rank-3 mapping with rows {{vector|A B C}}, you would need to check
 * A
@@ Line 853: / Line 855: @@
 This is the furthest progress that was made on SAD defactor before efforts were shifted to column Hermite defactor. This implementation still exhibits problems 2 and 3; only problems 1 and 4 were solved here. Problem 3 started to be solved, but was not quite quashed.
-{{Databox|Code|
+{{Databox|Wolfram Language code for SAD defactoring|
 <pre>
 confirmEnfactoredRowReplaced[m_] := Module[{i, enfactoredRowReplaced},
@@ Line 905: / Line 907: @@
 [[Category:Math]]
 [[Category:Pages with proofs]]
+[[Category:Algorithms]]