## Abstract

Since 1970, the Wittrick–Williams algorithm has been applied with increasing sophistication in structural mechanics to guarantee that eigenvalues cannot be missed and are calculated accurately. The underlying theorem enables its application to any discipline requiring eigenvalues of self-adjoint systems of differential equations. Its value in mathematics was recently illustrated by studying Sturm–Liouville equations on large homogeneous trees with Dirichlet boundary conditions and *n* (≤43) levels. *Recursive subsysteming* was applied *n*−1 times to assemble the tree progressively from sub-trees. Hence, numerical results confirmed the recent theoretical bounds of Sobolev & Solomyak for *n*→∞. In addition, a structural mechanics analogy yielded a proof that many eigenvalues had high multiplicities determined by *n* and the branching number *b*.

Inspired by the structural mechanics analogy, we now prove that all eigenvalues of the tree are obtainable from *n* substitute chains *r* (=1, 2, …, *n*) which involve only *r* consecutively linked differential equations and which have only singlefold eigenvalues. Equations are also derived for the multiplicities these eigenvalues have for the tree. Hence, double precision calculations on a PC readily gave eigenvalues for *n*=10^{6} and *b*=10, i.e. ≃10^{999 999} linked Sturm–Liouville equations. Moreover, a simple equation is derived which gives all the eigenvalues of uniform trees with Dirichlet conditions at both ends, and band-gap spectra are numerically demonstrated and theoretically justified for trees with the Dirichlet conditions at either end replaced by Neumann ones. Additionally, even if each multiple eigenvalue would be counted as if it were singlefold, the proportion of eigenvalues that are multiple is proved to approach unity as *n*→∞.

## 1. Introduction

