Graph-theoretic properties of scales: Difference between revisions
Wikispaces>genewardsmith **Imported revision 358515695 - Original comment: ** |
Wikispaces>genewardsmith **Imported revision 358515829 - 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-18 17: | : This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-18 17:50:09 UTC</tt>.<br> | ||
: The original revision id was <tt> | : The original revision id was <tt>358515829</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 19: | Line 19: | ||
=Characteristic polynomial= | =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. | 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 roots 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 roots 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 amd the number of triads is tr(A^3)/6, where "tr" denotes the trace.</pre></div> | 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 roots 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 roots 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 amd the number of triads is tr(A^3)/6, where "tr" denotes the trace.</pre></div> | ||
| Line 36: | Line 36: | ||
<br /> | <br /> | ||
<!-- ws:start:WikiTextHeadingRule:4:&lt;h1&gt; --><h1 id="toc2"><a name="Characteristic polynomial"></a><!-- ws:end:WikiTextHeadingRule:4 -->Characteristic polynomial</h1> | <!-- ws:start:WikiTextHeadingRule:4:&lt;h1&gt; --><h1 id="toc2"><a name="Characteristic polynomial"></a><!-- ws:end:WikiTextHeadingRule:4 -->Characteristic polynomial</h1> | ||
The | 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 /> | <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 roots 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 roots 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 amd the number of triads is tr(A^3)/6, where &quot;tr&quot; denotes the trace.</body></html></pre></div> | 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 roots 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 roots 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 amd the number of triads is tr(A^3)/6, where &quot;tr&quot; denotes the trace.</body></html></pre></div> | ||