WW (‘.'w-I—E. ‘,

7.":1‘1'“r1~1".’-T1T1"1"-"1'-7"" 1 111111113'1'“ 1.1" '1""'""."":
‘11 111111111111 T.'1T1 11.533111! 111111.1211111‘. ' 11"? ' "12' ' ‘ "
I1'1,1l1'11"v"'"""11'1”"11"1'11',""11111111, "'1' -.""'11'11111-1- ' 11.1“ '1'1'111';
1, 1 111111.11, , 1 .1'1'1111111—3'1;,i-1.1:1-1 111.1111 “-1111

ilJ""'.'1", '11". 1' 1, '"I'lv." "1""1'1'1
' 11111111'. 1111,1111'|.","11' (1'111'1'

”1",", |,1'11'1111- 111111 11" ”'11111 ,1", 1 1'1 '1‘? 1111111111111111\ 1'11'1'1‘II 11,11. '11,, 1'171'111'1"',11'1' '11

'1 " 1E'1 I
111 1 1 , 1. 11.11.11 .11, 1 '1'11111111'11111111 11.11111 _, -1111, 14:1
"1""'"1,,'1',|111"11'111,1"'11111',11'1.1”(1111111'1"""11'-1'11]"“1111'1' "1'1"M'g"'r,,"1"1'1""'""11'1 111,1

.1 1 ,
.I . f .

11'1 $11 1 .'-1 1'11'13‘1113,
’ '.r1 3.; :1— Ir.

‘10'11‘1 ,1, '11 - 11,11 ,

     
  

          
 
  
  
 
 

   
  

        
 

1'} ' .'1|1."'::..1', {11.1.}: 111'. 0:111"?
' '1' 1'" 1'", ,1'1"1,'," " " 1'1 11 ”111, "1A ' """"'"""'1.‘111:‘1"-1..“.‘ .-";‘T.'.'-f:'—
11', 1,111 111111,," 1,, 1.111, 1 1,11
1 1' 11111111'11',"1',11111111111111111111111111,1,1, 1111' 1 11,111, ,1, '1'1'1'1'11,

3
" 11,111"11 NM 1.: ' 111,"."11‘ ”11""1'11"'3i'1";':.11'1"f‘f:'1
‘ 1‘ 1, 111-1' 1'11'1 1'1'1'1'1'11'11'1 1'1"1"",'1" 1 1, 1,1‘1'1'1" 111 '1 1 ,1,11'11"‘1'",.'1"1111 1" ----, '
H .1 1.11,',1, 11111111111111.111111111 1 1111 1111 ,1'1'111'111'111'11111111',1, '1'1'1'111. ,1" 1

'11'1'1’” "'

' '"11' 1 '1" "" "1
1 , '11'111"11 ,
,1, ,1111 1,1,, 111

1:111, 111511 .
11'1' 1"11111
"",11' 1,1'1"1'11.'

M1111, '.

 

 

 

 

 

 

.' 1
x 11.11 1 11
t

1' 1 . ,1
.. ..
' 1
1 1
' 19 r
a k n
I: . . ‘ t I
1' 1 1+- 11 '
' 1
l‘ ‘1 '.',
1 ' 1 1

111.

"1‘ 1 ,

1.

,.

:

 

 

THESlS

 

 

 

This is to certify that the

dissertation entitled
BOUNDS ON THE EIGENVALUES FOR
CERTAIN CLASSES OF DYNAMIC SYSTEMS
presentedby

MOHAMED ASHRAF ZEID

has been accepted towards fulfillment
of the requirements for

Doctor 01“ P_h_i_LQ§_QDJLY_degreein Mechanical Engineering

Major professor

February 26, [982
Date

 

MS U is an Affirmative Action/Equal Opportunity Institntion 042771

 

MSU

LIBRARIES

 

 

 

RETURNING MATERIALS:
Place in book drop to
remove this checkout from

 

 

MAM-14001

 

n. your record. FINES will
be charged if book is
returned after the date
stamped below.

_ F5? 0 ’2 I994
LsL‘oe

 

 

BOUNDS ON THE EIGENVALUES FOR
CERTAIN CLASSES OF DYNAMIC SYSTEMS

BY

Mohamed Ashraf Zeid

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Mechanical Engineering

1982

ABSTRACT

BOUNDS ON THE EIGENVALUES FOR
CERTAIN CLASSES OF DYNAMIC SYSTEMS

BY

Mohamed Ashraf Zeid

Is it possible to estimate bounds on the eigenvalues of a system from
a pictorial model? Classical methods first derive the state equations,
then from the state matrix we obtain the bounds on the largest eigen-
value. For a class of systems, we obtain the bounds on the largest
real part and the largest imaginary part of the eigenvalues by inspect-
ing a graphical model of these systems. The graphical model used is a
canonical form of the bond graph, namely the gyrobondgraph.

Bond graphs are graphical models of systems. They depict the in-
trinsic energy structure of the systems by lines called bonds. The
nodes of the bond graphs are idealized energy handling devices depicted
by a standard set of alpha-numeric characters. As a tool for estimat-
ing the eigenvalues of systems, bond graphs offer a suitable medium.
They can model systems that handle different forms of energy, therefore,
they cover a wide range of engineering problems. A canonical form of
the bond graph, namely the gyrobondgraph, can be simplified to an
oriented graph.

We first studied systems with uniform parameters. They are common
in lumped models of continuous systems. The bounds obtained are used

as a base to estimate the bounds for systems with general parameters.

For systems whose gyrobondgrpah is a simple full graph, we estab-
lished a relation between the structure of the associated oriented graph
and the largest real and largest imaginary parts of the eigenvalues.
This relation is presented as an algorithm for computing the bounds and
is based on the order of the system and the number of gyrators in the
gyrobondgraph. The bounds given are comparable to bounds obtained
using the standard methods while the number of computations required is
substantially reduced. We also give a recursive formula for computing
the characteristic polynomial of systems with uniform parameters. This
formula was used to establish the bounds on the eigenvalues.

For a special case of systems whose gyrobondgraphs are a simple
partial graph, we could obtain bounds on the largest real part and
imaginary part of the eigenvalues. For the other classes, the standard
techniques had to be used to obtain the bounds.

The yield of this work is the reduction in the computational effort
required to obtain the bounds. This reduction becomes of major impor-
tance when the bounds are estimated for large scale systems. More
study is required to extend this eigenvalue estimation procedure to

cover other classes of systems.

© 1982

MOHAMED ASHRAF ZEID

All Rights Reserved

DEDICATION

To my father and mother

ii

ACKNOWLEDGMENTS

I wish to express my special appreciation to Dr. Ronald Rosenberg
for his guidance, advice and support throughout the preparation of
this thesis. His engineering insight has been an infinite source of
inspiration, and working with him has been a professionally fulfilling
and rewarding experience.

I also express my appreciation for the guidance and assistance of
Dr. Albert Andry, Dr. Hassan Khalil, and Dr. Norman Hills. Their
interest in my study and their ideas and critique have been most valu-
able.

A special word of appreciation is extended to my parents for their
continuous and consistant support and assistance. Their encouragement
has been of greal value. A special word of thanks to my wife Marilyn
for her support, patience and for her help in typing the rough draft of

this manuscript.

iii

CHAPTER

II.

III.

TABLE OF CONTENTS

INTRODUCTION . . . . . . . . . . .
Motivation . . . . . . . . . . .
Computing the Eigenvalues . . . .
Eigenvalues and Graphs . . . . . .
Summary of Results . . . . . . . .
Organization . . . . . . . . . . .
BACKGROUND AND DEFINITIONS . . . .
The Bond Graph . . . . . . . . . .

Bond graph definitions . . . .
Examples of bond graph models .

The Gyrobondgraph . . . . . . . .

The point graph . . . . . . . .
A class of systems . . . . . .

Graph Theory . . . . . . . . . . .
Graph 8 O O I O O O O O O O O O
Matrices associated with graphs
Spectrum of a graph . . . . . .

Linear Algebra and Matrix Theory .

BOUNDS FOR SIMPLE FULL GRAPHS . .

Introduction . . . . . . . . . . .

Uniform Parameters . . . . . . . .
Examples of the bounds . . . .
Bounds on the largest eigenvalue

Properties of cycles . . . . .
Partial R field . . . . . . .

iv

PAGE

10

10

11
16

18

25
29

32
32
42
45

47

'52

52

57

59
63
73
79

CHAPTER

IV.

VI.

General Parameters . . . . .-. . . . . . . . . . . . .

Examples 0 O O O O O O O O O O O O I O O p O O O O O
Bounds on the largest eigenvalue . . . . . . . . . .

IMPROVING THE BOUNDS FOR SIMPLE FULL GRAPHS . . . . . .

Intrwuction O C O O O O O O O O O O O O O O O O O O 0

Examples 0 O O O O O O O O O O O O O O O O O O O O 0
Procedures for inspecting th point graph . . . . .
The optimal graph 0 O O O O I O O O O O O O O O O O

The Characteristic Polynomial . . . . . . . . . . . . .

The coefficients of the characteristic polynomial .
A recursive formula . . . . . . . . . . . . . . . .

SIMPLE PARTIAL GRAPHS . . . . . . . . . . . . . . . . .

A Non-Connected Partial R Subgraph . . . . . . . . . .

Estimates from the State Matrix . . . . . . . . . . . .

CONCLUSION . . . . o . o o . . . . . . . . . . . . . .

Slmary O O O O O I O O 0-. O O O D O O O O 0 O O O O 0

Comparison to Other Methods . . . . . . . . . . . . . .

Further Directions of Research . . . . . . . . . . . .

APPENDICES

1.

2.

The Coefficients of the Characteristic Equation . .

Recurrence Formula for Computing the Characteristic
Po lynomi a1 0 O O I O O O O O O O O O O O O O O O O

The Characteristic Polynomial of an Oriented
Graph Containing a Bridge . . . . . . . . . . . . .

The Characteristic Polynomial of a Path . . . . . .
The Characteristic Polynomial of a Star . . . . . .
Bounds for Largest Eigenvalues of Trees . . . . . .

General Parameters Problem . . . . . . . . . . . .

PAGE

81

81
83

88
88
90
92
99
102

103
109

115

117

119

121

121

121

127

129

134

137

139

140

141

142

CHAPTER PAGE

8. The State Matrix of a Class of Simple Partial
Graphs O O O O O O O O O O O O O O O O O O O O O O O 1 46

9. Lower Bounds on Largest Eigenvalues for
General Graphs O O O O O O O O O O O ‘ O O O O O O O O 1 48

10. Bounds on Largest Eigenvalues Using Subgraphs . . . . 150
1 1 0 Optimal Graphs O O O O O O O I O O O O O O O O O O Q 1 52

12. A Definition of the Bond Graph Language . . . . . . . 154

“WMNCES . O O C . C O C O O O O O O O O O C O O O O O O O 1 S 8

vi

CHAPTER

1.1

I.2

1.3

I.4

II.1

II.2

IIO3

II.4

11.5

11.6

II.7

II.8

II.9

II.10

II.11

II.12

LIST OF FIGURES

A comparison of different approaches for estimating
eigenvalues of systems . . . . . . . . . . . . . . .

Different mechanical transational systems . . . . .
The bond graph models . . . . . . . . . . . . . . .

The point graph . . . . . . . . . . . . . . . . . .

(a) A sketch of a mechanical transational system
(b) The bond graph model . . . . . . . . . . . . .

(a) A sketch of an electrical system
(b) The bond graph model . . . . . . . . . . . . .

Transforming the bondgraph to a gyrobondgraph . . .

(a) and (b) Simple full graphs; (c) simple full I,
partial R graph; (d) simple partial I, full R graph,
(e) simple partial I, partial R graph; (f) complex
full graph . . . . . . . . . . . . . . . . . . . . .

Classification of Gyrobondgraphs . . . . . . . . . .
Simplification of the gyrobondgraph to a point graph

The point graphs corresponding to the gyrobondgraphs
in Figure II 0 4 O O O O O O O O O O O O C O O I O O O

(a) A mechanical system; (b) the bond graph
model; (c) the gyrobondgraph; (d) the point graph .

A graph with four points . . . . . . . . . . . . . .
m oriented graph . O O . O O O O I O O O I O O O O

(a) A path with four points: P4; (b) a cycle

With three mints : C3 0 O O O C O O O O O O O O O O
(a) An.odd length (numbered) cycle; (b) An even
length (numbered) cycle with even power; (c) An

even length (numbered) cycle with odd power . . . .

vii

PAGE

17

17

21

23
24

'26

26

28
34

34

34

36

CHAPTER

II.13

II.14

II.15

II.16

II.17

II.18

II.19

II.20

III.1

III.2

III.3

111.4

(a) A directed unlabeled graph; (b) and (c)
two different labelings of G; (d) and (e)
two subgraphs of G . . . . . . . . . . . . . . .

(a) A graph G, with point v and line x; (b)

A graph G obtained from G by removing the point
v; (c) A graph G2 obtained from G by removing the
line x . . . . . . . . . . . . . . . . . . . . .

(a) A complete graph with three points: K ;

(b) and (c) two possible power orientations on

a complete graph K4 . . . . . . . . . . . . . .
(a) A complete bigraph: (b) A complete

bigraph K (a star) . .

K2,3;
1,3 ° .

A graph G that has two components: G1 and G .
The subgraph G2 has a bridge y and a cut point v.

The direct sum of two labeled oriented graphs.
(a) and (b) are two labeled oriented graphs;

(c) the cortesian product of their points;

(d) the direct sum graph . . . . . . . . . . . .

(a) A (unoriented) graph G; (b) the adjacency
matrix of the graph G . . . . . . . . . . . . . .

(a) An oriented graph with 4 points
(b) The unoriented graph obtained from G
by relaxing the orientation . . . . . . . . . . .

(a) and (b) two point graphs for two identical
systems except for the parameters of their
energy storage elements . . . . . . . . . . . . .

(a) A hydraulic system; (b) the bond graph
model; (c) the point graph . . . . . . . . . . .

(a) A mechanical vibrating system; (b) the bond
graph model; (c) the point graph, with spectra
given by

.1?" .,2K .3?
Spec(G) = [:1V2i, i 1 iT-i Ila—3 0,0] . . .

a) A bond graph of a lumped parameter model

of a two power distributed system: transverse
vibration in a prismatic beam with shear
corrections. The model is adapted from L.S.
Bonderson (BG9). Here we used three elements.

b) Is the point graph model. . . . . . . . . . .

viii

PAGE

36

38

38

39

39

41

41

44

55

58

60

62

CHAPTER PAGE

III.5 The largest imaginary part of the eigenvalue
of some trees: b; versus their number of
mints N O O O O O O O O O O O O O O O O O O O O O O O 64

III.6 Bounds on the largest imaginary part of

the eigenvalue: b versus number of points N

for bound graphs: KN, K1,N-1’ PN’ CN . . . . . . . . . 65
111.7 The largest imaginary part (b) of the

eigenvalues of paths and cycles versus the

number of points N . . . . ... . . . . . . . . . . . . 66

III.8 a) A hydraulic system composed of a water
tank and four tubes; b) the bond graph model;
c) the gyrobondgraph; d) the oriented graph
with 5 points and spectrum: (21, -2i, 0,0) . . . . . . 67

111.9 (a) Is an optimal graph for the graph in (b). . . . . . 69

III.10 In (a), (b) and (o) Are three oriented graphs with
four points and five lines. The orientation on the
lines is different on each graph. The spectra of the first
two are identical, the spectrum of the third is
different . . . . . . . . . . . . ... . . . . . . . . . 69

III.11 a) A mechanical transation system consisting
of two masses, two springs, a lever with
transformation ratio equal 1. b) The bond
graph model; c) the gyrobondgraph reduction;
d) the corresponding oriented graph with four
points and spectrum:

Spec(G) = [in/'2', 1-5, 4.5, 4-5] . . . . . . . 78

111.12 The point graph of a lumped parameter model
of a beam . . . . . . . . . . . . . . . . . . . . . . . 80

111.13 Reducing the point graph of a system to an
equivalent point graph with unit inertias . . . . . . . 82

111.14 A two power model of 3 beam.

I1 = pAAx, 12 = Ax/K TA, 13 4

A-is the beam cross-section area,¢>is the mass

density, j is cross-section area moment, E is Young's
modulus, K is Timoshenko shear coefficient, T is

the shear modulus (adapted from BG9). . . . . . . . . . 86

, G and G 91

IV.1 Dissecting a graph G into subgraphs G1 2 3 . . .

ix

CHAPTER

IV.2

IV.3

IV.4

IV.5

IV.6

IV.7

IV.8

IV.9

IV.10

IV.11

VI. 1

A point graph with ten points and largest
degree A a 7 O O O O O O O I O O O O O O O O O O O

The point graph of a Timoshenko beam
with three microelements . . . . . . . . . . . .

Three possible dissection of a tree into subgraph

The point graph of a lumped model of a Timoshenko
beam. (a) A dissection that gives a lower bound
on b ; (b) a dissection that gives the upper

boun on b1 . . . . . . . . . . . . . . . . . . .

(a) and (b) are two directed paths with m and n
points. In (c) is a grid that is the direct
sum Of Pm wd Pn . O O O O O O O C O O 0 O O O O O

(a) a path P ; (b) an even cycle C9 and in (c)
. . e 4
is the direc sum of P2 and C4. . . . . . . . . .

The direct sum of a path P and a star Sn . . . .

2

a) The point graph with gyrator constants: a,b,c,d,e,f

b) The six basic figures with two points; c) The six

basic figures with four points. . . . . . . . . .

a) An oriented graph similar to the point graph
in Figure IV.9. except for the orientation on line
b. b) the basic figures with four points. . . . .

A point graph with a bridge uv, the character-
istic polynomial is:

P(G)=PN_4.S4 + PN-3°SB . .
A flow chart summarizing the results.
B.L. are boundary lines. The number in
the circles refer to a block in Table VI.1. . .

PAGE

91

91

96

98

100

100

101

105

106

113

122

LIST OF TABLES

CHAPTER PAGE

II.1 The Bond graph standard set element . . . . . . . . . . 13

11.2 Variables that can be modeled as effort and
flow for various energy domains. . . . . . . . . . . . . 14

11.3 Possible causal assignments for bond graph elements . . 1S

III.1 The spectra of some trees. . . . . . . . . . . . . . . . 68
111.2 Summary of the spectra of cycles . . . . . . . . . . ... 71

III.3 Example of equivalence of the spectra of cycles. . . . . 76

IV.1 Summary of results . . . . . . . . . . . . . . . . . . . 123

xi

CHAPTER I

INTRODUCTION

I.l Motivation

Eigenvalues play a major role in the mathematical description
of dynamic systems. The solution of many physical problems depend on
the calculation, or at least the estimation, of some or all of the eigen-
values. In design, using interactive computers, the knowledge of an
estimate of the largest eigenvalue of the designed system is useful for
setting time limits of integration. For large scale systems, the use of
techniques for estimating the largest eigenvalue from the state matrix
proves to be expensive. A less expensive technique is to find the
estimates from a graphical model of the system.

An estimate of the largest eigenvalue at the graphical model
stage provides an early estimate since it is obtained without deriving
the state equations. As we prove, in some cases estimates obtained from
the graphical model are better than those obtained from the state
matrix. The main advantage of using the graphical model is that it
provides a relatively accurate and cheap estimate of the largest eigen-
value of the system.

Using the graphical model as a medium for estimating the larg-
est eigenvalue will enable relating the structure of the system to its

eigenvalues.

The goal of this work is to relate the eigenvalues of systems,

through an estimation technique, to a graphical model of the system.

I.2 Computing the Eigenvalues

Current methods to compute the eigenvalues of a system start
from the state matrix. As shown in Figure I.l, for each system a class-
ical approach is used to determine the state matrix; then from the state
matrix the eigenvalues are estimated or computed. Iterative techniques,
for example the QR algorithm, are used to find all the eigenvalues of
the system. A substantial presentation of these methods is found in
Wilkinson (NAl). Computer software that uses iterative techniques is
available in most mathematics software packages. Iterative techniques
require extensive memory and a large number of computational operations,
which is expensive in terms of computer time and memory. This becomes
a basic issue when dealing with large scale systems. At early stages of
design, a relatively accurate estimate of the largest eigenvalue is
all that is required. Computing this estimate requires a relatively
smaller amount of computations. Estimate of the largest eigenvalue are
calculated from the state matrix. They are usually given in terms of
inequalities that give an upper and lower bound on the largest eigen-
value. As an example, the well known Gerschgorin Theorem provides
bounds on all the eigenvalues in terms of circles in the complex plane.
The circles have their centers at the diagonal entries of the matrix
and their radii are equal to sum of the rows entries. A complete sur-
vey of these inequalities is given in Marcus (NA10); more recent re-

sults can be found in Wolkowiz (NAll).

”w” OTHERS...)

CLASSICAL CLASSICAL CLASSICAL CLASSICAL A UNIFIED
APPROACH. APPROACH. "PROACH. "PROACH. APPROACH:

THE
BOND
GRAPH.

 

 

 

 

 

 

 

 

TRADITIONAL METHODS: NEW APPROACH:

INEQUALITIES FROM INEQUALITIES USING
THE STATE MATRIX. THE BOND GRAPH
1 , IN A CANONICAL FORM

ESTIMATES OF THE EIGENVALUES

 

 

 

 

 

 

 

Figure I.1. A comparison of different approaches for
estimating eigenvalues of systems.

I.3 Eigenvalues and Graphs

In this work we attempt to relate the eigenvalues of a system
to a graphical model of that system, and develop a procedure that pro-
vides a relatively accurate estimate of the largest eigenvalue of the
system, derived from that graphical model.

Eigenvalues are associated with graphs through the adjacency
matrix of these graphs. In some cases, physical systems are represented
by graphs. In electrical systems, signal flow graphs are represented
by linear graphs, and their adjacency matrix was studied (GT9). In
chemistry, the adjacency matrix represented the atom connectivity matrix
(GT6). M. Kac used linear graphs and their adjacency matrix to study
the vibration of a membrane (GT10). A complete account of linear graphs
and their spectra is given in Cvetkovic (GT12). For the purpose of this
study, we chose a graph that can be used to model a variety of lumped-
parameter systems. These systems can represent different energy types:
mechanical, electrical, hydraulic and others. The spectrum of the sys-
tem is associated with the graph through the skew symmetric adjacency
matrix (cf.II.3.2.). For a class of systems we succeeded in establish-
ing bounds on their largest eigenvalue. These bounds are given as a
function of the structure of the graphical model.