This paper makes major advances, described in §1*b*, on a recent paper (Williams *et al*. 2004) which showed how the Wittrick–Williams (W–W) algorithm and a structural mechanics analogy could be used to obtain extensive new theoretical and numerical results for the Sturm–Liouville problem on homogeneous trees. The theory presented relates to the general form of the classical second-order Sturm–Liouville equation, which may be written as(1.1)where *p*(*x*), *q*(*x*) and *w*(*x*) are all real valued and continuous with *w* positive and locally integrable, and both 1/*p* and , this being the set of all measurable functions *f* : (*a*^{*}, *b*^{*})→ such that on every compact interval . Williams *et al*. (2004) mainly confined their attention to homogeneous trees with *p*(*x*)=*w*(*x*)=1, usually also with *q*(*x*)=0. Before summarizing their work and that of the present paper further, the tree is defined and other relevant work on the Sturm–Liouville problem of (1.1) is indicated.

Figure 1 typifies the tree topology, shows the Dirichlet boundary conditions used unless otherwise stated and defines the edge and vertex levels, where *n* is the number of levels and *b* is the branching number. The trees are defined such that edge properties (i.e. *p*(*x*), *q*(*x*), *w*(*x*) and can vary between levels but not between edges at any level. In this paper, *x* is a local coordinate for each edge, so that *a*^{*}=0; all trees are classified as *repetitive* or *non-repetitive*, depending upon whether or not the edge properties at all levels are identical, and such trees are sub-divided into *uniform* or *non-uniform*, depending upon whether or not *p*(*x*), *q*(*x*) and *w*(*x*) are all constant functions. Hence, a repetitive uniform tree is a homogeneous one, whereas a repetitive non-uniform tree is not.

There has been much interest in developing algorithms and numerical software to compute the eigenvalues and eigenvectors of the classical Sturm–Liouville problem defined around (1.1) (e.g. Coddington & Levinson 1955; Marletta & Pryce 1991; Marletta 1994; Pruess *et al*. 1995). These algorithms and programs have been used to investigate the eigenvalue distribution of (1.1) when *a*^{*} is a regular point and *b*^{*} is either regular or singular, under separated self-adjoint boundary conditions. Further algorithms and programs have been developed so that both periodic and linked boundary conditions can be accommodated (Bailey *et al*. 2001). This work was motivated by the need for accurate eigenvalue estimates for (1.1), despite the analytic difficulties, which are such that few examples have so far been analysed. Furthermore, in both the regular and singular cases, precision can be given to these results by enclosing them in intervals whose bounds can be proven to be correct (see the recent paper by Brown *et al*. (2000)). There is also much current interest in the problem of homogeneous trees (Evans & Harris 1993; Evans *et al*. 2001) with the recent work of Sobolev & Solomyak (2002) being of particular relevance because they show that for an infinite tree the eigenvalues of the free Laplacian in one dimension form bands of absolutely continuous spectra with eigenvalues of infinite multiplicity in the gaps. For other operators on a homogeneous tree, having similar nature, the band-gap structure of the spectrum was established earlier by Carlson (1997) with the Hill operator. Sobolev & Solomyak (2002) also consider the effect on the complete spectrum of introducing a small perturbation in the form of a real-valued potential together with a coupling constant. Note that we use the term gap in the present paper similarly to the above, i.e. the gap can contain one, or occasionally more, isolated eigenvalues.

### (a) Summary of Williams *et al*. (2004)

The W–W algorithm (Wittrick & Williams 1971, 1973*a*), see the brief summary in §2, was developed well over 30 years ago and has been applied with increasing sophistication to problems involving buckling and vibration in structural mechanics ever since. Much wider applications are possible, using the theorem (Balakrishnan 1995) underpinning the algorithm, to any field requiring eigenvalues of self-adjoint systems of differential equations. These can be calculated to almost machine accuracy and none is missed. In fact, the W–W algorithm has not yet been used extensively in other disciplines, although it has been applied to, for example, fluid vibrating in piping systems (Frid 1989, 1990), heat diffusion (Mikhailov & Vulchanov 1983; Mikhailov *et al*. 1983; Mikhailov & Ozisik 1984), filtering (Zhong & Williams 1999), wave propagation (Williams *et al*. 1995) and vibration of spinning structures (Wittrick & Williams 1982).

Williams *et al*. (2004) illustrated the value of the algorithm in mathematics by studying Sturm–Liouville equations on large homogeneous trees in depth. These typically involved 10^{13} equations and eigenvalues, which often coincided to form high multiplicity ones. Computation was extremely quick (e.g. figure 3 was found in 0.006 s using double precision arithmetic on a SUN Ultra 10 333 MHz computer) and numerically stable because the multi-level subsysteming corollary of the theorem underpinning the W–W algorithm was used.

Numerical results (Williams *et al*. 2004) confirmed the theoretical bounds of Sobolev & Solomyak (2002) on the bands into which the spectrum is divided by gaps split by one eigenvalue of very high multiplicity *M*_{1} (e.g. see their typical result of figure 2). Additionally, a structural mechanics-based analogy, confirmed by numerical results, proved exact equations for *M*_{1} and for the high multiplicities of some of the eigenvalues in the band (e.g. figure 3). These covered all values of *b* and *n* and dividing these equations by the number of eigenvalues in one band-gap interval gave dimensionless results which became exact for *n*→∞ (e.g. the fractions in figure 3). Finally, the fragmentation of multiple eigenvalues caused by introducing a potential was studied numerically and interpreted using a structural mechanics analogy.

### (b) Main results of present paper

We show that all the eigenvalues of trees, whether repetitive and/or uniform or not, can be computed from a series (*r*=1, 2, …, *n*) of substitute stepped chains (see figure 4). (The stepped chain is formed by collapsing the tree so that all members at a particular level are adjacent, thus producing a chain with a stepped topology.) Hence, a very simple equation is derived which gives all of the eigenvalues of a repetitive uniform tree with Dirichlet boundary conditions. Here *r* is the number of levels within a sub-tree; for example, *r*=2 for CDEFGHJ in figure 1, and the substitute stepped chains are defined fully when the related theory is presented. Their existence is a very useful result because both exact and approximate (e.g. finite element; Zienkiewicz & Taylor 1988) programs able to solve chain problems are relatively plentiful, particularly if programs for the analogous bar structure of structural mechanics are included, whereas the tree program of Williams *et al*. (2004) is unique and not widely available. Another very significant contribution is a proof that all eigenvalues of the tree, except those given by the substitute stepped chain with *r*=*n*, are multiple, with multiplicities given by simple theoretically proven equations which involve only *r*, *b* and *n*. Hence, the process of finding the eigenvalues of trees and their multiplicities is split into the two steps of finding their multiplicities from these equations and computing their numerical values from the *n* substitute stepped chains.

These steps are illustrated in table 1, which is discussed more fully in later sections. For now we note that: the square roots of the eigenvalues are given in order in the central column; they were obtained from substitute stepped chains *r*=1, 2, …, 8 as indicated by the table of occurrences, in which the row and column of each unit entry show the eigenvalue and the value *r* which gave it; and each entry in the table of multiplicities is for a sub-tree with the value of *r* at its head and is the multiplicity of the eigenvalue to its left, for example the 15th eigenvalue is and has multiplicity 54 for *n*=8, reducing to 2 for sub-tree *r*=5.

This very simple and powerful procedure leads to proofs of many useful conclusions concerning eigenvalues of both repetitive and non-repetitive uniform trees, some of which also apply to non-uniform trees. It is also shown that numerical results remain accurate as *n* is increased to exceptionally high values (e.g. *n*=10^{6}) to simulate *n*→∞.

The set of theorems presented was initially deduced from proven results of structural analysis using the complete analogy that exists between (1.1) and a bar of a vibrating structure, so that the tree problem can be treated as a structure which consists of a set of rigidly connected axially vibrating bars which have the required tree topology but are all collinear, which is permissible in analysis even though it is impossible for real bars. Those familiar with the vibration of structures will often find it helpful to consider this analogous structure, briefly summarized in table 2.

The W–W algorithm is used extensively in the proofs of the theorems and in the theory and software used to find the eigenvalues of the substitute stepped chains. Therefore, it is summarized in §2, applied to the substitute stepped chain problem in §3 to give equations suitable for programming and used in some of the proofs of theorems in §§5, 6, 8 and 10.

## 2. Summary of the Wittrick–Williams algorithm

This summary is briefer than the previous one (Williams *et al*. 2004) but is sufficient.

### (a) Theory

The W–W algorithm applies to the following mathematical problem. When two or more differential equations have linking conditions imposed at vertices, the system equations can be written as(2.1)where ** A**(

*λ*) is a real, symmetric (

*N*×

*N*) system matrix and

**denotes the**

*X**N*eigenvector components at the vertices.

**is continuous between poles and the elements of**

*A***are transcendental functions of**

*A**λ*, e.g. trigonometric, hyperbolic or Bessel functions. The linking conditions are continuity of the function at the vertices and the Kirchoff condition. In structural mechanics, these are analogous to displacement compatibility and force equilibrium requirements at the nodes of a structure. A generalized theorem for the W–W algorithm was presented by Balakrishnan (1995; see also Yukhno 1995) which stated, with notation changes made to accord with most structural mechanics papers, the following.

*J*(*λ*), *the number of eigenvalues (counted to multiplicity) of* ** A**(

*λ*)

**=**

*X***0**

*in the interval*[0,

*λ*],

*for λ positive, is given by*(2.2)

*where J*

_{0}(

*λ*)

*is the number of zero eigenvalues (counted to multiplicity) of*

**(**

*A**λ*)

^{−1}

*in*[0,

*λ*]

*and s*{

**(**

*A**λ*)}

*is the number of negative eigenvalues (counted to multiplicity) of*

**(**

*A**λ*)

^{−1}.

The W–W algorithm relates to the Sturm sequence property of the generalized linear eigenproblem (*A*^{*}−*λ**B*^{*})*X*^{*}=**0**, where *A*^{*} and *B*^{*} are symmetric matrices, *A*^{*} is positive definite and *X*^{*} is the eigenvector. This fact forms the basis for one of its proofs (Wittrick & Williams 1973*b*; Simpson 1984; Leung 1993), as follows. Let the linear eigenproblem approximately represent the same problem as (2.1) represents, using any discretization procedure such that the error disappears as the order *N*^{*} of the linear eigenproblem approaches infinity. Now let with *X*^{*} ordered such that internal elements of the edges precede those at the vertices, i.e. they precede the ** X** of (2.1). The Sturm sequence property of the linear eigenproblem gives . Hence, (2.1) and (2.2) can be deduced as follows. Arresting the Gauss elimination after all rows involving have been pivotal gives

**(**

*A**λ*) as the untriangulated part of the matrix, which corresponds to

**and so gives (2.1). Then (2.2) follows too. Moreover, if contains vertices of one or more subsystems as its last elements, the proof of the W–W algorithm extends to include sub-structuring in structural mechanics problems (Williams 1971), and the analogous**

*X**recursive subsysteming*of this paper. Hence, recursive subsysteming is a corollary of theorem 2.1. Now (2.2) must be applied to the subsystem first and the resulting

*J*(

*λ*) becomes an extra quantity summed to obtain

*J*

_{0}(

*λ*) when (2.2) is applied to the parent system. The simplicity of the application of recursive subsysteming is illustrated in steps (i)–(ix) of §2

*b*, which implement the W–W algorithm, and by its application to recursive chain subsysteming, see around both (3.9)–(3.15) and (3.17)–(3.22).

The W–W algorithm is identical to (2.2) except that *λ* is given a numerical value, *λ*_{t}, and , or when subsystems are used.

Here *j*(*λ*_{t}) is determined from the differential equation and is the number of eigenvalues in [0,*λ*_{t}] when Dirichlet boundary conditions are imposed, for example in vibration problems it is the number of natural frequencies in [0,*λ*_{t}] of a member whose ends are clamped.

### (b) Steps to apply the W–W algorithm

The application of the W–W algorithm is illustrated by the following summary of its computational steps, in which *J*, *j*, *J*_{0} and ** A** are calculated at

*λ*

_{t}.

Select a trial (positive or negative)

*λ*_{t}.For each of the linked differential equations, compute

*j*, the number of eigenvalues ∈[0,*λ*_{t}] when it has Dirichlet boundary conditions, and also establish the relationship between*y*and its derivatives at the two boundaries of the equation (for Sturm–Liouville equations,*y*′ is the only derivative, see (3.4)).Use these relationships to assemble the system matrix

, for example using the well-established procedures used to assemble the stiffness matrix of structures when using the finite element method (Zienkiewicz & Taylor 1988).*A*Reduce

to its upper triangular form*A**A*^{△}by the usual form of Gauss elimination, noting that pivoting was found to be unnecessary for all results given in this paper.Calculate

*s*{} as the number of negative leading diagonal elements of*A**A*^{△}.Compute

*J*_{0}as*j*summed over all edges.Compute

*J*from*J*=*J*_{0}+*s*{}.*A*Use

*J*and any appropriate convergence routine to choose a new*λ*_{t}.Go back to step (i), or terminate if convergence is achieved.

When recursive subsysteming is used, steps (ii)–(ix) are looped over for each subsystem in turn, starting with the innermost subsystem, with the small adjustments that *J* computed at step (vii) becomes *J*_{s} for the subsystem which has Dirichlet (i.e. clamped in the structural mechanics case) boundary conditions imposed where it is linked to its parent system or subsystem, and *J*_{0} at step (vi) is obtained by summing *J*_{s} over all contained subsystems as well as *j* for all edges that are not within these subsystems.

### (c) Additional comments on the W–W algorithm

The earlier engineering proofs (Williams & Wittrick 1970; Wittrick & Williams 1971, 1973*a*,*b*) of the W–W algorithm, of which only the last two cover problems with negative as well as positive eigenvalues, may also be regarded as proofs of the structural mechanics equivalent of theorem 2.1.

The W–W algorithm applies in much more general contexts than that of this paper, for example to include: higher order differential equations than second-order Sturm–Liouville ones; linking topologies of general network form; and situations, analogous to structural mechanics ones, for which the *x*-axes of the linked edges rarely coincide, so that geometric transformations are needed when obtaining the linking equations.

## 3. Application of the W–W algorithm to Sturm–Liouville problem on trees

Here we discuss the derivation of the edge equation and *j* for the uniform second-order Sturm–Liouville equation and then show how the W–W algorithm applies these to solve tree problems, including non-uniform edges discretized into numerous uniform segments.

### (a) Derivation of the uniform Sturm–Liouville edge equation and *j*

The governing equation for a uniform edge follows from (1.1) as(3.1)where *w*, *p* and *q* have appropriate constant values. The general solution is then(3.2)

This solution is more general than that in Williams *et al*. (2004) because the latter was for *p*=*w*=1 and *q*=0, so that . However, the difference is only in the definition of *α* in (3.1) and so the derivation of (3.3)–(3.5) is identical to that of appropriate ones of (3.3)–(3.9) in Williams *et al*. (2004). Therefore, their derivation is only summarized below.

First, substituting the algebraic boundary conditions for *x*∈[0,*L*], i.e.(3.3)into (3.2) gives expressions for *A* and *B*. Hence, the first derivative of (3.2) has the values at *x*=0 and at *x*=*L* given by(3.4)

Because is used, (3.4) is analogous to the dynamic member equation for a bar in structural mechanics and so is called the edge equation. Specifically, *λ*, *y*, *p*, *q* and *w* are defined in the right-hand column of table 2. Then multiplying (3.4) through by *p* gives the member equation as follows. , , *y*_{L} and *y*_{R} are the amplitudes of the sinusoidally varying axial forces and displacements at the left- and right-hand ends; *α* is determined from (3.1); and the (2×2) matrix is the dynamic stiffness matrix. This analogy enables physical insight to be used extensively to interpret the proofs and calculated eigenvalues of this paper.

Finally, imposing the Dirichlet boundary conditions *y*_{L}=*y*_{R}=0 required by the W–W algorithm on (3.4) causes the edge to have eigenvalues (*k*=1, 2, …), such that , giving(3.5)where [.] denotes the greatest integer not exceeding the value in the brackets.

For later use in the paper, note that a Neumann condition can be imposed on the left-hand end of the edge of (3.4) by treating it as a subsystem with and applying the W–W algorithm. Hence, Gauss elimination gives and so the subsystem representing this special edge has(3.6)The corresponding result for a Neumann right-hand condition is easily seen to be identical to (3.6) except that the subscripts R are replaced by L.

### (b) Application of W–W algorithm to solve problems with chain and tree topologies

Equations (4.2)–(4.4) of Williams *et al*. (2004) showed how recursive subsysteming gave amazingly fast solutions to the tree problem by a procedure which: eliminated *y* at D in figure 1 for the sub-tree which connects vertices C, D, F and G; used the resulting matrix ** A** twice (to allow for the sub-tree (CEHJ); and the edge equation for BC to assemble the next larger size of sub-tree and used subsysteming to eliminate

*y*at C, etc. This theory is not repeated here both because it is unaltered by the introduction of

*q*into the definition of

*α*in (3.1) and because it was not used to obtain any of the results presented in this paper, although it was used as one way to check them.

The substitute stepped chains used in the present paper consist of edges linked together to form chains. Similarly, edges for which one or more of *p*, *q* and *w* are *x* dependent must be approximated by a very large number, *n*_{s}, of connected segments, i.e. very short edges, for which *p*, *q* and *w* are constant and which thus form non-uniform chains. Therefore, recursive subsysteming equations for these two types of chain are now presented, which both start with a two-edge system and recursively add an edge to get successive subsystems.

Figure 5*a* indicates non-uniform chain subsysteming for edges *c*, *d*, *e*, …; with the ends of *c* and *d* numbered as shown in the first row. The second row indicates that the first subsystem consists of *c* and *d* and has the three vertices numbered as shown. Then the subsysteming eliminates vertex 1 and results in *c*^{*} with its vertices (=ends) renumbered as 1 and 2. The third row indicates that the next level of subsysteming repeats the previous level except that *c* is replaced by *c*^{*} and *d* by *e*, etc. Now suppose that subscript *i*=1, 2, 3, …, *n*_{s}, is used to denote the *n*_{s} edges *c*, *d*, *e*, …; the left- and right-hand ends of edges are denoted by subscripts L and R; and preserving continuity we equate zeroth and first derivatives at the internal vertex 1. Hence for any of the subsystems of figure 5*a* prior to elimination of the internal vertex 1 (e.g. see on the left of the second row of the figure), this gives(3.7)

Hence, using (3.4), (3.8) becomes the equation for the three vertices of the *i*th row of figure 5*a*, in which *δ* and the terms involving ** B** are given by (3.9)–(3.13).

Let(3.8)Hence, also using (3.5), the equations computed by the recursive subsysteming are: the initial conditions of (3.9); those obtained by looping through (3.10)–(3.14) for *i*=2, 3, …, *n*_{s}; and (3.15).(3.9)

(3.10)

(3.11)

(3.12)

(3.13)

(3.14)

The ** A** and

*J*of the subsystem representing the general edge of (1.1), i.e.

*A*_{s}and

*J*

_{s}, are then given by(3.15)

The novel technique introduced herein, *recursive substitute stepped chain subsysteming*, differs from the above because: the factors involving *b* (see figure 4) need to be introduced; in order to match figure 4 the new edges *d*, *e*, … are added at the left of *c*, *c*^{*}, … in figure 5*b* instead of at the right; hence subscripts *i* and *r* below denote a sub-tree to the right of a vertex at level *n*−*i* or *n*−*r* (see figure 1); and the right-hand nodes now have Dirichlet boundary conditions because they are all at the right-hand end of the tree. Therefore, the recursive subsysteming needs only to retain vertex 2 when eliminating vertex 1 from substitute stepped chain *r*, so that (3.8) is replaced by (3.16) in which *E*_{i} is given by (3.17) and (3.18) and *δ*_{i} is given by (3.17), (3.19) and (3.20).(3.16)Hence, the recursive equations for stepped chain *r* for repetitive or non-repetitive uniform trees are: the initial conditions (3.17); those obtained by looping through (3.18)–(3.21) for *i*=2, 3, …, *r*; and when *r*=*n*, (3.22).(3.17)(3.18)(3.19)(3.20)(3.21)

Note that *J*_{r} is the only information needed to converge by bisection on any required eigenvalue of stepped chain *r*; *B*_{r} is not used and so need not be computed; and owing to the Dirichlet condition at the left-hand end of the complete tree, *J* of its stepped chain is given using the above equations with *r*=*n*, i.e.(3.22)

Note that for very large *r*, (3.18) causes underflow. This is avoided very simply by multiplying *E*_{i} and *B*_{i−1} by 1/*E*_{min} whenever *E*_{i}<*E*_{min}. *E*_{min}=10^{−20} was used to get the results presented. Such scaling does not alter the value of *J*_{i} computed by (3.21) and so there is no need to record how often it is done.

The stepped chain equations can be modified to solve the three variant problems given by non-uniform edges and trees with either left- or right-hand Neumann conditions. The last two variants are dealt with in §§8 and 9, respectively, while for non-uniform edges terms involving cot and csc in (3.16)–(3.20) must be replaced by terms given by prior application of (3.9)–(3.15).

## 4. Exceptionally well-conditioned and efficient nature of substitute stepped chain computations

The stepped chain computations: make negligible storage demands because (3.17)–(3.22), plus (3.9)–(3.15) if needed, require at most one (2×2) matrix and this matrix and all scalar storage can be reused at every cycle of the loop, i.e. storage is independent of *n*; never cause overflow or underflow (see (3.22)) of real numbers; and do not cause integer overflow because (3.21) shows that *J* cannot exceed *r*(1+*j*_{a}), where *j*_{a} is the average value of *j*_{i} in [*j*_{1},*j*_{r}], whereas the earlier sub-treeing method, outlined in the first paragraph of §3*b*, counts eigenvalues of the tree to multiplicity and so *J* grew very rapidly as *n* increased and consequently often caused overflow.

Numerical stability was phenomenally good. Results for the first and (*n*−1)th eigenvalues of the stepped chain for repetitive uniform trees with *b*=2 or 10 and with *p*=*w*=1 and *q*=0 were found for numerous high values of *n*. These demonstrated almost exactly quadratic convergence as *n* increased. The highest value of *n* used was 10^{6} and it gave no sign of ill-conditioning. The first and (*n*−1)th eigenvalues were selected because the table of occurrences presented later in table 3 shows that for any *n* they define the boundaries of the bullet-shaped curves of figure 2. Sobolev & Solomyak (2002) gave the exact equation for the lower bound for *n*=∞ and *L*=1 as(4.1)and they also gave the upper bound as *π* minus this value, due to the symmetry of the spectrum (proved below for the finite tree). Using (3.17)–(3.22) with *n*=10^{6}, the values *L*1 and *U*1 (see figure 2) were obtained which showed excellent agreement with (4.1) to approximately 11 significant figures for *b*=2 and 12 significant figures for *b*=10. These results were obtained using a 3 GHz Pentium 4 personal computer, which took 50 s to get the *b*=2 result and a similar time when *b*=10.

*n*=10^{6} was used above because the exceptional ability of the substitute stepped chain to obtain very high accuracy approximations for trees with *n*→∞ is valuable due to exact equations for *n*→∞ not usually being available for the wide range of trees covered by the theorems and coding of the present paper. Additionally, the almost quadratic convergence means that running *n*=10^{6} is rarely required, for example using parabolic extrapolation with the results for *n*=10^{4} and 2×10^{4} of the *b*=2 problem above gave 14 s.f. agreement with (4.1).

## 5. Theorems for non-repetitive trees with Dirichlet end conditions

The theorems of this section are for non-repetitive trees, whether uniform or non-uniform. We recall that the *r* shown in figure 1 is the number of levels within a sub-tree, for example *r*=2 for sub-trees CDFG and CEHJ.

*For non-repetitive trees with Dirichlet end conditions, any eigenvalue of sub-tree r for which the eigenvector has identical y*_{i}(*x*) *all along every edge at level i*=(1, 2, …, *r*), *with i (like r) measured from the right-hand boundary of the tree, is also an eigenvalue of all sub-trees with higher values of r, including r*=*n, when these all have Dirichlet left-hand boundary conditions*.

Consider sub-tree *r*. For example, in figure 1, *r*=2 gives the sub-tree CDFG formed by the three edges connecting vertices C, D, F and G. Because edges at level *i* share the same *y*_{i}(*x*), including where they are linked (i.e. at D for the example), their differential equations must all be satisfied if one is. This will be true for all levels of the tree, so it only remains to consider the left-hand vertex of the sub-tree, i.e. C for the example. Because the sub-tree has Dirichlet left-hand boundary conditions, this vertex has *y*=0. Now any other of the *b* sub-trees rooted at the same vertex (i.e. CEHJ for the example), which are all identical to each other by definition of the complete tree, can have *y*(*x*) equal everywhere to −*y*(*x*) of the original sub-tree, i.e. CDFG in the example. In the analogous structural problem, this means that the sub-trees are vibrating in anti-phase. Thus, the Kirchoff and continuity conditions (see (3.7)) are satisfied at the root vertex (e.g. at C) if the remainder of the tree, for example to the left of C, has *y*=0 everywhere and the constraint that *y*=0 at the root is removed. Thus, the sub-tree eigenvector gives an eigenvalue of the parent tree. ▪

This is illustrated by every row of the table of multiplicities in table 1, for example row 15 is fully populated for *r*≥4 and is void for *r*<4.

In the following theorem, an asterisk is used to denote a non-repetitive tree, hence is the eigenvalue multiplicity for a non-repetitive sub-tree of length *r*, whereas *M*_{r} is the higher multiplicity for repetitive sub-trees which we will derive later (see theorem 6.2).

*The compete set of eigenvalues for a non-repetitive tree have multiplicity* *given by*(5.1)

There are *b* sub-trees at the root vertex of sub-tree *r*, any two of which could have been chosen in the above proof. This gives *b*−1 possible independent eigenvectors of the complete tree. Additionally, the root could have been taken at any one of the *b*^{n−r−1} vertices at its level, i.e. at either of the two nodes C and K for the previous example, for which *n*=4, *b*=2 and *r*=2. Hence (5.1) follows.

In the case *r*=*n*, the root of the sub-tree is also the root of the tree (e.g. A in figure 1), so there are no other sub-trees and hence . ▪

This result is also illustrated by every row of the table of multiplicities in table 1. Thus, the 15th row is generated by *n*=8, *b*=3 and *r*=4. Hence, (5.1) gives =2×3^{3}=54, i.e. this was how the 54 in the *r*=8 column of the *k*=15 row of table 1 was obtained. Likewise, (5.1) also gave the values of shown for sub-trees with *r*=4, 5, 6 and 7, i.e. the values 1, 2, 6 and 18. Obviously, (5.1) causes the non-zero entries of every row of the table of multiplicities, reading from the right, to be 1, (*b*−1), (*b*−1)*b*, …, i.e. the first two entries are 1 and *b*−1 and then each successive entry is *b* times larger than its predecessor. This is illustrated by every row of table 1.

*Eigenvalues of sub-tree r can be computed as the eigenvalues of a substitute stepped chain r, which consists of the r levels shown in* *figure* *4*, *where* (×*b*^{−i}) *means that the edge is identical to an edge at the same level of the tree, except that p, q and w have been divided by b*^{i}.

Owing to theorem 5.1, all edges for *i*=1, i.e. at level *n*−2 in figure 1, share the same *y*_{i}(*x*) for *x*∈[0,*L*]. Hence, they share the same *y* and *y*′ at the vertices at levels *n*−1 and *n*−2 and so their *py*′ there sum to *b* times the *py*′ of one of them. This alternatively results from using only one of the edges but multiplying its *p*, *q* and *w* by *b*, which leaves *α* and *y*′ unaltered (see (3.1) and (3.4)) so that *py′* is multiplied by *b*. Arguing similarly at the other edge levels of the sub-tree shows that the substitute stepped chain obtained by multiplying *p*, *q* and *w* by *b* progressively at each vertex when moving from left to right shares eigenvalues identical to those of the sub-tree. Because (3.1) shows that *α* and *λ* are unaltered by dividing *p*, *q* and *w* by a common factor, i.e. *b*^{n−1} in this case, the substitute stepped chain shown in figure 4 can alternatively be used. ▪

The substitute stepped chain of figure 4 is preferred, because its level *n*−1 (i.e. the right-hand) edge is shared by all values of *r* and *n*. Hence, the table of occurrences shows which substitute stepped chain gave each eigenvalue, as indicated in §1. Thus, in table 1, the *r*=4 column of the table of occurrences indicates that substitute stepped chain 4 gave the 6th, 15th, 24th and 33rd eigenvalues for the tree with *n*=8. As can be seen in the table of occurrences, the eigenvalues of the substitute stepped chain have a multiplicity of one. To obtain all the eigenvalues of the tree using the substitute stepped chain requires the computation of eigenvalues of the whole set of stepped chains from length *r*=1 to *n*. For example, table 1 shows that all the eigenvalues of tree *r*=8 are obtained from all eight substitute stepped chains.

## 6. Theorems for repetitive trees with Dirichlet end conditions

The underlying theory for the tree problem allows for general edge length, *L*. For repetitive trees, we assume *L*=1 and for uniform trees we further assume *p*=*w*=1 and *q*=0, so that (see (3.1)). Hence, is used in the tables instead of *α*. As an illustrative example, table 3 was computed for the uniform repetitive tree obtained from the tree of table 1 by replacing its edge lengths *L*=0.999^{i} by unity. Four other illustrative examples were also solved by computation, two each being uniform and non-uniform. They shared a common table of occurrences which is given, along with their eigenvalues, in table 4 which also defines the problems. Note that eigenvalues for uniform trees which are known to equal *gπ* (Sobolev & Solomyak 2002; Williams *et al*. 2004) are referred to as such, even in the tables, see also figure 2, or see (3.1) and (3.5). However, the theorems and proofs remain valid for non-uniform edges, if *gπ* is replaced by the *g*th eigenvalue *α* of an edge with *L*=1 when it has Dirichlet boundary conditions at both ends.

*For repetitive uniform trees with Dirichlet end conditions, L*=1 *and* *for g*=0, 1, 2,…, *there is exactly one eigenvalue of multiplicity M*_{1} *at α*=*gπ and, for each sub-tree r*∈[2,*n*], *and there are N*_{r} *other eigenvalues of multiplicity M*_{r}, *where*(6.1)

All edges of any substitute stepped chain *r* for a repetitive uniform tree share the same eigenvalues when they have Dirichlet end conditions. Hence, *j* is the same for all edges and so (3.17)–(3.21) give *J*_{r}=*rj*+*m*, where 0≤*m*≤*r*−1. Because *j*=*g*−1 just below *gπ* and *j*=*g* just above *gπ*, we have just below *gπ*, or *J*≥*rg* just above *gπ*. Hence, the number of eigenvalues at *gπ* cannot be less than unity. However, there is clearly one, and only one, eigenvalue at *gπ*, for which the eigenvector is such that each level of the stepped chain has the same shape as the eigenvector associated with the *g*th eigenvalue of an edge with Dirichlet end conditions. However, owing to the final equation of (3.7), modified by the *b*^{−i} of figure 4, the amplitudes of the eigenvector at each level, reading from right to left in figure 4, are in the ratios 1 : *b* : *b*^{2} : … It follows that there must be *r* eigenvalues for of which only one is at *gπ*. ▪

The tables of occurrences of tables 3 and 4 confirm this theorem, for example, for *r*=8, there are seven eigenvalues below the first eigenvalue of an edge with Dirichlet end conditions, i.e. below *π*, for the three uniform trees or, more generally, below the *k*=22 result for all five problems, for all of which the seven lower eigenvalues are those for *k*=1, 5, 8, 11, 14, 17 and 21.

*Let* 1≤*r*≤*n and*(6.2)*Then the multiplicity M*_{r} *for a repetitive tree with Dirichlet end conditions is given by*(6.3)*where f*=[*n*/*r*], *h*=*n*−1−(*f*−*κ*)*r and* *for all u* (1≤*u*≤*f*).

