On Linear Algebraic Representation of Time-span and Prolongational Trees

Abstract

In constructive music theory, such as Schenkerian analysis and the Generative Theory of Tonal Music (GTTM), the hierarchical importance of pitch events is conveniently represented by a tree structure. Although a tree is easy to recognize and has high visibility, such an intuitive representation can hardly be treated in mathematical formalization. Especially in GTTM, the conjunction height of two branches is often arbitrary, contrary to the notion of hierarchy. Since a tree is a kind of graph, and a graph is often represented by a matrix, we show the linear algebraic representation of trees, specifying conjunction heights. Thereafter, we explain the ‘reachability’ between pitch events (corresponding to information about reduction) by the multiplication of matrices. In addition we discuss multiplication with vectors representing a sequence of harmonic functions, and suggest the notion of stability. Finally, we discuss operations between matrices to model compositional processes with simple algebraic operations.

1 Introduction

Schenkerian analysis suggested a layered structural importance of pitch events and showed the existence of an innate skeleton of music in a hierarchical way. As a more modern theory of this structural hierarchy, the Generative Theory of Tonal Music (GTTM) [5] aims at constructing two kinds of tree: Time-span tree and Prolongational tree, and the deriving process has been automated [1, 7].

Fig. 1.

Time-span tree.

The time-span tree in Fig. 1 shows that the C is more salient than the succeeding E and $F\sharp$, but surrenders to the final event G. Such a tree is roughly represented by a sequence

$$\begin{aligned} (C^{\dagger }(E^{\dagger }F\sharp ))(DG^{\dagger })^{\dagger } \end{aligned}$$

where the parentheses mean a bifurcation and the dagger ‘$\dagger$’ specifies the choice of the more salient branch between the two. Thus, the formula corresponds to the tree in Fig. 1. But, this representation with parentheses and daggers lacks information on the duration of pitch events.

Even when we add the information on duration for each pitch event, the tree cannot be fixed uniquely, as there remains the arbitrariness as to the height of junction point of branches. Matsubara et al. [8, 10] have tried to fix the junction height, regarding the number of beats, e.g., $2^n~\text {beats}\le L^n < 2^{n+1}~\text {beats}$ (Fig. 2), however, when they tried to include cadential retention the height still remained ambiguous.

Fig. 2.

Junction height by the number of beats [8].

We have proposed the notion of Maximum Time-span (MTS) of each pitch event, as the longest temporal interval during which the event is most salient [2, 11]. If a pitch event does not have branching, i.e., there is no more subordinate pitch event and is a leaf of the tree, its MTS is the original pitch length. At the other extreme, the MTS of the event that reaches the top of the tree is the whole length of the music piece. Here, we can write the MTS of Fig. 1 as in Fig. 3.

Fig. 3.

MTS for the tree.

We can naively represent the tree in a matrix as in Fig. 4, left-hand side, where a pitch event in the column is connected to the one in each row with the height indicated by the matrix cell value. Or, the height is relativized if we regard the entire height should be 1, as in the right-hand side of the figure. (We arbitrarily show the top event to be connected to itself. This allows the maximum time-span for each pitch event to be read from the row of that pitch event. This choice is justified further in the representation explained in Sect. 2.)

Fig. 4.

Height information by MTS and its relative representation.

But, these matrices in Fig. 4 do not possess sufficient non-zero diagonal elements, i.e., their rank is lower than their size, and are not regular; that is, the matrices are not algebraically tractable. In this paper, we revise the above representation and propose a musically meaningful matrix. In the following Sect. 2, we formally define a matrix for a music piece. In Sect. 3 we also introduce the multiplication by a vector of harmonic functions and in that process we discuss the notion of stability of a tree. In Sect. 4 we discuss the meaning of multiplication of matrices. In Sect. 5 we summarize our contribution and discuss the future direction, especially for new arrangement/composition methods by algebraic operations.

2 Tree Representation

In this section, we formally define the numeric values of matrices. If two consecutive pitch events have the durations $d_1$ and $d_2$, and the first one is more salient than the second (i.e., more fundamental in the melodic structure, in the sense used by Lehrdahl and Jackendoff [5]), the MTS would be $mts _1 = d_1 + d_2$ and $mts _2=d_2$. This situation is depicted in Fig. 5.

