Defactoring algorithms: Difference between revisions
Dave Keenan (talk | contribs) m →MADAM defactoring: Correct "Divide-out-GCG" to "Divide-out-GCD" |
Cmloegcmluin (talk | contribs) m update EBK and formatting |
||
| Line 48: | Line 48: | ||
This is a form of 5-limit [[porcupine]], a [[rank-2]] temperament (in fact it is the result of putting it into [[IRREF]]). Looking at either row, neither map has a common factor. But remember that we also need to check linear combinations of rows. If we subtract the 2nd row from the 1st row, we can produce the row {{map|3 -3 -6}}, which has a common factor of 3. So this mapping is also enfactored, even though it's not obvious from just looking at it. | This is a form of 5-limit [[porcupine]], a [[rank-2]] temperament (in fact it is the result of putting it into [[IRREF]]). Looking at either row, neither map has a common factor. But remember that we also need to check linear combinations of rows. If we subtract the 2nd row from the 1st row, we can produce the row {{map|3 -3 -6}}, which has a common factor of 3. So this mapping is also enfactored, even though it's not obvious from just looking at it. | ||
If you're unsure why this {{map|3 -3 -6}} matters despite not being in {{ | If you're unsure why this {{map|3 -3 -6}} matters despite not being in {{rket|{{map|3 0 -1}} {{map|0 3 5}}}}, we may need to quickly review some linear algebra fundamentals. It may take some getting used to, but a mapping can be changed to another equivalent mapping (both mappings will map input vectors to the same scalars) by replacing any row with linear combinations of its rows. That is, we could replace either {{map|3 0 -1}} or {{map|0 3 5}} in our original matrix {{rket|{{map|3 0 -1}} {{map|0 3 5}}}} to get {{rket|{{map|3 -3 -6}} {{map|0 3 5}}}} or {{rket|{{map|3 0 -1}} {{map|3 -3 -6}}}} and any of these mappings represent the same temperament. | ||
Another classic example of hidden enfactoring is the one used on [http://tonalsoft.com/enc/t/torsion.aspx Tonalsoft's article for torsion]. As a matrix, the pair of commas [[648/625]] and [[2048/2025]] for [[Joe Monzo]]'s periodicity block there would look like: | Another classic example of hidden enfactoring is the one used on [http://tonalsoft.com/enc/t/torsion.aspx Tonalsoft's article for torsion]. As a matrix, the pair of commas [[648/625]] and [[2048/2025]] for [[Joe Monzo]]'s periodicity block there would look like: | ||
| Line 115: | Line 115: | ||
Dave and Douglas did much of their work in [https://www.wolfram.com/language/ Wolfram Language] (formerly Mathematica), a popular programming language used for math problems. In this section we'll give examples using it. | Dave and Douglas did much of their work in [https://www.wolfram.com/language/ Wolfram Language] (formerly Mathematica), a popular programming language used for math problems. In this section we'll give examples using it. | ||
An input mapping <math>m</math>, such as the example Gene gives [[saturation|on the xen wiki page for Saturation]], {{ | An input mapping <math>m</math>, such as the example Gene gives [[saturation|on the xen wiki page for Saturation]], {{rket|{{map|12 19 28 34}} {{map|26 41 60 72}}}}, in Wolfram Language you would have to write as a list: | ||
<nowiki>m = {{12,19,28,34},{26,41,60,72}};</nowiki> | <nowiki>m = {{12,19,28,34},{26,41,60,72}};</nowiki> | ||
| Line 144: | Line 144: | ||
<nowiki>→ {{1,0,-4,-13},{0,1,4,10}}</nowiki> | <nowiki>→ {{1,0,-4,-13},{0,1,4,10}}</nowiki> | ||
And that result matches what Gene finds in that xen wiki article. Defactoring and putting into normal form is equivalent to canonicalization. | And that result matches what Gene finds in that xen wiki article. Defactoring and putting into normal form is equivalent to canonicalization. | ||
== Precedent: Pernet-Stein defactoring == | == Precedent: Pernet-Stein defactoring == | ||
| Line 186: | Line 186: | ||
So fitting the information from a rectangle into a square is the target, although in practice this is usually only possible by getting the information into echelon form. | So fitting the information from a rectangle into a square is the target, although in practice this is usually only possible by getting the information into echelon form. | ||
However, no method has been invented in mathematics that finds matrices like this; i.e. while it seems like it might be strictly easier to do this, to do the same stuff but stop earlier, it's not actually as simple as that or it would already exist. If such a thing did exist it would have massive ramifications for linear algebra in a broader sense, because it could be used for more basic things like finding | However, no method has been invented in mathematics that finds matrices like this; i.e. while it seems like it might be strictly easier to do this, to do the same stuff but stop earlier, it's not actually as simple as that or it would already exist. If such a thing did exist it would have massive ramifications for linear algebra in a broader sense, because it could be used for more basic things like finding nullspace bases. And so if such a thing were possible to develop, it is probably very challenging to create. The Hermite decomposition is just a practical and commonly available resource for attaining the state we need to defactor, even if it is slightly overkill. | ||
And we need the HNF otherwise to achieve canonical form, so pedagogically speaking, we may as well just explain it and that be it; why explain a second method for being simpler, if it's simplest to just use the one method. | And we need the HNF otherwise to achieve canonical form, so pedagogically speaking, we may as well just explain it and that be it; why explain a second method for being simpler, if it's simplest to just use the one method. | ||
| Line 201: | Line 201: | ||
# Because H is just S with a bunch of 0 cols appended, S⁻¹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 S⁻¹A = TU⁻¹. | # Because H is just S with a bunch of 0 cols appended, S⁻¹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 S⁻¹A = TU⁻¹. | ||
# Multiplying U⁻¹ 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 S⁻¹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⁻¹ 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 S⁻¹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 | # 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. | ||
# 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⁻¹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 y = S⁻¹Ax for any given lattice point y. And because S and A have the same image, we know that Sy = Ax, and therefore y = S⁻¹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⁻¹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 y = S⁻¹Ax for any given lattice point y. And because S and A have the same image, we know that Sy = Ax, and therefore y = S⁻¹Ax. | ||
# Proving (b) is even easier. Multiplying any matrix with an invertible matrix on the left keeps the | # Proving (b) is even easier. Multiplying any matrix with an invertible matrix on the left keeps the nullspace the same. S⁻¹ 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⁻¹ is not necessarily an integer matrix. But can show that S⁻¹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 y = S⁻¹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 Sz = Ax. But we also know that Sy = Ax. Since S is invertible, and therefore injective, y = z, so y is a lattice point. | # Proving (c) is a bit trickier, because S⁻¹ is not necessarily an integer matrix. But can show that S⁻¹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 y = S⁻¹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 Sz = Ax. But we also know that Sy = Ax. Since S is invertible, and therefore injective, y = z, so y is a lattice point. | ||
| Line 259: | Line 259: | ||
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'll 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 | 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]]): | ||
#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> | # 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. | ||
*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. | ||
| Line 269: | Line 269: | ||
====Hermite decomposition by hand==== | ====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 {{ | 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: | ||
<math>\left[ \begin{array} {rrr} | <math>\left[ \begin{array} {rrr} | ||
| Line 278: | Line 278: | ||
\end{array} \right]</math> | \end{array} \right]</math> | ||
Then we augment it with an identity matrix. However, unlike with the method for finding the | Then we augment it with an identity matrix. However, unlike with the method for finding the nullspace, we do not augment it on the bottom, but to the right: | ||
<math>\left[ \begin{array} {l} \begin{array} {rrr} | <math>\left[ \begin{array} {l} \begin{array} {rrr} | ||
| Line 519: | Line 519: | ||
\end{array} </math> | \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, {{ | 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 pseudoinverse 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==== | ====Putting it all together==== | ||
| Line 527: | Line 527: | ||
When doing a column-style Hermite decomposition by hand, we have two options: | 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; | #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 | #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 nullspace by hand). | ||
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. | 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. | ||
So, while it's a silly example, let's suppose we want to defactor the mapping {{ | So, while it's a silly example, let's suppose we want to defactor the mapping {{rket|{{map|6 5 4}} {{map|4 -4 1}}}}. Spoiler alert: it is 11-enfactored: | ||
<math>\left[ \begin{array} {rrr} | <math>\left[ \begin{array} {rrr} | ||
| Line 781: | Line 781: | ||
And that's all there is to defactoring! | 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 {{ | 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 {{rket|{{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 {{ | But what have we accomplished here, really? You may well feel underwhelmed by this matrix's transformation from {{rket|{{map|6 5 -4}} {{map|4 -4 1}}}} to {{rket|{{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 {{ | Well, the difference becomes clearer when we compare the HNF of the original matrix, which is {{rket|{{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} | <math>\left[ \begin{array} {rrr} | ||
| Line 793: | Line 793: | ||
\end{array} \right]</math> | \end{array} \right]</math> | ||
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 {{ | 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. | ||
==Other defactoring methods== | ==Other defactoring methods== | ||
| Line 799: | Line 799: | ||
When in development on an ideal defactoring method — the effort which culminated in column Hermite defactoring — Dave and Douglas experimented on other methods, which are imperfect (don't work all the time, are very slow, or too complicated). | When in development on an ideal defactoring method — the effort which culminated in column Hermite defactoring — Dave and Douglas experimented on other methods, which are imperfect (don't work all the time, are very slow, or too complicated). | ||
=== | ===Nullspace'n'back defactoring=== | ||
It's fairly self-explanatory: ''' | It's fairly self-explanatory: '''Nullspace'n'back defactoring''' is a defactoring algorithm that works by finding a basis for the nullspace of a mapping, and then finding a basis for the antinullspace of that result, which brings one back to a mapping. Depending on the implementation of your math library, nullspace'n'back defactoring ''may'' work<ref>It is proven to work in this other paper by Pernet, where the terms "right kernel basis" and "left kernel basis" are used instead: https://hal.archives-ouvertes.fr/hal-01829139, however, no one involved in the xenharmonic project as of yet has invested the time and effort necessary to understand and confirm this proof. Pernet uses (and indeed has contributed in major part to) the Sage math library, where nullspace'n'back ''does'' work, but it seems likely to work only because their code explicitly defactors matrices whenever taking the (anti-)nullspace, per our appraisal of their source code! Wolfram Language, on the other hand, which our RTT library uses, does not do this. Sintel has recommended that it does not make sense to return enfactored nullspace or antinullspace bases and that this therefore constitutes a bug in Wolfram Language; they have been subsequently contacted about the issue. Pernet himself has yet to weigh in but has been contacted about this by email.</ref>. For example, {{rket|{{map|7 11 16}} {{map|22 35 51}}}} has a nullspace basis of [{{vector|1 -5 3}}], and when we take the antinullspace of that with Wolfram Language, we get {{rket|{{map|3 0 -1}} {{map|0 3 5}}}} which is a classic case of hidden enfactoring as described above, so it does not work in this case. | ||
===Sum-and-difference defactoring=== | ===Sum-and-difference defactoring=== | ||
| Line 837: | Line 837: | ||
====Problem 1. edge case: multiple common factors ==== | ====Problem 1. edge case: multiple common factors ==== | ||
Some matrices can have multiple common factors, such as {{ | Some matrices can have multiple common factors, such as {{rket|{{map|17 16 -4} {{map|4 -4 1}}}}. The SNF of this mapping is {{rket|{{map|1 0 0}} {{map|0 33 0}}}}, and that 33 is actually a double common factor because it's not prime, but the product of 3 and 11. SAD defactoring unfortunately only removes one of these factors at a time, and so it therefore needs to be designed to perform recursively until no change occurs in an iteration, at which point all common factors have been removed. | ||
====Problem 2. edge case: well-hidden common factors==== | ====Problem 2. edge case: well-hidden common factors==== | ||
| Line 844: | Line 844: | ||
ones where there are no common factors to be found in sums or differences of the rows, but are to be found in sums or differences of ''multiples of'' these rows (what is described above as [[Canonical_form#well-hidden_enfactoring|"well-hidden" enfactoring]]). In order to solve this problem, SAD defactoring would need to be reworked to check every possible combination of integer multiples of each row, potentially up to the largest absolute value of integer in the given mapping, which would cause it to become intractably slow to compute. | ones where there are no common factors to be found in sums or differences of the rows, but are to be found in sums or differences of ''multiples of'' these rows (what is described above as [[Canonical_form#well-hidden_enfactoring|"well-hidden" enfactoring]]). In order to solve this problem, SAD defactoring would need to be reworked to check every possible combination of integer multiples of each row, potentially up to the largest absolute value of integer in the given mapping, which would cause it to become intractably slow to compute. | ||
Fortunately this did not turn out to be necessary. The solution here was to do one pass of HNF before doing the defactoring (and still do the HNF pass at the end too, when going for a canonical form). This pre-pass of HNF doesn't manage to remove the common factor, but it does at least unearth it from the well-hidden state into at least the [[Canonical_form#hidden_enfactoring|merely "hidden" state]], and possibly the [[Canonical_form#immediately_apparent_enfactoring|revealed state]]. For example, in the case of {{ | Fortunately this did not turn out to be necessary. The solution here was to do one pass of HNF before doing the defactoring (and still do the HNF pass at the end too, when going for a canonical form). This pre-pass of HNF doesn't manage to remove the common factor, but it does at least unearth it from the well-hidden state into at least the [[Canonical_form#hidden_enfactoring|merely "hidden" state]], and possibly the [[Canonical_form#immediately_apparent_enfactoring|revealed state]]. For example, in the case of {{rket|{{map|6 5 -4}} {{map|4 -4 1}}}}, the HNF is {{rket|{{map|2 9 -5}} {{map|0 22 -11}}}}, so that hidden common factor of 11 has now been completely revealed to humans, but more importantly put in a form where SAD defactoring is capable of removing it. | ||
So this is better than initially thought. But still not great to have to add another HNF pass at the onset. | So this is better than initially thought. But still not great to have to add another HNF pass at the onset. | ||
| Line 863: | Line 863: | ||
<nowiki> | <nowiki> | ||
confirmEnfactoredRowReplaced[m_] | confirmEnfactoredRowReplaced[m_] := Module[{i, enfactoredRowReplaced}, | ||
enfactoredRowReplaced = True; | enfactoredRowReplaced = True; | ||
For[i = 1, i <= Length[m], i++, | For[i = 1, i <= Length[m], i++, | ||
| Line 871: | Line 871: | ||
]; | ]; | ||
handleEnfactored[m_, maybeDisarmedRow_] | handleEnfactored[m_, maybeDisarmedRow_] := Module[{defactored, attemptedReplacementOfEnfactoredRow, i, enfactoredRowReplaced}, | ||
For[i = 1, i <= Length[m], i++, | For[i = 1, i <= Length[m], i++, | ||
attemptedReplacementOfEnfactoredRow = Prepend[Drop[m, {i}], First[maybeDisarmedRow]]; | attemptedReplacementOfEnfactoredRow = Prepend[Drop[m, {i}], First[maybeDisarmedRow]]; | ||
| Line 880: | Line 880: | ||
]; | ]; | ||
enhancedSadDefactor[m_] | enhancedSadDefactor[m_] := Module[{mNoAllZeros, reduced, linCombs, linCombsDisarmed, maybeDisarmedRow}, | ||
mNoAllZeros = removeAllZeroRows[m]; | mNoAllZeros = removeAllZeroRows[m]; | ||
linCombs = linCombsToCheck[mNoAllZeros]; | linCombs = linCombsToCheck[mNoAllZeros]; | ||
| Line 902: | Line 902: | ||
=Finding the greatest factor= | =Finding the greatest factor= | ||
To find the greatest factor of a mapping, put it into column HNF, and remove the extra columns of zeros. This gives the "greatest factor matrix". Its determinant is the greatest factor. A similar operation can be used for | To find the greatest factor of a mapping, put it into column HNF, and remove the extra columns of zeros. This gives the "greatest factor matrix". Its determinant is the greatest factor. A similar operation can be used for a comma basis. | ||
<code> | <code> | ||