The substitute stepped chain *ur* consists of *u* subsystems which: are stepped chain *r* scaled by *b*^{−(t−1)r} (*t*=1, 2, …, *u*); are connected end to end; and have the same eigenvalues as stepped chain *r* when they have Dirichlet end conditions. Thus, if their eigenvector amplitudes, reading from the right, are 1 : *b*^{r} : *b*^{2r} : ⋯ : *b*^{ur}, all necessary conditions are met for the removal of Dirichlet conditions at the *u*−1 interfaces to have no effect.1 Therefore, the multiplicity *M*_{r} of the repetitive tree equals the sum of for *u*=1, 2, …, *f*, which proves the first equality of (6.3).

In (6.3), the case will occur in only if *n* is divisible by *r*. In this case, *u*=*f* and (we note that in (5.1) the case is special), and the remaining terms in the sum correspond to 1≤*u*≤*f*−1. If *n* is not divisible by *r* then *κ*=0 and by (5.1) for all *u* (1≤*u*≤*f*). Thus, treating the case *u*=*f* separately in the sum, if it occurs, we have ▪

Equation (6.3) is a much improved variant of (5.5) of Williams *et al*. (2004), which gives identical answers and was derived in a very different and less rigorous way. Theorem 6.2 is confirmed by the following observations. Row *k*=7 of the tables of occurrences of tables 3 and 4 indicates that the *r*=6 result duplicates the *r*=3 one while row *k*=11 shows that the *r*=4, 6 and 8 results duplicate the *r*=2 one. The table of multiplicities of table 3 shows how this causes multiplicities to combine; for example, the *M*_{1}=547 at *k*=11 in table 3 combines the entries 486, 54, 6 and 1 of rows *k*=16, 15, 14 and 13 of table 1.