Bond graphs are a unified approach that provides graphical
models for lumped-parameter systems that can belong to various energy
domains. They use a standardized set of idealized elements, depicted
by alphanumeric symbols, to represent the real elements of the system.
The energy and power flow between these elements is depicted in the bond
graph by lines called bonds. A complete description of bond graph model—

ing theory is found in (8G2) and a bibliography is found in (BGS). Bond

graphs offered a suitable medium for this study because they can be used
to represent different types of systems: thus the results obtained cover
a wide range of problems. Bond graphs can be reduced to a canonical form,
namely the gyrobondgraph (861). This in turn is simplified to an oriented
graph. Here we call the simplified graph: the point graph. Changing
the lines of the point graph by adding or deleting them indicates a
change in the structure of the associated system. Also the orderly
fashion that the bond graph provides for deriving the state equations,
enables relating the change in the structure of the point graph to the
eigenvalues of the system. This relation was obtained here for a class
of systems, namely those whose gyrobondgraphs are simple full graphs.
Figure I.3a,b and c represents the bond graph models for the
systems sketched in Figure I.2a,b and c respectively. In Figure I.4a,b
and c, we see the point graph resulting from simplifying the gyrobond

graphs of the bond graphs in Figure I.3a,b and c.

I.4 Summary of Results

For a class of systems, namely those whose gyrobondgraph is a
simple full graph (BGl), we established bounds on the largest eigen—
value of the corresponding system. These bounds are given in terms of
the structure of the point graph and the parameters of the elements of
the system. A procedure to improve these bounds by means of further
examination of the structure of the point graph is also given. For the
same class of systems, we established a recursive formula for computing
the characteristic equation of the system from the point graph. This
formula provided us with an insight into the nature of the spectra of

the system. It also offered interesting facts about the power orientation

 

 

 

 

 

 

 

 

 

 

 

l ‘— I: - -_‘ —|
’77///7//////////// ///,z/ r 1.7

(a) (b) (c)

Figure I.2. Different mechanical transational systems.

I I
t f (r;
C C /
WNW W \o\
0—-[I—-£—;—~ O—JI /0 0/ I“?
(a) ___._C)_____’ [19”’ L I. C:
1 t l t c
I C I I
(b) (c)

Figure 1.3. The bond graph models.

......_._.._,. 4:; >‘

(a) (b) (C)

Figure I.4. The point graph.

of bond graph. For some special cases, namely those systems whose gyro-
bondgraph is a simple partial graph, bounds for the eigenvalue could be
established. For other cases, and the remaining classes of systems, we
had to appeal to the traditional methods of using the state matrix.

A theoretical ground is now laid for further investigation of
the subject. more study is needed to establish a complete understanding
of this complex problem.

The results given in this work allow us to provide a certain
description of the eigenvalues of systems. This description is obtained
- by examining the associated point graph. As an example, consider the
point graphs given in Figure 1.3. Let A = a + ib, be an eigenvalue of
the corresponding system. Let Al be the eigenvalue with the largest
modulus. If we assume unit parameters then from the point graphs we

can conclude:

a) for all three systems in Figure I.l we have:

2 cos '—1— < A < J 5
6-1—

b) A of the system in Figure I.l.b. is the smallest
A in all three systems.
c) A of the system in Figure I.l.a. is smaller than
A of the system in Figure I.l.c.
d) for the systems in Figure I.l.a. and Figure I.l.b. we know

all their eigenvalues; they are:
[i i 2 cos (£710, i i 2 cos (3710, i i 2 cos (371)]
for I.l.b. the eigenvalues are:

(t i 2 cos (%%9, i i 2 cos (ZéLO, 0, O)

e) for the system in Figure I.l.c. we can compute the

characteristic equation which is given by:
(124.1) (A4+4A2+l)=0

The above equation can be solved to find the eigenvalues

of the system.

We note that the results given above were obtained without having to
find the state matrix. This, together with the small computational
effort required for obtaining these bounds, offers an advantage over
existing methods for estimating the eigenvalues for this class of

problems.

I.5 Organization

Chapter II is a brief presentation of definitions and basic
theorems used to prove the results presented in this work. This chapter
is organized in four sections: Bond Graphs, Gyrobondgraphs, Graph Theory,
and Linear Algebra. Some new definitions and concepts are introduced
at the end of sections 11.2. and II.3.

Chapters III and IV are the core results of this work. They
deal with systems whose gyrobondgraph is a simple full graph. In
Chapter III we establish upper and lower bounds on the largest eigen-
value of systems. The first part deals with systems that have elements
with uniform parameters; they occur in some models of continuous sys-
tems. The results obtained were then used in the second part as a base
to derive bounds for the more general case of systems with arbitrary
parameters.

Chapter IV presents methods to improve the estimate found in

Chapter III by examining the point graph and using a dissection procedure.

Also a procedure to find the coefficients of the characteristic poly—
nomial is given, along with some results concerning the properties of
the eigenvalues of a system in relation to its oriented graph. These
results provide a theoretical basis for the extension of this work.
The third part of this chapter presents some results that are used to
estimate bounds in the case of general parameters.

In Chapter V we deal with simple partial graphs. We give some
results concerning the largest eigenvalue for some special cases. Then
for the remaining classes of systems some results concerning bounds on
eigenvalues are given using the state matrix.

As discussed in the summary, this work does not answer the
original question completely. It gives an answer for a certain class
of systems, and lays the groundwork for answering the question more

generally.

CHAPTER II

 

BACKGROUND AND DEFINITIONS

In this chapter we discuss briefly the background material
used to derive the main results of this work, and we introduce some new
definitions. we first present briefly the bond graph definitions and
give two examples of bond graph models for a mechanical and an electri-
cal system. we then discuss the gyrobondgraph, and present important
properties of two classes of gyrobondgraphs. We proceed then to define
the point graph and the gyroadjacency matrix associated with it. In
section II.3. basic definitions and terminology of graph theory are given.
In section II.4. matrices associated with graphs are discussed and the
skew symmetric adjacency matrix is defined. For the sake of complete-
ness, some basic definitions from linear algebra and matrix theory are
given; also some useful theorems are presented.

The bond graph material is adapted from (8G7), (attached in
appendix). The reader interested in detailed presentation of bond graphs
is referred to Karnopp and Rosenberg (3G2). Graph theory terminology

and definitions are adapted from Harary (GT1) and Cvetkovic (GT2).

II.1 The Bond Graph

Bond graphs are pictorial models of dynamic systems. Each real
component of the system is modeled by one or more elements of an ideal—
ized set. The idealized elements form the nodes of the graph and are
depicted by alphanumeric characters. They are connected by lines,

called bonds, that are associated with the energy and power handling in

10

11

the real system.
For certain classes of dynamic systems, bond graphs offer
some advantages over existing modeling procedures:
1) They offer a unified modeling approach. By the use of
a standard set of graphical elements we can build a
model for systems that handle different types of energy;
for example, mechanical, electrical, hydraulic and
others.
2) They are orderly and compact and they provide a syste-
matic procedure for deriving the state equations.
3) Coupled with logical capabilities of digital computers,
bond graphs are distinguished as a basis for a unified

approach to computer aided modeling.

II.1.l Bond Graph Definitions

Here we present a brief discussion of bond graph definitions.

A complete presentation of bond graph language is given in the definition
paper by Rosenberg and Karnopp (see appendix).

The basic idea in a bond graph model is the use of idealized
energy and power handling elements to model real elements. This set of
idealized elements is depicted by alphanumeric characters, and makes the
nodes of the graph. The nodes are connected by lines called bonds, when-
ever power flows between idealized elements. The resulting picture is
the bond graph. The standard set of elements of a bond graph are:

(Se, 5 I, C; R; TF, GY; 0, l)

f;
They are: source of effort, source of flow, inertia, capacitance, re-

sistance; transformer, gyrator; common effort junction, and common flow

junction.

12

In Table II.1. the elements of the standard set are described
according to their idealized energy handling role in the model.

The Eggtg_are the places on the idealized elements where they
are connected to other idealized elements.

The bggd_is a line defined together with two variables: the
effort e(t), and the flow f(t). A bond connects two elements through
their ports whenever power flows between them.

In Table II.2. examples of variables that can be modeled as
effort or flow are given for various energy domains.

The 29325 P(t), is defined as the scalar product of the effort

and the flow:
P(t) a e(t) . f(t)

The power direction is a half arrow on one end of the bond
designating a positive power on that port.

The causality is a perpendicular stroke at one end of the bond.
It denotes the input/output sense of the effort and flow variables.

In Table II.3. are possible causal assignments for bond graph
elements. The sources and the juctions, by definition, have only one
possible causal assignment; while the other elements each have two pos-
sible ways for causal assignment as shown. In the third column of the
table, we used the convention that the variable on the left of the equal-
ity is the output.

The choice of one of two possible causality assignments on
the storage elements (I,C) will result in either an integral or a dif-
ferential relation for the element as shown. For the resistance, the

relation in that sense is invariant to the causality choice. For the

13

 

 

 

 

 

 

 

 

 

m o
m I m
a I u u PM me u me u as me as
I A T
n mm + N0 + H0 c H mm + mm + H0 no He 30am cOEEou
mm mm
u mm + Na + as a n me + Na + as me He
mm "no u .m mm n we u aw mm,c gov, vacuum :ossoo mcoauocsn mason mouse oflmmn
Hmauu u my «mixes I am «a A“
IIIMVCRVIIIJY
Huh n we HmAxvu n «m m a He nonwh>o
Nae u so Holxce I am me as
u be u utho mcm memo: mcm m no 0 came
Hos u we Hoaxes n No me E as m we p me u m 39 . m
um u m Anya n .Illmdlm mocmumammm houndwmmfio >muocm
o o Una
U! .I. m A3 u I|.ll‘ U wouaonamo
A HI 0
H I H I u
.Ffl I m AQVHI I m .Immm1nH meuhocH monoum >0hmcm
>hthuwnhm Auvm >hmuuwoum Auvm
co>fio any“ co>wm Auvm .AIIIIMm mousom 30am
>hmuuwohm Auvu >Hmuuwnum any“ 0
co>wu Auvo cm>wm Auvo .Allll.m mousom uhOuum moonsom >muocm mahom oco venom
Messed Homewacoz 00w>op mcfidpcm: mason mo
cofluMCMMoo Hone>m oEmz >mumcm mo 0Q>E hopes: oflmmm

 

 

.uswsmam uwm unaccoum nacho once one

.~.HH mane?

 

14

Table II.2. Variables that can be modeled as effort and flow for

various energy domains.

 

 

Domain Effort, e(t) Flow, f(t)
Mechanical Translation Force Component Velocity Component
Mechanical Rotation Torque Component Angular Velocity Component
Hydraulic Pressure Volume Flow Rate

Electric Voltage

Current

15

 

Table II.3. Possible causal assignments for bond graph elements.
Possible
Element Causal Form Causal Relation

 

Effort Source

s-——*

e

e(t) = E(t)

 

Flow Source

st-—-—s

f(t) = F(t)

 

 

 

 

 

 

 

 

-1
Inertia I|-¢——— f =¢I (Ia dt) ...Integration causality
Ih—| e = g [42(3)
dt
Capacitor C |-l-—— f = <_i_ [¢(e)]
dt c
C h—i e =¢gl (Jf dt) ...Inegration causality
Resistance R I‘— f = £1 (e)
R .‘_—_—4 e =QDR (f)
Transformer 1 m 2 e m e
}——a-TF}———L l 2
f m f
2 l
' m —1
l ITF 2 I fl - m-lf2
e2 = m el
G rator l r 2 e - rf
y 1--*GY —-I 1 " 2
e2 = rf1
r —l
l IGY I 2 I fl — r e2
—1
f2 - r e1
Common Effort 1 10 2 | e2 = e1, e3 — el
Junction = _(f + f )
3 l 2 3
Common Effort I l I 2 f = f , f — f
Junction 1 2 1 3 l
3 e = —(e + e )

 

 

 

 

16

resistance, the relation in that sense is invariant to the causality
choice. For the transformer and gyrator, the choice of causal assign-
ment on one bond forces the causal assignment on the other bonds.

The common effort junction will have one input effort, forcing
the causal assignment on the other bonds. The common flow junction will
have one input flow, forcing the causal assignment on the other bonds to
be output flow.

A systematic procedure that is given in (G82) takes the sketch
of a system to a bond graph model. From the bond graph, and following
a systematic procedure (G82), the state equations of the system are de-

rived in the form:
x = Ax + Bu

Now two simple examples for bond graph models of a mechanical

and an electrical system are given.

II.l.2 Examples of Bond Graph Models

A mechanical system

Consider the simple mechanical transational system given in
Figure II.l.a. It consists of a Mass M, a spring K, and a hydraulic
resistance R1.

The bond graph model is shown in Figure II.l.b. The effect of
gravitation is modeled as a source of effort, Se; the spring is modeled
as a capacitance C: the hydraulic resistance is modeled as a resistance
R and the mass is modeled as an inertia I. In this case all elements

are adjacent to a common velocity junction. The velocity on this

l-junction is the relative velocity:

17

 

 

 

 

 

I
I
«(1)
X: 05%éNzi
am :0

(a) (b)

Figure II.1 (a) A sketch of a mechanical transational system

(b) The bond graph model

I

 

Wt) __.V

d

.f)
______'f______,

hPD

“(D

 

O
F?

2

C
c
1
J
F}

37::U+——\——-e.;,.

(a) (b)

Figure 11.2 (a) A sketch of an electrical system

(b) The bond graph model

18

From the bond graph given in Figure II.l.b., and following a

systematic procedure, the state equations are then derived.

An electrical system

In Figure II.2.a. is given an electrical system consisting of a
voltage source, and inductance and a resistance in series, and a capaci-
tance and a resistance in parallel.

In Figure II.2.b. is the bond graph model. Note that the vol-
tage source is modeled as a source of effort; the inductance modeled
as an inertia. The source of effort, the inertia and the resistance R1
are adjacent to a common flow junction. The capacitance and the resis-
tance R2 are adjacent to a common effort junction.

From Figure II.2.b. the state equations of the system could

be derived in the form:

x = Ax + Bu

 

 

 

 

 

 

 

They are:
F.‘ F ‘ ' 1
‘31 TL fp Fl
L C1
= + V(t)
q _1, -_1_ q 0
L R C
- d l- 2 lj - A u u

 

Where p is the flux linkage on the inductance and q is the

charge on the capacitance.

II.2. The Gyrobondgraph

In the standard bond graph a set of 9 elements is used to model
lumped-parameter systems. As stated before they are (Se, Sf; I, C, R;

TF, GY; 0, l). Gyrobondgraphs are a canonical form of bond graph (BGl).

19

Gyrobondgraph model will have its elements from the set: (Se’ I, R, GY,
1). This is called a primitive set. A primitive set is any minimal
set, that is irreducible, of which all lumped-parameters dynamical sys-
tems are composed (3G6). A primitive set must contain:
1) a gyrator
2) one type of source: effort source or flow source,
(56 or Sf).
3) one type of energy storage: inertia or capacitance,
(I or C).
4) one type of ideal junction: common effort or common
flow, (0 or 1).

5) a dissipation R.

According to the above conditions, there exist eight primitive sets whose
elements are chosen from the standard set. The gyrobondgraph set is one
of these sets.

A bond graph that has its elements from the set (Se; I; R; GY;

l) is a gyrobondgraph if it satisfies the following adjacency conditions:

Adjacency Conditions
1) Each I is adjacent to a l-junction at each I port.
2) Each R is adjacent to a l-junction at each R port.
3) Each Se is adjacent to a l-junction.
4) Each GY is adjacent to two distinct l-junctions.
5) Each l-junction is adjacent to no more than one I, one
R, and Se’ and to no other l-junctions.
6) Pairs of l-junctions have no more than one GY (or one

multiport R) coupling between them.

20

Gyrobondgraphs can be obtained from bond graphs using the
following two step procedure:
(a) Replacements

Replace each S by an S6 and a GY.

f

f

Replace each C by any equivalent I and a GY.

C —&——— a I .a___ cy.4;__.

Replace each TF by two GY's in cascade, one of which
has unity modulus.

r l r

Replace each O-junction by a l-junction and a GY

at each port. The moduli are unity.

l l
GY l GY

 

 

 

 

—0_-

lzGY

(b) Simplifications
l. Simplify each two unit gyrators in cascade by a

single bond.

1 l
GY---GY

 

 

 

2. Combine all l-junctions that are directly bonded.

].-—-—-l = 1

Example

In Figure II.3.a. is the bond graph obtained in Figure II.2.b.
for the system sketched in Figure II.2.a. Applying the replacement

steps, we obtain the graph in Figure II.3.b. Applying the simplication

21

———-¥J\I:r\

I

