|
Tag: Redirect target changed |
| (34 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| A regular temperament mapping is in '''defactored canonical form (DCF)''', or '''canonical form''' for short, when it is put into [https://en.wikipedia.org/wiki/Hermite_normal_form Hermite Normal Form] (HNF) after being [[#defactoring|"defactored"]].
| | #REDIRECT [[Saturation,_torsion,_and_contorsion#Defactoring/enfactoring]] |
| | |
| = vs. normal form =
| |
| | |
| == "normal" vs. "canonical" ==
| |
| | |
| A mapping in ''canonical'' form uniquely identifies a set of mappings that are equivalent to it. Historically, the xenharmonic community has most often used the word ''normal'' for this idea, and evidence of this can be found on many pages across this wiki. And this is not wrong; normal forms are indeed often required to be unique. However, canonical forms are required to be unique even more often that normal forms are<ref>According to [https://en.wikipedia.org/wiki/Canonical_form the Wikipedia page for canonical form], 'the distinction between "canonical" and "normal" forms varies from subfield to subfield. In most fields, a canonical form specifies a unique representation for every object, while a normal form simply specifies its form, without the requirement of uniqueness.'</ref>, and so we prefer the term canonical to normal for this purpose.
| |
| | |
| Also, using "canonical" helps establish a clear distinction from previous efforts to establish unique representations of equivalent mappings; due to its lack of historical use in [[RTT]], it appears to be safe to simply use "canonical form" for short to refer to matrices in defactored canonical form.
| |
| | |
| == vs. HNF ==
| |
| | |
| More importantly, and perhaps partially a result of this weak understanding of the difference between the conventions for normal and canonical forms, the xenharmonic community has mistakenly used HNF as if it provides a unique representation of equivalent mappings. To be more specific, HNF does provide a unique representation of ''matrices'', i.e. from a perspective of pure mathematics, and so you will certainly find throughout mathematical literature that HNF is described as providing a unique representation, and this is correct. However, when applied to the RTT domain, i.e. to ''mappings'', the HNF sometimes fails to identify equivalent mappings as such.
| |
| | |
| The critical flaw with HNF is its failure to defactor matrices<ref>This is because dividing rows is not a permitted elementary row operation when computing the HNF. See: https://math.stackexchange.com/a/685922</ref>. The canonical form that will be described here, on the other hand, ''does'' defactor matrices, and therefore it delivers a truly canonical result.
| |
| | |
| == defactoring ==
| |
| | |
| Defactoring a matrix means to perform an operation on it which ensures that it is not "enfactored". And a matrix is considered to be "enfactored" if linear combinations of its rows can produce another row whose elements have a common factor (other than 1). This definition includes matrices whose rows already include a common factor, such as {{map|24 38 56}} which has a common factor of 2. Being enfactored is a bad thing. Enfactored matrices — those in the RTT domain, at least — are sick, in a way<ref>According to [[saturation]], "...if [an RTT matrix] isn't saturated the supposed temperament it defines may be regarded as pathological..." </ref>; it's no accident that "enfactored" sounds sort of like "infected". We'll discuss this pathology in detail in [[canonical_form#the_pathology_of_enfactoredness|a later section of this article]]. Fortunately, the remedy is simple: all one has to do is "defactor" it — identify and divide out the common factor — to produce a healthy mapping.
| |
| | |
| Due to complications associated with enfactored mappings which we'll get into later in this article, we discourage treating them as representations of true temperaments.<ref>As Graham Breed writes [http://x31eq.com/temper/method.html here], "Whether temperaments with contorsion should even be thought of as temperaments is a matter of debate."</ref> Instead we recommend that they be considered to represent mere "temperoids": temperament-like structures.
| |
| | |
| == vs. IRREF ==
| |
| | |
| Elsewhere, [[Normal_lists|Integer Reduced Row Echelon Form]], or IRREF, has been proposed as a normal form for mappings. It has a similar problem as HNF does, however, in that it does not always defactor matrices. Worse, even, sometimes IRREF introduces enfactoring where before there was none! For example, consider this mapping for 5-limit porcupine, {{vector|{{map|7 11 16}} {{map|22 35 51}}}}. This mapping is not enfactored, but its IRREF is {{vector|{{map|3 0 -1}} {{map|0 3 5}}}}, which is 3-enfactored. More on this later.
| |
| | |
| == motivation ==
| |
| | |
| A key goal of introducing this canonical form is to achieve for the linear-algebra-only school of RTT practioners a unique ID for temperaments, which previously was only available by using lists of minor determinants AKA wedge products of mapping rows.
| |
| | |
| = terminology change proposal =
| |
| | |
| If you've studied RTT extensively, you've probably encountered the terms [[Saturation|"saturated" and "contorted"]] that are sometimes used to describe mappings. These two terms each have several flaws, and so this article presents alternative terms that are clearer and more descriptive: "defactored" and "enfactored", respectively. These new terms were coined by [[Dave Keenan]] in collaboration with [[Douglas Blumeyer]] in June of 2021<ref>Many, many other terms were considered before arriving at defactored and enfactored, including but not limited to: repeated, (up/down)sampled, decimated, divided/multiplied, divisive/multiplicative, completed/depleted/repleted/pleated, efficient, brown, dry, spongy/holey, fluffy, corrugated, copied, shredded, tupled, tupletted, enphactored (where the ph stood for possibly hidden)...</ref>.
| |
| | |
| == defactored, to replace saturated ==
| |
| | |
| Several concerns with the term "saturation" may be identified:
| |
| | |
| # It does not have any obvious musical or mathematical meaning in this context (whereas enfactored and defactored do have obvious mathematical meaning).
| |
| # It has another unrelated meaning within xenharmonics that it would conflict with: https://en.xen.wiki/w/Anomalous_saturated_suspension
| |
| # The most common everyday usage of that word is for "saturated fats", which are the bad kind of fats, so it has negative associations, despite "saturation" being the ''good'' state for a matrix to be in.
| |
| # Research on the tuning list archives suggests that [[Gene Ward Smith]] chose the word "saturation" because it was used in the mathematical software he was using at the time, Sage. However, no information about saturation indices has been identified elsewhere online. Certainly, if this mathematical concept of saturation is established outside of this particular piece of software, it is not well-established enough yet such that it's worth deferring to<ref>See: https://yahootuninggroupsultimatebackup.github.io/tuning-math/topicId_18026.html and https://doc.sagemath.org/html/en/reference/search.html?q=index_in_saturation. There's also https://doc.sagemath.org/html/en/reference/matrices/sage/matrix/matrix_integer_dense_saturation.html, which refers to an "index in saturation" which appears to be the common factor:<br>
| |
| <span style="font-family: monospace;"><br>
| |
| sage: C<br>
| |
| [11 16 21]<br>
| |
| [19 26 33]<br>
| |
| sage: C.index_in_saturation()<br>
| |
| 18<br>
| |
| sage: S = saturation(C); S<br>
| |
| [11 16 21]<br>
| |
| [-2 -3 -4]<br>
| |
| sage: S.index_in_saturation()<br>
| |
| 1<br></span><br>
| |
| Indeed 18 is the common factor in {{vector|{{map|11 16 21}} {{map|19 26 33}}}}.</ref>. We think we should avoid propagating Sage's decision to overload matrix saturation with a second meaning.
| |
| # Furthermore, there is another common but conflicting sense of saturation for matrices which clamps entry values to between -1 and 1<ref>See https://math.stackexchange.com/questions/1964814/linear-transformation-of-a-saturated-vector and https://faculty.uml.edu//thu/tcs01-june.pdf</ref>.
| |
| | |
| == enfactored, to replace contorted ==
| |
| | |
| As for the term "contorsion", the concerns with it are:
| |
| | |
| # Again, it does not have any obvious musical or mathematical meaning in this context. It's a word that was invented for RTT, so nothing else depends on it<ref>Here is the tuning list post where it was coined by [[Paul Erlich]]: https://yahootuninggroupsultimatebackup.github.io/tuning-math/topicId_2033.html#2456</ref>.
| |
| # It was made up due to false assumptions<ref>Authors note: to be absolutely clear, I don’t care who said what or how misconceptions arose (except insofar as it helps dispel any further misconceptions, some of which certainly may be my own). I have basically infinite sympathy for anyone who gets confused over this topic. It took my good friend Dave and I months of back and forth theorization, argumentation, and diagramming before we were able to settle on an explanation we both understood and agreed upon. I am not intending to get in the business of slinging blame (or credit) around. As far as I’m concerned, as long as we can have meaningful discussion with each other, and hopefully eventually arrive at conclusions that are more musically and intellectually empowering than we had previously, then we’re doing well together. Would I have make these mistakes myself? Yes! I have literally dozens of recent emails proving that I would have gone for the same duality myself, due to a case of asymmetry-phobia.</ref>. Through researching on tuning list archives, Dave and Douglas concluded that the associated concept of "torsion" was first described in January of 2002<ref>See: https://yahootuninggroupsultimatebackup.github.io/tuning-math/topicId_2937 which is also referred to here http://tonalsoft.com/enc/t/torsion.aspx</ref>, with regards to commas used to form Fokker periodicity blocks. The concept of enfactoring was recognized in temperament mappings (though of course it did not yet go by that name), and — because torsion in lists of commas for Fokker blocks looks the same way as enfactoring looks in temperament comma-bases — torsion got conflated with it<ref>See: https://yahootuninggroupsultimatebackup.github.io/tuning-math/topicId_2033.html#2405</ref>. But they can't truly be the same thing; the critical difference is that periodicity blocks do not involve tempering, while temperaments do. In concrete terms, while it can make sense to construct a Fokker block with {{vector|-4 4 -1}} in the middle and {{vector|-8 8 -2}} = 2{{vector|-4 4 -1}} at the edge, it does not make sense to imagine a temperament which tempers out 2{{vector|-4 4 -1}} but does not temper out {{vector|-4 4 -1}}. Unfortunately, however, this critical difference seems to have been overlooked, and so it seemed that enfactored comma-bases exhibited torsion, and thus because mappings are the dual of comma-bases, then enfactoring of a mapping should be the dual of torsion, and because the prefix co- or con- means "dual" (as in vectors and covectors), the term "con-torsion" was coined for it. "Torsion" already has the problem of being an obscure mathematical term that means nothing to most people, "contorsion" just compounds that problem by being made up, and it is made up in order to convey a duality which is false. So while "torsion" could be preserved as a term for the effect on periodicity blocks (though there's almost certainly something more helpful than that, but that's a battle for another day<ref>Perhaps we call it a "shredded periodicity block", due to the way how the paths that the multiple parallel generators take around the block look like shreds of paper, were the periodicity block imagined as a sheet of paper run through a paper shredder.</ref><ref>Furthermore, care should be taken to recognize the difference in behavior between, say<br><br>
| |
| <math>
| |
| \left[
| |
| \begin{array} {r}
| |
| -8 & -30 \\
| |
| 8 & -3 \\
| |
| -2 & 15\\
| |
| \end{array}
| |
| \right]
| |
| </math><br><br>
| |
| when it is used as a list of 5-limit commas defining a periodicity block versus when it is used as a comma basis for a temperament, namely, that in the first case the fact that the first column has a common factor of 2 and the second column has a common factor of 3 is meaningful, i.e. the 2-enfactorment will affect one dimension of the block and the 3-enfactorment will affect a different dimension of the block, or in other words, we can say that the commas here are individually enfactored rather than the entire list being enfactored, while in the second case there is no such meaning to the individual columns' factors of 2 and 3, respectively, because it would be equivalent of any form where the product of all the column factors was 6, or in other words, all that matters is that the comma-basis as a whole is 6-enfactored here. So perhaps it would be best if, for periodicity blocks, the term "enfactored" was avoided altogether, and instead commas were described as "2-torted".</ref><ref>The explanation for "why 'torsion' in the first place?" is interesting. It comes from group theory (see: https://en.wikipedia.org/wiki/Group_(mathematics)#Uniqueness_of_identity_element). In group theory, to have torsion, a group must have an element that comes back to zero after being chained 2 or more times. The number of times before coming back to zero is called the "order" of the element, sometimes also called the "period length" or "period". When the order is greater than 1 (and less than infinity), the element is said to have torsion, or to be a torsion element, and so the group it is an identity element of is said to have torsion. See also: https://en.wikipedia.org/wiki/Order_(group_theory). Clearly we can't use period (length) because period has another firmly established meaning in xenharmonics. But we could refer to torsion as "finite order greater than one", but that's quite the mouthful while still nearly as obscure.</ref>), the term "contorsion" must be banished from the RTT community altogether.
| |
| # A word with the same spelling was also coined with mathematical meaning outside of RTT, in the field of differential geometry: https://en.wikipedia.org/wiki/Contorsion_tensor<ref>In this field, it does definitely represent twisting, like in a Möbius strip. Also, DG contorsion is related to DG torsion by subtraction, not duality.</ref>
| |
| # It is prone to spelling confusion. People commonly refer to temperaments with contorsion as "contorted". But contorted is the adjective form of a different word, contortion, with a t, not an s. The proper adjective form of contorsion would be contorsioned. Would you use "torted" instead of torsioned? Or would people prefer "torsional" and "contorsional", even though that suggests only of or pertaining to in general rather than having the effect applied.<ref>If it was meant to most strongly evoke duality with torsion, it should have been spelled "cotorsion". Naming it "contorsion" is an annoying step toward "contortion" but stopping halfway there. But this isn't a strong point, because duality with torsion was the false assumption mentioned above.</ref>
| |
| # Due to its similarity with the word "contortion", the word contorsion evokes bending, twisting, and knotting. But there is nothing bendy, twisty, or knotted about the effect it has on JI lattices or tuning space.
| |
| | |
| == conclusion ==
| |
| | |
| In accordance with this research and reasoning, this article henceforth will eschew the terms saturation and contorsion in favor of defactored and enfactored.<ref>I am starting a conversation about how to relate this page to the existing page for saturation and contortion on its discussion page, here: https://en.xen.wiki/w/Talk:Saturation</ref>
| |
| | |
| = the pathology of enfactoredness =
| |
| | |
| In this section, we will use lattices to visualize enfactored temperaments, to demonstrate the musical implications of mappings with common factors, and the lack of musical implications of comma-bases with common factors.
| |
| | |
| == unenfactored case ==
| |
| | |
| [[File:Unenfactored mapping.png|365px|thumb|right|A 3-limit tempered lattice, superimposed on the JI lattice]]
| |
| | |
| First, let's look at an unenfactored mapping. This example temperament is so simple that it is not of practical musical interest. It was chosen because it's basically the numerically simplest possible example, where this type of simplicity empowers us to visualize the problem at a practical scale as clearly as possible. Please consider the diagram at right.
| |
| | |
| This is a representation of 2-ET, a 3-limit, rank-1 (equal) temperament, with mapping {{vector|{{map|2 3}}}}, meaning it has a single generator which takes two steps to reach the octave, and three steps to reach the tritave. This temperament tempers out a single comma, whose vector representation looks similar to the mapping: {{vector|-3 2}}, AKA 9/8. And so the comma-basis for this temperament is {{map|{{vector|-3 2}}}}.
| |
| | |
| We can imagine that we started out with a JI lattice, where movement up and down correspond to prime 2 (the octave) and movements right and left correspond to prime 3 (the tritave). We have tempered JI here, and so we've faded the JI lattice out to a faint grey color in the background. What we've done specifically is tempered out the comma {{vector|-3 2}} so that any nodes in this lattice which are 2 over and 3 up from each other are equivalent. Therefore we only need to consider a thin swath of the lattice anymore, specifically, a swath which connects the origin {{vector|0 0}}, AKA 1/1, to {{vector|-3 2}}, and then runs perpendicularly to infinity in either direction.
| |
| | |
| There's a couple good ways to interpret this situation:
| |
| # We've turned on a teleportation field for every point outside this swath, so that it moves by these (-3,2) intervals until it finds its way inside the swath.
| |
| # We've rolled up space, so that the line from 1/1 to 9/8 ₋ the width of our swath ₋ is like the circumference of a tube. In this case, since we're only working with 3-limit JI, "space" was only ever 2D, so we can just think of it as paper that we've rolled up, so the pair of dotted lines visualized here are touching along their entire lengths (and if you wanted to imagine further copies of these dotted lines at every (-3,2) interval farther out in either direction, and the paper is infinitely thin, just stack all the dotted lines on top of each other forever). | |
| | |
| Either way, then we just superimpose the new tempered lattice on top. It's drawn in blue.
| |
| | |
| You can see that in the grey lattice underneath, coordinates have 2 values, e.g. {{vector|-1 2}}. That's because the JI lattice essentially had two generators: the octave and the tritave. But tempering has helped us simplify things by reducing us to a single generator, so here, in the new blue-colored tempered lattice, the coordinates have only 1 value, e.g. {{vector|8}}, and they simply indicate how many iterations of the single generator here that we've taken to reach the given point.
| |
| | |
| We've superimposed the tempered lattice atop the former JI lattice so we can see which JI intervals map to which tempered intervals. For example, {{vector|-1 2}}, AKA 9/2, maps to {{vector|8}}. That tells us that if we want to use the temperament's approximation of the JI interval 9/2, then we want the tempered pitch arrived at by moving by the generator 8 times.
| |
| | |
| Note that whenever the path the generator takes leaves the main swath, it wraps around to the point on the opposite side. Again, you can think of this either way you prefer: the world is still flat, and you've just warped over there; or, the world has been curled up, and in reality you've been looping back around toward that point the whole time, and the dotted line in this flat representation just represents the point you cut the tube and unrolled it so it could be better visualized on a screen.
| |
| | |
| The tempered vector for the generator of this temperament is of course {{vector|1}}, but the JI preimage of the generator of this temperament is {{vector|-1 1}}, or 3/2. It's visually clear why this is the generator. We need to choose an interval which if we repeatedly move by it, while wrapping around the swath, we'll visit every node inside the swath. The best way to do that is to move from the origin to the node that's nearest to the dotted line labelled "tube circumference". We want this node because we want to move away from the tube circumference as little as possible each time, so we avoid skipping any nodes. If it's not obvious, you may want to experiment with drawing the generator line as if it had gone to any other point inside the swath; if you repeated that movement, would you visit every node? No.
| |
| | |
| All of this so far is actually only just explaining the basic setup for any tempered lattice. But we've got to lay the basics down first in order to discuss the effect of enfactoring. We'll do that now!
| |
| | |
| == enfactored mapping ==
| |
| | |
| [[File:2-enfactored mapping.png|365px|thumb|right|A 2-enfactored mapping represents a temperoid for which every other step of its generator lands on a pitch which no JI interval would ever temper to.]]
| |
| | |
| We are now comparing the previous diagram, which had the mapping {{vector|{{map|2 3}}}}, with the 2-enfactored version of it, i.e. the mapping 2×{{vector|{{map|2 3}}}} = {{vector|{{map|4 6}}}}, AKA 4-ET.
| |
| | |
| If you compare this lattice of an enfactored mapping with the previous lattice for a healthy, unenfactored mapping, they should look almost the same. They have the same comma and tube circumference. And the generator follows the same path through that tube/swath. The key difference is how far the generator moves with each step along that path.
| |
| | |
| Starting from the origin, we can see that it takes us 2 moves of the generator to reach the approximation of {{vector|-1 1}}, AKA 3/2, where before we made that step in one go. Then another 2 moves to reach the approximation of {{vector|-2 2}}, AKA 9/4, for a total of 4 moves, where before it only took us 2 steps. As you keep going, you'll see that each node it has taken us 2x as many steps as before to reach it.
| |
| | |
| And for what? What happens in the steps that are halfway between nodes that were on the JI lattice? These are shown with hollow blue circles instead of filled blue circles, to indicate that there's not JI lattice node underneath them. In other words, while these are legitimate musical intervals, there is no JI interval which would be said to temper to them. In other words, since this is 4-ET, that first generator step is to a node {{vector|1}} that's about 300¢. But {{vector|0 0}} tempers to {{vector|0}} and {{vector|-1 1}} tempers to {{vector|2}}; nothing tempers to {{vector|1}}. It's an interval that can certainly at least be heard and understood musically, but has no meaning with respect to tempering JI, or in other words, no RTT purpose.
| |
| | |
| And so this 4-ET doesn't bring anything to the table that isn't already brought by 2-ET. And so it is fitting to consider it only a temperoid, rather than a true temperament. Were this as bad as things got, it might not be worth pushing for distinguishing temperoids from temperaments. But once we look at enfactored comma-bases, we'll see why things get pretty pathological.
| |
| | |
| == enfactored comma-bases ==
| |
| | |
| [[File:2-enfactored comma-basis.png|365px|thumb|left|enfactored comma-bases are garbage]]
| |
| | |
| Here's where things get kind of nuts. Most recently we experimented with enfactoring our healthy temperament's mapping. Now let's experiment with enfactoring its comma-basis. In the unenfactored situation, if our comma-basis was {{map|{{vector|-3 2}}}}, then 2-enfactoring it produces 2×{{map|{{vector|-3 2}}}} = {{map|{{vector|-6 4}}}}.
| |
| | |
| We know that in the original diagram, the large-labelled {{vector|-3 2}} represented our comma, and this was the point that our dotted line ran through, the one that represented our boundary of warp/wrap. So our first thought should be: we must alter our diagram so that now {{vector|-6 4}} is that point instead. Fine.
| |
| | |
| But here's the problem. It simply doesn't make sense to double the width of our swath/tube! If {{vector|-6 4}} is tempered out, then so is {{vector|-3 2}}. That is, while nothing would stop you from drawing a diagram with a double-width swath/tube, the musical reality is that it is impossible to temper out {{vector|-6 4}} without also tempering out {{vector|-3 2}}. And so there is no meaning or purpose to the comma-basis {{vector|-6 4}}, whether RTT-wise or musically in general. It is garbage.
| |
| | |
| And so our lattice for an enfactored comma-basis looks almost identical to the original unenfactored lattice. The only difference here is that we've drawn a "supposed (but false)" tube circumference out to {{vector|-6 4}}, while the half of this length which is real is now labelled the "true" circumference.
| |
| | |
| == enfactored comma-bases vs. periodicity blocks with torsion ==
| |
| | |
| [[File:Torsion.png|400px|thumb|right|a reworking of the classic torsion example from Tonalsoft to reveal the twinned generator paths]]
| |
| | |
| And now we're prepared to confront the key difference between the enfactored comma-basis of a temperament, and torsion of a periodicity block.
| |
| | |
| What they have in common is that both take the form of a common factor found somewhere in linear combinations of entries in a list of commas defining a pitch structure, and that these commas can be visualized by slicing the JI lattice into swaths of "periodicity" (that's just a fancy word for the effect we've already been observing for temperaments, where nodes outside the swath related by the size of that comma are considered equivalent and therefore redundant, or repetitions of the same pitch class).
| |
| | |
| The key difference is that the former (temperaments) tempers the commas out, while the latter (periodicity blocks) does not.
| |
| | |
| Why is this the key difference? Well, remember how in the previous section, the reason we couldn't actually extend the width of the swath/tube to {{vector|-6 4}} was because the tempering: if {{vector|-6 4}} is tempered out, then {{vector|-3 2}} is as well, so the swath/tube cannot legitimately be extended. Since there is no tempering in the case of periodicity blocks, however, the width ''can'' legitimately be extended in this way.
| |
| | |
| Let's take a look at the example given in Tonalsoft's page for torsion. The diagram there has been reworked here to help clarify things. The origin, 1/1, has been placed in the corner of this parallelogram-shaped block, and the two commas that define it are in two of the other corners: 2048/2025 and 625/324. The value at the fourth corner, 12800/6561, has vector 2×{{vector|-8 8 -2}}. The first 2 is just to octave-reduce it to being positive, but you may recognize the actual vector part as 2 times the meantone comma. The most important part is that the vector is 2-enfactored. You can see that the node at the very center of this block is 160/81, which again is 2×{{vector|-4 4 -1}}, or the octave-reduced non-enfactored version of that same comma.
| |
| | |
| The red and blue lines that wrap around this block are two different generator paths. The point here is to show that by doubling the size of this periodicity block, we have made it impossible to choose a node to travel to from the origin, i.e. a generator, such that you can reach every node in the block. Instead, the best you can do is reach half of the nodes; that's the red path from the origin 1/1. The blue path is an exact copy of the red path, but offset.
| |
| | |
| So we can see how tempting the duality can be here. In the case of a 2-enfactored mapping, the generator path reaches ''twice'' as many nodes as there were JI nodes. But in the case of a 2-enfactored comma-basis — if we could legitimately extend the width of the block, as we do in untempered periodicity blocks! — we would reach ''half'' as many nodes. But this duality just is not musically, audibly real.
| |
| | |
| == enfactored mappings vs. enfactored comma-bases ==
| |
| | |
| One may pose the question: what is the relationship between an enfactored mapping and an enfactored comma-basis? Can you have one but not the other? Must you? Or must you not? Or does the question even make sense? Certainly at least some thinkers have suggested these cases are meaningfully independent<ref>such as in [[Kite Giedraitis]]'s writings on [[Color_notation/Temperament_Names|color notation]], which read "it's possible that there is both torsion and contorsion"</ref>.
| |
| | |
| The conclusion we arrive at here is that because enfactored comma-bases don't make any sense, or at least don't represent any legitimately new musical information of any kind that their unenfactored version doesn't already represent, it is not generally useful to think of enfactored mappings and enfactored comma-bases as independent phenomena. It only makes sense to speak of enfactored temperaments. Of course, one will often use the term "enfactored mapping" because enfactored mappings are the kind which do have some musical purpose, and often the enfactored mapping will be being used to represent the enfactored temperament — or temperoid, that is.
| |
| | |
| By the way, canonical form is not only for mappings. Comma-bases may also be put into canonical form, as long as they are first antitransposed[20], and then antitransposed again at the end, or in other words, you sandwich the defactoring and HNF operations between antitransposes.
| |
| | |
| == conclusion ==
| |
| | |
| So due to the high likelihood for confusion when conceptualizing enfactored temperaments, we believe that using HNF as the unique ID for temperaments, i.e. treating temperoids as true temperaments, is a dangerous and unhelpful road. Instead, canonical form should be used, essentially HNF but with defactoring built in, so that practitioners of RTT can focus on working with true temperaments.
| |
| | |
| = identifying enfactored mappings =
| |
| | |
| == immediately apparent enfactoring ==
| |
| | |
| Sometimes the enfactoring of a mapping is immediately apparent. For example:
| |
| | |
| <math>
| |
| \left[
| |
| \begin{array} {r}
| |
| 24 & 38 & 56 \\
| |
| \end{array}
| |
| \right]
| |
| </math>
| |
| | |
| This mapping has only a single row, and we can see that every element in that row is even. Therefore we have a common factor of at least 2. In this case it is in fact exactly 2. So we can say that this is a 2-enfactored mapping.
| |
| | |
| Being enfactored tells us that it's wasteful to use this mapping. Specifically, being 2-enfactored tells us that we have 2x as many pitches as we need. Said another way, half of the pitches in our system are bringing nothing to the table, at least not in terms of approximating intervals built out of the 5-limit primes 2, 3, and 5, which is the primary goal of a temperament.
| |
| | |
| This is the mapping for [[5-limit]] [[24-ET]]. To be clear, we're not saying there's a major problem with 24 as an [[EDO]]. The point here is only that — if you're after a 5-limit temperament — you may as well use [[12-ET]]. So we would consider 24-ET to stand for 24 Equal Temperoid.
| |
| | |
| Think of it this way: because every element is even, any [[JI]] interval you'd map with with the mapping must come out as an even number of steps of 24-ET, by the definition of the dot product, and every even step of 24-ET is just a step of 12-ET. Examples: {{vector|1 -2 1}}.{{map|24 38 56}} = 24 - 76 + 56 = 4, {{vector|1 1 -1}}.{{map|24 38 56}} = 24 + 38 - 56 = 6.
| |
| | |
| == hidden enfactoring ==
| |
| | |
| Other times, enfactoring is less apparent. Consider this example:
| |
| | |
| <math>
| |
| \left[
| |
| \begin{array} {r}
| |
| 3 & 0 & -1 \\
| |
| 0 & 3 & 5 \\
| |
| \end{array}
| |
| \right]
| |
| </math>
| |
| | |
| This is a form of 5-limit [[porcupine]], a [[rank-2]] temperament. 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 {{vector|{{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 {{vector|{{map|3 0 -1}} {{map|0 3 5}}}} to get {{vector|{{map|3 -3 -6}} {{map|0 3 5}}}} or {{vector|{{map|3 0 -1}} {{map|3 -3 -6}}}} and any of these mappings represent the same temperament.
| |
| | |
| == well-hidden enfactoring ==
| |
| | |
| Sometimes the hidden common factor is even harder to find. Consider the mapping:
| |
| | |
| <math>
| |
| \left[
| |
| \begin{array} {r}
| |
| 6 & 5 & -4 \\
| |
| 4 & -4 & 1 \\
| |
| \end{array}
| |
| \right]
| |
| </math>
| |
| | |
| To find this common factor, we need to linearly combine two of the first row {{map|6 5 -4}} and negative three of the 2nd row {{map|4 -4 1}} to produce {{map|0 22 -11}}. So we can see here that its common factor is 11. But there's no clear relationship between the numbers 2 and 3 and the number 11. And so we can begin to see that the problem of identifying enfactored mapping may not be very simple or straightforward.
| |
| | |
| = defactoring methods =
| |
| | |
| Even better than identifying enfactored mappings is actually full-on defactoring them. Here are two methods that do just that: Smith defactoring, developed by Gene Ward Smith<ref>but the name comes from a different Smith: [https://en.wikipedia.org/wiki/Henry_John_Stephen_Smith Henry John Stephen Smith], for whom the Smith normal form is named, which this method uses</ref>, and column Hermite defactoring, developed by Dave and Douglas (the name comes, of course, from Hermite normal form, which it uses<ref>named for Charles Hermite, who was French, by the way, and so his name is pronounced more like err-MEET, not like HER-might</ref>).
| |
| | |
| Neither of these methods have been rigorously proven to always defactor mappings, but tests Douglas ran on thousands of random mappings strongly suggested that both methods work and give the exact same results as each other.
| |
| | |
| This article prefers column Hermite defactoring to Smith defactoring because it is:
| |
| * Cheaper computationally, wasting less resources computing things irrelevant to the result<ref>
| |
| Using the following code in Wolfram Language:<br>
| |
| <span style="font-family: monospace; font-size: 10px;">hermiteUnimodular[m_]:=Transpose[First[HermiteDecomposition[Transpose[m]]]]<br>
| |
| columnEchelonDefactor[m_]:=Take[Inverse[hermiteUnimodular[m]],MatrixRank[m]]<br>
| |
| <br>
| |
| rightReducingMatrix[m_] := Last[SmithDecomposition[m]]<br>
| |
| smithDefactor[m_] := Take[Inverse[rightReducingMatrix[m]], MatrixRank[m]]<br>
| |
| <br>
| |
| ms = {};<br>
| |
| Do[<br>
| |
| d = RandomInteger[{2,6}];<br>
| |
| r = RandomInteger[{1,d}];<br>
| |
| m = RandomInteger[{-99,99},{r,d}];<br>
| |
| ms = Join[ms, {m}],<br>
| |
| 1000<br>
| |
| ]<br>
| |
| <br>
| |
| AbsoluteTiming[Do[smithDefactor[m],{m,ms}]]<br></span><br>
| |
| The first several results for Smith defactoring took (in ms) 3.55919, 3.45199, 3.58493, 3.63464, 3.80917, 3.77151, while the first several results for column Hermite defactoring took 3.30063, 3.39137, 3.33808, 3.21195, 3.16469, 3.20419. So this suggests a slight edge for column Hermite defactoring.
| |
| </ref>,
| |
| * Is easy to understand how it works, and can be worked out by hand (as we will demonstrate below),
| |
| * If interested, you can see what the common factor is, if there was any.
| |
| | |
| Column Hermite defactoring could not have been developed, however, were it not for Gene's pioneering work with the Smith defactoring (what he calls the process of "saturating" a mapping). At first Dave and Douglas had no idea what the right reducing matrix of the Smith decomposition (the process which also provides the Smith normal form) had to do with common factors, only that it somehow magically worked. So they analyzed the Smith decomposition until they isolated its key actions which actually effect the defactoring, and then honed their method down to do only these necessary actions. Again, they wouldn't have known where to start were it not for Gene.
| |
| | |
| == precedent: Smith defactoring ==
| |
| | |
| 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 <span><math>m</math></span>, such as the example Gene gives [[saturation|on the xen wiki page for Saturation]], {{vector|{{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>
| |
| | |
| The implementation of Gene's method in Wolfram Language is simple. Just two lines:
| |
| | |
| <nowiki>rightReducingMatrix[m_] := Last[SmithDecomposition[m]]
| |
| smithDefactor[m_] := Take[Inverse[rightReducingMatrix[m]], MatrixRank[m]]</nowiki>
| |
| | |
| So the first thing that happens to <span><math>m</math></span> when you pass it in to <code>smithDefactor[]</code> is that it calls <code>rightReducingMatrix[]</code> on it. This will find the Smith decomposition (using a function built in to Wolfram Language), which gives you three outputs: the Smith normal form, flanked by its left and right reducing matrices. Gene asks only for the right reducing matrix, so we grab that with <code>Last[]</code>. So that's what the function on the first line, <code>rightReducingMatrix[]</code>, does.
| |
| | |
| Then Gene asks us to invert this result and take its first <span><math>r</math></span> rows, where <span><math>r</math></span> is the rank of the temperament. <code>Invert[]</code> takes care of the inversion, of course. <code>MatrixRank[m]</code> gives the count of linearly independent rows to the mapping, AKA the rank, or count of generators in this temperament. In this case that's 2. And so <code>Take[list, 2]</code> simply returns the first 2 entries of the list.
| |
| | |
| Almost done! Except Gene not only defactors, he also calls for HNF, as we would, to achieve canonical (unique ID) form.
| |
| | |
| <nowiki>normalize[m_] := Last[HermiteDecomposition[m]]</nowiki>
| |
| | |
| Similar to the Smith Normal Form, we do a decomposition, which gives you the normal form plus some other bonus results. In this case we actually want the normal form itself, and it happens to be the last element in the result list. So putting it all together, we defactor and then normalize:
| |
| | |
| <nowiki>rightReducingMatrix[m_] := Last[SmithDecomposition[m]];
| |
| smithDefactor[m_] := Take[Inverse[rightReducingMatrix[m]], MatrixRank[m]];
| |
| | |
| normalize[m_] := Last[HermiteDecomposition[m]];
| |
| | |
| m = {{12,19,28,34},{26,41,60,72}};
| |
| normalize[smithDefactor[m]]</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 normalizing is equivalent to canonicalization.
| |
| | |
| == new development: column Hermite defactoring ==
| |
| | |
| Here is the implementation for column Hermite defactoring:
| |
| | |
| <nowiki>hermiteUnimodular[m_]:=Transpose[First[HermiteDecomposition[Transpose[m]]]]
| |
| 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.
| |
| | |
| 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).
| |
| | |
| Finally we take only the top <span><math>r</math></span> rows of this, where <span><math>r</math></span> is the rank of the original matrix. That's found with <code>MatrixRank[m]</code>.
| |
| | |
| === how/why it works ===
| |
| | |
| The basic idea is that the column Hermite decomposition leaves any common row factor the mapping might have had in the HNF part, while preserving in the unimodular part everything that's still meaningful about how the mapping works. So that's why we throw the column HNF away and keep the unimodular part. The rest of the algorithm is basically just "undoing" stuff so we get back to the structure of the matrix that we input.
| |
| | |
| So inverting is one of those "undo" type operations. To understand why, we have to understand the nature of this decomposition. What the Hermite decomposition does is return a unimodular matrix U and a Hermite normal form matrix H such that if you left-multiply your original matrix A by the unimodular matrix U you get the normal form matrix H, or in other words, UA = H. So, think of it this way. If A is what we input, and we want something sort of like A, but U is what we've taken, and U is multiplied with A in this equality to get H, where H is also kind of like A, then probably what we really want is something like U, but inverted.
| |
| | |
| Finally, we take only the top <span><math>r</math></span> rows, which again is an "undo" type operation. Here what we're undoing is that we had to graduate from a rectangle to a square temporarily, storing our important information in the form of this invertible square unimodular matrix temporarily, so we could invert it while keeping it integer, but now we need to get it back into the same type of rectangular shape as we put in. So that's what this part is for.<ref>There is probably some special meaning or information in the rows you throw away here, but we're not sure what it might be.</ref>
| |
| | |
| === various additional ways of thinking about how/why it works ===
| |
| | |
| ==== relationship with Smith defactoring ====
| |
| | |
| If you describe column Hermite defactoring as "column-Hermite inverse take-r-rows", the analogous way to describe Smith defactoring would be like "row-Hermite column-Hermite row-Hermite column-Hermite row-Hermite column-Hermite ... inverse take-r-rows". In other words, the nature of Smith decomposition is to essentially repeatedly Hermite decompose from either angle until you've achieved Smith normal form, which is wasteful and unnecessary in this context, when all that is required is a single column-Hermite decomposition. This helps explain why column Hermite defactoring is more performant in general than Smith defactoring, when code is run against thousands of examples at a time.
| |
| | |
| According to Wolfram<ref>See: https://reference.wolfram.com/language/ref/SmithDecomposition.html</ref>, "the Smith decomposition can often be found by two iterations of the Hermite decomposition". This notion is echoed in the Sage docs<ref>See: https://doc.sagemath.org/html/en/reference/matrices/sage/matrix/matrix_integer_dense.html</ref>, which read, "Use Hermite normal form twice to find an invertible matrix whose inverse transforms a matrix with the same row span as self to its saturation," remembered that saturation is the same as defactoring. The reason for the multiple applications of Hermite decomposition to achieve Smith normal form is that you won't necessarily get a diagonal matrix on the first go. But as we know from Smith defactoring, the center matrix of the Smith decomposition — the Smith normal form one — is not the target matrix, so its exact form is not necessary to achieve to accomplish defactoring.
| |
| | |
| ==== relationship with VEA ====
| |
| | |
| 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 minor determinants (or "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 extract the GCD of the entries in this list of minors. So if defactoring a list of minor determinants 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.
| |
| | |
| ==== unimodular matrix size ====
| |
| | |
| One reason for doing a column Hermite decomposition on a mapping can be understood by comparing the sizes of the unimodular matrices. Matrices are often described as <span><math>m×n</math></span>, where <span><math>m</math></span> is the row count and <span><math>n</math></span> is the column count. In the case of mappings it may be superior to use variable names corresponding to the domain concepts of rank <span><math>r</math></span>, and dimension <span><math>d</math></span>, i.e. to speak of <span><math>r×d</math></span> mappings. The key bit of info here is that — for non-trivial mappings, anyway — <span><math>d</math></span> is always greater than <span><math>r</math></span>. So a standard row-based Hermite decomposition, i.e. to the right, is going to produce an <span><math>r×r</math></span> unimodular matrix, while a column-based Hermite decomposition, i.e. to the bottom, is going to produce a <span><math>d×d</math></span> unimodular matrix. For example, 5-limit meantone has <span><math>r=2</math></span> and <span><math>d=3</math></span>, so a standard row-based Hermite decomposition is going to produce a unimodular matrix that is only 2×2, while the column-based Hermite decomposition will produce one that is 3×3. With <span><math>d>r</math></span>, it's clear that the column-based decomposition in general will always produced the larger unimodular matrix. In fact, the row-based decomposition is too small to be capable of enclosing an amount of entries equal to the count of entries in the original mapping, and therefore it could never support preserving the entirety of the important information from the input (in terms of our example, a 3×3 matrix can hold a 2×3 matrix, but a 2×2 matrix cannot).
| |
| | |
| === by hand ===
| |
| | |
| In an effort to demystify the effects of column Hermite defactoring, let's walk though an example manually.
| |
| | |
| First we need to learn how to perform its two building blocks by hand:
| |
| # 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.
| |
| | |
| 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 null-space of a mapping by hand (as demonstrated [[User:Cmloegcmluin/RTT_How-To#null-space|here]]):
| |
| # 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>
| |
| * null-space: augment to the bottom, go until you get columns with all zeros.
| |
| * Hermite: augment to the right, go until echelon form.
| |
| * 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 {{vector|{{map|12 19 28}} {{map|26 43 60}}}}, or as a matrix:
| |
| | |
| <math>\left[ \begin{array} {rrr}
| |
| | |
| 12 & 19 & 28 \\
| |
| 26 & 43 & 60 \\
| |
| | |
| \end{array} \right]</math>
| |
| | |
| Then we augment it with an identity matrix. However, unlike with the method for finding the null-space, we do not augment it on the bottom, but to the right:
| |
| | |
| <math>\left[ \begin{array} {l} \begin{array} {rrr}
| |
| | |
| 12 & 19 & 28 \\
| |
| 26 & 43 & 60 \\
| |
| | |
| \end{array} & \rule[-5mm]{0.375mm}{12mm} & \begin{array} {r}
| |
| | |
| 1 & 0 \\
| |
| 0 & 1 \\
| |
| | |
| \end{array} \end{array} \right]</math>
| |
| | |
| 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 that in detail later in this article [[canonical_form#HNF|here]]. The quick and dirty is:
| |
| | |
| # all 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
| |
| | |
| 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>
| |
| | |
| So let's begin by subtracting the 1st row from the 2nd row, and let's do it 2 times, because we can see that would get the pivot of the 2nd row pretty close to 0, which is where we're trying to get it, per the 2nd HNF constraint above.
| |
| | |
| <math>\left[ \begin{array} {l} \begin{array} {rrr}
| |
| | |
| 12 & 19 & 28 \\
| |
| 2 & 5 & 4 \\
| |
| | |
| \end{array} & \rule[-5mm]{0.375mm}{12mm} & \begin{array} {r}
| |
| | |
| 1 & 0 \\
| |
| -2 & 1 \\
| |
| | |
| \end{array} \end{array} \right]</math>
| |
| | |
| Okay. We can see now that if we subtract 6 times the 2nd row back from the 1st row now, we'll create a 0 in the first column. It's not in the bottom left where we need it, but that's no big deal; reordering the rows is an allowed row operation. So let's do that subtraction:
| |
| | |
| <math>\left[ \begin{array} {l} \begin{array} {rrr}
| |
| | |
| 0 & -11 & 4 \\
| |
| 2 & 5 & 4 \\
| |
| | |
| \end{array} & \rule[-5mm]{0.375mm}{12mm} & \begin{array} {r}
| |
| | |
| 13 & -6 \\
| |
| -2 & 1 \\
| |
| | |
| \end{array} \end{array} \right]</math>
| |
| | |
| And then reorder the rows:
| |
| | |
| <math>\left[ \begin{array} {l} \begin{array} {rrr}
| |
| | |
| 2 & 5 & 4 \\
| |
| 0 & -11 & 4 \\
| |
| | |
| \end{array} & \rule[-5mm]{0.375mm}{12mm} & \begin{array} {r}
| |
| | |
| -2 & 1 \\
| |
| 13 & -6 \\
| |
| | |
| \end{array} \end{array} \right]</math>
| |
| | |
| We're actually quite close to done! All we need to do is flip the signs on the 2nd row. But wait, you protest! Isn't that multiplying a row by -1, which we specifically forbade? Well, sure, but that just shows we need to clarity what we're concerned about, which is essentially enfactoring. Multiplying by -1 does not change the GCD of the row, where multiplying by -2 or 2 would. Note that because the process for taking the HNF forbids multiplying ''or dividing'', it will never introduce enfactoring where was there was none previously, but it also does not remove enfactoring that is there.
| |
| | |
| Perhaps another helpful way of thinking about this is that multiplying the row by -1 does not alter the potential effects this row could have being added or subtracted from other rows. It merely swaps addition and subtraction. Whereas multiplying the row by any integer with absolute value greater than 1 ''would'' affect the potential effects this row could have being added or subtracted from other rows: it would limit them.
| |
| | |
| So, let's do that sign flip:
| |
| | |
| <math>\left[ \begin{array} {l} \begin{array} {rrr}
| |
| | |
| 2 & 5 & 4 \\
| |
| 0 & 11 & -4 \\
| |
| | |
| \end{array} & \rule[-5mm]{0.375mm}{12mm} & \begin{array} {r}
| |
| | |
| -2 & 1 \\
| |
| -13 & 6 \\
| |
| | |
| \end{array} \end{array} \right]</math>
| |
| | |
| And we're done! Let's confirm though.
| |
| | |
| # '''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 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.
| |
| | |
| And so, we have performed the Hermite decomposition. The matrix to the left of the augmentation line — the one in place of our original matrix — is that original matrix in HNF:
| |
| | |
| <math>\left[ \begin{array} {rrr}
| |
| | |
| 2 & 5 & 4 \\
| |
| 0 & 11 & -4 \\
| |
| | |
| \end{array} \right]</math>
| |
| | |
| And the matrix to the right of the augmentation line is the other output of the Hermite decomposition: a unimodular matrix with a special property.
| |
| | |
| <math>\left[ \begin{array} {rrr}
| |
| | |
| -2 & 1 \\
| |
| -13 & 6 \\
| |
| | |
| \end{array} \right]</math>
| |
| | |
| This special property is that if you take the original matrix and left multiply it by this unimodular matrix, you will get the HNF.
| |
| | |
| <math>\begin{array} {l} \left[ \begin{array} {rrr}
| |
| | |
| -2 & 1 \\
| |
| -13 & 6 \\
| |
| | |
| \end{array} \right] & × & \left[ \begin{array} {r}
| |
| | |
| 12 & 19 & 28 \\
| |
| 26 & 43 & 60 \\
| |
| | |
| \end{array} \right] & = & \left[ \begin{array} {r}
| |
| | |
| 2 & 5 & 4 \\
| |
| 0 & 11 & -4 \\
| |
| | |
| \end{array} \right] \end{array}</math>
| |
| | |
| And that's all there is to the Hermite decomposition.
| |
| | |
| ==== inversion by hand ====
| |
| | |
| 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.
| |
| | |
| Here's a random example matrix (well, one I stole from a quick web search, anyway):
| |
| | |
| <math>\left[ \begin{array} {rrr}
| |
| 3 & -2 & 4 \\
| |
| 1 & 0 & 2 \\
| |
| 0 & 1 & 0 \\
| |
| \end{array} \right]</math>
| |
| | |
| The first step is to augment it. Similar to the Hermite decomposition process, we augment it to the right:
| |
| | |
| <math>\left[ \begin{array} {l} \begin{array} {rrr}
| |
| 3 & -2 & 4 \\
| |
| 1 & 0 & 2 \\
| |
| 0 & 1 & 0 \\
| |
| \end{array} & \rule[-7.5mm]{0.375mm}{18mm} & \begin{array} {r}
| |
| 1 & 0 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \end{array} \end{array} \right]</math>
| |
| | |
| Our goal now is to use elementary row operations until the original matrix — the one to the left of the augmentation line — is an identity matrix. At that point, the matrix on the right side of the augmentation line — the one that started out as an identity matrix — will be the inverse of the original matrix. I don't know about you, but for me, this relationship was instantly intuitive and memorable, and I'm super glad I learned how to this one by hand!
| |
| | |
| As our first step, let's rearrange the rows of the matrix. Just some obvious-looking moves (that ''probably'' won't backfire) to get us superficially closer to the identity matrix on the left:
| |
| | |
| <math>\left[ \begin{array} {l} \begin{array} {rrr}
| |
| 1 & 0 & 2 \\
| |
| 0 & 1 & 0 \\
| |
| 3 & -2 & 4 \\
| |
| \end{array} & \rule[-7.5mm]{0.375mm}{18mm} & \begin{array} {r}
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| 1 & 0 & 0 \\
| |
| \end{array} \end{array} \right]</math>
| |
| | |
| Okay, now let's target the bottom-right entry. How can we make that 3 into a 0? Let's subtract the 1st row from the 3rd row 3 times:
| |
| | |
| <math>\left[ \begin{array} {l} \begin{array} {rrr}
| |
| 1 & 0 & 2 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & -2 & -2 \\
| |
| \end{array} & \rule[-7.5mm]{0.375mm}{18mm} & \begin{array} {r}
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| 1 & -3 & 0 \\
| |
| \end{array} \end{array} \right]</math>
| |
| | |
| Okay, let's next target the bottom-center entry. How can we make that -2 into a 0? Let's add the 2nd row to the 3rd row 2 times:
| |
| | |
| <math>\left[ \begin{array} {l} \begin{array} {rrr}
| |
| 1 & 0 & 2 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & -2 \\
| |
| \end{array} & \rule[-7.5mm]{0.375mm}{18mm} & \begin{array} {r}
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| 1 & -3 & 2 \\
| |
| \end{array} \end{array} \right]</math>
| |
| | |
| Next, let's target the top-right entry, making that a 0 by adding the 3rd row to the 1st row:
| |
| | |
| <math>\left[ \begin{array} {l} \begin{array} {rrr}
| |
| 1 & 0 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & -2 \\
| |
| \end{array} & \rule[-7.5mm]{0.375mm}{18mm} & \begin{array} {r}
| |
| 1 & -2 & 2 \\
| |
| 0 & 0 & 1 \\
| |
| 1 & -3 & 2 \\
| |
| \end{array} \end{array} \right]</math>
| |
| | |
| Finally, we just need to divide the 3rd row by -2. Yes, unlike with the Hermite decomposition, all elementary row operations are permitted, including multiplying or dividing rows. And in this case there's no restrictions against non-integers (which we didn't even explicitly mention when doing the HNF, but yes, HNF requires integers). So here's where we end up:
| |
| | |
| <math>\left[ \begin{array} {l} \begin{array} {rrr}
| |
| 1 & 0 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \end{array} & \rule[-7.5mm]{0.375mm}{18mm} & \begin{array} {r}
| |
| 1 & -2 & 2 \\
| |
| 0 & 0 & 1 \\
| |
| -\frac12 & \frac32 & -1 \\
| |
| \end{array} \end{array} \right]</math>
| |
| | |
| As with the Hermite decomposition, we have a convenient way to check our work at the end, which involves matrix multiplication. With Hermite, we verified that left-multiplying our original matrix by the unimodular matrix resulted in the HNF. With inversion, we verify that left-multiplying<ref>or right-multiplying, in this case; it doesn't matter</ref> our original matrix by the inverse results in the identity matrix. And indeed:
| |
| | |
| <math>\begin{array} {1}
| |
| | |
| \left[ \begin{array} {rrr}
| |
| 3 & -2 & 4 \\
| |
| 1 & 0 & 2 \\
| |
| 0 & 1 & 0 \\
| |
| \end{array} \right]
| |
| | |
| & × &
| |
| | |
| \left[ \begin{array} {rrr}
| |
| 1 & -2 & 2 \\
| |
| 0 & 0 & 1 \\
| |
| -\frac12 & \frac32 & -1 \\
| |
| \end{array} \right]
| |
| | |
| & = &
| |
| | |
| \left[ \begin{array} {rrr}
| |
| 1 & 0 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \end{array} \right]
| |
| | |
| \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, {{vector|{{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 ====
| |
| | |
| 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.
| |
| | |
| 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;
| |
| # 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 null-space 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.
| |
| | |
| So, while it's a silly example, let's suppose we want to defactor the mapping {{vector|{{map|6 5 4}} {{map|4 -4 1}}}}. Spoiler alert: it is 11-enfactored:
| |
| | |
| <math>\left[ \begin{array} {rrr}
| |
| 6 & 5 & -4 \\
| |
| 4 & -4 & 1 \\
| |
| \end{array} \right]</math>
| |
| | |
| Our first step is to transpose it:
| |
| | |
| <math>\left[ \begin{array} {rrr}
| |
| 6 & 4 \\
| |
| 5 & -4 \\
| |
| -4 & 1 \\
| |
| \end{array} \right]</math>
| |
| | |
| And now we're going to augment it to the right, so we can do the first step of the Hermite decomposition. But we're actually going to go a bit further. We're going to go ahead and augment it to the right and also augment the augmenting matrix to the bottom, because that's where we're going to perform the next step, which is the inversion. We learned inversion using augmentation to the right, but remember: everything we're doing here is transposed! So augmenting to the bottom is the correct thing to do there. When we're all done, we'll transpose one more time to undo it. (In the Wolfram Language code it was more natural to transpose things between the Hermite decomposition and the inversion, but here I think the process is better illustrated with this rotated-L-shape structure.)
| |
| | |
| <math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
| |
| 6 & 4 \\
| |
| 5 & -4 \\
| |
| -4 & 1 \\
| |
| \end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
| |
| 1 & 0 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \hline
| |
| 1 & 0 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \end{array} \right] \end{array} </math>
| |
| | |
| Alright. So our first goal is to get the top-left matrix into HNF. Let's subtract the 2nd row from the 1st row — that will get us a 1 in the top-left entry, which is what we want if we can.
| |
| | |
| <math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
| |
| 1 & 8 \\
| |
| 5 & -4 \\
| |
| -4 & 1 \\
| |
| \end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
| |
| 1 & -1 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \hline
| |
| 1 & 0 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \end{array} \right] \end{array} </math>
| |
| | |
| Now let's subtract the 1st row from the 2nd row 5 times. That'll get us a 0 below that first pivot, which is what we need.
| |
| | |
| <math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
| |
| 1 & 8 \\
| |
| 0 & -44 \\
| |
| -4 & 1 \\
| |
| \end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
| |
| 1 & -1 & 0 \\
| |
| -5 & 6 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \hline
| |
| 1 & 0 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \end{array} \right] \end{array} </math>
| |
| | |
| Now let's add the 1st row to the 3rd row 4 times. That'll allow us to achieve all 0's below the first pivot.
| |
| | |
| <math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
| |
| 1 & 8 \\
| |
| 0 & -44 \\
| |
| 0 & 33 \\
| |
| \end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
| |
| 1 & -1 & 0 \\
| |
| -5 & 6 & 0 \\
| |
| 4 & -4 & 1 \\
| |
| \hline
| |
| 1 & 0 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \end{array} \right] \end{array} </math>
| |
| | |
| Now let's add the 3rd row to the 2nd row. We can see that if we do that, we'll simplify their relationship. If it's not clear now, it'll be clear in the next step.
| |
| | |
| <math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
| |
| 1 & 8 \\
| |
| 0 & -11 \\
| |
| 0 & 33 \\
| |
| \end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
| |
| 1 & -1 & 0 \\
| |
| -1 & 2 & 1 \\
| |
| 4 & -4 & 1 \\
| |
| \hline
| |
| 1 & 0 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \end{array} \right] \end{array} </math>
| |
| | |
| So now we can add the 2nd row to the 3rd row 3 times, and that'll get the entry below the 2nd pivot to be 0.
| |
| | |
| <math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
| |
| 1 & 8 \\
| |
| 0 & -11 \\
| |
| 0 & 0 \\
| |
| \end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
| |
| 1 & -1 & 0 \\
| |
| -1 & 2 & 1 \\
| |
| 1 & 2 & 4 \\
| |
| \hline
| |
| 1 & 0 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \end{array} \right] \end{array} </math>
| |
| | |
| We can flip the signs of the second row, because we need pivots to be positive.
| |
| | |
| <math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
| |
| 1 & 8 \\
| |
| 0 & 11 \\
| |
| 0 & 0 \\
| |
| \end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
| |
| 1 & -1 & 0 \\
| |
| 1 & -2 & -1 \\
| |
| 1 & 2 & 4 \\
| |
| \hline
| |
| 1 & 0 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \end{array} \right] \end{array} </math>
| |
| | |
| And we've completed the first step!<ref>Note that while the HNF is unique, the unimodular matrix is not. Because the 3rd row of the left matrix — the one in HNF — is all 0's, any number of that row can be added to either of the other two rows without altering the HNF at all, but with affecting the unimodular matrix on the right. Please feel free to experiment yourself, but I expect you will find that the inverse of any matrix you come up with this way, transposed, trimmed, and HNF'd, will give you the same canonical form — no need to worry about the exact path you happen to take to the HNF in the first step.</ref> The original matrix is now in HNF. So the next step is to take the other matrix we've been working on — the unimodular one from the Hermite decomposition — and invert it. Again, since we're in a transposed state, we're going to do the by-hand inversion technique, but to the bottom using elementary column operations rather than to the right using elementary row operations.
| |
| | |
| For our first step, let's add the 1st column to the 2nd column. That will get us a 0 in the top-center entry. Remember, we're trying to get the top-right matrix to look like an identity matrix.
| |
| | |
| <math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
| |
| 1 & 8 \\
| |
| 0 & 11 \\
| |
| 0 & 0 \\
| |
| \end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
| |
| 1 & 0 & 0 \\
| |
| 1 & -1 & -1 \\
| |
| 1 & 3 & 4 \\
| |
| \hline
| |
| 1 & 1 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \end{array} \right] \end{array} </math>
| |
| | |
| Now let's add the new 2nd column back to the 1st column. This will get the entry in the center-left to be 0.
| |
| | |
| <math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
| |
| 1 & 8 \\
| |
| 0 & 11 \\
| |
| 0 & 0 \\
| |
| \end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
| |
| 1 & 0 & 0 \\
| |
| 0 & -1 & -1 \\
| |
| 4 & 3 & 4 \\
| |
| \hline
| |
| 2 & 1 & 0 \\
| |
| 1 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \end{array} \right] \end{array} </math>
| |
| | |
| Now let's subtract the 2nd column from the 3rd column. This is sweet because it gets the center-right entry to be 0 as well as the bottom-right entry to be 1. A twofer! Plus it gives us our first column which has all zeros except for one row, which gives us the power to affect the entry in that row of other columns without messing up any of the other rows of those columns.
| |
| | |
| <math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
| |
| 1 & 8 \\
| |
| 0 & 11 \\
| |
| 0 & 0 \\
| |
| \end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
| |
| 1 & 0 & 0 \\
| |
| 0 & -1 & 0 \\
| |
| 4 & 3 & 1 \\
| |
| \hline
| |
| 2 & 1 & -1 \\
| |
| 1 & 1 & -1 \\
| |
| 0 & 0 & 1 \\
| |
| \end{array} \right] \end{array} </math>
| |
| | |
| Okay. So if we now subtract the 3rd column from the 1st column 4 times, we can get the bottom-left entry to be a 0.
| |
| | |
| <math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
| |
| 1 & 8 \\
| |
| 0 & 11 \\
| |
| 0 & 0 \\
| |
| \end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
| |
| 1 & 0 & 0 \\
| |
| 0 & -1 & 0 \\
| |
| 0 & 3 & 1 \\
| |
| \hline
| |
| 6 & 1 & -1 \\
| |
| 5 & 1 & -1 \\
| |
| -4 & 0 & 1 \\
| |
| \end{array} \right] \end{array} </math>
| |
| | |
| And now we can subtract the 3rd column from the 2nd column 3 times, so we can get the bottom-center entry to be a 0.
| |
| | |
| <math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
| |
| 1 & 8 \\
| |
| 0 & 11 \\
| |
| 0 & 0 \\
| |
| \end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
| |
| 1 & 0 & 0 \\
| |
| 0 & -1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \hline
| |
| 6 & 4 & -1 \\
| |
| 5 & 4 & -1 \\
| |
| -4 & -3 & 1 \\
| |
| \end{array} \right] \end{array} </math>
| |
| | |
| As our last step to achieve an identity matrix in the top-right matrix, let's just flip the signs of the 2nd column:
| |
| | |
| <math> \begin{array} {l} \begin{array} {l} \left[ \begin{array} {rrr}
| |
| 1 & 8 \\
| |
| 0 & 11 \\
| |
| 0 & 0 \\
| |
| \end{array} \right. \\ \begin{array} {l} \\ \\ \\ \end{array} \end{array} & \rule[2.5mm]{0.375mm}{18mm} & \left. \begin{array} {r}
| |
| 1 & 0 & 0 \\
| |
| 0 & 1 & 0 \\
| |
| 0 & 0 & 1 \\
| |
| \hline
| |
| 6 & -4 & -1 \\
| |
| 5 & -4 & -1 \\
| |
| -4 & 3 & 1 \\
| |
| \end{array} \right] \end{array} </math>
| |
| | |
| And so we've inverted the Hermite unimodular matrix. That's our result in the bottom-right matrix, isolated here:
| |
| | |
| <math>\left[ \begin{array} {rrr}
| |
| 6 & -4 & -1 \\
| |
| 5 & -4 & -1 \\
| |
| -4 & 3 & 1 \\
| |
| \end{array} \right]</math>
| |
| | |
| But we're not quite to our defactored result. We're very close though! All we've got to do now is take that result and transpose it, to get us out of the transposed state we've been in (in other words, flip every entry across the main diagonal, running from the top-left entry to the bottom-right entry):
| |
| | |
| <math>\left[ \begin{array} {rrr}
| |
| 6 & 5 & -4 \\
| |
| -4 & -4 & 3 \\
| |
| -1 & -1 & 1 \\
| |
| \end{array} \right]</math>
| |
| | |
| And we take from this thing the top <span><math>r</math></span> rows, where <span><math>r</math></span> is the rank of the input matrix, which in this case is 2:
| |
| | |
| <math>\left[ \begin{array} {rrr}
| |
| 6 & 5 & -4 \\
| |
| -4 & -4 & 3 \\
| |
| \end{array} \right]</math>
| |
| | |
| 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 {{vector|{{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 {{vector|{{map|6 5 -4}} {{map|4 -4 1}}}} to {{vector|{{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 {{vector|{{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}
| |
| 1 & 8 \\
| |
| 0 & 11 \\
| |
| 0 & 0 \\
| |
| \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 {{vector|{{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 {{vector|{{map|6 5 -4}} {{map|4 -4 1}}}} mapping the other direction like {{map|{{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 details to report =
| |
| | |
| The rest of the material in this article is not strictly necessary to understand canonical form and defactoring, but for posterity the work Dave and Douglas did to attain their insights has been summarized here in case it may be helpful to anyone else who might want to iterate on this later.
| |
| | |
| == criteria ==
| |
| | |
| In addition to being canonical and defactored, DCF has other important properties, which probably go without saying in the context of RTT mappings, but here they are just in case:
| |
| * '''integer''': contains only integer terms.
| |
| * '''full-rank'''<ref>Interesting tidbit regarding full-rank matrices and unimodular matrices: for square matrices, full-rank implies unimodularity, and vice-versa.</ref>: removes rank deficiencies, or in other words, rows that are all zeros (upon any linear combination of rows)
| |
| * '''preserves genuine unit-fraction-of-an-prime periods''': at first glance, when a pivot is not equal to 1, it might trigger you to think that the mapping is enfactored. But temperaments can legitimately have generators that divide primes evenly, such as 5-limit Blackwood, {{vector|{{map|5 8 0}} {{map|0 0 1}}}}, which divides the octave into 5 parts.<ref>Any form that enforces pivots all be 1's would fail this criteria.</ref>
| |
| | |
| === exclusion of generator size target criteria; mingen form ===
| |
| | |
| Initially, Dave and Douglas considered the proposal of a new standard RTT mapping form as an opportunity to include everything and the kitchen sink — in this case, to additionally massage generator sizes to fit a desirable rubric. It was ultimately decided to stay conceptually focused when drafting the proposal, leaving generator size out of the mix. Also, the particular generator size target they sought — named "mingen" — turned out to be a bit of a rabbit hole, especially above rank-2, both in terms of mathematical reality and engineering practicality. The results of those efforts are documented here: [[Generator size manipulation#mingen_form]]
| |
| | |
| == relationship between various matrix echelon forms ==
| |
| | |
| There are several well-known echelon forms for matrices that predate DCF. Let's review them and their properties.
| |
| | |
| === REF ===
| |
| | |
| The most general form, with the fewest constraints, is simply called '''[https://en.wikipedia.org/wiki/Row_echelon_form Row Echelon Form]''', or '''REF'''. Its only constraint is ''echelon<ref>The name "echelon" is a French word for a military troop formation with a similar triangular shape: https://en.wikipedia.org/wiki/Echelon_formation.</ref> form'': each row's pivot, or first nonzero entry, is strictly to the right of the preceding row's pivot. This single constraint is fairly weak, and therefore REF does not produce a unique representation. This constraint is shared by every matrix form discussed here.<ref>Note that the definition of REF is inconsistent and sometimes it includes some of the constraints of RREF, discussed further below. See: https://www.statisticshowto.com/matrices-and-matrix-algebra/reduced-row-echelon-form-2/</ref><ref>REF also requires that all rows that are entirely zeros should appear at the bottom of the matrix. However this rule is only relevant for rank-deficient matrices. We'll be assuming all matrices here are full-rank, so we don't have to worry about this.</ref>
| |
| | |
| In the below example, <span><math>x_{ij}</math></span> represents any number.
| |
| | |
| {| class="wikitable" style="text-align: center;"
| |
| |+REF
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₁₁
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₁₂
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₁₃
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₁₄
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₁₅
| |
| |-
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₂₂
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₂₃
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₂₄
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₂₅
| |
| |-
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₃₄
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₃₅
| |
| |}
| |
| | |
| === IREF ===
| |
| | |
| '''[https://people.sc.fsu.edu/~jburkardt/f_src/row_echelon_integer/row_echelon_integer.html Integer Row Echelon Form]''', or '''IREF''', is, unsurprisingly, any REF which meets an additional ''integer'' constraint, or in other words, that all of its entries are integers. This is still not a sufficiently strict set of constraints to ensure a unique representation.
| |
| | |
| In the below example, <span><math>n_{ij}</math></span> represents any number.
| |
| | |
| {| class="wikitable" style="text-align: center;"
| |
| |+IREF
| |
| |style="width: 25px; background-color: #93c47d;"|n₁₁
| |
| |style="width: 25px; background-color: #93c47d;"|n₁₂
| |
| |style="width: 25px; background-color: #93c47d;"|n₁₃
| |
| |style="width: 25px; background-color: #93c47d;"|n₁₄
| |
| |style="width: 25px; background-color: #93c47d;"|n₁₅
| |
| |-
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #93c47d;"|n₂₂
| |
| |style="width: 25px; background-color: #93c47d;"|n₂₃
| |
| |style="width: 25px; background-color: #93c47d;"|n₂₄
| |
| |style="width: 25px; background-color: #93c47d;"|n₂₅
| |
| |-
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #93c47d;"|n₃₄
| |
| |style="width: 25px; background-color: #93c47d;"|n₃₅
| |
| |}
| |
| | |
| === RREF ===
| |
| | |
| '''[https://en.wikipedia.org/wiki/Row_echelon_form#Reduced_row_echelon_form Reduced Row Echelon Form]''', or '''RREF''', takes REF in a different direction than IREF. Instead of stipulating anything about integers, it requires that the matrix is ''reduced'', i.e. that the pivots are exactly equal to 1. This may require dividing rows by a number such that some resulting entries are no longer integers. Actually, there's a second part to the "reduced" constraint: each pivot column (a column which contains any row's pivot) has zeros for all other entries besides the pivot it contains. Due to these strict constraints, the RREF of a matrix is the first one we've looked at so far here which does ensure uniqueness.
| |
| | |
| {| class="wikitable" style="text-align: center;"
| |
| |+RREF
| |
| |style="width: 25px; background-color: #d9ead3;"|1
| |
| |style="width: 25px; background-color: #93c47d;"|0
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₁₃
| |
| |style="width: 25px; background-color: #93c47d;"|0
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₁₅
| |
| |-
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #d9ead3;"|1
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₂₃
| |
| |style="width: 25px; background-color: #93c47d;"|0
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₂₅
| |
| |-
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #d9ead3;"|1
| |
| |style="width: 25px; background-color: #6d9eeb;"|x₃₅
| |
| |}
| |
| | |
| So IREF and RREF make a [https://en.wikipedia.org/wiki/Venn_diagram Venn diagram] inside the category of REF: some IREF are RREF, but there are some RREF that are not IREF and some IREF that are not RREF. When we scope the situation to a specific matrix, however, because RREF is a unique form, this means that one or the other sector of the Venn diagram for RREF will be empty; either the unique RREF will also be IREF (and therefore the RREF-but-not-IREF sector will be empty), or it will not be IREF (and vice versa).
| |
| | |
| === IRREF ===
| |
| | |
| '''[[Normal_lists|Integer Reduced Row Echelon Form]]''', or '''IRREF''': based on the name, one might expect this form to be a combination of the constraints for RREF and IREF, and therefore if represented in an [https://en.wikipedia.org/wiki/Euler_diagram Euler diagram] (generalization of Venn diagram) would only exist within their intersection. However this is not the case. That's because the IRREF does not include the key constraint of RREF which is that all of the pivots must be 1. IRREF is produced by simply taking the unique RREF and multiplying each row by whatever minimum value is necessary to make all of the entries integers<ref>Alternatively, IRREF can be computed by finding the null-space of a mapping, or in other words, the corresponding comma-basis for the temperament represented by the mapping, and then in turn taking the null-space of the comma-basis to get back to an equivalent mapping. The relationship between the process for finding the IRREF from the RREF and this process is not proven, but thousands of automated tests run as an experiment strongly suggest that these two techniques are equivalent.<br>
| |
| <span style="font-family: monospace; font-size: 10px;"><br>
| |
| rref[m_] := RowReduce[m]<br>
| |
| multByLcd[row_] := Apply[LCM,Denominator[row]]*row<br>
| |
| irref[m_] := Map[multByLcd,rref[m]]<br>
| |
| <br>
| |
| nullSpaceAndBack[m_]:=Reverse[NullSpace[Reverse[NullSpace[m],2]],2]<br>
| |
| <br>
| |
| <br>
| |
| output = "";<br>
| |
| Do[<br>
| |
| d = RandomInteger[{2,6}];<br>
| |
| r = RandomInteger[{1,d-1}];<br>
| |
| m = RandomInteger[{-99,99},{r,d}];<br>
| |
| <br>
| |
| n = nullSpaceAndBack[m];<br>
| |
| i = irref[m];<br>
| |
| <br>
| |
| If[n!=i,output = output <> "bad" <> n <> i, output = output <> "ok "],<br>
| |
| 10000<br>
| |
| ]<br>
| |
| <br>
| |
| Print[output] <br>
| |
| <br></span><br>
| |
| There is a difference in that IRREF does not remove rows of zeros in the end for rank-deficient mappings, while this "null-space'n'back" does, but for most normal cases, they're the same.
| |
| </ref>. Of course, this sometimes results in the pivots no longer being 1, so sometimes it is no longer RREF. It is always still REF, though<ref>Also, it will always still satisfy the second aspect of reduced, i.e. that all other entries in pivot columns besides the pivots are zeroes.</ref>, and because it is also always integer, that makes it always IREF; therefore, IRREF is strictly a subcategory of IREF. And because the RREF is unique, and the conversion process does not alter that, the IRREF is also unique.
| |
| | |
| {| class="wikitable" style="text-align: center;"
| |
| |+IRREF
| |
| |style="width: 25px; background-color: #93c47d;"|n₁₁
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #93c47d;"|n₁₃
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #93c47d;"|n₁₅
| |
| |-
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #93c47d;"|n₂₂
| |
| |style="width: 25px; background-color: #93c47d;"|n₂₃
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #93c47d;"|n₂₅
| |
| |-
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #93c47d;"|n₃₄
| |
| |style="width: 25px; background-color: #93c47d;"|n₃₅
| |
| |}
| |
| | |
| The multiplication of rows by whatever integer is required to clear the denominators of the RREF form is the action which is responsible for causing enfactoring, whenever the IRREF produces an enfactored mapping from a defactored one.
| |
| | |
| It is not possible for an RREF to be IREF without also being IRREF.
| |
| | |
| === HNF ===
| |
| | |
| '''[https://en.wikipedia.org/wiki/Hermite_normal_form Hermite Normal Form]''', or '''HNF''': this one's constraints begin with echelon form and integer, therefore every HNF is also IREF. But HNF is not exactly reduced (as discussed above; [[canonical_form#RREF|link here]]); instead, it is ''normalized'', which — similarly to reduced — is a two-part constraint. Where reduced requires that all pivots be exactly equal to 1, normalized requires only that all pivots be positive (positive integers, of course, due to the other integer constraint). And where reduced requires that all entries in pivot columns besides the pivots are exactly equal to 0, normalized requires only that all entries in pivot columns below the pivots are exactly equal to 0, while entries in pivot columns above the pivots only have to be strictly less than the pivot in the respective column (while still being non-negative).<ref>The exact criteria for HNF are not always consistently agreed upon, however.</ref><ref>There is also a rarely mentioned Hermite Canonical Form, or HCF, described here: http://home.iitk.ac.in/~rksr/html/03CANONICALFACTORIZATIONS.htm, which sort of combines the HNF's normalization constraint and the RREF's reduced constraint (all pivots equal 1, all other entries in pivot columns are 0, both above and below the pivot), but we didn't find it useful because due to its constraint that all pivots be 1, it does not preserve periods that are genuinely unit fractions of an octave. It also doesn't qualify as an echelon form, which becomes apparent only when you use it on rank-deficient matrices, because it doesn't require the rows of all zeros to be at the bottom; instead it (bizarrely, though maybe it's related to how the SNF requires all pivots exactly along the main diagonal) requires the rows to be sorted so that all the pivots fall on the main diagonal.</ref><ref>We are using "row-style" Hermite Normal Form here, not "column-style"; the latter would involve simply flipping everything 90 degrees so that the echelon requirement was that pivots be strictly ''below'' the pivots in the previous ''column'', and that pivot ''rows'' are considered for the normalization constraint rather than pivot ''columns''.</ref> In other words, elements above the pivot have to be reduced modulo the pivot. The normalization HNF uses is cool because this constraint, while strictly less strict than the reduced constraint used by RREF, is still strict enough to ensure uniqueness, but loose enough to ensure the integer constraint can be simultaneously satisfied, where RREF cannot ensure that.
| |
| | |
| So HNF has a lot in common with IRREF, which is the IREF you find by converting the RREF, but it is not always the same as IRREF.
| |
| | |
| === DCF ===
| |
| | |
| '''Defactored Canonical Form''', or '''DCF''' (listed here not because it predates itself of course, but for completeness) is closely related to HNF, because the second step of finding the DCF is taking the HNF. So the DCF is always ''a'' HNF, and therefore it has all the same properties of being echelon, integer, and normalized, and in turn therefore it also provides a unique representation. However it is not necessary ''the'' same HNF of the original mapping, due to the first step being defactoring; it is the same as as HNF except when the original mapping is enfactored.
| |
| | |
| In the below example, <span><math>p_{ij}</math></span> represents any positive integer, and <span><math>a_{ij}</math></span> represents any nonnegative integer less than the <span><math>p</math></span> in its column.
| |
| | |
| {| class="wikitable" style="text-align: center;"
| |
| |+HNF and DFC
| |
| |style="width: 25px; background-color: #e69138;"|p₁₁
| |
| |style="width: 25px; background-color: #ffe599;"|a₁₂
| |
| |style="width: 25px; background-color: #93c47d;"|n₁₃
| |
| |style="width: 25px; background-color: #ffe599;"|a₁₄
| |
| |style="width: 25px; background-color: #93c47d;"|n₁₅
| |
| |-
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #e69138;"|p₂₂
| |
| |style="width: 25px; background-color: #93c47d;"|n₂₃
| |
| |style="width: 25px; background-color: #ffe599;"|a₂₄
| |
| |style="width: 25px; background-color: #93c47d;"|n₂₅
| |
| |-
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #e69138;"|p₃₄
| |
| |style="width: 25px; background-color: #93c47d;"|n₃₅
| |
| |}
| |
| | |
| === SNF ===
| |
| | |
| There is also the '''[https://en.wikipedia.org/wiki/Smith_normal_form Smith Normal Form]''', or '''SNF''', but we won't be discussing it in this context, because putting a mapping into SNF obliterates a lot of meaningful RTT information. SNF is also echelon, and integer, so like HNF it is also always IREF. But SNF requires that every single entry other than the pivots are zero, and that the pivots all fall exactly along the main diagonal of the matrix. The SNF essentially reduces a matrix down to the information of what its rank is and whether it is enfactored. For example, all 5-limit rank-2 temperaments such as meantone, porcupine, mavila, hanson, etc. have the same SNF: {{vector|{{map|1 0 0}} {{map|0 1 0}}}}. Or, if you 2-enfactor them, they will all have the SNF {{vector|{{map|1 0 0}} {{map|0 2 0}}}}. So while the SNF is closely related to defactoring, it is not itself a useful form to put mappings into.<ref>Here is a useful resource for computing the Smith Normal Form manually, if you are interested: https://math.stackexchange.com/questions/133076/computing-the-smith-normal-form The fact that it involves calculating so many GCDs is unsurprising given its ability to defactor matrices.</ref>
| |
| | |
| {| class="wikitable" style="text-align: center;"
| |
| |+SNF
| |
| |style="width: 25px; background-color: #e69138;"|p₁₁
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |-
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #e69138;"|p₂₂
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |-
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #e69138;"|p₃₃
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |style="width: 25px; background-color: #274e13;"|0
| |
| |}
| |
| | |
| == cases temperaments can be regarding which of their mapping forms equal each other ==
| |
| | |
| [[File:Cases for temperament mapping forms3.png|300px|thumb|right]]
| |
| Considering only full-rank, integer mappings, we find three cases for a given temperament which is not enfactored. In all three cases, HNF is the same as DCF:
| |
| # The RREF, IRREF, and HNF are all ''different''. Example: [[Porcupine_family#Porcupine|porcupine]] with RREF of {{vector|{{map|1 0 <span><math>-\frac13</math></span>}} {{map|0 1 <span><math>\frac53</math></span>}}}}, IRREF of {{vector|{{map|3 0 -1}} {{map|0 3 5}}}}, and HNF of {{vector|{{map|1 2 3}} {{map|0 3 5}}}}.
| |
| # The RREF, IRREF, HNF are all ''the same''. Example: [[Meantone_family#Meantone_.2812.2619.2C_2.3.5.29|meantone]] with all equal to {{vector|{{map|1 0 -4}} {{map|0 1 4}}}}. This case is quite rare.
| |
| # The IRREF and HNF are the same, but the ''RREF is different''. Example: [[Kleismic_family#Hanson|hanson]] with IRREF and HNF of {{vector|{{map|1 0 1}} {{map|0 6 5}}}} but RREF of {{vector|{{map|1 0 1}} {{map|0 1 <span><math>\frac56</math></span>}}}}.
| |
| | |
| And there are three corresponding cases when a temperament is enfactored. In all three cases, the key difference is that HNF is no longer the same as DCF, with the only difference being that the common factor is not removed. In all cases below, the examples are shown with a common factor of 2 introduced in their second row, which stays behind in the second row of the HNF:
| |
| # Now ''all four'' are different. Example: enfactored porcupine, e.g. {{vector|{{map|15 24 35}} {{map|14 22 32}}}} causes the HNF to be {{vector|{{map|1 2 3}} {{map|0 6 10}}}}.
| |
| # Everything is still the same now, ''except HNF''. Example: enfactored meantone, e.g. {{vector|{{map|5 8 12}} {{map|14 22 32}}}} causes the HNF to be {{vector|{{map|1 0 -4}} {{map|0 2 8}}}}. This case, like the corresponding unenfactored state, is also quite rare.
| |
| # The ''only match'' now is between IRREF and DCF. In other words, the HNF and DCF diverged, and it was the DCF which remained the same as IRREF. Example: enfactored hanson, e.g. {{vector|{{map|15 24 35}} {{map|38 60 88}}}} causes the HNF to be {{vector|{{map|1 0 1}} {{map|0 12 10}}}}.
| |
| | |
| There is also a final case which is incredibly rare. It can be compared to the #3 cases above, the ones using hanson as their example. The idea here is that when the HNF and DCF diverge, instead of DCF remaining the same as IRREF, it's the HNF that remains the same as IRREF. There may be no practical temperoids with this case, but {{vector|{{map|165 264 393}} {{map|231 363 524}}}} will do it<ref>AKA 165b⁴c¹⁹&231b⁶c²⁴, which tempers out the 7.753¢ comma {{vector|-131 131 -33}}!</ref>, with IRREF and HNF of {{vector|{{map|33 0 -131}} {{map|0 33 131}}}}, DCF of {{vector|{{map|1 1 0}} {{map|0 33 131}}}}, and RREF of {{vector|{{map|1 0 <span><math>\frac{-131}{33}</math></span>}} {{map|0 1 <span><math>\frac{131}{33}</math></span>}}}}.
| |
| | |
| That accounts for 7 of the 15 total possible cases for a system of equalities between 4 entities. The remaining 9 cases are impossible due to properties of the domain:
| |
| * If HNF equals RREF, then the pivots of HNF are all 1's, which means the temperament is not enfactored, which means HNF also equals DCF. This eliminates 3 cases: HNF=RREF; HNF=RREF,HNF=IRREF,RREF=IRREF; HNF=RREF,IRREF=DCF.
| |
| * If RREF equals DCF, then RREF must be integer, which means RREF must also equal IRREF. This eliminates 3 cases: RREF=DCF; RREF=DCF,HNF=RREF,HNF=DCF; RREF=DCF,HNF=IRREF.
| |
| * The case where the only equality is between RREF and IRREF would only be possible when the temperament is both enfactored and rank-deficient, such as {{vector|{{map|0 0 0}} {{map|2 4 6}}}} which gives to HNF, RREF, IRREF, and DCF of {{vector|{{map|2 4 6}} {{map|0 0 0}}}}, {{vector|{{map|1 2 3}} {{map|0 0 0}}}}, {{vector|{{map|1 2 3}} {{map|0 0 0}}}}, and {{vector|{{map|1 2 3}}}}, respectively.
| |
| * The case where the only equalities are between RREF and IRREF and between HNF and DCF is impossible, because if RREF=IRREF that suggests that all entries are multiples of their pivots, which is easy if the temperament is enfactored, but if HNF=DCF then it is not.
| |
| | |
| == SAD (sum-and-difference) defactoring ==
| |
| | |
| When in development on an ideal defactoring method — the effort which culminated in column Hermite defactoring — Dave and Douglas invested a great deal of time in a defactoring method which still has some advantages over column Hermite defactoring but was ultimately rejected. This other method is called '''"sum-and-difference" defactoring''', or '''SAD defactor''' (it is sad partially because it didn't work out).
| |
| | |
| SAD defactoring's key advantage over column Hermite defactoring is that its mechanism for removing common factors is more straightforward to see and understand, as we will see in the next section.
| |
| | |
| SAD defactoring's key reason for rejection is that a number of edge cases were discovered that caused its algorithm to balloon in complexity, both insofar as it could be implemented in code as well as understood by humans.
| |
| | |
| === 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
| |
| | |
| * A
| |
| * B
| |
| * C
| |
| * A+B
| |
| * A-B
| |
| * A+C
| |
| * A-C
| |
| * B+C
| |
| * B-C
| |
| * A+B+C
| |
| * A+B-C
| |
| * A-B+C
| |
| * A-B-C
| |
| | |
| In other words, for each of A, B, and C, you have to check -1 of it, 0 of it, or 1 of it. You don't need to check any counts less than -1 or greater than 1, because then you'd of course be introducing a common factor to the mapping!
| |
| | |
| Anyway, the point is, if any of these combinations has a common factor, you simply remove the common factor, then replace a row in the mapping with this combined-and-defactored row.
| |
| | |
| === problem 1. edge case: multiple common factors ===
| |
| | |
| Some matrices can have multiple common factors, such as {{vector|{{map|17 16 -4} {{map|4 -4 1}}}}. The SNF of this mapping is {{vector|{{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 ===
| |
| | |
| SAD defactoring was found to fail in the case of [[canonical_form#well-hidden_enfactoring|well-hidden common factor]]s, i.e.
| |
| 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. 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 reveal it. For example, in the case of {{vector|{{map|6 5 -4}} {{map|4 -4 1}}}}, the HNF is {{vector|{{map|2 9 -5}} {{map|0 22 -11}}}}, so that hidden common factor of 11 has now been revealed, put in a form where SAD 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.
| |
| | |
| === problem 3. picking the correct row to replace ===
| |
| | |
| Initially it was thought that, upon finding a common factor in a combination of rows and removing it, it would be acceptable to replace any row of the mapping with the fixed row, and that we could then simply replace the first row. However this is not the case. When replacing a row with a defactored sum or difference, the replaced row has to be one of those involved in the sum or difference. It can always be the topmost one of those, but it can't always be the topmost row of the matrix. So this increases the complexity of the algorithm.
| |
| | |
| === problem 4. failure to remove rank-deficient rows ===
| |
| | |
| The way Smith defactoring works, and column Hermite defactoring works, a step which ensures that the final number of rows of the output is equal to the rank is built into how the core of the implementation works already. However, for SAD defactoring, a special extra pass is required to ensure this.
| |
| | |
| At this point, SAD defactor was considered "a mess".
| |
| | |
| === Wolfram Language implementation ===
| |
| | |
| 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 wasn't quite quashed.
| |
| | |
| <nowiki>
| |
| confirmEnfactoredRowReplaced[m_] := Module[{i, enfactoredRowReplaced},
| |
| enfactoredRowReplaced = True;
| |
| For[i = 1, i <= Length[m], i++,
| |
| If[Apply[GCD, m[[i]]] > 1, enfactoredRowReplaced = False]
| |
| ];
| |
| enfactoredRowReplaced
| |
| ];
| |
| | |
| handleEnfactored[m_, maybeDisarmedRow_] := Module[{defactored, attemptedReplacementOfEnfactoredRow, i, enfactoredRowReplaced},
| |
| For[i = 1, i <= Length[m], i++,
| |
| attemptedReplacementOfEnfactoredRow = Prepend[Drop[m, {i}], First[maybeDisarmedRow]];
| |
| enfactoredRowReplaced = confirmEnfactoredRowReplaced[attemptedReplacementOfEnfactoredRow];
| |
| If[enfactoredRowReplaced, defactored = enhancedSadDefactor[attemptedReplacementOfEnfactoredRow]];
| |
| ];
| |
| defactored
| |
| ];
| |
| | |
| enhancedSadDefactor[m_] := Module[{mNoAllZeros, reduced, linCombs, linCombsDisarmed, maybeDisarmedRow},
| |
| mNoAllZeros = removeAllZeroRows[m];
| |
| linCombs = linCombsToCheck[mNoAllZeros];
| |
| linCombsDisarmed = Map[extractGcd, linCombs];
| |
| maybeDisarmedRow = Complement[linCombsDisarmed, linCombs];
| |
| If[Length[maybeDisarmedRow] == 0, mNoAllZeros, handleEnfactored[mNoAllZeros, maybeDisarmedRow]]
| |
| ];</nowiki>
| |
| | |
| == MADAM (minors and divide-out-GCD, anti- minors) defactoring ==
| |
| | |
| Another technique which was experimented with took advantage of the fact that the list of minor determinants (or simply "minors") of a mapping is guaranteed to include any common factor as its entries' GCD. So, if one simply converted a mapping to its list of minors, removed the GCD (at which point you would have what in RTT is called a [[User:Cmloegcmluin/RTT_How-To#multimaps|canonical multimap]], or [[wedgie]]), and then performed an "anti-minors" operation to get back to a mapping form, any common factors should be removed.
| |
| | |
| Inspired by Gene Ward Smith's method for computing anti-minors as described [[Mathematical_theory_of_regular_temperaments#Wedgies|here]] and [[Basic_abstract_temperament_translation_code|here]], an anti-minors method was implemented in Wolfram Language. It was found that a defactoring algorithm based on '''M'''inors '''A'''nd '''D'''ivide-out-GCG, '''A'''nti-'''M'''inors, or '''MADAM defactoring''', does indeed work. However, it runs 10 to 20 times slower than Smith defactoring and column Hermite defactoring, and it is not compellingly easier to understand than either of them, so it is not considered to be of significant interest.
| |
| | |
| = references =
| |