*For repetitive uniform trees with Dirichlet end conditions, the complete set of eigenvalues* *for the tree consists solely of those obtained by summing the r eigenvalues of multiplicity* , 1≤*r*≤*n*.

The total number, *T*, of eigenvalues counted to multiplicity, summed over *r*, can be found by considering a non-repetitive tree that differs infinitesimally from the repetitive one. For example, the tree of table 1 has edge length *L*=0.999^{i} which differs very slightly from the tree of table 3 which has edge length *L*=1 for all edges. In detail, the row *k*=11 in table 3 shows a repeating eigenvalue for four substitute stepped chains with four unit entries in the table of occurrences. In contrast, table 1 shows that these four eigenvalues become distinct as seen in the four rows *k*=13−16. Hence, via (5.1) and theorem 6.1(6.4)Now it is easy to see that(6.5)So substituting (6.5) in (6.4) gives(6.6)But (5.1) of Williams *et al*. (2004) showed that the total number of eigenvalues in (*gπ*,*gπ*+*π*] is also given by the r.h.s. of (6.6), which proves the result. ▪

*For repetitive uniform trees with Dirichlet end conditions and L*=1, *eigenvalues α in* (0,*π*] *are symmetrically situated about α*=*π*/2 *and repeat (i.e. α is gπ greater) in* (*gπ*, *gπ*+*π*], *for g*=1, 2, 3, ….