Fig. 5.

Relation between branch length and MTS.

In Fig. 5, each branch length, that is $l_1$ and $l_2$, is proportional to its MTS though the angles versus the horizontal line are not fixed and thus arbitrary. Nevertheless, notice that the junction height correctly reflects the relation of the lengths of two branches when they are mapped to a hypothetical vertical axis. The matrix below each figure in Fig. 5 represents the tree configuration. For example, the (2, 1)-element of the left matrix shows that the second pitch event ($e_2$) is connected to the first ($e_1$) with the height relative to $l_1-l_2$.

Let the above be the base case of recursive construction of a tree. Then, given two subtrees in matrices $M_1$ and $M_2$ we consider to connect them in one tree, as follows. First, there are the most salient pitch events $p_i$ and $p_j$ in $M_1$ and $M_2$, respectively, and let their branch lengths be $l_i$ and $l_j$. The whole tree, consisting of the two subtrees, becomes such a disjoint union of matrices:

If $p_j$ is more salient than $p_i$, the branch lengths for $p_i$ would be added to $l_j$ as $\hat{l}_j \equiv l_i + l_j$. Thus, we revise the new matrix as in the left-hand side of Fig. 6. In the case $p_i$ is more salient than $p_j$ the revision would be $\hat{l}_i \equiv l_i + l_j$ and all $l_i$ are replaced with $\hat{l}_i$ as in the right-hand side of Fig. 6.

Fig. 6.

The result of combining two subtrees by left branching (left) and right branching (right).

Fig. 7.

Example of disjoint union.

Example. Let a sequence of two pitch events $p_1$ and $p_2$ be connected by right branching, with the branch lengths of $l_1$ and $l_2$, respectively. Also, let $p_3$ and $p_4$ be connected by left branching and have the lengths of $l_3$ and $l_4$, respectively. Then, the initial disjoint union becomes the left-hand side of Fig. 7. Now suppose $p_4$ is more salient than $p_1$. Then, the top of the tree becomes left branching, and thus $\hat{l}_4 \equiv l_4 + l_1$ appears at (1, 4)-position, and remaining $l_4$ are all replaced with $\hat{l}_4$, as in the right-hand side of Fig. 7. (This is equivalent to adding $l_1$ to all the existing non-zero elements in the column for $p_4$.) Note that the adequacy of (1, 4)-element is justified as in Fig. 8.   $\square$

Fig. 8.

Relation between four branches.

3 Reachability and Harmonic Stability

3.1 Reachability

The matrix representation described above gives two kinds of information: the branching of the tree (i.e., which time-spans are connected to which ones, and which is the dominating time-span); and the height of the branching in relation to the durations of the time-spans. In this section, we are concerned only with the connections and since this information is conveyed by whether a value is 0 or not, we simplify here by using only the values 0 and 1 in the matrix. We call this a topology matrix derived from the tree representation. For example, let $p_i~(i=1,\dots ,n)$ be a sequence of the pitch events of a given piece, and then the topology corresponds to the tree in Fig. 1 is shown as follows.

In the above matrix, the i-th row represents the connections from the i-th pitch event, e.g., the second pitch event $p_2$ is attached to $p_1$ ((2, 1)-element) as well as $p_2$ itself ((2, 2)-element).

The reduction hypothesis in GTTM is the idea that we can retrieve the fundamental structure of a given piece of music, pruning those non-salient branches from the time-span tree; such pruning process is called reduction and the lineage of reduced trees is called reduction path. Our objective is to represent not just the connections in the matrix, but the entire reduction path for pitch events. We now consider how the reduction path for pitch events can be represented and used in a matrix.

In matrix $M=(c_{ij})$, $c_{ij} > 0$ and $c_{jk} > 0$ where $i< j <k$ imply that $p_i$ is connected to $p_j$ and $p_j$ is connected to $p_k$. Thus, $p_i$ can reach $p_k$ via $p_j$ by two steps, or equivalently, $p_i$ is reduced to $p_j$ and then to $p_k$. We can represent these remote connections explicitly in the matrix through multiplication of the matrix by itself. To ensure that the resultant matrix is also a topology matrix, using only the values 0 and 1, we use Boolean addition for ‘+’ ($1+1=1$) in the matrix multiplication. For example, the following $M^2$ indicates the reachable pitch events within 2 steps in M; the squared-1’s mean the elements appear after the multiplication.

