PERFORMANCE CHAmiCTERISTECS OF A
STE“: EM #13 A FUNCTLGN OF 1T5 STRUCTURE

‘h’hesEs far tine Degree 0f Ph. D.
Mlfli‘ilfiAN STATE UNIVERSWY
Henry F. Wiiliams
3965

31-15513

 

This is to certify that the

thesis entitled

A)

(a

(1
*d
C‘
A)
[I]

presented by

flilllams

has been accepted towards fulfillment

of the requirements for

_. Fh- D0 degree in E- E-

Q

Major professor /

Date ?/N .42 2.71 /?11 5'

0-169

ABSTRACT

PERFORMANCE CHARACTERISTICS OF A SYSTEM
AS A FUNCTION OF ITS STRUCTURE

by Henry F. Williams

A system is a collection of component equations and
constraint (or graph) equations describing component inter-
connections. These two classes of equations together make
up what is called the system structure. A solution to the
system is a function that satisfies the system equations.
This thesis examines the solution characteristics of exis—
tence, uniqueness, and stability, as they relate to the sys-
tem structure.

Grassman Algebra and Matroid Theory provide the
principal mathematical tools by which the results are ob-
tained.

The principal results are:

l. A theorem providing necessary and sufficient
conditions for a linear monotonic System of n-
port components to have a unique solution;

2. A generalization of system theory to Hilbert

Spaces with two existence theorems;

Henry F. Williams

The most general existence and uniqueness theorem
yet published for non-linear n-port component
systems;

Explicit relations between system structure and
stability of its solutions for a wide variety of
systems;

The determination of algorithms for the system
determinants of linear time-invariant systems.
These algorithms show explicitly in one equation
the relation between the system determinant and
structure;

The algorithms in (5) also show the usefulness
of Grassman Algebra in a new, simplified, and

generalized topological analysis technique.

PERFORMANCE CHARACTERISTICS OF A SYSTEM
AS A FUNCTION OF ITS STRUCTURE

By, 3..

.\"'
\ 1‘

p (“J
Henry PX Williams

A THESIS

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

DOCTOR OF PHILOSOPHY
Department of Electrical Engineering

1965

ACKNOWLEDGMENTS

The author wishes to thank Dr. H. E. Koenig for
his constant encouragement and guidance and Dr. J. 5.
Frame for his inSpiration and suggestions.
He also wishes to thank the National Science
Foundation under whose auspices this research was done.
Finally, he wishes to thank his wife, Kathy, without

whose help and consent this would not have been possible.

*****

ii

TABLE OF CONTENTS

Chapter Page
I. INTRODUCTION . . . . . . . . . . . . . . . . . 1

II. MATHEMATICAL PRELIMINARIES . . . . . . . . . . 4
Part I. Grassman Algebra . . . . . . 5

Part II. Linear Graphs and Matroids . . . 35
Part;III. Components and Systems . . . . . 65

III. UNIQUENESS AND EXISTENCE OF A SOLUTION . . . . 70

Part I. Linear Systems . . . . . . . . . 71

Introduction . . . . 71

Existence and Uniqueness Theorems . . 79

Algorithms . . . . . . . . . . 101

Part II. Nonlinear Systems . . . . 123
Existence Theorems for Systems of

Type (3) Components . . . 129

Existence Theorems for Systems of
Type (1) Components . . . . . . . . 140

Conclusion . . . . . . . . . . . . . . . . 149
IV. STABILITY STUDIES OF SYSTEM SOLUTIONS . . . . 151
Part I. Linear Systems . . . . . . . . . 154
Part II. Nonlinear Systems . . . . . . . 182
Conclusion . . . . . . . . . . . . . . . . 190

V. APPLICATIONS AND EXAMPLES . . . . . . . . . . 192
Part I. Application of Grassman Algebra

to Topological Analysis . . . . . . 192

The General Transfer Function . . . . 195

The Classical Methods . . . . . . . . 204
Part 11. Examples

VI. SUMMARY . . . . . . . . . . . . . . . . . . . 214
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . 216

iii

LIST OF APPENDICES

Appendix Page
A. On Positive Definite and Semidefinite

Matrices . . . . . . . . . . . . . . . . . 220

'8. Nonlinear Mappings in Hilbert Space . . . . 235

iv

CHAPTER I

INTRODUCTION

Modern system theory can be described as the disci-
pline which seeks to determine the performance characteris-
tics of interconnected components from a knowledge of their
patterns of interconnection and component characteristics.
In lumped parameter system theory where a finite number of
components are interconnected, the circuit and cutset equa-
tions obtained from a linear graph, adequately describe the
interconnections of components. The components themselves
are described by a set of equations relating the thru and
across variables [FR-1]. These component equations may be
algebraic, integral, differential, or of the functional

analysis type.

Some performance characteristics that are frequently

examined are existence and uniqueness of a solution, stabil-

ity, optimization with reSpect to some criteria, or for

linear systems, location of characteristic frequencies.

This thesis examines the performance characteristics

of existence, uniqueness and stability of a solution as a
direct function of the system structure - namely the compo-

nent equations and their pattern of interconnection.

Various authors have examined system existence and
uniqueness, but in a much more restrictive sense than that
used in this thesis. (See [DU-l], [DU-2], [DU-3], [DU-4],
[BI-l], [MI-l], [WI-1], [DE-1].) For instance, no one, to
the author‘s knowledge, has given a theorem similar to
Theorem 3-1-3 which essentially reduces the problem of exis-
tence and uniqueness to that of a subset of the component
equations.

Previous stability studies have been mostly restricted
to the use of energy functions or analysis of state models
which give little Specific information regarding system
structure. However this thesis emphasizes this aSpect of the
system's problem as it relates to both the system analysis
and synthesis.

In linear systems, the algorithms of Chapters III and
V provide very useful equations relating system structure to
network functions and determinants. These results provide a
usefulbasis for realizing a best fit to a desired system
reSponse in terms of either the parameters in the component
equations or alteration of the component interconnections.

The techniques are also novel in as much as they, for
the first time, make extensive use of Grassman algebra and
matroid theory in examining performance characteristics.

In Chapter II, various preliminary concepts regarding

matroid theory, Grassman algebra, component equations and

graph theory are explained and some original theoretical
results for use in the remainder are derived.

Chapter III examines how the property of existence
and uniqueness of a solution affects the interconnections of
a given set of components. First the linear time-stationary
systems are examined. Methods are devised which give the
class of all interconnections that yield a unique solution.
Several necessary and sufficient conditions are given for
restricted classes of components to have a unique solution.
The same problem is then formulated for the non-linear sys-
tems, including mappings in Hilbert Space. Some Sufficient
conditions on the topology for a unique solution are given.

Chapter IV contains results on stability. Here
various types of stability of systems of components are
examined from the standpoint of the central problem: namely,
given a collection of components, determine the class of
interconnections that yield a stable solution. Again both
linear and non-linear equations are examined, and the results
given in the theorems shed light on the stability problem.

Chapter V applies the results of Chapters III and IV,
to several examples and shows the usefulness and generality
of the Grassman algebra technique over classical topological

analysis techniques.

CHAPTER II

MATHEMATICAL PRELIMINARIES

The purpose of Chapter II is to define the pertinent
notation for linear graphs and components,and to provide a
characterization of the cutset and circuit Space of a graph.
The unstarred theorems and lemmas herein proved are the

author's original results. However, Theorem 2-2-12 and the

 

techniques of Grassman algebra are not to determine whether

a given vector subSpace is graphic. The construction method
described in [TU-5] is much simpler and straightforward for
this purpose. These are derived and used for the purpose of
describing graphic vector subSpaces. They are also used in
Chapter III.

Theorem 2-1-6 is a new result in the theory of

 

Grassman algebra and useful in the algorithm of Chapter III.
Grassman algebra has a direct practical application in topo-
logical analysis as described in Chapter V.

The rather extensive discussion on matroid theory is
given to provide mathematical foundation for the application
of Tuttes matroid results to real vector Spaces. To the
author's knowledge this foundation is missing from the liter-
ature and is accomplished here for the first time. Tuttes
concepts of chains of integers have been extended to chains

4

of real numbers and the concept of a chain group to a chain
vector space. However, many of Tuttes results carried over
intact in this extension.

In passing, it should be mentioned that theorems on
graphic (mod 2) vector Spaces which follow directly from
Tuttes results, are given without proof in [SE-l] and [KI-1].
A more precise and practical statement of the conditions on

Kuratowski matroid minors is given in this thesis.

Part I. Grassman Algebra

 

Definition 2-1-1: A linear algebra over a field F is a

 

set which is a finite dimensional vector space over F and
which admits an associative and bi-linear multiplication.

Definition 2-1-2: A linear algebra G over a field P which

 

contains the finite dimensional vector space V over F is
a Grassman Algebra over V if

1. G contains a multiplicative identity element, eo

G is generated by eo and V

2

. . 2._
3. If x 15 1n V, x -O
4

The dimension of G (as a vector Space) is 2n.

(n = dimension V).

 

The associative multiplication of the algebra will

be called progressive multiplication.

 

Lemma 2-1-1: If g, xEV, then xg=-gx.

Proof: (x + g)€ V, (x + g)2 = x2 + gx + xg + g2 = 0

But x2 = g2 = 0, therefore gx = -xg.

 

*Lemma 2-1-2: Any two Grassman algebras G and G1 over

the same vector Space V are isomorphic.

Proof: See [MAC-1].

 

Let G be any Grassman algebra over V. G con-

tains a unique identity element eO and all its scalar
multiples aeo. Identify each scalar aE F with the corre-
Sponding multiples an, therefore eO = 1.

(Throughout the rest of this thesis, assume F is the real

numbers.)

e for V. Then

Select any ordered basis el,..., n

G contains all products of the various ei's. If P =
(i1,...ip) is a set of indices (a subset of (l,...,n),
arranged in increasing order), write

8P 2 [eil eiZ ... eip] (2-1-1)

Since eiév, e- = 0, e- 1- Using
these rules any product of e's can be arranged so that
it either has the form (2-1-1) with increasing subscripts
or is zero. Since any vector of V is a linear combina-
tion of the basis elements, it follows by the distrib-

utive law that any product of vectors of V is a linear

combination of the elements eP. Since G is generated by
eO and V, it follows by distributivity that G is spanned
by the elements eP, for P a subset of (l,...,n), But

this has 2n subsets and G has exactly the dimension 2n

so these elements are linearly independent and are a basis

for G.

*Theorem 2-1-1: The vectors u1,...,ut in V are linearly
independent if and only if their product [ul ... ut] in

the Grassman algebra G over V is not zero.

Proof: After [MAC—1]. If the vectors are independent, they

may be used as part of a basis
e of V.

The product [p1 ... vi] = [kl ... et] 15 then one of the
vectors in the basis eP of G, hence is not zero.

Conversely, if u1,...,u are dependent, then some

t

ui is a linear combination of the others so the product con—

sists of t-l terms each with a repeated factor, hence is zero.

 

Definition 2-1-3: A form of degree 0 is a scalar multiple of

 

 

the identity. A form of degree p (expressed d(g)=p) is an
element gEEG which can be expressed as a sum of products
[pl ... ué] with factors ui in V. A form of degree p

that is a product of p of the chosen basis vectors of V,

is called a basic form of degree p. A basic form of degree

 

l is called a basic unity. It was shown above that the basic

 

forms of degree p are independent. A linear combination of

a set of basic forms is called a canonical form, if each

 

basic form is ordered as in equation (2-1-1).

 

Example: Let e1, e2, and e3 be a baS1s for R3

(the real Euclidean Space of dimension 3). Then 1, e1, e2,

e3, e1e3, e2e3, ele2, ele2e3, are a ba51s for G, ele3 15

a basic form of degree 2, and e is a basic unity,

l
+ + . . .
ele2 ele3 eleZe3 1s a canon1ca1 form, ele2+ele3 15 a
canonical form of degree 2.
By the distributive law, it follows that any form of
degree p can be written as a linear combination of basic

forms of degree p. Notice that O is a form of degree p

for any p.

 

Definition 2-1-4: A simple form is a form that can be

 

expressed as a product of vectors in V. A simple form is

sometimes called an outer product.

Definition 2-1-5:' Two forms A and B of degree p are

equivalent if, and only if, there exists a scalar c f O

 

such that A = CB.

*Theorem 2-1-2: Two sets of p independent vectors

 

51,...,sp and tl,...,tp Span the same subSpace of V, if

and only if there exists a scalar c f 0 such that for

T: [t1 tp], S = [51 Sp], T = cS, i.e. they are

equivalent.
Proof: If the factors of T and of S span the same sub-
Space then

p .
t- =‘z a.1 S- for 1 j i j p.

J J J ‘l . . . .l I C

since every nonvanishing term in the product will be a permu—

tation of S. By Theorem 2-1-1,
c # 0 since T # 0.

Conversely suppose T = CS, c % 0. If some ti is

then O = [T ti] = c S ti # O

not dependent on 51 ... sp,
by Theorem 2-1—1. Therefore all ti are linear combinations
Of the Si.

 

By Theorem 2-1-2, any subspace of V is defined by
an equivalent simple form in G. By the distributive law,

any simple form in G can be written as the sum of a set of

10

basic forms. Let

Oil-7T=[ql qm] = 12d. eP

where the e are each of the basic forms of degree

Pi

 

I1
m

 

m in G. By definition :2 di eP. is a canonical form.
~ 1
1

The relation between the qi and the ei in V can be
written in matrix notation as Q = KE, where Q is the
column vector with components qi, E is the column vector
with components ei (the distinguished basis for V), and K,
mxn, is a change of basis matrix (see [BI-1], P. 244). Let
K(i) be the square matrix consisting of the (il,...,im)

columns of K in order. If eP, =
1

'0'

i1 eim] , then

di = det K(i). (2-1-2)

This follows directly from the definition of determinant and
outer product [PO-l], [MAC-1].

‘ From the above, the co-ordinates di of a simple
canonical form’fl'are the determinants of maximum rank sub-
matrices of the matrix K taking the chosen canonical basis
E into a basis Q for the subSpace represented by the form.
Therefore, the determinants of the maximum rank submatrices
of the matrix 'K uniquely determine the subSpace spanned

by 'Q, since they determine an equivalent simple form.

11

Definition 2-1-6: A subspace in V is just if it has a

 

canonical product whose co—ordinates di are restricted to

the values

di = +d, -d, O all i. (d = real number).

The rule for going from an outer product (in G) of
an arbitrary subSpace to the outer product of its orthogonal
complement is extremely simple and is stated below.

Here assume that the chosen canonical basis for V

is an orthogonal set.

Theorem 2-1-3: If a subspace V1 of V has a canonical

 

outer product 7732 di [ei ei ], then an outer product
. i 1 m
of V1' (the orthogonal complement of V1) is

m
1 .

o l J
- J: O .
ii di ( 1) [€1m+l o o o eln]

w'th e- ... - d ' 'n d .
1 {:¥m+l eln] arrange 1n ascend1 g or er

Proof: Consider the matrix:

U A

-AT ’U (1)
which is the echelon matrix of a subspace and its orthogonal
complement. The first set of rows represents a basis for
the subSpace. Premultiplying (l) by

U 0

AT U (2)

12

obtain

U A
(3)

o U+ATA

Therefore, the determinant of (l) is the determinant of

(U+AT A). But:

(—AT U) -A) = (U+AT A) (4)

U

 

Expanding (4) by the Cauchy-Binet Theorem [HO—l] shows that
the determinant of (1) is equal to the sum of the squared

max1mum rank minors M(k) (l) of

(-AT U)

2 (5)

T =
det. (U+A A) 214(k) (I)

where (k) represents a sequence of rows, (1) a sequence of
columns of (5). Expanding (1) by the Laplace expansion

[HO-l] about the first partitioned set of rows shows that

det. (U+AT A) =2<-1)z<i> *(J') M (6)

(i)(j) M(k)(l)

where M(i)(j) is a minor of (U A) and M(k)([) is the

complementary minor of (--AT U).

Similarly,

2 z T = T
2M(i)(j) det. (U+AA) det. (U+A A) (7)

and

l3

det. (U+A AT) = Z(-1) ERNM) M (8)

<k><() M<i><j>
and

200+“) Z<i>+<j) (9)

<-1) = <-l>
Let x be the p-tuple 0f the M(i)(j)

Let y be the p-tuple of the complementary M(k)([)

Let (x,y) be their Euclidean inner product

Z<k>+<£>
Let 2 be the p-tuple of the (-l) M(k)(1)
Obviously, (2,2) = (y,y).
From (5), (6), (7), and (8)
(x x) = (y y) = E(-1) Sikh“) M M -
’ ’ (k)(£) (i)(j)
(10)

= (2,X) = (2,2).
Therefore, (x-z, x-z) = (x,x) + (2,2) - 2(x,z) = O (11)
Therefore, x = z

and

= 2(i)+(j)
M(k)(£) (‘1) M(i)(j) (12)

Since we do not wish to choose particular bases for V1 and

Vi, we have for arbitrary bases

14

2(1) _ :(j)
(‘1) C M<k><i> ‘ (‘1) M(i)(j) (13)

but c(-l) 2X1) is a constant independent of the columns
of [D 1.
Choose the representative matrix of the orthogonal

complement of V1 to have the minors

(i)(j)
Since the coefficients of an outer product of Vi
are M(k)([) and those of V1 are M(i)(j) we have for

an outer product of Vi:

.2 1)
Edi (*1) J_l Iveim-t-l ... Bin] (15)
l

 

Example: Consider the example given after definition

(2-1-3). The subSpace represented by the change of basis

 

 

matrix 1 1 O

K:

1 O l ,

-811
with E = e2 has el+e2, el+e3 as a basis. Hence, its

e

L31
canonical outer product is e2 e3 - e1 e2 + e1 e3. The CO—
efficient l, of e e is the determinant of the second and

2 3

15

third columns. The coefficients of other columns are their
reSpective determinants. The outer product of the orthogonal
complement of the subSpace is -el-+e3‘+e2, where E is

taken to be an orthogonal basis.

 

Definition 2—1—7: If En = e1 ... en is a basic form of
degree n on the n-dimensional vector Space V, then [ :]o
is a mapping from the basic forms of degree n into the

real numbers, such that