From theorems 5.3 and 6.3, all eigenvalues of a repetitive uniform tree can be found from the substitute stepped chain computations of (3.17)–(3.22). Because the trees are repetitive and uniform, the subscript *i* can be omitted. Additionally, all occurrences of *α* in (3.17)–(3.20), other than in the combination *αL*, result in *α* appearing to power unity in both terms on the r.h.s. of (3.19). Hence, because *α* is always positive, it cannot affect *s*{*δ*_{i}} in (3.21). Therefore, it cannot affect the values of the eigenvalues converged on and so will be ignored here. Thus, only the combination *αL* with *L*=1 need be considered in (3.17)–(3.22). This occurs only in the forms cot *α* and csc^{2}*α*. Now and . Hence, *B*_{i} and *δ*_{i} at (*π*−*α*) are equal to their values at *α*, but are of opposite sign. However, as *α* increases *π*−*α* decreases. Therefore, whenever *α* has a value *α*^{*} for which *s*{*δ*_{i}} causes *J*_{r} in (3.21) to increase as *α* increases, *J*_{r} also increases as *α increases* through *π*−*α*^{*}. Thus, eigenvalues in (0,*π*] are symmetrically situated about *α*=*π*/2. Additionally, and . Therefore, all results for *α* repeat for *α*+*gπ*. ▪