$$M^2=\begin{pmatrix} 1&{}0&{}0&{}0&{}1\\ 1&{}1&{}0&{}0&{}0\\ 0&{}1&{}1&{}0&{}0\\ 0&{}0&{}0&{}1&{}1\\ 0&{}0&{}0&{}0&{}1\end{pmatrix}^2 = \begin{pmatrix} 1&{}0&{}0&{}0&{}1\\ 1&{}1&{}0&{}0&{}\fbox {1}\\ \fbox {1}&{}1&{}1&{}0&{}0\\ 0&{}0&{}0&{}1&{}1\\ 0&{}0&{}0&{}0&{}1\end{pmatrix}.$$

The reachability of all pitch events is shown by $\tilde{M}=M^k$ where for length n for the given piece $k~(\le n)$ is the height of the tree, i.e., the number of the maximum branching from the top node to a leaf, and $M^{(k+1)}=M^k$. In our current example, $\tilde{M}=M^3$ since $M^3 = M^4$, as follows

$$\begin{aligned} M^3= \begin{pmatrix} 1&{}0&{}0&{}0&{}1\\ 1&{}1&{}0&{}0&{}1\\ 1&{}1&{}1&{}0&{}\fbox {1}\\ 0&{}0&{}0&{}1&{}1\\ 0&{}0&{}0&{}0&{}1\end{pmatrix}. \end{aligned}$$

In a reachability matrix, the i-th row shows all the transitively accessible pitch events from the i-th pitch event. In $M^3$, the third pitch event $p_3$ can, besides reaching $p_3$ itself, reach $p_1$ ((3, 1)-element), $p_2$ ((3, 2)-element), and $p_5$ ((3, 5)-element), which are all the events above $p_3$ in the reduction process. On the contrary, a column indicates all the dominated pitch events. the first column vector (1, 1, 1, 0, 0) of $M^3$ means that $p_1$ is reached from $p_2$ and $p_3$ as well as $p_1$ itself. In other words, $p_1$ dominates (is more salient than) $p_2$ and $p_3$.

3.2 Harmonic Stability

The reachability can help to distinguish ‘stable’ from ‘unstable’ configurations in a prolongational tree, though stableness has not been clearly defined in Lerdahl and Jackendoff’s theory. We illustrate this through a discussion of two cases from GTTM.

Mozart K.331. In Fig. 9, the first part of the theme of the first movement of Mozart’s piano sonata in A Major K.331, is shown.

Fig. 9.

The theme of K.331 [5, p. 141].

In Lerdahl and Jackendoff’s time-span reduction, the V at the end of the first phrase is connected to the opening I and the I at the beginning of the second phrase is connected to the closing cadence. In outline, the matrix representation of this is as follows.

Lerdahl and Jackendoff consider the options for converting this time-span tree into a prolongational tree, as illustrated in Fig. 10. The central dominant may be attached to the cadence or the central tonic may be attached to the beginning tonic. Lerdahl and Jackendoff claim that the second is the better option. While the reasons are musically clear, they are not rigorously defined.

Fig. 10.

Stability comparison in K.331 by Mozart [5, p. 141, 223].

Here, we discuss the notion of reachable harmonic function. Each tonic and dominant in a piece of music is considered to play an important role in constructing a stable music structure. From the reachability matrix, we can find the sequence of harmonic functions which make up the reduction path to each pitch event. We propose that the more these sequences resemble complete and stable harmonic sequences, such as I V I, the more stable the overall structure is. For example, we can find harmonic functions in Fig. 9 as

$$(\text {I}_1, \cdots , \text {V}_1, \text {I}_2, \cdots , \text {V-I}).$$

If we multiply this vector by a reachability matrix, we can find which I’s and V’s reach which other I’s and V’s. In the matrix-vector multiplication, we take ‘+’ to concatenate harmonic functions into harmonic sequences, indicating which other harmonic functions are reachable.

Below, we show the three reachability matrices for the K.331 example, and their multiplication by the appropriate vector of harmonic functions. (1) corresponds to the time-span tree, (2) to the case where the central tonic is attached to the initial tonic, and (3) where the central dominant is attached to the cadence.