1. [EDJO = 1

2. If En1 = P(En) is a basic form that is a permu—
tation of the factors of En, then Enl is an
outer product and [EHIJO = (sgn P) [EnJO where
(sgn P) is the Sign of the permutation P. (See

[MAC-1], [BI—1] ).

If Em is a basic form of degree m then {Em} is
used to denote the set of basic unities in the outer product
.Em.

If A is any Simple form of degree n then the
mapping [ :] is defined as follows:

0

1. if A=O,
We”)

2. if A #’0, A = c En where c #'O and c is
real, since En is the only linearly indepen-

dent form of degree n (See [MAC-ll ) and

16

[A] O = c.

Definition 2-1-8: If E is any basic form, the supplement

 

of E (denoted by/E) is:
/E = [E E'] E',
o

where the factors of E' are all of the basis vectors,
e1,...,en which do not appear in E, (arranged in any order),

each taken just once.

Def1n1t1on 2-1-9: If A = kl El + ...+kr Er where El,...,E

are basic forms of degree m and ki is a real number, for

r

 

each i, then

/A : k1 /El + ... + kr /Er’

From Theorem 2-1-3 , above, and the definition of
supplement it can be shown that if A is the outer product
of a subspace, then /A is an outer product of the orthogonal
complement of A. In fact, by the distributive law for sup—
plements and Theorem 2-1-3 , it suffices to show this for
the basic forms. If E is a basic form /E = [E E1] 0 E'
'where E' is the complement of E. It suffices to take
bomb E and E' in increasing order since all other orders

differ from this by the Sign of permutation. By Theorem

2—1- ' = - . l: . .
3 , if E [e11 ... elmJ, E [e1m+l ... elm]

aI‘I‘anged in ascending order the orthogonal complement of E is

17

z i. :ij

'=1 .1 .
(-1) J 6- ... e- = (—l)J E‘.
1m+1 1n
The assertion is established when it is Shown that EB Bi

me
213'

= c (-1) 3:1 (where c is an arbitrary constant). Now

0

the number of transpositions required to put ei into its
m

proper position in E' is im - m. The number of transposi—

tions to put ei 1 into its proper position, is im-l - m+l.

o o ‘ _ (im—m)+(im-l-m+l) 00.
By induction EE'Eilo — (-1) [e1 ... en]o
m m
:ij-m2+m(m-l) Z i.

so [13 Bil '= (-1) 3:1 2 = c (4)3"?1 J.
o

(where (c = +1 or -1) and is a function only of m.)
Therefore, /E is an outer product of an orthogonal comple-
ment of E. By the distributive law for supplements and
Theorem 2-1-3, /A is the orthogonal complement of A.

Now in addition to the 3 operations of algebra given
in definition 2-1—2, we add a fourth operation, called a
regressive multiplication (as Opposed to the "progressive"
multiplication). From now on, let E be the unique basic
form of degree n, with the basis elements of“ V arranged
inincreasing order. Progressive multiplication is denoted
by simple brackets with no subscript, (i.e.:[: J), and

regressive multiplication is denoted by simple brackets with

the subscript l, (i.e.: [ J1).

18

Definition 2-1-10: The regressive outer product, [‘ J1, of
two basic forms E1 and E0 of degree m and k respec-

tively, where m + k > n, is:

(1) If {51} u {so} = {a}

(a. 12.1. 1» [elven].

E (sgn P) [E1 E2] 0 E3

where d(El) 4' d(EZ) = d(E) and {E1} U {E2} ={E},and
(sgn P) is the sign of the permutation P, taking E0 into

(E3 22).

(2) If {E1} U {E0} 7! {E} , [El EO]1EO

the regressive outer product is defined for arbitrary forms

I

by the distributive law.

 

Example: Consider the example given after definition
(2-1-3). The supplement of e1 e2 is, by definition (2-1-8),
[e1 e2 e3] e3 = e3. The supplement of 5 e1 e2 + e1 e3 is,

o
by def1n1t1on (2-1-9), 5 [%1 e2 e3]0 e3-+[el e3 eéJO e2 =
5 e3 - [e1 e2 e3] 0 e2 = 5 e3 - e2. The regressive outer
product of [e1 e3 and [e2 e1] is, by definition (2-1-10),

[[81 e3] [82 El] 1 = ('1) [[61 e3] [e1 e2]:[ 1 =

= {-1) [81 e3 e210 el = (+1) [e1 e2 e310 {-31 = 1

 

 

......

‘.0Av -

- .
u 1
.a u
.
u .-
\
-~ .~
.. ._
\
n. ...
\' '_
.
.. _
~ _'
.. .‘
I.
¢
-¢
.'_‘(
."---
a
g
1
u
.1 ‘
u.
,
-'
._~
' .
o
g
‘-
a
s
..-
a

19

Forder [FO-l] defines a regressive outer product
(denoted [: J 2) as follows:

If d(El) + d(EO) > n, [E1 £012 is such that

/ [E1 EO]2 = [/131 /E0] . ‘ ‘ (3)

It is now shown that this definition is equivalent to (2-1-10)

##-

H-..-

so that results given by Forder can be used in this thesis.

The right hand Side of (eq. 3) is the usual progres-
sive outer product. Therefore, the regressive outer product
is well defined by (eq. 3). By (eq. 3) and the distributive
law for progressive products and supplements, regressive

products are distributive.’ By definition (2-1-10) if
[E1 13211 7! 0, then [El E0]

where

E(sgnP) [E E] rE
1 1 2 o 3

E0 = (sgn P) [E3 E2]

It follows therefore that
/[1=.1 E0]l = (sgnP) /[[E1E2]o E3]
=(sgnP) [E E] [EE' E'
1 2O 3 3]O 3

and

‘1’.

C/El /E0] = [[131 52L 1:2] [/<ng P) [E3 132]] =
[[31 E2]O E2 (sgn P) [E3 E2 (E3 52):]0 (E3 152),] ___

(sgn P) [El E2]O [E3 122 (E3 132)]0 [£2 (£3 32):]

 

20

{ [E3132]} = {.3} ,.-...[{.,} u {(.,.,,}
{52'} n {”1339} = {E3}.

Since the sets are the same and the order of the complement

is arbitrary, let {£2 (E3 E2){] = E3'. It follows that
/ [£1 Eo]l : [/El /Eo]

If [E1E0]l =0, then {El} U {E0} 7! {E} , so

/[131 E0] =0

1

and
[/El /E0] 2 [E1 51'] 0 [E0 Eo'io [E1' 50'] = 0 °

This last result follows from the fact that

{31'} f) {130'} =( {E1} U {E0} )' 7’ {13'} =9,

where O is the null set.

Since El' and E0' have a common factor, [El' EO'] — O

and
/ EEI‘Eq]1 : [/El /E0]

Thus it is established that the definition (2-1-10) of a
regressive outer product is equivalent to the definition of
.Forder [PO-l]. However definition (2-1-10) is computation-

ally easier .

 

21

By convention, whenever referring to the product of
two basic forms (the sum of whose degrees is greater than n)

regressive multiplication is implied.

*Theorem 2-1-4: Rule of a repeated factor. If A, B, C
are any simple forms, the Sum of whose degrees is n, then
[LA 13] - [A 0]] =[ABC] A
l 0

Proof: Page 231 of [FO-l].

This theorem shows that a regressive outer product
either is a constant times the factor that is common to the
two multiplicands or is zero. The second case occurs when

the factors of A, B, and C are not independent.

 

Definition 2-1-11: A set of echelon forms for a canonical

 

form A of degree m is any set of m 'basic forms (Bi)
(i=1,...,m) of degree (n — m + l) where each has just one

factor of a distinguished non-zero term of A.

Theorem 2-1-5: An echelon basis for a subSpace of dimension
m can be obtained from a set of echelon forms by the regres-

sive multiplication

[A Bi] 1

[.4
ll
[.1
u
5

22

where A is the outer product of the subSpace of dimension

m and (Bi) are a set of echelon forms for A.

EEEQE‘ By Theorem 2-1-4 , [A Eé]l yields a vector in the
intersection of the subspace represented by A and that
represented by 51- Therefore the set EA.E£]1 is a set of
m vectors in A.

By the definition of a set of echelon forms and of
the regressive product, the distinguished term in A, when
multiplied by Bi’ gives the one common factor which appears
in no other term of the product. Since the Bi differ only
in this factor, when the distinguished term in A is multi-
plied by Ei the result is a common factor other than
[A Ei]1, j # i. From the definition of regressive product

it follows that this common factor appears in no other term

of any of the [A Bi] . This is precisely an echelon basis.
.; 1

 

Example: Consider the example given after definition
(2-1-3). The form e1 e2 + 5 e2 e3 is simple and has the set
{E1 e3, e2 eé} as a set of echelon forms for the distin-

guished term [e1 e%. Applying Theorem 2-1-5
[[61 e2 * 5 e2 e3] [61 633]] = [91 e2 e3]
1

= ...-.1 - 5 e3,[[e1 .2 + 5 e2 e3] [.2 .4]: [e1 e2 e3]0 e2+o = e2.

'e - 5 [E e e ] e
o 1 2 3 l o 3

23

Therefore the vectors, el — 5 e3, and e2, are an echelon
basis for the subSpace represented by the simple form

e1 e2 + 5 e2 e3.

 

Theorem 2-1-6: Let A be a canonical form of degree m.

 

Then A is simple if,and only if, [IA Bi] A] = O for
1
i=1 ... m-l, where (Ei)’ i=1 ... m-l, is some (m-l) of

the forms in any one set of echelon forms.

 

Wfi

Example: To illustrate Theorem 2-1-6 , consider the
Space R4 (the four dimensional real Euclidean space) and
1’ e2, e3, and e4 be a basis for it. Is the form
[E1 e2 + e3 e4] = A Simple? The set of echelon forms for

let e

the distinguished term e1 e2 is {e1 e3 e4, e2 e3 6%»

The products indicated in Theorem 2—1-6 are

[[81 82 4' 83 E4] [e1 83 64]]1 : [El 82 E3 €4]O el : el.

and
[A [81 e3 e4]]l A : [e1 [e1 e2 + e3 e4]]‘ = [e1 e3 e4]?! 0.

Therefore [e1 e2 + e} e4] is not Simple.

 

Proof of Theorem 2-1-6: Suppose [Ex Bi] A] = O ,
l
.i=l,...,m-1, for a set of echelon forms, (Ei)’
Since the regressive product [A E1] is of degree

1
1. it is simple. By definition of a regressive product each

24

[A Ei] % 0. By an argument identical to the proof of
1

2—1-5 , [AEi]
l . -
vectors [AEi] are independent. Let [AEi] (i=1,...,m-l),
1

1
be made part of a basis for a vector Space and expand A in

Theorem is in echelon form,so the set of

the basic forms correSponding to this basis; i.e.,

I

A = c- PUB] 131 't E: d. D.
i=1 ll: 11 1 i=b+l 1 1

bdcr

where [[AEL] Bi] and D1 are the independent basic forms
1 .

of degree m and Di do not contain [AEL] . Since
1

[[Afifll A] = 0,

But since the [[AEl] Di] (i=b+l,...,z) are independent
1

basic forms of degree m+l. It follows that

di = O, (i:b+l,.../)
and b
A = 2 Ci [Duh] Bi]
i=1 1
Setting
b
P]. = '2 Cl Bi
1=l
gives

 

 

25

A = [@3111 [AEk]l Pk]

then PR is a form of degree (m—k) which does not con—

tain any of the factors [AEJ , i=l,...,k.
' 1

Let

where

[[AEk+1]l Pi] and Hi are the 1ndependent ba51c
forms of degree (m-k) and Hi do not contain [AEk+l]

Since
[[AER+1J A] = o
1
it follows that
j

i=§il di [[AEk+1]l [FE¥J1 ... [AEk]l Hi] = 0

But since the forms
[AB ] [AB ] ... [AB ] H.] (i=f+l,...,j)
[ k*1 1 1 1 k 1 1
are independent of degree m, it follows that
di = o (i=f+l,...,j)

and

1.

.li- .. 2!..- n24 “—‘a..-n_m

26

Setting

f
Pk+l = 2 di Fi
i=1

gives

“tea. ...... w. ...]

By induction, it follows that
A = [AB] [AE _ P _]
|: 1 1 m 1]1 m l

where Pm-l is a form of degree 1.
Therefore A is simple.

Conversely, if A is Simple, then [Mai] is a factor of A
l

by Theorem 2-1-4, so [[AEi] A]=O for all Ei'
l

 

Theorem 2-1-6 provides a method of determining
Whether a canonical form, A, is Simple. If A is given,

a Set of echelon forms can be chosen and the products

[[A 6E1] 1 A]

fDrmed for i = 1,... m - 1. This procedure gives one condi-
tion on the coefficients of A for each term in the above

prodnets. The total number of such terms is

m
z: (
i=1

 

_ n ' n-m
- (m-l) m+l) ' m+l

 

 

IA

27

o 0 ‘
where 3i = —.1.—-.-
(J) (1-J)IJI

An examination of the determinants of an echelon
basis for a subSpace of dimension m in an n-dimensional

vector Space, shows that there are

- 1 — m (n-m)

 

 

conditions on the coefficients of its outer product.

Since it can be Shown that for n' > m

(In—1) [1.31) ] . [

there is much redundancy if Theorem 2-1-6 is used to deter-

1’1 ,
In

n—m

m+l -1 - m (n-m) for m > 1,

 

 

 

 

 

mine whether a canonical form is simple. The next two
Corollaries and the remark following them give a Simplified

criterion which eliminates all the above redundancy.

Definition 2-1-12: A set of echelon unities for the canon-
ical form A of degree m is a set of m-basic unities of
a distinguished non-zero term of A1. Therefore, each

eChelon unity corresponds in a (1-1) fashion to the echelon

fOI‘m that contains it.

L:majy 2-1-1: Let A be a canonical form .of degree m,
and (Bi) (i=1,...m) a Set of echelon forms of A, for a
distinguished non-zero term, P, of A. Let each Ei cor-

respond to the echelon unity ei of P. (i=1,...m). Let

 

28

A0 = A, and Ai be the subsum of Ai-l that multiplies
the echelon unity ei of P. (i=1,...m). (A subsum is the
sum of all forms that multiply a common basic unity in A.

See definition 2-2-5.) Then A is simple if, and only if,

HA Eg A. :1: O (for i = 1,...m-l) (2—1-3)
1 1-1

‘Nriere (Ei) (i=1,...m-l) are some m-l of the set of eche—

lcan forms.
I?rw:of: By Theorem 2-1-1, A is simple if,and only if,
[113% A = o (for i=l,...m—l)
1
Thus the Corollary is proven when it is shown that

[:[A Ei]1 A1 = 0 if, and only if, HAEi] l Ai-l] = 0 (2-1-4)
for i=1,

...m-l.
For i=1, statement (2-1—4) is an identity.

Suppose statement (2-1-4) is true for i f k.
We have

Ai-l : Al 8i + Bi (i=1,...k) (2'1’5)
“filere no term of Bi contains ei. Let
Ci: [Eel e2...ei], c0=1 '
k
A :[Ak Ck + 2 Bi Ci-l] (2-1-6)
i=1

‘ *‘fin'
.

A;

29

First Suppose

[[A Eiflh A] = 0 (i=1,...k)

By (2-1-6)7
k
HA Ek+l] Ak Ck] + .2 [A Blvd] Bi Ci-l] = O
1 1-1 1
But
LA Ek+lil Bi Ci-l] has no ei, (i=1,...k).
Therefore—
[A EiflL Ai Ci] = 0 (i=1,...k). g

 

 

Since no factor of C- is contained in “A E. J A}
1+1 1 1 ’
[[A Eifljl A1]: 0.

Conversely suppose

[IA Ei+l]l Al] : O. (i=1,...k).
By ( 2-1-6) ,

k
[A 3...] A] = [1A E...) (5:, ], (2.1-7)

F"

But

[A Edi A] = 0

:[A EKL Ak Ck] + [[A Edi '2-21 13i Ci_l)]= 0 . (2_1_8)

 

1—

A150 every term of

k
A E A c + d e E B- c-_ (2-1-9)
[{ kjl k k] [ k i=1 1 1 )]

Contains ek as a factor (where d is the coefficient of

ek in [A E1511), and no term of

 

30

[([A 13le - d 6k) (:1 Bi Ci_l)] (2—1—10)

1
contains an ek. Therefore (2—1—9) and (2—1-10) are linearly
independent and are both zero.

From (2-1—9)

H

= Up. 13,41 [A 131,41 Ak ck]: 0

SSince ek is not a factor in any term of

k
[A Ek-rl] ‘1 ek .2 Bi Ci—
- 1 1:1

_ k
[A Ek+1] .2 Bi Ci-l :
1 1:1

k
B- c-_l = 0 (2-1-11)
k*1 1 i=1 1 1

Therefore, by (2-1-7), and (2—1-11)

[[A Ei+l]lA] = 0 (i=1,...k).

It follows that statement (2-1-4) is true for
iF4£+1. Consequently, by induction, statement (2-1-4) is

txrue for i=1,...m—l, and the Corollary follows.

 

The following Corollary gives in (2—1—12), an

e3‘3111iva1ent and shortened form of (2-1-3).

 

 

31

Corollary 2-1-2: Let all notation be the same as in Corol-

 

lary (2—1-1), and let

[AEJ-J1 = [d1 ei + Di] , where Di does not contain

ei and di # 0.

Then
[[A E5111 Ai-l] = 0 if, and only if,
[di ei Ai_1 + 1)i Ai ei] = 0. (i=1,...m-1). (2-1-12)

Proof: By (2-1-5)

where no term of Bi contains ei.

Suppose
[he] 1. J = 0
1 1 1-1.
Then
[E11 el +D1] [A1 ei +1311] = E11 el B1 +Di Ai e1 +Di Bi]: 0
Hence

E11 ei Bi + DiAi ei] = O and [Di Bi] = 0.

Therefore

(1. ‘: . .. .. . =
[1 ei Ai-l + Di A1 81] [d1 e1 Bl + D1 A1 e1] 0

32

Conversely suppose

Then
and

Since D- Bi] does not contain ei

Remark: In Corollary 2-1-1 , Ai Ci can be written as

A1 Ci : :[ [A Ei+1]1(/‘Ei+l)J 1 Di

where Di does not contain any term of

[[A Ei+l]l(/Ei+1)]

Therefore

“A Em] 1 1i]: [[1 EML D]

 

 

33

Thus the computation of

[[1 131.1] 1 Ai]

produces some redundant terms that are always zero. These

terms can be removed if

“A Eiui 1 (/Ei+l)]

5.5 removed from [Ai Ci} prior to performing the multipli-

czation, If
[A1 Ci] : [A1 Ci] 1: [[A EJ111111 (/Ei+l)] , then

[A m1 As] = [A w A]

Let Av be the subsum of A;_ that multiplies the

1 1

ecflielon unity ei.
Then (2-1-12) and (2-1-3) can be replaced by the
ecniivalent condition:

A is simple if, and only if,

: ll .-
[di ei Ai—l + Di Ai ei] — O (1—l,...,m-1) (2—1-13)

 

EXactly
m-l
n-i _ _ _ = n _ _ _
E m+l-i (m 1) (n m) 1 m(n m)
i=1

 

 

 

different terms must be zero for (2-1-13) to be satisfied.
IYNJS there is not redundancy of computation in this instance,

SJJiCe each independent condition is checked only once.

 

34

Example: To illustrate Corollaries 2-1-1, 2-1-2, and the

above remark, consider the Space R5. Is A simple?

A = A0 = ele2e3+3ele2e4 — ele3e5 - e2e3e4.

(Shoose eleze3 as the distinguished term of A. In the

110tation of the two corollaries and remark, we obtain

A1 : 8283 + 36284 ‘ 6385 B1 : ‘62e384, El : 618465

A2 = C3 + 384 B2 = '3385, E2 = 626485
A3 = 1 B3 = 3e4, E3 = e3e4e5
[A E111 - (81 - 64), C11 3 1, D1 : ~84
[21 E211 = (92 1 e5): d2 = 1, D2 = +85
PX Eé]1 = (e3 + 3e4), d3 = 1, D3 = +3e4

11>
ll

r——1
r—1
>
m

£14
H
h\
\
m
H
V!
L_J
l

“ ele2e3 - e4e2e3, o 3ele2e4 - ele3e5
A” = 3e2e4- e3e5

* 9561831 i = 3eze4
A” : ‘3e4

[EA E311 (/E3)] = e3ele2 + 3e4ele2, A2 = O.

— e26163

r-—:
P
[T]

£14

l-‘
A
F;
N
Ml
g;
I

t H :
[d1 81 A0 + D1 A1 81] e4e3eseif 0
[d2 e2 Ai + D2 A5 e2]: -3e5e4e2.

Therefore A is not simple.

—-.-—‘ .MA-m
z...”

35

Part II

Linear Graphs and Matroids

Pr eliminary Definitions:

 

A finite graph G is a finite set E(G) of edges,
21 .finite set V(G) of vertices, and a ternary relation of
5-r1cidence which associates with each edge an ordered pair of
VEfrtices, called its ends.
A sequence P = (a0, A1, al,...,An, an), having at
J—Eéast one term, is a path from aO to an if the following
C Onditions are satisfied:
1. The terms of P are alternately vertices al
and edges Aj of G
n

2. If_ 1 f j 5 then a. and aj are the tWo

J-l
ends in G of Aj’

If x, yEEV(G), we say x and y are connected in

(:;‘ if there is a path in G from x to y. The relation

<2>4fr connection is an equivalence relation partitioning V(G)

:i~i11tup disjoint equivalence classes (V1,...,Vk) [TU—4]

I: <:)IL—l] [SE-1]. The subgraph whose vertices are members of
“v’le and whose edges have both ends in Vi will be called a
‘::‘C3rnponent of G. This is a graphic component, to be distin-
guished from physical component equations. The context

Ei';1~\nnays will clarify what definition of component is used.

 

 

 

 

 

36

All the definitions given in [FR-l] will be used

except the following:

1. Cutset is a minimal non-null set of edges whose
removal separates a component into two disjoint
components.

2. A circuit is a set of edges that form a simple !

closed curve.

q '3 o'_o--

——.1_—o—'." —_

A forest is a collection of trees, each taken from a

g..-

 

i~

distinct component. It can be shown that a forest is a ;
maximum set of edges that contains no circuits. A co-forest
is a complement of a forest. It can be shown that a co-forest
is a maximum set of edges that contains no cutsets. Theorem
(3.2.2) of [FR-1] is true when tree is replaced by forest,
zand when co-tree is replaced by co-forest.
A matroid on a finite set M1, is a class M of
IIon-null subsets of M1 which satisfies the following axioms:
4522§£fl_£: No member of M contains another as a proper subset.

W: If X,YEM, aEXflY, and b€(X-Y), then there

exists ZEM such that
b€Z g (XUY) - {$1.

YThe elements of M are called the points of M.
Let C(G) be the set of circuits of a finite graph
G' Then C(G) is a matroid. In fact the edges of the graph

a . . . . .
re the set M1° Since a Circuit 15 a Simple closed curve

37

formed from a subset of B(G), [FR-1], it has no crossover
vertices, therefore, contains no other closed curves, so
satisfies axiom 1. If X and Y are two circuits with a
common edge a and some edge bE(X — Y), let X and 3
denote the two vertices of a, then the curve 2' from 3
along X to 2K , then along Y to ,8 is closed and does
not contain a. Now 2' contains b but may not be
simple, however, since b€(X — Y) there exists a simple

closed curve 2 contained in 2' such that bEZ. Z is

 

the required circuit that satisfies axiom 2. Henceforth
C(G) is called the circuit matroid of the finite graph G.
Let B(G) be the set of cutsets of a finite graph
G. Then B(G) is a matroid. To see this, let the edges of
the graph be the set Mr A cutset is defined as a minimal
non-null set of edges whose removal separates a component
into two disjoint components. Since cutset is defined as
minimal it satisfies axiom 1. If X and Y are two cut—
sets, a €(xny), and bE(X — Y) then let 2' be the set
01' edges (XUY) - {a}. Let the disjoint sets of vertices

of the components formed by the removal of X be denoted by

C1 and

V - .
Ertices of a byo< and 25 . Let the set of vertices of

C2, and those for Y be D1 and D2, the two

the component be C. Therefore ClU C2 = D1 U D2 = C.

Since without loss of generality,

(X EClfl Drag eczn D2,

38

le1 D2 or szW D1 is non-empty, since other—
Then 2‘ sepa-

then either
is non-empty.

Assume C1(W D2

wise X = Y.
into the disjoint sets

rates the vertices C Clfl D2 and
Cl r\ D1. Therefore, 2' separates the component whose
vertices are C into at least two parts. Since b g(X - Y)
CZZ', let 2 be the minimal subset of 2' containing b
vnuich separates the component into exactly two disjoint com-

B(G) satisfies axiom 2. B(G) will be

ponents. Therefore

called the cutset matroid of the finite graph G.

A matroid is graphic if it is the cutset matroid of a

 

finite graph, and co-graphic if it is the circuit matroid of
a finite graph. The points of a matroid M on M1 are the

elements of M.
To describe any finite dimensional vector Space by a

R denote the real numbers. If M1 is any

nlatroid let
R as 'a* mapping f

Ifjhite set define a chain on Ml over

of M1 into R. If aéMl then f(a) is the coefficient

of a in f. The set of all aeMl, such that f(a) #0 is
If f(a) = O for all a then f

the domain lfl of f.

Ml over R.
of two chains f and g on M1 over

R defined by the following rule:

1 S the zero chain on
'The sum f-tg

15 a chain on Ml over

(f+g) (a) = f(a) + g(a) aEM1

39

M

With this definition of addition, the chains on 1

<3ver R are the elements of an additive Abelian group where

tflie zero chain is the zero element, and the negative of a

cfluain f is the chain (-f) where the coefficients of f

are multiplied by (-l).

Scalar multiplication is defined by the following rule:

If

aEM then rf(a) = r x f(a).

reR, f is a chain 1’

With this definition of addition and scalar multipli-

N iso-

cation the set of all chains form a vector space 0’

morphic to the vector Space Spanned by a corresponding set of

n-tuples.
If M1 is a finite set of n elements we thus have
a. 1—1 correSpondence between the elements of M1 and a
E for the

7

(distinguished set of orthonormal basis vectors

11~dimensional chain vector Space.

Throughout the remainder of this thesis a canonical

c)‘J’tErproduct refers to the expansion of the outer product

in terms of this set E taken as the basic unities. A

rtlatrizxfor this set of basis vectors is defined as follows:

Let M1 = {al,...,aé}
Then [f(al),. ,,,f(an):|

15 a row vector which is called the representative vector of

 

40

the chain f with reSpect to the chosen enumeration of M1.
Let: A be a matrix of r rows and n columns whose elements
are: elements of R and r rows are linearly independent over
R. 'Then the set of chains on M1 whose representative vectors
are .linear combinations of rows of A with coefficients from
It are elements of a chain subspace N, of NO on M1. A
is called the representative matrix of N. For the above
basis, E, A is also the change of basis matrix defining
the subspace, N. (See (2-1-1).)

Now any n dimensional vector space is isomorphic
to the chain vector space NO on n elements since the set
of n-tuples is isomorphic to any n-dimensional vector space
[BI-1].

By the following theorem and the above paragraph we
flave a matroid associated with every finite dimensional vec-
ticw subspace. A chain f of N is elementary if it is
rion-zero and there is no non-zero g 6N such that 'g' is

El pr0pe1- subset of lfl.

‘flh
-.:!h§0ren1 2-2-1: The Class M(N) of domains of elementary

Qllains of N is a matroid on Ml“

m: See mm].

 

The following lemma gives an important property of

every chain vector subspace.

"-‘~ .. -3...» ...“...

 

 

41

{Lemma 2-2-1: The domain of every non-zero chain of N is

21 union of points of M(N)°

22:92:: [TU-3].

 

A subspace N is called graphic (cographic) if its
nuitroid M(N) is graphic (cographic).

A primitive chain of N is an elementary chain f
of N in which the coefficients f(a) are restricted to
the values 0, l, -l.

The subSpace, N, is regular if to each elementary
chain there correSponds a primitive chain with the same
domain. A matroid is called regular if it is the matroid of
a regular chain vector subSpace. By the above definition
every regular matroid has a representative matrix.

A condition equivalent to the regularity of a chain
‘vector subspace is given in the following theorem. In its

.Enoof the following definition is used.

IEEfinition 2-2-1: A dendroid is a minimal non-null subset

(Di M1 such that it meets the domain of every non-zero

Chain of N.

.:!:§gorem 2-2-2: Let A be a representative matrix of a

Vector space, N, of order r x n. Then a necessary and
Sufficient condition that A be the representative matrix
Of a regular chain vector Space on M1 is that the determi-

n - °
ants of 1ts square submatrices of order r are 0, d, and

 

42

-d, where d is a real number # O.

Ilroof: Suppose A is the representative matrix of a regular
vmector Space. Let P be a set of r columns of A that

rnas a non—vanishing determinant. Without loss of generality

zassume P is in the first r columns of A and write
P’1 A = P‘1 [P B] = [U A0].

Since [U A0] is another representative matrix of a regular
chain.vector space and the chains of [U A0] are elementary,

there exists a set of primitive chains in the vector space,

with the same domain as those of [U A0]. Therefore, another
representative matrix for the regular chain vector Space is
the matrix [U Al] in which every row vector of the matrix

[U Al] is a primitive chain.

Since A and [U Al] both have maximum rank and

IePresent the same vector Space,there exists a non-singular

real matrix M such that
M A = [U Al]
Let Pl be any r columns of [U A1] that have.a

inon-vanishing determinant and without loss of generality
‘write

[U A1] = [A2 P1 A3]

43

and

—1
Pl [A2 P

1 A3] = [A4U A

5]

Since [A4 U A5] is another representative matrix of a

rwegular chain vector Space and the chains of [A4 U A5] are

(elementary, there exists a set of primitive chains in the

‘vector Space with the same domain as,the row chains of

LA4 U’ASJ.‘ Therefore, another representative matrix for the
regular chain vector Space is the matrix [A6 U A7] in
which every row vector is a primitive chain with the same

domain as its correSpondent in [A4 U A5] and there exists

some matrix P2 such that

P2 [UAl] = P2 [A2 Pl A3] = [A6 U A7]

But by definition of a primitive chain the entries of

[A6 U] are either :1, or O, consequently the columns of

[A6 U] corresponding to the unit matrix in [U A1] are a

linear combination (with :1, or O) of the rows of the unit

matrix of [UAl]. -It follows that all entries of P2 are

‘1-1,

x

0r 0. But since
P2 P1 = U

and beth, P2 and P1 are matrices of integers, it follows

that (det. p2) (det. P1) = 1 and (det- P2) =11-

44

It has been established that the determinant of any
nonsingular submatrix of [U Al] equals “:1” Therefore
the determinant of any nonsingular submatrix of A is
(det. M'l) (3: 1) = 1 (:1.

Conversely, suppose the determinants of the square
submatrices of the representative matrix A are 0, d, and
-d. Let N be the vector Space spanned by the rows of A.
Let f be any elementary chain of N. Let {a} be any
member of [fl and C any dendroid of N - (Ml - [f|);
(i.e., if S‘E.M12 N - S is the class of restrictions to
S of the chains of N.) Take f such that f(a) = 1.

Then if a chain h of N has a domain not meeting C LWE}
its domain must be a subset of [fl - {a}. Since f is

elementary, this is possible only if h is zero. Therefore
some subset D, of (3 U {a} is a dendroid of N. Since D

Inust meet Ifl, D/llfl = {a}. The following lemma is needed.

 

*ggemma 2-2-2: Let A be an r-rowed representative matrix of

 

bq__ Then a subset S of M1 is a dendroid of N if, and
()Illy if,it has just r elements and is such that det. A (S)

5" <3. A(S) is the matrix whose columns correSpond to elements

<>;E’ S.

M: [TU-l].

 

Returning to the proof of Theorem 2-2-2 , since A

ha S all determinants equal to id or O, det. A(D) = id.

45

Let A' = (A(D))-l A. The matrix A' is a representative
matrix for N. The matrix A‘(D) is a unit matrix. There—
fore there exists a chain g of N such that g(a) = l

and lgl/[D = {a} . Then f-f(a) g is a zero chain since
its domain does not meet D. Accordingly f==f(a) g, and
f(a)==1, so f =g. Also since (A(D))—1 has a determinant
equal to I é and every (r)<r) ~submatrix of A has deter-

minant : d, every (r)<r) submatrix of A' has determinant
:1.

Now consider the (r)<r) submatrix A'(D') formed
from the columns correSponding to D' = (D-{a}) U{b} where
b Elfl such that b # a. Then det. A‘(D') equals : f(b)
since the columns correSponding to D-{a} are distinct
columns of the unit (r)<r) matrix. But det A'(D')==: 1

from above, so f(b)==: l. The same is true for every

element b Elf]. Therefore f is primitive.

 

__emma 2-2-3: N is a regular vector subspace if, and only

inf, its outer product is just.

I’Jroof: Follows immediately from definition 2-1-6 and Theorem

22-—2-2.

 

Let R1 be the field of integers (mod 2). By the
ESame way a matroid was defined on a vector space, No’ over
'tT11e2 field R of reals, a matroid can be defined on a vector

Space N6 over the field R1 of integers (mod 2).

46

N5 is called a binary chain vector Space. NO and
N6 define the trivial matroids where each element of M is
an element of M1' In the same way that the subSpaces N of
N define the non-trivial matroids, the subSpaces N' of
N5 define the non-trivial matroids. N’ is called a binary
chain vector subSpace.

A matroid will be called binary if it is the matroid

of a binary chain vector subSpace.

*Theorem 2-2-4: Every regular matroid is binary.

 

Proof: [TU-3].

Theorem 2-2-5: Every regular matroid correSponds to a unique

 

binary vector subSpace of N5.

.§£22£‘ Let M be a regular matroid. By Theorem 2-2-4 M

is binary so is the matroid of a binary vector subSpace N'.

ESuppose M is also the matroid of another binary chain vec-
txDr subSpace N'l. By Theorem 2-2-1, the elementary chains
<31? N‘ and N’l have the same domain and since their coef-
ficients are both (mod. 2), the chains are equal.

Take any echelon representative matrix A' of N'

:ECJr the diStinguished set of orthonormal basis vectors of
Iqé,. Then each row of A' correSponds to an elementary chain
‘Dfr N'. Therefore A' is also a representative matrix for
.N‘.1- Since N' and N‘1 have the same representative

matrix, PW = N'l.

 

47

The unique binary vector subSpace associated with a
regular matroid M can be determined from any real vector
subspace N which has M as its matroid. First obtain an
echelon representative matrix A for ,N. Since every row
of A correSponds to an elementary chain of N, the rows of
A can be replaced by a set of rows having :1. or 0 only
as coefficients Since N is regular. The new matrix B
thus obtained is in echelon form. Consequently, its rows
are linearly independent and have all elements .11- or 0.
Replace all non-zero elements of B by the corresponding
residue class (mod. 2), to obtain B'. All rows of B' are
linearly independent (mod. 2). Also, the rows of B‘ are
elementary chains of N' and their domains are the same as

the elementary chains of N.

 

The determinant of every maximum rank submatrix of

'the matrix B above is equal to :gl or O by Theorem

23-2-2 , since B is in echelon form and B is a represen-
tEltive matrix of a regular vector subSpace. By the way in
Which the matrix B' is obtained, it follows that the deter-
miI‘lants of maximum rank submatrices of B' are equal to the
determinants of B (mod 2). Let the basis vectors of NO
aJ1C1 N'0 be put in 1-1 correspondence with M1° Now by
e"Elnation (2-1-1) the corresponding terms of the canonical
Omrter products of N and N' have for their coefficients

the determinants of their correSponding columns in B and B‘.

48

Therefore:

Lemma 2-2-4: If M(N) = M(N') where N is regular and N'
is binary, then a coefficient of a term of the outer product
of N’ is non-zero if,and only if,the coefficient of the

correSponding term of the canonical outer product of N is
non-zero. Here the distinguished basis vectors of NO and

N'o are in a 1-1 correspondence.

 

Given a chain vector subSpace N, on the elements
of the finite set M1, and S 9 M1’ let N . S be defined
as the class of restrictions to S of the chains of N, and
N X S as the class of restrictions to S of those chains f
of N for which lfl g5.

Let

Nl ={f : fEN, lfl gSgM}.

N1 is a subSpace of N, since if fENl, la fl = lfl <_: S.
If f€N1, gENl, then

lf+gl§ lfl U lglgS.

Therefore, by Theorem 1, p. 164, of [BI—l], N1 is a sub-
Spaceoflw

There is a 1-1 correspondence between the basis
VeC‘tors E of No and the elements of M1. Let E1 be

tr“? subset of E corresponding to the elements of S. It

49

follows that N1 is the subspace of vectors of N that are
linear combinations of the chains of El.

If S has m elements, El has m elements. Con-
sider the m-dimensional SpaCe, N2, Spanned by the restric-
tions to S of the chains of E1. The chain f', formed
from chain fEN by restricting f to S, is an element
of N2. The class N X S is the subspace of N2 formed
from the chains gENl by restricting g to S. Thus,

N X S and N’- S are subSpaces of N2.

Note that N2 is an m-dimensional Space and each of
its vectors have m coefficients, one correSponding to each
element of its basis,whereas N and N1 are subSpaces of
NO which is n-dimensional and therefore, each vector has n

coefficients. Now consider the subSpace (N X S) - T. If
E21E_E are the basis elements of NO corresponding to the
set (S/WT), and S()T has t elements, E2 has t ele-
nuents. Let N3 be the t—dimensional vector Space spanned
liy'the restrictions to S, of the chains of E2. Therefore
(Pq X.S) ° T is a subSpace of N3.
Let M be a matroid on the set M1’ and the matroid
M(N) on the subSpace N defined by Theorem 2-2-1
Let (M X S) be the class of all sets of M which

are subsets of S. Then (M X S) satisfies axioms I and II

at“: is therefore a matroid on S.

f .

50

Let Ms be the class of intersections with S of
members of M, and let (M - S) be the class of all minimal
non-null members of Ms' In [TU—3], it is Shown that
(M - S) is a matroid on S.

From: [TU—3]

M (N) X S

M(NXS)

M(N.S) M(N).s

The matroids of the form (M X S) - T (where T,
S g M1) are called minors of M.
If M is the matroid of a chain vector Space N,

then

(M(N)XS) - T = M(NXS) - T = M((NXS) - T) (2-2—1)

 

filatroid Minors and Outer Products

In the notation above, (N X S) - T can be inter-
preted as the class of restrictions to (T08) of the chains
‘31? N1. Let E3 be the restrictions to (S/)T) of the
C31£1ins of E2. If a representative matrix A of N is
chOsen such that a maximum set B1 of linearly independent
VeCtors of N1 are represented by rows of A, then (N X S)
'T 4is spanned by those linear combinations of elements of E3
re{presented by the vectors of 81' Let AO be the submatrix

of? A composed ofthernrows corresponding to Bland n columns

 

in

.;

n...

[.

Q-

51

corresponding to their coefficients in El. Therefore a sub-
matrix A1 of AO whose rows represent vectors that Span
(N X S) - T is the subset of columns of AO corresponding

to E and the rows of A0. A representative matrix for

2,
(N X S) - T could be obtained from A1 by choosing a max-
imal linearly independent set D of rows of A1. Thus D
is some submatrix of A. Also since the rows of A corre-
sponding to the vectors of B1 are linearly independent and
all coefficients of vectors of Bl corresponding to (E - E1)
are zero, it follows that the rows of the submatrix A0 are
linearly independent. By performing linear combinations on
the rows of AO it can be assumed that the complementary
set of rows to matrix D in A1 is 0. Let A2 denote the
matrix composed of the rows of AO that were deleted to form
D and the columns of AO correSponding to the coefficients
of '(El - E2). Then the rows of A2 are linearly indepen-
<1ent since if they were not, AO would not have linearly

independent rows. Let A3 be a submatrix of A2 with

-1:inearly independent columns. By elementary row operations

'tlle entries of the submatrix of AO corresponding to the

ITDVVS of D and the columns of A can be made 0.

3
The remaining rows of A can be Split into two sub-

mafitrices. Let A4 be those columns corresponding to El

at“: let A5 be those columns corresponding to (E - E1).

:It is claimed that the rows of A5 are linearly independent.

“V“

(II

I"

52

If they were not, there would be some row combination of the
matrix [A4 A5] with coefficients not all zero such that
the columns correSponding to A5 are zero. But the same
combination of the rows of A4 would be non-zero since A

is a set of linearly independent rows. By definition the
resulting row is a vector of N1. But it was already assumed
Ao contains all such rows. Therefore, the rows of A are
not all linearly independent, contrary to assumption on A.

This contradiction establishes that the rows of A5 are

linearly independent. Thus the following has been established:

Lemma 2-2-5: A representative matrix D of any subspace of

 

the form (N X S) - T can be made a submatrix of a represen-
tative matrix A for N in which the submatrix D1 of A
composed of the set of rows complementary to D and the set
of columns complementary to D has linearly independent rows,
aind the submatrix D2 of A composed of the set of rows of

I) and a set of columns of maximum rank in D1 is zero.

 

Lemma 2-2-5 and equation (2-2-1) give:

.Eagfiiprem 2-2—6: A matroid M(N) ‘on Ml contains a given

 

millor K if,and only if,
1. There exists a representative matrix A, of N
that possesses a submatrix D that is a represen-

tative matrix of the minor K,

53

2. The submatrix D1 of A composed of the set of
rows complementary to D and the set of columns
complementary to D has linearly independent.
rows, and

3. The submatrix D2 of A composed of a set of
columns of maximum rank in D

1 and the set of

rows of D has zero for each entry.

 

Using Theorem 2-2-6 , one can determine from the
canonical outer product F of N, whether M(N) contains

a given minor K. Suppose M(N) possesses a given minor K,
and dimension of N is n1. From A the outer product of

N can be expanded in terms of the elements of E Since A

is a change of basis matrix. By equation (2-1-1), the coeffi-
cient of term EP. of F is the determinant of the n1 x nl
submatrix of A taken from the n1 columns corresponding to
the factors of EPi' Let D3 be 'a square submatrix of D1
which is nonsingular. Since D has linearly independent rows
and Since the sum of all rows of D3 and D is n1 and D2
is zero, the determinant of every square submatrix of D
multiplied by (det. D3) is a coefficient of a term of F.

The terms corresponding to these coefficients are the terms

of E correSponding to the columns of D3 and the columns

of D. Thus:

 

54

Theorem 2-2—7: A matroid M(N) on Ml contains a given
minor K if and only if the canonical Grassman outer product
F of N, contains the outer product P1 (of the vector

Space corresponding to K) multiplied by a basic form E3.

 

. I

The above basic form E3 lis the subset of E corre-
Sponding to the columns of any nonsingular D3.

Since any regular matroid M(N) is the matroid of a
unique binary vector Space N' by Theorem 2-2-5 , and Since
any minor of a regular matroid is regular [TU—l (3.5)], for
regular matroids, we may substitute N' for N in the above
theorem and the outer product F‘ of N' for F and the
outer product F'1 of the binary vector Space correSponding
to the minor K, for Fl'

Using Lemma 2-2-4 , the problem of determining the
existence of a given minor of a regular matroid is reduced

to the determination of the existence of a collection of sets

(called residue sets).

Definition 2-2-2: A residue set of an echelon representative
matrix A of N is the unordered subset of E (the basis
vectors of the Space NO) which have non-zero coefficients
in some chosen row of A.

If an echelon representative matrix A has 111 rows,

it has nl residue sets, one for each row of A.

55

Definition 2-2-3: A reduced residue set of an echelon rep-
resentative matrix A of N is a residue set where the basis

element correSponding to the diagonal coefficient has been

removed.

Definition 2-2-4: The residue sets (reduced residue sets)
of a non-vanishing term of an outer product are the residue
sets (reduced residue Sets) of the echelon representative
matrix associated with the set of echelon forms of the non-

vanishing term (by Theorem 2-1-5).

 

The reduced residue sets or the residue sets are a
way of describing an echelon basis within a column permuta-
tion in a mod. 2 Space. If M is regular Theorem 2-2-6
can be applied to its unique binary vector Space of Theorem

2-2-5, and determine the minors present in some echelon
representative matrix. Therefore, to determine the minor's
presence the reduced residue sets need only be examined for

their size and intersections.

The above discussion is summarized in this lemma:

Lemma 2-2-6: Let N‘txza unique binary m—dimensional vector
subspace derived from a regular matroid M on a finite set
Ml' Let the set M1 have n elements which correspond l-l
to a basis set E of a binary vector Space N'O. Of course
1W EEN'o- Then M contains a given minor K if and only
if there exist reduced residue sets of an echelon represen-

tative matrix of N' which when intersected with a subset

 

 

56

of E, form the reduced residue sets of the unique binary

vector space N'l which represents K.

 

If all possible echelon representative matrices of

N'l were known, every set of k columns need be examined

only once. This is the technique used in Theorem 2-2-12
Graphic Matroids and Outer Products

Theorem 2-2—8: A matroid, M, is graphic (cographic) if

 

and only if it is regular and has no minor which is the

circuit-matroid (cutset—matroid) of a Kuratowski graph.

Proof: [TU-4] (Main Theorem)

 

The two Kuratowski graphs are the Thompson and the

complete - 5. They are Shown below:

/\
W

Thompson Graph Complete - 5 Graph

 

 

>4

 

 

Theorem 2-2-9: A real vector subSpace, N'E NO, is graphic

 

if and only if it has a just canonical outer product F

/

which does not contain the outer product Fl (of a circuit

57

vector Space corresponding to a Kuratowski graph) multiplied

by a basic form E3.

Proof: The proof is an immediate application of the defini—
tion of regular matroid, Lemma 2—2-3 , Theorem 2—2-7 , and

Theorem 2-2-8

Theorem 2-2-10: A real vector subSpace, N §.N is graphic

0’

 

if,and only if,it is:

1. regular,

2. has no representative matrix, A, that possesses
a submatrix D that is a representative matrix of
a Kuratowski circuit minor,

3. the submatrix D1 of A composed of the set of
rows complementary to D and the set of columns
complementary to D has linearly independent
rows, and

4. the submatrix D2 of A composed of a set of
columns of maximum rank in D and the set of

1

rows of D has zero in each position.

Proof: Follows immediately from the definition of regular

matroid, Lemma 2-2-3 , Theorem 2-256 , and Theorem 2-2-8

 

Theorem 2-2—11: A real vector subSpace N is graphic if,and

 

only if,it has a just canonical outer product F that has no

non-vanishing term with reduced residue sets such that their

58

intersection with some subset of E forms the reduced residue

sets of a Kuratowski circuit subspace.

Proof: By the definition of regular and Lemma 2-2-2, we see
that N is regular if and only if N has a just outer prod-
uct. By Lemma 2-2—6, M(N) contains a Kuratowski circuit
minor if and only if there exist reduced residue sets of

some echelon representative matrix of N' (where N' is

the unique binary vector Space such that M(N)==M(N')) whose
intersection with some subset of E forms the reduced resi-
due sets of a Kuratowski circuit subspace. .But by the con-
struction process described after Theorem 2-2—5, the reduced

residue sets of echelon forms of N and N' are identical.

This theorem provides the simplest interpretation of
a graphic vector Space since it means that once we know a
vector Space is just, we perform the search for non-graphic
subSpaces in set algebra, or in its equivalent, (mod. 2)
algebra.

The following analysis of the circuit subspaces of
Kuratowski graphs provides the final theorem which is use-
ful in the algorithm of Chapter 3. An m-form is a form
generated by m of the distinguished basis elements.

Analysis of the Thompson graph Shows that there are

only 2 distinct structures of co-trees,

59

1. those that form a path and,
2. those where three edges form a path and the fourth

edge is not connected to the other three.

Within a suitable permutation of the columns the two
echelon representative matrices for these structures are
unique because of the symmetry of the graph; and can be put
into the forms below: I

For structure 1:

l l l O O l O O O
l O 1 O l O l O O
O l O l l O O l O
O O l l 1 O O O 1
For structure 2:
l l l l l l O O O
l l l O O O 1 O O
l l O l O O O l O
l 0 O 1 l O O O l

where, of course, the order of the columns between structures
1 and 2 has been permuted. The orientation of the elements
is neglected since by Lemma 2-2-6 , it is unimportant.

Let A be an arbitrary Simple just nine form of
degree 4. Denoting the first five elements of both struc-
ture l and structure 2, by a, b, c, d, e, it is obvious that
a non-vanishing term of A corresponds to the unit matrix
in structure 1, if and only if the residue sets of the term

are:

{21, b, c} , {a, c, e},{b, d, e}, {c, d, «2} (T1)

 

60

for some suitable permutation of the first five columns.
Likewise, a non-vanishing term of A corresponds to the
unit matrix in structure 2 if,and only if,the residue sets

of the term are:

{a, b, c, d, e}, {m b, c}, {21, b, d},{a, d, e} (T2)

for some suitable permutation of the first five columns.
Residue sets (T1) and (T2), are called the Thompson

residue sets. Thus the following has been shown:

Lemma 2-2-7: Let A be a Simple just nine-form of degree 4.
A corresponds to a circuit space of Thompson graph if and
only if any non-vanishing term has a Thompson residue set.
(Only one term need be examined Since A is simple, and the
echelon set uniquely determines an echelon basis by Theorem
2-1-5 ).
An analysis, Similar to the above for a complete-5
graph shows that there are 3 distinct structures of co-trees:
1. those correSponding to a union of two circuits
with one edge in common,
2. those corresponding to a union of two 3-edge
circuits with one edge having a free vertex, and

3. those correSponding to a complete-4 graph.

W

 

 

 

 

 

 

 

 

Structure (1) Structure (2) Structure (3)

61

Again, as in the Thompson graph, because of the sym-
metry of the graph, the two echelon representative matrices
for these structures are unique except for a suitable permu-
tation of the columns. Allowing for this, the echelon
matrices are as follows:

For structure 1:

 

 

 

 

— -fi
1 l l l l O O O O O
l l 1 O O l O O O O
O 1 1 l O O l O O O
l l O O O O O l O O
O l l O O O O O l O

_O O l l O O O O O 1_

For structure 2:
l l l O l O O O O O
l l O 1 O l O O O O
l l O O O O l O O O
O 1 l O O O O l O O
O 1 0'1 0 O O O l O
O O l l O O O O O 1
For structure 3:
l l O O l O O O O O
l O l O O l O O O O
l O O l O O 1 O O O
O l l O O O O l O O
O l O l O O O 0 l 0
LO 0 l l O O O O O 1'

 

 

Let B be an arbitrary simple just ten-form of
degree 6. Let the first four columns in the matrices above
be denoted by a, b, c, d.

Similarly to the above analysis for the Thompson
graph, a non-vanishing term of B correSponds to the unit

ma'trix in structure 1 if and only if the residue sets of the

term are:

62

{a,b,c,d}, {a,b,c} , {b,c,d} , {at} , {he} , {C,(l} (Kl)

for some permutation of the first four columns.
Similarly a non-vaniShing term of B corresponds to
the unit matrix of structures 2 or 3, if and only if, residue

sets of the term are:
{a, b, c}, {21, b, d}, {a, b},{b, c}, {m d}, {c, d}(K2)
or

{a, b}, {a, c}, {a, d}, {m c}, {1), d}, {c, d} (K3)

respectively, for some permutation of the first four columns.
Residue sets (K1), (K2), and (K3), are called the

complete-5 residue sets. It has been established that:

Lemma 2-2-8: Let B be a simple just ten-form of degree 6.

 

B correSponds to a circuit Space of a complete-5 graph if
and only if any non-vanishing term has a complete-5 residue
set. (As for the Thompson graph, one non-vanishing term
need be examined Since B is simple and the echelon set

uniquely determines a basis.)

Definition 2-2-5: A sub-sum of an outer product is the sum
of all forms that multiply a common basic form. Example:
Let {x1, x2, x3} be the basic unities. Then

a x1 x2 + b x1 x3 + c x2 x3

has (b x1 + c x2) as the sub—sum multiplying the common

basic form, x3.

63

Theorem 2-2-12: Let E be the set of basic unities of No'
Let NO be a real vector Space of dimension n. A real vec-
tor sub—Space, N, of NO, is graphic if and only if the
just canonic outer product F of N has no sub-sum which
has either Thompson or complete-5 reduced residue sets for a

non-vanishing term.

Proof: The process of forming an intersection with the resi-
due sets is equivalent to forming a sub-sum and then taking
the residue sets of the sub-sum. The rest follows from

Theorem 2—2-11 , and Lemma's 2-2-7 , and 2-2-8 .

 

Note here that there is no need to form the complete
sub-sum but only to look for the presence of certain terms in

the sub-sum.

 

The following two important graphic operations used

in the next chapter are taken from [TU-l].

Definition 2-2—6: Let G be a finite graph, and S a sub-

 

set of edges in G (i.e., S B(G)); Let G - S be the
subgraphof G whose edges are members of S and whose
vertices are the ends of members of S. G : S is the sub-
graph of G whose edges are members of S and whose ver-

tices , are all the vertices of G.

64

Definition 2-2-7: Let G be a finite graph, S a subset

 

of B(G). G ctr. S is the subgraph of G whose vertices
are the components of G: (B(G) - S) and whose edges are
the members of S; the ends in G ctr. S of an edge vA
are those components of G: (B(G) - S) which contain as
vertices the ends of A in G. We may regard G ctr. S
as obtained from G by contracting each component of G:
(B(G) - S) to a single point. G X S is the graph obtained
from G ctr. S by suppressing its isolated vertices. These
vertices are clearly those components of G whose edges all
belong to B(G) - S.

If C(G) is the circuit matroid of the graph G,

and B(G) is the cutset matroid of G,

B(G ° S) = B(G) - S
B(G x S) = B(G) X s
C(G - S) = C(G) x s
C(G X S) = C(G) - S

For proof, see [TU-4].

By the definitions of B(G) - S and the others before (2-2-1)

we have
B(G x s) = M(Nl x 5)
(2-2-2)
C(G : S) = M(N X S)
C(G x S) = M(N - s)

65

where N1 is the graphic vector Space of G, N is the
cographic vector Space of G, and M is the unique matroid
corresponding to each vector space by Theorem (2-2-1).

Likewise

B[(G x S) - T] M [(Nl x S) - T]

B[<G - S) X T] M [(Nl - S) X T]

(2-2-3)

C[(G ° S) X T] M[(N X S) ' T]

M[(N - S) x T]

C[(G X S) ° T]
More complex minors are computed similarly to these.
Part III

Components and Systems

 

Let CE be a set of equations called component
equations, perhaps parametrized by an independent variable
t, relating the coefficients of a distinguished set K, of
orthonormal basis elements of a finite dimensional vector
Space V' of dimension 2e. Let all the basis elements of V
be put into exactly e ordered pairs, and let P be the
vector Space generated by the first elements of the ordered
pairs. Let P' be the vector Space generated by the second
elements of the ordered pairs. The distinguished basis
elements of P are called across variables, and the dis-
tinguished basis elements of P' are called through

variables.

66

Let G be a finite graph of e edges and let P
be a 1-1 correSpondence between the set of edges of G and
the ordered pairs of V. Let N be the co-graphic vector
subSpace of P and N1 the graphic vector subSpace of P'
correSponding to the graph G by F.

A system is defined as the ordered triple {CE, G, E}.
A system can be described by a set of equations, CE togeth-
er with the equations formed by equating all vectors of N
and N1 to 0. (These latter equations are the generalized
Kirchoff's laws of [FR-1].)

A graph, G1, is a subgraph of a graph, G, if
B(Gl) C B(G) and V(Gl) CV(G). Let N' be the co-graphic

vector subSpace of P -correSponding to the subgraph G by

1
F and N'l the graphic vector subSpace of P' correSpond-
ing to the graph G1 by P. Then a subsystem of {CE, G, B}
is the ordered triple {CE1, G1, Bj>. The equations describ-
ing the subsystem are:
l. the equations CEl relating the coefficients of

the distinguished basis ordered pairs of V that

correSpond to the edges of G1 (it is assumed .
that G1 is chosen so that all other coeffi-
cients are in the remaining equations of CE)

2. the equations formed by equating all vectors of

N' and N'1 to O.

67

It is assumed that all component equations are
written with reSpect to the distinguished basis of V. The
representative matrix of N or of its orthogonal complement
is assumed to be defined with reSpect to the distinguished
basis of, V.

Throughout this thesis systems are examined whose
componentequations are: ordinary differential, integral,
algebraic, or combinations of the above three; i.e., a single
valued mapping or operator between abstract Spaces or func-
tion Spaces, as described in works on functional analysis,
and system theory, [ZAH-l],[ZAM-l],[WIE-l],[ZAH—2],[BOS-l],
[BAR-1],[MC-l]. (An algebraic equation means a relation
between coefficients of basis elements that does not relate
differentials, integrals, or limits of the variables.)

The component equations considered are identified as
the following types: ‘

Type (1): Differential and algebraic equations of

form:
d -
3? 'wk.‘ Fk( wk’ zik’ t)

Z = G (]V , Z- , t)
ok k k 1k

where Z-k and Z0k are each vectors of a finite dimen-

sional Space V of order Nk-l and each contains exactly

68

one coefficient xj or yj corresponding to each edge
j=(l,2,...Nk-1) of the correSponding graph (defined in
[PR-1]). The vector tfik is called the state vector of the
multi-terminal component and t is an independent real
parameter, usually time. 2 Zi le are vectors in E“

°k’ k’

which vary with the parameter t.

Type (2): Integral and algebraic equations of the

general form:

10k<t) = chzikcs), s. t) ds

20k GRC Vk’ zik’ 1:)

Type (3): If the component is described by an Oper-
ator between abstract Hilbert Spaces, equations of the

following form:
20k = Fk(Zik, t)

where the quantities are as defined above, except that the
vectors are elements of the Hilbert Space Lka, [See Part II,
Chapter III] or the real Euclidean space of dimension mk.
The vector subSpace N generates, for a 2e dimen-
sional vector Space V, e linear algebraic constraint
equations. As shown in [FR-l] and [KO-l], these con-

straint equations represent a generalization of Kirchoff's

69

laws and they can be written without loss of generality in

the forms
A Y = O

and (2-3-1)
B X = 0

where A is a representative matrix of the orthogonal com-
plement of N, B is a representative matrix of N, Y is
a vector of thru variables, one coefficient correSponding to
each edge of the graph and therefore to each basis element
of the Space, and X is the corresponding vector of across
variables. This notation is all defined in [FR-l].

If a system has m components, the equations describ-
ing the system behavior can be written as the direct sum of
m component equations of Type (1), (2), or (3), (which is
CE), and the set of e algebraic constraint equations

(2-3—1).

 

CHAPTER III
UNIQUENESS AND EXISTENCE OF A SOLUTION

A system, €E, G, F}, is said to have a unique
solution if all system variables are determined uniquely
from the component and graph equations.

In the first part of this chapter, uniqueness and
existence results are given for linear, constant coefficient
systems of algebraic, integral, and differential equations.
Since the linear operators of differentiation, integration
and algebra are commutative, the determinant of these such
linear operators has meaning and is useful in uniqueness
studies. Perhaps the most novel theorem is 3-1-3 where
uniqueness problems involving positive semi-definite compo-
nents are reduced to the linear independence of a subset of
the component and graph equations.

In the second section the conditions for existence
and uniqueness of non-linear systems are examined, and some
new results derived which are a generalization of those

previously known. [WI-l].

70

 

71

Part I. Linear Systems
Introduction

Consider first the linear time-stationary components
of type (1); i.e., components governed by differential and

algebraic equations of the form:

£1.

dt Wk=Powk+Pl Zi +Fo (t):

k k
(3-1-1)
2 = P + P 2- + F (t)
where Pok(t) and Flk(t) are almost everywhere continuous
real-valued functions of t on some interval I.

Now let (s==aT), and write (3-1-1) in the form

(5 D + D ) + D 2. + D 2 = P (t) (3-1-2)
1k 2k Vk 3k .1 4 0k 3k

k k

where D = D = D

II
D
I

ll
0
F“

F
3k F1

and U is the unit matrix.

Solving the first set in (3-1-1) for 1Vk gives:

1n. = (s U - PO)-l P1 zik + (s U - PO)-l F0k(t) (3-1-3)

72

Substitute (3-1-3) into the second expression of

(3-1-1) to obtain:

_ -l -1
20k — P2(s U - P0) P1 zik + P3 Zik + P2(s U - PO)
F0 (t) + F1 (t) (3-1-4)
k . k
Setting
(P2 Adj. (5 U - P0) P1 + P3) = -Clk(s)

[det. (s U - PO)] U = Cok(s)

and
-1 _
Cok(5) P2 (5 U - PO) Fok(t) + F1k(t) - F3k(t)
(3-1-4) becomes
+ - = - -
Cok(s) Zok Clk(s) 21k F3k(t) (3 l 5)
where [Cok(s) C1k(si] is a square matrix of polynomials

in s and each row is assumed to be a vector polynomial of
minimum degree.

Consider an arbitrary system S of components of
type (3-1-5). Let the direct Sum of the component equations

be written as

00(5) 20 + 01(5) 21 = Fo(t) (3-1-6)

 

 

73

Repartitioning the Z0 and 21 into the thru
variables Y and across variables X, (3-1-6) takes on

the form
51(5) x + 52(5) Y = F1(t) (3-1-7)

where El(s) and E2(s) are square matrices of polynomials
in s, and the entries of X and Y are ordered so that
complementary variables correSponding to the same edge are
in correSponding positions.

Combining (3-1-7) with the circuit and cutset equa-
tions (2-3-1), a general form of the system equations for a

linear system is given as follows:

 

 

 

31(3) E2(s) x "Pl(tf'
B 0 Y = 0 (3-1-8)
0 A ' o

— A b .1

 

The following analysis is valid for any equations in
form (3-l-8). Some Type 2 components can also be put in this
form as well as any equations with derivatives on the input
variables.

A necessary and sufficient condition for a unique
solution to (3-1-8), on some interval on t, with incompat-
ible boundary values [IN-l], is that the determinant of the
matrix on the left of (3-1-8) is not identically zero.

[IN—1] [CR-l] [GA-l].

74

An alternate form of (3-1-8) for equations of Type 1
is obtained if the direct sum of the components of a system

S1 of form (3-1—2) is written as

(5 D1 + D2) ‘4” D3 zi + D4 20 = 1:30;) (3—1—9)

The alternate for equation (3-1-8) is:

 

 

 

s 131+ 132 El 13;] yfl F3(t)'l
o B o x = 0 (3-1—10)
0 o A y o

_. .. .. _ L. _.

 

 

 

where E1 and E2 are the properly partitioned columns of
D3 and D4.

It is well known that for systems having driver type
components (i.e., X0 = Fa(t), Y1 = Pb(t)) a unique solution
exists only if all edges correSponding to variables Xo can
be put in a forest T of the system graph G, and all edges
correSponding to variables Y1 can be put in the co—forest
of T in the system graph G. [KO-l].

Within the context of the notation used here a driver

type component is defined as:

Definition 3-1-1: A driver-type component is a component of
form (3-1-1) where P1 and P3 are zero matrices.

The following theorem and its corollary shows how
the driver type components can be removed from further con-

sideration in existence and uniqueness studies.

 

75

Theorem 3-1-1: Let the direct sum of a set of component

equations, CE, of system {CE, G, R} ‘be of the form:

(s D1 + D2) 1V+ E11 x1 + £21 Y1 = F1(t) - (3-l-ll(a))
x0 = F0(t)
(3-l-ll(b))
Y2 = F2(t)

where the set of edges corresponding to X0 and Y2 contain
all the driver-type components. Let Sxi be the edges cor-

responding to the variables X i = 0, l, 2. Let G' be

i!
the subgraph [G X (B(G) - Sx°)] - Sx{] .

(a) If the set of edges corresponding to Xo can be
made part of a forest T of the graph G and the edges cor-
reSponding to Y2 can be made part of the co-forest of T,
then the System {CE, G, P}’ has a unique solution if, and
only if, the subsystem {DE1, G', R} has a unique solution.

(b) If the conditional part of (a) is not satisfied,

the system {CE, G, F} has no unique solution on I.

Proof: Assume the hypothesis of (a).. Using the notation
of [PR-1], take the circuit and cutset matrices in echelon
form. Under the partitioning given in (3-1-11) (a) and (b),

(3-1-10) for system {CE, G, F}’, can be written as

76

 

 

 

 

.___ ____1 __ _. .1
(5 ”1*92) 0 E111 B112 0 0 E211 B212 0 '1’ F1(t)
. 0 U o o o o o o 0 x0 Fo(t)
o o o o o o o 0 U x1e P2(t)
0 B1 32 U o o o o o x1c == 0
0 B3 B4 0 U o o o 0 x2 0
o o o o 0 U o -B1T -B3T Yo o
T T
L__ o o o o o 0 U -32 -B4 Ylb L_.0
—_l —
ch
Y2 (3-1-12)
L..D

 

 

(where le and X1

and Yi are complementary pairs corresponding to the same

c is a suitable partitioning of X1 and

Xi
edges).

System {CE, G, B} has a unique solution if,and only
if,the matrix of (3-1-12) is nonsingular. By elementary row

operations transform (3-1-12) into

 

 

 

 

F73 91‘92) 0 E111 B112 0 0 E211 5212‘6_ F@'-w l_E1(t) -j
0 U o o o o o o 0 5x0 POCt)
o o o o o o 0 =0 U l x1b P2(t)
o o 32 U o o o o o ‘ x1c = -BlFo(t)
o 0 B4 0 U o o o 0 x2 -B3Fo(t)
o o o o 0 U o -BlT 0 Yo B3TP2(t)
l__ o o o o .o 0 U -B2T .9] Ylb ;_?4TP2(EZ
ch
_¥2_l (3-1-13)

 

 

77

By (2-2-3), (3-1-10) for system ‘{CE1, Gl’ F}’ can be

written as

 

 

 

 

(5 91*D2> E111 E112 E211 B212 1” F1(t)
o 32 U o o le = o
o o 0 U -BZT x1C o
L— —_J _—"
Ylb
Y (3-1—14)
L.1Es

 

 

Comparing (3-1-13) and (3-1-14), it follows that
(3-l-l3) has a unique solution if,and only if,(3-l-14) has a
unique solution, and the conclusion (a) follows.

If the condition in (a) is not satisfied then by
Theorem 3.3.1 in [FR-l] and an analogous theorem in [KO-l],
the system {CE, G, R} has no unique solution, and Theorem

3-1-1 is proved.

 

Definition 3-1-2: The operation of breaking a vertex into

 

two vertices and then connecting an edge between them is

defined as a vertex Splitting operation.

Corollary,3-l-l: Let CE be the component equations of

 

(3-1-11, (a) and (b)). Let the System {CE1, G', B} have

a unique solution. Let G be the graph formed when each
across driver in (3-1-11(b)), is added by a succession of
vertex Splitting operations, and each thru driver in

(3-l-ll(b)) is added between any two connected vertices in

G'. Then the system ‘{CE, G, B} has a unique solution on I.

78

Prggfz Since each vertex Splitting operation is performed
on a Single vertex by a succession of Splitting operations
the graph G1 thus formed contains no circuits of across
drivers. Therefore, by Theorem 2-12 of [SE-l] and its
immediate extension to disconnected graphs, the edges of the
across drivers are part of some forest T of the graph G1.
Adding the edges El correSponding to thru drivers
in succession between two existing connected vertices of G1,

generates the graph G having the same vertices as G The

1.
forest T is also a forest of the graph G and therefore

contains no thru driver edge, and the corollary follows.

 

Remark: In reducing graph G to G' by the operations in

[Theorem 3-1-1, 1-edge circuits (called loops) and l-edge cut-

sets may be formed. This is equivalent to short circuiting
or open circuiting component terminals.

In View of Theorem 3-1-1 and Corollary 3-1-1, through-
out the remainder of Part I, it is assumed that no driver

type components are present in the systems examined.

79

Existence and Uniqueness Theorems

The following theorem gives a sufficient condition
for a unique solution for an important class of passive

components.

 

Theorem 3-1-2: Consider component equations of the form
(3-1-7). If for some real constant 5 the quadratic form
XT E1(s) E2T(s) X #'0 for all real vectors X %'O, then any
system having the component equations (3-1—7) has a unique

solution.

Proof: It will be shown that the matrix on the left of
(3-1-8) is non-singular when the conditions of this theorem

are satisfied.

Lemma 3-1-1: Let E and KO be the following square matrices:

E= [R El E2] U o o]
0 AT 0
T

 

 

Lo 0 B

KO = R El E2
0 B O
O O A

 

 

where B and A are given in (2-3-1). Then if A has t

rows and e columns,

8O

det. E = (-l)e(e-t)det. KO.

Proof: Suppose the columns of K0 are permuted so that
there is a nonsingular matrix in the first (e-t) columns

of B. Let the columns containing A be permuted similarly.

Then if P is the permutation matrix, by Theorem 3.2.1 of

 

 

[PR-l]:
R E3 E4 E5 E6
KOP = 0 Cl ClB1 O O
o o o -c23f c2
or
KOP = C0 K1
where
R E3 E4 E5 E6 1] 1
K1 = O U B1 0 O and Co = C1
T
LO 0 0 -B1 UJ , C2

 

 

 

 

[E3 E4] and [E5 E6] are matrices formed by suitable
permutations of the columns of E1 and E2, C1 and C2
are the nonsingular matrices obtained by the permutation.
Since P does the same permutation on both the
columns of El and the columns of E2, P is an even

permutation so

81

 

 

det. P = 1
If det. I} 7
C1 = c f 0, then
L C2-
det. K0 = c det. K1. (3-1-15)
Premultiply K1 by

 

 

to'obtain

R o E4-E3Bl 55+5631 0
K2: 0 U 131 o o
o o 0 -BT U
L l J

 

 

and det. K2 = det. K

Now

_ e(e-t) T
c det. K2 - c(-l) det.[-R E4-E3B1 E5+E6B1]

 

 

 

 

 

 

 

From (3-1-15)

det. KO = (-l)e(e't)det. E} and the Lemma follows.

 

Returning to the proof of Theorem 3-1-2, suppose the
matrix of (3-1-8) is singular. By Lemma 3-l-l, there is a
non-zero row'vector Z{(s) with polynomial entries in

powers of s such that the vector
21115) [131(5) 132(5)] (3-1-16)

A O
is orthogonal to the row Space of ; i.e., for
O B
T T . .
some row vectors 22(5) and 23(5) w1th polynomial

elements.

L-l3

83

le(s) E1(s) = 22T(s) B
and , (3-1-17)
le(s) £2T(s) = Z3T(s) A .

Therefore, by Theorem 3.2.1 of [FR-l],

ZlT(S)E1(S)E2T(s)Zl(s) = 22T(s) B AT 23(5) = o (3-1-18)

Equation (3-1-18) is true for every S, and at least one
co-ordinate of 21(5) is a non-zero polynomial.

If 21(5) were zero for some real 5 (say 5 = a),
then every coefficient of 21(5) would have a factor
(S - a) and could be written as 21(5) = (s-a) Zl'(s),
where Zl'(s) satisfies (3-1-16), (3-1-17), and (3-1-18),
for some ZZ'(S) and Z3'(S). Proceeding in this fashion
obtain a vector Zl"(s) of minimum degree that vanishes
for no real 5 and satisfies (3-1-16), (3-1-17), and
(3-1-18), for some 22"(s) and some Z3"(s). It suffices,
therefore, to suppose that 21(5) is a vector of minimum
degree, not equal to zero for any 5.

If follows, that (3-1-18) is a contradiction to the
hypothesis of Theorem 3-1-2 , so, the system has a unique

solution for all interconnections.

 

Corollary 3-1-2: Let the component equations be given in

' ’ U A
the form (3-1-9). Let (s D1+D2)==s O + C , D==adj. (s U'PA),

84

and d = det. (s U-tA). If for 5 equal to some real con-

stant the quadratic form

xT [—CD dU] E1 EZT —(ch)T

x #‘o
dU

for all real X f 0, then any system having these compo-

nent equations has a unique solution.

Proof: It will be shown that the hypothesis implies that
the matrix (3-1-10) is nonsingular.
If the matrix in (3-1-10) is singular, then there is

a non-zero vector ZlT(s) such that

T
21 (s) [(5 D1 +D2) El E2] (3-1-19)

is orthogonal to

 

 

71 o a“
o A o (3-1-20)
0 0 SJ

T _
Therefore, Z1 (5) (s Dl-tDZ) - O

and
T

o (s) ECD dil

since the rows of [-CD dU] Span the orthogonal complement

ZlT(5) : Y

of the columns of (s D1-+D2).

85

From relations analogous to (3-1-17) it follows that

[mm

T
YOT(S) I-CD dU] E E T dU ] yo(s)==ZZT(s) BAT 23(5) = O

1 2
(3-1-21)
If 21(5) is chosen so that yo(s) is a minimal degree
polynomial vector in s, then yo(s) is non-zero for all
S, which contradicts the hypothesis. Therefore, the system

has a unique solution for any graph.

 

If, in particular, [El(s) E£T(Sg is negative
definite for some real 5, by Theorem 3-1-2 the system has

a unique solution. When a system contains some Semi-definite

 

components, (those where E1 EZT is a semi-definite matrix),

 

Theorem 3-1-2 can be extended to yield a new sufficient con-

dition for a unique solution.

Corollary 3-1-3: Let the component equations be given in

 

form (3-1-7), and let the components be subdivided into two
classes (for s==c (a real constant)),

1. Those where
XT El' (c) EZ'T (c) X < O, for real X # O, and

2. Those where

X T T

I!
1 El (C) 32"

(c) X1 5 O, for real X1, and

86

q

[El"(c) E2"(c)'Jhas maximum row rank. If there exists no
circuit or cutset in G composed entirely of edges corre-
Sponding to the components of El"(s), the system {C, G, B}

has a unique solution.

Proof: Write the component equations in a direct sum as

follows
E1'(s) O 2'(s) 0

X1-

Y = F1(t) (3—1—22)
0 E1”(S) o E2"(s)

The matrix of equation (3—1-8) must be Shown to be

non-singular. If it is singular, then by Theorem 3-1-2,

Z
l
for s = c, there exists a non-zero real vector 2 =
22
such that
T El'CC) EéT(C) 0
Z Z = O (3-1-23)

T
H H
0 E1 (c) E2 (c)

Expanding (3-1-23):

ZlT El'(c) E2'T(c) 21+22T E1"(c) E2"T(c) 22 = 0

If Z is non-zero, equation (3—1—23) is less than

1
zero. Therefore Z1 is zero and 22 is non-zero. By the

proof for Theorem 3-1-2, and 3-1-17, 2 can be chosen such

that

87

E '(c) O
1
2T = Z3T B
O E ”(c)
1
and
E ‘(c) 0
2T 2 = 24T A
O E2”(c)
for some real 23 and Z4.
Since 21 = 0 it follows that
ZZT [o El”(c)] = 23T B
and (3-1-24)

T ,, T
22 [0 E2 (c)] 24 A
But since 22 is non-zero and the component equa—
tions have linearly independent rows, both ZZT E1"(c) and

22T E2"(c) cannot vanish simultaneously. If 2 [O E1"(c)]

2
= Z is not zero, then in the terminology (of Chapter II) it

5

is a non-zero chain in the co-graphic chain vector Space N,
Spanned by the rows of the representative matrix B. Hence
there exists an elementary chain in N whose domain is con-
tained in I25|. But by Theorem 2-2-1 and the fact that N
is a co-graphic vector Space, the domain of each elementary
chain of N is a circuit of the graph. Therefore, there
exists a circuit of the graph Whose edges correSpond to semi-

definite components only, contrary to hypothesis. This con-

tradiction establishes the Corollary.

3

 

88

Remark: The non-existence of a circuit or cutset of nega-
tive semi-definite components is equivalent to the existence
of a forest and a co-forest of negative definite components
by Lemma 2-2-2 and definition 2-2-1.

A necessary and sufficient condition for a unique
solution for systems containing negative definite and semi-

definite components only, is given next.

Theorem 3-1-3: Let the direct sum of component equations,
CE, be written in form (3-1-22), where for all real 5 on
some interval I1, (I1 is not a point interval)
1. xT El‘(s) 1323(5) x < o for all real x 7! o
,T

T
2. X1 El"(s) Eb (5) X1 5 O for all real X1.

Let S» denote the set of edges corresponding to the compo-
nents of El"(s) and E2"(S). For a given graph G, let

N be the co-graphic subSpace with representative matrix

B, and N1 be the graphic subSpace with representative
matrix A. Let B1 be a representative matrix of the sub—
space N X S, (as defined in Chapter II) (i.e., the subspace
spanned by the circuits composed of edges of components
correSponding to El"(s) and E2”(s)). Let A1 be a
representative matrix of the subspace Nl X S (i.e., the
subSpace Spanned by the cutsets composed of edges of com-
ponents corresponding to El"(s) and E2”(s)). Then the
system -{CE, G, F:} has a unique solution if,and only if,

the matrix

-19

89

E1”(s) E2"(S)
B1 0 (3-1-25)

L 0 A1 .—

 

 

has linearly independent rows.

Proof: Tutte, [TU-4], has Shown that the orthogonal comple—
ment of (N X S) is (Nl - S). By its definition, (Nl X S)

is contained in the subSpace (N S). Therefore, the last

1
two rows of (3-1-25) are of maximum rank and have linearly
independent rows. Also B1 can be obtained directly from

A by considering the submatrix of A made up of the col-

umns of S and taking its orthogonal complement. Similarly

Al can be obtained directly from B.
When E1 is the direct sum of El' and E1" and
E2 the direct sum of E2' and E2" the system -{CE, G, R}

has a unique Solution if,and only if,the coefficient matrix
of (3—1-8) has a determinant that does not vanish identically.

Suppose the system has no unique solution. Then,
following the proof of Corollary 3-1-3, for every 5 on 11’
there exists some row vector 22T(S) such that

T T _

22 (S) El”(s) E2” (5) 22(5) - 0,

22(5) is non-zero for all but a finite number of points on

11, and

90

p

z T(s) o El"(s)]

2

Z3T(s) B
(3-1-26)

F

ZZT(S) O E2”(si

L.

Z4T(s) A

 

By (3-1-26), the non—zero entries of 23T(s) B correspond
to edges of the components El"(s). Therefore, Z3T(s) B
is a chain of N X S, and there exists some row vector

25T(s) such that
T [J
Z3 (5) B 25 (s) 0 B1
and
T _ T
22 (s) El"(s) - 25 (5) B1“
Similarly, there exists a 26T(s) such that
Z4T(s) A = 26T(s) A1
and
Z T(s) E ”(s) = Z T(s) A for some 2 (s) and Z (s)
2 2 6 l 6 ’ 2

does not vanish identically on I.
It follows that the rows of (3-1-25) are linearly

dependent for s on I Since the determinants of all

1.
maximum order matrices of (3-1-25) are polynomials, which
vanish for an infinite number of points of 11, they are

zero.

91

Conversely, suppose the rows of (3-1-25) are linearly

dependent. Then there exists a non-zero row vector

%7T(s) 28T(S) 29T(s)] such that

Z7T(s) E1"(s) -28T(s) B1

and (3-1-27)

T H T
27 (5) E2 (s) -29 (5) A1

Since [El"(s) E2"(s):], B1, and Al, each have linearly
independent rows, 28T(s) B1 or 29T(s) A1 or both, is non-
zero, and Z7T(s) is non—zero. Without loss of generality,
suppose 28T(S) B1 is non-zero.

Now every vector of B1 is a vector of N X S, so
28T(s) [5 B3 = 210T(s) B for some non-zero row vector

zloT(S).

Therefore
T = T
27 (s) [O El”(si] ZlO (S) B
Similarly

Z7T(s) [o E2”(s)] 211T(S)A

where leT(S) is some row vector, possibly zero.
Rewriting (3-1—8) for this system, and premultiply-

ing by [O Z7T(s) -ZlOT(S) -leT(s)] gives

 

-22

92

I:OZ7T(S) -ZlOT(s) -leT(s):l PE1'(S) O E2‘(s) O
I o El”(s) o 52"(5)
B O

L O A __

(3-1-27)

 

 

from which it follows that (3-1-8) is singular and the system

{CE, G, F}> has no unique solution.

 

Remark: By (2-2-2) the graphs of N X S and N1 X S are
G ° S and G X S reSpectively.

Notice in the second part of the proof of Theorem
3-1-3, no use is made of conditions (1) and (2) of the
hypothesis. The second part of this theorem is, therefore,
valid for all Systems and is worth rephrasing as a separate

corollary.

Corollary 3-1-4: Let the direct sum of the component equa-
tions be written as in form (3-1-22). Let S, N, N1, B, B1,
A, and A1 be as defined in Theorem 3-1-3. If the matrix
(3-1-25) has linearly dependent rows, the system has no

unique solution.

 

Corollary 3-1-4 is important to the synthesis problem, and
indicates that if a given subassembly has no unique solution,
the circuits and cutsets involved in the dependent set

(3-1-25) must be altered.

93

Corollary 3—1-5: Let the direct sum of the component equa-

 

tions be written in form (3—1-23), where El" and E2" are
constant matrices. Suppose for some real number c
1. XT El'(c) EZ'T(c) xw<o for all real x #‘o,

2. XT E1" E2”T x 5 o for all real X.

Let S denote the set of edges correSponding to the compo-

nents of El" and E2". Let N, N B, B A, and A1 be

1’ 1’
defined as in Theorem 3-1-3. Then the System has a unique

solution if,and only if,the matrix

”E11: E2“?
131 o (3-1-28)
EC Al._

 

 

has linearly independent rows.

Proof: Identical to Theorem 3—1-3 where the constant c is

substituted for the interval 11’

 

Corollary 3-1-6: Suppose, just for this corollary, driver

 

type elements only are allowed to compose E1”(S) and
E2"(S). Let the direct sum of the component equations be
given in form (3-1-22), where for some real number c,

XT E1'(c) E2'T(c) X # O for all X #’0. Then any system
containing component equations (3-1-22) has a unique solu-
tion if, and only if, there exists no circuit of across

drivers nor cutset of thru drivers.

94

Proof: The conditions of Corollary 3-1-5 are met. There-
fore, the system has a unique solution if, and only if,
(3—1-28) has linearly independent rows. For these component

equations rewrite (3-1-28) as follows:

(3-1-29)

 

 

Let P be the edges corresponding to the across
drivers. Obviously, the rows of (3-1-29) are linearly inde-
pendent if, and only if, there exists no non—zero vector in
(N X S) X P or (Nl X S) X (S-P). There exists a non—zero
vector in (N X S) X P or in (N1 X S) X (S-P) if, and
only if, there exists an elementary vector in (N X S) X P
or in (N1 X S) X (S-P). There exists an elementary vector
in (N X S) X P or in (N1 X S) X (S-P) if, and only if,
there exists a circuit of elements of P (or a cutset of

elements of (S-P)).

 

Suppose the system is composed of linear components
(3-l-l) but which are entirely algebraic and time-varying.
After suitable manipulation the system can be described by
(3-1-8) and, of course, the necessary and sufficient condi-
ition for a unique solution for t = c is that the deter-

minant not vanish for t = c. These systems were studied

 

95

in [WI-l]. The following corollary is a useful addition to

the results of [WI-l].

Corollary 3-1-7: Suppose the component equations, CE, are

 

algebraic and time-varying linear, and El(t) and E2(t)
are composed of the direct sum of E1'(t) and El"(t) and
E2'(t) and E2”(t) reSpectively. Let G, S, N, N1, B, Bl,
A, and Al be as in Theorem 3-1-3. Then, for each t such
that:

1. XTEl'(t) EZ'T(t) x < o for all real x #‘o,

T

2. X1

E1"(t) E2”T(t) x1 :_o for all real x1,

the system <{CE, G, F:} has a unique solution if, and only

if, the matrix

PEI-M(t) E2”(t)
Bl

L. O . Al -

 

 

has linearly independent rows.

Proof: Similar to Theorem 3-1-3 with obvious changes of

notation.

 

By the following Lemma and remark, the matrix of
(3-1-25) has linearly independent rows if, and only if, a

matrix with fewer rows has linearly independent rows.

 

96

Lemma 3-1-2: Let

 

 

 

El(s) E2(s) A T O
2
E = Bl O and KO = [El(s) E2(s)] T
0 B2
__0 Al

where Al and B1 have linearly independent columns and A2
Spans the orthogonal complement of the rows of B1, B2 Spans
the orthogonal complement of the rows of Al. Then E has
linearly independent rows if, and only if, KO has linearly

independent rows.

Proof: If E has linearly dependent rows, there exists a

Z
l . . .
non—zero column vector, , With polynomial entries
22
such that
B O
z T E (s) E (s) = z T l (3—1—30)
1 l 2 2
O A1
The vector Z1 is non-zero since the matrix on the right of
_ Z1
(3-1-30) has linearly independent rows and is non-zero.
‘ Z
2
Also
2 T
T Bl O —] A2 0 _
22 T _ O
0 A1 O B2

by hypothesis. Therefore,

97

and Ko has linearly dependent rows.
Conversely, if Ko has linearly dependent rows,

there exists some non-zero column vector 21 such that

T _
Z1 KO ~ 0
B O
or z T E (s) E (s) = z T 1
1 1 2 2
0 A1
for some row vector ZZT. Therefore,

T T. _
[21 22:] E - O
and E has linearly dependent rows.

Remark: Let the component equations be given in the form
(3-1-22) and let G, S, N, N1, Bl, and A1 be defined as in
Theorem 3-1-3. Let A2 be the representative matrix of

(N1 - S) and B be the representative matrix of (N - S).

2
By [TU-4], (N1 ° S) is the orthogonal complement of
(N X S), and (N - S) is the orthogonal complement of
(N1 X S). Then by Lemma 3-1-2 it follows that (3-1-25) has
linearly independent rows if,and only if,[E1"(s)A2T,E2"(s)Bzf]

has linearly independent rows.

 

Definition 3-1-3: A set of component equations in the form

E1(S) 0 X F1(t)

98

where E2(s) is the orthogonal complement to E1(s) for

every 5, is called a perfect coupler component.

 

If the components represented by E1"(s) and E2"(S)
in Theorem 3-1-3 are perfect coupler components, then by a
procedure analogous to that used in Lemma 3-1-2 it can be
shown that the system has a unique solution if, and only if,

the matrix

'

Bl E2"(s):l T O .1

c 0 A1 E1149]?
..J

has linearly independent rows. Since this matrix usually

(3-1-31)

 

 

has very few rows, the independence of the rows is easily

checked.

Corollary 3-1-8: Let CE, G, S, N, N1, B, Bl, A, and A1 be
as in Theorem 3-1-3. Let E be a non-singular submatrix
(i.e., a matrix with a non-zero determinant) of

[31"(5) E2"(s)] . Let S1 be the edges of G correSponding
to the columns of E1" in E. Let 82 be the edges of G
correSponding to the columns of E2” in E. If no edge of
$1 is in a circuit of G - S and no edge of S2 is in a
cutset of G X S, the system ‘{CE, G, Fj}, has a unique

solution.

99

Proof: By Theorem 3-1-3, ‘{CE, G, P}: has a complete and
unique solution if, and only if, (3—1-25) has linearly inde-
pendent rows. Under the hypothesis and by (2-2-2), upon

permutation of its columns, (3-1-25) becomes

D E D E
- 4
3 4 7 <3—1—32)

 

 

o
_o o 0 A2

where D1 and D2 correSpond to the edges of S1 and $2

reSpectively and B2 and A2 are suitable submatrices of

B1 and Al reSpectively.

D1 Dz
The matrix 2 has linearly independent rows
D D
‘3 B o
O O 2 O O
by hypotheSis. The matrix . has linearly inde-

O A .
pendent rows by definition. Therefore (3-1—32) has linearly

independent rows and ‘{CE, G, E} has a unique solution.

 

Theorem 2.4 of [WI-l] is a Special case of Corol-

lary 3-1-8.

Corollary 3-1-9: Let the component equations, CE be given
in the form (3-1-22), where E1'(s), E2'(s), E1"(s), E2"(s)
are as in Theorem 3-1-3. Let the semi-definite component
equations*of CE be called C2 and the edges correSponding

to the C2 variables be called 5. If either the subsystem

 

*See page 85.

-30

100

{C2, G’X S, F]’ or {C2, G - S, E}' has a unique solution,

the system {C, G, E} has a unique solution.

nggf: By (2-2-2), the subsystem {C2, G X S, E}, corre-
Sponds to the vector Spaces (N ' S) and (N1 X S), and
the subsystem {C2, G - S, E} corresponds to the vector
Spaces (N X S) and (N1 - 5). (Here the notation of the
paragraph preceding definition 3-1-3 is used.)

By Theorem 3-1-3, the System has a unique solution
if, and only if, (3-l-25), has linearly independent rows.
But (N X S) is contained in (N - S) and (N1 X S) is
contained in (N1 - S). The theorem follows immediately by
noting that if the rows of the representative matrix of
{C2, G X S, F}- or {C2, G ° S, B}» are linearly independent,
the rows of (3-1-25) are linearly independent, since these

are a subset of the rows of the above.

 

Remark: Indefinite components (i.e., those where E E T

1 2
is an indefinite matrix) can be included in each of the

above theorems and corollaries if it is assumed that
a. each edge corresponding to an indefinite compo-
nent is either
1) in a circuit of across drivers, (call all
these edges 51) or,
2) in a cutset of thru drivers, and (call these

edges 52),

101

b. the indefinite component equations are such that
they can be written explicit in the thru variables
corresponding to the edges of S1 and the across
variables correSponding to the edges of $2,

In this case, the circuit and cutset equations to-
gether with the driver components uniquely determine the
across variables correSponding to the edges of S1 and the
thru variables correSponding to the edges of 82. From the
component equations the remaining variables are given explic-
itly. Therefore the thru and across variables for these
edges can be treated as known, and the edges removed from

discussion.

Algorithms

The following definitions and theorems, besides be-
ing useful for analysis, are the foundations of an algorithm
for determining the class of all graphs that yield a unique
solution for a given set of component equations.

In the following, again assume there are no driver
type components, (3-1-1), since all graphs yielding a unique
solution can be obtained from the graphs of the system with-
out drivers by the techniques of Theorem 3-1-1 and Corollary
3-1-1.

Let A be a representative matrix for the graphic

vector Space N1.

102

Definition 3-1-4: Let T be the Set of all forests of a
finite graph G. Let every tiéT be assigned a distinct
positive integer. Let S = {flq -l:}.
The function sgn T [i, j]: (TXT)->S, is defined
as follows:
sgn T [i, j] = +1. if forest ti and forest tj
have the same Sign determinant

in the incidence matrix.

sgn T [i, j] -.1 otherwise.

Therefore, sgn T [i, j] defines a partition of T

into two disjoint classes.

Definition 3-1-5: Let the columns of A be numbered in the

natural order. The function Sgn [i]: T——>S, is defined as

follows:
sgn [i] = +1. if the sum of the column num-
bers of A corresponding to
the edges of tree ti is even.
sgn [i] = -1. otherwise.

By Theorem 2-1-3, definition 3-1-5 correSponds to determining
the relative determinantal Sign between a forest and its

co-foreSt.

Definition 3-1-6: The Signed summation of all tree prod-

ucts is defined when the admittance matrix, Y exists

adm.’

103

(i.e., when in (3-1-7), E2=IL and Yadm. = El), and is

2: (sgn T [i, j]) [(det. Yiégfj)) + (det. Yigifi){l
i>j

'9 :5 (det. Yééifj))
i

Yum)

where
adm.

is the submatrix of Yadm composed of the

rows correSponding to the edges of the forest i and of
the columns correSponding to the edges of forest j, both

taken in their natural order.

Definition 3-1-7: The Signed summation of all co-tree prod-

 

ucts is defined when the impedence matrix 2 exists

imp.’

(i.e., when in (3-1-7), E = U, and Zim

l = E2), and is

p.

:2 (sgn T [i, j]) (sgn [i]) (Sgn [j]) [(det. Z(i)(j))

imp.
i>j
(j)(i) (i)(i)
+ (det. zimp. ) + (det. Zimp. )
i
where ZE$£<J> is the submatrix of Zimp composed of the

rows correSponding to the edges of the co-forest of forest i,
and of the columns correSponding to the edges of the co—forest

of forest j, both taken in their natural order.

104

Definition 3—1-8: The Signed Summation of all [tree -

 

co-tree] products is defined when the eomponent equations

are written in the form:
RC5) 1,11 + 131(5) x + 122(5) Y = F4(t) <3-1—32)

(This form includes both (3—1-9) and (3-1-7)), and is

2' sgn T [i, j] Sgn [j] (det.[R El(i) E2(j)])
i,j
where El(i)

(J)

are columns of El correSponding to tree (i),
and E2 are the columns of E2 corresponding to co-tree

(j), both taken in their natural order.

Theorem 3-1-4: Let

 

 

 

2
K0 = o B o
o o A

L J

where B and A are given in (2-3-1). Then det. K0 is
equal to (:51) times the signed summation of all [tree -

co-tree] products of the graph correSponding to B and A.

Proof: By Lemma 3-l-l,
det. KO = (1 l) det. E
where

= ' ’ 1
E [B E1 E%] U o o

o (3-1-33)

 

 

105

But by the Cauchy-Binet determinant eXpansion,

det. E = Z (det. A(i)) (det. B(j)) (det. R B1(i)B2(3))
ivj
(3-1-34)

where A(i) and El(i) are a set of columns of A and E1
(reSp.) correSponding to the sequence (i), and B(j), and
E2(j) are a set of columns of B and E2 (reSp.) corre-
Sponding to the sequence (j). All columns are taken in
their natural order. The sequences (i) and (j) are both
strictly monotonic. Now A and B are regular so they can
be chosen so that every square submatrix of maximum order
must have a determinant _:l. or 0. By Theorem 3.2.2 of
[FR-l] (see also [SE-1]), every determinant of maximum rank
minor of A correSponds to a forest, and every determinant

a maximum rank minor of B correSpondS to a co-forest. It

follows from Definitions 3-1-4 and 3-1-5 that
(det.A(i))(det. B(j)) = (Sgn.T[i,j])(sgn.[j]) (3-1-35)

Substituting (3-1-35) into (3-1—34) and using defini-

tion 3-1-8, the theorem follows.

 

Corollary 3-1—10: If the component equations are given in
form (3-1-32), then there exists a unique solution for all
system variables if, and only if, the Signed summation of all
[tree - co-tree] products of the graph is not identically

zero.

106

Theorem 3-1-5: If the component equations are given in form
(3-1-7), where El(s) = U (unit matrix), and the entries of
E2 are rational functions of s, then there exists a unique
solution for all system variables if, and only if, the signed
summation of all co-tree products of the graph is not identi-

cally zero.

Proof: By Lemma 3-l-l, the system has a unique solution if,
and only if, the matrix
U E2(s) BT
(3-1-36)
B 0
is non-singular. But (3-1-36) is non-singular if, and only

if,
F = B E2(s) BT
is non-singular. By the Cauchy-Binet expansion,

det. F= Z (det. 3‘”) (det. E2(i)(j)) (det. BUD? o, <3—1-37)

1:J

l is a set of columns of B correSponding to
sequence (i), E<i><j> is the submatrix of E with rows
correSponding to sequence (i) and columns corresponding to
sequence (j). All columns are taken in their natural order.
(i) and (j) are both strictly monotonic sequences of posi-

tive integers. Choose B so that every square submatrix of

maximum order must have a determinant :1 or 0. (Theorem

107

2-2—2.) By [FR-l], [SE-l], every determinant of a maximum
rank minor of B correSponds to a co-forest. Therefore

from Definitions 3-1-3 and 3-1-4,
(det. 13(1)) (det. 3‘”) = (sgn. T [i,jD (sgn. (1)) (sgn. (1))
(3-1-38)

Substituting (3-1-38) into 3-1-37), making use of the
fact that (sgn. T [i,i]) = l, and applying Definition

3-1-7, the theorem follows.

 

Corollary 3—l-ll: If the component equations are given in

 

form (3-1-7) where E2(s) = U and the entries in E1(s)

are rational functions in s, then there exists a unique
solution for all system variables if, and only if, the signed
summation of all tree products of the graph is not identically

zero .

Proof: Identical to Theorem 3-1-5, with obvious changes of

notation.

 

Remark: By Lemma 3-1-1, det. F in (3-1-37), is equal to
(+1)det. K
— 0

Theorem 3-1-4 has an immediate practical application
in the analysis of general linear Systems. In topological
analysis, (see [SE-1]), formulas for network determinants

are confined to the components where the impedance or

108

admittance matrix exist. Theorem 3-1-4 on the other hand,
applies to network determinants with no restriction on the
types of components.

Theorem 3-1-5, and Corollaries 3-1-10 and 3-l-ll,
provide the basis for two algorithms that generate the graphs
of all systems that have a unique solution.

Corollary 3-1-10 immediately suggests the following

algorithm.

Algorithm-l

 

Let the component equations be given in form (3-1-32).

Consider the matrix of order (Jg+-n)x(A!+ 2n)
[R(s) El(s) E2(s)] (3-1-39)

obtained from the matrices of (3-1-32). Suppose E1 and E2
each have n-columns and K is the set of columns from El.

Let the columns of E and E be each numbered from 1 to

l 2

n in their natural order. Determine the values of all

2n
n

 

 

(= QED—'2) determinants of the set L of maximum
(n!)

order Square submatrices of (3-1-39), where each submatrix
in L contains all columns of R.

Let those submatrices of L having i columns from

K be designated Li' Each Li has n)2 elements and

l

 

n
L} Li = L. For each matrix, B, of Li, let (k)
i=0 .

109

represent the sequence of columns of B from E and (j)

l?

the sequence of columns of E not in B.

2

Now proceed as follows for each i:

1.

For a square matrix Ji made up of the determi-
nants of each element of Li’ where the rows of
Ji correspond to the sequences (k), and the

columns of Ji correSpond to the sequences (j),
and if (k) = (j), the correSponding entry is on
the diagonal of Ji' Therefore, the (k,j) entry
of Ji correSpondS to the sequences (k) and

to the sequence (j).

For each column of Ji’ evaluate the sum
i

2(3):: in where (j)=(jl,...ji). If the
h=l

sum is odd, change the Sign of all entries in this
column of Ji. (By definition 3-1-5, this corre-
Sponds to evaluating the function sgn. [j].)

Find all solutions to the equation
x Ji XT = o (3-1—40)

where X is a row vector, with all entries +1,
-1, or O of dimension (2) .

The rig entry of X correSponds to the sequence
representing the rEE row of Ji' Each such
sequence correSponds to a unique canonical basic

form where the columns of K are the basic

110

unities. Therefore, every vector X corresponds

to a unique homogeneous multilinear form, Ax,
of degree i. Thus for each solution, X, to
(3-1-40), form AX'

5. By the techniques of Corollaries 2-1-1, and
2-1-2, examine each AX obtained above to see
whether it is simple.

6. Examine each Simple AX to determine whether it
contains a sub-sum with a complete-5 or Thompson
reduced residue set. If AX does not contain a
sub-sum with either of these, A is graphic,

X
by Theorem 2-2-12.
Conversely if a Simple AX does contain
such a sub-sum, then AX is not graphic.
. 7. The set of all graphic simple AX represents the

set of all graphs that yield no unique solution

to the linear system.

 

Remark 1: Since (3-1-40) is a quadratic form, the solutions
of (3-1-40) may sometimes be more easily found by making Ji
upper triangular. This can be accomplished by simply adding
the (k,j) entry to the (j,k) entry, k>j ,and then substi-
tuting zero for each entry below the diagonal of Ji' Also
since the component equations are a direct sum, most of the

entries of Ji are zero.

41

111

Remark 2: An analysis of the negative definite, semi-
definite, and indefinite portions of Ji in (3-1-40) pro-
vides a fundamental insight into the uniqueness problem for
linear systems. Possible system behavior characteristics
are also found in the matrix Ji as (3-1-40) represents the

system determinant by Theorem 3-1-4; i.e.,

T _

x Ji x — (I) det. K (3-1-41)

0'
The matrix Ji is a function of the component equations
only. The vector X is a function of the graph only.
Consequently, it is believed that (3-1-40), when thought of

as a system determinant, is a fundamental structural tool in

the synthesis of linear Systems.

Remark 3: The solution of equations Such as (3-1-40) with
integer constraints has been studied by many authors in var-
ious facets of quadratic and nonlinear programming (see
[GR—1]).

Step 3 can be changed into a programming problem
Since (3—1-40) can be squared and the resulting function

minimized, Subject to the constraints on X.

Remark 4: Equation 3-1-41 has deeper Significance than the

algorithm mentions. Suppose that a given system performance
is desired (as reflected in the system determinant, for

instance, certain eigenvalues may be wanted). Then given a

-42

112

set of components with parameter and unrestrained intercon-

nections, J- can be determined as a function of the param-

i
eters from the component outer products for each i.
By solving (3-1-41) with the desired determinant

either an exact solution or a ”best fit" in the squared

sense of Remark 3 can be obtained.

Remark 5: Step 5 can be altered if a given entry of X is

assumed to be non-zero. Then the conditions given in Corol-
laries 2-1-1 and 2-1-2 can be stated in terms of

[(2) -l-i(n-i)] quadratic equations. The resulting equa-
tions can be solved simultaneously with (3-1-40). However,

because of the large number of equations and the assumption

’ of a non-zero entry of X it seems that the method given in

step 5 is preferable.

Remark 6: The entire algorithm can be fitted to machine

computation since Grassman algebra (used in steps 5 and 6)

can easily be performed by a computer.

Remark 7: The work of evaluating the (a?) determinants

can be performed by Grassman algebra, since by (2-1-2), the
(a?) determinants are simply part of the Grassman outer
product of the subSpace Spanned by the rows of (3-1-39),

with the columns as the basic unities.

113

Remark 8: Equation 3-1-41 has profound applications to
t0pologica1 analysis since in this case the graph is given
so X can be found as the outer product of the graphic
vector Space N1, and Ji can be determined immediately

from the outer product of the component equations.

Remark 9: In step 3 of the algorithm, if all primitive
vectors, X, are found that satisfy (3-1-40), then all
unions of disjoint primitive vectors are also solutions.

In cases where an impedance or admittance matrix
exists, R(s) in (3-1-39) has no columns, and the determi-
nants involved can be evaluated with smaller submatrices.
The following algorithm is the adaption of Algorithm 1 to

these cases.

Algorithm-2

 

Let the component equations be given in form
(3—1—7), and assume the impedance (admittance) matrix exists.
(See definitions 3-1—6 and 3—1-7.) Suppose E1 and E2
each have n-columns and number them in both E1 and E2
from 1 to n in their natural order. Evaluate the (a?)
determinants of all square submatrices, L, of the imped-
ance matrix E2 (or of the admittance matrix E1, if the
admittance matrix exists).

For the admittance matrix let those submatrices of

L of order i be designated Li' For the impedance matrix,

114

let those submatrices of L of order (n-i) be designated

9‘2

n
L-. Each Li has (1) elements and L] Li==L. For the

i=0

admittance matrix, for each matrix, B, of L let (k)

1’
represent the sequence of rows of B, and (j) the sequence
of columns of B. For the impedance matrix, and for each
matrix, B, of Li, let (k) represent the sequence of
rows not in B, and (j) the sequence of columns not in B.
Now proceed as follows for each i:
1. Form a Square matrix Ji made up of the determi-

nants of each element of Li, where the rows of

J .

1 correSpond to the sequences (k), and the

columns of Ji correSpond to the sequences (j),
and if (k) = (j), the correSponding entry is
on the diagonal of Ji'

2. If this algorithm is being carried out on the
admittance matrix, skip this step. If this algo-
rithm is being carried out on the impedance matrix,
for each column of Ji’ evaluate the sum 2 (j)
as in (2) of Algorithm-l. If the sum is odd,
change the sign of all entries in this column
and in its correSponding row of Ji' (This corre-
Sponds to the evaluation of sgn. [j] in Defini-

tions 3-1-5 and.3-l-7.)

115

3. Find all solutions to equation (3-1-40) where X
is a row vector with all entries +1, -1, or O.

4. Same as (4) of Algorithm-l.

5. Same as (5) of Algorithm-l.

6. Same as (6) of Algorithm-l.

7. Same as (7) of Algorithm-1.

 

Remark 1: By the remark after Theorem 3-1-5, and Corollary
3-1-11, (3-1-41) is the system determinant when the impedance

or admittance matrix exist.

Remark 2: The solution of (3-1-40) and the work of step 5
are simplified when all components are two terminal. Then
Ji is diagonal for all i, so Signs of the entries of X
have no effect on (3-1-40) and step 5 can be performed in

@od. 2)arithmetic.

Suppose the component equations are given in form
(3-1-7). Each of the above algorithms for a graph of n-
edges requires the evaluation of (a?) determinants of
order less than or equal to n. An alternate method examines
the determinant of a matrix of form (3-1-8), or of the form
of K0 in Theorem 3-1-4, for every graphic subSpace N1.
(Each of these latter matrices has order 2n) and the num-

ber of different graphic subspaces for n=>4 is far greater

than (a?) as the following table shows.

116

TABLE (3-1-1)

 

 

no. of different graphic

 

subSpaces for non- 2n
n = no. of edges separable graphs n
2 2 6
3 8 20
4 64 7O
5 832 252
6 10,336 924
7 139,904 3,432

 

Even this table is not a complete comparison since
the number of non-separable graphs on n-edges are only a
portion (about one-third in the above examples) of the total

number of all graphs on n-edges.

Example: Of Algorithm-2:

Suppose the direct sum of the impedance matrices is:

 

:2
S
-552+l
-l 5
4 -l
-2
L_. 1

 

Since this matrix is non-singular, if each edge of

the graph is a self-loop the system has a unique solution.

117

Also, if all edges of the graph form a forest, the system

has a unique solution. The matrices J1, J2, J3, J4, and

 

J5, defined by the algorithm are:
(23456) (13456) (12456) (12356) (12346) (12345)
J51:
—6 , —552+1, —1, —1, —2, 1,
s
(12456) (12356)
-9
(3456) (2456) (2356) (2346) (2345) (1456)
J4:= 2 2
'6('55 +1): 9 2 9, g , :2, “('55 +1):
5 s s s s
(1356) (1346) (1345) (1256) (1246)
-(-5$2+l), -2(-552+l),+(-552+l), ~19, 2,

(1245) (1236) (1235) (1234) (2456)(2356)

-1, 2, -1, —2, +54
S

 

J

(1456) (1356) (l246)(1236) (1245)(1235)

-9(-5s2+1), +18, -9

118

 

(456) (356) (346) (345)
J :
3 {}6(-552+l), 6(-552+l), l2(-552+1), ;g(—552+l),
S S S S
(256) (246) (245) (236) (235) (234) (156)
.114, s2, 9, s12. 2. 12, -19<-552+1>.
S S S S S S
(146) (145) (136) (135)

2(-552+l), -l(-552+l), 2(—552+1), —1(—552+1),
(134) (124) (126) (125) (123) (456)(356)

-2(_552+1), 2, 38, —19, 2, +54 (-552+1),
. S

(246)(236) (245)(235) (146)(l36) (145)(135)

slgé, .123, +18(-552+1), —9(—552+1),
S 5
(124)(123)
18
(56) (46) (45) (36)
J :
2 {ilflC-552*1): ;1§(-552+1>, 9(-552+1), .;1§(-552+1),
S S S S
(35) (34) (26) (25) (24) (23)

6(-552+1), lg(—552+1), -228, 114, —12, -12,
S S S S S S

(16) (15) (14) (13)
38(-5$2+l), -l9(-5$2+l), 2(—552+1), 2(-552+l),

119

(12) (46)(35) (45)(35) (24)(23) . (14)(13)

38, -lO8(-5s2+l), ,153(-552+1), -108, +18(—5$2+l)
S S S
(6) (5) (4) (3)
J‘ =
1 -228(-5$2+l), llfl(-552+l), :l2(-552+l), :12(-552+l),

S S S S
(2) (l) (4)(3)

-228, 38(-5$2+l), —108(—5s2+1)

S S

where each of the above Ji's has had its sign changed as
in step 2, and made upper triangular. For shortness of nota-
tion, Ji is not written in matrix form and only the non-
zero elements of Ji have been given together with their
correSponding sequences. The diagonal elements of Ji
refer to only one sequence.

The work to obtain Ji can be Shortened by using
the results of Ji-l'
Substituting J5 into (3-1-40), solving for X,

and forming AX gives thefknurmultilinear forms:

+1 +1

Z12456 - 212345’ +1

212356 11 212345

where zij = Z; Zj. This means that edge 6 and edge 3 or 4
cannot form both a cutset and a circuit. Proceeding analo-
gously, by steps 3 and 4, the remaining solutions to (3-1-40)

yield:

from

From

120

J4:

(+22456iz2345)'(*z2356122345)’(+21456121345)'(+21356

121345)’(+21246121234)’(+zi236121234)’(+22456122345

),(

+
121456121345)’(22456322345121356321345 22456-22345

121246121234)'(22456122345121236121234)’(22456122345

),(

+2 +2 +2 +2 2 +2 +2 +2
- 1456- 1345‘ 1246‘ 1234 2456’ 2345- 1456— 1345

),( ),

+ + + + + + +
-21236-21234 22456-22345-21356-21345-21246—21234

(22456122345121356121345121236121234)’(22356122345

121456121345)’(22356122345121356121345)’(22356122345

(

121246121234): z2356322345121236121234)'(22356122345

121456121345121246121234)+(22356122345121456121345

),(

121236121234 22356322345121356121345121246121234)’

(22356122345Izi356izi345121236121234)’(21456131345

121246:21234)’(21456121345121236121234)’(21356izl345

121246121234)’(21356121345121236121234)’

J : (+2

3 45612345)’(+2356:Z345)’(+224612234)’(+223612234)’

(+2146izl34)’(+zl36:2134)’(24561234SIZZ4612234)’

121

( ),(2 +2 +2

+
456— 345- 146-2134)’(

+ + +
Z456-2345—223612234 2456—2345
1213612134)’(24561234512246122341214612134)’(245612345

1224612234izl36izl34)’(Z4561234512236:2234izl46lzl34)’
(24561234512236i22341213612134)’(2356123451224612234

1214612134)’(23561234512246122341213612134)’(225612345
12236122341214612134)’(Z3561234512236122341213612134)’
(23561234512246:2234)’(2356123451223612234)’(235612345

1214612134)’(2356123451213612134)v<2246iz23412146izi34)+

( (

2246122341213612134)’(2236122341214612134)’ 2236:2234

3213612134)

from J : (+2 ),( )

46iz34 +2361234

from J : There are none.

Application of step 5 of the Algorithm, shows that

the following of the above forms are simple:

from J : (

5 2124561212345)’(2123561212345)

122

from J4‘ (22456122345)’(22356122345)’<Zi456121345)’(21356
121345)’(21246121234)’(21236121234)’(22456122345121456
+(an) Z1345)’(22456122345I21246 ‘ (SfD) 21234),
(2 +2 +2 + (sfn) z ) (2 +2 +2
2356— 2345_ 1356 1345 + 2356— 2345— 1236

‘ (SfH) 21234)’(21456121345121246 ' (an) 21234),

- (sfn) z

(21356121345121246 1234)

From J3‘ (245612345)’(Z356iz345)’(224612234)’(223612234)’

- (sfn) z

(2146:2134)’(213612134)’(2456iz34512246 234),

(24561234512146 ' (an) Z134>,(Z456:Z345:Z246 - (an)
Z23417-146 ‘ (5fn> 2134)’(Z356:Z345:2236 ‘ (an) 2234

12136 ‘ (5fn) Z134)’(23561234512236’2234)’(235612345

+ (sfn) z ),

:2 - (sfn) z

136 134

134)’(2246:2234:zl46

(22361223412136 * (an) 2134),

from J23 (246:234)’(Z3O:Z34)

where (sfn.) is either equal to (+1), or (-1) and is

evaluated as follows:

123

Consider the (sfn) coefficient of the basic form
zi‘jkl' (or Zijk)' Take all the residue sets of this basic
form, ignoring the elements of the residue sets which have
an (sfn) as a coefficient. Multiply the coefficients of the
two remaining elements of the residue sets to obtain (sfn).

Since there are only Six edges in the graph, the
multilinear forms contain no forbidden residue set, and are
therefore, graphic. They represent the set of graphs in
which there is no unique solution. All other graphs have a

unique solution.

Part II. Non-Linear Systems

 

The first two theorems, (3-2—1), and (3—2-2), of this
section apply to System components of Type 3 (See Chapter II,
Part 3). As will be shown in Chapter V, these results apply
also to many components of Type 2. These theorems are an
extension of the results of [MI—l] and [DU—2], to general
positive semi-definite components.

Theorem 3-2-3 and Theorem 3-2-4 are restricted to
components of Type 1. Theorem 3-2-3 and Theorem 3-2-4 are
a generalization of most known results on monotonic mappings
as found in [DU—2], [DU-3], [DU—4], [WI-l], [DE-l].
Many of the results published there are Special cases of
these two theorems.

Most of the mathematical details upon which the

results of Part II are based, are contained in Appendix B.

124

The conditions called for in the theorems are given in the
appendix.

Before giving these theorems, some pertinent defini-
tions for systems with Type 3 components are introduced.
The reader is assumed to be familiar with the definitions of
a vector Space, norm, and Lebesgue integral.

Formally, a real Hilbert Space, H, is a complete
normed real vector Space with an inner product defined on
it. A complete Space is one in which every Cauchy sequence
converges to an element of the Space. An inner product
(denoted <\,>)) on a real vector Space, H, is a symmetric
bilinear mapping from H X H into the real numbers such
that <x,)> 3 o, and llxll2 = <x,x>, (H denotes the
norm that is defined on the Space). A Banach Space is defined
as a complete normed vector Space. Therefore a Hilbert Space
is Simply a Banach Space with an inner product defined on it.

A few examples of real Hilbert Spaces are:

l. the Space ’Z2’ of sequences {71} of real numbers,

such that E; yi2 <°°, with inner product
<[Xil’ [Yib = E Xi Yi'
2. a real finite dimensional Euclidean Space in

which the inner product is the Sum of the productscfi the

coordinates for an orthonormal basis set.

125

3. the Space L2 (a,b); i.e., the set of real
valued functions y(s) of the real variable 5 such that
b
the Lebesgue integral f. y2(s) dS<;oe, with inner
a

product

b
<?(s), x(s); = 3]” y(s) x(s) ds.

4. the Space used in describing components of Type 3
is the Space L2 m(a,b); i.e., the set of real m-tuple
7
valued functions Y(s) of the real variable 5, such that

[PE yi2 (5) ds <20
a 1:

where the integral is again Lebesgue and yi(s) are the real
coordinates of the m-tuple Y(S), with inner product
<Y(s), X(s)> = [p g yi(s) xi(s) ds.
a i=1

It can be shown that 2€2 and L2 are isomorphic
and, in fact, that every separable infinite dimensional real
Hilbert Space is isomorphic to these. Also, every finite
dimensional real Hilbert Space is isomorphic to the real
Euclidean Space of the same dimension.

Lemma's B-11 and B-l2 use the concept of a direct
product of Hilbert Spaces. AS shown on (p. 303), of [RI—l],
the direct product Space, H X H, of any Hilbert Space, H,
is also a Hilbert Space defined as the set of all ordered
pairs (x,y) where foH and yEEH. The inner product on,

H X H, is defined as

126

<(X1: Y2), (X2, Y2>> : <Xl’ X2> + <Y1, y2>'

Scalar multiplication is defined as c(x,y)=(cx,cy). Addi-

tion is defined as

(X1, Y1) + (X2, Y2) = (X1 + X2, y1 + Y2)-

Higher order product Spaces are defined Similar to the above.

Components of Type 3 are either mappings from the
real Euclidean Space of dimension m into itself or mappings
from the Space Lz’m(a,b) into itself, where m may vary
from one component to another and where a and by are
finite.

Algebraic component equations of Types 1 and 2 are
examples of a mapping from Em into itself. (Em is the
Euclidean Space of dimension m.) An example of mapping
from L2,m into itself, is a mixed algebraic and integral
operator of Type 2; i.e.,

b

20(t) = a], F(Zi(s), S, t) ds + G(Zi(t), t).

Definition 3-2—1: A mapping F of a Hilbert Space H into

 

 

itself is called monotonic if <Xl -x2, F(x1) - F(x2)> 3 O

for all x1 and x2 in H. If

<%l-x2, F(xl)-F(x2)>>: c Hx1‘-x2l|2

for some constant c>O, and for x1, x26 H, F is called

strongly monotonic.

 

127

Definition 3-2-2: A mapping F from the Hilbert space H

 

into itself is said to satisfy a Lipschitz condition on D,

if
HF(X1) - F(x2)Il: cllxl — XZ'I (c = constant)

for all x1 and x2 in D. If D=H, F is said simply
to satisfy a Lipschitz condition.

Lemmas B-7 and B—8 provide a basis for examining
operators on a Hilbert Space for monotonicity. Lemma B-9
provides a practical method for examining algebraic equations,
and Lemmas B-10 and B-ll, together with the remark after
Lemma B-8 provide a basis for checking integral equations for
monotonicity. In general,Lemmas B—9, B—10, and B—ll, can be
used to examine all points x06 H that satisfy these lemmas
in a neighborhood of XO. The remaining points must be
checked by some other means.

For mappings in L2,m’ the following notation is
used in this thesis. Since a component equation is, by
definition, a set of relations between a distinguished basis
set on a finite dimensional vector Space, the set of m-tuples
that are the range of y(s)€ L2,m are considered to be the
finite dimensional vector Space. The distinguished basis set
for this Space is chosen as the orthonormal set fi=(l,0,...,0),
[32=(O,l,0,..., 0), etc. The constraint (graph) equations

are defined in terms of this distinguished basis set.

128

The component equations of Type 3 for component j

are:
ZO (s,t) = F(Zi (s,t), t) (3-2-1)
J j
where
T‘XO (s,t) 7 Yi.(5,t)
Zo (s,t) : J : Zi. (5,t) = J
j YO (s,t) J Xij(s,t)
J

 

and correSponding entries of the 20. and Zi. mj-tuples
J J

are the paired distinguished basis elements which correspond

to to the mj edges of a graph Gj and ZO,(s,t) and
J

21 (s,t) are assumed to be elements of L2 m,(a,b). The
. , J

J

variable t is a parameter of the mapping (not necessarily
time).
The constraint equations for mappings in the Hilbert

Space, L2 m are of the form given in (2—3-1), Since they

7

only relate values in the range of ZO(S,t) and Zi(s,t),

where Z and Zi are the reSpective direct sums of 20.

o
J

and 2i.-

J

In this section and in Chapter IV it is more conve-
nient to rewrite (2-3-1), in the form of the primary and

secondary variables of Frame and Koenig, (see [FR-1]).

129

Existence Theorems for Systems
of Type 3 Components
Suppose all components in the system are of form
(3-2-1). Let the topology (or interconnection pattern) of
the system graph be such that there exists a forest T for
which:
1. The direct sum of the terminal equations for all

m components in the system can be written in the form:

zsi : F1 (Zpl’ 252’ t)
sz = F (zpl, 252, t)
253 = F (Zp3’ 254’ t)
(3-2-2)
zp4 = F (Zp3’ 254, t)
zp5 = F5 (255’ t)
zp6 = F (t)
where the mapping
Fl (Zpl, 252, t)
F2 (Zpl’ 252’ t)
satisfies condition (C1) of Appendix-B for all on set I,

and the mapping

F3 (Zp3’ 254’ t)

F4 (2P3,

Zs4’

t)

130

is continuous in all variables except t, and monotonic for
all t on I.

2. The constraint equations of the system graph, G,

for correSpondence F, are of the form
35; 7211 Q12 Q13 Q14 0 Q1. 2p:
252 —QE2 o o o o Q26 ng
Zs3 :: '913 9 Q33 Q34 9 Q36 Zp3 (3_2_3)
Zs4 ‘Qi4 O —Q§4 Q44 0 Q46 Zp4
255 o o o o o Q56 zp5
_Fsg_ _;8i6 "Q26 ”Q36 ‘Q46 -Q§6 Q92__ _Ep64

 

 

 

 

 

 

where Qii is skew for i=1, 3, 4, 6.

Let Spi denote the subset of edges of B(G) corre-

Sponding to the variables Zpi for (i=1, 2, 3, 4, 5, 6).

Let sgi and 5:1 denote the subset of edges of B(G) cor-

responding to the variables Xpi and Y reSpectively for

pi
(i=1, 2, 3, 4, 5, 6).
Then (3-2-3) restricts G in the following four ways:

1. C(G ' SE6) = d (the empty set);

Y
2. B(G X Sp6)

¢;
. Y X Y = .
3. B([G (sp5 U Sp6)] X SP5) d)

X y o :
4. C([G x (sp5tj spb)] s ) d

131

This statement follows from (2-2-2) and (2-2-3), and the

fact that the remaining zeros can be obtained by suitable

choice of forest (see [WI-1]).

Note: Throughout this thesis, C(Gl) and B(Gl) represent
the circuit and cutset matroids respectively on the

graph G1'

Lemma 3-2-1: Let the component and constraint equations
for {CE, G, F]~ be given in (3-2-2) and (3-2-3) reSpec-
tively.

Then there exists a forest T2 with constraint
equations (3-2-3) in which Sp3 = O and Q44 is a zero
matrix if, and only if, the following two conditions are

satisfied:
1. B([G x (5,331 U 5:2 Usp3 U SP4 US$59] ~ (8’53 US$21» = ¢.
.2. cm; - (sglu sgzu sp3 asp. Us’gén x (55,3 Us’g.» = (2!.

Proof: Conditions (1) and (2) are satisfied if, and only if,

the following two conditions are satisfied:

3. B([G x (sglUSp3U sp4 US$60] - (8),;3 Usg4)) = £3,
4. C([G ' (SglUSp3U Sp4 U526” X (5:53 US$54” = 93-

To Show that (l) is true if, and only if, (3) is

true, let

132

Glo = [G X (SYl Usp2U5p3Usp41/sgéfl - (sX 3Usy4)
(:20 = [G X (SglUsp3USp4USé6)] - (5’1;3 US$41)

G30 = G X (sglUsp3Usp4Usg6) and

G40 2 G X (53’1 L/sp 2p3Us W4ljsgb)

Then B(G20)CB(G1 ), So if B(Glo) = o, B(GZO) =¢.

0

If B(Glo) 7’ (3, let el 7’ (Z, and ele Ble B(Glo). Then by
(2-2—2), (BlL/BZ)E B(G4O) for some set B2C1E(G). If

E SX2(](BlLJB2), then by definition of SX there is

132’

another B36 B(G4O) Such that W3(:(S L/Sp éljBlL/B2)-{e2}

x
and e16 B If e36 Sp2/]B3, for the same reason as above

30

there eXists another B46 B(G4O) such that e16 B4 and

B4c:(Sp1(/Sp 63L/B ) - {e3}u Proceeding in this fashion if
eiE (Bi/[8:2), there exists another Bi+l€ B(G4O) such

that e1? Bi+l’ Bi+1C:(Syl USY6 UBi ) - {ES} Since 8:2 is
finite, there exists some BnE B(G4O) such that e16 Bn and

B nC:(Sm [jSp 6(/Sp3[}Sp4). Therefore elE Bné B(G3O) and

eiE Bn/)(S:3US;4)E B(GZO) 7! ¢

133

It follows that (l) is true, if, and only if, (3) is
true.

The proof that (2) is true if, and only if, (4) is
true, and is identical to the above with obvious changes of
notation.

Now assume that (3) and (4) are true. By the defini-

tion of a forest and co-forest in Chapter II,
Ml/S 4l/Sp6) can be contained in a forest, T2,
and (Sy lUSP NL/ p4USY6 ) can be contained in the co-forest

of T2, since the two sets are disjoint. (See Theorem 6—10

of [SE-1].) For forest T2,Sp3 = ¢, and T2 has constraint

equations (3-2-3).

By (2-2—3) and (3) and (4) above, the matrix = O.

Q44

Q44 = o and SP3 = d in (3—2-3)

Then by (2-2—3), (3) and (4) are true.

Conversely suppose

for forest T2.

 

Theorem 3-2-1: Let the component and constraint equations

 

for '{PE, G, B} ‘be given in (3-2-2) and (3-2-3) respectively.

Suppose the following two conditions are satisfied:

y y . x y _
1. 13([GX(sp lUsp 2p3Us Usp4Usp6H (sp3Usp4)) —¢

X

2. C([G - (splU

Y
sYZUsp3Usp4Usp6>1 X (Sp 3Usp4)>= (3.

Then ‘{CE, G, F}’ has a unique solution for all t on I.

134

Proof: By Lemma 3—2-1, there exists a forest T2 with con-
straint equations (3-2-3) in which Sp3 = ¢ and Q44 is a
zero matrix.

Substituting (3-2-3) into (3-2-2) and reducing,
T
F1 (zpl’ ‘Q12 Zpl + Q26 F6(t)’ t) ‘ Q11 Zpl ' Q12 F2(Zpl’
T T

: Q F6(t)' (3-2-4)

16

By Lemma B6 the left hand side of (3-2-4) satisfies
condition (Cl) for all t on I. Therefore by Theorem Bl,

there exists a unique solution for Z for all t. All

pl
other variables can be obtained uniquely from these.

 

The following Corollary is an important Special case

of Theorem 3-2—1.

Corollary 3-2-1: Let the component and constraint equations

 

for {GE, G, B}' be given in (3-2-2) and (3-2-3) reSpectively.
If (Sp3l/Sp4) = ¢, the system {GE, G, B} has a unique

solution for all t on I.

 

Lemma 3-2-2: Let the component and constraint equations for
{§B, G, B} be given in (3—2—2) and (3-2-3) respectively.
Then there exists a forest T2 with constraint equations
(3—2—3) in which Sp4 = ¢ and QE3 is maximum row rank if,

and only if, the following four conditions are satisfied:

135

1. C(G-(SE1U8;2U5:3U5;4US;6)) - C(G~(S)I:1US;2 US$69) = Q!
2. B(GX(sglUsgzUsg3Usg4Usgb)) - B(GX(S;1US:2 US$69) = $5
3. C(G - (Sp3USp4US:6>> = £3
4. B(Gx<sp3USp4USIy,6>> = 9‘-

Proof: Conditions (1) and (2) are satisfied if, and only if,

the following two conditions are satisfied:
. x x y X = .
5. C(G (SplUSp3USp4USp6D Cf,
Y X Y =
6. B(GX (splUsg3Usp4usp6D 9!.

To show this let

. X Y X Y X
G1 G (SplUSpZUSp3 Usp4USp6)

G

. x X Y X
0 G (Splusp3U8p4USp6) and

. x y x

X

If clecmo), then 01 ¢ C(GZ) since (5:1Usp6)

contains no circuits by its definition. Therefore,
CIE'CCGl) - C(GZ).

. - _ Y
Conversely if C16 C(Gl) C(GZ) and ele‘lelspz,
by definition of SE2 there exists another circuit

X X
C26 C(Gl) - C(G2) such that C2C(Sp1USp6UCl) - {e1}.

136

If eZETC2f7522, for the same reason as above there
exists another circuit C3C1(S:1L1826L}C2) - {Eé}. Proceed—
ing in this fashion, if eie Ci{)sg2’ there exists another
circuit ci+lc:(s’1§1us’géu Ci) - {ei}. Since sgz is finite,
there exists some circuit Cnc:(S§1LJS;3USg4(JSg6). 'There-
fore C(GO) f'¢. This shows that (5) is true, if, and only
if, (1) is true.

The proof that (6) is true, if, and only if, (2) is
true is identical to the above with obvious changes of nota-
tions.

Assume (3), (4), (5), and (6), are true. Since (5)
and (6) are true, by the proof for Lemma 3-2-1, there exists
a forest T2 with constraint equations (3-2-3), such that
SP4 = ¢.

Since there is no circuit in (Sp3LJSp4Ljsgé), by
(2-2-2) and definition (2-2-1), 5:1 must contain a dendroid
of C(G - (s’g‘lUsp3Usp4Us’g6).

Also since there is no cutset contained in
(sp3usp4usg6), by (2-2—2) and definition (2-2—1), SE1.
must contain a dendroid of B(G X (SEILJSP3LJSP4LJSE6)).
Together these two conditions imply, by Lemma 2-2-2, that
the matrix QE3 has maximum row rank.

Conversely suppose there exists a forest T with

2
constraint equations (3—2-3) in which Sp4 = ¢ and QE3 has

maximum row rank. By Lemma 3-2-1, (5) and (6) are true.

137

By Lemma 2-2-2, SE1 and Sil contain a dendroid of
Y , x x
B(G x (sp lUsp3 Usp4Usp6)) and C(G (splusp3usp4usp6n

. Y _
respectively, so B(G X (Sp3L/Sp4L/Sp6)) — ¢ and

C(G - (sp3Usp4us’56D = d.

 

 

Theorem 3-2-2: Let the component equations, CE, of Type 3,
be given in form (3-2—2) and the constraint equations in

form (3-2-3). Suppose:

l. the mapping Fl (zpl’ 252, t) satisfies
F2 (Zpl’ 252’ t)

condition (Ll) for all t on I;
2. C(G SXplUSyzUSp3 usp4 Uspén - C(G (s: USPZUSP6D= -;¢
3. B(GX (splUsp2U5p3usp4L/sp6» — B(G x (sp lL/spzcjspé»: -¢;

4. C(G-(Sp3U 4Usp 6)) =¢;

U1

B(GX (sp3usp4 pusgén = d,

Then the system, {CE, G, B} has a unique solution for all t

on I.

Proof: Beremma 3-2-2, there exists a forest T2 with con-
straint equations (3—2-3) in which Sp4 = ¢' and QT3 has

maximum row rank.

138

Substituting (3-2-3) into (3-2-2) yields
T _ _ _ T
F<zpl’—Q122pl+Q26F6(t)’t) Qllzpl Q12F2(Zpl’ Q122p1+Q26F6(t)’t)
: Q13 zp3 + Q16 F6(t) (3‘2'5)
and

T _
F3(Zp3, t) +Q13 z - Q36 F6Ct). <3—2-c)

— 2
p1 Q33 p3
The left hand side of (3-2-5) satisfies condition (L1). By

Theorem B1 and Lemma BB,

2 = F7(Ql3 zp3 + Q16 F6(t), t) (3-2-7)

pl

where F6(t) is Specified and F7 satisfies condition (Cl)
and is continuous in all variables except t.

Substituting (3-2-7) into (3-2-6) gives
T = - _
F3(zp3’t)+Q13F7(Q13Zp3+F8(t))"Q33Zp3 Q36Fc(t)° (3 2 8)

By Lemmas B5 and B6, the left hand side of (3-2—8) satisfies

condition (Cl) so by Theorem Bl, Z is uniquely deter—

p3

mined. From Zp3, all other variables can be uniquely

determined.

 

Corollary 3-2-2: Let the component and constraint equations

 

for {CE, G, B}' be given in (3-2-2) and (3-2-3) reSpectively.

Suppose:

139

l. the mapping Fl (Zpl, 252, t) 15 strongly
P2 (Zpl’ 252, t)

monotonic and satisfies a Lipschitz condition for all t

on I;
. X _ .
Y _
3. B(G x (sp3LJsp4Ljsp6)) — ¢.

Then the system {CE, G, B} has a unique solution for all t

on 1.
Proof: By (2) and (3) (SX USy (jSX ) can be contained
—————- ’ p3 p4 p6

. y x Y . .
in a forest T2 and (Sp3LJSp4ljSp6) can be contained in

theco~forest of “T2. By Lemma B4, the mapping

F1 (zpl’ 252, t)

F2 (Zpl’ 252’ t)

can be solved explicitly fOr the primary

variables of T and the resulting mapping is again

2’

(STRMLC) for all t on 1. Consequently, sz = ¢ and con-

ditions (l) and (2) of Theorem 3-2-2 are satisfied. The
assertions of the Corollary follow by application of Theorem

3-2-2.

 

Initial
initial

initial

140

Existence Theorems for Systems

of Type 1 Components

Suppose all components in the system are of Type 1.

value problems of such systems will be examined. The

value problems will be called consistent when the

values of all variables which are differentiated in

the equations are given and such values satisfy the system

algebraic and constraint equations.

Let the topology of the system graph be such that

there exists a forest T for which:

1. the direct sum of the terminal equations for all

ponents in the system can be written in the form:

1111

No

p3

s4

55

p6

F1 (¢;, 251, t)

G1(r1’ 251’ t)

F2(¢§’ 252’ t)

G2‘ 2, t)

F31(¢” Zp3’ 254’ 253’ Zp4’ t)
F32(¢’: Zp3’ Zs4’ 253’ Zp4’ t)
F33(¢” Zp3’ 254’ 253’ Zp4’ t)
F5 (ZpS’ Zsc’ t)

F6 (ZPS' 256’ t)

m COITI-

(3-2-9)

141

Zs7 = P7 (zp7’ 258’ t)
zp8 = P8 (zp7’ 258’ t)
ng = F9 (t)

where the mapping F32(¢J, Zp3, 254, 253, Zp4, t)

Z

F33(¢J’ Zp3’ Zs4’ 253’ p4’ t)

is strongly monotonic in the variables 253, Z for

p4’

every ¢’, Zp3, and 254 and every t on an open set

I of reals, the mapping F5 (Z Z t)

p5? 56’
F6 (ZpS’ Z56’ t)

is strongly monotonic for all t on I, the mapping

F7 (Zp7’ 258, t)

F8 (Zp7’ 258’ t)

is monotonic for all t on I,

F1, F2, F31, F32, F33: F5: F6, I:7, FB’ G1 and G2

satisfy a Lipschitz condition in all variables except t,

and all mappings of (3—2-9) are continuous in t on I.

The constraint equations for system graph, G, for corre-

Spondence F, are of the form

142

T T
253 “Q13 Q23 Q33 Q34 Q35 Q36 Q37 Q38 Q39 Zp3
z o o -Qi o o o o 0 Q 2
s4 34 49 p4

 

 

 

 

 

 

255 == 0 ‘Q25 "Q35 0 Q55 Q56 Q57 Q58 Q59 Zp5 (3—2—10)
256 O Q36 ‘an O ‘an O O O Q69 Zp6
2s7 0 -Q§7 “Q37 0 -Q§7 O Q77 Q78 Q79 Zp7
Zs8 O 'Qgs 'an O -Q§8 O ’Qgs Q88 Q89 Zp8
25: 'Qig "(2:9 “Q39 “Q29 ‘ng 42:9 “Q39 ”Q39 Q99 sz9

where Qii is skew for i =2, 3, 5, 7, 8, 9.

Let Spi denote the subset of edges of B(G) corre-

Sponding by F to the variables Zpi’ for i==l,..., 9.

Let 5:1 and séi denote the subset of edges of B(G) cor-
reSponding to the variables Xpi and Ypi reSpectively for
i =1, ..., 9.

Then (3-2-10) restricts G in the following six ways:

1. C(G - sx )

p9 ¢ (the empty set);

¢;

Y
2. B(G X Spg)

. y X X Y X Y = .
3. B([G (spit/sp2L15p3L/SP4L/SP9)1 X Spl) ¢3

143

x X - .
4. C([G x (Sp1USp2U 133st 4Usp9)] - SP1) - (If,
5. B([G x<s§1UsgzUsg3Us§4Us¥39>1 - (sylusp 2)) = 9!;
6. C([G - (S :ZUS); 3Usp 4Us:9)] x (5:1Us’gzn = d.

This statement follows from (2-2—2) and (2-2-3), and the
fact that the remaining zeros of (3-2-10) can be obtained

by suitable choice of forest.

Theorem 3-2-3: Let the component and constraint equations
for the system «{CE, G, B}' be given in (3—2-9) and (3-2-10)
reSpectively. Suppose the following conditions are satisfied:

1. B([G x (sp_2 UsY 3Usp 4USY5 Usx péusp7 usp8 Usggfl
5X7 Usggn = s4;

2. C([G - (5’52Us’lg3 Us};4 Us§5Usgéusp7Usp305§9n
x (sg7Us’g8n = ¢.

Then the system ‘{CE, G, F}. has a unique solution for a con—
sistent initial value problem in a neighborhood of any t on

I.

Proof: By a technique identical to the proof of Lemma 3-2-1,
conditions (1) and (2) above are true if, and only if, the

following two conditions are true:

(If;

3. B([GX(sg2Usg3Usg5 Usp7 Uspg Usggfl ' (5’1;7 US$89)

4. B([G'(S§2U5:3UsgsUSp7USp8USEQH - (SE7 5);;8» _

l
‘9

144

Again following the proof of Lemma 3-2-1, there
exists a forest T2 with constraint equations (3—2—10) such
that sp7 = d and Q88 = o. 3

Substituting the appropriate rows of (3-2—10) into

in (3—2—9) gives:

55’ $6

the equations for Z Z and Zp8

F (2

T T T
5 p5’ ”Q26 Zp2 "Q36 Zp3 ‘Qsc ZpS * Q69 Zp9’ t) ‘ Q55 sz

T T T
‘Qsc Pp (ZpS’ 'Q2s Zp2 "Q36 Zp3 'Q56 Zp5 * Q69 Zp9’ t)
T T T _
"Q58 F8 (‘Q28 Zp2 “Q38 Zp3 ‘st zp5 + Q89 Zp9’ t) ‘
T 2 T 2 + z (3 2 11)
‘Q25 p2 "Q35 p3 Q59 p9 " ‘

By Lemma B6, the left hand side of (3-2-11) is strongly
monotonic in ZpS‘ It also satisfies a Lipschitz condition
in all variables except t since it is a composite mapping
of functions satisfying Lipschitz conditions.

By Lemma B4, the inverse exists and

z = F10 (2P2, zp3, t) (3—3-12)

p5

By Lemma B4 and the Corollary to Lemma B3, P10

satisfies a Lipschitz condition in all variables except t
and by these Lemmas is continuous in t.
Substituting the appropriate rows of (3-2-10) into

the equations for Z and Z5

p3 in (3-2-9) gives:

4

145

T T T T
Q34 P32 (#1, Zp37 -Q34 Zp3 + Q49 Zp9’ -Q13 Zpl -Q23 Zp2

Z

* 'Q33 zp3 + Q34 Zp4 + Q35 Zp5 + Q36 p6 + Q38 zp8+ Q39 qu' Zp4’ '0

T T T
F Z - Z + Z — Z - Z + Z
33 (#5’ p3’ Q34 p3 Q49 p9’ Ql3 pl Q23 p2 Q33 p3

Z Z Z

+ Q34 p4 + Q35 p5 + Q36 p6 + Q38 Zp8 + Q39 Zp9’ p4’ t)

s (t) (3-2—13)

By Lemma B6, the left hand side of (3-2-13) is strongly
monotonic in Zp4. It also satisfies a Lipschitz condition in
all variables except t, and it is continuous in t.

By Lemma B4, the inverse exists and

zp4 = Fll(Zpl, zpz, zp3, zps, zpé, zp3, t) (3—2—14)

By Lemma B4 and the Corollary to Lemma B3, Fll satis-
fies a Lipschitz condition in all variables except t and by
these Lemmas is continuous in t.

By (3—2-9), (3-2-10), (3—2-12), and (3-2-14), all
terminal variables are known eXplicitly as a function of
KQJ¢EJL32 Zp3’ and t which satisfies a Lipschitz condition
and is continuous in t. Substituting these into the differ-
ential equations gives a normal form model of the system

which satisfies a Lipschitz condition in all variables except

t, and is continuous for t on I.

146

By Theorem 2.1 of [Lfiel], the normal form model has
a unique solution locally from which all other variables can

be determined uniquely.

 

A different hypothesis on the algebraic equations

yields the following.

Theorem 3-2-4: Let the component and constraint equations

 

for the system ‘{CE, G, B}' be given in (3-2-9) and (3-2-10)
reSpectively. Suppose the following two conditions are
satisfied:

1. C(G - (51:2 Us’g3 Ung/sp7 uspg US’ggn

X Y X _ 3

2. B(G x (ngUsg3 U534 (Jsp7Usp8 Usggn
-B(G x (sg3Us’g4 Usggn = £4.

Then the system.-{CE, G, B} has a unique solution for a
consistent initial value problem in a neighborhood of any t

on 1.

Proof: By the proof for Lemma (3-2-2), (1) and (2) are true
if, and only if, the following two conditions are true:

3. C(G - (5’3205’53 Usp7Usp8 Us’ggn = 91;

4, B(G x (s’gZUsg3Usp7USngSggD = (21.

147

By (3), (4), and (3—2—10), (sglL)s§2LJs§3LJs:4(15:7L)

Sy (15x ) can be contained in a forest T and
p8 p9 2

(SEIL/SEZL/SE3{/Sg4LJSE7Ljsg8ljsgg) can be contained in the

coeforestcfl? T2. By Lemma B4, the mapping F5 (ZpS’ 256’ t)

_p3 (zps, 256, t)

a

2
and the resulting mapping is again (STRMLC) for all t on I.

can be solved explicitly for the primary variables of T

Consequently, the constraint equations for T2 are in form
(3—2-10) Wlth (spétlsp8) = d.

Following the proof for Lemma (3-2-2), Q§7 is
maximum row rank.

Substituting the appropriate rows of (3-2-10) into

the equations for Z and Z5

55 in (3—2—9) yields

7
F5(Z 5,t)-Q5525=—Q'£ z -QT z +Q z +Q z.
P p 5 p2 35 p3 57 p7 59 p9
(3-2r15)
The left hand side of (3-2-15) is (STRMLC) for all t
on I, so by Lemma B4, it has an inverse

_ T T
Zp5 ‘ F13(‘Q25 Zp2 'Q35 Zp3 + Q57 Zp7 + Q59 F9 (t), t)-

Also by Lemma B4 and the Corollary to Lemma B3, F10
is (STRMLC) for all t on I and is continuous in t.
Substituting (3—2-16) and the appropriate row of

(3-2-10) into (3-2-9) gives:

148

F (Z

7 p7’ t) "Q

T T T
+ _ —
77 Zp7 Q57 P10 ( Q25 Zp2 Q35 zp3

’ _ T T
* Q57 Zp7 * Q59 F9 (t): t) ‘ “Q27 Zp2 'Q37 Zp3 * Q79 F9 (t)-
(3—2—17)

By Lemmas B5 and B6, the left side of (3-2-17) is
strongly monotonic in Zp7 and also satisfies a Lipschitz
condition in all variables for all t on I. By Lemma B4,
the left hand side of (3-2-17) has an inverse with reSpect

to Z Thus

p7‘

Zp7 = F14 (Zp2, Zp3, t). (3-2‘18)

By Lemma B4 and the Corollary to Lemma B3, F14

satisfies a Lipschitz condition in all variables except t

for all t on I, and also is continuous in t on I.
Substituting suitable rows of (3-2-10) into (3—2-9)

yields an equation similar to (3-2-13) and by the same rea-

sons given in Theorem 3—2-3 ,

Zp4 : F15 (Zpl’ Zp2, Zp3, Zps, zp7, t), (3-2-19)

and for all t on 1, F15 satisfies a Lipschitz condition
in all variables except t and is continuous in t.

By (3-2-9), (3-2—10), (3-2-18), and (3-2-19), all
terminal variables are known explicitly as a function of

‘¢;,1p3,1p3, zp3 and t, which satisfies a Lipschitz con-

dition for all variables and is continuous in t on I.

149

Substituting these into the differential equations gives a
normal form model of the system which satisfies a Lipschitz
condition in all variables except t, and is continuous in
t on I.

By Theorem 2.1 of [LE—l], the normal form model
has a unique solution locally from which all other variables

can be determined uniquely.

 

Conclusion

 

Theorem 3-1—3 and its corollaries provide the com-
plete background for the examination of linear semi4definite
component systems. By these theorems, the problem of unique-
ness is reduced to the examination of the interconnections
of only semi—definite components. These theorems provide a
fundamental tool in the examination of such systems.

The algorithms of Part I provide the second basic
contribution of the thesis. The material here culminates in
(3-1-41) which is an expression for the determinant of an
arbitrary linear time invariant system in terms of its compo-
nent equations (reflected in Ji) and its graph (reflected
in X). This is the simplest equation yet given in the
literature which shows the relation between the system struc-
ture and the graph for any general linear time invariant

system.

150

Theorems 3-2-1 and 3-2—2 are the first theorems
known to the author on systems in a Hilbert Space. These
theorems are a generalization to Hilbert Space of the mono-
tonic properties of mappings as utilized in Theorems 3-2—3
and 3-2-4.

Theorems 3-2-3 and 3—2-4 are the most extensive
existence theorems for algebraic and differential equations
yet seen by the author. Practically every other theorem on
uniqueness of systems published is a Special case of these
or a slight modification of a Special case. For example,
the theorems of [DU-1], [DU-2], [DU-3], [DU-4], [SE-1],

[BI-2], [DE-1], and [WI—l], all fall into this category.

CHAPTER IV
STABILITY STUDIES OF SYSTEM SOLUTIONS

Most contemporary stability studies are based on the
so-called Second Method of Lyapunov as applied to a set of
first-order differential equations characterizing the system.
Almost nothing has been said about stability as it relates
to the two fundamental structural features of the system;
namely, the characteristics of the system components and ‘
their topology; i.e., their pattern of interconnection. A
given set of system components, for example, may be stable
when connected in one manner but unstable when the connec-
tions are altered. .

This chapter examines several classes of systems,
containing both linear and nonlinear components, and estab-
lishes sufficient conditions on the topology of the System
for stability of a solution. A set of necessary and suffi-
cient conditions for system stability are also given on
the component characteristics of a system having a given
topology.

In this study components of Type (1) only, are exam-
ined for stability of a solution subject to a perturbation

in initial conditions.

151

152

Stability, as it relates to the structure of the

system is concerned, then, with a study of the stability

characteristics of the system of e equations of Type (1)

when the vector, (20, Zi) of order 2e is subjected to the e

linear constraint equations in (2-3-1). The stability char—

acteristics discussed in this chapter are limited to the

class of systems for which the equations characterizing each

of the m components in the system are of the form
d _

20 = vb

01'

Z

0 G(Zi)

The most general linear forms considered are

3L
dt

P(t) zi + F(t)

ip

Z0
and

Z0 = C(t) Zi + G(t)

(4-1-1)

(4-1-2)

The definition of stability considered is that given

originally by Lyapunov,

153

Definition 4-0-1: A solution 46(t) of the system of equations

 

L1! = Pup, t)

is stable for the initial point t = t0 if, and only if, for
every E> 0, there exists a 8> 0, such that ”Ll/OH) -glj(t)|| <6
for all t 3 t0 if “111060) - ‘JJ(tO)H < 5, where 1,110“) is an
n-tupie of time functions,lp(t) is an arbitrary solution and
the indicated norm is the euclidean norm.

The development is based on the so-called direct
method of Lyapunov [HA-l], using a positive definite, real
valued, continuous function v on the n+1 dimensional Euclidean
Space (Vb, t). The system is stable if the total time deriva-

tive of v along the trajectories lp(t) is not positive in

Hh,tO: qu-Ipoll: h, t 3 t0. Following Hahn [HA-1], if R is

the set of real numbers, then a function g} R:—>R.belongs to
class K, means that fl is a continuous real function defined
on the closed interval 0 f r 5 h and B(r) vanishes at r = O
and increases strictly monotonically with r.

A positive definite function v of radius h at IPO is
a real valued function from the (1p, t) space which vanishes
at one point HUD for 't Z.t0 and in the half-cylindrical

neighborhood

Hh,t0‘ W“— WC” 5 h, t 3 to

and

154

MP, 1:) : Milk/14110)!)

A matrix A, whose entries are continuous functions
of (Y, t) is said to be positive definite if for any ve'ctor‘J/il O,

IPT Atp‘> O for all t 3 t and all Y, and positive semi-

O’
definite if 42A #1,: O for all Y, t 3 to. It can be shown
that the quadratic form associated with a positive definite
matrix is a positive definite function of some radius h at
\PO = 0. Whereas most applications in the literature of
positive definite and semidefinite matrices are restricted

to symmetric matrices, the applications in this chapter

require no such restriction.

Part I. Linear Systems

 

Let the mathematical models of each of the m multi-
terminal components of a system having a graph G be given in
one of the three following forms:

1. Dynamic Components

20 = P(t) zi + F(t)

2. Algebraic Components

2 = C(t) Z. + G(t)
O 1

3. Excitation Components

ZO = B(t)

155

where

E(t), G(t) and F(t) are known continuous vector

functions of t, the entries of the matrices P(t) and C(t)

are continuous functions of t, and Z

O and 2i are com-

plementary terminal vectors, i.e., the direct sum (20, 2i)

contains exactly one component xj and one component yj
correSponding to each edge in the terminal graph of the

component.

Let the topology of the system be such that there

exists a forest T in G for which:

0

l. the direct sum of the terminal equations for all

m components in the system can be written in the form

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

r—. '1 r— 1 P— -1 '— -'
Zpl p11(t) p12(t) zsl F1(t)

= +
‘254 p21(t) p22<t>J zp4 F4(tz

(4-1-3)

P w — n - a - w
Zp2 C11(t) 012(t) Zsz 32(t)

= +
Zs3 C21(t) C22(t) L Zp3 L G3(t)
Zp5 = E(t)

where ij = (ij, ij) (j=l, 2, 3, 4, 5) is a vector of

primary variables, i.e., all components of ij correSpond

to edges in forest TO (branches) and all components of Y -

PJ

156

correSpond to edges in the complement of T0 (chords). The

vector 2 . = (Y

sj X .) (j=l, 2, 3, 4, 5) represents the

Si’ SJ

complement of ij, i.e., all components of Ysj correSpond

to edges in TO and all components of ij correSpond to

edges in the complement of To.

2. the constraint equations of the system graph are

of the form:

r W " ‘T l" "I
Zs1 Q11 Q12 Q13 Q14 Q15, Zp1
_ T 1
2s2 Q12 Q22 Q23 0 Q25 sz
z : -QT _QT Q 0 Q Z (4-1-4)
53 13 23 33 35 p3

T
zs4 'Q14 0 0 0 Q45 zp4

T T T T
Zs5 'Q15 'Q25 “Q35 ‘Q45 Q55 zp5

 

 

 

 

 

 

 

The zeros in (4-1-4) are obtained by selecting the
forest TO such that the vector 254 is of lowest possible
order. Since (4-1-4) represents the constraint equations for
one forest To, the matrices Q11, Q22, Q33, and Q55 are
skew. The only restraint that (4-1-4) has placed on the graph
G is that there be no cut-Sets of thru drivers or circuits of

across drivers which is a necessary condition on the system

for the existence of a unique solution. [KO-l].

157

Let Spi denote the subset of edges of E(G) corre-

Sponding to the variables zpi for (i=1, 2, 3, 4, 5). Let

SX and Sy denote the subset of edges of E(G) corre-

pi pi

Sponding to the variables X - and Y

p1 pi reSpectively for

(i=1, 2, 3, 4, 5).

Let G1 be the graph [[G X (E(G) - (5)51 U SE4 U 52%)]
(Sp2 LISp3i]. Let CE represent the component equations
(4-1-3), and let P be the correspondence between the compo—
nent equations and G as described in Chapter II. yThen the
subsystem {CE, G1, E> has a unique solution for any t if,

and only if,

— —

— -p —

U o c11(t) C12(t) Q22 Q23

det. - #’0 (4—1—5)

 

 

 

 

 

 

_:Qg3 Q33 _C21(t) C22(t)_ O U

— -I

 

 

In this case the component equations are:

 

 

 

 

 

 

 

 

Zp2 C11(t) C12(t) Z52 92(t)
= +
j 2533 LC21(t) C22(t) zp3 G3(t)

By (2—2-3), the graph equations for G are given by

l
the submatrix in the second and third rows and second and
third columns-of (4-1-4). Substituting the graph equations

from (4-1-4) into the component equations gives

—

 

 

 

 

1—

158

 

 

which yields (4-1-5) immediately.

U 0 Cll(t) C12(t) Q22
T
L:923 Q33 C21(t) C22(t) 0

Suppose (4-1-5) is satisfied.

matrix

PCt) =

 

_

p11(t)

p21(t)

—1

p12(t)

p22(t)

 

 

 

 

p2

p3

 

G4(t)

 

 

G5(t)

If, in addition the

in (4-1-3) is positive definite and symmetric, then it is a

simple algebraic exercise to Show that when the linear con-

straint equations in (4-1-4) are substituted into (4-1—3),

the system model can be reduced to the form

Zpl

where F(t)

J("FQTT‘PM Q13]

K(t) J(t) 2

p1

—

—

——a

U 0

 

 

 

T
‘Q23 Q33

,
£15234 + Q14§21 + Qi4€22Qi4j

+ E(t)

C11

 

C

——1

12

 

,c21 c22

Q22 Q23

0

‘—

U

 

—'f

.1

 

d

 

-1—C

 

—1

(4-1-6)

11

C21-U

O

is a continuous vector function of time and

— 1—

 

 

 

d

159

— 1
£11”) 12“)

= P(t)‘l

 

 

£2100 @2503

Since P(t) is symmetric, P(t)-l is symmetric and by

Lemma A2, is also positive definite. Since the matrix

 

 

 

 

 

 

 

‘Qi4: U * “L521 +£22Qi4 E22

is symmetric and positive definite, it follows that K

positive definite and symmetric.

 

U O 7):11 5121:} O K £12 +Q14§22T
_§21 €22_

(4-1—7)

is

In one of the stability theorems following, P(t) is

not necessarily positive definite, only nonsingular and sym-

metric. If 254 is of zero order and condition (4-1-5) is

satisfied, then the System model in (4-1-6) reduces to

ipl = P(t) J(t) zp1 + F1<t>

where F'(t) is a continuous vector function of time.

By definition 4-0-1, stability of any solution
only on a perturbation of the initial conditions. The
bation equations for investigating the stability of an

trary solution of the linear System

W=Au>¢+Fd>

(4—1-8)

depends
pertur-

arbi—

(4-1-9)

160

are determined as follows:

Let (P0(t) represent a solution for which stability

(put)

tion derived from a perturbation of the initial conditions.

is to be investigated and let be the perturbed solu-

Let

2(t) = (V(t) - 4100:)
then (4-1-9) becomes

é(t) = A(t) z<t>

and it follows that the stability of any solution to the
system under consideration is determined by the stability of
the homogeneous parts of (4—1-6) and (4-1-8).

In the remainder of Part I, let

_ i.
C11(t) C12(t)
C(t) =
L?21<t) C22(t)_
where
Cll(t) C12(t)
_?21(t) C22(t{3

 

is the matrix of (4-1-3).

 

 

 

161

The following definition and lemmas are needed for

Theorem 4-1-1.

Definition 4-1-1: Let G be a graph and S and T be

 

complimentary non-null subsets of E(G). Then G is said
to be separable into the two parts, G ° S and G ° T if
G has no cutsets or circuits with edges in both G ° S and

G - T.

Lemma 4-1—1: There exists a forest T1 of the system graph,

 

G, that has constraint equations (4-1-4) with Q11, Q22, Q23,

and Q33 zero if and only if the subgraph
X o =
[[G x (E(G) - sp5)] (E(G) - spy] G1

is separable into two parts such that Sél, 8g4, 5%2 and 8g3

SX and SX

S p2’ p3

are in one part and Sy are in the other

X
pl’ p4’

part.

Proof: By (2—2-3), the first 4 rows and columns of (4-1-4)
is a representative matrix for the graphic and cographic
vector Spaces correSponding to G1.

Suppose G1 is separable as above. Let

= X y y y
s (spl u SP4 usp2 usp3).

The representative matrices, A, and B, of B(G) and of
C(G) reSpectively can, after rearrangement of rows and columns,
1 0 B1 0

be partitioned as A = , B = , where the

162

columns of Al and B1 correSpond to the edges of S. The
zero entries of A and B contain Q11, Q22, Q33 and Q23.

Conversely suppose Q11, Q22, Q33, and Q23 are
zero. Then the two representative matrices A, and B, of
G can be partitioned as above, so G is separable into

1
G - S and G - (E(G) — S).

 

Lemma 4-1-2: The submatrix [D12 Q13] of (4-1-4) has max-
imum column rank if, and only if, the following two condi-
tions are satisfied:
. . . . . x
1. There is no Circuit contained in (sztj sp31jlsp5),
and

2. There is no cutset contained in (SP2 L/Sp3 Llsgs).
Proof: Assume l and 2. Since there is no circuit contained
. x . . .
in (szlj Sp3lj SPS)’ by (2-2-2) and definition 2-2-1 ,

SX

pl must contain a dendroid of C(G ° (S;1(/'Sp2(j Sp3 LISES).

. o o o y
Also Since there is no cutset contained in (Sp2(J'Sp3[j SpS)’
by (2—2-2) and definition 2-2-1 , 531 must contain a den-

. y Y
drOid of B(G X (Spl L’sz L/Sp3lJ Sp5)). Together these
T
Q12
T
Q13
hasmaximum row rank, so its transposeluusmaximum column rank.

two conditions imply by Lemma 2-2—2, that the matrix

163

. 1 ‘ . .
Conversely, assume iQ12 Q13! 15 max1mum column
L ‘ 3

rank. Then by Lemma 2-2-2, SE1 and 5:1 contain a den-

- Y Y
drOid of B(G X (SplL/ Sp2(J Sp3lj SP5) and

X

. X . .
C(G (Spl(J SpZLj S U Sp5)) reSpectively, so there is no

p3

. . y . . —
cutset contained in (Sp2(J Sp3tj Sp5) and no Circuits con

. . X
tained in (Sp2\J Sp3 U Sp5)'

 

Theorem 4—1-1: Consider a system for which the model is

 

given in the form of component equations (4-1-3) and con-
straint equations (4-1-4), where P(t) and C(t) are
constant matrices and P is symmetric and positive definite.
If the graph of the system is such that:

l. The subgraph PG X (E(G) - 5:5)1 ° (E(G) - Sij = G1

is separable into two parts, Gl - S and G1 ° T, such that
sgl and SE4 are in G1 - S and Sgl and S§4 are in the
G1 ° T.

2. There is no circuit of G contained in

(sp2 u SP3 [1 533).

3. There is no cutset of G contained in

(5133 U SP3 U 5135).

4. The output variables of each of the algebraic

components can be partitioned into those correSponding to

164

edges in G1 - S or G1 ° T. Thus let Xi and Y: be the

output variables of component i correSponding to the edges

1 i
1 3 and Y4 be

the output variables of component i corresponding to the

of component i in G ° T. Similarly let X
edges of component i in G1 - S.

Suppose each of the algebraic components of (4-1-3)

are as follows:

for component i:

 

 

 

Y2 = “Gig C22 023 C34 X: + Gi(t) (4-1-10)
X3 'Cig C23 C33 C34 Y3
Y3; 611-033-631: C24 3‘1.

 

 

 

where O: , C1 C1 and C24 are symmetric, and the

 

-3 .3
i 1
C22 C23
matrix is nonsingular.
iT i
C
23 C33
L— ...

 

Then any solution to the system is stable if, and

only if, C(t) is positive semidefinite.

165

Proof: Since there is no circuit contained in
(szlj Sp3lj 5:5), and no cutset contained in (Sp2l}Sp3L}5g5),
(sz L/Sp3) contains no cutset nor circuit of G1. The edges

_ X Y _
of S (SplljSp4) are a subset of (Sp2(j SP3) so they con
tain no cutsets. Therefore, (Séllj SE4) contains a dendroid,

D of B(Gl - 5). (See definition (2-2-1).) By (2-2-2) and

l?

the definition of G sX = D

1’ pl Also, the edges of

lo
T-(S;l(j 5:4) are a subset of (szlj SP3) so they contain

no circuits. Therefore (sgl LISE4) contains a dendroid, D2,
of C(G - T). Also by (2-2-2) and the definition of

G 5y

1’ p1 = D

2.
Since B (G1 - T) B (G1 - S) = B (G1), Dltj D2

is a dendroid of B (G1) so are the edges of a forest, T0,

of G1. Let (4-1-4) be written for forest To' Then sgz

and 5g3 are in S and 8:2 and S§3 are in T.

By Lemma 4-1-1, Q11, Q22, Q23, and Q33 of
(4-1-4) are zero. By Lemma 4-1—2, the matrix [D12 Q1% of

(4-1-4) has maximum column rank.

Let X Y- represent the direct sum of all compo-

j’ J

nent Xg, Y3 reSpectively for j=l, 2, 3, 4. It is clear

that for forest To,

166

 

 

 

 

X1 X2
zp2 = , zp3 =
L34. _¥3
and the matrix
F— _} h -
C11 C12 C11 C12
C: :
T
_?21 C22 LT 12 C22

 

 

 

 

where C11 and C22 are symmetric, since C is the direct
sum of the component equations (4-1-10).
Also C22 is nonsingular Since it is the direct sum

of nonsingular matrices.

Then J of (4-1—6) becomes

._ __l,._ T—
U 'C12 C11 UT [U12

J = ”E112 Q13]

 

 

 

 

 

 

T T
_0 '0223 _fC12 “U3 __13,
_ '— -' r- — r- — —T-
"EQlZ Q13] U C12 Cll 0 U 0 Q12
1
0 U o c '1 cT U QT
.. J ... 22 ... L... 12 _4 L 13.1

 

 

 

 

 

 

 

 

so J is symmetric.

167

Since P is positive definite, K is positive

definite and can be written as the product

__ T
where K1 is nonsingular [BE—2]. Setting Zpl = K1 R in

the homogeneous part of (4-1-6) gives

° _ T

Since the eigenvalues of KJ of (4-1-6) are the same as the

eigenvalues of the symmetric matrix KT it follows

1 1’
that the system is stable if, and only if, the eigenvalues of

K? J K1 are not positive. Consequently, the system is stable

J K

if, and only if, J is negative semidefinite. But since
12 Q13] has maximum column rank, it follows from Lemma A8
that J is negative semidefinite if, and only if, C is

positive semidefinite, and the theorem is proved.

 

Corollary 4-1-1: Assume all the hypotheses of Theorem 4-1-1
except that P(t) can be time varying. Suppose
1

1. P(t)-1 = i P-

dt (t) exists and is negative semi-

definite for t 3 to.
2. Each algebraic component in (4-1-10) can have
i o o o o o . . .
C11, C22’ C33, CZ4, C33, and Ci4 as time varying matrices.

3. For each component i, the matrix

168

 

 

 

 

 

i i
C11 C14
CiT Ci
14 44
d ’ l
a? F i i—--l
C22 C23
iT i
_923 C33

 

u— a

is negative semidefinite for all t 3 to.

4. All time varying entries of each component in
(4-1-10) are bounded and C22(t) and Cll(t) are nonsingular
for all t 3 to. Then any solution to the system for initial
time tO is stable if, and only if, C(t) is positive semi-
definite for all t 3 to.

Proof: In this case Q11, Q22, Q23, and Q33 are 0 and

 

 

F _
C11 C12
C:
CT C
L- 12 22
with C11 and C22 symmetric and nonsingular for all t.
As in Theorem 4-1-1, J is Symmetric. J is also
nonsingular Since C11 and C22 are nonsingular for all
t 3 t

O.

169

Consider the scalar function

v =§DT J(t) ll}

Along the trajectories

<0
ll

2U} J<t>x11+ 4}" 3m

ztpT J(t) K(t) J(t)UJ+UUT J(t)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

i" — ...... —- p— au- -T-
U 012 C11 0 U o Q12
J”) = '[Qiz Q13]
—1 T
U U 0 C22 C12 U Qi3
where C12 is a constant matrix so
_ .1 _ . _ ._ ..T _
U c12 C11 0 -i U o Q12
- _ d
J”) - '[le Q13] dt
-1 T T
L9 U _» LO C22 3\_912 U_ _Ui3_
\- d

 

 

which is positive semidefinite since

 

 

C11 0
.9.
dt 0 c -1
_ 22 _3

is a direct sum of negative semidefinite matrices. Since
K(t) is positive definite, v is positive definite.

Since C(t) is bounded for t 3 t v is decrescent, by

07
Theorem 1.2 of [HA-l].

170

If J(t) is not positive semidefinite for all
t 3 to, then v has a domain < O and by Theorem 5.2 of
[HA—1], any solution is unstable. If J(t) is positive

semidefinite for all t 3 to, then take the scalar function

v =4} K‘1(t)\p
Along the trajectories

x}: 241T K‘1(t) {p + \pT X-l(t)\lJ
2\,L'T J(t)“) + \pT {Clan/J

. ° -1 d -1 . . .
The matrix K (t) = 7g? K (t) is negative semi-

definite by Lemma A10. Since J(t) is negative semidefinite,
v is negative semidefinite. Also, since K(t) is positive
definite, by Lemma A2, K-l(t) is positive definite and any
solution is stable.

Therefore J(t) is negative semidefinite if and only
if the system is stable.

AS in Theorem 4-1-1, J(t) is negative semidefinite
if, and only if, C(t) is positive semidefinite, and the

Corollary is proved.

 

Theorem 4-1-2: If in (4-1-3), P(t) is positive definite

 

. . ' - -1 . .
and symmetric, if P(t) 1 = 7%? P (t) eXists and is nega-
tive semidefinite and if C(t) is positive definite, then

the system is stable for all graphs for which the constraint

171

equations for some forest T in the system graph can be

written in the form (4-1-4).

Proof: Condition (4-1-5) is satisfied by Lemma A9. There—

fore, the system model is (4-1-6). The matrix X(t)'1 =

_9_ K_l(t) is negative Semidefinite by Lemma A10.

dt
Consider the Scalar function

v = 111T K(t)-1L1} (4—1—11)
Along the trajectories
21.11T K(t)—l ‘1”ng f(a)-14;
2\,i/T J(tmj +UJT fi<t>'1\/J

But since J(t) is negative Semidefinite, v is negative

<0
ll

semidefinite and the theorem is proved.

 

By use of the following lemma, a condition for asymptotic

stability of the system can be obtained.

 

Lemma 4-1-3: The submatrix [D12 Q13] has maximum row
rank if and only if the following two combinations are
satisfied:

1. There is no circuit contained in (SplU SP4U 5:5)
. . . . x y x . .
other than those Circuits contained in (Spl U Sp4 U SpS)’ i.e.,

C(G - (splu sp4 U 5:5» - C(G - (5?, U SE4 U 5’55» = 16 and

where G is the empty set.

172

. . . y
2. There is no cutset contained in (SPILj Sp4lj Sps)

°~Y X Y.-
other than those cutsets contained in (Spll/ Sp4lj SpS)’ i.e.,

Y _ Y X =
B(G x (spl U SP4 U sp5)) B(G x (spl U SP4 U 5%)) 16.

Proof: Assume l and 2.
Conditions (1) and (2) are satisfied if and only if the fol-
lowing two conditions are satisfied:

3. There is no circuit contained in (SplL/Sg4tj 5:5);
- . x x -
i.e., C(G (Spl(/ Sp4lj SP5))-0,

and

4. There is no cutset contained in (Spltlsg4lJ Sgs);

. y y _ .
i.e., B(G X (Sple Sp4lj Sp5))-O. To show this let

X

X _ x
O u $135)], G1 - [G - (splu sp4u sp5>1

= o X y x
and G2 [G (Spllj SP4!) Sp5)]°
. x x
Let Cl 6 C (GO), then Cl}.Z C (G2) Since Spl U Sp5

contain no circuits by their definition. Therefore,
(5.6 C (G1) - C(GZ).

Conversely let Cl 6 C (G1) - C (G2). If Cl con-

tains an edge, e1, of Sy by definition of sg4, there

p4’
exists another circuit C2 E C (G1) - C (G2) such that

X X
C2C(Spl U sp5 11 c1 — {e1} ).

173

Y
If e2 6 (CZ/)Sp4), for the same reason as above

there exists another circuit C3C.(S];l U 5:5 U C2 — {e2}).
Proceeding in this fashion if eiE (Ci/]S;4), there exists
another circuit Ci+1Cl(S§1(J SgsllCi - {€3}). Since Sg4
. . . . . . x X
is finite, there eXists some Circuit Cn(:(Sp1 b/Sp4 LISPS).

Therefore, C (GO) # G. This shows (3) is true if and only
if (1) is true.

The proof that (2) is true if and only if (4) is
true is identical to the above with obvious Changes in nota-
tion.

. . . . . . x x
Since there is no Circuit contained in (SplLlSp4()Sp5),
by (2—2—2) and definition 2-2-1 , (8:2 blsfi3) must contain
a dendroid of C(G - (spl U 333 U 5’53 U 5’34 U 535)).
Also since there is no cutset contained in
(spltj 534(1 SE5), by (2-2-2) and definition 2—2-1 ,
Sy Sy . .
( p2lj p3) must contain a dendrOid of
B(G x (spl U 552 U 533 U 83%., U 51%)).

Together these two conditions imply, by Lemma 2-2-2,

that the matrix [D12 Q13] iS maximum row rank.
J

174

Conversely, assume [Q12 Q13] is maximum row rank.
Then by Lemma 2-2-2, (8;2(J SE3) and (sgztj 5:3) contain
a dendroid of B (G X (Spl U sgz U SE3 U 8%4 U S§5)) and
C (G ° (Spl U 5’52 U 833 U 82:4 U 52:5» reSpectively so there
is no cutset contained in (Sple sg4lj 835) and no Circuit

contained in (Sple 5;4{J 5:5).

 

Corollary 4-1-2: If in addition to the hypothesis of Theorem

 

4-1-2, P—l(t) in (4-1-3) is bounded for all t 3 t0 and the
following two conditions are satisfied:

1. There is no Circuit contained in (Spl(j Sp4 Llsgs)
other than those Circuits contained in (SE1 U Sg4 U 52:5).

2. There is no cutset contained in (Spl LlSp4lJ sgs)
other than those cutsets contained in (SglL/Sé4 bisgs). Then
any solution to the system is asymptotically stable.

Egggfz The submatrix [D12 Q13] is maximum row rank by
Lemma 4-1-3. Therefore by the Corollary of Lemma A4, J(t)
iS negative definite.

It follows from (4-1-7) that K-l(t) is bounded for

all t>t.
- o

175

The Scalar function of (4-l-ll) iS positive definite.
It is also decrescent by Theorem 1.2 of [HA-1]. Along the
trajectories, v is negative definite so for initial instant

to, any solution to the system is asymptotically stable.

 

Theorem 4-1-3: If in (4-1-3) P(t) is positive definite and

 

Symmetric, P(t)"l exists and is negative semidefinite,
C(t) is positive semidefinite and condition (4-1-5) is

satisfied for all t 3 t then any solution to the system

0’

is stable for a topology correSponding to (4-1-4).

Proof: The system model is given in (4-1—6). By Lemmas A3
and A4, J(t) is negative semidefinite. Therefore, the
Lyapunov function (4-l-ll) shows that any solution to the

system is stable.

 

The following lemma and corollary provide a suffi-

cient condition for condition (4-1-5) to be satisfied.

Lemma 4-1-4: Let the submatrix

 

 

T
‘Q23 Q33
A

of (4-1—4) be rearranged and partitioned according to posi-

tive definite or positive semidefinite components so that

176

 

 

 

 

 

 

‘2:§- _-Qlll Q112 Q211 Q2121 72$?—
223 _ ‘Qil2 Q113 Q213 Q214 2:3
2:3 ”9211 '9213 Q311 9312 ZS?
is? _'Q212 42214 421312 Q3133 £1133

where PD refers to positive definite components and PS
refers to positive semidefinite components.

Let SPD and SPS refer to the edges corresponding
to the positive definite components and positive semidefinite

components reSpectively. Then the submatrix

"' qr

T T
Q211 Q213

 

 

T T
1Q212 Q214

is maximum row rank if and only if the following two condi-
tions are satisfied:

1. There is no circuit contained in (SPSL)S§1Llsg4L/SES)
. . . . X y X . .
other than those Circuits contained in (SplL/Sp4L/Sp5), i.e.,
PS x
C(G - (5’51 U Spat} S U 82%)) - c (G - (5’51 U sly” U sp5>) = {6

and

177

. . . PS y X y
2. There is no cutset contained in (S L’splL/Sp4L/Sp5)

other than those cutsets contained in (5311/ SE4lj Sés); i.e.,

PS X X Y =
B (G X (sglu s U sp4U 535)) - B (G X (5g1 U Sp4 U Sp5)) [6.
Proof: Assume l and 2.
Conditions (1) and (2) are satisfied if and only if the

following two conditions are satisfied:

3. There is no circuit contained in (sgltj SPslj 5:5);
ie C(G-(SXUSPSUSX))=¢
. ., pl p5

and

4. There is no cutset contained in (SV

PS y .

i.e., B (G X (5%l U SPSU $55)) = B.

To show that (2) is true if and only if (4) is true,

let G

O [G x (53111 sPSU 51%)], G1 = [G x (sglus’g4uspsu 5%)]

Y X Y
and G2 [G x (spl U SP4 U sp5)].
Suppose B E B (G ) Then B K B (G ) since (Sy U Sy )
l 0 ° 1 2 pl p5
contains no cutsets by definition. Therefore

B16 B (G1) - B (G2).

178

Conversely, suppose Bl E B (G1) - B (G2). If B1

x
p4

there exists another cutset B2 6 B (G1) - B (G2) such that

contains an edge, e1, of 5:4, by definition of S

Y
132c(s;1UspS(/B1 - {e,} >.

x
If e26 (B.2 fl SP4), for the same reason as above

' Y Y _
there eXists another cutset 82C(Spl USPSUB‘2 {e2} ).
Proceeding in this fashion if ele (8140 5:4), there exists
. . y y _ . X
another Circuit Bi+lC(Spl U Sps U Bi {ei} ). Since Sp4

is finite, there exists some cutset BnCZ(Sg1(J S£5(/ SPS)°
Therefore B (GO) # fl.

Therefore (4) is true if and only if (2) is true.

The proof that (l) is true if and only if (3) is true
is identical to the above with obvious change of notation.

Let SPDX refer to the edges of SPD in the chosen
forest of (4—1-4) and SPDY refer to the edges of SPD in
thecomforest correSponding to (4—1-4).

Since there is no circuit contained in (SPSL/Sglt/Sgs),

by (2-2-2) and definition 2-2-1 , SPDX must contain a den-

droid of c (G ° (sX U sPDXU SPSU sx )),
P1 p5
Also since there is no cutset contained in

(SPS(/ Sgllj Sgs), by (2-2-2) and definition 2-2—1 , SPDy

179

must contain a dendroid of B (G X (sglLlsPDYL/SPS[/s;5)).

Together these two conditions imply, by Lemma 2-2-2,

that the matrix

,_
T T
Q211 Q213

T T
LQ212 Q214

 

 

is maximum row rank.
Conversely, assume the matrix in question is maximum

SpDX

row rank. Then by Lemma 2—2-2, and SPDy contain a

dendroid of C (G ° (SE1 U SPDX U SPSU $365)) and
B (G X (Sgllj SPDle Spstj S;5)) reSpectively so there is

no circuit contained in (8;1|J SPS(J Sés) and no cutset

. . PS
contained in (S§1(J S (J 8:5).

 

Corollary 4—1-3: Let all conditions on the component equa-

 

tions in Theorem 4-1-3 apply except that it is not known that
condition (4—1-5) is satisfied. Let the direct sum of the
algebraic equations in (4—1-3) be rearranged if necessary so
that C(t) is partitioned into the direct sum of positive

definite components and positive semidefinite components.

180

SPS

Let SPD and refer to the edges correSponding

to the positive definite and positive semidefinite components
reSpectively. If:

. . . . . S
1. There 15 no Circuit contained in (SP L/SglL/Sg4L/Sgs)
other than those circuits contained in (SX [J Sy (j Sx )
pl p4 p5 '
and
2 There is no cutset contained in (SPSUSy Lij Lij )
' P1 p4 P5
other than those cutsets contained in (Sy (l5x L/Sy )
p1 p4 p5 '
Then any solution to the system is stable.

Proof: Let the following be the above mentioned partition of

 

 

 

 

 

 

C(t).
FIWT _ ‘ —Pfi
Zs3 C11 C12 Zp3
PD PD
2 C c z
2 21 22 52
p = t — (4-1—12)
PS PS
Zs3 C33 C34 2p3
P5 P5
sz2 C43 C44 _F52

 

 

The matrix H of Lemma A7 is a rearrangement of the
rows and columns of the matrix of (4—1-5), so is nonsingular

if and only if condition (4-1-5)is satisfied.

181

By Lemma 4-1—4 and Lemma A7, condition (4-1-5) is

satisfied, and the Corollary follows from Theorem 4-1-3.

 

Theorem 4-1-4: In (4-1-3), let P(t) be nonsingular, sym-

 

metric and P'1(t) bounded for t 3 t let P(t)"l be

0’
negative semidefinite and let Zp4 be of zero order. If
C(t) is positive definite and the conditions on the topology
stated in Corollary 4—1—2 are satisfied, the system is

stable only if P(t) is positive semidefinite for all t 3 to.

Proof: By Lemma A9, condition (4-1-5) is satisfied, and the
system model is given in (4-1-6). Consider the scalar func-

tion

v = KPT P_llp

. -l . .
Since P (t) is bounded for t 3 t v is decrescent.

0’

Along the trajectories
x}: 2(1/T J(t) QJ+¢T1°><tYl¢

But J(t) is negative definite by Corollary 4-1-2 . Con-
sequently, v is negative definite, and by Lyapunov's in-
stability theorem [HA-l] the system will be unstable if

P(t) is not positive semidefinite for all t 3 to.

 

182

Part II. Nonlinear Systems

Let the topology of the system graph be such that there

exists a tree T for which:
1. The direct sum of the terminal equations for all

m components in the system can be written in the form

pl = F (251, t) (4-2-1)
Zp2
: G (252’ Zp3)
z$3

 

 

where F and G have continuous first partials in all

their arguments.

 

r
8 G11 G121

Let G = (4—2—2)
21 G22L

 

 

where the columns of G11 and G21 correSpond to the

partial derivatives with respect to the variables of 252,

and the columns of G12 and G22 correspond to the partial

derivatives with reSpect to the variables of Z 3.

2. The constraint equations of the system graph are

of the form

 

 

 

 

 

 

 

183

 

 

 

 

 

 

 

- 1 --- 1
Zsi r-Q11 Q12 Q13 Zp1
I
z = -QT Q Q 2
s2 12 22 23 p2
T T
_zs3 _:Q13 ‘Q23 Q33 [?P%.
where Q11, Q22, and Q33 are skew.
If
_ T’ c 7 _ _
U 0 G11 G12* Q22 Q23
det. - f
T
_:Q23 Q32, _G21 522‘ _? U J
for all values of (252, Zp3) and t 3 to,

0 (4-2-4)

then upon sub-

stituting the constraint equations in (4-2-3) into (4-2-1)

there results

where

J(Zsz, z

251

p3)

Qii‘ P12 (313}:

 

, T
:‘Q23 Q33

t

 

It can be shown that if G

"G

G

 

11 G12

 

21 G22

 

 

is differentiable in

 

 

 

(4-2-4) is precisely the condition that the order of the

system (i.e., the order of the state vector) be maximum.

fact, suppose (4-2—4) is not satisfied.

Then let the

(4-2-5)
_ '-V1_ -
Q22 Q2; G11 0
[0 U _ 921-3

0t,

In

Q

 

-13,

12

 

184

functionally independent algebraic equations in (4—2-1) be

differentiated with reSpect to t. Consequently, by the chain

 

 

 

 

 

rule,
2 ” * '2 ‘
p2 5G 52
= 4-2-6
i 8(252, zp3) i ( )
.. S31 ‘ Lp3_

Substituting the constraint equations (4-2-3), into (4-2-5)

and (4-2-1) gives

2

 

 

 

p1 = F (Q11 Zpl+Q12 zp2“Qi3 zp3't)
U o — G G _ T2 Q _i _. G 0 GT“
11 12 22 23 p2 11 12
- = F (4—2—7)
T ' T
‘Q23 Q33 G21 G22 _0 U _Zp3‘, G21'-U 813

 

 

 

 

 

 

The system of differential equations, (4-2-7), is of
maximum order if and only if the matrix of (4—2-4) is non-
singular. But the system (4-2-7) is obtained from (4-2-1)
and (4-2-3), by differentiating a set of algebraic equations.
Thus the order of (4-2-7) is equal to the number of function-
ally independent algebraic equations differentiated plus the
order of the system (4-2-1) and (4-2-3). Since (4-2-4) is
assumed not satisfied the order of (4-2-7) is not maximum.
Thus the order of the system (4-2-1) and (4-2-3) is not

maximum.

185

If the indefinite line integral

Zsl

91(251’t) ' d 251

o
Zsl

is a positive definite function in some half-cylindrical

neighborhood Hh,to of some point 221 in the Z81 space,

where F1(Z:l,t) s o for all t 3 to, then the system is

said to satisfy condition N1.

If the indefinite line integral

Zsl é)
J 7;? F1 (251’ t) ‘d 251
51

is a negative semidefinite function in some half—cylindrical

neighborhood Hh t for some point 221 in the 251 Space,
’ o

0

where F1(Zsl’ t) E O for all t32t then the system is

0’
said to satisfy condition N2.

In this thesis, only stability or equilibrium points
are considered with t = t0 representing the initial time.
It is assumed that Fl(Zsl, t) vanish only at isolated points
of the 251 Space.

By Theorem 1.11 of [NE-l], the conditions imposed

above on the functions F and G assure the existence of a

186

solution locally if the initial conditions satisfy the alge-

braic set in (4-2-1) and (4-2-3).

 

Theorem 4-2-1: In (4-2-1), let the matrix 81: be symmet-
8251

 

ric for all t > t . If 8G is positive definite
" ° 8(252’ Zp3)
for all 2 and Z t 3 t then each equilibrium solu-

52 p3: 0:

tion where conditions N1 and N2 are satisfied is stable.

Proof: Since 8G _ is positive definite, (4-2-4)
8(252’ Zp3)

is satisfied, by Lemma A9. Consequently, J(Zsz, Zp3) in

(4-2-5) is negative semidefinite by Lemma A4, and (4-2-5)

applies.

Consider the scalar function,fkn'the equilibrium

point, 6,
251
v = f F (251, t) - d 251 (4-2-8)
4.
Since 81: is symmetric, this line integral is independent

 

8251
of path. [KA-l] [CI-1]. When evaluated along the trajecto—

ries, v gives

187

Zs1
v = FT 2 l + I .352. d z
5 J 8t 51
9
(4-2-9)
251

_ T F ,

_ F J F1 + jr -§%—- d 251
9

Therefore, v is non-positive in a cylindrical neighborhood

Hh t of each equilibrium point, 6, where conditions Nl
’ o

and N2 are satisfied, and the theorem is proved.

 

Corollary 4-2—1: Suppose, in addition, to the hypothesis of
Theorem 4-2-1, F is bounded in a neighborhood Hh,tc, of
an equilibrium point where conditions N1 and N2 are satis-
fied, and the following two conditions are also satisfied:

1. There is no circuit contained in Spl;
and

2. There is no cutset contained in SP1.
Then the equilibrium point is asymptotically stable.

Proof: The scalar function of (4-2-8) is a function only of
251 and t, and v is decrescent by Theorem 1.2 of [HA-1],

since F is bounded for all t 3 to.

188

In this case J in (4-2-5) is negative definite by Lemma
4-1-3, the Corollary to Lemma A4, and Lemma A5.
Then v is negative definite by (4—2-9) and then

each such equilibrium point is asymptotically stable.

Theorem 4-2-2: In (4-2-1), if SP is symmetric, if

8251

 

 

28G Z is positive semidefinite and if (4-2—4) is
8( 52’ p3)
satisfied for all 252 and Zp3, then each equilibrium

point satisfying conditions N1 and N2 is stable.

‘Erggf: Since (4-2-4) is satisfied for all 252 and Zp3
(4-2-5) applies.

By Lemma A4, J (252, Zp3) in (4-2-5) is negative
semidefinite.

The scalar function of (4-2-8) is, as in Theorem
4-2-l,only a function of 281 and t, and v in (4-2-9)
is non-positive in a cylindrical neighborhood Hh,to of

each equilibrium point where conditions N1 and N2 are

satisfied. Therefore, each such equilibrium point is stable.

 

Corollary 4-2-2: Suppose all the hypotheses of Theorem 4-2-2

 

are satisfied except that it is not known whether condition
(4-2-4) is satisfied.

Let the direct sum of the algebraic equations in
(4-2-1) be rearranged if necessary so that G is partitioned

into the direct sum of positive definite components and

189

positive semidefinite components. Let SPD and SPS be as

in Corollary 4-1-3, and SK

p1 and 5%, as in Part 1 of this

chapter.
If:
. . . . . PS X
1. There is no Circuit contained in (S L/Spl),
and
2. There is no cutset contained in (SPS L/sgl), then
any equilibrium point satisfying conditions N and N is

l 2
stable.

Proof: Let Eh; be partitioned as in (4—1-12).
8(252 ’ Zp3)

Then the matrix H of Lemma A7 is a rearrangement of the

 

rows and columns of the matrix of (4-2-4) so is nonsingular
if and only if condition (4-2—4) is satisfied. Lemma 4-1-4
applies Since Sp4 and Sp5 are null.

By Lemma 4-1—4 and Lemma A7, condition (4-2-4) is

satisfied, and the Corollary follows from Theorem 4-2-2.

 

F .
Theorem 4—2-3: In (4-2-1) let 8 1 be Symmetric. Let

2S251

t) be bounded in a neighborhood Hh t of an equi-
’ o

 

Fl(zsl’

librium point, 6. Consider the line integral

v = J F1 (251, t) - d 251 (4-2-10)
6

190

 

If 8G is positive definite, if condition N2 is
Ekzsz, zp3)
satisfied in Hh t and if there is no circuit or cutset
’ 0

contained in S then the equilibrium point, 6, is stable

pl’
only if the line integral in (4-2-10) is positive semidefinite

for t 3 t in a neighborhood of the equilibrium point.

0

F . .
Proof: Since .égzl— is continuous and symmetric, v is a
51

function only of 251 and t, and v is decrescent in

H by Theorem 1.2 of [HA-l] since F1 (251’ t) is

h,t0
bounded.

As in Corollary 4-2-1, J in (4-2-5) is negative
definite by Lemma 4—1—3, the Corollary to Lemma A4, and
Lemma A5.

Then v is negative definite by (4-2—9).

If v in (4-2-10) is not positive semidefinite in
some neighborhood of the equilibrium point for t 3 to, the

equilibrium point is unstable by Theorem 5.2 of [HA—l].

The Theorem follows.

 

Conclusion

Although the stability theorems given in this thesis
are restricted as to component type and system topology, they
apply to a useful class of systems. In general, most systems

of purely dynamic orpmre algebraic components are covered.

191

Theorem 1 is particularly useful when the system contains
only constant coefficient dynamic components. The theorems
on linear systems cover certain classes of systems contain—
ing n-terminal perfect couplers, gyrators, and transistors
and vacuum tubes having sufficient forward conductance or
negative feedback to make the coefficient matrix in the com-
ponent model positive semidefinite.

The primary limitation of the theorems on stability
of nonlinear systems is the restriction to the stability of
equilibrium points and the inability to include excitation
functions. The theorems, however, apply to Systems including
such components as nonlinear two-terminal semidefinite compo-
nents, to which there has been some literature devoted, non;
linear perfect couplers, gyrators and vacuum-tube type,
elements.

In addition to their application to particular sta—
bility studies the theorems also show that, given certain
topological configurations, it is possible to go from a
stable to an unstable system only by altering the component
parameters so as to introduce indefinite coefficient matrices

in the component models.

CHAPTER V
APPLICATIONS AND EXAMPLES

The purpose of this chapter is to Show some applica-
tions of the theorems developed in the preceeding chapters.
During the discussion an attempt is made to Show the advan-
tage of these methods over classical methods.

Part I. Application of Grassman
Algebra to Topological Analysis

Topological analysis is a means of computing linear
time—invariant network functions, such as transfer and driv-
ing point admittances or impedances, by inspection of the
network without actually expanding various determinants and
cofactors. The topological methods provide a Short-cut in
evaluating network determinants and cofactors. All these
methods use the Cauchy—Binet determinant expansion and the
unimodular property of cut-set and circuit matrices. All
methods so far devised have assumed the impedance (or admit-
tance) matrix exists for all components [SE-l]. I

The theorems of this thesis and the theory of Grass—
man Algebra provide an essentially new technique of topolog-

ical analysis. As opposed to older methods, this technique

192

193

is simpler both computationally and conceptually and applies
to all linear time-invariant components. This method
applies universally no matter whether the impedance, admit-
tance, or neither matrix exists.

Before explaining this new technique, some defini-
tions and discussion about the algorithm of Chapter III are

needed.

 

Definition S-l-l: Let a system, «{CE, G, B}', have compo-
nent equations in form (3-1-32) with possibly some driver
type components included in (3-1—32). (See Def. 3-1-1.)

Then the system matrix of ‘{CE, G, B} is given by K0 in

 

Theorem 3—1-4.

Definition 5-1-2: The system determinant of system

 

{CE, G, E} is the determinant of the system matrix of
{012, G, F}.

Suppose the system, -{CE, G, B}, contains some
driver type components. Let {CE1, G', g} be the subsystem
of ‘{§El, G, E} that is described in Theorem 3-1-1. In
view of Theorem 3—1-1 and Corollary 3-l-l, to determine
whether the system CE, G, F has a unique solution, it
suffices to examine the subsystem '{CE1, G', E} for a non-
zero system determinant. Therefore in the algorithms of
Chapter III, the system determinant for '{CE1, G', E}> is
examined. The system determinant of {CE, G, E}- is differ-

ent from the system determinant of {CE1, G', E}; However,

194

Theorem 3-1-4 holds for any system matrix of form KO so
can be used to evaluate the system determinant of «{CE, G, E}.
It follows that if Ji in (3-1-41) is formed for component
equations CE (instead of CEl) and X is formed for graph
G (instead of graph G'), (3-1-41) gives the system determi-
nant of CE, G, 6}.

Suppose G has t edges in a forest. An outer

product, P, of the graphic vector Space of G is
[Ff [32... Q] (544)

where /? i=l,...,t, is an incidence vector [FR-l], and
F: #' F3 for i # j. By [KI-l], the incidence matrix,
[FR-l], is unimodular so every coefficient in the expansion
of (5—1-1) in terms of the basic unities is I l, or O.

The vector, X, to be substituted in (3-1—41) for
the graph G, can be taken directly from the outer product
(S-l-l). It is simply the vector of coefficients in the
expansion of (5-1—1) in terms of the basic unities.

Algorithm 2 is simply another method of obtaining
the matrix Ji of Algorithm 1. Therefore in this chapter
the results will be given only for systems with components

of the general form (3-1-32).

195

The General Transfer Function

Suppose one wants to know the ratio between the
response of one system variable and an excitation. Such a
ratio is called a transfer function. To determine a trans-
fer function, all internal sources in the system are set
equal to zero and a Specified non—zero driver, (either thru
or across), is inserted between two chosen vertices as an
excitation. The reSponse of the other system variable is
then measured. Fortunately for linear time—invariant sys-
tems, the entire process can be done analytically.

Let the system ‘{CE, G, B}> of Definition (5-1-1) be
given. Let the given excitation variable be xj (or yj),
the reSponse variable xi (or yi), and place all other

Specified functions equal to zero. The resulting system

equations for {CE, G, H}~ can be written as either:

 

 

 

 

1. if xj is the excitation .. _‘
"(T 1 o o o o o- it. .?1(t7
R1 0 E11 E12 0 E21 E22 x o
o 131 132 B3 0 o 0 xi — 0
Lo_ 0 o 0 Al A2 A3__ J _o _
Y
..Yi_ (5-1-2)

 

 

or

196

 

 

 

 

2. if yj is the excitation, ____
E77 0 o o 1 o G_—1 i3 fl(t)
R1 0 E11 E12 0 £21 522 X _ o
0 B1 82 B3 0 O 0 xi 7 0
o o o 0 A1 A2 A3 yj _0 __
"‘ —__I Y
Vi (5-1-3)

 

 

where x. x., y., y. are variables corresponding to their
1

J’ J 1
reSpective edges, X and Y are vectors containing the
remaining system variables, R1 is the appropriate sub-
matrix of R in (3-1-32), and Ai and Bi for i=1, 2, 3,
are suitable partitions of A and B of (2-3-1).

There are four possible transfer functions, two with
x. as excitation, and two with yj as excitation. From

J
(5-1-2) and (5—1-3), they can be computed as:

 

 

 

 

 

Xi = Ai1
xj AX
Y1 = Ali
Xj [5X
(5-1-4)
Xi = Ai1
yj AY
yi £511

 

 

197

where Ail is the cofactor of the first row and the
column correSponding to Xi’ Ali is the cofactor of the
first row and the column correSponding to yi, Ax is the

system determinant for (5-1-1), and [1y is the system
determinant for (5-1-2).

Suppose graph G has t edges in a forest. Then
the determinant AX (or Ay) can be formed by the follow-

ing algorithm.

Algorithm 3

 

If Ax is wanted, consider the matrix

0 l O O O O 0

(5-1-5)
R1 0 E11 E12 0 E21 E22 ’
obtained from (5-1-2).
If Ay is wanted, consider the matrix
0 O O O l O O
. (5-1-6)
R1 9 E11 E12 9 E21'522 : -
obtained from (5—1-3). Let
1 o o o o o ‘
E1X = and E2X =
0 E11 £12 0 521 E22

so (5-1-5) is equal to

198

O
R E1x E2x
l .
Similarly let
0 O O 1 O O
E = and E =
1y 2y
0 E11 E12 0 E21 E22
so (5-1-5) is equal to
O
R Ely E2y
1
Let Elx’ EZX? Ely’ E2y each have n columns, and number

them from 1 to n in their natural order. If Ax is
wanted, determine the values of all (3)2 determinants of

the maximum order submatrices, Li, of (5-1-5) that contain

all columns of R1 and t columns of E If Ay is

wanted, determine the values of all

lx'
n
t

the maximum order submatrices, Lz, of (5-1-5) that contain

 

2
) determinants of

all columns of R1 and t columns of Ely'

For each matrix, B, of Lt' let (k) represent

the sequence of columns of B from Elx (or Ely’ if Ay

is desired), and (m) the sequence of columns of E (or

2x
B ) not in B.
2y
Then proceed as follows:
1. Form the square matrix J: (JZ) made up of the determi—

nants of each element of L: (L¥), where the rows of

199

J: (JZ) correSpond to the sequences (k), the columns

of J: (JZ) correSpond to the sequences (m), and if
if (k) = (m) the corresponding entry is on the diagonal
of J: (JZ). Therefore, the ,(k,m) entry of J: (JZ)

correSponds to the sequence (k) and to the sequence (m).

2. For each column of J: (J:)’ evaluate the sum

t

2(m) = 112:1 mh, where (m) = (ml,...,mt).

If the sum is odd, change the sign of all entries in
this column of J: (JZ). Let the resulting matrix be
called JX

ts
Sponds to evaluating the function sgn. [(m)].)

(J:s)' (By definition (3~l-5), this corre-

3. Form the outer product, P, of (5—1-1) for graph G.
4. From P, obtain x as the row vector of coefficients

of the terms of P in its canonical form.

5. Then
_ T
AX - (:1) [X st X ] (5-1—7)
and
_ , Y T'
Ay — (:1) [[X Jts X] (5-1-8)

where it is understood that entries corresponding to the

same sequences are multiplied together.

The proof of this Algorithm, as that for Algorithm-l,

follows from Theorem 3—1-4. The (:dL)sign is in (5-1-7) and

200

(5-1-8) since the cutset and circuit unimodular matrices of
(5-1-2) and (5-1-3) can be chosen and their rows ordered
many different ways, thereby changing the Sign of the deter-

minants, A and Ay' Certainly the cutset and circuit

x
matrices can be chosen to make both (5-1-7) and (5—1-8) a

 

 

 

 

(+1).
The cofactors Ail and Ali of (5-1—4), can be
written as follows:
,A : n+r - -
i1 (‘1) det. R1 0 E11 0 E21 E22
0 Bl B o o 0 (5-1—9)
_0 O 0 A1 A2 A3‘
A 2n+r ... —
11 = (-l) det. R1 0 E11 E12 0 EZL
0 B1 32 B3 0 o (5-1—10)
LC 0 O 0 A1 A2
where r is the number of columns of R1.

By a procedure analogous to the proofs of Theorems

3-1-4 and 3-1-5, the following algorithm can be devised to

evaluate (5-1—9) and (S—l-lO).

Algorithm 4

If A11

M0 = [R1 0

is wanted,

consider the matrix

E11 E21 E22]

obtained from (5-1-2), or (5-1-3), where the

1 column matrix.

(5-1-11)

matrix is a

201

If Ali is wanted, consider the matrix

M1 = [R1 E11 E12 0 £21] (5-1-12)

obtained from (5—1-2), or (5-1-3), where the 0 matrix is a

1 column matrix.

Let Eil = [0 E11] and Ei2 = [E21 E22] so
(5-1-11) is equal to [R1 Bil E12]. Similarly let
Eli = [Ell E12] and E2i = [0 E21] so (5-1-12) is equal

to [R1 Eli E2i]' Let Eil’ Eli’ Ei21 E21 each have (n-l)
columns and give them the same numbers as their corresponding

columns in (5-1-5) and (5-1-6).

 

 

If [Ail is wanted, determine the values of all
n- . . . i1
t-l determinants of the maXimum order submatrices, Lt—l
of (S-l-ll) that contain all columns of R1 and t-l columns
of Eil'

2
If Ali is wanted, determine the values of all 6‘?)

li
determinants of the maximum order submatrices, Lt , of

(5—1-12) that contain all columns of R1 and t columns of

Eli.

il Lli
t-l (or t

represent the sequence of columns of B from Ei1 (Eli),

For each matrix, B, of L ), let (k)

and (m) the sequence of columns of B12 (E2i) not in B.

Then proceed as follows:

202

Form the square matrix J11 (J1

i
t-l' t ) made up of the

determinants of each element of Liil (Lil), where

the rows of inl (Jil) correSpond to the sequences

11 (J11

(k), and the columns of Jt-l t

) correspond to the

sequences (m), and if (k) = (m) the corresponding

i1 li

t-l (Jt ). There the

entry is on the diagonal of J

11 (J11) corresponds to the sequence

(k,m) entry of Jt-l t

(k) of E. (E

11 .) and to the sequence (m) of E12

11

11 (J11

1
t-l t ) eva uate the sum

For each column of J
t-l -t

E(m) = Z mh (2(m) = Z mh) where (m) =
h=l h=1

(ml""’mt_1),‘ or (m) = (ml,...,mt). If the sum is

odd, change the sign of all entries in this column of

i1 1i

Jt-l (Jt )' Let the resulting matrix be called

Ji1 (Jli) (B definition (3 l 5) this corres onds
(t-l)S ts ' y ’ p

to evaluating the function sgn. [(m)].)

 

203

3. If Zlil is to be evaluated, from X obtained in steps
3 and 4 of Algorithm—3, obtain X+i by deleting all
entries from X that correSpond to a sequence not con-
taining edge i. Remove edge i from each correSpond-
ing sequence. Similarly obtain X+j'

If 131i is to be evaluated, from X obtained in
steps 3 and 4 of Algorithm-3, obtain X_i by deleting

all entries from X containing edge i. Similarly

obtain X_j
4. Then
A = (+1) [X Jil XT ] (5 1 11)
i1 _ +i (t-l)s +j " “
_ 11 T
A11 - (:1) [X_j Jts X_i] (5-1-12)

where in (5-l-ll) and (5-1-12) it is understood that
entries correSponding to the same sequences are
multiplied together.

By keeping track of the Sign of the determinants,

the following equations can be obtained:

204

 

 

 

 

 

i1 T
f; : (_l)i+n-t Xi J(t-1)s X%
x. X
J X Jts X
_ 11 T
ZiL. _ (-1)1+1 X'J Jts x_i
xj X Jx XT
ts
(5-1-13)
i1 T
:1 _ (_1)i+n-t X1 J(t—1)s Xi
Y- y XT
3 X JtS
, 1i T
h =(-)1+1 X_J Jts X_i
yj X Jy XT
ts

The Classical Methods

As Opposed to the above two algorithms the classical
methods are based on the results obtained by Maxwell and
Kirchoff [MA-1]. For two terminal networks they obtain the
matrix Jts or something equivalent. However, to find the
vector X, the techniques given in the literature are sadly
lacking. Various "rules" have been devised for stepping
from one tree to another with a correSponding determination
of Signi [MA-2], [MA-3], [MA-4]. However, this technique
has the disadvantage that after a certain number of steps it
is possible to obtain the same tree (or forest) twice and it
is not easy to determine when all trees have been found.

The major defect here is that there is no clear and simple

205

rule to find all trees. The Grassman outer product, on the
other hand, provides a clear and simple evaluation of X,
which is easily programmed on a computer. In fact, since
for two terminal networks, the_sign of the entries of X

are of no consequence, the Grassman product can be formed in
(mod . 2) algebra .

For the general network where the impedance (or
admittance) matrix exists, Mason, Coates, and Mayeda have
all given methods based upon the formulation of two graphs
and whose common tree must be found to accomplish the analy-
sis. Again there is no clear and simple method to find all
common trees and their relative Signs. Using (5-1-1) and
Algorithms 3 and 4, Grassman algebra handles all such numer-
ical work simply and effectively, not necessitating the for-
mation of two graphs and modified equations. To use this
algorithm, neither the impedance nor admittance matrix need
exist.

Besides the above advantages, (5-1-1) handles tree
Sign and forest determination of the general linear system
program of Coates and Mayeda by a simple formation of the
Grassman outer product of incidence sets.

The advantages and the generality thus obtained
alone show that the techniques of Grassman algebra as used
in this thesis are an important mathematical tool for sys-

tem analysis.

The

1

 

[CD <5 0

The

206

Part 11. Examples

 

Example 1

Determine :2 for the following system.
x
1

component equations are:

 

 

 

 

 

o o o 0 o o 0" ‘xl? T17

1 o o 0 r2 0 0 x2 0

o 1 o o 0 r3 g3 x3 = o

O O, l O O g4 :flj x4 b _1
y1
y2
y3

' Ly“ _
graph is:

 

 

 

207

 

 

 

 

 

 

 

 

Solution:
(12) (13) (14) (23) (24) (34)
x _ ,
J2s - -(r3r4-g3g4) O O O O O
0 -r2r4 +r2g4 O O O
O O O O O O
O O O O O O
O O O 0 O O
_____ ———-1
M1 = ”'1 o o o o o 7
O l O 0 r3 g3
_O O l 0 g4 r43
(l3) (14) (34) ,.
li
J2s ' (24) “'33 +1’3 0
(34) _ O O 03
[31:61*e4:/32=ei+62*e3
[If [g]: 8182 3 - ele4 - e2 - e3e4.
Therefore
(12) (13) (14) (23) (24) (34)
X = .[ 1 1 —1 0 -1 -1]

208

 

 

 

x_2 - [ 1 -1 -l]
By (5-1-13)
1i T
lg = x-1 J23 X-z = '33 -r3
x1 X Jfis XT “r3r4*8384 'r2r4 ‘r2r3 "233 “’234
Example 2

Does the following system have a unique solution?

1. The component equations are:

l a x1 + O O y1 = f1(t)
0 0 x2 -a l y2 f2(t)
x3 + o 1 y3 = f3(t)
x4 -1 O y4 f4(t)

s+5 1 x6 s -+5s s-+1 yé] o

2 s-3 x7 s-l. s n+5 y7

209

2. The graph, G, is:

 

 

 

 

 

 

Solution: Let ={e1, e2, e3, e&, where ei E E(G),
i = 1, 2, 3, 4.
Then G - S =
2
3
1
4
and G X S =

 

By Corollary 3-1-5 , the system has a unique solution for

a f 1 and no unique solution for a = l.

 

210

Example 3

Does the following system have a unique solution on

7
L2’7 (5,15).

l. The component equations are:

 

 

F “15 m
x1(t) ts [y1(s)y2(s)+2yl(s)+sin y1(s)] ds
= +
x2(t) ts [-y1(s)y2(s)+sin y2(s)+4y2(s)] ds
J
2y1(t) + cos. y1(t)
Y2(t) + 6ty2(t)
x3(t) '2etx4(t)
y4(t) 42ety3(t)
x5(t) = sin y5(t)
Y6(t) = 4X6(t)
Y7(t) = f7(t)

2. The system graph, G, is:

211

Solution: By Lemmas BB, B9, and B10, the components corre-
Sponding to edges 1, 2, and 6 are strongly monotonic. By

Lemma B9 the component corresponding to edges 3 and 4 is

monotonic. All components also satisfy a Lipschitz condition.

I x .
The graph G (sp3 Usp4 Uspé) 15
+
3

y .
The graph G X (Sp3 L’Sp4 LISpé) is
\I
4

Therefore, by Corollary 3-2-2, the system has a unique

solution.

 

Example 4

Is the following system stable?

1. The component equations of Type 1 are:

x1 = 5 1 yl

x2 1 6 y2

y3 0.5t +1 0 1‘ "x31

y4 = O 3 1 x4
1 l 2 x

LYS _ _ L.§

 

 

 

 

 

 

212

 

 

 

213

Solution: Take forest T0 =‘{}, 2, 6, 9, ll, 13

x . .
The graph [1: G X (E(G) - Sp5)] (E(G) - Sp5)] is.

11 8

 

By Corollary 4-1-1, the system is not stable for a < O,

and stable for a > O.

CHAPTER VI
SUMMARY

The principal results of this thesis are as follows:
Grassman algebra is shown (in Algorithms l, 2, 3, and 4)
to be the abstract mathematical discipline that enables
one to calculate more Simply and concisely the determi-
nant functions that describe the behavior of linear
time-stationary systems.

In Theorems 2-1-3 and 2-1-6 and Corollary 2-1-2, two new
results are given in the theory of Grassman algebra which
are used in the algorithms.

The chains of integers of Tutte's matroid theory are
extended to real vector Spaces.

A foundation is given for the relationship between graph
theory and the Grassman outer product of a vector sub—
Space. This knowledge is extremely useful for the
methods of topological analysis and synthesis.

For the first time this thesis has shown the intermediate
role which matroid theory plays in the establishment of
the connection between the graph and its two related

vector subSpaces.

214

10.

215

An important new theorem (Theorem 3-1-3), is derived
which gives the necessary and sufficient condition for

a unique solution for linear Systems with semidefinite
components.

Mappings in Hilbert Spaces are analyzed in the light of
present system theory and two new theorems given
(Theorems 3-2-1 and 3-2-2).

Two very general theorems for Systems of algebraic and
differential equations are given. These theorems encom-
pass practically all previously published results
(Theorems 3-2-3 and 3-2-4).

The graph theoretical Lemmas of Chapters III and IV pro-
vide some important direct connections between graphs
and the representative matrices for their subspaces.

The stability theorems provide direct relations between
the graph equations, the component equations, and the

system solution characteristic of stability.

 

[BAR-1]

[BE-1]

[BE—2]

[BEN-1]

[BI-1]

[BI-2]

[BOS-l]

[BR-1]

[CI-1]

[CR-1]

BIBLIOGRAPHY

Barrett, J. F. "The Use of Functionals in the
Analysis of Nonlinear Physical Systems,”
Statistical Advisory Report, Ministry of Supply,
Great Britain, Jan. 1957.

 

Bellman, R. Stability Theory 9f Differential
Equations, McGraw-Hill, 1953.

 

 

Bellman, R. Introduction to Matrix Analysis,
McGraw-Hill, 1960.

 

”1‘ amp-fiat All-V-“ ...\‘.-P‘
.

Bendixson, M. I. "Sur Les Racines D'une Equation
Fondamentale," Acta Mathematica, Vol. 24, 1902,
pp. 367-370.

 

Birkhoff, G., MacLane, S. A Survey of Modern
Algebra, MacMillan Company, 1953.

 

Birkhoff, G., Diaz, J. B. "Nonlinear Network
Problems," Quart. of Applied Math., Vol 13,
Jan. 1956, pp. 431-443.

 

Bose, A. G. "A Theory of Nonlinear Systems,"
M.I.T. Research Laboratory of Electrogigs Report
No. 309, Cambridge, Massachusetts, 1956.

 

Browder, F. E. "The Solvability of Nonlinear
Functional Equations," Duke Math. Journal, 1963,
p. 557.

 

Civita, T. Levi. The Absolute Differential Calculus,
Blackie & Son, Ltdi, 1929.

 

Chrystal, G. “A Fundamental Theorem Regarding the
Equivalence of Systems of Ordinary Linear Differ-
ential Equations, and Its Application to the
Determination of the Order and the Systematic
Solution of a Determinate System of Such
Equations,” Trans. of the pral Soc. of Edin.,

Vol. 38, Pt. I, 1895, pp. 163-173.

216

[DE-l]

[DU-1]

[DU-2]

[DU-3]

[DU—4]

[DU-5]

[PO-l]

[FR-1]

[GA—1]

[GR-1]

[HA-1]

[HO-l]

[IN-l]

[KA-i]

[KI—1]

[KO-1]

217

Desoer, C. A., Katzenelson, J. "Nonlinear R.L.C.
Networks," Bell System Technical Journal,
Jan. 1965, p. 161.

Duffin, R. J.
Math. Soc., Vol. 52,

"Nonlinear Networks I," Bull. Am.
1946, pp. 833-838.

 

Duffin, R. J. "Nonlinear Networks II," Bull. Am.
Math. Soc., Vol. 53, 1947.

 

 

Duffin, R. J.
Math. Soc., Vol. 55,

”Nonlinear Networks III," Bull. Am.
1949, p. 12.

 

Duffin, R. J. "Nonlinear Networks IV," Proc. Am.
Math. Soc., Vol. 4, 1953, p. 233.

 

Duffin, R. J. "Analysis of the Wang Algebra of
Networks," Trans. Am. Math. Soc., 1959.

 

*n “‘4‘.“- Wu“?

Forder, H. G. The Calculgs of Extension,
Cambridge University Press, 1941.

 

Frame, J. S., Koenig, H. E. ”Applications of
Matrices to Systems Analysis," IEEE Spectrum,
May 1964.

 

Gantmacher, F. R. The Theory of Matrices, Vol. 1 &
2, Chelsea Publishing Co., 1959.

 

Graves, R. L., Wolf, P. Recent Advances in
Mathematical Programming, McGraw-Hill, 1963.

 

Hahn, Wolfgang. Theory and Applications of Lyapunov's
Direct Method, Prentice-Hall, 1963.

 

Hohn, F. E. Elementary Matrix Algebra, MacMillan
Company, 1958.

 

 

Ince, E. L. Ordinary Differential Equations, Dover
Publications, 1926.
Kaplan, W. Advanced Calculus, Wiley & Sons, 1953.

 

Kim, W. H., Chien, R. T. Topological Analysis and
Synthe§is of Communication Networks, Columbia
Univ. Press, 1962.

 

Koenig, H. E., Tokad, Y. A., Kesavan, H. K.
Analysis of Discrete Physical Systems, McGraw-
Hill, to be publiShed in 1965.3

 

[LE-1]

[MA-1]

[MA-2]

[MA-3]

[MA-4]

[MAC-1]

[MC-1]

[MI-1]

[MI-2]

[NE-1]

[on—1]

[PA-1]

[RI—1]

[no-1]

218

Lefschetz, 5. Differential Equations: Geometric
Theory, Interscience Publishers, Inc., 1957.

 

Mayeda, W., Seshu, S. "Topological Formulas for
Network Functions,” Bull;_No. 446, Univ. of 111.
Engr. Exper. Station, 1957.

 

Mayeda, W., Van Valkenburg, M. E. "Analysis of
Non-Reciprocal Networks by Digital Computers,"
Inst. Radio Engrs. Nat'l.Convention Record,
Vol. 6, Pt. 2, 1958, pp. 70-73.

Mayeda, W. "Topological Formulas for Active
Networks," Proc. of_Nat'l. Elec. Conference,
Chicago, Vol. 15, 1958, pp. 1-13.

Mayeda, W. "Reducing Computation Time in the
Analysis of Networks by Digital Computers,"
IRE-Trans. PGCT 6, 1959, pp. 136-137.

 

MacLane, Saunders. "Grassman Algebra and
Determinants," Lecture Notes, Univ. of Chicago.

 

Frank, P., McFee, R. ”Determining Input-Output
Relationships of Nonlinear Systems by Inversions,”
IEEE Trans. on Circuit Theory, CT-lO, June, 1963.

 

Minty, G. J. ”Monotone Networks,” Proc. Royfl Soc.
London, 257A, 1960, pp. 194-212.

Minty, G. J. "Monotone (Nonlinear) Operators in
Hilbert Space,” Duke Math. Journal, Vol. 29,
1962, pp. 341-346.

 

Nemytskii, and Stepanov. Qualitative Theory of
Differential Equations, Princeton Univ. Press,
1960.

 

 

Ore, Oystein. "Theory of Graphs,” Am. Math. Soc.,
Providence, R. I., 1962.

Paul, John C. "An Application of Modern Algebra to
Engineering Graph Theory,” Un ublished Thesis,
Oklahoma State Univ., Dept. o Elec. Engr.,

May 1963.

Riesz, P., Nagy, 5. Functional Anal sis, Frederick
Ungar Publishing Company, 1955.

Royden, H. L.
1963.

 

Real Analysis, MacMillan Company,

 

[SE-1]

[TU-l]

[TU-2]

[TU—3]

[TU-4]

[TU-5]

[WI-l]

[WIE-l]

[ZAH-l]

[ZAH-Z]

[ZAM-l]

219

Seshu, 5., Reed, M. B. Linear Graphs and Electrical
Networks, Addison-Wesley Publishing Company,
1961.

 

Tutte, W. T. ”A Class of Abelian Groups,"
Canadian J. of Math., Vol. 8, 1956, pp. 13-28.

Tutte, W. T. "Homotopy Theorem for Matroids I,"
Trans. Am. Math. Soc., Vol. 88, 1958, pp. 144-
160.

 

Tutte, W. T. "Homotopy Theorem for Matroids II,"
Trans. Am. Math. Soc., Vol. 88, 1958, pp. 160-
174.

 

Tutte, W. T. "Matroids and Graphs," Trans. Am.
Math. Soc., Vol. 90, 1959, pp. 527-552.

 

Tutte, W. T. ”An Algorithm for Determining Whether
a Given Binary Matroid is Graphic," Proc. Am.
Math. Soc., Vol. 11, 1960, pp. 905-917.

 

Wirth, J. L. "Time Domain Models of Physical
Systems and Existence of Solutions,",Ag
Unpublished Thesis, Elec. Engr. Dept.,
Michigan State University, 1962.

Wiener, N. Nonlinear Problems in Random Theogy,
Wiley and Sons, 1958.

Zadeh, L. T. Linear System Analysis, McGraw-Hill,
1963.

Zadeh, L. T. ”A Contribution to the Theory of
Nonlinear Systems,” Journal of the Franklin
Institute, Vol. 255, 1953, pp. 387-408.

 

Zames, G. "Functional Analysis Applied to
Nonlinear Feedback Systems,” IEEE Trans. on
Circuit Theory, CT-lO, 1963, pp. 392-404.

 

 

APPENDIX A

ON POSITIVE DEFINITE AND SEMIDEFINITE MATRICES

Lemma Al: Any positive definite matrix is nonsingular.

 

2£ggfz Since A is positive definite it follows that A + AT
is positive definite and has positive eigenvalues [BE-2].
By Bendixson's theorem [BEN-l], the real parts of
the eigenvalues of A are between the minimum and maximum
eigenvalues of A + AT. Therefore, A has eigenvalues with

positive real parts, and A is nonsingular.

 

Lemma A2: The inverse of a positive definite matrix is

 

positive definite.

Proof: Let A be positive definite and Y % 0. By Lemma A1,
A is nonsingular. If Y = AX then X i O and it follows that

YT A'1 Y = XT AT X = XT A X > 0.

 

T

Lemma A3: If A is positive semidefinite, B AB is positive

 

semidefinite for arbitrary B.
Proof: Let Y be an arbitrary vector and let X = BY, then

YT ET A B Y = XT AX 3 o

 

220

 

221

Lemma A4: Let

 

 

 

 

T 1

C1 0
C5 -

C3 -U

Let

r !

C1 C2
C :

C3 C4

L _J

 

be positive Semidefinite, Q11 and Q22 skew and U the

unit matrix and assume

 

 

 

 

 

 

 

’5. H F‘ H r— -1 1
U 9 C1 C2 911 C212
_ : D
T
-Q12 Q22 C3 C4 0 U
L "" L- —[ L ..J

 

is nonsingular. Then D'l C5 is positive Semidefinite.

T

Proof: Let Y # O. Y = D X for some X, since D is non-

singular, and X #10.

YT D‘l C5Y = XT CSDTX _>_ o

 

 

 

 

 

 

 

 

since
7 ~ 7- — T r'T T:
Cl 0 U "Q12 811 UH C1 C3
T _ _
05D — ... _-
T T T T
LC3 “U, L0 “Q23 _Qiz 1: .02 C42
-— Ab

 

 

 

mum

222

 

 

 

 

_ - t‘ T T T
C1 0 “C1Q11C1 ‘C1812+C1Q11C3 1
+
T _ T T T T _ _ T T+ T ‘Ti T
LP3+C C4. L.C3Q11C1+Q12C1 C3Q12 C3Q11C3 Q12C3 Q22_.
so C DT has the same symmetric part as C, and is there-

5
fore positive semidefinite.

 

Corollary: If in addition to the above, C is positive

 

definite, D is positive definite.

 

 

Lemma A5: If A is positive definite and B has maximum

column rank, then BTAB is positive definite.

Proof: Let Y # O, X = BY. Since B has maximum column

rank X % o and it follows that

YT BT ABY = XT AX > o

 

Lemma A6: The matrix

 

 

 

C1 C2
C:
LC3 C4

is positive definite, if and only if the matrix

_ -

—1 —1
C1 - C2C4 c3 c204

-1 -1
C4

 

 

is positive definite.

 

223

. = _ —1 —1 - -
Proof. Let A (Cl C2C4 C3) . If either KO or C is

positive definite A’l exists and is nonsingular. The matrix

-1 — 1-

c1 c2} A —A 02c4

—1 -1 -1

1
L:C4 C3A C + C4

‘

C3A C2C4

 

 

 

 

3:9 .3—

is positive definite if and only if C is positive definite

by Lemma A2. Therefore the matrix

 

 

 

 

 

 

FA"1 0" r"(:1 CZU‘l "(A"1)T c§<c4‘l)T1 3
K1 = 1
LC4 c3 U3 L03 C43 L 0 U a
" -1 T T -1 T 411
(A ) (C3(C4 ) - 02c4 )
—1
L 0 C4 .

 

 

is positive definite if C is positive definite. Let
K2 = K1 + KlT, so K2 is positive definite if and only if

K1 is positive definite, but K2 is twice the symmetric

part of K0' Therefore K0 is positive definite if and

only if C is positive definite.

 

224

Lemma A7: If the matrix -

 

 

 

 

 

 

r‘ -1 h- —
i Q111 Q112 Q211 Q2121 :C11 C12 {—U 0 O O -1
Q 3 i-T :
I U U 0 O E C21 C22 , ‘Q112 9113 9213 Q214
‘ I
11=‘ T ; - .
-Q£11-Q213 Q311 Q312 C33 C34 : U U U 0
T T T
._O O O U _ C43 C44J‘:Q212'Q214'Q312 Q3r3,
r n " "
C11 C12 C33 C34
where is positive definite and
C21 C22 C43 C44
.—J L ...1

 

 

is pOSitive semidefinite, Qlll’ Qll3’ Q3ll’ and Q313 are Skew and

F
T T
Q211 Q213 , .
has maximum row rank, then H is nonSingular,

 

T T
C8212 Q21AJ

Proof: Premultiply H by the nonsingular matrix

F T

U ”Q112 O "Q212

O U 0 O ’

T
O Q213 U ‘Q312

 

 

L0 O O U

 

 

 

 

 

 

 

 

225

 

C43 C44‘

to obtain:
Q111 O Q211 O
0 U o 0
H1 = T o
"Q211 O Q311
L o o 0 U_
'_' - - '-hE c
U Q112 O Q212 11 12
0 U o o 021 022
T
— c
Q213 Q312 33
i
o o 0 U
1. _.L
'— 1F
Q111 O Q211 O
0 U o o
T
‘8211 O Q311 O
o o 0 U
L— ..J
'E +Q c QT c
55 212 44 212 25
C52 C22
— T T T
Q21305243462212 Q213C22
T
‘9449212 0

U 0 O O

-Q112 U Q213 9

O O U 0

 

 

 

 

C25Q213"Q212Co4
C22 Q213
C+QT CQ

66 213 22 213

C64

T T
;Q212 0"(2312 U.

'inzc4

4

 

 

fi

where

 

OOOC

The matrix

 

—

C55

C

2
L_5

C

22

 

226

O

Q214
O

OCOO

 

Q313

Q112 C21
C22 Qiiz
Q112 C22
Q312 C43
Q312 C44

T
C44 Q312

 

so is positive definite.

The matrix

—

 

Coo

C

C C
64 44
L

1
46

 

d

r.

U

0 U

L

 

so is positive semidefinite.

‘Q312

T T
- C12 9112 + 9112 C22 9112

 

C11

C21

 

 

.—

 

 

 

 

T T
' C34 Q312 * Q312 C44 Q312

T

112
L

 

T
'Q312
L

 

 

 

227

The matrix C

22 so has a pOSitive

is positive definite

 

 

definite inverse by Lemmas Al and A2. Premultiply H1 by
the nonsingular matrix
1 -
—1
'U C25022 0 “Q212
—1
o 022 o o
T
o Q213 -U o
o o 0 U
L ._
to obtain
C77 C78 '8211 ‘Q212
C87 C88 "Q213 ”Q214
H2 = T T T T
— — - +
Q211 C46Q212 Q213 C46Q214 Q311 Coo C46Q313
T T 'T.
C44 Q212 +C448214 ‘Co4 'U'C44Q313
where
c = -Q + C - c c '1 c
77 111 55 25 22 52
c = c c '1
78 25 22
c _ -1
87 ‘ "C22 C52
0 - c '1
88 ‘ 22 "Q113

 

 

 

 

 

 

228

 

 

 

 

By Lemma A6, and the fact that Qlll and Q113 are skew
' -[

C77 C78

is positive definite.

C87 C88
L ._
Let
f' -I ...l -—l n—

T _ T T T

Q211 ' C46 Q212 Q213 ' C46 Q214 C77 C78 K1

0 QT c QT C c K

L 44 212 44 214 L 87 88 3

Premultiply

 

to obtain

C77

 

H2

0
U
-K2

-K4

C78 ‘Q211 ‘9212

by the nonsingular matrix

0 C: O O

 

lCOOOI

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

229

 

 

 

 

 

 

 

 

 

 

 

 

 

 

where
K5 K6 1"Q311'*Coo C46 Q313
H4 - -
K7 K8 ‘Co4 U"C44 Q313
L 2 i J
I T T T T " F ‘ I ‘
* Q211"C4o Q212 Q213"C4o Q214 D1 Dz Q211 Q212
c T c T D D Q
44 9212 44 9214 3 4 213 9214
_ _ J L J
P - F "r—l
D1 D2 C77 C78
where = so is positive definite.
D3 D4 C87 C88
5. .1 L _l
Now H3, and hence H is nonsingular if and only if
the matrix H4 is nonsingular. Expand H4 as
C66"8311 C46 Q313
H4 =
'Co4 U ‘ C44 Q313
P T —
U “C46 Us DoT
+
0 C44 D7 D8
L _ e l
where
P III '- T T "1 " q "' -
D5 D6 Q211 Q213 D1 D2 Q211 Q212
T
D7 Us 9212 9214 D3 D4 9213 9214
L _ L _ L - E J

 

230

Since

r -
T T

Q211 Q213

T T
Q212 Q214

 

 

b

is maximum row rank, by Lemma AS the matrix

 

 

is positive definite.

Now combine all factors of H4 so

 

 

 

 

— q
Coo ' C2311 *Ds ' C46 D7 C46 C2313 *Do ' C46 D8
H =
4
'C64 * C44 D7 U - C44 9313 * C44 De
-— —J
- 1
C66 H31 ' C46 E3 ‘046 E4 ”*2
“C64 * C44 53 U * C44 E4
where
7 '1 '7 7
El E2 D5 ‘ Q311 Do
E3 E4 D7 D8 ' Q313
L .1 L ..

 

 

 

 

and is positive definite. Postmultiply H by the non-

4
singular matrix

231

 

 

 

 

 

 

 

 

U o
-1 1
-E E E '
4 3 4
L l
to obtain
PC +13 E E '1 E 0 +13 E '1
oo 1 ' 2 _ 4 3 ' 4o 2 4
H :
5 -1 -1
L '%4 ' E4 E3 E4 * C44 _
P. - P E ’1 E E E '17
Coo “C46 E1 ‘E2 4 3 2 4
= + 1 1
-c C -13 ' E E "
64 44 4 3 4
L l L J
The matrix
I— ‘1 f- ! F" q r— -
Coo -C4o ‘U 0 Coo C46 'U 0
'Co4 C44 0 U C64 C44 0 U

 

 

 

 

 

 

 

 

so is positive semidefinite.

The matrix

 

 

is positive definite by Lemma A6. Therefore H5 is positive

definite, so is nonsingular and therefore H is nonsingular.

 

232

Lemma A8: If M is a rectangular matrix with maximum row

T

rank, then M AM is positive semidefinite if, and only if,

A is positive Semidefinite.

Proof: If A is positive semidefinite, let X be any

vector and let Y MX. Therefore,

XTMTAMX YT AY3O

If MT AM is positive semidefinite, let Y be any vector,
since M is maximum row rank there exists at least one

vector X, such that Y = MX. Therefore,

YTAY=XTMTAMX3O

 

Lemma A9: Let

 

 

C1 C2
C :
LC3 C4

be positive definite, Q11 and Q22 skew and U the unit

matrix. Then

 

 

 

 

 

 

 

L- 1 - '-

F U 0 F231 C2 r911 912
_ : D

.. i .1 _ .1

 

is nonsingular.

 

233

Proof: Premultiply D by the nonsingular matrix

1
F U 0

 

 

T
'Qi2 ”U
L ...

to obtain

 

 

U'Cs Q11 C6
D1 =
“'07 Q11 Cs
where
' 1 F " " . '- - r ..
C5 C6 U 0 C1 02 U -Q12 0 0
= +
T

C7 C8 -Q12 -U C3 C4 0 -U 0 -Q22

 

 

 

 

 

 

 

 

 

 

so is positive definite. The matrix C8 is positive definite, and

its inverse is positive definite by Lemma A2. Postmultiply I) by

1

 

 

to obtain

F —1
U-Cs Q11 +Co C8 C7 Q11 Co

0 C

 

 

234

The matrix

F— - r- -!
05 Co U

 

 

 

 

LC7 c8 -(08‘1)T06T
—J I- .J

so is positive definite. Therefore premultiply D2 by

 

 

to obtain

7 -1 -1 ‘
C9 "811 C9 C6
D3 -
o c
L 8 J

 

 

and since C9"1 is positive definite, D3 is nonsingular.

 

Lemma A10: If P(t)"l = é% P'1(t) exists and is negative

semidefinite, and if K(t) is as defined in (4-1-6), then

K(t)"1 = c: K'l(t) is negative semidefinite.

Proof: From (4-1-7),

 

 

 

 

(- 1 F- q
-1 -_1
d K 612 +Q14 622 K 612 +QM, £22
'5'? =
T T
E21 * 622 914 522 E21 +£22 Q14 522 J
L. _J _
W [- '1
FU 0 T U 0
_. [dd—t" P-1(t)] which is negative
._ T T
Q14 U 814. U

 

 

 

 

. . . a '_ . . L . -. .
semidefinite so K 1 is negative semidefinite.

APPENDIX B

NONLINEAR MAPPINGS IN HILBERT SPACE

In Part 2 of Chapter III, some Simple concepts from
Hilbert and Banach Space were introduced. The following
sequence of results utilize the definitions given there.

Let < , > denote the inner product in a Hilbert

Space.

Theorem Bl: Let G be a continuous mapping of the Hilbert

 

Space H into itself such that for all x1 and x2 in H,

@(xl)-G(x2), xl—x2>3 c max {l‘xlu , lllel} ”x1_x2“2
where c(r) is a positive non-increasing function of r

such that

Then G is 1-1, onto, and its inverse is continuous.

Proof: [BR-l].

 

Condition (C1): A mapping G: H-9H satisfies condition

 

(Cl) if it is continuous and for all x1 and x2 in H,
<G(x1) - G(xz), xl-x2> 3 c (max {Hle , HXZH}) ”xl'XZHZ

235

236

where c(r) is a positive non-increasing function of r

such that

J/, c(r) dr = °°.
1

Condition (L1): A mapping G: H‘TH satisfies condition (Ll)

 

if, for all ,x1 and x2 in H,

2
w - e<x2>> :cmaxfllxlll , IIX2||1> [In—en

and

<Xl‘X2’ G<x1> - G<X2>> : c (maXfllGWlL”mam"llG<X1>-G<X2>||2

where c(r) satisfies the requirements of condition (Cl)

Remark 1: If G is Strongly monotonic and satisfies a

 

Lipschitz condition. G satisfies condition (Ll).

Lemma B2: Suppose each mapping of a Set of mappings on Em

 

(the m dimensional Euclidean Space), or on L , satisfies

2,m
condition (Cl). Then their direct sum satisfies condition

(C1).

Proof: Let G be the direct sum of the mappings Gi’ and
ci(r) be the c(r) in condition (Cl) corresponding to Gi-

If h(r) = min [{pi(r):}] , then

f h(r) dr =°°
l

237

 

<<=<x1> -G<X2>, x-x> :

h Maintain, 4|me II’H u, 41ml)» “xx-x2"?

But max{]lxlill, ... ,llxmil|:}is a norm equivalent to

'lXil| on Em or L2,m.

Therefore there exists some function hl(r) such that

00
.jp h1(r) dr = <>° and
1

(mp - w x. --x2> : humaxfllxl u, “441le rang

 

Lemma B3: If X=FO(Z, Y) is a continuous function of Z

 

and Y from one Banach Space to another, and there exists a
continuous inverse in X for each Y, such that Z=F1(X,Y),

then F1 is a continuous function of X and Y.

Proof: Fix X so that

2) = o.

FO(Zl, Y1) - FO(ZZ, Y
Then ||po(zl,Y1)-FO(22,Y1)||=‘1PO(22,Y1)-FO(22,Y2)”

By the continuity of F0 as a function of Y, for every

6 > 0, there exists 8 > 0, such that for

238

“Y1 - Y2||< 8,"1=O(22, Y1) - FO(22, Y2) "<61
and ”FO(Zl, Y1) - FO(Z2, Y1) ”<61.

Now let

Then

N
ll
’1']

Therefore, for
llYl 4% 8,
[le - X2,,..,.....1 - 221:“.

since F1 is continuous at ~Y1.

For each 62, there exists 61 and a 8 such that

”Y1 - Y2 H < 8 implies ”21 - 22” < G 2.

It follows that for each fixed X, F1 is a continuous func-
tion of Y.
Also,

”F1(XU, Y3) - F1(X4, Y4)|| 5
”F1(X3, Y3) - F1(X4, Y3)|'+|IF1(X4, Y3) - F1(X4, Y4)”

so F1 is a continuous function of X and Y.

 

 

239

Corollary: If X = FO(Z, Y) is a function from one Banach

 

Space to another that satisfies a Lipschitz condition for

all 2 and Y, and there exists an inverse that satisfies

a Lipschitz condition in X for all fixed Y (the Lipschitz
constant is independent of Y), such that Z = F1(X, Y),

then Fl satisfies a Lipschitz condition in X and Y.

Proof: By the technique of Lemma B3, for each fixed X, F1
satisfies a Lipschitz condition in Y and the Lipschitz

constant is independent of X.

 

Lemma B4: Suppose a set of equations are given in the form

 

Z F (2 , Z )
0‘ = O 2 3 (1)
21 F1 (22, 23)_
2h
where F0 and F1 are continuous. Let Zh= I 1 ,
2
h.
i

h = (o, 1, 2, 3), 20, F0,

and 23 be p—tuples, and <Z2, 20> + <23, 21> be the

inner product that is strongly monotonic and satisfies a

and 22 be m-tuples, 21’ F1,

Lipschitz condition, (abbreviated - STRMLC). Then (1) can

be solved explicitly for 20 and 23 to give

2 F (2 , z )
° = 2 2 1 _ (2)

2 F3 (zz, 21)

where F2 and F3 are continuous, and (2) is (STRMLC).

240

Proof: If 22 is kept fixed, F1(22,

requirements of Theorem Bl so has a continuous inverse

Z3) satisfies the

defined everywhere for each fixed 22.
23 = P3 (22, 21).

Now F3 is continuous by Lemma B3. Let

F2 (22, 21) = F0 (22, F3 (22, 21)) and p2

is continuous since F0 and F3 are continuous. Since (1)

is (STRMLC), it follows that (2) is (STRMLC).

 

Lemma B5: If Q is a finite matrix transformation with

 

maximum column rank and a mapping F satisfies condition
(C1), then QTF Q (the composite function) satisfies condi-

tion (c1),
Egggf:
(X1 - x2, QT F m x1> - 4T F (q x2)> =
<QX1 ‘QX2,F(QX1)- F (Qx2)> 3
C1<Q X1. Q x2)||Q x1 - Q x2||2 e
C1(Q X1: Q X2) <QT Q(x1 - x2), x1 - X2> 3

a'C1CQ X1, Q X2)‘1X1 ‘ X2112 : C2(X1’ X2)llxl ' XZI'Z

241

where c2(xl, x2) satisfies the condition (C1). The Constant
a is positive and 'IQ XII 3 a H x H, since QTQ is posi-
tive definite by Lemma A5, and strongly monotonic by Theorem
A1 of [WI-l]. Also since Q is a matrix, it represents a
bounded linear transformation so IIQ x H : alllx H. There-
fore ‘lxll and I'Q x H are equivalent, [RO-l], so there
exists a c2(xl, x2) which satisfies the requirements of con-

dition (Cl).

 

Lemma B6: If F is monotonic,

 

<X1 - X2, F (X1+Y) - F (X2+Y)> : O
for all x1 and x2.
Proof: (X1 - x2, F (xl+y) .. F (X2+y)> =

<xl + y) - (x2+y), F(x1+y)'- F (x2+y)> :0.

 

Corollary: If F satisfies condition (Cl), then P(X'+y)

 

satisfies condition (Cl) for each y when considered as a

function of x.

 

Lemma B7: If X is a Banach Space, and F is defined on a

 

convex set DCZX, a necessary and sufficient condition that
F be monotone over D is that each point xED has a
Spherical neighborhood B(x) such that F is monotone over

D/l B(X).

242

Proof: [MI-2].

 

Corollary: If X is a Banach Space and .F is defined on a

 

convex set D(:.X, a necessary and Sufficient condition
that F be strongly monotonic (or satisfy condition Cl) is
that each point x e D has a Spherical neighborhood B(x)
such that F is strongly monotone (or satisfies condition

Cl) over D19 B(x).

M: (After MI—2.) For any distinct x1, x26 D, the
straight line Segment t x1 + (l-t) x2 (0 f t j l) is
totally bounded so is compact and contained in D; therefore
there is a finite covering by neighborhoods of the hypoth—
esis. Choose €> 0 smaller than the smallest radius such

that ||X1 ' X2 H is an integer n. Let
E

_ a E -
tm-“XITXZH (m-O,..., n),

and

ym 2 1:m Xl + (l-tm) X2
so that

Ym - Ym_1 = AY

for all m. For each m, ym and ym_1 lie in one of the

neighborhoods of the hypothesis, so

243

<ym-ym_l, P(ym) -F(ym_l)> = <Ay, F(ym) -F(ym_1)> _>_

...... [1|va ’ [hm-1H? HAY [[2

Sum over m, to obtain
<Ay, F(x1) -F(xo)> 3 c (max{”y0 yn'fi) nHAy"2

Also ' ' ‘
n(Ay) = x1 -x0.

Therefore

<5 w -F<xo>> : ...... Upon w-wnvnnk nZIlAvHZ
[uvou llvnll} >uxl «ouz
But c(max fi‘yo H ,..., ”ynll} ) = c(max{||x1” , “x0”})

since all ym are on a straight line and maximum norm is an

end point.

 

Definition: A mapping, F, from a Banach Space, X, into

 

another Banach Space Y, is said to have a directional

derivative é% F(xO +t X) (or Gateau differential) at xO if

lim = O

'F(xO-ttx) - P(xo) - <1 (P(xo-tt x)
t->O _

t dt

 

 

 

 

 

and dfit' P(xo+t x) is linear in x. Let K = {xéXz ”x”= I}.

If the convergence relationship above is satisfied uniformly

244

with reSpect to xEK, F is said to be Frechet differen-
tiable at x0.

Theorem B8: (This theorem is modeled after a theorem in

 

[MI-2].)
Let F: D->H where D is a convex subset of a Hilbert

Space H. If the directional derivative exists, then

<h, Ed? F(x + th)>

is equal to the value of

él—XZ’. F(xl) - P(x2)> , for h=x1-x2; x1, XZED,

and x = 5x14 (1-5) x2 (0<f< 1)

Proof:'-Consider any x1, x2 6 D.

Let
f(s) = <xl-x2, P(s xl+(l-S) x2)> ,

and f is differentiable for O 5's 5 1 since the direc-

tional derivative of F exists. Now
(x1 — x2, P(xl) -1=(x2)> = f(l) - f(O).
By the mean value theorem,

d
f(l) -f(0) ='- [3; <Xl -x2, P(s X1 +(1-S) x2)>]
_ s=§

lim <xl -x2, P(x +AS (xl-x2)) - F(x)>
AS ‘

 

245

where O<E<l and x=E X1+(1-E)X2

lim = x —x , F(x+As(x -x )) - F(x)
(Ss-—>O <: l 2 (S: 2 :>

lim F(x +As(x -x ))-F(x)
<x-x, A590 1AS 2 >

(h , f;- (F(x+t h)>

 

 

 

 

Lemma B9: If F is a mapping from a Euclidean Space into

itself and the Jacobian matrix XSEéél exists and is con-

tinuous then its uadratic form hTSU<X> h is e ual.
2 q SIX— q

to the value of <x1-x2, F(xl) -F(x2)> , where (h=xl-x2)

and (x = 6x1+(1-€) x2), for some 0 <E< 1.

Proof: The directional derivative of <h, F(x +t h)> is

lim <hy F(x+(As)(h))-F(x)>_ ,lim F(x+(As)(h))-F(x)
135-90 [35 _ [AS—90 [35

= hT 813:3) h (see [KA-1]).

This last equation follows Since F is continuously differ—

entiable.

 

Lemma BlO: Suppose that the function K(S, t, u), maps

 

Ed——>Em, where s and t are parameters, K(S, t, u) is

LebeSgue measurable with reSpect to s and t and twice

246

continuously differentiable with reSpect to u for a f.t : b,

a f s j b, -Cx3< u <<x=. Suppose also for these values of u,

S, t,

(a) “K32 (s, t, u)” :“J(s, t)||E

Em X Em X Em m X Em

for all u

(b) ”K(S, t, 0)” E 6L2 X 1.2
m

(c) “Kfi (s, t, 0)” 6 L2 X L2
Em X Em

where‘l H ,|l ll , and” II
Em X Em X Em Em X Em Em

denote the norms of Em X Em X Em, EIn X Em, and Em

reSpectively, and J(s, t) is an element of L2 m)(L2 m'
’

7
Consider the operation
b

y(S) = P(X(s)) = jf K(s, t, x(t)) dt (1)
a

Then the operation (1) maps the Space L2 m into itself, has
’

a Frechet differential P'(x0, x) at every point XOEL2 m’
2

and
b
P'CXO, x) = J/- K; (S, t, x0(t)) x (t) dt (2)
a 0
Proof: Since K(S, t, u) is continuous in u and measurable

in s and t, and Since u is an element in L2 m’ u is
’

measurable; so K is measurable. By Taylor's theorem:

 

247

K(S, t, x(t)) = K(S, t, O) + Kfi (s, t, O) x(t)
+ 1/2 XT(t)[X32 (s, t, 6 x(t)fl:x(t)
(O < e < 1)

Therefore:

bb 2 bb 2
if a[ HK(S,t,x(t))H E dt ds;§a[. af HK(5,t,O)H Em dt ds

m

*J f Iwame men/21 J Ix WM...
a 11 Em ‘ u Em

by Minkowski's inequality,

b b 2 b b 2
5 f .{HK(5vt:O)H C” <15 + f j HK'Cs,t,0)|| dt dS
a a Em a a u EmX Em ><
b b 2 b b 2
j fllxmll dt + 1/2 f f ”ML-in)“ dt ds X
a a Em 3. a Em X Em

b b 2 2 3
J afllx‘tUlEm C” < oo

by (a), (b), and (c) and by Holders inequality. Therefore,

P maps L into L . To show P is Frechet differen-
2,m 2,m

tiable and P‘ is given by (2):

 

248

 

 

 

 

7%;m ‘fb [K(s,t,x0+7X(t))-K(S,t,x0(t))-K'Xo(s,t,xo(t))x(ti]dt
O
a T L2,m
= 1im fbfll xT(t) fez (s,t,x0(t)+e7'x(t))]x(t) dt
7L9C) a. 2 u L2
111

2 b 2 , 2
5 lim J‘b bfll ”J(s,t)” dt ds ffl'x(t)“ dt
190 af. 2 13m XEm a Em

: lim .A 7'
7&0

ll
0

x(t)

 

 

 

 

L
2

by Taylor's theorem, (a), Holder's inequality, and A is a

positive constant. The limit is uniform forl‘x(t)|| = 1
L2 m
’

with reSpect to x(t). Therefore,

b
P'(x0, x) = sf K'X (s, t, x0(t)) x(t) dt.
0

 

Lemma B11: Suppose that the function K(s,t,u) is contin—

 

uously differentiable with respect to u for a f t f b,

a f 5.: b, -00< u <‘n , and that for these values of
s, t,HK(s,t,O)H e L X L and K' (S,t,x) <
2 2 x _
E E X E
m m m
|P(s,t)“ for all XEEm where H M denotes
Em X Em E

Euclidean norm on the Space of dimension m, and J is an

249

element of L2 m X L2 m

’ ’

and I. H the direct product
EmXEm

norm. Consider the operation:

y =P(x), y(s) 71b K(S,t,x(t)) dt. (1)

Then the operation (1) maps the Space L2 m into itself,

7

has a Gateau differential P'(x0, x) at every point

XoEL2,m’ and
b
P‘(xo, x) =~f K'X (s,t,x0(t)) x(t) dt. (2)
a 0

Proof: Observe that since K(S,t,u) is continuous,

K(S,t,x(t)) is measurable. By Taylor's theorem:

K(S,t,x(t)) = K(S,t,0)'tK'(S,t,6 x(t)) x(t)
u (O<<6 < 1)

Therefore:

b b 2 b b 2
L / “K(S,t,x(t))HE ds dt 5! I; “K(s’t’O)HE ds dt
a
m

m

+ fablbllfls’t)”: X E ds dt LbHX(t)“: dt < co
m m I“

Since ||K(s,t,O)H 6 L2 X L2, and by Holderls inequality.
E

I'll

Therefore P maps L2,m into L2,m

To Show P is differentiable and P‘ is given by (2):

By Taylor's theorem, and Holder's inequality,

 

250

2

 

 

 

E

HK(s,t,xO(t)+Tx(t))-K(s,t,x0(t)) — K); (s,t,x0(t))X(t)
O
m

,.
2 2
L, x 3,140".

2 2
j 4 ||J(s.t)|[E X 1:. “x(t)“E (o < e < 1)
m

<

|K§O(S,t,xo(t)+97k(t))-K;O(s,t,xo(t))

 

 

m

Since this latter function is integrable, by using the
Lebesgue convergence theorem, [RO-l], it is permissible

to pass to the limit under the integral Sign.

 

Therefore:
lim b 2
7‘90 [K(S,t ,xO+Tx(t))-K(S,t ,x0(t)) — K30(x,t ,xo(t))x(t)] dt

a ‘T L2m

 

 

2

X0

lim b
: 790 [E0 (5 ,1: ,x0(t)+07'x(t))-K)'(O(S,t ,X0(t))]>((t)] dt

L2m

 

IA

b b 2
if limllK)‘{0(s,t,xO(t)+eTx(t))x(t)-K,'(.O(S,t,xo(t))x(t)“E dt dS

a 'F90 m

= O, in view of the continuity of K;
0

Therefore:

b
P‘(x0(t), x(t)) = [Ki (S,t,xo(t)) x (t) dt
3, O