The repetitive aspect of theorem 6.4 is why table 3 was not continued beyond and comparison of the results for *k*=3 and 19 illustrates its symmetry aspect because *π*−2.4188584=0.7227342. Hence, it would have been sufficient to show just the rows down to (i.e. the first 11 rows) plus the row for.

## 7. Constructing tables for non-repetitive trees

Theorems 5.1–5.3 were stated and proved for non-repetitive trees and they were used to show how the tables of occurrences and of multiplicities of table 1 could be constructed. However, *f=*0.999 was used to approximate the case *f* infinitesimally less than unity, i.e. an infinitesimal perturbation of a repetitive tree. The rows of the tables of occurrences and of multiplicities were constructed from substitute stepped chains *r* (=1, 2, …, *n*) via theorems 5.1–5.3 and so must be valid for any non-repetitive tree. However, the order in which the rows occur in the tables is not unique, as table 5 now demonstrates.

Temporarily ignoring its first columns, table 5*a* was obtained using (extended) columns *r*=1 to 5 of the table of multiplicities of table 1, and making adjustment from *b*=3 of table 1 to the *b*=4 of table 5 using (5.1). The substitute stepped chains then gave the eigenvalues in the order shown in table 5*a*. Noting that the table of multiplicities becomes a table of occurrences if all entries other than unity are deleted (as table 1 illustrates), table 5*a* gives the eigenvalues of the substitute stepped chain *r*=2 as , 9.8586252, etc. However, the eigenvalues in table 5*a* are clearly not in ascending order and so its rows must be reordered as shown in table 5*b*. Note that the values of *k* in table 5*a* were deduced from those of table 5*b*.

