Defactoring algorithms: Difference between revisions
Cmloegcmluin (talk | contribs) →The actual defactoring conditions: add link to image |
Cmloegcmluin (talk | contribs) finding the greatest factor |
||
| Line 197: | 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 (this is our "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⁻¹) 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 899: | Line 899: | ||
This defactoring technique is used specifically in the process of preparing matrices for [[temperament addition]]; it defactors while managing to change only a single row of the original matrix, a necessary constraint of that problem. But this method is not computationally efficient or easier to understand, so unless you have this specific need, it is not your best option. Details can be found here: [[Temperament addition#3. Addabiliziation defactoring]]. | This defactoring technique is used specifically in the process of preparing matrices for [[temperament addition]]; it defactors while managing to change only a single row of the original matrix, a necessary constraint of that problem. But this method is not computationally efficient or easier to understand, so unless you have this specific need, it is not your best option. Details can be found here: [[Temperament addition#3. Addabiliziation defactoring]]. | ||
=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 the comma basis. | |||
<code> | |||
getGreatestFactor[a_] := Det[getGreatestFactorA[a]]; | |||
getGreatestFactorA[a_] := Transpose[Take[hnf[Transpose[a]], MatrixRank[a]]]; | |||
</code> | |||
=Footnotes= | =Footnotes= | ||