Graph-theoretic properties of scales
IMPORTED REVISION FROM WIKISPACES
This is an imported revision from Wikispaces. The revision metadata is included below for reference:
- This revision was by author genewardsmith and made on 2012-08-18 21:39:30 UTC.
- The original revision id was 358534207.
- The revision comment was:
The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.
Original Wikitext content:
[[toc|flat]]
=Graph of a scale=
Given a [[periodic scale]], 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 [[Scala]]. 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 "5/4" represents {...5/8, 5/4, 5/2, 5, 10 ...} and both "1" and "2" 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 < s < 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.
We now may define the **graph of the scale**, which more precisely is the graph G = G(S, C) of the scale S together with the consonance set C. This means G is a (simple) [[http://en.wikipedia.org/wiki/Graph_(mathematics)|graph]] in the sense of [[http://en.wikipedia.org/wiki/Graph_theory|graph theory]]. The vertices of G, V(G), is the set S of pitch classes, and an edge is drawn between two distinct pitch classes r and s if X⋂C ≠ ∅, where X = {x/y|x∊r, y∊s}. This means that there is a relation of consonance, as defined by C, between the pitch classes r and s. It should be noted that we have defined things assuming pitches are given multiplicatively, but we can equally well express them in logarithmic terms as for instance by cents or by steps of an [[EDO]].
=Connectivity=
We can attribute various properties to a scale, given a choice of consonance set, by the presence of a graph-theoretic property in the graph of the scale. One key graph-theoretic property is connectivity. A graph is said to be //connected// if for any two vertices a and b, there is a path of edges between a and b. A scale is therefore connected if you can go from any one note to any other note by means of consonant intervals only. The graph G has an edge-connectivity λ(G) if it is possible to disconnect the graph by removing λ(G) edges, but no smaller number of edges will do. Similarly, it has vertex-connectivity κ(G) if it is possible to disconnect the graph by removing κ(G) vertices (notes of the scale) but no smaller number will do. The graph is //k-edge-connected// if λ(G) ≥ k, and //k-vertex-connected// if κ(G) ≥ k; these definitions transfer immediately to scales, and a high degree of connectivity may often be desired in a scale.
A [[http://en.wikipedia.org/wiki/Clique_(graph_theory)|clique]] in a graph is a subgraph such that there is an edge connecting every vertex; that is, the subgraph is a complete graph. In music terms, a clique is a [[dyadic chord]]. Hence, counting cliques of various degrees (number of notes) is a relevant consideration when analyzing a scale.
=The Characteristic Polynomial=
The [[http://en.wikipedia.org/wiki/Adjacency_matrix|adjacency matrix]] A of a graph is the square symmetric matrix with zeros on the diagonal, with 1 at the (i, j) place if the ith vertex is connected to the jth vertex, and 0 if it is not. The [[http://en.wikipedia.org/wiki/Characteristic_polynomial|characteristic polynomial]] of a graph is the characteristic polynomial det(xI - A) of its adjacency matrix, and is a property (graph invariant) of the graph alone, without consideration of how the vertices are numbered. The degree n-1 term is 0, the n-2 term is minus the number of edges of the graph and therefore dyads of the scale, and the n-3 term minus twice the number of triads (3-cliques) in the graph and therefore the scale.
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 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// of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the //Lplace 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 yhe //algebraic connectivity//. The vertex-connectivity κ(G) is greater than or equal to the algebraic connectivity.
The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to n, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.Original HTML content:
<html><head><title>Graph-theoretic properties of scales</title></head><body><!-- ws:start:WikiTextTocRule:8:<img id="wikitext@@toc@@flat" class="WikiMedia WikiMediaTocFlat" title="Table of Contents" src="/site/embedthumbnail/toc/flat?w=100&h=16"/> --><!-- ws:end:WikiTextTocRule:8 --><!-- ws:start:WikiTextTocRule:9: --><a href="#Graph of a scale">Graph of a scale</a><!-- ws:end:WikiTextTocRule:9 --><!-- ws:start:WikiTextTocRule:10: --> | <a href="#Connectivity">Connectivity</a><!-- ws:end:WikiTextTocRule:10 --><!-- ws:start:WikiTextTocRule:11: --> | <a href="#The Characteristic Polynomial">The Characteristic Polynomial</a><!-- ws:end:WikiTextTocRule:11 --><!-- ws:start:WikiTextTocRule:12: --> | <a href="#The Laplace Spectrum">The Laplace Spectrum</a><!-- ws:end:WikiTextTocRule:12 --><!-- ws:start:WikiTextTocRule:13: -->
<!-- ws:end:WikiTextTocRule:13 --><br />
<!-- ws:start:WikiTextHeadingRule:0:<h1> --><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 "5/4" represents {...5/8, 5/4, 5/2, 5, 10 ...} and both "1" and "2" 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 < s < 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 />
<br />
We now may define the <strong>graph of the scale</strong>, which more precisely is the graph G = G(S, C) of the scale S together with the consonance set C. This means G is a (simple) <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Graph_(mathematics)" rel="nofollow">graph</a> in the sense of <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Graph_theory" rel="nofollow">graph theory</a>. The vertices of G, V(G), is the set S of pitch classes, and an edge is drawn between two distinct pitch classes r and s if X⋂C ≠ ∅, where X = {x/y|x∊r, y∊s}. This means that there is a relation of consonance, as defined by C, between the pitch classes r and s. It should be noted that we have defined things assuming pitches are given multiplicatively, but we can equally well express them in logarithmic terms as for instance by cents or by steps of an <a class="wiki_link" href="/EDO">EDO</a>.<br />
<br />
<!-- ws:start:WikiTextHeadingRule:2:<h1> --><h1 id="toc1"><a name="Connectivity"></a><!-- ws:end:WikiTextHeadingRule:2 -->Connectivity</h1>
We can attribute various properties to a scale, given a choice of consonance set, by the presence of a graph-theoretic property in the graph of the scale. One key graph-theoretic property is connectivity. A graph is said to be <em>connected</em> if for any two vertices a and b, there is a path of edges between a and b. A scale is therefore connected if you can go from any one note to any other note by means of consonant intervals only. The graph G has an edge-connectivity λ(G) if it is possible to disconnect the graph by removing λ(G) edges, but no smaller number of edges will do. Similarly, it has vertex-connectivity κ(G) if it is possible to disconnect the graph by removing κ(G) vertices (notes of the scale) but no smaller number will do. The graph is <em>k-edge-connected</em> if λ(G) ≥ k, and <em>k-vertex-connected</em> if κ(G) ≥ k; these definitions transfer immediately to scales, and a high degree of connectivity may often be desired in a scale.<br />
<br />
A <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Clique_(graph_theory)" rel="nofollow">clique</a> in a graph is a subgraph such that there is an edge connecting every vertex; that is, the subgraph is a complete graph. In music terms, a clique is a <a class="wiki_link" href="/dyadic%20chord">dyadic chord</a>. Hence, counting cliques of various degrees (number of notes) is a relevant consideration when analyzing a scale.<br />
<br />
<!-- ws:start:WikiTextHeadingRule:4:<h1> --><h1 id="toc2"><a name="The Characteristic Polynomial"></a><!-- ws:end:WikiTextHeadingRule:4 -->The Characteristic Polynomial</h1>
The <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Adjacency_matrix" rel="nofollow">adjacency matrix</a> A of a graph is the square symmetric matrix with zeros on the diagonal, with 1 at the (i, j) place if the ith vertex is connected to the jth vertex, and 0 if it is not. The <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Characteristic_polynomial" rel="nofollow">characteristic polynomial</a> of a graph is the characteristic polynomial det(xI - A) of its adjacency matrix, and is a property (graph invariant) of the graph alone, without consideration of how the vertices are numbered. The degree n-1 term is 0, the n-2 term is minus the number of edges of the graph and therefore dyads of the scale, and the n-3 term minus twice the number of triads (3-cliques) in the graph and therefore the scale. <br />
<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 "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.<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 />
<br />
<!-- ws:start:WikiTextHeadingRule:6:<h1> --><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 <em>Laplace matrix</em> of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the <em>Lplace 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 yhe <em>algebraic connectivity</em>. The vertex-connectivity κ(G) is greater than or equal to the algebraic connectivity.<br />
<br />
The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to n, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.</body></html>