The discussion above shows that one way of finding the eigenvalues of any non-repetitive tree is: to start by constructing a table of multiplicities (and hence the related table of occurrences) from that of table 1; to calculate the eigenvalues of its substitute stepped chains 1, 2, …, *r* and place them by this table of multiplicities; and then reordering rows to give all the eigenvalues of the tree in ascending order and with their multiplicities next to them. Note that the table of multiplicities contains the tables of multiplicities for a tree with any lower value of *n*, from which its eigenvalues can be obtained in ascending order by reading across to the eigenvalues column. However, it is important to note that this tree is a sub-tree of the original tree. Thus, in the case of table 5 and *n*=2, the lengths of its two levels are 0.7^{3} and 0.7^{4}, respectively.

## 8. Trees with Neumann condition *y*′=0 at right-hand boundary

It is readily seen, by verifying that their proofs work for either *y*=0 or *y*′=0 at the right-hand boundary, that theorems 5.1–5.3 remain valid for trees with Dirichlet/Neumann conditions at their left/right-hand boundaries. Using (3.6) and the sentence beneath it, it is easy to see that (3.17)–(3.22) remain valid for the stepped chains *r* (=1, 2, …, *n*) so long as the right-hand Neumann end condition is represented by replacing (3.17) with(8.1)It is also easily shown that theorem 6.4 and its proof remain valid for repetitive uniform trees with Neumann right-hand boundary conditions, because *α* still only exists in the forms cot *α* and csc^{2}*α*, because the *α* tan *α* of (8.1) is (cot *α*)^{−1}. Hence, it is only necessary to consider eigenvalues for in (0,*π*/2], as illustrated by the computed results of table 6. It will now be proved that as *r*→∞, i.e. *n*→∞, the four gaps in the table between and (*k*=1, 2, 3, 4) remain unaltered, for example, for *b*=3, there is a gap of width 0.5235988−0.2526803=0.2709185 and there is also a gap below of width 0.0431608.

*For repetitive uniform trees with n*→∞, *L*=1 *and with Dirichlet left-hand boundary conditions and Neumann right-hand ones there is a gap in the spectrum for α in* (0, *δ*), *with eigenvalues spaced throughout it, where* *for b*=2, *and* *for b*≥3. *This pattern repeats for α in* (*gπ*, *gπ*+*δ*), *and its reflection occurs for α in* (*gπ*−*δ*, *gπ*), *where g*=1, 2, 3, ….

The final sentence is proved directly from theorem 6.4. The proof for *α*∈(0, *δ*) starts by noting that (8.1) and (3.18)–(3.22) give the first eigenvalue for *r*=2 (with subscripts omitted from *α* because the tree is repetitive and uniform) as that for which, from (3.21), . Hence(8.2)gives the first eigenvalue for *r*=2. It will now be proved that, for *b*≥3, no value of *r* gives an eigenvalue between and *δ*_{3}, the lowest eigenvalue for *r*=3, for example in table 6. The proof consists of showing that stepped chains *r*, for *n* infinite and 3<*r*<*n*, have their first eigenvalue below and their second one above *δ*_{3} as follows. Owing to (3.21) and because *j*=0 from (3.5), the first eigenvalue decreases as *r* increases. Therefore, the first eigenvalues for *r*=4, 5, … lie below . Hence, it only remains to prove that, for *b*≥3, the second eigenvalue of stepped chain *r* (=4, 5, 6,…) cannot lie below *δ*_{3}, as follows. Without writing them in detail, it is obvious that the stepped chain equations (8.1) and (3.18)–(3.22) could be replaced by similar ones, but starting from the left-hand end of the chain. Assuming that (8.1) is still used for edge *n*−1 (using the numbering of figure 1), the last vertex appearing in the equation is *n*−1. Now suppose that a Dirichlet condition is imposed there. Hence, (3.21) with *j*=0 shows that this reduces *J* by at most one. Therefore, only the first eigenvalue can lie below the lowest eigenvalue of either part into which the chain has in effect been divided by the Dirichlet condition. These consist of a single edge with a Dirichlet condition at one boundary and a Neumann one at the other and a stepped chain *r*−1 with Dirichlet boundary conditions. Now from (8.1) the first eigenvalue for the single edge is given by cot *α*=0, i.e. *α*=*π*/2, while the lowest eigenvalue for the chain *r*−1 when *n*→∞ is the *η* of (4.1). The lowest eigenvalue of the chain for *r* finite must exceed *η*. But it is readily verified that, for *b*≥3, (4.1) and (8.2) give *η*≥*δ*_{3} and hence the second eigenvalue of chain *r* exceeds *δ*_{3}, which proves the *b*≥3 case of the theorem.

The proof for *b*=2 differs only because *η*≃0.3398 and so that *η*<*ν*. Because (8.2) gives *ν*=*δ*_{3}, this completes the proof for *b*=2 and hence the theorem is proved. ▪

The results for table 6 illustrate both *b*=2 and *b*≥3 cases.

## 9. Trees with Neumann condition *y*′=0 at left-hand boundary

Such trees still have the Dirichlet right-hand boundary condition. Hence, it is readily verified that theorems 5.1–6.3 and their proofs remain valid except: in theorem 5.3, the left-hand boundary condition is now a Neumann one for the substitute stepped chain *n* only; in theorem 6.1, (6.1) is replaced by *N*_{r}=*n* when *r*=*n*; and in theorem 6.2 the possibility *r*_{1}=*n* must be excluded, so that *M*_{1} is reduced by one.

Clearly, (3.17)–(3.22) remain unaltered for the substitute stepped chains *r*=(1, 2, …, *n*−1), but when *r*=*n* the last time (3.19) and (3.21) are used, i.e. when calculating *δ*_{n} and *J*_{n}, (3.6) must be used to account for the Neumann left-hand condition. This requires no new equations because the problem is now the stepped chain of §8 rotated 180° about its centre, so that *b*^{−1} must replace *b* and the scaling given beneath (3.22) becomes: whenever *E*_{r}>*E*_{max} divide *E*_{r} and *B*_{r} by *E*_{max}, where *E*_{max}=10^{20}.