$$\begin{aligned} \begin{pmatrix} 1&{}\cdots &{}&{}&{}\cdots &{}1\\ \vdots &{} \ddots &{}&{}&{}&{}\vdots \\ \fbox {1}&{}\cdots &{}1&{} 0 &{}\cdots &{}1\\ 0&{}\cdots &{}0&{}1 &{}\cdots &{}\fbox {1} \\ \vdots &{}&{}&{}&{}\ddots &{}\vdots \\ 0&{}\cdots &{}&{}&{}\cdots &{}1\end{pmatrix} \begin{pmatrix}\text {I}_1 \\ \vdots \\ \text {V}_1 \\ \text {I}_2 \\ \vdots \\ \text {V-I}\end{pmatrix}= \begin{pmatrix}\text {I}_1 +\text {V-I}\\ \vdots \\ \text {I}_1 + \text {V}_1 + \text {V-I} \\ \text {I}_2 + \text {V-I}\\ \vdots \\ \text {V-I}\end{pmatrix} \end{aligned}$$

(1)

$$\begin{aligned} \begin{pmatrix} 1&{}\cdots &{}&{}&{}\cdots &{}1\\ \vdots &{} \ddots &{}&{}&{}&{}\vdots \\ \fbox {1}&{}\cdots &{}1&{} 0&{}\cdots &{}1\\ \fbox {1}&{}\cdots &{}0&{} 1 &{}\cdots &{}1\\ \vdots &{}&{}&{}&{}\ddots &{}\vdots \\ 0&{}\cdots &{}&{}&{}\cdots &{}1\end{pmatrix} \begin{pmatrix}\text {I}_1 \\ \vdots \\ \text {V}_1 \\ \text {I}_2 \\ \vdots \\ \text {V-I}\end{pmatrix}= \begin{pmatrix}\text {I}_1 +\text {V-I}\\ \vdots \\ \text {I}_1 + \text {V}_1 +\text {V-I}\\ \text {I}_1 + \text {I}_2 +\text {V-I}\\ \vdots \\ \text {V-I}\end{pmatrix} \end{aligned}$$

(2)

$$\begin{aligned} \begin{pmatrix} 1&{}\cdots &{}&{}&{}\cdots &{}1\\ \vdots &{} \ddots &{}&{}&{}&{}\vdots \\ 0&{}\cdots &{}1&{} 0 &{}\cdots &{}\fbox {1}\\ 0&{}\cdots &{}0&{} 1 &{}\cdots &{}\fbox {1}\\ \vdots &{}&{}&{}&{}\ddots &{}\vdots \\ 0&{}\cdots &{}&{}&{}\cdots &{}1\end{pmatrix} \begin{pmatrix}\text {I}_1 \\ \vdots \\ \text {V}_1 \\ \text {I}_2 \\ \vdots \\ \text {V-I}\end{pmatrix}= \begin{pmatrix}\text {I}_1 +\text {V-I}\\ \vdots \\ \text {V}_1 + \text {V-I} \\ \text {I}_2 + \text {V-I}\\ \vdots \\ \text {V-I}\end{pmatrix} \end{aligned}$$

(3)

All three prolongational trees are shown in Fig. 11.

Fig. 11.

All the possible prolongational trees of K.331; left (1), mid (2), and right (3).

The two central harmonic sequences in the resultant vector change with the changed branching. The branching which Lerdahl and Jackendoff reject for the prolongational tree (3) produces a sequence which begins with the dominant $\text {V}_1$, which is less stable than one beginning with the tonic $\text {I}_2$. The preferred branching (2) is the same as the result for the time-span tree except that the tonic which starts both middle sequences is the initial tonic $\text {I}_1$, putting all the main pitch events of the theme in the context of the overall motion from the initial to the final tonic ($\text {I}_1$ to V-I).

Fig. 12.

The time-span tree of St. Anthony Chorale, register simplified [5, p. 205], with red lines indicating the branches in the prolongational tree which are different from the time-span tree.

St. Anthony’s Chorale. In their introduction to prolongational reduction, Lerdahl and Jackendoff present both time-span and prolongational trees for the theme of Brahms’ variations on the ‘St. Anthony Chorale’ [5, pp. 203–210] (Fig. 12). We have represented both these trees by matrices and calculated the results of multiplying them by the vector of harmonic functions, according to our own analysis of the harmony. As examples, we show the results of matrix calculations corresponding to the pitch events marked a–f in Fig. 12.

