Graph-theoretic properties of scales: Difference between revisions
Wikispaces>genewardsmith **Imported revision 359126205 - Original comment: ** |
Wikispaces>genewardsmith **Imported revision 359129583 - Original comment: ** |
||
| Line 1: | Line 1: | ||
<h2>IMPORTED REVISION FROM WIKISPACES</h2> | <h2>IMPORTED REVISION FROM WIKISPACES</h2> | ||
This is an imported revision from Wikispaces. The revision metadata is included below for reference:<br> | This is an imported revision from Wikispaces. The revision metadata is included below for reference:<br> | ||
: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-22 | : This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-22 02:06:38 UTC</tt>.<br> | ||
: The original revision id was <tt> | : The original revision id was <tt>359129583</tt>.<br> | ||
: The revision comment was: <tt></tt><br> | : The revision comment was: <tt></tt><br> | ||
The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.<br> | The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.<br> | ||
| Line 23: | Line 23: | ||
These properties can be also expressed in terms of the roots of the characteristic polynomial, which are the eigenvalues of the matrix. These roots are real numbers, some of which may be multiple. The //spectrum// of G is the [[http://en.wikipedia.org/wiki/Multiset|multiset]] of roots, including multipicities, so that some roots may be repeated. From [[http://en.wikipedia.org/wiki/Newton's_identities|Newton's identities]] we can also say that the sum of the squares of the spectrum is twice the number of edges of the graph, which means twice the number of dyads of the scale, and the sum of the cubes of the spectrum is six times the number of triads of the scale. In terms of the adjacency matrix A, the number of dyads is tr(A^2)/2 and the number of triads is tr(A^3)/6, where "tr" denotes the trace. Since tr(A^2)/V, where V is the degree (number of notes) is the variance of the spectrum, we can see we prefer the variance to be larger rather than smaller. Also, tr(A^3)/V divided by the 3/2 power of the variance is the skewness of the spectrum, from which we can conclude we want the skewness to skew positive. | These properties can be also expressed in terms of the roots of the characteristic polynomial, which are the eigenvalues of the matrix. These roots are real numbers, some of which may be multiple. The //spectrum// of G is the [[http://en.wikipedia.org/wiki/Multiset|multiset]] of roots, including multipicities, so that some roots may be repeated. From [[http://en.wikipedia.org/wiki/Newton's_identities|Newton's identities]] we can also say that the sum of the squares of the spectrum is twice the number of edges of the graph, which means twice the number of dyads of the scale, and the sum of the cubes of the spectrum is six times the number of triads of the scale. In terms of the adjacency matrix A, the number of dyads is tr(A^2)/2 and the number of triads is tr(A^3)/6, where "tr" denotes the trace. Since tr(A^2)/V, where V is the degree (number of notes) is the variance of the spectrum, we can see we prefer the variance to be larger rather than smaller. Also, tr(A^3)/V divided by the 3/2 power of the variance is the skewness of the spectrum, from which we can conclude we want the skewness to skew positive. | ||
The epitome of these properties is found in the complete graph, which in scale terms means every note is in consonant relation with every other--in other words, the scale is a dyadic chord. This has a spectrum with V-1 values of -1 and one of V-1. The [[http://en.wikipedia.org/wiki/Distance_(graph_theory)|distance]] between two vertices (notes) is the number of edges (consonant intervals) of the shortest path between then, and the [[http://mathworld.wolfram.com/GraphDiameter.html|diameter]] of a graph is the length of the greatest distance between two vertices. The diameter of a compete graph is 1, and in general a small diameter is another desirable quality. A graph with diameter d must have at least d+1 distinct values in the spectrum. | The epitome of these properties is found in the complete graph, which in scale terms means every note is in consonant relation with every other--in other words, the scale is a dyadic chord. This has a spectrum with V-1 values of -1 and one of V-1. The [[http://en.wikipedia.org/wiki/Distance_(graph_theory)|distance]] between two vertices (notes) is the number of edges (consonant intervals) of the shortest path between then, and the [[http://mathworld.wolfram.com/GraphDiameter.html|diameter]] of a graph is the length of the greatest distance between two vertices, while the radius is the minimax distance--the minimum over all vertices of its maximum distance to any other vertex. The diameter of a compete graph is 1, and in general a small diameter is another desirable quality. A graph with diameter d must have at least d+1 distinct values in the spectrum. | ||
=The Laplace Spectrum= | =The Laplace Spectrum= | ||
| Line 33: | Line 33: | ||
=The Genus= | =The Genus= | ||
A graph is [[http://en.wikipedia.org/wiki/Planar_graph|planar]] if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable [[http://en.wikipedia.org/wiki/Compact_space|compact]][[http://en.wikipedia.org/wiki/Orientability|orientable]] [[http://en.wikipedia.org/wiki/Surface|surface]] with "donut holes", which we may view as a closed and bounded surface in 3 dimensional Euclidean space. If a surface has g holes, it is of [[http:// | A graph is [[http://en.wikipedia.org/wiki/Planar_graph|planar]] if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable [[http://en.wikipedia.org/wiki/Compact_space|compact]][[http://en.wikipedia.org/wiki/Orientability|orientable]] [[http://en.wikipedia.org/wiki/Surface|surface]] with "donut holes", which we may view as a closed and bounded surface in 3 dimensional Euclidean space. If a surface has g holes, it is of [[http://mathworld.wolfram.com/GraphGenus.html|genus]] g, where the sphere (or plane) has genus 0. The minimum number of holes needed to draw the graph is the genus of the graph. | ||
Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is [[http://en.wikipedia.org/wiki/NP-complete|NP-complete]]. However, finding bounds on the genus is a much easier problem. For small enough scales, the genus routine of [[http://www.sagemath.org/|SAGE]] can manage to finish computing after an acceptable amount of time. | Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is [[http://en.wikipedia.org/wiki/NP-complete|NP-complete]]. However, finding bounds on the genus is a much easier problem. For small enough scales, the genus routine of [[http://www.sagemath.org/|SAGE]] can manage to finish computing after an acceptable amount of time. | ||
If the genus is g, the graph can also be drawn on any surface of genus greater than g; one way to accomplish that, but not the only way, is simply not to use more than g of the holes--that is, not to draw an edge passing through it. In fact, beyond a certain point you would not be able to use all of the holes and would have to leave some without edges drawn through them. The maximum number of holes, all of which can actually be used by having an edge pass through them, is called the maximal genus an is another invariant of the graph. | |||
A 5-limit JI scale, meaning a scale composed of 5-limit JI intervals such that {6/5, 5/4, 4/3, 3/2, 8/5, 5/3} is the consonance set, is always planar. This because the [[http://xenharmonic.wikispaces.com/file/detail/hexagonal-lattice.gif|hexagonal lattice]] of 5-limit pitch classes is planar, and the graph of any scale will simply be a finite subgraph of that lattice, considered as a graph. On the other hand, a non-contorted 5-limit scale in any equal temperament will be of genus 1, since the two commas serve as boundaries for a parallelogram which defines a torus (we can visualize this as rolling it up and glueing ends together.) | A 5-limit JI scale, meaning a scale composed of 5-limit JI intervals such that {6/5, 5/4, 4/3, 3/2, 8/5, 5/3} is the consonance set, is always planar. This because the [[http://xenharmonic.wikispaces.com/file/detail/hexagonal-lattice.gif|hexagonal lattice]] of 5-limit pitch classes is planar, and the graph of any scale will simply be a finite subgraph of that lattice, considered as a graph. On the other hand, a non-contorted 5-limit scale in any equal temperament will be of genus 1, since the two commas serve as boundaries for a parallelogram which defines a torus (we can visualize this as rolling it up and glueing ends together.) | ||
| Line 50: | Line 52: | ||
If A is the adjacency matrix, which is a VxV square matrix, the [[http://en.wikipedia.org/wiki/Graph_automorphism|automorphism group]] Aut(G) of the graph G is given explicitly by the set {P|P⋅A = A⋅P} of VxV [[http://en.wikipedia.org/wiki/Permutation_matrix|permutation matrices]] which commute with A. Equivalently, it is the set {P|A = P⋅A⋅P^(-1)}, where A is identical to itself under a similarity transformation. For most graphs, the automorphism group is trivial; however this is often not the case for graphs of scales. For instance, a symmetric scale such that if s is in the scale, then so is its octave inversion 2/s, will have an element of order 2 in its automorphism group. A MOS will always have an element of order 2, resulting from some composition of inversion and translation. Graph automorphisms such as these preserve the property of being a dyadic chord, making such things of considerable musical interest. | If A is the adjacency matrix, which is a VxV square matrix, the [[http://en.wikipedia.org/wiki/Graph_automorphism|automorphism group]] Aut(G) of the graph G is given explicitly by the set {P|P⋅A = A⋅P} of VxV [[http://en.wikipedia.org/wiki/Permutation_matrix|permutation matrices]] which commute with A. Equivalently, it is the set {P|A = P⋅A⋅P^(-1)}, where A is identical to itself under a similarity transformation. For most graphs, the automorphism group is trivial; however this is often not the case for graphs of scales. For instance, a symmetric scale such that if s is in the scale, then so is its octave inversion 2/s, will have an element of order 2 in its automorphism group. A MOS will always have an element of order 2, resulting from some composition of inversion and translation. Graph automorphisms such as these preserve the property of being a dyadic chord, making such things of considerable musical interest. | ||
If the spectrum of the graph contains no repeated values, then Aut(G) is an [[http://en.wikipedia.org/wiki/Elementary_abelian_group|elementary abelian 2-group]], meaning all non-identity elements are of order 2. Hence for the more interesting automorphism groups, including non-abelian groups, we need repeated values in the spectrum, in other words eigenvalues with multiplicity greater than one corresponding to eigenspaces with dimension greater than one.</pre></div> | If the spectrum of the graph contains no repeated values, then Aut(G) is an [[http://en.wikipedia.org/wiki/Elementary_abelian_group|elementary abelian 2-group]], meaning all non-identity elements are of order 2. Hence for the more interesting automorphism groups, including non-abelian groups, we need repeated values in the spectrum, in other words eigenvalues with multiplicity greater than one corresponding to eigenspaces with dimension greater than one. | ||
=Examples= | |||
=The Zarlino scale= | |||
The Zarlino scale, or "just diatonic" as it's often called, is the scale 9/8-5/4-4/3-3/2-5/3-15/8-2, with three major and two minor triads. It has a characteristic polynomial x(x+1)(x^2-3)(x^3-x^2-7*x-3) = x^7 - 11x^5 - 10x^4 + 21x^3 + 30x^2 + 9x. From the coefficients of this we can read off that it has 11 dyads and 5 triads, and from the roots, we find that its automorphism group is an elementary 2-group--in fact, it is of order 2, with the nontrivial automorphism being inversion. The three connectivities, algebraic, vertex, and edge, are 0.914 ≤ 2 ≤ 2. The scales radius is 2 and its diameter is 3. Its genus, of course, is 0, but less obviously its maximal genus is 2. | |||
</pre></div> | |||
<h4>Original HTML content:</h4> | <h4>Original HTML content:</h4> | ||
<div style="width:100%; max-height:400pt; overflow:auto; background-color:#f8f9fa; border: 1px solid #eaecf0; padding:0em"><pre style="margin:0px;border:none;background:none;word-wrap:break-word;width:200%;white-space: pre-wrap ! important" class="old-revision-html"><html><head><title>Graph-theoretic properties of scales</title></head><body><!-- ws:start:WikiTextTocRule: | <div style="width:100%; max-height:400pt; overflow:auto; background-color:#f8f9fa; border: 1px solid #eaecf0; padding:0em"><pre style="margin:0px;border:none;background:none;word-wrap:break-word;width:200%;white-space: pre-wrap ! important" class="old-revision-html"><html><head><title>Graph-theoretic properties of scales</title></head><body><!-- ws:start:WikiTextTocRule:16:&lt;img id=&quot;wikitext@@toc@@flat&quot; class=&quot;WikiMedia WikiMediaTocFlat&quot; title=&quot;Table of Contents&quot; src=&quot;/site/embedthumbnail/toc/flat?w=100&amp;h=16&quot;/&gt; --><!-- ws:end:WikiTextTocRule:16 --><!-- ws:start:WikiTextTocRule:17: --><a href="#Graph of a scale">Graph of a scale</a><!-- ws:end:WikiTextTocRule:17 --><!-- ws:start:WikiTextTocRule:18: --> | <a href="#Connectivity">Connectivity</a><!-- ws:end:WikiTextTocRule:18 --><!-- ws:start:WikiTextTocRule:19: --> | <a href="#The Characteristic Polynomial">The Characteristic Polynomial</a><!-- ws:end:WikiTextTocRule:19 --><!-- ws:start:WikiTextTocRule:20: --> | <a href="#The Laplace Spectrum">The Laplace Spectrum</a><!-- ws:end:WikiTextTocRule:20 --><!-- ws:start:WikiTextTocRule:21: --> | <a href="#The Genus">The Genus</a><!-- ws:end:WikiTextTocRule:21 --><!-- ws:start:WikiTextTocRule:22: --> | <a href="#The Automorphism Group">The Automorphism Group</a><!-- ws:end:WikiTextTocRule:22 --><!-- ws:start:WikiTextTocRule:23: --> | <a href="#Examples">Examples</a><!-- ws:end:WikiTextTocRule:23 --><!-- ws:start:WikiTextTocRule:24: --> | <a href="#The Zarlino scale">The Zarlino scale</a><!-- ws:end:WikiTextTocRule:24 --><!-- ws:start:WikiTextTocRule:25: --> | ||
<!-- ws:end:WikiTextTocRule: | <!-- ws:end:WikiTextTocRule:25 --><br /> | ||
<!-- ws:start:WikiTextHeadingRule:0:&lt;h1&gt; --><h1 id="toc0"><a name="Graph of a scale"></a><!-- ws:end:WikiTextHeadingRule:0 -->Graph of a scale</h1> | <!-- ws:start:WikiTextHeadingRule:0:&lt;h1&gt; --><h1 id="toc0"><a name="Graph of a scale"></a><!-- ws:end:WikiTextHeadingRule:0 -->Graph of a scale</h1> | ||
Given a <a class="wiki_link" href="/periodic%20scale">periodic scale</a>, meaning a scale whose steps repeat, and assuming some multiple of the period is an interval of equivalence (usually this means the octave, ie interval of 2, which from now on we will assume is the interval of equivalence) then we may reduce the scale to a finite set S of pitch classes. This relates to the usual way of defining a scale, as used for instance by <a class="wiki_link" href="/Scala">Scala</a>. If we say 1-9/8-5/4-4/3-3/2-5/3-15/8-2 is a scale, we mean that each step of it represents a class of octave-equivalent pitches, so that &quot;5/4&quot; represents {...5/8, 5/4, 5/2, 5, 10 ...} and both &quot;1&quot; and &quot;2&quot; mean {...1/4, 1/2, 1, 2, 4...}. Suppose we have a finite set of pitches C strictly within the octave, so that s∊C entails 1 &lt; s &lt; 2, and suppose if s∊C then also 2/s∊C. The elements of C represent consonant pitch classes exclusive of the unison-octave class. <br /> | Given a <a class="wiki_link" href="/periodic%20scale">periodic scale</a>, meaning a scale whose steps repeat, and assuming some multiple of the period is an interval of equivalence (usually this means the octave, ie interval of 2, which from now on we will assume is the interval of equivalence) then we may reduce the scale to a finite set S of pitch classes. This relates to the usual way of defining a scale, as used for instance by <a class="wiki_link" href="/Scala">Scala</a>. If we say 1-9/8-5/4-4/3-3/2-5/3-15/8-2 is a scale, we mean that each step of it represents a class of octave-equivalent pitches, so that &quot;5/4&quot; represents {...5/8, 5/4, 5/2, 5, 10 ...} and both &quot;1&quot; and &quot;2&quot; mean {...1/4, 1/2, 1, 2, 4...}. Suppose we have a finite set of pitches C strictly within the octave, so that s∊C entails 1 &lt; s &lt; 2, and suppose if s∊C then also 2/s∊C. The elements of C represent consonant pitch classes exclusive of the unison-octave class. <br /> | ||
| Line 69: | Line 77: | ||
These properties can be also expressed in terms of the roots of the characteristic polynomial, which are the eigenvalues of the matrix. These roots are real numbers, some of which may be multiple. The <em>spectrum</em> of G is the <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Multiset" rel="nofollow">multiset</a> of roots, including multipicities, so that some roots may be repeated. From <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Newton's_identities" rel="nofollow">Newton's identities</a> we can also say that the sum of the squares of the spectrum is twice the number of edges of the graph, which means twice the number of dyads of the scale, and the sum of the cubes of the spectrum is six times the number of triads of the scale. In terms of the adjacency matrix A, the number of dyads is tr(A^2)/2 and the number of triads is tr(A^3)/6, where &quot;tr&quot; denotes the trace. Since tr(A^2)/V, where V is the degree (number of notes) is the variance of the spectrum, we can see we prefer the variance to be larger rather than smaller. Also, tr(A^3)/V divided by the 3/2 power of the variance is the skewness of the spectrum, from which we can conclude we want the skewness to skew positive.<br /> | These properties can be also expressed in terms of the roots of the characteristic polynomial, which are the eigenvalues of the matrix. These roots are real numbers, some of which may be multiple. The <em>spectrum</em> of G is the <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Multiset" rel="nofollow">multiset</a> of roots, including multipicities, so that some roots may be repeated. From <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Newton's_identities" rel="nofollow">Newton's identities</a> we can also say that the sum of the squares of the spectrum is twice the number of edges of the graph, which means twice the number of dyads of the scale, and the sum of the cubes of the spectrum is six times the number of triads of the scale. In terms of the adjacency matrix A, the number of dyads is tr(A^2)/2 and the number of triads is tr(A^3)/6, where &quot;tr&quot; denotes the trace. Since tr(A^2)/V, where V is the degree (number of notes) is the variance of the spectrum, we can see we prefer the variance to be larger rather than smaller. Also, tr(A^3)/V divided by the 3/2 power of the variance is the skewness of the spectrum, from which we can conclude we want the skewness to skew positive.<br /> | ||
<br /> | <br /> | ||
The epitome of these properties is found in the complete graph, which in scale terms means every note is in consonant relation with every other--in other words, the scale is a dyadic chord. This has a spectrum with V-1 values of -1 and one of V-1. The <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Distance_(graph_theory)" rel="nofollow">distance</a> between two vertices (notes) is the number of edges (consonant intervals) of the shortest path between then, and the <a class="wiki_link_ext" href="http://mathworld.wolfram.com/GraphDiameter.html" rel="nofollow">diameter</a> of a graph is the length of the greatest distance between two vertices. The diameter of a compete graph is 1, and in general a small diameter is another desirable quality. A graph with diameter d must have at least d+1 distinct values in the spectrum.<br /> | The epitome of these properties is found in the complete graph, which in scale terms means every note is in consonant relation with every other--in other words, the scale is a dyadic chord. This has a spectrum with V-1 values of -1 and one of V-1. The <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Distance_(graph_theory)" rel="nofollow">distance</a> between two vertices (notes) is the number of edges (consonant intervals) of the shortest path between then, and the <a class="wiki_link_ext" href="http://mathworld.wolfram.com/GraphDiameter.html" rel="nofollow">diameter</a> of a graph is the length of the greatest distance between two vertices, while the radius is the minimax distance--the minimum over all vertices of its maximum distance to any other vertex. The diameter of a compete graph is 1, and in general a small diameter is another desirable quality. A graph with diameter d must have at least d+1 distinct values in the spectrum.<br /> | ||
<br /> | <br /> | ||
<!-- ws:start:WikiTextHeadingRule:6:&lt;h1&gt; --><h1 id="toc3"><a name="The Laplace Spectrum"></a><!-- ws:end:WikiTextHeadingRule:6 -->The Laplace Spectrum</h1> | <!-- ws:start:WikiTextHeadingRule:6:&lt;h1&gt; --><h1 id="toc3"><a name="The Laplace Spectrum"></a><!-- ws:end:WikiTextHeadingRule:6 -->The Laplace Spectrum</h1> | ||
| Line 79: | Line 87: | ||
<br /> | <br /> | ||
<!-- ws:start:WikiTextHeadingRule:8:&lt;h1&gt; --><h1 id="toc4"><a name="The Genus"></a><!-- ws:end:WikiTextHeadingRule:8 -->The Genus</h1> | <!-- ws:start:WikiTextHeadingRule:8:&lt;h1&gt; --><h1 id="toc4"><a name="The Genus"></a><!-- ws:end:WikiTextHeadingRule:8 -->The Genus</h1> | ||
A graph is <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Planar_graph" rel="nofollow">planar</a> if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Compact_space" rel="nofollow">compact</a><a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Orientability" rel="nofollow">orientable</a> <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Surface" rel="nofollow">surface</a> with &quot;donut holes&quot;, which we may view as a closed and bounded surface in 3 dimensional Euclidean space. If a surface has g holes, it is of <a class="wiki_link_ext" href="http:// | A graph is <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Planar_graph" rel="nofollow">planar</a> if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Compact_space" rel="nofollow">compact</a><a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Orientability" rel="nofollow">orientable</a> <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Surface" rel="nofollow">surface</a> with &quot;donut holes&quot;, which we may view as a closed and bounded surface in 3 dimensional Euclidean space. If a surface has g holes, it is of <a class="wiki_link_ext" href="http://mathworld.wolfram.com/GraphGenus.html" rel="nofollow">genus</a> g, where the sphere (or plane) has genus 0. The minimum number of holes needed to draw the graph is the genus of the graph. <br /> | ||
<br /> | <br /> | ||
Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/NP-complete" rel="nofollow">NP-complete</a>. However, finding bounds on the genus is a much easier problem. For small enough scales, the genus routine of <a class="wiki_link_ext" href="http://www.sagemath.org/" rel="nofollow">SAGE</a> can manage to finish computing after an acceptable amount of time.<br /> | Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/NP-complete" rel="nofollow">NP-complete</a>. However, finding bounds on the genus is a much easier problem. For small enough scales, the genus routine of <a class="wiki_link_ext" href="http://www.sagemath.org/" rel="nofollow">SAGE</a> can manage to finish computing after an acceptable amount of time.<br /> | ||
<br /> | |||
If the genus is g, the graph can also be drawn on any surface of genus greater than g; one way to accomplish that, but not the only way, is simply not to use more than g of the holes--that is, not to draw an edge passing through it. In fact, beyond a certain point you would not be able to use all of the holes and would have to leave some without edges drawn through them. The maximum number of holes, all of which can actually be used by having an edge pass through them, is called the maximal genus an is another invariant of the graph.<br /> | |||
<br /> | <br /> | ||
A 5-limit JI scale, meaning a scale composed of 5-limit JI intervals such that {6/5, 5/4, 4/3, 3/2, 8/5, 5/3} is the consonance set, is always planar. This because the <a class="wiki_link_ext" href="http://xenharmonic.wikispaces.com/file/detail/hexagonal-lattice.gif" rel="nofollow">hexagonal lattice</a> of 5-limit pitch classes is planar, and the graph of any scale will simply be a finite subgraph of that lattice, considered as a graph. On the other hand, a non-contorted 5-limit scale in any equal temperament will be of genus 1, since the two commas serve as boundaries for a parallelogram which defines a torus (we can visualize this as rolling it up and glueing ends together.)<br /> | A 5-limit JI scale, meaning a scale composed of 5-limit JI intervals such that {6/5, 5/4, 4/3, 3/2, 8/5, 5/3} is the consonance set, is always planar. This because the <a class="wiki_link_ext" href="http://xenharmonic.wikispaces.com/file/detail/hexagonal-lattice.gif" rel="nofollow">hexagonal lattice</a> of 5-limit pitch classes is planar, and the graph of any scale will simply be a finite subgraph of that lattice, considered as a graph. On the other hand, a non-contorted 5-limit scale in any equal temperament will be of genus 1, since the two commas serve as boundaries for a parallelogram which defines a torus (we can visualize this as rolling it up and glueing ends together.)<br /> | ||
| Line 87: | Line 97: | ||
A <a class="wiki_link" href="/dyadic%20chord">dyadic chord</a> pentad is of genus 1, and any scale containing dyadic pentads is therefore not planar. The embedding of a pentad's graph on a torus is illustrated below:<br /> | A <a class="wiki_link" href="/dyadic%20chord">dyadic chord</a> pentad is of genus 1, and any scale containing dyadic pentads is therefore not planar. The embedding of a pentad's graph on a torus is illustrated below:<br /> | ||
<br /> | <br /> | ||
<!-- ws:start:WikiTextLocalImageRule: | <!-- ws:start:WikiTextLocalImageRule:26:&lt;img src=&quot;/file/view/pentad.gif/358612239/pentad.gif&quot; alt=&quot;&quot; title=&quot;&quot; /&gt; --><img src="/file/view/pentad.gif/358612239/pentad.gif" alt="pentad.gif" title="pentad.gif" /><!-- ws:end:WikiTextLocalImageRule:26 --><br /> | ||
<br /> | <br /> | ||
The edges leading from the four outer vertices wrap around to the opposite side, creating the torus embedding. On the other hand, a tetrad is of genus 0, since it can be drawn on a sphere as the verticies of a tetrahedron. <br /> | The edges leading from the four outer vertices wrap around to the opposite side, creating the torus embedding. On the other hand, a tetrad is of genus 0, since it can be drawn on a sphere as the verticies of a tetrahedron. <br /> | ||
| Line 96: | Line 106: | ||
If A is the adjacency matrix, which is a VxV square matrix, the <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Graph_automorphism" rel="nofollow">automorphism group</a> Aut(G) of the graph G is given explicitly by the set {P|P⋅A = A⋅P} of VxV <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Permutation_matrix" rel="nofollow">permutation matrices</a> which commute with A. Equivalently, it is the set {P|A = P⋅A⋅P^(-1)}, where A is identical to itself under a similarity transformation. For most graphs, the automorphism group is trivial; however this is often not the case for graphs of scales. For instance, a symmetric scale such that if s is in the scale, then so is its octave inversion 2/s, will have an element of order 2 in its automorphism group. A MOS will always have an element of order 2, resulting from some composition of inversion and translation. Graph automorphisms such as these preserve the property of being a dyadic chord, making such things of considerable musical interest.<br /> | If A is the adjacency matrix, which is a VxV square matrix, the <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Graph_automorphism" rel="nofollow">automorphism group</a> Aut(G) of the graph G is given explicitly by the set {P|P⋅A = A⋅P} of VxV <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Permutation_matrix" rel="nofollow">permutation matrices</a> which commute with A. Equivalently, it is the set {P|A = P⋅A⋅P^(-1)}, where A is identical to itself under a similarity transformation. For most graphs, the automorphism group is trivial; however this is often not the case for graphs of scales. For instance, a symmetric scale such that if s is in the scale, then so is its octave inversion 2/s, will have an element of order 2 in its automorphism group. A MOS will always have an element of order 2, resulting from some composition of inversion and translation. Graph automorphisms such as these preserve the property of being a dyadic chord, making such things of considerable musical interest.<br /> | ||
<br /> | <br /> | ||
If the spectrum of the graph contains no repeated values, then Aut(G) is an <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Elementary_abelian_group" rel="nofollow">elementary abelian 2-group</a>, meaning all non-identity elements are of order 2. Hence for the more interesting automorphism groups, including non-abelian groups, we need repeated values in the spectrum, in other words eigenvalues with multiplicity greater than one corresponding to eigenspaces with dimension greater than one.</body></html></pre></div> | If the spectrum of the graph contains no repeated values, then Aut(G) is an <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Elementary_abelian_group" rel="nofollow">elementary abelian 2-group</a>, meaning all non-identity elements are of order 2. Hence for the more interesting automorphism groups, including non-abelian groups, we need repeated values in the spectrum, in other words eigenvalues with multiplicity greater than one corresponding to eigenspaces with dimension greater than one.<br /> | ||
<br /> | |||
<!-- ws:start:WikiTextHeadingRule:12:&lt;h1&gt; --><h1 id="toc6"><a name="Examples"></a><!-- ws:end:WikiTextHeadingRule:12 -->Examples</h1> | |||
<br /> | |||
<!-- ws:start:WikiTextHeadingRule:14:&lt;h1&gt; --><h1 id="toc7"><a name="The Zarlino scale"></a><!-- ws:end:WikiTextHeadingRule:14 -->The Zarlino scale</h1> | |||
The Zarlino scale, or &quot;just diatonic&quot; as it's often called, is the scale 9/8-5/4-4/3-3/2-5/3-15/8-2, with three major and two minor triads. It has a characteristic polynomial x(x+1)(x^2-3)(x^3-x^2-7*x-3) = x^7 - 11x^5 - 10x^4 + 21x^3 + 30x^2 + 9x. From the coefficients of this we can read off that it has 11 dyads and 5 triads, and from the roots, we find that its automorphism group is an elementary 2-group--in fact, it is of order 2, with the nontrivial automorphism being inversion. The three connectivities, algebraic, vertex, and edge, are 0.914 ≤ 2 ≤ 2. The scales radius is 2 and its diameter is 3. Its genus, of course, is 0, but less obviously its maximal genus is 2.</body></html></pre></div> | |||