Defactoring algorithms: Difference between revisions
Cmloegcmluin (talk | contribs) m →Defactoring methods: use fancy word "empirical" |
Cmloegcmluin (talk | contribs) include "greatest factor" |
||
| Line 154: | Line 154: | ||
Here is the implementation of Pernet-Stein defactoring: | Here is the implementation of Pernet-Stein defactoring: | ||
<nowiki> | <nowiki>getGreatestFactorA[a_] := Transpose[Take[hnf[Transpose[a]], MatrixRank[a]]]; | ||
pernetSteinDefactor[m_] := Inverse[getGreatestFactorA[m].m;</nowiki> | |||
== New development: column Hermite defactoring == | == New development: column Hermite defactoring == | ||
| Line 160: | Line 161: | ||
Here is the implementation for column Hermite defactoring: | Here is the implementation for column Hermite defactoring: | ||
<nowiki>hermiteUnimodular[m_]:=Transpose[First[HermiteDecomposition[Transpose[m]]]] | <nowiki>hermiteUnimodular[m_] := Transpose[First[HermiteDecomposition[Transpose[m]]]] | ||
columnHermiteDefactor[m_]:=Take[Inverse[hermiteUnimodular[m]],MatrixRank[m]]</nowiki> | columnHermiteDefactor[m_] := Take[Inverse[hermiteUnimodular[m]],MatrixRank[m]]</nowiki> | ||
So this implementation begins by finding the unimodular matrix from a column Hermite decomposition. To make it a column Hermite decomposition, we first transpose the matrix. The decomposition in Wolfram returns two items - the unimodular matrix, and the input matrix in Hermite normal form, in that order — and in this case we actually want the unimodular matrix. So we take that with <code>First[]</code>. Then we <code>Transpose[]</code> it to in effect undo the transposition we did at the beginning. | So this implementation begins by finding the unimodular matrix from a column Hermite decomposition. To make it a column Hermite decomposition, we first transpose the matrix. The decomposition in Wolfram returns two items - the unimodular matrix, and the input matrix in Hermite normal form, in that order — and in this case we actually want the unimodular matrix. So we take that with <code>First[]</code>. Then we <code>Transpose[]</code> it to in effect undo the transposition we did at the beginning. | ||
| Line 196: | Line 197: | ||
# 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 (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, 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, 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. | # 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 "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⁻¹) and right-multiply both sides of our equation by the inverse of U (U⁻¹) to get S⁻¹AUU⁻¹ = S⁻¹HU⁻¹. The U's cancel out on the left so we end up with S⁻¹A = S⁻¹HU⁻¹. At first glance we don't seem to have gained any further insight. But there's more we can do from here. | # We can left-multiply both sides of our equation by the inverse of S (S⁻¹) and right-multiply both sides of our equation by the inverse of U (U⁻¹) to get S⁻¹AUU⁻¹ = S⁻¹HU⁻¹. The U's cancel out on the left so we end up with S⁻¹A = S⁻¹HU⁻¹. 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⁻¹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⁻¹. | ||
| Line 793: | Line 794: | ||
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 {{ket|{{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 {{ket|{{map|6 5 -4}} {{map|4 -4 1}}}} mapping the other direction like {{bra|{{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>In the doubly-enfactored case of {{ket|{{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 {{ket|{{map|6 5 -4}} {{map|4 -4 1}}}} mapping the other direction like {{bra|{{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== | ||