There is not space to show the complete results here, so we report only the significant differences. Of the 65 sequences in the complete resultant vector, 39 are different for the prolongational tree compared to the time-span tree. The most common change (13 cases, including two with a further change) is in sequences which, in the case of the time-span tree, began with V, corresponding to the V after the double bar. Because this is attached to the initial tonic in the prolongational tree, these sequences now begin with I. As discussed above, we believe this may be an indicator of a more stable tree. The next most common change is to replace instances of vi V I by just I (6 cases). The progression vi V is allowed by some harmonic theories (e.g., [9]) but not by others (e.g. [4]), and in any case it is not common, so this change too could be regarded as contributing to greater stability. On the other hand, the next most common change (4 cases) replaces vi V I by vi I, which is worse. In 4 other cases V is omitted from I V I sequences to yield only repetitions of the tonic, which makes little difference to stability. In 3 cases the progression vi I is replaced by just I, counterbalancing the introduction of the questionable progression vi I in the cases referred to previously. The remaining cases are smaller in number: replacing $\text {IV}^{6}$ V by $\text {IV}^{6}$ $\text {ii}^{6}$ V, which improves stability (2 cases); replacing $\text {vii}^{b7}$/V V I by $\text {vii}^{b7}$/V I, which is worse because the diminished seventh does not resolve regularly (2 cases); replacing $\text {I}^{6}_{4}$ V I by $\text {I}^{6}_{4}$ $\text {ii}^{6}$ V I, which is irregular (2 cases); adding $\text {IV}^{6}_{4}$ after I $\text {V}^{7}$/IV, which is better because it gives the resolution of the applied dominant seventh $\text {V}^{7}$/IV (2 cases); replacing I $\text {V}^{6}_{4}$ by V $\text {IV}^{6}_{4}$, which is neutral (1 case); and replacing I vi I by I V vi I, which is also neutral (1 case).

In summary, a majority of the changes in harmonic sequences in the result of multiplying the reachability matrix of the preferred prolongational tree by the vector of harmonic functions can be explained as producing a harmonically more stable tree than the time-span tree in both of these examples. However, the theory of what constitutes harmonic stability, especially in this context, is not well developed and requires further research.

4 Discussion on Multiplication of Matrices

We now return to the matrix representation which gives information about the height of branching also (i.e., matrices using not just 0 and 1) and consider how this kind of matrix can be multiplied to produce a kind of reachability matrix (i.e., one which gives information about the entire reduction path for pitch events) which preserves information about duration and branch height. In the case of topology matrices discussed above, in order to preserve the property that matrices contained only the values 0 and 1, we modified the normal matrix multiplication operation to use Boolean addition. Similarly, in order to preserve information about duration and branch height, it is necessary to modify matrix multiplication in this case.

This can be achieved by defining the multiplication and addition operations to be used in matrix multiplication as follows. For the elements of two matrices $A=(a_{ij})$ and $B=(b_{ij})$, let $a_{ij}*b_{ij} \equiv \min (a_{ij},b_{ij})$ and $a_{ij} \oplus b_{ij} \equiv \max (a_{ij}, b_{ij})$. Obviously, these are commutative and associative. Since all the elements in the matrices are equal to or larger than zero, $x *0 = 0,~ x *x = x,~ y \oplus 0 = y$, and $y\oplus y = y$.

Proposition 1

$(x *(x-y)) \oplus (y *(x-y)) = x-y~{where}~ x \ge y.$

Proof

Since $x \ge x-y$, $x *(x-y) = x-y$. If $x-y \ge y$ then $y *(x-y) =y$ and thus $(x-y)\oplus y = x-y$. Otherwise, $x-y < y$, then $y *(x-y) = x-y$ and $(x-y)\oplus (x-y)= x-y$.    $\square$

This proposition shows that in the matrix representation of a fundamental binary tree, either one of x and y is superordinate and the height information becomes $|x-y|$.

Proposition 2

All the diagonal elements remain as the same values when a matrix is multiplied by itself.

Proof