31y:I)‘¢———-(:>

(a) £3""""
*6

ECU ‘

A]
l—hGY—H-I—eGY—a- GY—I
\

1 er
R . \R

(b) 8—-
e

'\I:I\

g,
1"
1

(c)

\—-—>

.__A.(3Nffl__a_/

ۤ.___a-

I
fi’fi
R

-I
2

~m’m 4—.

Figure II.3. Transforming the bondgraph to a gyrobondgraph.

22

steps we obtain the gyrobondgraph in Figure II.3.c. The * on I and R
denotes transformed elements. The parameters for the transformed ele—

men 118 are

*3
I Cl
R*=l_

R2

The state equations in terms of the transformed elements are

 

 

p ‘Rl ‘i p 1
E C1
= + V(t)
o -1
9* -1- 422 p* 0
L _—
c
1
.- d b J b .1 .. J

 

 

 

 

 

 

Classification of the gyrobondgraphs

Gyrobondgraphs are classified as simple or complex as follows:
"A gyrobondgraph is simple if every I element and every R
element is a one port. Otherwise the gyrobondgraph is complex."
They are classified as full I or partial I as follows:
"If the number of I-field ports is equal to the number of
l-junctions, the gyrobondgraph is full. Otherwise it is partial."
For the purpose of estimating eigenvalues, a classification defining
the fullness of the R field is useful. Following the line of the above
definitions, we classify a full R or partial R gyrobondgraph as follows:
"If the number of R-field ports is equal to the number of

l-junctions, the gyrobondgraph is full R. Otherwise it is partial R."

Note: (1) While "Full I, full R" characterizes all the l-junctions
in the gyrobondgraph as being adjacent to one I and one
R port, the partial I, partial R does not provide such

characterization.

23

 

I I I I
I I I I
1 ——a-G Y——>~[ 1—-——-¥-GY 1
I I
F? F?
(a) (b)

I I I

I I I

1 G)’ 1 I—dGY—dl

 

 

IJJ"F"‘—
*—
V—

(C) (d)

R
1 I
1
I G/|\
I—GY—sI—GY—q / Y 1 6‘”
R R
(e) (f)

Figure II.4. (a) and (b) simple full graphs; (c) simple full I, partial
R graph; (d) simple partial I, full R graph; (e) simple partial I,
partial R graph; (f) complex full graph.

24

Cl. ASS/F/CA T/ON OF GYROBOND GRA PHS

SIMPLE

A
1
l .

Arbi-
graph

Figure 11.5. I)
II)
A)
B)

1)
2)

a)
b)

 

YROBONDGRAP

B A

PARTIAL
I I

PARTIAL

1

PARTIAL

R

hiliill’ illlll' .‘IHIII’

l ‘ 2 1
Arbit Arbit.
'graph {graph ,

Simple:

Complex :

Full I: Each 1-junction
Partial I: At least one
I element.

Full R: Each 1-junction
Partial R: At least one
R element.

U.P.: All parameters of

G.P.: The parameters of
trary values.
Arbit. graph :

Tree:

II
EIHI E3
2
PARTIAL
R
iiIllIll’ iilllll"

Arbit
,graph

All R,I elements are one port.
At least one R or I element is a multiport.

has one I element adjacent.
1-junction does not have an

has one R element adjacent.
1-junction does not have an

the system are equal 1.
the system may assume arbi-

The oriented graph has at least one cycle.
The oriented graph has no cycles.

(2)

(3)

(4)

25

From this arises a need to define the l-junctions accord-
ing to their field adjacencies.

"Full graph" will be used to denote a full I graph where
the R field can be either full R or partial R.

"Partial graph“ will be used to denote a partial I graph

where the R field can be either full R or partial R.

In Figure II.4. are examples of different classes of gyrobondgraphs. In

Figure 11.5. is the classification of gyrobondgraphs.

11.2.1 The Point Graph

The point graph is a simplified representation of a gyrobond-

graph. The reasons for the simplification are:

(l)

(2)

The gyrobondgraph becomes an abstract conventional form
namely the linear graph. The properties of this linear

graph can then be studied and related to the eigenvalues
of the associated system.

Compactness is achieved, especially when plotting large

scale systems on CRT. This plotting could be achieved

in a hierarchical fashion (LA6).

Before proceeding with the simplification we classify the l-junctions

according to their adjacencies as follows:

(1)

(2)

A full point: is a l-junction that has an adjacent I
element. It may or may not have an R element. The graph—
ical symbol of a full point is a darkened circle (a point)
as in Figure II.6.a.

A partial R point: is a l-junction that has only an R

element adjacent. The parameter of the R is non-zero.

Figure II.6.

26

NJ?)
_.

 

 

 

(LR) (LR) (I) (1)
its 440 O; ‘0
(a) (b)
(LR) (R) (Li?) (R)
0 4 e—o-——o
(d) (e)
Figure 11.7.

Figure II.4.

_1_-.R

(R)

III
A

(b)

(d)

Simplification of the gyrobondgraph to a point graph.

 

(e)

The point graphs corresponding to the gyrobondgraphs in

27

The graphical symbol of a partial point is a small
circle as in Figure II.6.b.

(3) A partial point: is a l—junction that has neither I
or R elements adjacent. Its graphical symbol is a small

square as in Figure II.6.c.

Simplification of the gyrobondgraph

To simplify a gyrobondgraph to a point graph the following
two step procedure is used.

(1) Replace each l-junction by the corresponding point as

stated above.
(2) Replace each gyrator together with its bonds by a
‘directed line joining the two adjacent points.

The linear oriented graph obtained will be called the point graph. The
gyrator modulus (if different than one) can be written beside the directed
line. The value of the parameters of the inertia and the resistance can
be written beside the points. No confusion will occur here between the
directed line and a bond since the latter will be adjacent to a multi-
port element. The compactness of the point graph can be seen when com-
paring Figure II.4. and II.7. In Figure II.7. are the point graphs
corresponding to the gyrobondgraphs in Figure II.4. The point graph
could be considered as a more abstract form of bond graph. It offered
however a suitable medium for examining the eigenvalues of the associated
system. An example of a system and the associated point graph is given
in Figure II.8.

Throughout this work we will examine the point graph. The
points of the point graph will be labeled by numbers 1,2,...N, where

N is the number of total points in the point graph.

28

 

 

 

(a) (b)

/.___S.C;)K___a./...—h.éggkz_a-V(___a.<:;)/__a-J’

I I I I

I I’ I?

 

(c)
A4 #9 4"” %:i 4::2
(d)

Figure II.8. (a) A mechanical system; (b) the bond graph model;
(c) the gyrobondgraph; (d) the point graph.

29

The objective of this work will be to relate the structure of
the point graph to the eigenvalues of the associated system. We will
develop a procedure to estimate bounds on the largest eigenvalue of a

system if its gyrobondgraph is full, by using the structure of the

point graph.

II.2.2 A Class of Systems

In this section we present the class of systems studied through
this work. They are the dynamic systems whose gyrobondgraph is a simple
partial graph, with the condition that each l-junction has at least
one I or one R element adjacent.

In terms of the point graph they are systems whose point graph
has full points and partial R points only.

It could be easily proven that for such a class of systems,
all storage elements in the gyrobondgraph have integration causality.

A basic matrix in studying this class is the gyroadjacency
matrix. It is defined in relation to the point graph as follows:

For a point graph having f full points and p partial R points,
the total number of points in the point graph is: N a f + p; we associ-

ate the gyroadjacency matrix SNxN ‘ [sij] such that:

sij = rij if there is a directed line from point i to

point j with gyrator modulus equal rij; and

S13. --rij if there is a directed line from point j to

point i with gyrator modulus equal rij; and

s.. = 0 otherwise.
1]

30

The state matrix

For the class of systems defined above, we give the state
matrix in terms of the gyroadjacency matrix and diagonal matrices of
the resistances and the inertias defined below.

Let R ... be the diagonal matrix whose entry R

F Fii

is the resistance of the full point i,

R 7
1R2 <:)

 

 

 

 

0 °
Rf
L .
and let RP . . . be the diagonal matrix whose entry RPii
is the resistance of the partial R point i,
Rf+l 01
RP: OO'R
N
b d
-l . . .th .
and let I . . . be the diagonal matrix whose 1 entry is the

inverse of the inertia on the full point i,

-l

O ".1.
_ 1%

(The points are not necessarily labeled in order in the graph, but they

 

 

are ordered in the above matrices: first the full points, then the

partial points.)

31

If we write SF S12
3: T
'S 12 SP
-l T -1
then A . [(sF -RF) + 512 (sp -Rp) 512] [I 1 ...(1)

provided (S -R )-1 exists.
P P .
where SF...is the gyroadjacency matrix of the subgraph having all its
points full,
and Sp...is the gyroadjacency matrix of the subgraph having all its
points partial.

The proof for the above theorem is given in Appendix 8.
The simple full graph,

A simple full graph has a point graph with all its points

being full points. Thus

:6 (I)
II
0 <3

and the state matrix is given by

-1
A = [sF - RF] (I )

This result could also be obtained from (861).

Example
Consider the system in Figure II.3. The gyrobondgraph given

in Figure II.3.c. is simple full, hence

the gyroadjacency matrix is
0 l
-l 0

the resistance matrix is

32

(R ) = ’
F -l
0 R2

and the inertia matrix is

l/L 0

0 l/C1

Applying the expression for the state matrix of a simple full graph,

we obtain P -
A a o 1 R1 0 1/L 0 _ 421 /L l/cl
-I 0 0 R’1 o l/C -l/L «12"1
2 1 2/c

 

 

which is the same result obtained earlier.

II.3 Graph Theory

Next we introduce some basic definitions of graph theory with
some illustrating examples. A new matrix associated with the oriented
graph is introduced; we call it skew symmetric adjacency matrix*. Also
here we state some theorems from the theory of graph spectra. These

theorems were used in some of the proofs in this work.

II.3.1 Graphs

Here we introduce the mathematical definition of graphs and
the terminology related to them.

A Graph: denoted G or G(p,q) consists of the following: a
finite nonempty set V=V(G) of p points** together with a prescribed set

x of q unordered pairs of distinct points of V.

 

*The skew symmetric matrix introduced here has been introduced
as an adjacency matrix of a special class of tournaments (LA7).

**Sometimes called nodes, vertices, junctions.

33

***
A Line: each pair x=(u,v) of points of X is a line . u

and v are called adjacent; x and u are called incident to each other.

Adjacent Lines: if two lines are incident to a common point
they are called adjacent lines.

In Figure II.9. G is a graph, number of lines q-S and number
of points p24, line x is incident to point u, line y is incident to
point u; and thus lines x and y are adjacent.

Directed Line: is an ordered pair of distinct points. Line
2 is a directed line. Because the direction of the line is the power
direction in a point graph, the term power direction will be used
throughout this work.

Oriented Graph: A graph with all its lines being directed
lines. No multiple lines between same points and no directed line from
one point to itself. Figure II.10 is an Oriented graph.

A Walk: of a graph G is an alternating sequence of points and
Iines beginning with a point and ending with a point. In this alter-
nating sequence a line is incident with the point preceding it in the
sequence and with the point following it. The sequence (w,y,u,x,v,x,u)
in Figure II.9. is a walk.

A Closed walk: is a walk beginning and ending with the same
point.

A Path: is a walk with all its points and lines distinct. In
Figure II.9 (w,y,u,x,v) is a path. A graph that is a path and that con-
sists of p points will be denoted by: Pp. In Figure II.ll.a. is a

path with four points: P4.

 

***Sometimes called edge, arc, branch.

34

Figure II.9. A graph with four points.

 

Figure II.10. An oriented graph.

(a) (b)

O—O—H...

 

Figure 11.11. (a) A path with four points: P '

4. (b) a cycle with
three points: C3.

35

A Cycle: is a walk with distinct points that is closed. In
Figure II.9. (w,y,u,x,v,z,w) is a cycle. A cycle with p points will be
denoted by CP. Figure II.ll.b. is a cycle with three points.

In oriented graphs we classify cycles according to their num-
ber of points and their power orientation as follows:

Odd (even) numbered cycles are cycles having odd (even) num-
ber of points.

we define power clockwise (counter clockwise) of a cycle as
the number of directed lines in that cycle that are directed clockwise
(counter clockwise).

Odd powered cycles are cycles having their power clockwise or

 

counter clockwise equal an odd number; otherwise they are even powered.

In Figure II.12.a. the graph is a cycle. It is odd numbered,
and is 3 clockwise powered, zero counter clockwise powered and thus odd
powered.

Note: this definition implies all odd numbered cycles are
odd powered. .

In Figure II.12.b. the graph is a cycle. It is even numbered,
and is 4 clockwise powered, zero counter clockwise powered and thus
even powered.

In Figure II.12.c. the graph is a cycle. It is even numbered,
and is 3 clockwise powered, 1 counter clockwise powered and thus odd
powered. Thus even numbered cycles can be odd or even powered.

Labeling a Graph: is assigning to the N points of the graph
numbers from 1 to N. There exists more than one way to label a graph

(or an oriented graph). Figure II.13.a. is an oriented graph; in b and

c are two different labelings for the same oriented graph.

36

 

I T I

 

 

 

 

L J A 7:

(a) (b) (C)

 

 

 

Figure 11.12. (a) An odd length (numbered) cycle; (b) An even length
(numbered) cycle with even power; (c) An even length (numbered) cycle
with odd power.

 

(a)

(d), (e)

Figure II.13. (a) A directed unlabeled graph; (b) and (c) two different
labelings of G; (d) and (e) two subgraphs of G.

37

Subgraphs: a subgraph of the graph G is a graph having all
its points and lines in G. G1 and G2 in Figure II.13.d. and Figure II.13.a.
are subgraphs of G.

Removal of a Point: the subgraph obtained from a graph G by
removing a point v, and denoted (G—v), consists of all points of G ex—
cept v, and all lines of G except those adjacent to v. In Figure 14.b.
the subgraph G1 is obtained from the graph G in Figure II.14.a. after
removing the point v.

Removal of a Line: the subgraph obtained from a graph G by
removal of a line x, and denoted (G-x), is the graph having all lines
of G except x. In Figure II.14.c. the graph G2 is obtained from the

graph G by removing the line x.

Connected Graph: a graph is connected if every pair of points

 

are joined by a path.

The Degree of a Point: is the number of lines incident on

 

this point.

Minimum Degree: of a graph G: denoted d(G) is the smallest

 

degree of all points of G.

Maximum Degree: of a graph G; denoted A(G) is the largest de-

 

gree of all points of G.
End Point: is a point of degree 1.
The Complete Graph: denoted Kp’ is a graph having every pair

of its p points adjacent. Examples of oriented K3 and K4 are given in

Figure II.15.a,b.c. NOte that for oriented graphs with four points,

K4 is not unique because of possible different power orientations; for

example: Figure II.15.b. and Figure II.1S.c. are both K4.

38

(D
C)
ll
0
I

<1

 

(a) (b) (c)

Figure 11.14. (a) A graph G, with point Vand line x; (b) A graph G1
obtained from G by removing the point v; (c) A graph G2 obtained
from G_by removing the line x.

¥

 

 

 

 

 

 

 

 

(a) (b) (C)

Figure 11.15. (a) A complete graph with three points: K ;

(b) and (0) two possible power orientations on a complete graph K4.

39

. ,
<

(b)

Figure II.16. (a) A complete bigraph: K (b) A complete bigraph

2’3’
K1,3 (a star).

 

I V
G : G 2' G :- m

Figure II.17. A graph G that has two components: G1 and G2. The sub~
graph G2 has a bridge y and a cut point v.

40

The Tree: is a graph with no cycles.
Bigraph: a graph whose set of points V can be partioned into

subsets V1 and V2 such that every line of G joins V1 and V2.

Complete Bigraph: denoted by K.m n' If V1 and V2.have m and n
3

points and G contains every line joining V1 and V2. Example in Figure

II.16.a. the graph is K .
2,3

A Component: of a graph G is a maximal connected subgraph of

A Cutpoint: of a graph is a point whose removal increases the
number of components.

A Bridge: of a graph is line whose removal increases the
number of components.

In Figure II.17 is a graph G having two components G , G

l 2'

Removal of point v increases number of components, and removal of line
y will increase number of components. v is a cut point, y is a bridge.

A Star: is a complete bigraph with V having only one point.

1

K is a star with 4 points

A star with p pOints is denoted Kl,p—l° 1,3

and is shown in Figure II.16.b.
The Direct Sum: of two oriented graphs G1(ui,xi) and G2(vi,yi),
denoted by G1 + 62, is a graph G :- G1 + 62' The points of G are the

cartesian product of the points of G1 and G2;

and there exists a dir-
ected line in G from the point wi = (ui,vi) to the point wj = (uj,vj)
whenever the following is true: ui a uj and there is a directed line
in G2 from vi to vj; or vi = vj and there is a directed line in G1 from
ui to uj.

In Figure II.18.b., the point a and the point b have the same

first coordinate: (l); and in G2 there is a directed line from point 3

41

a =(1.3) b ?(1.4)

e e )0——-*7

._L_.|—a

 

 

 

. . I. A

’C =(293) d =(294)

 

hmt~fi

b
O
Q.

(a) (b) (e) (d)

Figure II.18. The direct sum of two labeled orineted graphs. (a) and
(b) are two labeled oriented graphs; (c) the cartesian product of their
points; (d) the direct sum graph.

 

 

 

 

 

 

5

1 4 '01011'
A(G) 8 1 0 1 0 0
O l 0 1 O
G: 1 0 L 0 1
_10010J

2 dLv (0‘3

(a) (b)

Figure II.19. (a) a (unoriented) graph G; (b) the adjacency matrix of
the graph G.

42

to point 4. They are the second coordinates in point a and point b.

So we join point a and b by a directed line as shown in Figure II.18.d.
On the other hand, point a and point d do not have any coordinates that
are identical so no line joins a and d in Figure II.18.d. Point b and
point d have the second coordiantes identical and there is a directed
line in G1 joining point 2 to point 1, so we insert a directed line from

d and b as in Figure II.18.d.

II.3.2. Matrices Associated with Graphs

A graph can be completely determined by its adjacencies and
incidence. This information can be stated in matrix form. Here we
introduce two of those matrices, namely the adjacency and incidence
matrices. They have been studied in detail in graph theory and spectral
graph theory. we also introduce a new matrix, the skew symmetric ad-
jacency matrix. It is associated with oriented graph, and is basic

to the results proven in this work.

The adjacencypmatrix of an unoriented graph

Let G be an unoriented graph with p points. Then the adjacency

matrix A(G) = [aij] is a pxp matrix with its entries aij as follows:
aij = 1 if point i is adjacent to point i,
a.. = 0 otherwise.
13

In Figure II.19.a. is a labeled unoriented graph and in Figure
II.19.b. is its adjacency matrix. Note that the adjacency matrix of an

unoriented graph is symmetric.

43

The adjacenpy_matrix of an oriented graph

Let G be an oriented graph with p points, then the adjacency

matrix A(G) = [a..] is a pxp matrix with its entries aij as follows:

1]
aij = I if there is a directed line form point i to
point j
a.. = 0 otherwise.
13

Note that this matrix can be symmetric only in case of two
directed lines between two points. This matrix is mentioned here for
the purpose of not confusing it with the skew symmetric adjacency matrix

defined below.

Incidence matrix

Associated with a graph G(p,q) a matrix B pxq with entries

b.. = 1 if v. and x. are incident, b.. a 0 otherwise.
13 l J l]

The skew symmetric adjacency matrix

The skew symmetric adjacency matrix is the gyroadjacency ma—
trix, defined in section II.2., if all gyrators have unit modulus.

For an oriented graph G(p,q) define a pxp matrix‘A = [Eij] such that;

no

aij = +1 if there is a directed line from j to i,
Eij a -1 if there is a directed line from i to j, and
a.. = 0 otherwise.

1]

In Figure II.20.a. is an oriented graph G. The skew symmetric adjacency

matrix associated with G is:

”A(G) =

F‘P‘H‘O
c>
c>
I
H

44

 

 

 

 

(a) (b)

Figure II.20 (a) an oriented graph with 4 points

(b) the unoriented graph obtained from G by relaxing
the orientation.

45

If we relax the orientation on G, the obtained unoriented graph G shown

in Figure II.20.b. has an adjacency matrix A = [aij]:

A(G) -

F‘F‘F'O
PJC>OIH
F‘C>O)4
OIdIdIA

Note that aij is the absolute value of the entries of the skew sym-

metric adjacency matrix A = [aij]:

31: ‘ '31;
We conclude that the operaiton of relaxing the orientation on the oriented
graph, will result in an equivalent operation on the adjacency matrices.
This operation will produce a symetric adjacency matrix. The above

definition could be also extended to a weighted oriented graph.

II.3.3 Spectrum of a Graph

Throughout this work we will be dealing with connected graphs,
no multiple lines between two points, and no loops (a line between a
point and itself). Thus we will be dealing with two different types
of adjacency matrices. The skew symmetric adjacency matrix will be
associated with oriented graphs and the symmetric adjacency matrix with
unoriented graphs.

We mean by spectrum of a graph the roots of the characteristic
polynomials of the adjacency matrix, A, given by det(A-A.U)=O. 'A' here
denotes the symmetric adjacency matrix if we are dealing with graphs
that are not oriented, and the skew symmetric adjacency matrix as de-
fined in II.3.2. if we are talking about oriented graphs.

Labeling: the spectrum of a grpah is invariant under different

labeling. This is true for symmetric spectra and skew symmetric spectra

46

as well. If A is the symmetric or the skew symmetric adjacency matrix,
and A* is the new adjacency matrix obtained by the relabeling operation,
then A* = P-1 AP, where P are orthogonal permutation matrices.
Invertinngowers: on one point of an oriented graph. The
skew symmetric spectrum of an oriented graph obtained from its skew
symmetric adjacency matrix is invariant under the operation of switching
all powers on one point. This operation is shown in Figure 11.21. This
operation is equivalent to the similarity transformation of multiplying
the matrix A by the matrix E and E".1 where E is an identity matrix ex-

cept for some entry eii of E; and eii a -l,

A =- E-lAE.

Next we introduce some theorems from theory of graph spectra.
These theorems are applicable to the symetric adjacency matrix. An
asterisk will denote that the theorem applies also to the spectra of
skew symmetric adjacency matrices.
Theorem 1 (GT2)
(a) If G is disconnected; then the spectrum of the graph G is
equal to the union of the spectra of the components of
G. (*)
(b) The sum of the eigenvalues of a graph is equal to zero.
(*)
(c) If G has N points; and if C is the number of closed walks
of length k in G; then

C = tr Ak =.§ AK
i=1 3

Theorem 2 (GT5)
Let G be a graph with N points, and letAi be an eigenvalue

of G such that:

then:

 

I
(a) 2 cos N+l .5

(b) If G' is a subgraph of G, and A; are the eigenvalues of
the subgraph; then

Ill! 5 All

For the skew symmetric spectra, the bounds in theorem 2 (a) apply;
however for this case, closer bounds exist. We hive these bounds in
Chapter III.

Theorem 2 (b) applies in case of the skew symmetric spectra
only in case G' is obtained from G by deleting at least one point. The
case of a subgraph obtained by deleting a line does not apply here since
the Frobenius theorem used for the proof of theorem 2 is applicable only

for non-negative matrices.

II.4 Linear Algebra and Matrix Theory

In the following section we present some concepts and notations
from Linear Algebra and Matrix theory. We also give some theorems
relevant to graph spectra.

Eigenvalues: if A is an NxN matrix, a vector 2 = xech is
an eigenvector of A if there exists a scalar A such that:

Ax = Ax.
Ais an eigenvalue of A.

The set of all eigenvalues of A are called the spectra of A.

The polynomial

det (A - AU) = 0, where

48

U is the identity matrix, is the characteristic polynomial. The roots
of the characteristic polynomial are the eigenvalues of the matrix A.
We arrange the eigenvalues as follows:
IANI E .... §_IA1| , and
we arrange their real and imaginary parts as follows: If A: a + ib,
and istIT then:

< .... 5 lb

‘3 °°°°.E Ia

Note that A1 is not necessary equal to a1+ibl.

The following theorems from matrix theory are useful in study-
ing the spectra of graphs:

1. For symmetric or hermitian matrices all eigenvalues are
real.

2. For skew symmetric matrices all eigenvalues are pure
imaginary.

3. The sum of the diagonal elements of a matrix, called the
trace, is equal to the sum of the eigenvalues of that
matrix.

4. If A is a skew symmetric then iA is Hermiltian, is -1.

Norms

A norm of a matrix is a real valued function defined on the
space of matrices and satisfying the following relations:

For an arbitrary matrix A and B, and an arbitrary scalar c,

a) N(A).Z 0; and N(A) = 0 if and only if A=0,

b) N(cA) = |c| N(A)

We define

Where the

49

c) N(A+B) 5_N(A) + N(B)
d) N(AB) ‘3 N(A).N(B)

the following norms:

*
x Ax 15 called spectral norm;

 

N2(A) - max [ *
x#0 x x

2 5
NB(A) a I Elaijl 1

called Euclidean norm.

superscript * denotes the transpose of the matrix.

For any square matrix of dimension n:

l. NE(A) a NE(|AI), where the entries of. A are the moduli
of the entries of A.

2. N2(|AI) 5N2(A)

H
3. N2(A) _<_NE(A) _<_n N2(A)

%

4. N2(A)§n N2(IAI)

Theorems for locating eigenvalues:

The following are theorems frequently used to local the

eigenvalues of matrices:

l. Gerschgorin Theorem: for a matrix A a [a..] the
nxn ij
eigenvalues lay in the union of discs with center at

aij and radius ri given by:

n
r. a 2 ai.
j=1 3
3A
2. Interlacing Theorem: for relating the eigenvalues of
a matrix to the eigenvalues of its principal submatrices:
Let Anxn be a hermitian matrix with eigenvalues Ai

such that

IA | 5 _<_ IA then

n lI ’

50

A . < u. < A.
n-m+i - i - i

where "i are the eigenvalues of the mxm principal sub-
matrix of A. We say that the eigenvalues of the prin-
cipal submatrices of a matrix interlace with its
eigenvalues.

Average row sum theorem: (Haemers) (GT3)

Let A be partitioned as follows:

 

 

All ... Alm
A = I :
Aml ... Ammj

and Aii is a square matrix for i a l, ... , m;

let B = [b..] where b.. = the average row sum of
mxm ij ij

Aij; then the eigenvalues of B interlace with the

eigenvalues of A in the sense defined in theorem 2.

Interlacing theorem for the sum of two hermitian

matrices: if A, B and C are hermitian matrices with

eigenvalues Ai, ”i and vi respectively, and if:

C = A + B
then

v < A +
r+s-l - r u

The above theorems will be used in proving some of
the results given in this work.

Properties of skew symmetric matrices: there are
important properties to know since the gyroadjacency

matrix S is skew symmetric.

51

1) If S is NxN and N is odd, then there exists at
least one zero eigenvalue.
2) If we denote by Spec (S), or spectrum of S, the
the set of all the eigenvalues of S:
Spec S = [+ 1 Al, + i A2, ..., -iA2, -i All
then is, i a J:I, is a hermitian matrix and
Spec (i5) = [+Al, + Aé,...,-A2,-Al]
This is an important fact since all theorems appli-
cable to the spectrum of hermitian matrices will be
applicable to the imaginary part of the spectrum of
the skew symmetric matrices.
This will allow us to speak about the interlacing in
the eigenvalues of skew symmetric matrices, meaning

the interlacing in the imaginary parts of the eigen-

values.

CHAPTER III

BOUNDS FOR SIMPLE FULL GRAPHS

I I I . 0 Introduction

Simple full graphs as defined in section II.2. are gyrobond-
graphs (BGl) that have every I and every R element a one port, and the
number of I field ports is equal to the number of l-junctions.

The point graph of a simple full graph has full points only.
(cf. II.2.l.).

A large class of systems can be represented by simple full
graphs.- Examples of these systans are given throughout this chapter.
The bounds given here are used in some other classes of systems where
simple full graphs are subgraphs of the point graph.(cf. Chapter V).
Also for large scale systems an estimate of the largest eigenvalue ob-
tained from the point graph will save a large computational effort.
In ‘Lthe following chapter‘lwe provide these bounds as a function of the
number of l-junctions in the simple full graph, or the number of points
N in the point graph, and the structure of the graph.

We present bounds on the largest eigenvalue of systems. The
information required to obtain these bounds is:

1) Number of points of the point graph of the system N.
2) The type of parameters the system has:
a. Uniform parameters (defined below). (Sec. III.1.)

b. General parameters. (Sec. III.2.)

52

S3

3) The structure of the point graph:
a. a tree
b. a general graph
In III.1. we give the results for systems with uniform para-
meters. In section III.l.l. are three examples of physical systems
that have their point graph a tree, a cycle, and a general graph. In
section III.1.2. we give the bounds for systems whose point graph is a
tree, then for systems whose point graph is a general graph. In sec-
tion III.1.3. we present important properties of cycles. Section
III.1.4. the case of simple full graph with partial R field is dis-
cussed and an example demonstrating application of the results is given.
In III.2. bounds for systems with general parameters are given. In
section III.2.l. two examples of physical systems that have general
parameters are presented along with the bounds obtained on their largest
eigenvalues. In section III.2.2. the procedure for obtaining the bounds
for systems with general parameters is given. Next we present defini—
tions relevant to this chapter.
For a system represented by a simple full graph, the £5323
matrix is given by:
A = (SF - RF) (1'1)
where (cf. II.2.2)
S ...is the gyroadjacency matrix,

F

RF...is the diagonal matrix of resistances, and

I ...is the diagonal matrix of the inverse of inertias.

S4

A similarity_transformation

Two systems are similar if they have the same spectrum. For
a given system with general parameters, a similarity transformation
using the point graph and a simple procedure will produce a similar
system. The new system will have the same point graph as the original
system with all the parameters of its inertias equal 1.

Tranformation procedure:

1) On each line replace each gyrator modulus rij by:

'k

r.. a r..
ij ij
41. I.
1 3
where Ii’ Ij are the inertias on points i and j adjacent
to r. ..
13

2) On each point replace each resistance Ri by:

at
R.=
1.

H :0
P. P.

where Ii is the adjacent inertia.
In Figure III.1. is an example of the reduction procedure.

'A'
The proof could be easily found from the fact that the matrices A and

** u u u
A are Similar if:

'A' **
A=ADandA =DL’AD5

and D is diagonal.

Systems with uniform parameters

Systems with uniform parameters will have:

i' i
R. =c1and r .. = B
i ij

55

 

 

 

 

(a) (b)
_* p Ri
R' =-—— for i - 1, 2, 3, 4
i I
i
* In.
rij a for i,j as above.
“I I

Figure III.1. (a) and (b) two point graphs for two identical systems
except for the parameters of their energy storage elements.

56

where g,_Bare constants and R: and r:j are defined as above. A possible
case of uniform parameters will occur when 6-8 =- l, in this case we
say the system has ppig parameters. Systems with uniform parameters
are easily detected from their transformed point graph. This can be

seen in Figure III.12.
Ordering the eigenvalues
If a system has an NxN state matrix A, and if
Aj = ak + ib2 , i s J-l
is an eigenvalue of the matrix A, we arrange the eigenvalues as follows:
< O O O <
IANL _lxll , and
we arrange the real and imaginary parts of the eigenvalues as follows:
5'... .‘3 la
5 . . . < lb

Upper bounds on the largest eigenvalue, denoted by Au, is any number
such that:

IAII _<_ In

In the same sense the subscript u on either a or b, will denote a
number that is an upper bound on either the real or the imaginary part

of the eigenvalue:
:Ial
_<.Ib|

Note that the upper bound on the largest eigenvalue is an upper bound
on all the eigenvalues. A lower bound on the largest eigenvalue will

not necessarily be a bound on any other eigenvalue.

S7
Gerschgorin theorem

Applying the Gerschgorin theorm to the skew symmetric adjacency

matrix or the gyroadjacency matrix of the transformed point graph gives:
*

b < A or b < max 2 r .
l- - . . ij

1 J

l

where A is the largest degree of the point graph associated with the
system. This bound becomes efficient to use in case the number of points
in the point graph is much larger than A. This is demonstrated in the

example given in III.l.l for a system with a general point graph.

III.1 Uniform Parameters

The bounds on the largest eigenvalue of systems with uniform
parameters are studied for two major reasons:
1) Some physical systems are modeled as systems that have
unit parameters. See, for example, lumped models of
single power line continuous systems (cf. example 1
section III.l.l).
2) The bounds obtained for systems with unit parameters
are used as a base to obtain bounds for the more
general case of systems with general parameters.
Systems with uniform parameters could be recognized from the transfor-
med point graph. This can be easily done by scanning the parameters on
the r:j and R: on the point graph. Examples of these systems are given
next in III.l.l. In section III.1.2. we give bounds first for tree
point graphs, then for the general point graph. In III.1.3. properties
of cycles are discussed; and in III.l.4. partial R field graph is

discussed.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

58

 

I-sO-fi‘
. I /I I II I
- I [R 1 [R I
I: /I /
1’ F? If?
(a) (b)
(c)

Using the bond graph

Usinngerschgorin

Using iterative methods _

 

 

1.87 1 b1: 2.64

 

b1_<_4

 

bl = 2.14

 

Figure 111.2. (a) A hydraulic system; (b).the bond graph model;

(c) the point graph.

 

59
III.l.l Examples of the Bounds

A tree'

In this example we present a hydraulic system whose point
graph is a tree. We give the bounds on the largest eigenvalue and
compare it with the values obtained using iterative algorithms and al-
so compare it with bounds obtained using the Gerschgorin Theorem.

In Figure III.2.a. we have a hydraulic system as shown. It
consists of six pipes connected to two gravity tanks. In III.2.b. is
the bond graph model and in III.2.c. is the point graph model. Here
the number of points N=:8. If we assume all parameters equal unity:

C = I a R = 1, then from results presented in this chapter the follow-

ing bounds are given:

1.87 < b ‘5 2.64
A bound computed using Gerschgorin Theorem would give an upper bound.
bl-S 4
The iterative methods provide accurate values; using the EISPACK routines
we get for bl’
b = 2.14

A cycle

Consider the system of Figure III.3.a. Here we have four
masses of mass M and four massless springs of spring constant K. In
Figure III.3.b. is the bond graph and in Figure III.3.c. is the point
graph. Here the number of points is N = 8. This is a case of uniform

parameters. From results presented in this chapter and for this case we

60

 

 

 

 

 

 

 

 

 

 

K M K M I C I

M L I I
I—i I_.0_.,

W m 1
04—0 0—~C

M K ._M__ K ' '
L__- NVNJ\‘ J\”VI I'sF-(D~r-I
W“ W W I I I
I C I

(a) (b)

(C)

Figure III.3. (a) A mechanical vibrating system; (b) the bond graph
model; (c) the point graph, with spectra given by:

. K . 2K . 2K
Spec(G) = [ii 2%;, i 1%;:, i 1 £;:, 0,0]

61

know all the eigenvalues exactly. They are:

Spec (G) = (:12 [5' x i I315, : i (315,0,0)
M M M

The above results coincide with the results given by J.N. Boyd (8G8),
except here we used massless springs. The example was set as masses
arranged around a circle with all motion confined to the circle. It demr
onstrated the use of projection operators in obtaining natural fre-

quencies of a one-dimensional crystal.

A general graph

 

Consider the lumped-parameter bond graph model of a two power
distributed system. The bond graph model of the Timoshenko model for
transverse vibration of a prismatic bar with shear corrections is
adapted from Bonderson (BG9) and given for 3 microelements in Figure III.
4.a. In Figure III.4.b. is the point graph; it has N = 12 points.
Assume that all parameters are equal to 1. Then from.resu1ts presented

in the next two sections,tflmafollowing bounds could be estimated for b

1:
1.941 .E bl‘: 7.59
Using Gerschgorin Theorem gives a better upper bound on bl.
<
bl-— 3

The computed value using interative techniques gives:

= . 7
b1 2 3 0

We note that the difference between the upper bound and the real value
is too large. In this case the use of Gerschgorin Theorem would give
closer bounds. (In Chapter IV we present techniques that would reduce

the upper bound to b .5 2.802.)

1

62

(a)

(b)

 

Estimates
(Using the point ggaph

Using Gerschgorin

Computed value
Using iterative methods

 

1.941 ib1 _<_ 7.59

 

 

b1s_3

 

h1 = 2.370

 

Figure III.4.
distributed system:
corrections.
used three elements.

a) A bond graph of a lumped parameter model of a two power
transverse vibration in a prismatic beam with shear
The model is adapted from L.S. Bonderson (BG9).
b) Is the point graph model.

 

Here we

63

III.l.2 Bounds on Largest Eigenvalue

In this section we give the bounds on the largest eigenvalue
of systems with uniform parameters. A plot that depicts the bounds
for trees is given in Figure 111.5. A plot of the bounds for general

graphs is in Figure III.6. In Figure III.7. is a plot showing the

lower bounds on arbitrary graphs.
Trees

Let G be a point graph associated with a system with uniform
parameters. Let G be such that:
(a) G has no cycles
(b) G has N points; and all the points are full.
Let A: a + ib, be an eigenvalue of the system,

(a) If G is a star, then

Spec (G) = [i i84N- , 0, . . . 0] and

b = BxIN-lE b
u uS

(b) If G is a path, then

Spec (G) = [i i 28 cos 1 ,...,i 28 cos 51 1, k=l,...,N
N+l N+l

and b = 26 cos n E b
u -— uP-

(c) For any G that is a tree with N points

28 cos x = b < b < b =BJN-l
NII uP- 1" us

(d) The spectrum of the symmetric adjacency matrix of the
oriented graph obtained by relaxing the orientation on G,
and the spectrum of the skew symmetric adjacency matrix

are identical. (Apart from i = 4—1.)

64

semen mnmno> in

.z spewed mo Hones:

"woman meow mo osam>so0eo ecu mo when >uocwomsa ummmhoa 0:8

 

 

 

 

09 03 03 09 cm 00
. _ _ 1I _ q a I4
I I .. .. s. I I I....I..\.
I\ \...\
2.. x \
.\\ \
\\ \
\. . \
.\\xflmwmw\\ .\\ \\
mmm///JV\\..\\\\.\\\\\\\\
...\.x\ \ \ \
\\>I\x\ \
.. \
72‘! w\ \

 

.m.HHH assess

65

~ I g
.20 zm .P 2 PM .zz "mcnmhm ocson how 2
mucHOQ mo hoses: momHm> o

 

 

 

 

 

2
8 Om 0% 0m. ON 9 Mt
I IIIIIIIIIIIIIIIIII “a IIIIIIII-..IIIIIIIIIIHII....I.....hmM.
I.2 . IIIIII \
Monica ImOQN.I.~<Q. ....... I - II ..
-IInm ........... WI .\
(x \\ I
\ .\
\I2>»m>§.m \.
\\\ IL
. \
\
\
2N . 2 ..
Mk8 . wkmqlS‘OO .w\ I
\\\
.\
.\ L
.\
\

"osam>cmmam ecu mo when >hmcemmEH unwound on» :0 mocsom .o.HHH choose

9

ON

Om.

 

Fm

66

 

 

 

bI secosiflL-
2 2N
— s o s o ,
""‘——-V-. —
V/ ’ ‘1 ...
/"’ .2kxf§>"* ‘1¥?COSE%5-
/+// / \\
L73 r — - - - V/ j ,0/ ‘ 2 COS _ZL
//' /// \u___ AI

' /
I I

PATHS

EVEN ORIENTED CYCLES

000 L ENCTH CYCLES

I l l l I l I L

2 4 6 8 IO N;

 

-I-
CI
O 000 ORIENTED CYCLES
V
I

 

* Figure III.7. The largest imaginary part (b) of the eigenvalues
of paths and cycles versus the number of points N.

67

 

 

 

 

 

 

 

 

 

 

(b)

a)

(

R
I/I

R

I

 

/

I

I

61)”
I‘— GY‘-l-‘- GY—‘I

\

R

I
Y
/--rI

/I

R

(d)

(c

nted

system composed of a water tank and four
-2i, 0,0).

; b) the bond graph model; c) the gyrobondgrahp; d) the orie

L
9.
c t
i C
l e
u D.
a s
m. a
h m
A s
t
I, n
a .m
a 5
I .n
I t
I .i
w

e
web
so.
Qba
.iur
F t a.

68

 

 

Emoom n on "$902 I ZN
2 V m;
a... APIZVNQOON ..ooqafilzvNMOON «MWHMNWMOON

uls+x~c pm a L
l m. N a

.0

.mco Amoco
Z

:
msasooe cps3 woos Amlzv ocm .uoon Chow mco ocm . +9)" o "0902

P+Q_HI.HI.HI....~O~...qflafiar+Q5HH

omUOOH OHON
um»

a- .23: 62...; m: E. . .253- 1755175..» I an "802

IN.» IN»

 

 

 

 

 

. . .05. «zuzwl «A PIzIerI 72v... \LH «2;sz «A PIszwlA 75+» AH

 

 

 

m+m2+izu2

 

 

Eoum>m mcwoconmohhoo mo enhuoonm

wh3u0:HUm one was» NO mEmz

 

.momhu 050m m0 whuomam one H.HHH magma

69

K : K °
40P7' 4

 

 

 

 

 

 

(a) (b)

Figure III.9. (a) Is an optimal graph for the graph in (b).

(a) (b) (C)

Figure 111.10. In (a), (b) and (o) Are three oriented graphs with four

points and five lines. The orientation is different on the lines.

The spectra of the first two are identical, the spectrum of the third
is different.

70

(e) Spec (G) is invariant under power orientation.

(f) The realpparts of the system's eigenvalues: a = -a
An example of a system that has a star point graph is
given in Figure III.8. The constant a,8~ are as defined

in uniform parameter systems.

Some special cases of trees

 

In Table III.1. are the spectra of some trees. These spectra
could be found easily by applying the recursive formula in Chapter IV.
The result (d) will allow us to use the results of the well developed
spectral graph theory to obtain insight into the spectra of systems
whose point graph is simple full and has no cycles. Symmetric spectra

of all trees with N §_10 are given in Cvetkovic (CT2).

Generalggraph

Here we present bounds on systems whose gyrobondgraph is a
simple full graph. The condition of no cycle is relaxed. The bounds

are given for a point graph that may have cycles.

 

Define the optimal graph (Gopt) of a point graph G with N

points and q lines as a graph with N points and q1 lines such that

q_<_q1

and the power orientation on the lines of Go is such that if b1(G)

pt

is the largest eigenvalue in Spec (G), then

b1 (c) _<_b1 (Gopt)

The optimal graph (K

Nopt) of a complete p01nt graph WIth N pOints (KN)

is given in Figure III.9.a. for N = 4.

.mmsam>comwo ones 03» o>oc sunbeam on» .usflon co>m noBOQco>o some;
.ouou m o>ms uoc mwoo muuomam on» .mucaod cm>o uo3oa ooo some

 

 

 

71

 

 

 

 

 

 

s s a
N u... D $0 Q H I“ NOON II: Q
2 mooN «a IIIIIMWIII mOON UGO N\z
mxm nap + MNV
o: z s N I an
o n “.N moom u n z co>o
moo moo cm>m
u:+x~c N .2. 38 N ~\2 2
waINI mOON H in
u
ZN
IIIIIIIII moo o 2
ex. + xmv m oo
mucwoa
mo Hones:
..II. Q " n u z
hmzom ooo pom Mozom co>m Mom hm3om

 

 

 

PIz .. . . .p .o u x .mmaoxo mo whooonm ecu mo >umEE3m .N.HHH canoe

72

For a system with uniform parameters, if the associated point
graph G has N points all of them are full points. If A= a + ib is an
eigenvalue of the system, then

If G is KN then

Spec (KNopt) = [18 cotzfi , 18 cot %% , . . . , 18 cot (2k;;)r]

k = 0,1,...) N-l

and bu =Bcot_§_= b

2N uKopt

If G is a cycle, the spectrum is given in Table III.2.2.

 

If G is a general graph and if N is odd, then

 

28 cos x = b
N+l

uP 5-bl 5-buKopt = B cot _1 , and

If N/2 is even

 

28 cos I = b 0 < b
- uC

<
'_ l-— buKopt 8 cot _1 , and

 

N 2N
If N/2 is odd, then
.1 e < < = .
28 cos §_ buC __bl __buKopt 8 cot 3%

The proof of the upper bound could be derived easily by finding the

graph associated with the matrix H given in Pick's Theorem (see Bodewig
(NA2) ). The matrix H has the largest eigenvalue over all skew symmetric
matrices of the same order.

The proof for lower bounds is given in appendix 7.

Power Orientation (on lines of general graphs)

If the power orientation on a line that is not part of any
cycle or that is part of odd numbered cycles only, is changed, the spec-

trum of the point graph does not change. This power orientation rule is a

73

corollary of results in Chapter IV concerning the characteristic poly-
nomial of the point graph. For more information about the effect of
power orientation see Chapter IV. An example of the power orientation
rule is given in Figure III.10.a. and Figure III.10.b. we see two point
graphs with the same spectrum since the power orientation is changed on
the line x that belongs only to odd numbered cycles. The point graphs in
Figure 10.c. will have different spectra since the power orientation is

changed on line y that belongs to even numbered cycles.

III.1.3. Properties of Cycles

 

The spectrum of a cycle with large number of points can be
equivalent to the union of spectra of graphs of smaller numbers of points.
This can be used to substantially decrease the number of computations,
when computing the eigenvalues of a cycle that has a large number of

points.

Equivalence of cycles

 

Let CNe denote a cycle with N points and even power, and

0
let CN denote a cycle with N points and odd power, and

let ZN, PN denote the tree in Table III.1, and the paths with

N points, then
(a) For N = odd number

Spec (CN) = Spec (ZN+l) - (0)

(b) For N/2 = odd number (N = 6,10,...)

Spec (C = Spec (CN 2) U Spec (CN 2)), and

/ /

Spec (C ) = Spec (P ) U Spec (P ) U (2, -2)

2020

(N-2)/2 (N—2)/2

74

(c) For N/2 = even number (N = 8,12,...)

e o o
Spec (CN) = Spec (CN/Z) U Spec (CN/Z)’ and

o
Spec (CN) = Spec (Z(N+2)/2) U Spec (Z(N+2)/2) - (0,0)

The above properties are due to the fact that for a cycle, the charac-
teristic polynomial has a cosine function as follows:
If N is odd, then
det (SF - AU) = cos N9 = 0, and
If N is even and the cycle has even power, then
det (SF — AU) = cos N6 - iN = 0, and
If N is even and the cycle has odd power, then
det (SF - AU) = cos N6 + iN = 0.
The determinants described above could be obtained from the recursive
formula given in Chapter IV. The solution of the characteristic equa-
tions given above, gives the prOperties that are given in Table III.2.
The equivalence properties could be deduced from Table III.2. From the
equivalence identities we can conclude that a cycle, on which power
change will produce a change in the associated spectrum is reducible
to a graph whose spectrum is invariant under power change.
The possible reduction in the number of computations is given
in the following examples.

e

48 From the equi-

Suppose we need to find the spectrum of C

valence identities we have

e e O
Spec (C48) Spec (C24) U Spec (C24)

e 0
Spec (C12) U Spec (C12) U 2 * Spec (Z13) - (0,0)

Spec (CE) U Spec (C2) U 2 * Spec (Z7) U 2 *

75

= 2 * Spec (C3) U 2 * Spec P U 2 * Spec (Z7)

2
U 2 * Spec (Z13) - (0,0,0,0) + (2,2)
where for shorthand we used

2 * Spec (.) for:Spec (.) U Spec (.)

In this case the reduction of computation is obvious. Instead of com-
puting the spectrum of a graph with 48 points, all we need is to find
the spectrum of a tree with at most 13 points. The spectrum of ZN is
given in Table III.1.

In Table III.3. are more examples for the spectra of cycles
and the equivalent graphs.

A question that is not yet answered is: could the above
equivalence be generalized to some more general graphs?

The zeros in the spectrum of a cycle: a double zero in the
spectrum of a mechanical transational system, denotes the existence of
a rigid body mode of motion in the system. The only cycles that have a
double zero in their spectra are cycles with even number of points and
even power. This fact can be deduced from the general term for the
eigenvalues of the cycles given in Table III.II. Examples of systems
whose point graphs are cycles with even number of points and even powers
are given in Figure I.2.b. in Chapter I, and in Figure III.3. Notice
that in these systems a rigid body motion mode is possible. Cycles
with even number of points and odd power do not have zeros in their
spectra. An example of a system whose point graph is a cycle with even

number of points and odd power is given in Figure III.11. we note that

this system does not have a possible rigid body motion.

76

 

Ao.o.m©h.ol.¢m.Pl.m©h.o.¢m.9v

AvaoQO

 

 

Ammh.01.¢m.Pl.m©h.o.vm.F.mwh.cl.vm.wl.m®h.o.¢m.Pv H AMUVUQO
a I. m Q m a I 0
Ac so A Nvoo m + A Nvo m I Aouvomom
N “H"
«0.0VI VIIIV*N
thp.Pl.Nom.pl .o.o.o.o.®br.e.mom.Pv n AwNv omam
Ache.FI.Nom.PI.o.o.©hF.F.Nom.wv u AmUv oQO
Amer.PI.Nom.pl.o.o.®hp.quom.elawhp.—I.Nom.PI.o.o.th.P.Nom.Fv u Aowovomam

L o I Aoucomami + Amocomam I lowucomam

«6.. C+

 

.mmao>o mo whuooaw on» no mocmam>eooo mo manemxm

 

.m.HHH THEME

77

 

Uvomam

Avp¢.PI.¢—¢.P.qu.—I.vp¢.pv A

Ao.o.~n.mv u A ovomam

(DQCDQ'OV

Ao.o.o.o.<_v._n.v—v.F.v_v.9-.q.¢...~:.mv u A ovomam

Awuvomqm + Awovomam u Amovomam

I+I H... Q

 

 

Amwo.os.mpo.Pl.mem.o.mrm.Fv n Avmvomam

 

Amvo.ou.m_o...mpm.o.mpo...mpo.ou.m_o.Fa.um.o.um...Nu.mv « Aowuvomam
A~.~nv + Aqmv 00am * m u Aowuvomam
. .u Xi‘— .v “0 Ann
mw mw. 1+. wk mw

 

Aomzcfiucoov .m.HHH magma

 

78

\&H

L

O—A'O
...».

 

  

O
C)
7‘1'*—\

\ \ \ \\\‘\ \‘T'\

 

 

\\~ \\\\\\\\\\\ \\\\\

(a)

\v

(b)

(c) (d)

Figure III.11. a)

A mechanical transational system consisting of two
masses, two springs, a lever with transformation ratio equal 1.
b)

The bond graph model; c) the gyrobondgraph reduction; d) the cor-
responding oriented graph with four points and spectrum:

Spec(G)=[i J5, i 5, -i J3, -1 J5]

79

III.l.4 Partial R Field

 

If a system has uniform parameters, as defined in III.l., and
if the associated point graph has N full I points and m full R points
then:

A m
-a < a < -a- N
-av-g§ a < 0
<
bl(A) _ 101(5)

where a,B are as defined in the introduction of Chapter III and bl(A)
denotes the imaginary part of the largest eigenvalue of the state matrix
of the system A, and bl(S) is the largest eigenvalue of the skew symmetric
adjacency matrix S of the point graph.

The above result is proved using a theorem given by Amir-Moéz
(NA12) and by finding the symmetric and the skew symmetric components of
the state matrix.

An example of this class of systems is the beam in Figure III.
12.a. Consider the single power lumped-parameter model of the beam in
Figure III.12.b. Note that here we have two resistances on the second
and the fifth masses. The bond graph model is given in Figure III.12.d.
In the point graph we have: N = 10, and m = 2.

In Figure III.12..e. we have the reduced point graph after reduc-
ing the inertias to unit parameters. We find a,B :

0,:

2|”

KIN

The point graph here is a path and its spectrum is given by:

Spec (G) = i 2 cos 51, k=l,...,N
ll

80

(a) (b)

 

 

 

 

 

 

 

Q:

a;
r:
in:

(c)

KMKMngf'MKM
CICICICICI
rtrrrtrIr-t
()4L..LJ_.C)45.Jag..()4h_.[‘__.C).5.JQ5-.C)45.I
Ir L
R R

(d)

.4 -I
(K310) , (”20) [(60) , 01,0) , (K10) I (PM), (6’0) / (no) / 090) ’04,?)
OIE-—-dOIE-—-OIh--Oih--O1-———dO‘--—-.lh-—-—CHL———-Oflh————O

(e)

Em
‘sz

J25

' fi—O—O——O——-O————O———O-——-O-—O——O
0:0) (/;0/ (b0) (LO) (/,O) 01:78} (60) (50) 0,0) (5/7?)

.55 K

ER!

11 11
M M

Figure III.12. The point graph of a lumped parameter model of a beam.

81

This spectrum represents the set of all the eigenvalues of the undamped
system. Since here we have two full R points: m = 2 we conclude the

following bounds:

l
Klan
IA
0)
IA
l
:znv

IA
m

IA
0

I
IKH”
5'”

III.2 General Parameters

 

Here we relax the condition of uniform parameters set in III.1.
The bounds in this section are given for system whose gyrobondgraph is
simple full and whose parameters can assume any arbitrary values. In
III.2.l. we give two examples of such systems and compare the bounds
that we obtained to the computed eigenvalues. In III.2.2. we give the

procedure used to obtain the bounds.

III.2.l Examples: A Tree

Consider the example of a hydraulic system in Figure III.2.
If we assume the system has general parameters, then the point graph
associated with the system will be as shown in Figure III.13.a. We then
use the reduced unit inertia graph in III.13.b. and the upper bound
given in section III.2. to obtain:

b ‘5 . 439 , and

J
\1
VI
A
0)
IA

I
b

82

(a)

 

 

 

 

 

 

(4.3) (4,3)
1 1
1 1 , ,
(5%) #LM # (2) 1 1‘.(9 4)
1 1
o. o
(443) (4.3)
(b)
(1.3/4) (1,3/4)
1.
1/6 1/6
(1.2/5) .149 (1.4/9) (1.2/5) 1“1.4/9)
E t
.149 .149
1/6 1/6
(173/4) (133/4)

Figure III.13. Reducing the point graph of a system to an equivalent
point graph with unit inertias.

83

Using the iterative techniques, the interated values are:
b1 = .289

a1 = .750

A general graph

Consider the example of the lumped model of the two power dis-
tributed system discussed in section III.1. Here we will use the para-
meters as shown in Figure III.14.a. From the reduced unit inertia graph
in Figure III.14.b. we can estimate the following bounds:

b1 _<_ 1.253

The computed value of b using iterative methods gives:

1

h1 = .715

III.2.2 Bounds on the Lar est Ei envalue

We next give the bounds on the largest imaginary part and the
largest real part for systems with arbitrary parameters.

For systems with arbitrary parameters, reduce the point graph
to a similar point graph that has all inertias equal to 1. This pro-
cedure is described in III.0.

From the obtained point graph, find:

*
max r.. = max r.. , and
l] i]

41.1.
1 J

31

and

12
11
3
P.
:1
:0

14- :1
II
a
P.
:1
:U

P.

N
"Z:: mi

84

This procedure is shown in Figure III.13.b. and III.14.b. After finding

the values of a , am, a and 8N we proceed to estimate the bounds as

follows:

1 N

If the Point Graph G is a Tree:

1) Find b (G)
u
2) The bounds are: b1.g 81 x bu (G)
—a1 5- a1 -<- -am

-am: aN i -a

In the first step we find the upper bound on the largest
eigenvalue of the skew symmetric adjacency matrix. This
is done using the bounds given in III.1. or the improved
bounds that will be given in IV.1.

In the example given in III.13.b. we can easily find that:

81 = .25 , and
a1 = .75 , and
a8 = .4 , and
mm = .58

From the example of a tree given in III.1.1. we have:
b = 2.64
u
Hence the bOunds given in the example of a hydraulic system
in Figure III.2.a. with general parameters as in Figure III.13
are: b ié—x 2.64 = .439 , and

1
-.75 < a

IA

1 " 0.58 , and

-.53 E aN': - .4

85

If the Point Graph G is a General Graph:

1) Find the optimal graph Gopt of G.

2) Find b (G ).
u opt

3) The bounds than are:
b §_B x b (G

15315'“

- a ‘5 a ‘5 — a

The optimal graph is defined in III.1.2. In Chapter IV we
give a procedure to find Gopt for a class of point graphs.
More work however is needed at this point to establish a

. If for G we do

more general procedure for finding Gopt

not know any Go , we use Kb . This will give bound on

pt pt

b1 similar to the bound given in Pick's Theorem (see NA2).

In the example in Figure III.14.a. using K1 as the optimal

2

graph will give:
b1 (K12) = 7.59

However using information in IV.3.2. about the sum of two
graphs, we can deduce that the graph shown in Figure 111.14.
C. is an optimal graph of G and that:

b1 (Gopt) = 2.802
Then from the graph with unit inertia, in Figure III.14.b.
we find:

3 .447

1

and thus: b1 §_.447 x 2.802 = 1.252

Obviously the first bound is better. If we compare the

bounds obtained here to the computed value of b1:

86

I1 I2 I1 I2 I1 I2
Set
r r I1 = 3
12 = 4
13 I4 I3 I4 I3 I4 I3 = 6
I4 = 5
r = 2
(b)

 

(c)

 

‘11)

Figure 111.14. A two power model of a beam.

 

I a pAAx, 1 = Ax/KzFA, I

1 2 3

A is the beam cross-section area, 9 is the mass density, j is cross-

= Ax/Ej, I4 = ijx, r = 1/Ax.

section area moment, E is Young's modulus, K2 is Timoshenko shear

coefficient, F is the shear modulus.(adapted from BG9).

87

Computed b1 = .715

Upper bound using Go : b 1.252

pt u

b 3.392

12: u

Upper bound using K

Upper bound using Gerschgorin theorem: bu = 1.000

Obviously in this case, using Gerschgorin theorem applied
to the reduced point graph in Figure III.14.b. gives a

better bound.

CHAPTER IV

IMPROVING THE BOUNDS FOR SIMPLE FULL GRAPHS

IV.0. Introduction

 

To refine the bounds obtained earlier, more information needs
to be extracted from the point graph. Here we give a procedure based on
inspecting the point graph structure with the objective of improving
the bounds on the largest eigenvalue of the associated system. We also
give a formula for computing the characteristic polynomial of a special
case of uniform parameters. This formula was basically used in proving
the results obtained in Chapter III. It can also be used as a tool to
calculate the eigenvalues of the systems by using available techniques
for obtaining the roots of a polynomial.

Section IV.1. deals with improving the bounds obtained in
Chapter III. we first give two examples, (sec.IV.l.), to show the pos-
sible improvement in the bounds. Section IV.2. presents a procedure
aimed at improving the bounds through a dissection technique. In IV.3.
an important property of the eigenvalues of the direct sum of two graphs
is given. We then related the graph obtained by the direct sum to the
class of optimal graphs. Section IV.2. provides results concerning the
characteristic polynomial of a point graph. IV.2.1. introduces a for-
mula for the coefficients, and in IV.2.2 a recursive formula to obtain

the characteristic polynomial of a point graph is given.

88

89

Two definitions relevant to this chapter are presented as follows:
A dissection of a point graph G will mean partitioning G into
two or more subgraphs. None of the subgraphs are empty. The lines
common to two subgraphs will be called boundary lines.
A boundary degree, denoted by 6: of the boundary point i, is
the number of boundary lines incident with i. The largest boundary de-
gree will be denoted by A2. In Figure IV.1. the point graph G is dis-
, and G

sected into the subgraphs 61’ G Point 2 is a boundary point

2 3°

and its boundary degree is 6: a l.

IV.1 Improving the Bounds

In Chapter III we derived bounds on the largest eigenvalue of
a system with unifonm parameters. The bounds were based on the follow-
ing information:

(a) The number of points N in the point graph.

(b) The existence of cycles in the point graph.
The bounds deduced from this information are the best possible. This is
due to the fact that they correspond to the largest eigenvalue of exist-
ing graphs. For example, the upper bound for trees corresponds to the
largest eigenvalue of a star tree.' Thus in order to improve these
bounds, more information needs to be known about the point graph. In
section IV.1.2. we give a procedure that improves the bounds by applying
the rules given in Chapter III to chosen subgraphs of the point graph.
Two examples of systems and their improved bounds are given in IV.1.l.

Optimal graphs are necessary for obtaining bounds on the
largest eigenvalue of systems with general parameters. In v.1.3. graphs

that can be optimal are presented together with a procedure to obtain

them for a given general graph.

 

90

IV.l.l Examples

Atree

Consider a system with unit parameters whose point graph is as
shown in Figure IV.2. The number of points N = 10, and the graph has
no cycles.

From results given in Chapter III,the bounds on the eigenvalues

al=l,

1.918 = 2cos‘1
11

IA

Using the Gerschgorin Theorem applied to the point graph we obtain
a = -1

13157

In this chapter we will give the following bounds:

2.67 _<_ bl g 3.44

Iterative methods will give the following value

b1 = 2.682

In this example we see that the lower bound is improved while the upper
bound is not. The upper bound given in IV.2. is better than the upper
bound given in Chapter III if

3 1.5

DIZ

Where N is the number of points and A is the largest degree in the tree.

91

 

’ G andG 0

Figure IV.1. Dissecting a graph G into subgraphs G 2 3

Figure IV.2. A point graph with ten points and largest degree A = 7.

Figure IV.3. The point graph of a Timoshenko beam with three microelements.

92

A general graph

Consider the point graph in Figure IV.3. The associated system
is a lumped-parameter, two-power distributed system which is discussed 1
in Chapter III.1. The bounds on the largest eigenvalues obtained
earlier as compared to the improved bounds given in this chapter are

The bounds of Chapter III

1.941 5 b 5 7.59

1
Using Gersgorin Theorem

r1153

Using the dissection procedure given in section IV.II

2 5b _<_2.732

1
Using the optimal graph as a bound as given in section IV.III

b1 _<_ 2.302

The computed value using the EISPACK subroutines

bl = 2.370

We see that in this case, and as compared to the previous example, the
upper and the lower bounds are improved. The bound given using the
optimal graph appears weaker than the bound given by the dissection
procedure. However, the bound given by the optimal graph is essential

for obtaining bounds for the general parameter case.

IV.l.2 Procedures for Inspecting the Point Graph

Let G be a point graph with all its points full

Let G1, G ... be the subgraphs of G obtained by a certain

2

dissection

93

Let bl(Gk) denote the largest eigenvalue of the skew symmetric

adjacency matrix of the graph Gk’

Let the ordering of the subgraphs G ,Gé,... be such that

1
b1 (Gk) 51:1 (cl) ; k . 2.3,...

Let Ab be the largest boundary degree in all subgraphs,

Let AB be the NxN block diagonal matrix whose diagonal block

matrices are the skew symmetric matrices of the subgraphs GI’GZ’°"
Let the matrix C by such that
Ca-A-AB
then bl (G) 5-bl (G1) + bl (C) ..
or b (G) < b (G ) + Ah
1 ‘- l 1 '°
and b1 (61) 5-b1 (G) ..

(for proof see appendix 10)

To improve the bounds obtained earlier we need to minimize the left

. (l)

. (2)

. (3)

hand

side of the inequality (1) or (2); and to maximize the left hand side of

inequality (3). We next give two procedures aimed at achieving this

optimization. We first give the procedure for trees.

Trees

The procedure to improve the estimates on the bounds for the

largest eigenvalue is based on the following inspection of the point

graph G.

1. To Improve the Lower Bound

a) If the largest degree A in the point graph is A.E 3,

no improvement is obtained by the steps b or c.

94

b) Find the star SM that is a subgraph of G and has the

largest degree A.. A first improvement then is

A_<_b (c).

l

c) Find the tree WK or SK’ described in Table III.1, such

that K>'M, an improvement of the bound given in (b),

then is
bl (WK)-£ bl (G)
or bl (SK) S.bl (G).

If both WK and SK are present, choose the one with the largest number

of points. If both of them have the same number of points, choose WK'

2. To Improve the Upper Bound

a) If the ratio §_l.5, no improvement in the bounds will

E.

A
be obtained by step b.

b) Choose a dissection of the graph G that minimizes the
largest degree of the boundary points and at the same

time, maximizes the largest degree of G then an

1;

improved upper bound is

b (c) 31: (cl) + Ab.

l 1

For cases when the graph G has the ratio of its number of points N to

its largest degree A: .5 1.5, no significant improvement in the bounds

E.
A

obtained in Chapter III will be obtained by the step (b). This could

be concluded by comparing both bounds. Generally speaking, ififl = l,
A
the tree is approximate to the structure of the star, therefore, the

bound given by the largest eigenvalue of the star is close enough.

95

From the above procedure we see the need to extend the proper-
ties of the spectra of trees given in Table III.1. This will improve

the comparing capabilities and improve the lower bounds.

General graph

For a general graph the presence of cycles requires a different
procedure. The following is the procedure.
1) To Improve the Lower Bound

Find a dissection that produces a subgraph G1 that is a

complete graph Kp or a star Sn (or a tree Wn). If both

Kp and Sn exists and if JEB'p, take G1 a Sn' Otherwise

take G1 a Kp. The lower bound is then given as

1.1 (cl) 5111 (c)

2) To Improve an Upper Bound
- If E.; 1, use bounds given in Chapter III. Otherwise
A .
- Dissect the graph into subgraphs of known bl, and

minimizing Ab. Then

b
bl (G) S-bl (G1) + A .
Examples
A tree

An example of applying this procedure to a point graph that is
a tree, consider the point graph in Figure IV.4.

Procedure: l.(a). The star with the largest degree is the

 

subgraph G1 and has A: 7, thus

2.64 = J‘I—g bl (G).

96

(a) C;

 

 

(b) . » .. G

 

 

(c) (a? t (35

 

 

Figure IV.4. Three possible dissection of a tree into subgraph.

97

Procedure: l.(b). We recognize the tree WN (of. Table III.1.)

with N=9. It is the subgraph G in Figure IV.4.b. From Table III.1.

l

 

 

b (w ) = J8 + J64 - 4.1.6 - 2.67
l q 2

and 2.67 g bl (G).

Procedure: 2. A dissection that minimizes Ab is shown in

b

Figure IV.4.c. Here A = 1. G1 is shown as a star with Na7
and b1 (G) 5 47-1 + l
_<_ 3.449

Note that the ratio is §_= 10': 1.4. Therefore, the upper bound given
A 7
in Chapter III is stronger and is not improved by this procedure. The

calculated value of b1 using EISPAK subroutines is

bl = 2.682

A general graph

An example of applying the procedure for a general graph is
given in Figure IV.5.a. The point graph was studied in Chapter III and
is the point graph of a three microelement model of a Timoshenko beam
(BG9).

By inspecting the graph, we see that there exists an uncomplete
graph as a subgraph. We also see that a subgraph W exists. From

6
Table III.1. we have

 

 

b (W)=J5+425-4.2.2=2
1 6 2

 

and the lower bound is then 2 §.b1 (G).

98

 

 

 

(b)

Figure IV.5. The point graph of a lumped model of a Timoshenko beam.
(a) a dissection that gives a lower bound on b1; (b) a dissection that
gives the upper bound on b1.

99

To obtain an upper bound, the dissection shown in Figure IV.5.b.
will provide a minimal boundary degree.

Ab = l

and the subgraph G is the cycle C , thus

1 6

b1 (61) = Zoos 1 = 1.732
6
and the upper bound on bl (G) is

bl (G) g 1.732+1

The actual computed value of bl (G) is

bl (G) a 2.370

IV.l.3 The Optimal Graph

Optimal graphs are defined in III.l.2. They are necessary to
obtain an effective upper bound on the largest eigenvalue of systems
with general parameters when their associated point graph is a general
graph. Optimal graphs also provide upper bounds for systems with un-
iform parameters when their point graph is a general graph. A major
property of optimal graphs is defined below (for the proof see appendixii).
If G and G are two optimal graphs, then the graph G obtained

1 2

from their direct sum is an optimal graph, and

b1 (G) = b1 (G) + bl (G2)

A point graph that is the direct sum of the path Pn and the path Pm, is
a mxn grid as shown in Figure IV.6. The largest eigenvalue of the grid
is

b (G) = 2cos n + Zoos n
l _- ...
m+l n+1

100

3‘0
9‘0

 

(a)

Figure IV.6. (a) and (b) are two directed paths with m and n points.
In (c) is a grid that is the direct sum of Pm and Pn.

 

NT)

e e
C G S‘fg

(b) (c)

Figure IV.7. (a) a path P (b) an even cycle c: and in (c) is the
direct sum of P and C .

2 4

2;

101

 

 

 

Figure IV.8. The direct sum of a path P and a star Sn.

2

102

Since the path is an optimal graph (by definition any tree is an optimal
graph), then the grid shown in IV.6.c. is an optimal graph. The graph

G (Figure IV.7.) is the direct sum of the path P2 and the cycle C2.

The largest eigenvalue of G is

bl (G) bl (P2) + (C4)

= l + 2 = 3

e

The graph G is an optimal graph because the cycle C4

is an optimal

graph, and the path P is an optimal graph.

2

In Figure IV.8. the graph G is the direct sum of the path P2

and a star Sn' The largest eigenvalue of G is

bl (G) 3 b1 (P2) + b1 (Sn)

= l + JE:I
Here also G is an optimal graph.
To obtain an optimal graph for a given general graph, add as
many lines as required until the obtained graph becomes an optimal
graph. For graphs with an odd number of points, this procedure does

not render an optimal graph and other procedures have to be used.

IV.2 The Characteristic Polynomial

The formula we give here is for the characteristic polynomial
of a system whose point graph is simple full and whose parameters are
general except for the resistances; all resistances are assumed equal
to zero. This formula, in other words, computes the characteristic
polynomial of the gyroadjacency matrix defined in II.2.2. In case of
a system with unit parameters, the formula then gives the characteris-
tic polynomial of the skew symmetric adjacency matrix as defined in

II.3.2.

103

The formula given here was mainly used to prove the bounds
given in Chapter III, and to obtain the spectra of the trees in table
III.1. It can provide an alternative in calculating all the imaginary
eigenvalues of systems with zero resistances by using standard poly-
nomial solving techniques.

In IV.2.1. we give the coefficients of the characteristic
polynomial from the point graph. Section IV.2.2. presents a recursive
formula for finding the characteristic polynomial of a point graph in
terms of its subgraphs. For proofs of the formulae given here, see
appendix 1,2,3. A similar formula for the characteristic polynomial of
the symmetric adjacency matrix of an unoriented graph was derived by
A. Schwenk (1973), and is found in (GT1). Another similar formula
computed for the symmetric adjacency matrix for a Sigraph was found by

M.K. Gill and B.D. Acharya (1980), (GT7).

IV.2.1. The Coefficients of the Characteristic Polynomial

Let G be a point graph, and let P(G) be the characteristic
polynomial of the gyroadjacency matrix S of G such that

P(G) = det (S- AI) = An + a An-1 + ... + a = 0

Define: An elementary figure is either

a) The graph K (the path with two points), or

2
b) Every graph Cq, 9.2 3 (the cycle with q points).

A basic figure U is every graph all of whose components are
elementary figures.

Let iii be the set of all basic figures contained in G and having 1

points.

104

Let H(U) be the product of the gyrators moduli on the lines
belonging to the cycles C in U, and the square of the gyrators moduli
on K2 belonging to U.

Let C(U) be the total number of cycles with even length in U
and ce(U) be the total number of cycles with even power in U. The co-
efficients of P(G) are given by

a 0 if i is odd, otherwise

i

e
= (-1)° (U) 20‘”) 11(0) (1)

ai 113411
in the case of unitjparameters:
H(U) = 1
Thus the coefficients of the characteristic polynomial of the skew sym-

metric adjacency matrix are

ai = 0 if i is odd, otherwise
e
Z c (U) C(U)

Exagple

Consider the point graph given in Figure IV.9.a. In FigureIV.
9.b. is the set of all basic figures with two points:112 . By defini-
tion of point graph, no cycles exist inalz. Thus the powers of (—1)

and 2 in equation (1) equal zero.

C(U) = 0
ce(U) = 0

and.

a = a2 + b2 + c2 + d2 + e2 + f

105

 

 

 

 

4 (a) 3

.h--3-O 10-r--4D
c d .\\\\\:‘. e
(b)

Basic figure number:
1 2 3 4 ' 5 6

I N

Figure IV.9. a) The point.graph with gyrator constants: a,b,c,d,e,f.

b e

 

C

...—_a—h.
C.
f
O-e--‘.
)

b) The six basic figures with two points; c) The six basic figures with

four points.

106

 

 

 

 

 

gasic figure number:

 

Figure IV.lO. a) An oriented graph similar to the point graph in Figure
IV.9. except for the orientation on line b. b) The basic figures with

four points.

107

The set of all basic figures with four point 244 are given in IV.9.c.
The first three basic figures consist of one cycle each so the power of

(-l) in all three is
C(U) = 1

The first and the third basic figure are both even power cycles thus

the power of (2) in both is
ce(U) = 1

The second basic figure is an odd cycle thus the power of (2) is
ce(U) = 0

The last three basic figures consists of two paths K each and no cycles,

2
so the power of (-l) and 2 in all three of them are equal zero.

Thus the coefficients of f)is

. (abef) + (—1)°. 2 . (acfd) + (-19 . 2‘. (cbed)

+ a2. f2 + c2. d2+ b2. e2

1 1

1
34,: (-1) . 2

Now consider the point graph in Figure IV.10.a. It is basically the
same as the point graph in Figure IV.9.a. except for the power orienta-
tion on line b. This power change does not effect the coefficients of
AZ, since the basic figuer with 2 points does not have cycles. The
power change on b changes the power direction on the first and third
basic figures with four points. They both become odd powered as seen

in Figure IV.10.b. and thus the coefficient a4 becomes

1 1 1

(abef) + (--1)0 2 (acfd) + (-1.)0 2 (abed) +

a2 f2 + c2 d2 + b2 e2

0
a4 — (-1) 2

108

If the parameters a = b a c = d = e a f = 1, then for Figure IV.9.a.
the characteristic polynomial is thus

1? + 61? + 1 a 0 , and

for Figure IV.10.a., the characteristic polynomial is
A4+ 612+9=0

These results could be easily checked by finding the determinant of the

skew symmetric adjacency matrix for both point graphs.

Corollary

1. For Trees:

a) The spectrum of the gyroadjacency matrix of a tree is invariant
under power orientation.' This can be proved form equation (1)
since the term with negative sign is only dependent on cycles.

b) The spectra of the skew symmetric adjacency matrix and the
symmetric adjacency matrix are identical, (apart from the
factor 1 - J:I). This can be proved by substitutingl.by il
in the characteristic polynomial of the symmetric adjacency
matrix. The coefficients given in Cvetkovic (GT2) then be-

comes

ai = 0 if i is odd, otherwise

:2 (-1)p(U) (-1)j

a.
U a .
J {1]
where p(U) is the number of components in U, for a tree

p(U) = j and thus

109

a (-1)2j

j a U621 UeQIIL
which is identical to equation (1) reduced to unit parameters
and zero cycles.

2. Cycles with Odd number of Points
The spectrum of the gyroadjacency matrix is invariant under the
change of power orientation on any single line that belongs
only to odd number cycles. This can be easily proven from
equation (1) since odd number cycles do not effect the sign
in the summation. Only even numbered cycles with even powers
contribute to the power of (-1). Note also that cycles with
odd number of points do not contribute to the coefficients

of the characteristic equation.

IV.2.2 A Recursive Formula

This recursive formula serves to obtain the characteristic
polynomial of a point graph if we know the characteristic polynomial
of one of its subgraphs.

Let ruv denote the gyrator modulus on the line between the point u and
the point v,

Let Ce(v) denote a cycle with even power that passes through the point
V.

Let Co(v) denote a cycle with odd power that passes through the point
v.

Let HC(v) denote the product of all gyrator moduli of the lines of the

cycle C that passes through the point v.

Let P(G-C(v)) denote the characteristic polynomial of the point graph
obtained from G by deleting all points and lines belonging to
the cycle C(v).

Let P(G-v) denote the characteristic polynomial of the point graph ob-
tained from G by deleting the point v and all lines incident
with it.

Then

P(G) 3A.. P(G - v) + 2E: r2 . P(G - v - u) +
uv

*

2. Z 11c0 (v) . p(c — C0(v)) -11ce (v) . P(G - c°(v)) (3)

**

where 2;: is the summation over all points u that are adjacent to
the point v, and is the summation over all the odd and even
power cycles that pass through the point v.

Note that cycles with odd number of points do not contribute
to the summation.

The following notions, although of an abstract nature, are
useful in applying the above formula.

1. If G is a point, then P(G) = A

2. If G is an empty graph, then P(G) = 1

3. If G has two disconnected components, G. and G then

1 2’
Me) = P(G1) . P(GZ)

An example of the use of this formula is given below. Consider again

the point graph given in Figure IV.9. Applying equation (3):

P(G) AP(G - l) + a2 . P(G - 1 - 2) + b2 . P(G - 1 - 3) + c2

P(G - 1 — 4) + 2[adfc . P(G - adfc) - abef . P(G - abef) — cbed .

P(G - cbed)]

2
P(G - 1) = 13+ (d2 + e2 + f )1

19((9-1-2)=12+f2
P(G-1-3)-12+e2
P(G-1-4)=12+d2

P(G - adfc) = 1 (since it is empty)
P(G - adef) - 1

P(G - abed) = 1

Substituting, we get
3 2 2 2 2 2
P(G) - 111. + (d + e + f )1 ] + a (1 + f )
2 2 2 2 2 2
+ b (1 + e ) + c (1. + d )
+ 2(adfc - abef - cbed)

4 2 2 2 2 2 2 2
=1 + (a + b + c + d + e + f )1

2 2 2 2 2 2
+ 2[ (adfc - abef - cbed)] + [a f + b e + c d 1

If we substitute for a a b = c = d = e = f = 1, we obtain
A 4 2
p(G) a 1 + 61. + 1

which verifies the results obtained in the proceeding section.

Corollary

Let G be a point graph having two subgraphs G1 and G2 con-

nected by a bridge. Let the bridge be incident to point u in G1

and point v in G Let ruv be the gyrator modulus on the bridge uv.

2.
Then

P(G)=P(G) .P(G)+r 2pm -u) .P(G -v) (4)
1 2 uv 1 2

112

The use of the above equation to obtain the characteristic polynomial
of a system is shown in the following example. Consider the point G
shown in Figure IV.11. It can be dissected as two subgraphs G1 and G2
with the bridge uv connecting them. If we assume unit parameters and
if the characteristic polynomial of a path with N points is written

as P", and the characteristic polynomial of a star with N points is

written as S , than

N
P(G) = P(Gl) . P(GZ) + P(G1 - u) . P(G - v)
a S4 . PN—4 + 53 . PN-S
N-2 2
We know that SN = 1 (1 + (N-2)) then
2 2 2
P(G) =1 (1 + 3) . PN-4 + 1(1 + 2) . PN-S'

After some algebraic manipulations_and using the following properties

 

of PN
AP = N+1 - PN-l
.N . -1 .
and l . PN = Sln (n+l)6 , 6 = cos (i1 )
sin 2
We obtain P(G) a 1 . cos (N-l)0 = 0
thus 6 = (sk + l)!
2(N-l)

and the roots of the characteristic polynomial are

1

0,1=21C08(2k+l)1t 3k=O,-o,N-l;i=V"o
2(N-l)

The above example is an illustration of the method used to obtain the
spectra of trees given in Table III.1. It gives an example of a

possible technique for extending these results.

113

 

 

 

Figure IV.11. A point graph with a bridge uv, the characteristic
polynomial is:

P(G) = PN_4 . 84 + PN_3 . S

114

The number of walks

The concept of the number of walks is related to the sum of
the eigenvalues of the skew symmetric adjacency matrix. Let Nk(i,j)
be the sum of signed walks of length k from point i to point j. Each
line in the walk is signed negative (-) if the walk is in the same
direction of the power orientation, and is signed positive (+) other—
wise. The sign of the walk from i to j is the product of all signs
on the lines of the walk. If Sk = (3:2)) is the kth power of the

skew symmetric adjacency matrix then

k

sij = Nk(l,j) and
N k N
Z )(i . Z "k (1,1)
121 i=1

The above result is expected to be used as a basis to investigate the
spectrum of the complements of the point graph with a goal of obtain-
ing more insight into the effect of the change of power orientation

on the spectrum of a point graph.

CHAPTER V

SIMPLE PARTIAL GRAPHS

Simple partial graphs are the most general form of simple
graphs and thus obtaining an estimate for the largest eigenvalue is a
more complex problem. For a special case, we can give estimates; how-
ever for the majority of this class we still have to refer to the
traditional procedure of obtaining the estimate through the state
matrix.

If the simple partial point graph has only full points and
partial R points and if no two partial R points are adjacent, then the
bounds on the imaginary part of the eigenvalue is given in V.1. At
this point more work is required to extend these results.

In V.2., and for the purpose of completeness, we present a
numerical technique given by H. Wolkowiz (NAS) for estimating the
eigenvalues of non-normal matrices. The choice of method is due to
the fact that remaining classes do not have a distinct reduction to

normal matrices as for systems represented by simple full graphs.

Similarity Transformation

The procedure described here for a system whose point graph is
simple full-R partial-I will give a new system that has the same spec-
trum and the same point graph as the original system. The advantage

is that the new system has all inertia parameters equal 1. This reduces

115

116

the state matrix given in II.22. equation 2 from:

A a [(SP - RF) + S

A

(sP - R )"1 sT ] [1"] to

12 P 12

1 ~T

= (S - RF) + 812(SP - R ) S ... (1)

F P 12

and A is similar to A.

The procedure is

Notations

1.

If

Replace the gyrator modulus rij between point i and

point j by r:j where

*

rij a ri. if pOints i and j are both full pOints
41.1.
1 J
* I s
rij = ri. if the pOint j is a partial R pOint
JI.
i
*
Replace the resistance on the full point i by Ri where
*
R. a R
1 _i
I.
i

This procedure gives a simpler system whose eigenvalues

can be studied and then related to the original system.

G is a point graph that has N full points then

... is the subgraph of G that contains all the N full points

and will be called the simple full subgraph, and

... is the subgraph of G that contains all the partial R

points and will be called the simple partial R subgraph.

(G) will denote the largest imaginary part of the eigenvalue

of the system associated with the point graph G.

117

Next we present some results for the case when all points of

the partial R graph are not connected with each other.

v.1 A Non-Connected Partial R Subgraph

If every partial R point of the point graph G is not adjacent
to any other partial R point, we have a non-connected partial R sub-
graph. In this case the bounds on the largest real and imaginary part

of the eigenvalue of the system associated with G are

bN (GP) gbl (G) 5 131 (GP), and
. ~ ~ -1 ~T
if we let B = -(R + S R S ) ; then

P 12 P 12

aN(B) 5’s (G) g a (B).

l l

The value of b1 (GP) can be found for the simple full subgraph by

applying the procedures given in Chapter III and IV on the subgraph GF'

A special case

Sparse partial R points: If no two partial R point are adja-
cent to the same full point, we say that the partial R points are
sparse. The bounds on the imaginary part of the eigenvalue are as

above, and the bounds on the real parts become

min(R1".+Zr1lk.1Z R .-I) < a (G) gmax (RFi + Z: *2 R-l)

. r.. .
1 F1 3 ij Pi l 1 j ij Pi
Where
*
rij' . . is the gyrator modulus between the full point i and the

partial point j,

R . . . . is the resistance on the full point i, and

R . . . . is the resistance on the partial point j.

118

If we assume unit parameters

*
RPi = RFi a rij = 1 for all i = l . . .

then the bounds on al(G) reduce to

-(l +A?) _<_a _<_-1

l

where
A: is the largest boundary degree of all partial R points.

The above bounds could be easily proven using the results given in
Amir-Moez (NA12) on the bounds of the real and imaginary part of the
eigenvalues; and noting that when the partial I subgraph is not con-
nected then

SP 3 0

At this point more investigation is needed in the following directions:
1. In the case of non-connected partial R.subgraph, the matrix
S12 can be considered as a signed adjacency matrix of the
subgraph whose points are the boundary points in the partial
R subgraph and the boundary points in the full subgraph.
The eigenvalues of such graphs are studied in (GT7) and more
development will lead to relating the bound of the real
part to the structure of the above mentioned subgraph.
2. The effect of different structures of GP on a1(G) could
be found for some special cases of boundary points.
3. In the most general case; we have two possibilities:

a) Either relating the bounds to some function of the

structure of the subgraphs GF’ GF and others or

119

b) starting from the point graph and constructing a re-

lated oriented and non-oriented linear graph that can

be used to estimate bounds on the largest real and

imaginary part of the eigenvalues.

For the purpose of completness, we present next a numerical method

that gives bounds on the eigenvalues and that uses the state matrix.

These bounds are given in Wolkowitz and Styan (NAS). They give bounds

on the eigenvalues, their real and imaginary part using the state matrix.

v.2 Estimates From the State Matrix

For the remaining classes of systems, the state matrix is in

general a non-normal matrix.

given in this chapter.

This justifies the choice of the estimator

Let: A be an nxn matrix, and N(A) be the euclidean norm of A,

define

* *
D 8 AA - A A

 

1 *
B=§(A+A)
1 *
C-2(A-A)
u 4
KA=EN (A)—
2
K=[N2(A)-
A
r
u [194(13)-
Ka=<
[N2(B)-
\
2 2
KB=[N (B)-
[112(c)-
u
Kc- 2
[N (C)-

 

 

MD) 1

if N(B) 3 N(C)

otherwise,

if N(C) Z N(B)

otherwise,

120

 

 

 

3
2 2 n — n 5
KC=[N(C)-(48)N(D)]
u 2
(5;)2 a KT - ITr(T)I /n for T = A, B or C
n
x; - ITr(T)| 2/n
(82) a max (0 )
T ’ n
u
u 1c), 2 I'm-(21)]
”AH—A.) ”‘A‘ 71——
n
mu _ m2 a Tr(B) mu _ m2 3 Tr(C)
B's n ’ c‘c n
Theorem

Let 1: be the ith eigenvalue of the matrix TE A, B or C; and

let the matrix A be a real nxn matrix, then for 1 §_j E'k g’n,

 

k
2 u j - l 5 1 T u u n - k H
”T ‘ ST ( n - j + 1) 5-k - j + 1 iaj Ai 5-”T + ST ( k )
1.1
74-17:: *5 _<- (591’
J J 2k

This theorem gives bounds that are closer than gerschgorin discs. It
requires more computations, but it offers more information about the
eigenvalues of the matrix.

This theorem can be used together with equation (1) to obtain
bounds on the eigenvalues for some special structures of simple full
R graphs. The theorem given here can be programed as a subroutine to
obtain estimates in cases when the methods of Chapter III are not

applicable.

VI . CONCLUSION

Summary of Results

Bounds on the largest eigenvalue of a class of systems are
obtained by inspecting the bond graph model. A summary of the procedure
is given in the chart in Figure VI.1.and Table V1.1. The given pro-
cedure is obtained from the results given in Chapter III and Chapter V,
and can be coded to be used in digital computers. To be able to pro-
gram the results given in Chapter IV, some graph theory subroutine will
be needed to detect various structures of graphs. These are not
needed when coding the results of Chapter III because we need only to
discirminate between trees and general graphs. This discrimination
could be obtained as follows: If the number of gyrators is equal to
or greater than the number of l—junctions, then we have a general graph
(cf.GTl). We next compare the results obtained in this work to some

classical results.

Comparison To Other Methods

We compare the bounds given here to the bounds given by three
other methods. They are:

Pick's Theorem (1919) for obtaining an upper bound on the

largest real and imaginary part of the eigenvalue of a

matrix, (NA10).

Gersgorin Theorem (1931).

The Euclidian Norm: NE(A), (of. section II.4).
The reason for this choice is that the information, the number of Opera-

tions required, and the accuracy for the four methods are comparable.

121

122

 

SKETCH 0F
SYSTEM.

1

BOND GRAPH
MODEL .

 

 

 

 

 

L

GYROBONDGRAPH;
POIN T GRAPH.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure V1.1. A flow chart summarizing the results. B.L. are boundary
lines. The number in the circles refer to a block in Table v1.1.

123

Table VI.l. Summary of Results.

(1)

 

 

UNIT PARAMETERS:

GENERAL PARAMETERS:

a = -l

t
2cos N:I ‘:_b : VN-l (cf. sec. III.l.2)

min (R.) <|al< max (R.)
. i ‘- -— . i

l l
r..
Findmax—ll— ar

i,j JIin m

Find bu for the equivalent unit parameter graph

b < b x r (cf. sec. III.2.2)
-' u m

 

(2)

 

 

UNIT PARAMETERS:

If N is odd:

If N is even:

GENERAL PARAMETERS:

-l
§.cot‘-

IA.m
O'u

x
2cos N+l

I
2cos 5. b 5 C°t 5,? (cf. sec. III.l.2)

min (R.) <|a|<max (R.)
i i ‘- '- . 1

Find max -£l- - rm
i,j 45.1

Find the optimal graph
Find bu for the Optimal graph

(cf. sec. III.2.2)

 

continued next page

 

 

124

Table V1.1 (continued)

(of. sec. V.l)
(3)

 

 

UNIT PARAMETERS AND GENERAL PARAMETERS:
For bounds on b: apply (1) or (2) to the simple full subgraph.

For bounds on a: apply Gerschgorin theorem to the matrix
-1 T

b ' ' RF ‘ S12RP s12

 

(4)

 

 

UNIT PARAMETERS:

For bounds on b: apply (1) or (2) to the simple full subgraph.

For bounds on a:

GENERAL PARAMETERS:

For bounds on b: apply (1) or (2) to the simple full subgraph.

For bounds on a: apply Gerschgorin theorem to the matrix

-i T
B ' ' RF ‘ S12"? S12

 

(5)

 

Find the state matrix and then use Gerschgorin theorem (or see v.2).

 

 

 

 

125

Bond Graph Method

Limitations:

 

Applies currently to only systems whose gyrobondgraph is a
simple full graph or a special form of simple partial graph.

Information Needed:

The simplified gyrobondgraph (the point graph).

The largest parameter on the similar gyrobondgraphs (that has
all inertias parameters equal 1).

Number of Computations:

For a system of order N:
If the system .has general parameters then the number of required compu-
tations n is

C

N + 2 5_nc S N2 + 4
depending on the structure of the gyrobondgraph.
If the systems has uniform parameters then the number of re—
quired computations nC ; 5 depending on the structure of the gyrobond—

graphs.

Accuracy:

For systems with uniform parameters, the bounds are the best
in comparison to the three other theorems.

For systems with general parameters, the upper bound is better

only to the bound given by Pick's theorem.

Pick's Theorem

 

Limitations:
'A' - *
A+A A-A

For any real matrix A and if G = —E— and T 2

 

1 = a + ib is an eigenvalue of ANxN then

126

fall‘s g.N , and

JL
b‘s t.cot 2N ,

where g is the largest entry of G and t is the largest entry of T.

Information Needed:

The order of the matrix and the largest entry of the real and
imaginary components of the state matrix.

Number of Computations:

For a matrix of order N, we need 3N:§. operations for each
of the real and imaginary part, in addition to the computations re-
quired to find the state matrix.

Accuracy:

The upper bounds given here are larger than any upper bound

obtained by the three other methods.

Gerschgorin Theorem

'Limitations:

For any complex matrix, if the union of the discs is the disc
with the largest radius, then we cannot obtain a lower bound.

Information Needed: The state matrix.

Number of Computations:

For a real matrix, to obtain bounds on the largest real and
largest imaginary part of the eigenvalues, then we need 3N + N2
operations for each.

Accuracy:

For a system with uniform parameters the bounds obtained using

the bond graphare better. In case of general parameters, the bounds

obtained here are better than any of the methods discussed.

127

The Eucledian Norm

Limitations:

Gives only upper bound.

Number of Computations:

For a real matrix, to obtain bounds on the largest imaginary
part of the eigenvalue, we need (N_:_£)2 operation for each.

Accurac :

For the general case comes after the Gerschgorin method.

Further Directions of Research

From the above comparison we note a substantial decrease in
the number of computations required to obtain the bounds. This justi-
fies an extension of this work aimed at broadening the range of prob-
lems to which the estimation procedure given here is applicable. The
following points are suggested directions for further work.

1. For systems with general parameters we obtained an upper

bound on the largest imaginary part of the eigenvalues.
The results need to be extended to provide a lower bound.
2. For systems whose point graph is simple partial, can we
use the results developed in this work to provide bounds
on the imaginary part of the eigenvalues, and use the
spectral graph theory to obtain bounds on the real parts?
3. For systems whose gyrobondgraph is complex can we construct
a linear graph that can be used to estimate the eigen-

values of the system?

128

Given a system with general parameters and with the con-

straint that Ri = constant for all i, we know the effect

I.
of changing thé power direction on one line on the charac-

teristic equation. This result needs to be generalized
as to the constraint given above. We also need to in-
vestigate the effect of the power change on the largest

eigenvalue.

APPENDICES

129

APPENDIX 1

 

The Coefficients of the Characteristic Equation:

The expression for the coefficients of the characteristic
equation of the skew symmetric adjacency matrix with arbitrary entries
Acan be obtained from a theorem by A. spialter (GT5). The theorem is
also described in (GT5) by Cvetokovic. In their work they give the
coefficients of the symmetric adjacency matrix. This could be ex-
tended as shown below to the case of a skew symmetric adjacency matrix
associated with a directed graph. we first present the theorem for

the symmetric case .

Theorem 1. [GT2], [GT6]

Let G be a graph with weighted edges, and let

P(G) a det (1I-A(G)) = 1n + a1 1“-1 + ... + a0 = 0

be the characteristic polynomial of G. Define:

Elementary figure E: The graph K or

2
The graph Cq (q> 2),
Basic figure U: Every graph all of its components are

elementary figures

p(U): the number of components in the basic figure U,
ct(U): the total number of cycles in the basic figure U,
QL i: the set of all basic figures contained in G and

having exactly i points,
e(E): the set of edges belonging to an elementary figure E

w(u): the weight on the edge u,

Then:

where

130

C(u,U) = 1 if u is contained in a cycle in U, and
= 2 if u belongs to K2; K26 U.
c (U)
a. a Q (-l)p(U) O 2 t O H(U) ... (l)
1 (Je .

J.

C(u,U))

HUS) = g; y (w(u) ... (2)

* is the product over all e(E).

** is the product over all Es U.

Next theorem 1 is used to derive a formula for the coefficients

of the characteristic polynomial of the skew symmetric adjacency matrix.

We note that from the definition of S(G) the sign of the weight on any

direct edge of G changes according to the direction of traversal of the

edge. This produces the need for classifying cycles according to their

orientation.

Define:

Q§Q_(gygp) cycle: as a cycle with an odd (even) length.

9gp oriented cycle (gygp oriented cycle): as an even cycle
in which the number of edges that have a clockwise direction

is odd (even).

We note that the definition for the orientation of cycles does not

apply to odd cycles.

Theorem 2

Let C(U) be the number of even cycles in the basic figure U,

ce(U) be the number of even oriented cycles, and let

131

P(G) a det (1I-S(G)) = A“ + a1 A“"1 + + a0 a o

be the characteristic polynomial of the oriented graph G.

If i is odd, then

ai = 0 , and ... (3.a)
if i is even, then
s
ai - éz;%i (--l)C (U) 2C(U) N(U) ... (3.b)
i

where H(U), U, andqli are as defined in Theorem 1.

m:

In equation 1, Theorem 1, the factor of 2 is due to the two
directions of traversal of each cycle in every elementary figure [GT6].
In the case of the coefficients of P(G), the weights on the edges do
not change signs for different directions of traversal. However in the
case of P(G) the weights change signs depending on the direction of
traversal of the cycle.

We have three possible cases for cycles Cq a E; EE:U.

C(u,U)) in equa-

l. g is odd: In this case the product.H(w(u)
tion 4 will have a positive sign in one direction of
traversal and a negative sign in the other direction. So
if E a Cq, q is odd then H(U) = 0 whenever qu:U, and the
contribution of the basic figure in the sunmation 3.b is
zero.

Now whenever iis odd then any Uecui will have an elementary

figure E that is a cycle Cq, q is odd. Thus every term

in summation (3) will be equal zero, and 3.a follows.

132

2. If g is even and Cq is odd oriented: In this case the

product “(w(u)C(u’U)

) will have the same sign in both
directions of traversal, and the sign of the product is
negative. Thus the power of (-l) in equation 1 will be
decreased by the number of even cycles that have odd
orientation and that belongs to U. The power of 2 in
equation 1 will contain the number of Cq with odd

orientation, q even.

3. If q is even and Cq is even oriented: Here the product

C(uttJ)

 

 

H(w(u) ) will also have the same sign for both

directions of traversal and the sign of the product is
positive. We conclude that the power of (-l) in equation
3 will contain the number of cycles, with even orientation
and even length, that belongs to U.
The power of 2 in equation 3 will also contain the number
of cycles, with even orientation and even length, that
belongs to U.

If E a K

the product of the weight on K is negative, and

2’ 2

the power of (-l) in equation 3 is decreased by the number of K2611.
Now in equation 1 if we subtract from the powers of 2 the

number of odd cycles in U, and subtract from the power of (-l) the

number of K2 and the number of even length cycles with odd orientation,

we obtain equations 3.b.

Corollary 1
Changing the direction on any edge that does not belong to an

even cycle does not change the spectrum of the oriented graph G.

133

This fact can be easily proved by observing that odd cycles
do not contribute to any coefficient of P(G). Also the orientation
on any edge that does not belong to a cycle does not effect the terms

of equation 3.b.

Corollary72

 

If G is an oriented tree, and G is obtained from G by relax—

ing all the directions on its edges, and if the spectrum of S(G) is:

Spec(G)=[i 3'1 '1' 3'1 ...],j=~/:I

1’ 2’
Then the spectrum of A(G) is

Spec (6) = [i1 , i1 ...]

l 2’

Proof:

If G is a tree then Theorem 1 reduced to:

a. ...— : (-1)p(‘” 11111) (4)
i UIEQLi

Now in (2) if every w(u) is replaced by jw(u), j = 4—1, then equation

5.b, for G is a tree, becomes identical to equation 4 as follows:

..-Z

11 11 (jw(u)2) = (_me1 11(1)).
1- ** *

From equation 4, and for trees if i is odd:

‘U

i 0 and

134

APPENDIX 2

Recurrence Formula for Computing the Characteristic Polynomial:

Starting from the formula for the coefficients of the charac-
teristic equation developed above; we use a proof similar to the proof
used by A. Shwenk to develop a recursive formula for the characteristic
equation of the symmetric adjacency matrix. Here we prove a general

parameters formula for a skew symmetric case.
Theorem

Let G—v be the oriented graph obtained from.G by deleting
the node v and all edges that have v as their
initial or terminal node,

c°(§) be the even cycle with even orientation that con-
tains the node v,.and
C°(v) be the even cycle with odd orientation that con-
tains the node v, then
the characteristic polynomial of the skew symmetric adjacency matrix
of the oriented graph G is given by:
2

P(G) = 1.P(G-v) + 2:: ruv . P(G - v - u)

'k

+ 2. Z (11c°(v)) . p(c; - c°(v))

- 2. E (IICe(v)) . p(c; - cam) ...(5)

Where:
v is any node of the oriented graph G of order n,

ruv is the weight on the directed edge (uv),

135

* is the summation over all the nodes u adjacent to v,

** is the summation over all even cycles with odd orientation
that contains the node v, and

*** is the summation over all even cycles with even orienta-

tion that ocntains the node v.
Proof

From equation 3.b we have

ce(U) 2c(U)

a. (-l) . . N(U)

i 3 Us ‘Ui
We prove (5) by establishing a one to one correspondence be-
tween the basic figures contributing to the coefficient ai on the left
hand side of equation 5, and the basic figures contributing to one term
on the right hand side.
Let Ue‘ui be a basic figure of G and let m be its contribution
to the coefficient ai. We ahve two possibilities:

(l) v t U take U' = U and U' is viewed as a subgraph of (G-v).

(2) v e EsU take U' =U - E and U' is viewed as a subgraph

of (G - E).
In case (1) since U' = U - E, the U' will contribute m to the coefficient
of 1n-J'-'l in P(G - v) and thus supplies m towards the coefficient of
n-i

1 in 1P(G - v).

In case (2), since U' = U - E, then U' will contribute:
ce(U') our)
(-1) . 2 . II(U') ... (6)
to the coefficient of 1n-2-(l-2) = 1n-1 in P(G - E) and 2 is the number

of vertices of E.

136

Now if E = K then expression 6 becomes:

21
ce(U) C(U) n<u> m
(-1) . 2 . ———— . .

2 2
r r
uv uv

 

Hence U' supplies m to the coefficient of 1n-l in:

r2 . P(G - u - v) .
uv

If E = Ce(v), then expression 6 becomes:

ce(U) 1 2c(U) -1 11(1)) 3 .111

(-1) o (-1)- o o 2 o e -——e-—-
HC (v) 2.(HC (v))

Hence U' supplies m to the coefficient of 1n-l in:

-2.(HCe(v)).P(G — Ce(v)) . .

If E a C°(v), then expression 6 becomes:

6 I
(_l)c (U) . 2C(U) . 2-1 . HQU) 3 1110
US (v) 2.(HC (v)

Hence U' supplies m to the coefficient of 1n-l in:

2.(HC°(v)).P(G - c°(v)) .

Now if E = Cq(v), and q is odd, then the contribution of U to
the coefficient a.1 is equal to zero. In this case let m a 0.k, where
the zero is due to the presence of Cq, and k is the contribution of
all other elementary figures in U. Hence U' supplies k to the coeffi-

cients of 1“.1 in the term:

q
We conclude that the term P(G - Cq(v)) does not exist on the
left hand side of equation 5.
Thus the contribution of each basic figure U to the left hand
side is matched by a corresponding contribution to the right hand side

by a basic figure U‘, which completes the proof.

137

APPENDIX 3

 

The Characteristic Polynomial of an Oriented Graph in Relation to Two
Subgraphs Connected by a Bridge

Let G be an oriented graph with characteristic polynomial P(G)

let G1 and G2 be two subgraphs connected by a bridge as shown in Figure

1. Then
P(G) :- 1=(c; ) . p(c ) + r2 . p(c; -w) . p(c - u) (6)
1 2 uw 2 1
Proof:

Applying the recursive formula 3 successively we get:

P(G)

1P(G - u) + 2;: r2 P(G - u - w) +
wu

2 . ; 11c°(u) . P(G-C°(u)) -IICe(u) . p(ecemn

2
1P(GZ) . P(G1 - u) + rwu P(Gl - u) . P(G2 - w) +

P(G ) .IZ:: r2 P(G - u - w) +
2 wu 1 -

*

P(GZ) . (2.211 c°(u)p(G—c°(u)) -IICe(u)P(G-Ce(u))

** fl

... (6)

where * is the summation over all w adjacent to u,

and ** is the summation over all C°(u) and Ce(u).

The above formula is usefull computing the characteristic polynomial of
sparse systems.
Using equation 5 we can find a general formula for the path

as follows.

138

 

Figure 1. Example of two subgraphs joined by a bridge.

139

APPENDIX 4

The Characteristic Polynomial of a Path
For a path with N point let

det (SF - 1U) = PN = 0 , U is the identity matrix.

then:
N N-l Pn+1

From equation 5, and starting with a path with N points; construct a

path with N+l points, then

P = 1PN + P

N+l N-l

This is the recursion formula for Chebichev's polynomial Uj of the

second kind as follows:

 

(i)3+1 . pj g Uj=l(£3}) , i a y:;
and u = sin ( (j + 1) cos-1(i 1/211
3 sin cos -l(i 1/2)

The above results could also be obtained from the characteristic poly-
nomial of the symmetric adjacency matrix, since for trees the absolute

values of the spectrum of the symmetric and skew symmetric are the same.

140

APPENDIX 5

 

The Characteristic Polynomial of a Star

For a star with N points let

then S = 1 ( 1 = (N-l)

Proof:

Applying equation 5

S a 1P(G-u) + (N-l) P(G-u-w)

N
P(G-u) = 1N”1
P(G-u-w) = 1N.-2
80 SN = 111”"1 + (N—l) 1N-2
: 1”"2 (12 + (N-l))
which gives b = JN-l = b
u us

where bus is the largest eigenvalue of the star tree.

141

APPENDIX 6

 

Bounds for Largest Eigenvalues of Trees

b < b = 4N—l
us

u
Since all trees with N points havethe same number of lines:

N-l; then the number of entries of the matrix S is = 2(N-l)

F
for a tree IISFII : = 2(N-l)
; 2 2
but ||—|-|E=):).i
SO N
Z 12 = 2(N-l)
i-l 1

and since 1i occurs in complex conjugates then:

N/2 2
2 Z 1 = 2(N—l)
i=1 i

2
11 _<_ (11-1)

1 < VN-l = b

l‘- us

142

APPENDIX 7

General Parameters Problem

Given a skew symmetric matrix SF 2 [Sij] define a matrix H =

[h..] such that h.. a sgn (3..)
13 l] 1]

let: 3 a max 3.. ,
. . ij
i,j

let G be an oriented graph associated with the matrix H, such that
H is the skew symmetric adjacency matrix of the oriented graph G,

if ib(.) is an eigenvalue of a skew symmetric matrix such that

bum: _<_bl(.)

then:
(A) If G is a tree or having only cycles with odd number of
points then:

b1(SF) §_bl(H) * s
(B) If G has cycles with even number of points then:

bl(SF) _<_bl (Hopt) * s

where H0 is the adjacency matrix associated with an

pt
optimal graph Gopt of G.
i.e. b1(H) E-bl(Hopt)
Proof:

Let

P1h‘ g
'6
X

143

IAX = blx
*
x x = l
b *1 Z (* *) (1)

Proceed as follows:

(A)

(B)

Whenever xr has a negative real part, change the sign of
xr so we have the real part of all x's positive. At the
same time change the sign of the corresponding ars such
that equation (1) remains unchanged. This is equivalent
to the similarity transformation of multiplying row r
and column r by -1. In the graph G this corresponds to
inverting all powers on point r. After this operation

we will have xr having their arguments or such that:
-x/2 < 0 _<_t/2
Rename the new vector y and equation 1 now becomes:

b = l :E:: c (y* - y *) (2)
rs rys rys "°

1 i r<:s
Note that:

lc lb

I‘Sl I‘Sl

Reorder the vectors y in equation (2) by changing the

indeces such that we always have:

o_>_<1

r r+l

At the same time change the signs of brs whenever needed

such that equation (2) remains unchanged.

144

This operation is equivalent to a similarity transforma-
tion by permuting row k and column k. In the oriented
graph G this is equivalent to a relabeling operation.

Now rename the new vectors z and equation (2) becomes:
1 2 * t

b 3'? d (z z - z z )
i r s r 3

Note that here

(C) We have for r45

rqe4

* *
(z z - z z ) a 2.r r sin ( O — O ) > 0
r s r s r s r 3
(since in step 2 we made all 0r>103 , and in step 1 we
made all -1t/2< 0r _5 1/2)
r , r are the modulus of the vectors 2 , z .
r s r s

(D) Equation (3) now becomes

b a 2::: 2.d .r r sin( 0 — 4 )
1 rs r s r s

r<<s
_ d t *
< 2. d .r r Sln ( 0 - o ) <-? (z z - z z )
-— r s r s - i r s r s
r<:s
where d = max Id 1
rs
r,s
d * * 1
so b <-? . 2 H z = d z . ruH. z < d.b (H)
1.. i i - l

H is a skew symmetric matrix with the same number of

zeros as the matrix SF and has all the upper diagonal

enteries positive.

(E)

(F)

145

In the case of a tree or all odd numbered cycle graph;
changing the power direction on the individual lines does
not change the spectra of the graph. Therefore H can be
taken as an adjacency matrix of the oriented graph G
that is obtained from G by operations in (a), (b) and
then by changing some powers on individual lines in step
(d).

If G has even numbered cycles, H can be taken as the skew
syrmnetric adjacency matrix of the oriented graph G that
has the same numberof lines as G but with different power
orientation. Since G is spectrally different from G,

and G is unknown, choose G as the optimal graph such as:

... < 2
b1 (H(G)) __ bl (H(G))

146

APPENDIX 8

The State Matrix of a Class of Simple Partial Graphs

Let G be a point graph that has full points and partial I
points only. The state matrix of the system associated with such point
graph is given by:

-l

T
A 2 [(SF - RF) + S12 (SP - RP) $12] [I 1

where:

315"” is the gyroadjacency matrix of the simple full subgraph, and

SP... is the gyroadjacency matrix of the simple partial subgraph, and
S . SF S2 is the gyroadjacency matrix of the point graph, and
--ST S
12 P

RF"' is the diagonal matrix of resistances adjacent to full points

RP... is the diagonal matrix of resistances adjacent to partial R points
I-l... is the diagonal matrix of the inverse of the inertias adjacent

to the full points.
Proof:

In a gyrobondgraph we have only effort sources. Assigning
causalities to sources and integration causalities on storage elements
does not complete the augmentation of the bondgraph. In this case a
proper but not unique (see B62 pp 150), choice is to assign conductance
causalities to resistances adjacent to partial points.

Let e ,f

f be the effort and the flow on bonds adjacent to a

f
storage element.
Let ep,fp be the effort and the flow on bonds adjacent to a

resistance that is adjacent to a partial point.

147

Let __ denote a column vector; then for the simple partial

graph with causality as discussed we can write:

 

 

 

 

 

 

 

 

 

 

- r - q - .-
Fgf 31? 812 FR? 0 3f
2 a " 000 (l)
e -sT s o o f
:9] _ 12 P] _ 1, :9.
Also we have for the storage elements:
-1
Ef a I ‘p ... (2)
And for resistances adjacent to partial points:
9,6 ’ Rp Ep (3)

By substituting (3) into the equation of 2p and then into pf and

knowing that p_- ef , we obtain the-state matrix A:

1321819

-1 T -l
and A 3 [(SF - RF) + S (SE, - RP) $12] [I ]

12

148

APPENDIX 9

 

Lower Bounds on Largest Eiggnvalues for General Graphs

Then:

and

and

The obtained graph will have smaller b

Let G be a general graph with N points.
Let S (G) be its skew symmetric adjacency matrix.
Let bl(S(G)) be its largest eigenvalue.

Let buCO be the largest eigenvalue of an odd power cycle

N
having N points.
Let buCe be the largest eigenvalue of an even power cycle
N

having N points.

If N/2 is odd

2cos N a b e < b (G)
N uCN 1
If N/2 is even
2 cos I a b 0 < b (G)
N uCN 1
If N is odd
5 cos 1' = tom’s):1 (G)
N+1
Proof:

Arrange all graphs into two classes:

1) All trees with N points, and all optimal graphs with N
points.

2) Graphs that are not optimal.

Now delete a line from a graph belonging to the first class.

1. Classify the obtained graph

according to whether it is optimal or not. If it is optimal we can

149

proceed with deleting a line. The minimal connected graph resulting
from repeating this operation is a tree, and from results in appendix 1

and Cvetkovic (BGZ, p73), the graph with smallest b is the path. In

1

the second class, deleting a line will either produce a graph of the

first class with bl larger than the original (because of continuity

property of the eigenvalues as function of parameters on the line of
the graph), or will produce a graph of the second class with smaller

b The first case was discussed above. The minimal connected graph

1.
obtained if the second case continues to happen is the cycle with

bl - 2 cos 3. From properties of cycles presented in Chapter III, in
N

Table III.1, we conclude the hypothesis.

150

APPENDIX 10

 

Bounds on Largest Eigenvalue Using Subgraphs

or

and

Let G be a point graph with all its points being full;:
let A be its skew symmetric adjacency matrix,

let G , G

1 . . be subgraphs of G obtained by a certain

2 O
dissection,

let Ab be the largest boundary degree in the subgraphs otained,

let AB be the NxN block diagonal matrix with its diagonal

blocks being the skew symmetric adjacency matrices of

the subgraphs G1, G2, . . .

let the matrix C be such that

CSA‘AB’

and let b1(.) denote the largest eigenvalue of skew symmetric

adjacency matrices, then

bl(G) _<_bl(Gl) + 161m) (1)
b(G)<b(G)+Ab (2)
1 - 1 1

161ml) 5161(6) (3)

Proof:

 

The Lower Bound (inequality 3)

From the definition of dissection, G has at least one point

1

less than G. Thus, the skew symmetric adjacency matrix of G is a

l

principle submatrix of the skew symmetric adjacency matrix of G. Then

by the use of the theorem of interlacing of the eigenvalues of principal

151

submatrices, (Theorem 2, Chapter II.4), and using property (2) for

skew symmetric matrices, (Chapter II.4), we obtain the lower bound.
The Upper Bound

We have

A = AB + C

and the eigenvalues of A interlace with the sum of the eigenvalues of
B
A and C, and

bl(A) §_bl(AB) + b1(C)

Using Gerschgorin theorem on matrix C and knowing that the largest row
sum in C is Ab, we get

b
<

and bl(AB) a b1(Gl) by definition

and thus we conclude

b
b1(A) 5.bl(Gl) + A

Note: 1. The lower bound given in the inequality 3 is weaker than
the equivalent lower bound for the symmetric adjacency
matrix. This is due to the fact that the latter was
based on Frobenius-Perron theorem for non-negative ma-
trices (GT2) which apply to the symmetric adjacency
matrix but not the skew symmetric case (cf.II.3.2.).

2. An application of a result given by Slepian and Landaw

in (NA7) would give the bound

 

b (G) < (b (G’) +\/ (b (G’))2 + 46 ))
l - l l
2

 

where G’ is the subgraph obtained from G by deleting only one point with

degree 6 .

152

APPENDIX 11

ngimal Graphs

Let G1 and G2 be two optimal point graphs, then the point graph

obtained from their direct sum, G a G + G2’ is an optimal graph and

l

b1(G) = bl(Gl) + b2(G2) ... (1)

Proof:

If A(G) is the skew symmetric adjacency matrix of the point
graph G, then using the theorem given in (LAS), and used in (GT2) for

giving the same result for symetric adjacency, we obtain
A(G) . A(Gl) ® 12 + 11 ® A(Gz) (2)

where I I are identity matrices of the same order as A(Gl) and

l’ 2
M62) and ® is the Kronkner product, then

b.(G) = b.(G ) + b.(G ) (LAS)... (3)
i i l i 2
Now the matrix A(G) can be written as

A(G) = A32 + C

where AB2 is a block diagonal matrix with all its block diagonal
matrices are A(Gz), and C is as defined in the previous proof.

1 a
Let A(G ) 8 A32 + C

where C’ is different from C by changing in G the power direction on
one or more lines or deleting one or more lines.
New from the theorem of interlacing of the eigenvalues of the

sum of matrices (cf.II.4, Theorem 4), we have

153

) J
bl(G 15610182) + bl(C ).

Now the matrix C ; A(Gl) ® I2, is similar to a diagonal matrix whose
diagonals blocks are the skew symmetric adjacency matrix A(Gl) and
C’ will also be a block diagonal with its diagonal blocks the same as

for C except for the changes. If G is an optimal graph, then

1

bl(C’) _<_ b(C)

J
and bl(G ) _<_ 131(6)

The same proof is repeated for G as an optimal graph.

2

R. B. ROSENBERG

Associate Professor.

Oapartmant of Machanical Englnaaring.
Michigan Stats Univarsity, East

' Lansing. Mich.

language
I). C. KARROPP

Protassor, Dapartrnant of
Mechanical Englnaarlng, Unlvarslty of
California. Davis. Cam.

lntrod uctlon

In purpose of this paper is to pruanttha basic
dafinitions of the bond graph language in a compact but general

form. The language presented herein is a formal mathematical .

system of definitions and symbolism. The descriptive names
are stated in terms related to energy and power, bacausc that is
the historical basis of the multiport concept.

It '3 important that the fundamental definitions of the lan-
guage be standardized because an increasing number of people
around the world are using and developing the bond graph
language as a modeling tool in relation to multiport systems.
A mmmon set of reference definitions will ha an aid to all in
promoting case of communication.

Some care has been taken from the start to construct defini-
tions and notation which are helpful in communicating with
digital computers through special programs, such as ENPORT

[51.l It is hoped that any subsequent modifications and extan- °

siom to the language will give due consideration to this goal.
Principal sources of extended descriptions of the language and
physical . applications and interpretations will be found in
Paynter (ll, Karnopp and Rosenberg [2, 3], and Takahashi, at
al. [41. This paper is the most highly codified version of language
definition, drawing as it does upon all previous cflorts.

Basic Definitions

Maltlport filaments. Ports, and Bands. Mufliport elements are
the nodes of the graph, and are dasignated by alpha-numeric
characters. They are referred to as elements, for convenience.
For example, in Fig. 1(a) two multiport elements, 1 and R, are
shown. Paris of a multiport element are dasignatcd by line

 

members in brackats daaignata Ralaranm at and of papar.

Cambutad by tho Automatic Control Division for publication (without
presentation) in tha Jonas“. or Dunno Smsua, Mucous-1m. ass
Courses. Manuscript racslvad at ASME Hoadquartara. May 9, 1972. Paper
No. TZ-Aut-T.

154

APPENDIX 1 2

A Definition of the Band Graph

sagmcntaincidantonthsclamsntatonaand. Portaaraplacaa
wharathaalcmcntfcanintaract with its environment '

For example, in Fig. 1(1)) the l clamant has three ports and
thaRelomenthssoncpor-t. Waaay thattha 1clcmcnt‘na3—
port, and the R element is a l-port.

Bonds are formed when pairs of ports are joined. Thus bonds
are connections between pairs of multiport elements.

For example, in Fig. "1(a) two ports have Man joined, forming
abondbctwcentha l andthaR.

load Graphs. A bond graph is a collection of multiport
elements bonded together. In the general sense it is a linear
graph whose nodes are multiport elements and whose branches
are bonds.

’ A bond graph may have one part or several parts, may have
no loops or several loops, and in general has the characteristics
of any linear graph.

An example of a bond graph is given in Fig. 2. In part (a) a
bond graph with seven elements and six bonds is shown. In
part(b) thasamographhashadits powers dircctadandbonds
labeled.

Abondgmphfmgmauisabondgraphnotallofwhoscports
have been paired as bonds.

An example of a bond graph fragment is given in Fig. 1(a),
which has one bond and two open, or unconnccmd, ports. ,

Poi-Warlocks. Associated with a given port are three direct
and three integral quantities.

Efl'orl, e(t), and flow, f(t), are directly associated with a given
port, and are called the port power variables. They are assumed
to be scalar functions of an independent variable (t).

Power, P0), is found directly from the scalar product of chart
and flow, as

1’0) - e(l)'f(‘)~

The direction of positive power is indicated by a half-arrow on
the bond.

Momentum, 11(1), and displacement, q(l), are related to the
effort and flow at a port by integral relations. That is,

(a) (b) (C)

Fig. 1 Multiport elements. ports. and hands: (a) two multiport
elements; (is) the elements and their parts: (c) formation of a bond
R

R
l 1‘
l 3 u
SE—‘i—VTF—Tl 6
I J
C

(a) (b)

Fig. 2 An example of a bond graphs (a) a bond graph: (h) the bend
graph with powers directed and bends labeled

at) - pa.) 4- [I «max

and q(t) - 9“.) + 1:: f(h)dh, mpecn'vely.

Momentum and displacement are sometimes referred to as
energy variables.
Energy, EU), is related to the power at a port by

re) - Ea.) + f.I mm

The quantity 3“) - 3(a) represents the net energy transferred
through the port in the direction of the half-arrow (i.e., positive
power) over the interval (a, l). '

In common bond graph usage the efi’ort and the flow are often
shown explicitly next to the port (or bond). The power, dis-
placement, momentum, and energy quantities are all implied.

Basic Multlpert laments. There are nine basic multiport
elements, grouped into four categories according to their energy
characteristics. These elements and their definitions are sum-
marized in Fig. 3.

Sources.
Source of efort, written SE _e_, '5 defined by e :- e(t).
Source offlow, written SF_fz ..is defined by f - f(t).

Storages.

Capacitance, written 5. C, is defined by

. - on) and 9(1) =- an.) + f.I f(kldk.

That is, the effort is a static function of 'the displacement and
the displacement is the time integral of the flow.

Inertance, written; I , is defined by

f are») _and no - pa.) + f.I c(h)dh.

That is, the flow is a static function of the momentum and the
momentum is the time integral of the effort.

Dissipation.

Resistance, written; R, is defined by
‘Me, I) - 0.

130/SEPTEMBER19721

SYMBOL CEF in: ‘.' ! ON MAN!
.I.- ———’— _
SE—é—y e - e(t) source of cffOrx
5;__f_., f ' f(t) source of flow
Cl-—:-- e ' 0(a) capacitance
e(t) - qit°)+ {f-dt
I‘---%— f 8 0(p) inertanca
p(tl-p(t°)+ re-dt
R‘-§——— Me,” - 0 resistance
l 2
-—;TF——-p e1 - ill-e2 transfcmer
l:m
l'll fl - f2
l 2
firm—.7 .l m r f2 gyrator
f
32 I r.f‘

col-Von effort

2 junction
f‘ + f2 - f3 I 0
l
_.,I._.L_, f| - f2 e f3 cannot-.31”
2 o June..on

1 e‘4-sz-e3

Fig. 3 Definitions of the basic multiport elements

Thatis, astaticrelationexistsbetween theefi'ortandfiofatthe
port.

Junctions: Z-Port.

Transformer, written :7: TF’ 197:, is a linear 2-port elegant de-
fined by
e. =- we.
WI: " ft.

and

where m is the'modulus.

Gyroior, written 2 GY 93, is a linear 2-port element :‘efined
I 3
by
e; =- r-f,

and. 3! “'rfihs

where r is the modulus.
Both the transformer and gyrator preserve power (1.2.. P; -
P2 in each case shown), and they must each have two guns, so

they are called essential 2-port junctions.
Junctions: 3-Port.

. 1 3
Common efi'orl junction, wntten —7 O —7

2’]

is a linear 3-port element defined by
er a e. =- e. (comma: eiort)

fi‘i'fs "fs " 0-

Other names for this element are the flow junctio:

'(flow stzzstion)

ad the

and

Transactions of the .LSME

l 3
___7l—7s

2?

zero junction. Common flow junclion, written

is a linear 3-port element defined by .
fl " f: 8 f: (common flow)
and P: + e. — r. a 0. (short. summation)

Other names for this element are the efl'or: junction and the our
junction. ‘

Both the common effort junction and the common flow junc-
tion preserve power (i.e., the net power in is zero at all times).
so they are called junctions. If the reference power directions
are changed the signs on the summation relation must change
accordingly.

Extended Definitions -
Inltiport Fields .
Storage Fields. Multiporf capacitance, or-C-fiefds, are written

—-l-7C (2— , and characterized by

2’1"

6; =- filings,“ (1.),3' - lion,

and q.-(t) - (Mic) + 1:: fr(}\)d)\, i a l to n.

Mufti-port incriances, or I-fields, are written —-l—7 1 V1,"!

21“
and characterized by
is - 4’60!» Pa, ..

ma) - ma.) + .I «(mm -.1 to ...

.p.),i-lton,
and

If a C-field or I-field is to have an associated “energy" state
function then certain integrability conditions must be met by
the <1); functions. In multiport terms the relations given in the
foregoing are suficient to define a C-field and I -field, respectively.

Mixed multiport storage fields can arise when both C and I-
type storage effects are present simultaneously. The symbol for
such an element consists of a set of 0’s and ['3 with appropriate
ports indicated.

For example, —l-7 IC’I e—a— indicates the existence of a set
’12
of relations
ft ‘ <l’iO’l- (It: P3).
c: =- ‘ifitpi. <12. Pal.
I: = 4’10’!’ th- Pa).

and
Mt) = Mi.) 4» fl: «(Md)»
rum = mu.) + flIMde.
Mt) = M.) + II «max.
Rn .....-l -t h

I] --------- ..e «seal Pnn§pnl

.lluitipm-t «lissfpnlors, or [if-fields, are written —l—7 R 41-

2 I‘s'

and are characterized by
(pi((ls ll. ‘30 2' ' ' ‘

If the R-ticld is to represent pure dissipation, then the power
function :txmcintcd with the R-field must be positive definite.

.llullr'pari junctions include 0 junctions and l - junctions with
n ports, n 2 '3. The general case for each junction is given
in the following.

eflofl) - 0’ i a [to n.

l

__704."T_ 4714—1.—
2/\ ... 2A ....
“I: an

6|-¢‘-....‘fis fr-fs"----"fn

ie-o £«-°

i-l r-r

Modulated z-Poet Junctions. The modulated transformer, or

l 100:)

MTF 2
‘7

e. - fil(8)'¢g

and "£0043 " fa.

where m(x) is a function of a set of variables, x. The modulated
transformer preserves power; i.e., P;(t) - P38).

MTF written _17 implies the realtions

7(3) i
The modulated gyrator, or MGY, written 1 MGY 2
‘7 ‘7

implies the relations

('1 - f(xj'f,

and en - f(xl'fi.

where r(x) is a function of set of variables, x. The modulated
gyrator preserves power; i.e., P10) - P30).

Junction structure. The junction structure of a bond graph is
the set of all 0, l, GY, and TF elements and their bonds and
ports. The junction structure is an apart that preserves power
(i.e., the net power in is zero). The junction structure may be
modulated (if it contains any M01": or MTF’s) or unmodulated.

For example, the junction structure of the graph in Fig. 20)) is
a 4-port element with ports 1, 2, 5, and 6 and bonds 3 and 4. It
contains the elements 0, TF, and 1. '

Physical Interpretations

The physical interpretations given in this section are very
succinctly stated. References (1], [2], and [3| contain extensive
descriptions of physical applications and the interested reader is
encouraged to consult them.

Mechanical Translation. To represent mechanical translational
phenomena we may make the following variable associations:

1 effort, e, is interpreted as force;

‘2 flow, I, is interpreted as velocity;

3 momentum, p, is interpreted as impulse-momentum;

4 displacement, q, is interpreted as mechanical displacement.

Then the basis bond graph elements have the following in-
terpretations:

1 source of effort, SE, is a force source:

'2 source of flow, SF, is a velocity source (or may be thought
of as a geometric constraint):
1 9 7 2 / 181

<FPTF'N‘RFR

3 resistance, R, represents friction and other mechanical
loss mechanisms;

4 capacitance, 0, represents potential or elastic energy
storage effects (or spring-like behavior);

5 inertance, I, represents kinetic energy storage (or mass
efl'ects);

6 transformer, TF, represents linear lever or linkage action
(motion restricted to small angles);

7 gyrator, GY, represents gryational coupling or interaction
between two ports; -

8 O-junction represents a common force coupling among the
several incident ports (or among the ports of the system bonded
to the O-junction); and

9 l-junction repraents a common velocity constraint among
the several incident ports (or among the ports of the system
bonded to the l-junction).

The extension of the interpretation to rotational mechanics
is a natural one. It is based on the following associations:

1 efi'ort, e, is associated with torque; and

2 flow, I, is associated with angular velocity.

Because the development '3 so similar to the one for translational
mechanicsitwillnotberepeatedhere.

flectrlcei Networks. In electrical networks the key step is to
interpret a port as a terminal-pair. Then variable associations
may be made as follows:

1 eiort, e, is interpreted as college;

2 fiowJ, isinterpretedaecta-rent;

3 momentum, p, is interpreted as flux linkage;

t displacement, q, is interpreted as charge.

The basic bond graph elements have the following interpret»
tions:

1 source of short, SE, is a voltage scum;

2 source of flow, SP, is a current source;

3 resistance, R, represents electrical resistance;

4 capacitance, C, represents capacitance effect (sbrpd
electric energy);

5 inertance, I, represents inductance (stored magnetic
cum);

6 transformer, TF, represents ideal transformer coupling;

7 gyrator, 61’, represents gyrational coupling;

8 O-junction represents a parallel connection of ports (com-
mon voltage across the terminal pairs); and

9 l-junction represents a series connection of ports (common
current through the terminal pairs).

Hydraulic Circuits. For fluid systems in which the significant
fluid power is given as the product of pressure times volume
flow, the following variable associations‘are useful:

1 efl’ort, e, is interpreted as prmure;

2 flow, I, is interpreted as volume flow.

3 momentum, p, is interpreted as pressure-momentum;

4 displacement, q, is interpreted as volume.

The basic bond graph elements have the following interpreta-
tions:

1 source of short, SE, is a pressure source;

2. source of flow, Si", is a volume flow source;

132/SEPTEMBER 1972

3 resistance, R, represents loss effects (e.g., due-to leakage,
valves, orifices, etc);

4 capacitance, 0, represents accumulation or tank-like efl'ecis
(head storage);

5 inertance, 1, represents slug-flow inertia effects;

6 O-junction represents a set of ports having a common
pressure (as. : pipe we): .

7 l-junction represents a set of ports having a common
volume flow (i.e., series).

Other interpretations. This brief listing of physical interpret»
tions of bond graph elements is restricted to the simplest, most
direct, applications. Such applications came first by virtue of
historical development, and they are a natural point of de-
parture for most classically trained scientists and engineers.
As referencm [1-4] and the special issue collection in the
Jonson. or DYNAMIC Stat-sits, Mancunian, ano Con-
nor. TRANS. ASME, Sept. 1972, indicate, bond graph elements
can be und to describe an amazingly rich variety of complex
dynamic systems. The limits of applicability are not bound by
energy and power in the sense of physics; they include any ,.
areas in which there exist useful analogous quantitiestdenergy.

Concluding Remarks

In this brief definition of the bond graph language two im-
portant concepts have been omitted. The first is the concept of
bond activation, in which one of the two power variables is sup-
pressed, producing a pure signal coupling in place of the bond.
Th'n is very useful modeling device in active systems. Furthc
discussion of activation will be found in reference [3), section
2.4, as well as in references [1] and [2].

Another concept omitted from dismaion in this definitional
paperis that ofoperott'onolcausalt'ty. Itisbymeansofcausality
operations applied to bond graphs that the algebraic and dif-
ferential relations implied by the graph and its elements may be
organised and reduced to state-space form in a systematic
manner. Extensive discussion of causality will be fetmd in .
reference [3], section 3.4 and chapter 5. Systematic formulation
of relations is prmented in reference [6]. -

References

1 Paynter, H. M., Analysis and Design of Engineer-nip
Systems. M.I.T. Press, 1961.
2 KarnoppiaD. C., and Rosenberg, R. C., Analyst} and
.' it

Simulation of 'port Systems, M.I.T. Press. 1968.
3 Karnopf. D. C., and Rosenberg, R. C., “System Dy-
namics: A nified Approach,” Division of Engineering Re-

search, College of Engineering, Michigan State University, East
Lansing, Mich.. 1971.

4 Takahaski. Y., Rabins. M., and Auslander. D., Control.
.tddlisor-Wesley, Reading, Ma" 1970 (see chapter 6 in par-
ticu ar .

5 Rosenberg, R. C., “EN PORT User’s Guide." Division of
Engineering Research, College of Engineering, Michigan State
University, East Lansing, Mich.. 1972.

6 Rosenberg, R. C., “State-Space Formulation for Bond
Graph Models of Multiport Systems." JOURNAL or Drniunc
Srs'rzns, MEASUREMENT, AND Comma, TRANS. ASME. Saris
G. Vol. 93, No. 1, Mar. 1971, pp. 35-40.

Transactions of the ASME

158

LIST OF REFERENCES

BG1. R.C. Rosenberg, "On Gyrobondgraphs and Their Uses", Journ. Dyn.
Sys., Meas. and Control, March 1978, Vol. 100/76.

BG2. D. Karnopp, R. Rosenberg, "System Dynamics a Unified Approach",
JOhn Wiley & Sons, Inc., 1975.

BG3. P.E. Wellstead, “Introduction to Physical System Modeling",
Academic Press, NY, 1979.

BG4. A.S. Perelson, "Bond Graph Sign Conventions", Journ. Dyn. Sys.,
Meas. and Control, June 1975, pp. 184-188.

865. V.D. Gebben, "Bond Graph Bibliography", Franklin Inst. Journ.
16-0032/7910901-0361.

BG6. H.M. Paynter, D.C. Karnopp, "Design and Control of Multiport
Engineering Systems: Proc. of IFAV Tokyo Symposium, 1965,
pp. 443-454.

8G7. R.C. Rosenberg, D.C. Karnopp, "A Definition of the Bond Graph
Language", Journ. Dyn. Sys. Meas. and Control, Sept. 1972, 1-4.

BG8. J.N. Boyd and P.N. Raychowdhury, "A One Dimensional Crystal
With Nearest Neighbors Coupled Through Their Velocities",
Journ. Dydn. Sys. Meas. and Control, Sept. 1981, Vol. 103/293.

BG9. L.S. Bonderson, "Vector Bond Graphs Applied to One Dimensional
Distributed Systems", Journ. Dyn. Sys. Meas. and Control,
March 1975, 75-82.

GT1. F. Harary, "Graph Theory", Addison-Wesley series in mathematic,
Reading, MA, 1972.

GT2. D.M. Cvetkovic, "Spectra of Graphs, Theory and Applications",
Academic Press, NY, 1980.

GT3. W.H. Haemers, "Eigenvalue Techniques in Design and Graph Theory",
The Mathematical Center, 49, 2e Boerhaavestraar, Amsterdam.

GT4. F. Harary, "The Determinant of the Adjacency Matrix of a Graph",
SIAM Review, Vol. 4, #3, Jul; 1962 (203-209); "A Graph
Theoretic Method for the Complete Reduction of a Matrix with
a View Toward Finding its Eigenvalues", Journ. Math. Physics,

38 (1959), 104-111.

159

GT5. A.J. Schwenk and R. Wilson, "Selected Topics in Graph Theory",
Academic Press, NY, 1979.

GT6. L. Spialter, "The Atom Connectivity Matrix and its Character-
istic Polynomial", Journ. Chem. Documentation 4 (1964) 261-274.

GT7. M.K. Gill and B.D. tharya, "A Recurrence Formula for Computing
the Characteristic Polynomial of a Sigraph", Journ. Comb. Inf.,
and System Sciences, Vol. 5, #1, 68072, (1980).

GT8. Hoffman, A.J., "On Composite Matrices with (0,1,-1) Entries",
Journ. Comb. Theory A14 (1973), 302-309.

GT9. Chen W.K., "Applied Graph Theory. Graphs and Electrical
Networks", North-Holland Publ. Co., Amsterdam - London - New
York, 1971.

GT10. Kac, M., "Can one hear the Shape of a Drum?", Amer. Math.
Monthly, 73 (1966), April, Part II, 1-27.

LA1. G. Strang, "Linear Algebra and its Applications", Academic Press,
NY, 1976.

LA2. E. Nering, "Linear Algebra and Matrix Theory", Wiley, NY, 1963.

LA3. D.J. Hartfield, "Concerning the Eigenvalues of DA under
Variations of the Entries of D and A", SIAM Journ. Math. Anal.
Vol. II, No. 4, July 1980.

‘LA4. C.R. Johnson, "Eigenvalue Inequalities for Principal Submatrices",
Linear Algebra and its Applications, 37:11-22, (1981).

LAS. D.E. Rutherford, "Some Continuant Determinants Arising in
Physics and Chemistry", Proc. Royal Soc. Edin. A LXX II (229-
236) 1947.

LA6. M.H. Carpano at M. Delarche, "Approt des Techniques Graphiques
Interactives a L'Analyse Structural de Syste: mes." R.A.E.R.O.
Automatique/System Analysis and Control, Vol. 14, m:2, 1980,

p. 205-222.

LA7. Seidel, "Orthogonal Matrices with Zero Diagonal I, II, Canadian
Journ. of Math., No. 5, 1971, pp. 816-232.

NA1. Wilkinson, J.H., "The Algebraic Eigenvalue Problem", Clarendon
Press,London, 1965.

NA2. Bodewig, 8., "Matrix Calculus", North Holland Publishing Co.,
Amsterdam, 1956.

NA3. Eberlein, P.J., "On Measures of Non-Normality for Matrices",
Amer. Math. Month., 72 (1965), 995-996, (MR 32#1205).

NA4.

NAS.

NAG.

NA7.

NAB .

NA9.

NA10.

NA11.

NA12.

160

A. Vandersluis, "Gershgorin Domains for Partitioned Matrices",
Linear Algebra and its Applications, 26:265-280, 1979.

H. Wolkowiz and Styan G.P.H., "More Bounds for Eigenvalues
using Traces", Linear Algebra and its Applications, 31:1 (1980).

Henrich, P., "Bounds for Iterates, Inverse, Spectral Variation
and Fields of Values of Non-Normal Matrices", Num. Math. 4,

Slepian, D. and Landay, H., "A Note on the Eigenvalues of
Hermitian Matrices".

Todd, J., ”Basic Numerical Mathematics% Birkhauser Verlag
Basel, 1977.

Smith, G.D., "Numerical Solution of Partial Differential
Equations: Finite Difference Methods", Clarence Press,
Oxford, 1979.

Marcus, M., Mine, 8., "A Survey of Matrix Theory and Matrix
Inequalities", Allyn and Bacon, Inc., Boston, MA (1964).

H. Wolkowiz and G.P.H. Styan, "Bounds for Eigenvalues Using
Traces", Linear Appl., 29:471-506 (1980).

A.R. Amir-Moéz and A.L. Pass, "Elements of Linear Spaces",
Pergamon, Oxford, 1962.