Graph-theoretic properties of scales: Difference between revisions
Wikispaces>genewardsmith **Imported revision 358758489 - Original comment: ** |
Wikispaces>genewardsmith **Imported revision 358780951 - 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-20 | : This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-20 13:56:11 UTC</tt>.<br> | ||
: The original revision id was <tt> | : The original revision id was <tt>358780951</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)/n, where n 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)/n 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)/n, where n 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)/n 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 n-1 values of -1 and one of n-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 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 n-1 values of -1 and one of n-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 //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 Laplace Spectrum= | =The Laplace Spectrum= | ||
If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the //Laplace matrix | If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the [[http://en.wikipedia.org/wiki/Laplacian_matrix|Laplace matrix]] of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the //Laplace spectrum//. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the [[http://en.wikipedia.org/wiki/Algebraic_connectivity|algebraic connectivity]]. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices; consequently λ > (π/V)^2 ε. | ||
We can also relate the diameter d to the algebraic connectivity, since 4/(Vλ) ≤ d ≤ 2((Δ+λ)/4λ)ln(V-1), where Δ is the maximal degree of the vertices of G. Also, if ρ is the mean distance, meaning the average of all of the distances in G, then 2/((V-1)λ) + (V-2)/(2(V-1)) ≤ ρ ≤ (V/(V-1))((Δ+λ)/4λ)ln(V-1). Hence when λ is small, distances will be large. | We can also relate the diameter d to the algebraic connectivity, since 4/(Vλ) ≤ d ≤ 2((Δ+λ)/4λ)ln(V-1), where Δ is the maximal degree of the vertices of G. Also, if ρ is the mean distance, meaning the average of all of the distances in G, then 2/((V-1)λ) + (V-2)/(2(V-1)) ≤ ρ ≤ (V/(V-1))((Δ+λ)/4λ)ln(V-1). Hence when λ is small, distances will be large. | ||
| Line 45: | Line 45: | ||
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. | 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. | ||
If V is the number of notes (vertices) of the scale, and E the number of dyads (edges), then the maximum value for E is C(V, 2) = V(V - 1)/2. This suggests the definition for [[http://en.wikipedia.org/wiki/Dense_graph|graph density]], 2E/(V(V-1)). Since the maximum number of edges for a genus 0 graph with V>2 is 3V - 6, the maximum density for a genus 0 graph is 6(V-2)/(V(V-1)) whih has series expansion 6/V - 6/V^2 - 6/V^3 ...; if the density is 6/V or greater the graph must be of a higher genus, hence, higher genus scales are to be expected in music. If each note is harmonically related to at least three other notes, an obviously desirable property which in graph-theoretic language means the minimum degree | If V is the number of notes (vertices) of the scale, and E the number of dyads (edges), then the maximum value for E is C(V, 2) = V(V - 1)/2. This suggests the definition for [[http://en.wikipedia.org/wiki/Dense_graph|graph density]], 2E/(V(V-1)). Since the maximum number of edges for a genus 0 graph with V>2 is 3V - 6, the maximum density for a genus 0 graph is 6(V-2)/(V(V-1)) whih has series expansion 6/V - 6/V^2 - 6/V^3 ...; if the density is 6/V or greater the graph must be of a higher genus, hence, higher genus scales are to be expected in music. If each note is harmonically related to at least three other notes, an obviously desirable property which in graph-theoretic language means the minimum degree is greater than two, then the genus g ≥ E/6 - V/2 + 1. On the other hand, for a connected graph we have g ≤ (E - V + 1)/2 | ||
=The Automorphism Group= | |||
If A is the adjacency matrix, which is a VxV square matrix, the 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 never the case for graphs of scales, as we have assumed that if an interval s is in the consonance set, so is its inversion 2/s. Hence, Aut(G) at least contains an element of order 2, the involution induced by inversion. This, of course, preserves the property of being a dyadic chord, which is true of any graph automorphism, making such things of considerable musical interest. | |||
</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:12:&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:12 --><!-- ws:start:WikiTextTocRule:13: --><a href="#Graph of a scale">Graph of a scale</a><!-- ws:end:WikiTextTocRule:13 --><!-- ws:start:WikiTextTocRule:14: --> | <a href="#Connectivity">Connectivity</a><!-- ws:end:WikiTextTocRule:14 --><!-- ws:start:WikiTextTocRule:15: --> | <a href="#The Characteristic Polynomial">The Characteristic Polynomial</a><!-- ws:end:WikiTextTocRule:15 --><!-- ws:start:WikiTextTocRule:16: --> | <a href="#The Laplace Spectrum">The Laplace Spectrum</a><!-- ws:end:WikiTextTocRule:16 --><!-- ws:start:WikiTextTocRule:17: --> | <a href="#The Genus">The Genus</a><!-- ws:end:WikiTextTocRule:17 --><!-- ws:start:WikiTextTocRule:18: --> | <a href="#The Automorphism Group">The Automorphism Group</a><!-- ws:end:WikiTextTocRule:18 --><!-- ws:start:WikiTextTocRule:19: --> | ||
<!-- ws:end:WikiTextTocRule: | <!-- ws:end:WikiTextTocRule:19 --><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 64: | Line 69: | ||
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)/n, where n 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)/n 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)/n, where n 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)/n 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 n-1 values of -1 and one of n-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 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.<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 n-1 values of -1 and one of n-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 <em>diameter</em> 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 /> | ||
<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> | ||
If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the < | If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Laplacian_matrix" rel="nofollow">Laplace matrix</a> of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the <em>Laplace spectrum</em>. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Algebraic_connectivity" rel="nofollow">algebraic connectivity</a>. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices; consequently λ &gt; (π/V)^2 ε.<br /> | ||
<br /> | <br /> | ||
We can also relate the diameter d to the algebraic connectivity, since 4/(Vλ) ≤ d ≤ 2((Δ+λ)/4λ)ln(V-1), where Δ is the maximal degree of the vertices of G. Also, if ρ is the mean distance, meaning the average of all of the distances in G, then 2/((V-1)λ) + (V-2)/(2(V-1)) ≤ ρ ≤ (V/(V-1))((Δ+λ)/4λ)ln(V-1). Hence when λ is small, distances will be large.<br /> | We can also relate the diameter d to the algebraic connectivity, since 4/(Vλ) ≤ d ≤ 2((Δ+λ)/4λ)ln(V-1), where Δ is the maximal degree of the vertices of G. Also, if ρ is the mean distance, meaning the average of all of the distances in G, then 2/((V-1)λ) + (V-2)/(2(V-1)) ≤ ρ ≤ (V/(V-1))((Δ+λ)/4λ)ln(V-1). Hence when λ is small, distances will be large.<br /> | ||
| Line 82: | Line 87: | ||
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:20:&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:20 --><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 /> | ||
<br /> | <br /> | ||
If V is the number of notes (vertices) of the scale, and E the number of dyads (edges), then the maximum value for E is C(V, 2) = V(V - 1)/2. This suggests the definition for <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Dense_graph" rel="nofollow">graph density</a>, 2E/(V(V-1)). Since the maximum number of edges for a genus 0 graph with V&gt;2 is 3V - 6, the maximum density for a genus 0 graph is 6(V-2)/(V(V-1)) whih has series expansion 6/V - 6/V^2 - 6/V^3 ...; if the density is 6/V or greater the graph must be of a higher genus, hence, higher genus scales are to be expected in music. If each note is harmonically related to at least three other notes, an obviously desirable property which in graph-theoretic language means the minimum degree | If V is the number of notes (vertices) of the scale, and E the number of dyads (edges), then the maximum value for E is C(V, 2) = V(V - 1)/2. This suggests the definition for <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Dense_graph" rel="nofollow">graph density</a>, 2E/(V(V-1)). Since the maximum number of edges for a genus 0 graph with V&gt;2 is 3V - 6, the maximum density for a genus 0 graph is 6(V-2)/(V(V-1)) whih has series expansion 6/V - 6/V^2 - 6/V^3 ...; if the density is 6/V or greater the graph must be of a higher genus, hence, higher genus scales are to be expected in music. If each note is harmonically related to at least three other notes, an obviously desirable property which in graph-theoretic language means the minimum degree is greater than two, then the genus g ≥ E/6 - V/2 + 1. On the other hand, for a connected graph we have g ≤ (E - V + 1)/2<br /> | ||
<br /> | |||
<!-- ws:start:WikiTextHeadingRule:10:&lt;h1&gt; --><h1 id="toc5"><a name="The Automorphism Group"></a><!-- ws:end:WikiTextHeadingRule:10 -->The Automorphism Group</h1> | |||
If A is the adjacency matrix, which is a VxV square matrix, the automorphism group 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 never the case for graphs of scales, as we have assumed that if an interval s is in the consonance set, so is its inversion 2/s. Hence, Aut(G) at least contains an element of order 2, the involution induced by inversion. This, of course, preserves the property of being a dyadic chord, which is true of any graph automorphism, making such things of considerable musical interest.</body></html></pre></div> | |||