Let $A=(a_{ij})$ and note that $a_{ij} > 0~(i\ne j)$ implies $a_{ji} =0$. Then (i, i)-element in $A^2$ is equal to $\sum _{j=1}^n a_{ij} *a_{ji} = a_{ii} *a_{ii} = a_{ii}$.   $\square$

This multiplication gives information about reachability, as before. For example, in the tree represented in the matrix below, the second pitch event can reach the fourth, as non-zero (2, 4)-element appears by the multiplication.

$$\begin{pmatrix} l_1 &{} 0 &{} 0&{} ~l_4-l_1\\ l_1-l_2 &{}~ l_2 &{} 0 &{} 0\\ 0 &{} 0 &{} ~l_3 &{} ~l_4-l_3\\ 0&{} 0&{} 0&{} l_4 \end{pmatrix}^2=\begin{pmatrix} l_1 &{} 0 &{} 0&{} l_4-l_1\\ l_1-l_2 &{} l_2 &{} 0 &{} ~(l_1-l_2)*(l_4-l_1)\\ 0 &{} 0 &{} ~l_3 &{} l_4-l_3\\ 0&{} 0&{} 0&{} l_4 \end{pmatrix}$$

However, it is not clear what the value $min (l_1-l_2, l_4-l_1)$, calculated by the height times the height, means in musical terms. Also, while the result of multiplying or repeatedly multiplying a matrix by itself is always a valid reachability matrix, this is not true when multiplying two different matrices. We have examined the base cases of right- and left-branching trees of two pitch events with equal maximum time span of their heads. Multiplying two trees of this kind which have the same branching results in a copy of the left multiplicand when the duration of its first pitch event is less than or equal to the duration of the first pitch event in the other tree, and in other cases by either a copy of the right multiplicand or an invalid matrix which mixes elements from the two matrices, depending on the relation of the durations to each other and to the time-span of the head. Multiplying matrices with different branching produces an invalid matrix with non-zero values in all elements. A possible musical interpretation is that the resultant matrices indicate a distribution of possible trees resulting from the combination of the two multiplicands, but we have yet to investigate this in detail.

5 Conclusion

In this paper, we proposed a linear algebraic representation for the tree structure of music. The significance of this work is two-fold.

First, we have shown that the matrix uniquely fixes the configuration of the tree. Thus far, time-span trees and prolongational trees in GTTM include an ambiguity at conjunction heights of branches. We have revised the issue by the notion of maximum time-span (MTS), and assumed that each branch has a height relative to a virtual vertical axis in accordance with its MTS. We placed each branch height at the diagonal element and the difference of the height of two branches at the junction element in the matrix, and thus, trees have come under the rigorous mathematical domain for algebraic operations [3].

Second, rewriting those elements in matrices by Boolean values, we have defined the class of topology matrices which represent connectivity according to graph theory. Multiplying a topology matrix with itself until saturated to obtain the transitive closure results in a reachability matrix, which shows the reachability from each leaf pitch event to other higher-level pitch events. When we multiply the reachability matrix by a vector of harmonic functions, we arrive at a representation of the harmonic functions which govern each pitch event in the reduction.

We have applied this representation in an exploration of stability, hypothesizing that more stable prolongational reductions have more typical harmonic progressions in the sequence of harmonic functions which govern each pitch event. Further work is required to more rigorously define what stability means and how it can be calculated from a matrix and vector of harmonic functions. Prolongational trees are intended to represent tension and relaxation in right and left branching, respectively, so theories of harmony and tonal pitch space [6] which also include notions of distance from and to harmonies should be explored.

Future developments of our formalization are as follows. Our earlier works concerned tree operations to determine the similarity of two pieces of music and to generate new music by a tree-combination morphing process. The algebraic operations on matrix representations have the potential to lead to a new methodology for arrangement and composition. For example, join and meet of two trees are realized by addition of two matrices, where in the join operation we should redefine $a_{ij}+b_{ij} \equiv max (a_{ij},b_{ij})$ whereas in the meet operation $a_{ij}+b_{ij} \equiv min (a_{ij},b_{ij})$. In addition, if we would like to reverse the tree chronologically, that is, each left/right-branching is reversed, we can represent the retrograde by the transposition of the original matrix. Furthermore, as outlined above, we can consider the possibility of multiplication of two different matrices, producing a new piece from given two pieces.