Hence, for non-repetitive trees, the tables of occurrences and of multiplicities can be constructed exactly as in §5. Similarly those for repetitive trees can be constructed exactly as in theorem 6.2, except that all multiplicities to which substitute stepped chain *n* contributed are one lower than before and there are correspondingly more entries of unity in each table. Thus, in the *r*=8 column of the table of multiplicities of table 3, the two entries of 55 and the entries of 547 and 2187 become 54, 546 and 2186 while there are eight unit entries instead of four. Note that entries for *r*=1, 2, …, 7 are not altered and so still relate to trees with *n*=1, 2, …, 7 and Dirichlet boundary conditions at both ends and so are not valid for trees with *n*<8 and a left-hand Neumann condition.

The eigenvalues of table 7 act as illustrations for substitution of a Neumann left-hand boundary condition into all except one of the trees of tables 1, 3, 4 and 5. Asterisks indicate singlefold eigenvalues given by the substitute stepped chain *n* with its Neumann left-hand boundary condition. According to the above theory, for uniform trees, half of these should replace the singlefold eigenvalues for the substitute stepped chain *n* of the earlier tables for uniform trees because they all had *n*=8. Comparison of the results in tables 3 and 4 with those of table 7 shows that this has indeed happened. For example, the four singlefold eigenvalues for *r*=8 in table 3 (e.g. 1.2329949) are absent from table 7 and there are eight eigenvalues with asterisks, including four due to the symmetry. Additionally, the four eigenvalues denoted by dagger in table 7, including one due to the symmetry, were observed to have a multiplicity one less than in table 3, for example 54 instead of 55. Otherwise, the theoretically proven requirement that all other eigenvalues of tables 3 and 7 are identical is obeyed. Hence, all the results of table 7 were predicted by the theory.

## 10. Equations giving the eigenvalues of repetitive uniform trees with Dirichlet conditions at both boundaries

We are able to establish the following.

*For all values of b, the complete set of distinct eigenvalues in* (0,*π*] *of a repetitive uniform tree with Dirichlet conditions at both boundaries are given by π*, *π*/2 *and*(10.1)

The set is complete because the eigenvalue at *π* is given by theorem 6.1 and the eigenvalue at *π*/2 is given by the theorem stated in the electronic supplementary material, which also shows that (10.1) gives all the remaining eigenvalues of the stepped chains to which theorem 6.3 relates. ▪

Equation (10.1) satisfies the theorems of §§5 and 6 without making them redundant.

## 11. Conclusions

The Wittrick–Williams (W–W) algorithm has been summarized, along with the steps needed to implement it and its underlying theorem. It is applicable to finding with certainty the eigenvalues of any self-adjoint system of differential equations, regardless of their number, their (even) order, or the form of the network obtained by linking them. The results presented have indicated the great power of the algorithm, both when obtaining the eigenvalues numerically and also when proving theorems, noting that every use of *J* in the proofs implies use of the W–W algorithm.

The bands of eigenvalues for a finite uniform tree are discrete. This is because the use of the W–W algorithm requires a restriction that the tree is finite. The numerical results show that the bands become more densely populated as the tree increases in size and approaches the structure that is obtained for an infinite tree where the eigenvalues of the free Laplacian form bands of absolutely continuous spectra.

The illustrative problem considered in depth was the topical one of finding the eigenvalues for Sturm–Liouville equations on trees for any values of *n* and *b*, the number of levels and branching number of the tree. The following principal conclusions have been theoretically proved and usually also illustrated by examples.

Nearly, all the eigenvalues appear to multiplicity, and (5.1) and (6.2), which depend only upon

*r*,*b*and*n*, have been derived to give their multiplicities for, respectively, non-repetitive and repetitive trees.Tables (or equivalent when programming) of occurrences and of multiplicities can be constructed

*a priori*from these equations, with the former being independent of*b*. The details of such tables depend on whether the tree is repetitive or non-repetitive, but not on whether or not it is uniform.Substitute stepped chains can be used to easily obtain all the distinct eigenvalues of trees (see figure 4), and clear rules have been given about which row of the above tables the eigenvalues should be placed in. These substitute chains simplified the theory presented as well as giving much insight into the tree problem, particularly when used with the analogous structural mechanics problem of an axially vibrating stepped bar.

These stepped chain computations are almost unbelievably well conditioned, having been tested up to

*n*=10^{6}, i.e. for a tree with approximately 10^{999}^{999}linked Sturm–Liouville equations. This is a big improvement over the earlier (Williams*et al*. 2004) sub-treeing method.Moreover, unlike the sub-treeing approach, the stepped chain results can relatively easily be duplicated by other workers, using a variety of existing computer programs, either by data preparation or by making minor program adjustments.

The percentage of the distinct eigenvalues that are singlefold eigenvalues approaches zero as

*n*→∞. This follows from (5.1) and (6.1).The equations given can be used to find the fractions of the total number of eigenvalues which the eigenvalue multiplicities approach as

*n*→∞, although this has not been done in this paper because, as figure 3 shows, it was proved for some of the eigenvalues (but not, for example, those denoted by*X*) by Williams*et al*. (2004).Trees with Dirichlet/Neumann conditions at their left/right-hand boundaries have a gap in the spectrum as

*n*→∞, which often has well-separated eigenvalues spaced throughout it, as discussed in §8. This behaviour is not present for Dirichlet conditions at both boundaries.Trees with Neumann/Dirichlet conditions at their left/right-hand boundaries have identical eigenvalues to those given by Dirichlet/Dirichlet boundary conditions, with the exception of singlefold ones.

Very importantly, it was possible to derive (10.1), which gives all the eigenvalues for any repetitive uniform tree with Dirichlet conditions at both boundaries.

## Acknowledgments

The authors are extremely grateful to Prof. B. M. Brown and Prof. W. D. Evans of Cardiff University for calling their attention to the relevance of the W–W algorithm to the infinite tree problem in mathematics. The work forms part of an EPSRC grant no. GR/R05437/01.

## Footnotes

Electronic supplementary material is available at http://dx.doi.org/10.1098/rspa.2007.1905 or via http://www.journals.royalsoc.ac.uk.

↵In the structural analogy, this means that equilibrium and compatibility are both satisfied where the subsystems are connected.

- Received January 10, 2007.
- Accepted August 31, 2007.

- © 2007 The Royal Society