A TECHNIQUE FGR 1W WECEFECATEON
QF VAREAELH RELATENG 7’0
ELECTMC; E‘QWER NETWORKS

must: for ”to Degree cf pl). D.
WCEEGAN SHTE WHY '
Maurice rWoIIa
1966

 

Tunas;

 

W 7 ’1 It!

LIBRARY

Michigan State
University

f‘

This is to certify that the

thesis entitled

A TECHNIQUE FOR THE SPECIFICATION OF
VARIABLES RELATING TO ELECTRIC
POWER NETWORKS

presented In;

Maurice Wolla

has been accepted towards fulfillment
of the requirements for

Ph. D. Electrical Engineering

degree in

A»). \IM’RLVLO

Major professor

 

Date May 2: 1966

0-169

A TECHNIQUE FOR THE SPECIFICATION OF VARIABLES

RELATING TO ELECTRIC POWER NETWORKS

by

.
.'_ .
l‘ I , f

r‘ C‘ I
Maurice Wolla

AN ABSTRACT

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

DOC TOR OF PHILOSOPHY

Department of Electrical Engineering

1966

ABSTRACT

A TECHNIQUE FOR THE SPECIFICATION OF VARIABLES
RELATING TO ELECTRIC POWER NETWORKS

by Maurice Wolla

To effectively plan the current operation as well as the
future expansion of electric power systems requires a knowledge
of the operating characteristics of the existing and/or proposed
systems. Analysis of a class of power system studies utilized
in determining the electrical characteristics of a. power system
indicates that these studies are essentially problems in the
analysis of electric networks. These studies differ from
problems in "conventional" network analysis primarily in two
aspects: (1) the size and complexity of the network under
consideration, and (Z) the type of initial problem specifications.
The availability of digital computers has alleviated, but not
eliminated, difficulties associated with the size of the network.
Problems associated with the initial specification of variables
are more fundamental in nature and must be considered within
the framework of the network equations since it is mandatory
that inconsistencies are avoided. It is logical that a re-examination
of the variable specification aspect of these network studies should
originate at the level of the correlating graph and associated
primary system of equations since they constitute the foundation

for electric network theory.

MAUR ICE WOLLA

The w-domain graph correlates of the networks under
consideration are comprised of two general types of elements:
relation elements (F-elements) and no-relation elements (N-
elements); the latter type is characterized by a lack of any
fixed interrelation between the associated V and I variables
and furthermore neither of these variables is specified initially.
The resulting primary system of equations is homogeneous in
form and certainly consistent. Properties of subgraphs of F-
elements are subsequently utilized to define classifications of
the N-elements such that either, neither, or both of their
associated variables can be assigned arbitrary values with no
danger of introducing inconsistencies. The investigation clearly
indicates that a multiplicity of N-element classification patterns
exist for a given graph and provides the basis for new and more
general approaches to the analysis of electric networks—-
particularly those problems in which it is desired to maintain

prescribed operating conditions .

A TECHNIQUE FOR THE SPECIFICATION OF VARIABLES

RELATING TO ELECTRIC POWER NETWORKS
by

Mauri c e W ollla

A THESIS

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

DOC TOR OF PHILOSOPHY

Department of Electrical Engineering

1966

ACKNOWLEDGEMENTS

The author expresses appreciation to his thesis advisor,
Dr. Myril B. Reed, for his invaluable insight, advice, and
guidance throughout the author's graduate program and in the
preparation of this thesis, and to the members of his guidance
committee for their counsel during the entire program of
graduate study. In addition, the author gratefully acknowledges
his indebtedness to the Department of Electrical Engineering
and the Division of Engineering Research of Michigan State
University, the United States Steel Foundation, and the Ford
Foundation for their generous support during various phases of

this investigation and the author's graduate program

ii

TABLE OF CONTENTS

Page
ABSTRACT
ACKNOWLEDGEMENTS ii
Chapter 1. INTRODUCTION. . . . . . . . . . . . . . 1
1.1. Background........... ..... 1
1.2. Load or Power-Flow Studies. . . . . . . 5
1.3. Another Viewpoint . . . . . . . . . . . . 10
1. 4. A Variable Specification Problem in
Network Analysis . . . . . . . . . . . . 13
Chapter 2. SYSTEMS OF HOMOGENEOUS, LINEAR,
ALGEBRAIC, CONSTANT -COEFFICIENT
EQUATIONS-00000000000000coo. 15
2.1. Definitions and Fundamental Properties . 15
2. 2. The Complete Solution for a System of
HolacEquations 18
2. 3. The Complete Solution -- Another
VieWpOinteeoeoooeeeeeoooo 27
Z. 4. Interrelating the Two Viewpoints . . . . 32
Chapter 3. GENERAL PROPER TIES OF SYSTEMS
OF NETWORK EQUATIONS . . . . . . . . . . 36
3.1. IntrOdUCtlonoooo-o0000-00-00 36
3. 2. Characterization of the Graph Elements . 39
3.3. Circuit and Seg Equations . . . . . . . . 43
3.4. Primary Systems of Equations. . . . . . 48
3. 5. I-Explicit Primary Systems Associated
Wlth Power Networks 0 o o o o o o o o o 51
Chapter 4. MAXIMUM TERM RANK SUBMATRICES
OF AND CORRESPONDING F-ELEMENT
SUB RAPHS. O O C O O O I O O O O O O O O I O O 67
4.1. Introduction------ooco-ooooo 67
4.2. The Binet-Cauchy Formula. . . . . . . . 7O
4. 3. Nonsingular Submatrices of the
Complete Incidence-seg Matrix .
and Corresponding Subgraphs. . . . . . 73
4. 4. Maximum Term Rank Submatrices of
and Corresponding Subgraphs . . . 82

4. 5. F om Subgraphs to Maximum Term
Rank SmeatI‘lceS o o o o o o o o o o o o 93

iii

Chapter 5. COMPLETE SOLUTIONS FOR THE

PRIMARY SYSTEM OF EQUATIONS. .....

5.1. Subgraphs and Feasible Proper
Partitions . . C . C C C . O O O C O O C

5. 2. Particular Solutions and Specification

ofVariables..............

5. 3. Applications in the Analysis of Electric

Power Networks. . . . . . . . . .

5.4. Example. . .

Chapter 6. SUMMARY AND SUGGESTIONS FOR
FURTHER RESEARCH . . . . . . . . . .

6°1'SummarYoeoeoooooooooo
6. 2. Suggestions for Further Research .

BIBLIOGRAPHY

iv

Page

96

96
100
103
109

127

127
128

130

Figure
l. 2.1.

3.5.1.
4.4.1.
4.4.2.
5.3.1.
5.4.1.

5. 4. 2.
5. 4. 3.
5. 4. 4.
5. 4. 5.
5. 4. 6.
5. 4. 7.
5. 4. 8.
5. 4. 9.

5. 4.10.

5.4.11.

LIST OF FIGURES

General Representation of a (M+l)-node
Power Network Diagram. . . . . . . . . .

Graph Correlate of a Power Network . . . .

Vertex Partition

Allowable Subgraphs, m ‘-
Illustration of Zoning Technique . .

Interconnection Diagram for

Transmission Network . .

Key to Symbols . . . . . .

Nodal Diagram - Zone 1

Nodal Diagram - Zone 2 . . . .

Nodal Diagram - Zone 3 . . . .

Nodal Diagram - Zone 4 . . . .

Nodal Diagram - Zone 5 . . . .

F-Element Subgraph . . . . . . .......

Subgraphs which Satisfy the 6-Tree
Pair criteria 0 C C O . C O O O O O O O O O O

Subgraph which Satisfies the 7-tree
Pair Criteria .

F-Element Subgraph from Zone 4 .. . . . . .

Page

60
86
89
105

110
111
112
113
114
115
116
121

121

122
124

Chapter 1

INT RODUC TION

l. 1. Background

Planning the current Operation and future expansion
of a modern-day electric power system is a complex task
and one of ever-increasing importance. These systems
have grown from small, independent, local units at the turn
of the century to the vast, interconnected ”pools" Of today -
with still larger interconnections prOposed for the future1'4.
It soon became apparent that the ability to Operate the small
utilities successfully based primarily upon past experience
was not adequate to COpe with the problems associated with
these rapidly expanding systems. Advances in analysis and
control techniques coupled with the availability of digital and
analog computers have provided the system planners of today
with the Opportunity to study and plan the Operation of these
large-scale power systems. Considerable effort has been
directed toward the complete automation of system planning
and Operations-9.

The components of an electric power system can be

divided into three general categories: (1) the generating

2
stations, (2) the transmission and distribution network, and
(3) the loads. The basic Operating problem is to schedule the
generating stations so as to supply the total load demand,
plus losses within the transmission and distribution network,
in a manner consistent with dependable and economical
performance Of the power system. The planning phase is
necessary to insure that the power system has adequate
generating capacity and transmitting capability to meet the
constantly growing load demands.

The effective planning Of the current Operation and
future expansion Of a power system requires a knowledge of
the performance characteristics of the existing and/or prOposed
systems. The very nature of a power system precludes any
possibility of "laboratory testing" the actual system as is
commonly done with many types of physical systems. Thus
the system planners must devise an adequate model for the
system and subsequently determine the performance
characteristics of this model. The validity of the models used
in such system studies is tested by correlating the performance
characteristics determined from the model with those obtained
from observations made on the actual system.

The investigations of this paper relate to those phases

of power system studies which are primarily concerned with

the steady-state electrical characteristics of the power system.
These studies utilize a single-phase network representation of
the power system and in general they require a complete steady-
state solution for the network, 1. e. voltages, currents, real
and reactive powers, power factor, etc. at various points
within the network. Thus, these studies are essentially
problems in network analysis. However they differ from the
"conventional" problems in network analysis in a number of
respects. The network to be analyzed is considerably larger
and more complex than one might encounter in other areas.

In addition, it has generally been the case in the past that

the entire network must be considered as a unit for the
purposes of analysis. In contrast many communication and
control systems are often analyzed on a "piece-meal" basis
since signals are channeled along desired paths by the use

of uni-lateral devices and/or filtering. Thus as the size

of a power system increases due to expansion and inter-
connection the additional complexity itself presents a
formidable problem and it magnifies the need for a better
understanding of the fundamental concepts involved in the
analysis of the associated network. Perhaps the most
significant difference in this type of study is related to the

manner in which the initial problem specifications are given.

4
In power system studies of the type under consideration the
specifications are stated in terms of real and reactive
powers and voltage magnitudes, whereas the foundations of
network theory have been deveIOped with voltages and currents

104 1. Quantities

as fundamental or primary variables
such as real and reactive power are consequently considered
as derived or secondary variables since they are defined in
terms of the primary variables. Thus for any particular
network element the inter-relation (complex number form)

between. the voltage V, current I, real power P, and reactive

power Q, is given by the following relation:

P+jQ,=v1* (1.1.1)
or

P = Re {v1*} (1.1.2)

O = Im {v1*} (1.1.3)

Here one notes that on the one hand if V, I are known, then
P and Q are determined; on the other hand, however, if P, Q
are known, then neither V nor I is determined. This change
in the specification of variables causes considerable difficulty
in the attempt to determine a complete network solution. A
specific example of this type of problem is considered in a
later section.

Originally it was felt that the performance of a power

system could be best predicted through the use of a miniaturized

system commonly referred to as a network analyzer. How-
ever, in recent years the digital computer has replaced the
network analyzer as the primary tool for large-scale power
system studies. By its very nature the digital computer is
a more versatile and flexible device. Moreover, it is
capable of handling not only all Of the problems which can
be solved on the network analyzer, but an almost endless

variety of different problems as well.

1. 2. Load or Power-Flow Studies

The load or power-flow study exemplifies the general
type of problem under consideration in this investigation. A
study of this type requires a complete steady-state solution
for a single-phase network representation of the power
system. The network is made up of generator elements,
load elements, and elements corresponding to the inter-
connecting transmission and distribution network. The general
configuration of this type of network is given in Figure 1. 2. l
where the details Of the transmission and distribution network
are not shown. For simplicity it is also assumed that each
non-reference node is incident to exactly one generator or

load element.

th

gene rator or load
element

 

 
   

transmis sion
and distribution
nehnork

reference node
(ground or neutral bus)

Figure 1. 2. 1. General Representation of a (M+l)-node
Power Network Diagram.

The general nature Of a load or power-flow study
can be described as follows?" 12'14:
l. The complex number form of the node system

of equations for the network of Figure l. 2. 1

can be written as

M
1k = - 21 Yann , k=1,2,...,M (1.2.1)
11:
where

.9k

1k = IIkIeJ (1.2.2)
. j¢n

vn — anIe (1.2.3)
~0'

Ykn- IYknleJ 1‘“ (1.2.4)

7
In the usual load study, three types Of load and
generator specifications are considered:
A. For all load elements the real and reactive
power
P+jQ = VI’i‘ (1.2.5)
is specified.
B. For all generator elements except one, the
real power and voltage magnitude
P = Re{VI*} and |v| (1.2.6)
are specified.
C. For the remaining generator element, i. e.
the ”slack" generator, the phasor voltage
v = |v(eJ'¢ (1.2.7)
is specified.
The problem then, is to determine a set Of Vk

and I k=1, 2, . . . . M, such that the node system

k'
of equations, (1. 2. l), is satisfied subject to the
specifications,(l. 2. 5) through (1. 2. 7), for the
appropriate generator and load elements. Once
this has been done, then all voltages, currents,
real and reactive powers, etc. within the
transmission and distribution network can be

calculated and the complete solution will have

been determined.

8
Unfortunately the load and generator specifications
cannot be used directly to obtain a solution to the node system
of equations. Rather some form of iteration is used to
determine a solution. One such approach proceeds in the
following mannerlz'.
1. Initial estimates are made for the Vk'
2. The corresponding Ik’s are found from (1. 2. l),
3. The apprOpriate quantities, (1. 2. 5) through
(1. 2. 7) are calculated, compared to the
specified values, and the errors are determined,
4. Suitable correction relations are used to determine
new estimates for the Vk'
Steps 2 through 4 are repeated until (hOpefully) the errors
calculated in 3 are less than some prescribed precision
index.

2,13,14’ is to

Another commonly used technique
modify the node equations so as to obtain a system of
simultaneous nonlinear equations expressing the real and
reactive power for each generator and load element in
terms of the generator and load voltages and the node
admittance parameters of the transmission system. Since

for k=1,2,...,M:

Pk+ij = Vka* (1.2.8)

then, from (1.2.1)

M

. _ 9: *
Pk+JQk — - nzzlkakn' vn (1.2.9)
Also, using (1. 2. 2) through (1.2. 4)
Pk +ij = bzglw I I I IV Iej(¢k 44'6an
(1.2.10)
or
Pk = - 112—1|ka IYk nI IVnI cos(<I>k-¢n-trkn)
(1. 2.11)

)

Qk = 1%: IVkl lYknl IVnl sin (¢k;¢n-¢kn

The initial problem specifications can now be inserted
directly into any one Of these last three sets of nonlinear
"power equations, " (l. 2. 9), (1. 2.10), or (1. 2.11). Each
generator element and each load element has four
associated variables in this final formulation: . Pk, Qk,
I Vkl , (bk ; for each element two of these variables are
specified and the remaining two must be determined. Once
again an ‘iterative technique is used to determine a solution.

In the past the sheer size of the network and the
accompanying large number of equations to be solved has
been a major-Obstacle in load studies. However, the
introduction of the digital computer, as well as specialized
programsls' 16, has reduced considerably -- although

certainly not eliminated -- this problem. The major

difficulties in this type of study are those associated with

10
the iterative methods employed to determine a solution. The
key considerations are those relating to existence and
multiplicity Of solutions, convergence, rate of convergence,
the effect of initial estimates on covergence, etc. In many
respects the original problem has been transtrmed from
one in network analysis to one in numerical analysis in
order to accommodate the initial problem specifications in
the form given. Investigations into the problems assoéiated
with load studies, as well as other studies of this general
type, have been primarily concerned with improving the

iterative techniques used to Obtain a solutionlz' 13’ 17-20.

As a result Of these efforts computer programs, which are
capable of handling large-scale power systems, are avail-

able and in use today5'8’ 21.

l. 3. Another Viewpoint

Studies of the type considered in the preceding section
play a major role in predicting the current performance and
analyzing the future expansion of a power system. Thus'it
is essential that one be able to obtain an accurate numerical
solution for a particular study. Moreover, it would be of.
considerable benefit to a system planner if the problem

formulation and associated solution processes could also be

ll
utilized as a basis for a theoretical study of the system
characteristics. Unfortunately the present problem
formulation does not readily lend itself to a theoretical
study of system characteristics. Rather, the resulting
nonlinear equations tend to shift the emphasis to
characteristics of the iterative techniques which are used
to obtain a numerical solution for a particular study.

A re-examination of the basic structure of a load
study, for example, indicates that this study is essentially
a problem in the analysis of an electric network and that
the major source of difficulty is the form in which the
variables for certain elements are specified. In order to
avoid nonlinearities at the outset Of the problem it is
necessary to reconsider the form in which the variables
are specified. Since these are essentially problems in
network analysis, it would seem natural to return to the
basic structure of network theory and tO give consideration
to choosing a form for the variable specifications which is
more compatible with the existing theory. Perhaps the
most logical choice to consider would be that of the voltage
and current variables for an element. This choice can be
given initial support by noting that specifying the voltage

and current variables for a network element determines the

12
real and reactive power variables for that element - see
equations (1. l. 1) through (1. l. 3). Thus this choice would
be closely related to the original specifications. Further-
more, an extensive body of network theory already exists,
in which voltages and currents are considered as fundamental
or primary variables, and elements having either their
voltage or current variables specified have been considered
within this theory. Therefore, consideration of elements
having both voltage and current variables specified would
be a logical extension of this theory. Also of importance
is the fact that this approach provides an orderly and precise
formulation technique and thus is well-suited for use in
conjunction with the digital computer.

Within the area of network analysis little consideration
has been given to elements having both voltage and current
variables Specified. Undoubtedly this is due to the unlikelihood
of finding a correlating physical device in the laboratory.
However some consideration has been given to the possibility
of synthesizing ”pathological" elements of this type using
components such as ideal transformers, ideal gyrators, and

22' 23. IrreSpective of whether or not

negative resistances
such devices are physically realizable, the fact remains

that elements of this type can be useful in theoretical studies.

13
The investigations of this paper are concerned with extending
the class Of network elements to include those for which both
voltage and current variables are specified and then utilizing

these elements in the analysis of electric networks.

1. 4. A Variable Specification Problem in Network Analysis
Any investigation into allowable patterns Of element
variable specifications must be based upon a study Of the
apprOpriate systems of network equations since it is
imperative that inconsistencies be avoided. The primary

system of network equations“). 16

provides a logical
starting point for such a study. This system of equations
contains all of the information relative to the element
voltage and current variables and ultimately it is the
solution of this system of equations which is sought.
Chapter II is devoted to summarizing prOperties
of systems of homogeneous, linear, algebraic equations
with constant coefficients. These equations play a
fundamental role in this investigation -- in particular those
rank prOperties of the coefficient matrix which define
partitions of the variables into dependent and independent

sets. Following chapters return to a study of the electric

network via the correlating oriented linear graph and

14
associated systems of network equations. Interrelations
between subgraphs and the coefficient matrix in the network
equations are exploited to interpret rank properties of the
coefficient matrix in terms of interconnection patterns of
the linear graph and element parameters. In this manner
it is possible to determine conditions on the structure of
the linear graph and the element parameters such that the
graph may contain elements for which both the voltage and
current variables can be arbitrarily specified. In addition
one finds that still another type of element is required --
one for which neither the voltage nor the current variable
is specified and further, the voltage and current variables
are not interrrelated in any fixed manner, as is the case
for the graph elements correlating with resistors, inductors,
and capacitors. Finally, consideration is given to the
effect of extending the class of graph elements to include .
these new elements. A new approach is suggested for the
analysis of large-scale electric networks by utilizing

these elements in conjunction with zoning techniques.

Chapter 2
SYSTEMS OF HOMOGENEOUS, LINEAR, ALGEBRAIC,
CONSTANT-COEFFICIENT EQUATIONS

2. 1. DefinitiOns and Fundamental Properties

For reference purposes and to define terminology it
is convenient, at this point, to collect certain definitions and
fundamental prOperties of homogeneous, linear, algebraic
equations with constant coefficients. The proofs of the basic
theorems may be found in most texts on matrix theory or
linear algebraz‘l.2 , and are not repeated here.

In the interest of brevity, and at the same time to be
complete, the following abbreviation is us ed:

Definition 2. l. l. Holac Equations.

 

The abbreviation holac is us ed to denote

 

homogeneous, linear, algebraic, constant-coefficient.

Consider a system of m holac equations in n variables

n _
j§l aij xj = 0 , 1=1,2,...,m (2.1-1)

or, in matrix form

£1: 0 (2.1.2)

Definition 2. 1. 2. Rank of a System Of Holac Equations

 

Let the rank of coefficient matrix. a. in (2. 1. 2)

be r, then r is said to be the rank of the system (2. l. 2).

15

16

Definition 2. 1. 3. Characteristic Of a System Of

 

Holac Equations
Let the rank of the system (2. 1. 2) be r, then
the ordered triplet of integers, (m, n, r} is said to be the

characteristic of the system (2. 1. 2) and is written

wt: 0, {m, n, r,}

Definition 2. 1. 4. Linearly Dependent (Independent)

 

Equations
The holac equations, QIC= 0, are said to be
linearly dependent (independent) if and only if the rows of

the coefficient matrix, w, are linearly dependent (independent).

Definition 2. 1. 5. Equivalent Systems of Equations

 

Two systems of equations are said to be
equivalent systems of equations if every solution of either

system is also a solution of the other.

Consider a system of holac equations with characteristic

{m, n, r} i. e.

d1: 0, {m,n, 1'} (2.1.3)

Theorem 2. 1. l. A necessary and sufficient

 

condition that (2. 1. 3) have non-trivial solutions is that

r <no

l7

flieorem 2. 1i The equations of the system (2. l. 3)

are linearly dependent if and only if r < m.

Theorem 2. l. 3. Every system of holac equations
equivalent under elementary row Operations to the system

(2. l. 3) may be represented in the form

(Cd)}[=0 (2.1.4)

where a is a non-singular matrix of order m. Conversely,
if a is any non-singular matrix of order m, then (2.1. 4) is

equivalent to (2. l. 3) under elementary row Operations.

Theorem 2. l. 4. Any subset of r linearly
independent equations from (2. l. 3) forms an equivalent system

of equations.

It should be noted that the characteristic Of a system
Of holac equations is, in essence, a description of the
coefficient matrix, i. e. , a is of order mxn and has rank r.
Thus the previously stated properties of a system of holac
equations are in fact properties of the coefficient matrix--
the variables in the system play a rather minor role. In
general the variables have little, if any, significance with
regard to the mathematical properties of a system of equations;
they serve as little more than "labels" associated with the

columns of the coefficient matrix.

18

2. 2. The Complete Solution for a System of Holac Equations

Theorem 2. 1. 1 states a necessary and sufficient
condition on the coefficient matrix such that (2. l. 3) possesses
non-trivial solutions. Although the theorem itself gives no
indication of what these solutions might be, the proofs of
this theorem generally exhibit acomplete solution of (2. 1. 3).
It is a well-known prOperty of a system of holac equations
with characteristic {m, n, r } that the complete solution can
be obtained by solving the system of equations for some set
of r variables in terms of the remaining n-r variables. A
necessary and sufficient condition is that the r columns of
the coefficient matrix corresponding to the first set of
variables be linearly independent. Before stating this result
formally it is convenient to introduce the following notation
for a sub-matrix. Let a: [ a-ij] be a matrix Of order
mxn. The sub-matrix of order pxq formed from the array of

entries located at the intersections of rows i1, i2, . . . , ip

and columns jl’ jz, ..., Jq

,where lfiil<iz<...<i <m

and l _<_j1 < jz < < jqin is denoted by the symbol

a) i1, 12, ..., ip

jl' jZ, coo, j

l9

 

 

1. e. ,
aizil eaiziz aizjq
i ,i , . . . ,i
(2;. 1 2 P = . . . . (2.2.1)
J19J2,0"!‘Jq a. . a. . a. e
Ile ‘592 "' ngj

In some instances the set of row indices and the set of
column indices are each denoted by a single symbol, say R

and C respectively, then the above notation may be shortened

to 4%).

 

Theorem 2. 2. 1. Given a system of holac equations
(2§)Zs=0 {rn.n.r} (2.2.2)
Let le, sz, ., Xjr , (l: jl < jZ < < Jr: n),

be any subset of r variables from X. If and only if the

rank of a .1 ’ .2, ' ' ' ,m is r, then the complete solution
Jl’J2"°"Jr'

for the system (2. 2. 2) can be obtained by solving the equations

for X' , x- , . . . , x. in terms of the remaining n-r variables.
J1 J2 Jr

Consider the system of holac equations (2. 2. 2). By
Theorem 2. l. 4, any subset of r linearly independent equations
from (2. 2. 2) form an equivalent system of equations. Let any

such subset of equations be

62% 16’: (L {r,n,r} . (2.2.3)

20
If r = n, then £1 is non-singular and the trivial solution is
the only solution. If r < n, then by Theorem 2. l. l, the
system (2. 2. 3) possesses non-trivial solutions and thus the
original system (2. 2. 2) has non-trivial solutions. Since @1

has rank r, then there exists at least one set of column

1! 2: ooosr
_<_n such thata1( )

indicesl<'<’<...<' .. .
—J1 J2 JlsJZs oooer

Jr

has rank r. With no loss in generality suppose that

al (1’ 2’ ' ‘ ‘ ' r) has rank r. Then (2. 2. 3) can be written
9 9-0., 1'

in the form

Z1
[all Q12] 12 = 0 (2.2.4)

where all is rxr and non-singular. Solving for 2:1

l1: - QII’IQIZZ’Z . (2.2. 5)

Therefore a complete solution for (2. 2. 3) and hence (2. 2. 2) is

given by

_I

I'll idli-lalz 12 1 1411-4412-1
2'/:I—/Z2 = 12 = Z( [2

 

 

 

 

 

where ”is the unit matrix Of order n-r.

Since (2. 2. 6) represents a trivial extension of (2. 2. 5),

it is common to refer to either as representing a complete

21

solution for (2. 2. 2). A complete solution (2. 2. 6) of the
system (2. 2. 2) defines an infinity of particular solutions --
one particular solution of (2. 2. 2) for each distinct choice
for £2-

The relation (2. 2. 5) indicates that the r variables in
11 are dependent upon the n-r variables in 12. It is
common practice to designate the variables in [I as
dependent variables and those in 12 as independent variables.
Although this is a convenient description to use, it can at
times be misleading since it may lead one to view this
description as a prOperty of the variables rather than as a
prOperty of the coefficient matrix. With the apprOpriate
interpretation it does, however, provide a useful notation.
The following sequence of definitions relate to the subsequent
use of this terminology in conjunction with a system of holac

equations such as (2. 2. 2).

Definition 2. 2. 1. p-set of L

 

A subset of the variables in ,6: xj , xj ,
. 1 2
.,xjp.wh~erel:jl<j2<...<jpin. issaidtobe

a p-set of Z.

22

Definition 2. 2. 2. p-set of Dependent Variables,

 

Complete Set of Dependent Variables
A p—set of [K is said to be a p-set of dependent
' 1, 2, . . . , m
variables for (2.2.2) if and only if the rank of d. J. jz J.
19 s 0 ° - s p

is p. If p = r (the rank of the system), the designation of a

complete set of dependent variables for (2. 2. 2) is also used.

Definition 2. 2. 3. p-set of Independent Variables,

 

Complete Set of Independent Variables

A p-set of l is said to be a p-set of independent
variables for (2. 2. 2) if and only if its complement in 1
contains a complete set of dependent variables for (2. 2. 2. )
The complement in I of a complete set Of dependent variables
is also designated as the corresponding complete set of

independent variables for (2. 2. 2).

Thus each set of r linearly independent columns of the
coefficient matrix in (2. 2. 2) defines a partition of the n
variables in I into two mutually exclusive, all inclusive sets
-- an r-set of dependent variables and the corresponding
(n-r)-set of independent variables. Since the coefficient
matrix has rank r, then there exists at least one such
partition, although in general there may be more. Except

for the trivial case when ais the zero matrix (r = 0), a

23
complete set of dependent variables always contains at least
one variable; a complete set of independent variables is
empty if and only if n = r.
Consider

axl=0.{m.n.r}, O<rf_n. (2.2.7)

the n variables in 1 can be partitioned into an r-set and

n!

m distinct ways.

the corresponding (n-r)-set in (:1) 2
Any given r-set of I may or may not be acomplete set of

dependent variables for (2. 2. 7). This fact results in the

following designation:

Definition 2. 2. 4. Pr0per Partition

 

A partition of the n variables in (2. 2. 7) into

an r-set{X.i , X'i , . . . 'Xi } and the corresponding (n-r)-set
1 r

{ x- . x.. , . . . , x. } is said to be a prOper partition of
J1 32 Jn-r
h _ 'f 'f f l, 2, . . . , m
t e variables 1 and only 1 the rank 0 a ilviZ: . . . , ir

is r; i. e. , if and only if {xil’ X12, . . ., Xir} is a complete

set of dependent variables for (2. 2. 7).

Each proper partition of the variables in a given system
of holac equations can be used to determine a complete solution.
Since any one complete solution is sufficient to generate all of
the particular solutions for a system of equations, it is not

necessary to determine more than one prOper partition of the

24
variables. Nevertheless, the form of the complete solution
varies with the choice of prOper partition and for a particular
system of equations one choice may be more desirable than
another.

Given a system of holac equations, such as (2. 2. 7),
and one or more partitions of the variables into an r-set and
the corresponding (n-r)-set the question of whether or not
any particular partition is a prOper partition of the variables
can be answered by checking the rank of the apprOpriate
sub-matrix of the coefficient matrix. All of the possible
prOper partitions could be determined by locating all mxr
sub-matrices which have rank r. Unfortunately the number
of sub-matrices to be tested can become large for moderate
sized systems of equations. For example, to determine all
of the proper partitions of the variables fora system having
a characteristic of {10, 20, 10} requires checking the rank
of fig) = 184, 756 sub-matrices of order 10x10. This is a
formidable task and would: require considerable time, even
on a high-speed digital computer.

It is possible, however, to use the complete solution
derived from one proper partition of the variables to readily

Obtain information concerning other partitions. Consider

Q1: 0, {r,n,r} . (2.2.8)

25
l, 2, . . . , r
Suppose that det Q“, 2, . . . , r) # 0. then {x1, x2, . . . , Xr}
is a complete set of dependent variables for (2. 2. 8). Solving

for the r dependent variables in terms of the n-r independent

variables to obtain a complete solution:

 

 

 

 

 

 

 

 

I'- % I— "" r—

Xl All ... Arl al,r+l

x2 . A12 Ar2 a2,r+1

o = -1

' detw(1,2,...,r)

xr_I Alr Arr Lar, r+1

(2.2.9)
- - 1,2,...,r
where Aij is the cofactor of aij 1n detafi’ 2’ . . . , r), or

r- ” ‘r' r T ‘1
X1 , b11 b12 bl,n-r Xr+1
x2 b21 b22 ban-i- xr+2
' = ° (2.2.10)
x1 br1 br2 ' ° ' br, n-r xn

 

 

 

 

 

 

 

where
r
23 . .
b - k=1 ak9r+JAk1 (i=1, 2, 'r ) (2 Z 11)
ij — 1,2,...,r ’ j=1,2,...,n-r- ° '
'det¢(1,2,...,r)

The numerator of bij in (2. 2. 11) is the determinant of a

sub-matrix similar to that appearing in the denominator

26

except that column r+j of fl, has replaced column i. Thus

bij )9 0 (=0) if and only if the altered sub-matrix has rank

- r (<r). Therefore, the r-set {X1, x2, . . . ,xi_1.

xi+1, . . . , xr, xr+j } is a complete set of dependent variables

for (2. 2. 8) if and only if bij )9 0. This result can be

generalized to the following:

Theorem 2. 2. 2. Given

QIZ=O, {m,n,r}

Let {Xi-1w x12, . . . , Xir} be any complete set of dependent

variables for this system of equations, {le, ij. . . . . xjn-r }

be the correSponding complete set of independent variables,

and the corresponding complete solution be

 

 

 

I-xu DD11 ID12 b1,n-r I—le I
xi2 b21 b22 . . . b2, n-r sz
: (2.2.12)
x b b b x.
Iii-I r1 r2 r, n-r—I Jn—r-I

 

 

 

The partition of the variables which results from the inter-

change of Xis and xjt' (s=1,2,...,r; t=1,2,...,n-r), is

a prOper partition if and only if bSt )5 O.

27
Consequently, a single complete solution such as
(2. 2. 12) can be utilized to determine, by inspection, whether

or not an additional r(n-r) partitions are prOper partitions of

the variables of a system of holac equations. Although

Theorem 2. 2. 2 considers only a "singular" interchange of

variables, i. e. , one variable from each set, it can be used

in an iterative manner to test any partition. Once a prOper

interchange has been found then the complete solution
corresponding to the new prOper partition is readily
determined from the original complete solution by inter-
changing the two appr0priate columns (with due regard to

the signs of the entries) and then performing a sequence

of at most r elementary row operations. A second proper

interchange can be determined and the above process

repeated. In this manner it is possible to determine all

possible prOper partitions of the variables, if desired.

2. 3. The Complete Solution -- Another Viewpoint

In the discussion of Section 2. 2 certain rank prOperties

of the coefficient, matrix in a system of holac equations with

characteristic (m, n, r } are used to define a proper

partition of the variables. A complete solution is then

obtained by solving the system for the r dependent variables

in terms of the n-r independent variables. Other approaches

28
to the problem of determining a complete solution are
possible and the following discussion considers one such
approach which occurs frequently in certain types of
applied problems.

First, consider the sequence of steps used in
Section 2. 2 for determining a complete solution for the
following system of holac equations:

al=0, {m,n,r} (2.3.1)

1. An equivalent system of equations consisting

of any subset of r linearly independent
equations is extracted from (2. 3. 1):
alz=0, {r,n,r} . (2.3.2)
2. Let the first r column of 41 be linearly
independent, then 111 = 41%: g: : :) is
non-singular and a complete solution for (2. 3. 2)
and (2. 3. 1) is given by

Fill F'dll-l a

12

f=r.= a f2

— — — A

_ a!

 

 

 

 

(2. 3. 3)
Since the n-r variables in [2 can be arbitrarily chosen

let the following n-r sets of values be successively assigned

.. l2.

29

I_1— I'o _ I-o—I

 

 

 

 

 

 

(-03 _.° 1 ..‘J
and the corresponding particular solutions determined
from (2. 2. 3). Thus each of the n-r columns of

- £11-] Q12 is a particular solution of (2. 3. 1);

V

furthermore, these n-r solutions are linearly independent.
The complete solution as given in (2. 3. 3) may then be

interpreted as any linear combination of these n-r linearly

independent solutions. In general:

Theorem 2. 3. 1. If a system of holac equations

has characteristic { m, n, r} , then every solution may be

eXpressed as a linear combination of any n-r linearly

independent solutions.

Definition 2. 3. 1. Fundamental System of Solutions,

Fundamental Matrix of Solutions

Let Agrgz, ..., lid, be any n-r linearly

independent solutions of (2. 3. 1),then i 1. 4. . . . ,5”. }

is called a fundamental system of solutions for (2. 3. l) and

the n x (n-r) matrix g=[g,5, . . . ’4-r] determined by

30

these solutions is called a fundamental matrix of solutions.

Consequently, if gs any fundamental matrix of
solutions for the system 4%: 0, then the columns of
flare linearly independent and ev_er_y linear combination
of the columns of gis also a solution. From Theorem
2. 3. 1 it follows that a complete solution for (2. 3. 1) can

be written in the form

2: =5? (2.3.4)

where gis any fundamental matrix of solutions and % is
a column matrix consisting of n-r arbitrary entries.
Frequently the entries in% are considered as a new set
of variables and (2. 3. 4) is subsequently considered as defining
a transformation of variables. The use of the transformation
of variables (2. 3. 4) in conjunction with the system (2. 3. 1)
results in replacing the n variables in/Z by the n-r
variables infand also reduces (2. 3. l) to the matrix
identity 0:0.

The interrelationship between the coefficient matrix
in a system of holac equations and a fundamental matrix of
solutions for that system is a characteristic of a larger Class

Of matrices defined according to;

31

Definition 2. 3. 2. Apolar Pair 28

 

Let 4,ghave orders mxn and nxp ,
respectively. An ordered pair ((,g) of matrices is said

to be an apolar pair if and only if (1)45: 0, and (2) rank

of 4 plus rank of 1: 1f .

Using this concept the following result can be stated:

Theorem 2. 3. 2. Given 4% = 0, {m,n, r} and

 

let gbe a matrix of order nx(n-r). Then Zia a

fundamental matrix of solutions for the given system if

and only if (4,5) is an apolar pair.

The existence of a suitable gis assured by the following28:

'_1‘_heorem 2. 3. 3. Given any matrix 4 there

 

exists another matrix flsuch that (4,g) is an apolar pair.

For a given coefficient matrix 4 the process of
constructing a matrix g such that (4,5) is an apolar
pair closely parallels the process of the solving the system
of equations themselves and hence is not considered here.
However, for certain systems of holac equations, some of
which will be considered in later sections, it is possible

0 \

to determine the matrix gindependently of the matrix a,

32

2. 4. Interrelating the Two Viewpoints

Two approaches for obtaining a complete solution to
a system of holac equations were considered in Sections 2. 2
and 2. 3. Since both techniques produce a complete solution
for the same system of holac equations then they must be
interrelated.

Consider the system of holac equations (2. 3. 1) and
a complete solution given by (2. 3. 3). The particular
solution, )4), correSponding to any arbitrary choice, £20,
for 12 is, from (2. 3. 3):

F - r- _1 -I
Z10 ' Q11 Q12

lo : £20 : a ([20

_. ... L. .1

 

 

 

 

(2.4.1)

Also, let jbe any fundamental matrix of solutions for
(2. 3. 1). Since a complete solution is given by (2. 3. 4),

then there must be at least one set of valu08%o, such that

20 . 5% (2....)

01'

 

= (2.4.3)
1.. 5. 0

 

 

 

33

From (2. 4.1) and (2. 4. 3):

[20: 5% (2.4.4)

2
where i2 is a square matrix of order n-r. If 20 = 0,

then from (2. 4. 1) it follows that [0 = O, and (2. 4. 2) yields

g% = 0' consequently ya: 0 Since the columns of g

are linearly independent. Therefore:

2/ :0 implies %=0 (2.4.5)

20

On the other hand, from (2. 4. 4) with 20 = 0, one Obtains

a system of holac equations

(15% = 0, {n-r, n-r, p} (2. 4. 6)
where p is the rank of g.

2

Suppose p < n-r. Then the system (2. 4. 6) has an
infinity of non-trivial solutions for %, which contradicts
(2. 4. 5). Since p cannot exceed n-r, it follows that ,

p = n-r and thus 5 is non-singular. Hence for the same

particular solution, Z0,

if), = .124 X40 (2.4.7)

and there exists a one-to-one correspondence between 120

and f0.

34
The preceeding argument also establishes a relationship
between certain sub-matrices of Qand g.

Theorem 2. 4. 1. Given the system of holac equations

£16: 0, {m,n,r}

and any associated fundamental matrix of solutions, A? Let

 

i1, i2, . . . , ir and j1,j2, . . . , jn-r be sets of indices
complementary with respect to the set of column indices
1,2,...,n; i. e., il,i2,...,ir and j1,j2,...,jn_r taken
together form a complete set of indices 1, 2, . . . , n. Then

a (_1’ 2' ' ‘ ° ’ mo.) has rank r if and only ifflql’ jz’ ' ' ' ’ jn--I‘)

113i23000,1r ,2,...,n-r

has rank n-r.

Theorem 2. 4. 1 can be extended to the more general case of
an apolar pair since if (4,5) form an apolar pair, then g
of order nxp is rank equivalent to [31, O ] where 51 is of
order nx (n-r), has rank n-r, and by Theorem 2. 3. 2 is a
fundamental matrix of solutions for the system of holac
equations having 4 as a coefficient matrix. Thus:

Theorem 2. 4. 2. Let (1,5) be an apolar pair where

 

Q. is of order mxn and rank r; gis a matrix of order nxp.
Let i1, i2, . . . , ir and j1,j2, . . . , jn-r be sets of indices

complementary with respect to the column indices 1, 2, . . . , n.

35

Then:

i19i-2’ooe’1r

jl’j2""’jn-r'
has rank n-r.
1.2 .....p

1 ,2 ,...,
Q/ .m) has rank r if and only if

Chapter 3
GENERAL PROPERTIES OF SYSTEMS
OF NETWORK EQUATIONS

3. 1. Introduction

Network equations are formulated in a number of
different forms depending upon the type of solution that is
sought. Formulation in the time-domain is most general
and results in a system of ordinary differential and algebraic
equations. However, for a large class of network problems,
experience has shown that it is possible, and in fact, more
convenient, to by-pass time-domain formulation in favor of
frequency—domain or to -domain formulation. With this
approach the network equations are wholly algebraic in form
and involve complex numbers. The solutions, in terms of
complex numbers, are correlated with time-domain solutions
as well as observations on the physical systems. The complex
number form of the network equations, resulting from
formulation in the w-domain, is used as the basis for the
investigation of this paper. Thus prOperties of a system of
linear equations over the complex field play a:fundamental

role in this study.

36

37

It is possible to approach the general problem of
assigning specific values to variables within a system of
linear equations from two points of view. In one approach
the equations are considered in a homogeneous form and
rank prOperties of the coefficient matrix are used to define
a partition of the variables into a dependent set and an
independent set, i. e. , a prOper partition. Once a prOper
partition has been determined, then the variables within the
independent set are assigned arbitrary values with no danger
of introducing inconsistencies. As noted in the preceding
chapter, the variables themselves do not enter into the
partitioning process; in fact, it is possible to obtain a complete
solution from the coefficient matrix alone.

The other approach is, in some respects, the reverse
of the above process. As an initial step one can assign values
to a subset of the variables and subsequently examine a. system
of non-homogeneous equations to determine whether or not it
is consistent. If it is, then it is possible to determine a
complete solution; it not, then the Specification pattern is
altered and the process repeated. With this approach, the
number of variables assigned Specific values is, to a certain
extent, flexible; however, great care must be exercised in the

choice of both the variables which are specified and the specific

38

values which are assigned. The consistency conditions depend
not only upon prOperties of the coefficient matrix, but also upon
the Specific values assigned to the variables. Insofar as this
investigation is concerned, the first approach possesses a
definite advantage over the second in that the nature of the
process is such that it removes any doubt about consistency --
one is always assured of a solution. Because of this, it is
possible to make definite decisions with regard to the question
of which variables can be specified, based solely upon properties
of the coefficient matrix. These decisions are not influenced
or affected by any Specific set of values which might have been
assigned to a particular subset of the variables.

While systems of holac equations play a fundamental

role in electric networktheory, the theory Of graph329' 30

also occupies a positiOn of equal importance. The approach

to network theory based upon a study of the correlating oriented
linear graphlo’ 11’ 16’ 31'35 has done much to add insight and
precision into the formulation and solution of problems within
this area. The mapping of significant subgraphs into matrices,
which subsequently appear within the. coefficient matrices of

the network equations, allows one to interrelate prOperties of

these subgraphs with associated prOperties of the equations and

their solutions. In the present chapter consideration is given

39

to a fundamental system of network equations and some of
its general prOperties; the following chapter is devoted to
examining, in more detail, the relationships between certain
subgraphs and rank prOperties of the coefficient matrix.

Given a particular network for analysis, it is assumed
that a correlating oriented linear graph (herafter referred to
as a graph) has been established. In addition, two complex
variables are associated with each element of the graph- -a
voltage variable, V, and a current variable, I. An extensive
background of foundation material is assumedlo’ 11; the
terminology and notation used here is essentially that found
in these references.
3. 2. Characterization of the Graph Elements

In general the graph elements used in electric network
theory are classified as either relation elements (F-elements),
or no-relation elements (N-elements), depending upon the
presence or absence, respectively, of certain fixed mathe-
matical equations relating the primary variables, V and I,

16.

associated with each element. Formally

Definition 3. 2. 1. F-element

 

An F-element is a graph element characterized

by some fixed mathematical relation which relates V or I for

40

that element to V or I of the same element or any other
element of the graph. The mathematical relations are
characteristics of the elements themselves and are independent
of the manner in which the F-elements are imbedded in the
graph. The correSponding equations are called F-equations.

Commonly encountered examples of F-elements are
the graph element correlates of resistors, inductors, capacitors,

transformers, and the like.

Definition 3. 2. 2. N-element

 

An N-element is a graph element characterized
by: (1) either, neither, or both V and I for the element are
arbitrarily specified; and (2) V and I for that element are not
related in any fixed manner by an equation which is characteristic

Of the element iself.

N-elements are further classified into four different
types depending upon the pattern of element variable

Specifications. Thus:

Definition 3. 2. 3. Ne-element10

 

An N-element for which the element variable

V is arbitrarily Specified is designated as an Ne-element. The

 

specified variable V is designated by E, and the unspecified

41

variable I is determined by the graph incident to this Ne'

element.

Definition 3. 2. 4. Nh-elementlo

 

An N-element for which the element variable

I is arbitrarily specified is designated as Nh-element. The

 

specified variable I is designated by H, and the unspecified
variable V is determined by the graph incident to this

Nh' element.

Definition 3. 2. 5. Neh-element

 

An N-element for which both of the element

variables, V and I, are arbitrarily specified is designated as

 

an Neh-element. The specified variables V and I are

designated by E and H, respectively.

Definition 3. 2. 6. No-element

 

An N-element for which neither of the element

variables is arbitrarily specified is designated as an No-element.

 

Both of the element variables, V and I, are determined by the

graph 1nc1dent to this No-element.

Of these four types of N-elements, the Ne- and Nh-
elements are "familiar" since they are the graph element

correlates of regulated voltage and current sources, respectively.

42
Applications of Nah-elements were considered briefly in
Section 1. 3. In spite of its apparent lack of any distinguishing
characteristics (other than this very lack itself), the No-
element has considerable utility in network analysis. The
complete dependence of both of its variables upon the incident
graph makes the No-element useful for determining certain
characteristics of the incident graph per se. For example,
in the following pages these elements are used as "test
elements" to determine allowable locations, within a graph,
for the other types of N-elements.

The form in which the F equations appear is Often a
deciding factor in choosing a solution technique for the
network equations. For a set of nF F-elements, the
F-equations can appear in three basic form in the ‘wwdomain:

(1) the non-explicit F-equations:

n
F .
131 (flik 1k + fZik vk) = o, 1=1,Z,...,nF (3.2.1)

or, in matrix form

.212. + .9, 2.

where 31 and n42 are complex matrices of
order nF x nF, and F' 71“ are column matrices

of the I . and ’V

k reSpectively.

k,

43

(2) the I-explicit F-equations:

CQF-%420 (3.2.3)

where %F is a complex matrix of order annF
and is called the F-element admittance matrix;

(3) the V—explicit F-equations:

magi, .. 0 (3.2.4)

h . .
w ere f}? 18 a complex matrix of order “III-“XIII?

and is called the F-element impedance matrix.

Although the non-explicit form in (3. 2. 2) is most general,
the latter two (if they exist!) are generally more desirable
forms. No matter which of the three forms is considered,
the F-equations are a system of nF holac equations in ZnF
variables.
3. 3. Circuit and Seg Equations

The coefficient matrices for two fundamental systems
of network equations -- Kirchhoff’s voltage and current
equations -- are established by mapping certain classes of
subgraphs into matrices. As a result of mapping illcircuits
of a graph G into a matrix one obtains a complete circuit
matrix for G; the associated system of holac equations is

called a complete system of circuit equations for G:

44
E. 7 . (...,.

where 4 is a complete circuit matrix for G, and
7; is a column matrix of the element V's.
Mapping a3 segs of G into a matrix results in a complete
seg matrix for G; the associated system of holac equations
-- a generalization of Kirchhoff's current equations -- is
called a complete system of seg equations:
a e = O (3. 3.2)

where /a is a complete seg matrix for G, and

‘O/e is a column matrix of the element I's.

The rank of gis e-v+l, and that of ,Zis v-l,

for an e-element, v-vertex connected graph G. Thus,
from Theorem 2. 1. 4: any subset of e-v+l linearly
independent equations from a complete system of circuit
equations constitutes an equivalent system of equations;
_a_n_y subset of v-l linearly independent equations from a
complete system of seg equations constitutes an equivalent
system of equations. Hence it is neither necessary nor
desirable to consider a complete system of circuit or seg
equations in order to study their properties. Rather, one

need consider only a basis system of circuit equations:

—

(£7 = 0, {e-v+1, e, e-v+1} (3.3.3)
e

45

and, a basis system of seg equations:

.IL ‘= o, {v-l, e, v—l} (3.3.4)

e

where

Definition 3. 3. 1. Basis circuit matrix 5

 

Any (e~v+l)-row, e-column, (e-v+1)-rank
sub-matrix of a complete circuit matrix 5 is designated

as a basis circuit matrix ;

Definition 3. 3. 2. Basis seg matrix ,/

 

Any (v:-bl)-row, e-column, (v-1)-rank
sub-matrix of a complete seg matrix 1Z3. is designated as

a basis seg matrix

In Section 2. 2 rank prOperties of the coefficient
matrix in a system of holac equations are used to define a
prOper partition of the variables. This prOper partition is
subsequently used to determine a complete solution for the
system. The following Theorems provide a foundation on
which to interrelate certain interconnection patterns of the
elements'of a graph and certain rank prOperties of the
coefficient matrices which appear in basis systems- of'circuit
and seg equations:

Theorem 3. 3. 1. Let G3 be an m-element

 

subgraph of a connected graph G, 1 _<_ m 5 e-v+1; and

46
let 5: [ £1 4 ] be any basis circuit matrix for G,
where the columns of 1 correspond to the elements of
Gs‘ Then the columns of 4 are linearly independent if

and only if G8 contains no seg of G.

Theorem 3. 3. 2. A subgraph 63' of a connected

 

graph G, is a subgraph of some cotree if and only if G8

contains no seg of G.

Theorem 3. 3. 3. Let Gs be an m-element

 

subgraph of a connected graph G, 1 _<_ m 5 v-1; and let
J = [ 1 Z ] be any basis seg matrix for G, where
the columns of l corre8pond to the elements of Ga.

Then the columns of 1 are linearly independent if and

only if Gs contains no circuits.

Theorem 3. 3. 4. A subgraph GB, of a connected

 

graph G, is a subgraph of some tree of G if and only if

G8 contains no circuits.

Theorem 3. 3. 5. Let G be a connected graph.

 

If G1 and G2 are any two subgraphs of G such that:
i) GI and 02 have no elements in common, ii) G1 contains

no circuits, and iii) G2 contains no seg of G; then there

47
exists some tree T Of G such that Cl is a subgraph of T

and G2 is a subgraph of the complement, in G, of T.

G

Another approach to determining a complete solution
for a system of holac equations is considered in Section 2. 3.
The approach there is based upon the concept of a fundamental
matrix of solutions. Again the graph and certain of its
associated matrices provide an effective means to obtain a
fundamental matrix of solutions. The following theorem
provides the needed relationships:

Theorem 3. 3. 6. Let G be a connected graph, and
let g3 and [a be, respectively, a complete circuit matrix
and a complete seg matrix for G. If the columns of a and

)[a are ordered the same with reSpect to the elements of G,

1311': o and flaw/Q: 0. (3.3.5)
rank of g + rank )[a = (e-v+1)+(v-1)=

a

then

Since

(3.3. 6)

then, from definition 2.3.2, one concludes that (A, 5a )

and (1;, 1a) are apolar pairs. Furthermore, if /a
and/or ga are replaced by any basis seg matrix [and

any basis circuit matrix g respectively, then similar

48

conclusion follow. Thus: the transpose of any basis circuit
matrix K is a fundamental matrix of solutions for both a

transpose of any basis seg matrix is a fundamental matrix

complete system and any basis sst of seg equations; the
Of solutions for both a complete system and any basis system

of circuit equations. Therefore, from Theorem 2. 3. 2,

78.7. 771 , (3.3...

where is any basis seg matrix for G, and
?fl is an arbitrary (v-l)-rowed column matrix,

is a complete solution for (3. 3.1) and (3. 3. 3);

J... 5 2;, (3....

where g is any basis circuit matrix for G, and
71/2 is an arbitrary (e-v+l)-rowed column
matrix,
is a complete solution for (3. 3. 2) and (3. 3. 4).
3. 4. Primary Systems of Equations
Collectively, the circuit, seg, and F-equations
contain all the information relative to the primary variables,
V and 1, associated with the elements of a graph. Due to the

fundamental nature of these equations it is useful to have a

single designation for this collection of equations. Accordingly:

49
Definition 3. 4. 1. Primary system of equations
The combination of a_n_y basis system of seg
equations, a_ny basis system of circuit equations, and the
F-equations associated with a graph is designated as a

primary system of equations for the graph.

A primary system of equations is also classified as non-
explicit, I-explicit, or V-explicit depending upon the form
of the F-equations which appear within the system.
Ultimately, it is a solution for a primary system of
equations that is sought, although this does not imply that
one must solve these equations as they stand. It is more
often the case that certain secondary or derived systems
of equations, such as the mesh, branch, and node equations,
are utilized to Obtain numerical solutions since they generally
involve fewer Simultaneous equations to solve. However,
these secondary systems are established from the primary
system as a base.

Consider a non-explicit primary system of equations

for a connected graph G containing e elements, v vertices,

and n N-elements:

v-l ’- 0
j ,1 o 7 1Q ‘-
e-v+1 oN oF A g ~93 *3 0

e-nO flon-I VN

:11
0:1

 

 

 

 

(3. 4. 1)
where the N and F subscripts refer to the

N-elements and the F-elements, reSpectively.

If, at the outset, the N-elements are all No-elements, then
there are no Specified variables in (3. 4. 1), and this is a
system of 2e-n M equations in 2e variables. Suppose

that the rank of this system is also 2e-n, as is the case with
the w-domain graph correlates of many classes of electric
networks. If n > 0, then (3. 4. 1) possesses non-trivial
solutions and complete sets of independent variables consist
of some subsets of n of the element variables. Thus, the
number of variables which can be assigned arbitrary values
is equal to the number Of N-elements in the graph. Consider-
ation of the various combinations of the element variables
which could occur within a complete set of independent
variables indicates that if V, I, or V and I for an No-element

appear within this set then it is possible to replace the

51
No-element by an Ne" Nh" or Nah-element, respectively,
with no danger of introducing inconsistencies. In this sense
the No-element is used as a "test element" to check whether
or not certain patterns of N-elements can be present within
a given graph. Furthermore, the number of independent
variables is fixed at n regardless of the type of N-elements
present; thus, if both variables for one N-element occur in
an independnet set then both variables for some other N-
element must occur in the dependent set. In a similar
manner, if an F-element variable occurs in an independent
set then both variables for some N-element must occur
within the dependent set.
3. 5. I-Explicit Primary Systems Associated with Power
Networks

The present section is devoted to a consideration
of the w-domain graph correlates of electric power networks
of the type discussed in Sections 1. 1 and l. 2. These graphs
contain three general types of elements; namely: elements
correlating with generators, loads, and the components
which comprise the transmission and distribution network.
The elements associated with the generators are N-elements,
while those associated with the transmission and distribution

network are F-elements. Unfortunately the elements

52

corresponding to the loads cannot, in general, be categorized
in a clear-cut manner. One is inclined to consider these
elements as F-elements and characterize them, in the
to -domain, by a complex admittance or impedance. However,
more often than not, the load admittance or impedance is
either not known or, at best, only partially specified at the
outset of a problem. Consequently, these elements do not
readily fit into the F-element classification. The specifications
for the load elements are Often stated in terms of specified
variables such as real and reactive powers; thus they do not
immediately fit into the N-element classification, which
involves V and/or I specifications. However, based upon
the discussion of Section 1. 3, the N-element classification
seems more apprOpriate as a general rule. If the load
admittance is given, then, as shown next, it is possible to
use either classification -- F-element or N-element.

Consider an I-explicit primary system for a connected
graph Of e elements and v vertices. Let the graph contain
n No-elements, and further, suppose that the system of

equations has characteristic {Ze-n, 2e, 2e-n} :

 

 

 

 

n e-n n e-n
v-l ’- N 1F 0 0 C.) ”"iNT
e-v+l 0 0 N 6F 5Q}?
e-n o {(F o -%J flN
._ YE
L. .J
where .

complex entries.

This system of equations is presented in more do

a

(3.5.1)

F is a non-singular diagonal matrix with

tail below in

order to cqnsider the most general distribution of element

variables within the dependent and independent as

 

ts of a proper

 

 

 

partition:
”is?
Jim
”am
4N4
“I:1;I_l{l§Z_l§B_N£_F_l_£2_F3J_O_°_° _oI_o_ o- _0_ ran
...1._ EL 3 3 1°_ 1.0.: 344.41.; 44142.3 44.
nFlooooFé.looIooooil-Floo ’le
anooooIofionIooooIo-fizo 7N2
nF3 o o o 0 I0 0 74.3Io ~o 0 0:0 o—%.3 'flm
“ _. £14
VF;
frz
Lyra
where n1+nz+n3+n4 = n, and
nFli-an+r1F3 = -n

54

Rearranging the columns to indicate the desired distribution

of element variables

ream“
t" I/ '-

/N1XN2 0 2 Fl 0 I F21? "Q/NZ
O 0 N1 N3 0 Fl. 0 F3 71:11
0 o o o ”Flfi‘l: o 0 Wm

0000 OOIFZO F1

 

 

I
0 0 0 0 0 0 I 0 -%F3_I W171

» .

 

 

 

 

 

 

 

(3. 5. 3)

If and only if the coefficient matrix on the left-hand side of
(3. 5. 3) is non-singular, then the above partition of the variables

is a proper partition into a complete dependent set

55

{‘fl’Nl' ”nil . 7

N2 N3'

I 7.4

F1’ F1’ F2’%3'} (3'5”!)

and the corresponding complete independent set

{7N2 flN3’ 'Q/N4’ 7144’ 7F? £53} - (3.5.5)

Suppose that this is the case. Then it is necessary that

That is, the number of N-elements having both variables in
the dependent set is equal to the number of N-elements
having both variables in the independent set plus the number
of F-elements having one variable, either V or I, in the
independent set. It is noted that it is not possible to have
an F-element of the type considered here with both variables
in the independent set. However, Specification of either
variable for this type of F-element immediately determines
the other variable. Thus specifying one variable for an
,,F-element has the same effect as Specifying both variables
-- only one of which is arbitrarily chosen. In fact an
F-element having one variable in the independent set can
also be handled as an N-element with both variables in the
independent set -- provided that one assigns values to these
variables in a prescribed manner. Consider the coefficient

matrix on the left-hand Side of (3. 5. 3.):

 

 

 

 

= 07/722=
Jflz

L. (3. 5. 7)

Since, by hypothesis, the matrix ”A is non—singular then
M 11 and 2%22 are non-singular. In fact, due to the nature
of ”Z 22, one has thatflb is non-singular if and only if 773“
is non-Singular. Suppose that the last two sets of an + nF3
F-equations in (3. 5. 2) or (3. 5. 3) are deleted; however, the
corresponding graph elements are _n_cg deleted -- so the seg
and circuit matrices remain unaltered. The only change is
that these elements are now classified as N-elements. Thus

both the number of equations in the system and the rank of
the system are diminished by an + nF3, but the number of
variables remains unchanged. Consequently the number of
variables in a complete dependent (independent) set is
decreased (increased) by “F2 + nF3. If this altered system

of equations is now rearranged to include the nFZ variables

57

in oQ’FZ and the “F3 variables in 73:3 in a new set of
(potential) independent variables then one obtains (retaining

the notation of (3. 5. 2) ): 2
F-
N

 

 

 

 

 

 

 

(3. 5. 8)
The coefficient matrix on the left-hand Side of (3. 5. 8) is
precisely 27111 from (3. 5. 7) and thus has the prOper order
and rank if and only if the coefficient matrix fl on the

left-hand Side of (3. 5. 3) has the prOper order and rank.

58

Since, by hypothesis, 2h; has the proper order and rank then

~QNl' 7N1, ‘0‘sz N3’ ”aEl'E (3' 5° 9)

is a complete set of dependent variables for (3. 5. 8) and

{W79 797

N2” iN4’ 7N? F2’ F2’ bQFB’ 711B}
.. (3. 5. 10)
is the corresponding complete set of independent variables.
Although the systems of equations (3. 5. 2) and (3. 5. 8)
are neither ichntical nor equivalent systems of equations they
are closely related. Every solution of (3. 5. 2) is also a
solution of (3. 5. 8) but the converse is not true. However,

every solution of (3. 5. 8) for which the variables £172,

”Fa. “0/33. 753 are chosen so that
F2 7172 and ”an = %“3 71:3

(3. 5. 11)
is also a solution of (3. 5. 2).

The transition from (3. 5. 2) to (3. 5. 8) was accomplished
by deleting certain F-equations from the primary system of
equations; in effect changing the character of the elements
involved from F-elements to N-elements, but otherwise leaving
the graph unaltered. It is then possible to assign values to

the variables associated with these N-elements so as to maintain

59

any desired relationship between them. The admittance
coefficients for the ”transformed" F-elements no longer
appear within the system of equations; thus it is possible
to effectively handle Situations where these coefficients are
not completely known, or are variable, without introducing
unknown or changing quantitiesinto the coefficient matrix.

A distinctive feature of a "per-phase" representation
of a power network is the presence of a common node or
"ground bus". In particular, within the graph correlate, the
N- and F-elements corresponding to the generators and loads
are incident to a common vertex--the “reference" vertex.
With no loss in generality it is assumed that each non-
reference vertex of the graph is incident to exactly one N-
element and that all N-elements are also incident to the
reference vertex. For the case of a non-generator, non-
load vertex, or a load vertex for which the admittance
coefficient of the incident load element is known, then the
incident N-element can be specified as an Nh-element for
which H E 0, i.e., an open-circuit, or possibly an
Neh-element for which H "=' 0 and E is an arbitrarily
specified complex number. With this assumption the graphs
under consideration consist of the union of a v-vertex
connected graph of F-elements and a Lagrangian tree of

v-l N-elements---see figure 3. 5.1.

60

 

 

 
   

N-element v-vertex

connected
graph of
elements

 

 

reference vertex

Figure 3. 5.1. Graph Correlate of a Power Network.

In the formulation of a primary system Of equations
for the graph correlate of a network one has, in general, a
variety of basis seg matrices from which to chooselo; in
the following sections an incidence—seg matrix a, is used
exclusively. There is no loss in generality in this choice,
and one has an advantage in that a basis incidence-seg matrix
is formed with relative ease from data which is readily
available. Furthermore, this matrix is well-suited for
formation by a digital computer. 15’ 16

Consider an J-explicit primary system of equations
for the v-vertex graph Of Figure 3. 5. l --where n=v-l is the

number of N-elements, n is the number of F-elements, the

F
F-element admittance matrix y} is a complex diagonal
matrix, and the subscripts N, F refer to the N-element and

F -e1ement subgraphs re Spectively:

 

 

 

 

 

 

n nF n nF _ I—°'aNI
n I—VF 4F 0 0 'Q/F
nF 0 O 5N ”F fN = O, {2nF+n, 2(nF+n), 2nF+n} .
nF ° Z{E 0 '%E 7F
_. _I _J
- (3. 5.12)
From (3. 3. 5)
£504 N54.][1{N€F1'=.gN+flI. = 0 (3.5.13)
or
5N = - a? . (3.5.14)
Using the above relation to eliminate KN from (3. 5.12):
.. a s 5.91.7
5(N F o 0 .0.
F
0 0 ‘4‘F QF «N : 0, { 2nF+n, 2(nF+n), 2nF+n}
o ”F o - %. [F (3. 5.15)
b "' I. ..l

 

 

Upon premultiplying the coefficient matrix in (3. 5. l 5) by the following

non-singular matrix

0 7E ZCE
: 0 W F 0
LQN ‘ 4E yr ‘ 41?

(3.5.16)

 

 

one obtains, after a slight rearrangement Of the variables, the

following equivalent system of equations:

 

 

 

 

—- ' hI F
Q}. 0 0 ' FaF 7f}.
0 [(F 0 - F ‘QN = 0, {'ZnFi-n, 2(nF+n), 2nF+n} .
L0 0 {{N 4F fr 415‘ {N
" (3. 5.17)

Thus every solution of (3. 5.17) is a solution of (3. 5.12) and conversely.
Consider now the last set of n equations in (3. 5.17):
[”N 7’] 7N = 0, {n, 2n, n} (3.5.18)
N

where 7 = a]? % 41:. .

First, one notes that each solution of (3. 5.17) certainly determines
exactly one corresponding solution of (3. 5.18); second, each solution

of (3. 5.18) determines exactly one corresponding solution of (3. 5.17):
r— "I r-
I
£1“ 0 yr 4 F
y}; 0 fig" JN
j e . (3. 5.19)
N {(N 0 %\I

q

 

 

 

 

The systems of equations (3. 5.17) and (3. 5.18) are, in a sense,
equivalent systems of equations Since each solution of either
determines exactly one corresponding solution of the other. Since

one of the primary concerns in this investigation is to study the

63

properties of solutions of (3. 5. 12) in terms of the variables associated

with the N-elements, then it is appropriate to examine the solutions

of (3. 5.18).

In order to consider the most general partition of the

variables in (3. 5.18) it is necessary to subdivide the set of N-

elements into four subsets.

Since each N-element is incident to

exactly one non-reference vertex then the vertices of the graph are

subdivided into five subsets--the reference vertex alone and four

additional subsets, each corresponding to a distinct N-element

subset

incidence - 8 eg matrix:

I N1

0
a: o a...

 

I—

O

0

0

0

o 0 an"
0 0 an

”N3 0 an

 

i(N4 QF4

and the corresponding changes in (3. 5.18):

 

2 N2
n3 0 0 ”N3 0 %2
n4 0 O 0 Z(N4 %2

n3 n4

‘-

713 %4 N3

 

 

 

This necessitates a more detailed partitioning for the

(3. 5. 20)

= 0 (3.5.21)

where

fij

64

11
3"
ll M4":
p—I

and n

_>_o.

' o o
: 4F17F4Fj s 19.]:19 2: 3: 4

Rearranging (3. 5. 21) to indicate the most general partition of the

variables:

_n1 n2 n1 n3 __
n1 Z{Nl 0 %l %3
n2 0 Z(N2 $1 $3
n3 0 0 31 $3
114 0 O yin %3

 

 

E9 1‘

 

 

I13
I"
0

0

7..

 

—

0 OyN4 fi24

”2

i

2

H
,b.

19$ we”

72

w
,p

 

(3. 5. 22)

I—flN;
.9
7N

4

Z
N

2
,1;

 

 

fiLW

From Definition 2. 2. 4 it follows that the above partition is a proper

partition of the variables in (3. 5.18) if and only if

and

7..

7..

det 741 743 )5 0.

If this is the case, then a complete set of dependent variables

consists of the n variables:

M4 7..7..}

(3.5.23)

(3. 5. 24)

(3. 5. 25)

65

and the corresponding complete set of independent variables consists

of the n variables:

(firm, 9N4, 74m, /} . (3.5.26)

N4

At this point the characterization of the N-elements can be Specified
with no danger of introducing inconsistencies; i. e. , the graph can
be considered to contain nl No-elements, n2 Ne-elements,

n3 Nh-elements, and n4 Nah-elements.

AS noted earlier, the condition 111 = n4 requires that for
each Neh-element in the graph there must also be a distinct No-
element. Moreover, there is a stronger and more useful inter-
relation between the Neh-elements and the NO-elements in a

graph. Since yin (3. 5.18) is a symmetric matrix, then in (3. 5. 21):

_ t . . _
y”. _ %i 1,, _ l,2,3,4. (3.5.27)
731 733 9'13 %4
det - det (3. 5.28)

Hence,

74173 73 7

However the necessary and sufficient conditions for

{‘Q’Nz' “QN4’ 7N? Z94} (3' 5° 29)

to be a complete set of dependent variables for (3. 5. 21) are that
r11 = r14 and that the second determinant in (3. 5. 28) be non-zero.

Therefore, the set of variables in (3. 2. 25) is a complete set of

66

dependent variables for (3. 5. 21) if and only if the set of-variables
in (3. 5. 29) is also. Consequently, within a given allowable
classification of the N-elements of a graph into the No-, Ne-s
Nb" and Neh-classes, it is possible to interchange the NO-

and Neh-classifications.

It is worthwhile to note once again that although the preceding
discussion is concerned with the variables within a system of equations,
it is the cofficient matrix which actually contains the necessary
information and properties. In the next chapter these properties of
the coefficient matrix are "reflected" back into corresponding

properties of the graph.

Chapter 4
MAXIMUM TERM RANK SUBMATRICES OF AND
CORRESPONDING F-ELEMENT SUBGR HS

4. 1. Introduction

In the preceding chapters rank properties of the coefficient
matrix are used to define a prOper partition of the variables with-
in a system of holac equations. In Section 3. 5 this definition is
applied to a general partition of the variables within a system of
holac equations associated with the graph correlate of an

electric network:
I— _
[(6.1% VO/N =0. {n.Zn.n} (4.1.1)

7..

_. _I

y, : 4F %F 41; (4.1.2)

Of the resulting necessary and sufficient conditions for the

 

 

where

partition of (3. 5. 22) to be a proper partition, the first, (3. 5. 23),
insures that the appropriate submatrices have the proper orders,
while the second condition, (3. 5. 24), requires that a certain
minor from det7/ does not vanish. In a particular case this
minor can be evaluated and the corresponding partition checked.
Although this procedure provides a definite test, it gives little
insight into the reasons why a particular partition either passed

or failed the test.

67

68

Now , and hence all properties of yfare dependent solely
upon the subgraph of F-elements and the associated F-element
admittance coefficients; in (4. 1. 2), £1, can be construed as a
basis incidence-seg matrix of order (v-l) by nF for the
connected v-vertex, nF-element subgraph of F-elements, and
%F is 'the ' diagonal matrix of the F-element admittance
coefficients. The partitioning of the N-element variables, as in
(3. 5. 22), identifies the corresponding minor from day which
must be tested, but this is the extent of the effect of the N-elements
in the partitioning and testing process. The following sections of
this chapter are devoted to examining the composition of the
matrix ?’ in (4.1. 2) in order to establish interrelations between
subgraphs of F-elements and non-vanishing minors of det%.

In general the expansion of a minor involves a summation of
terms; thus a minor can vanish for one of two reasons-~each term
in the summation is zero, or the non-zero terms are such that
their summation is zero. If the minor does not vanish then the
summation of necessity contains non-vanishing terms. As shown
later, the presence or absence of non-vanishing terms in the
expansion of a minor of det7’ is directly related to the existence
or non-existence, respectively, of certain subgraphs of F-elements.
In anticipation of this result the following terminology is introduced:30

Definition 4. 1. 1. Term Rank of a Matrix

 

The term rank of a matrix is the order of the greatest

minor containing a non-vanishing term in its expansion.

69

The following theorems can be utilized to check the term rank of a

matrix:

Theorem 4.1. l. The expansion of the determinant of a
square matrix m of order r contains non-vanishing terms if and
only if any k rows of ”Z include non-vanishing entries mij from

at least k columns, k: 1, 2, ..., r.

Theorem 4.1. 2. The term rank of a square matrix of

 

order r is less than r if and only if there exists a zero Sub-

matrix of order m by n with m+n> r.

If a square matrix of order r has term rank r then its determinant
may be non-zero for some sets of values for the entries or possibly
for all sets of non-zero values for the entries. If the term rank

is less than r, then the determinant vanishes for all sets of values
for the entries.

Consider a minor of order r from det . In either case--
direct evaluation of the minor, or determination of the rank of the
corresponding submatrix using Theorem 4.1. l or Theorem 4. 1. 2
it is necessary to form the matrix % or at least the appropriate
submatrix, in order to test it; as the size and complexity of the graph
increases the formation of the matrix itself becomes a Significant
problem. Furthermore this process provides no explicit information
about the properties of the graph itself in relation to the partitioning

problem although the graph of F-elements determines the properties

«7

70

4. 2. The Binet-C auchy Formula

A generalization of the Binet-C auchy formula25 provides a
technique to establish an interrelation between subgraphs of

F-elements and non-vanishing minors of det :

Let fl,g be matrices of order r by n and n by q

respectively, and let 8 =Qi. Consider an arbitrary minor

of order m from dete:

2' m (4.2.1)

where

1<i <i<...<i <r

t—|

<
Then, if 1: m: n:

i,i.ooo,i i’i1999’i
dete l 2 m : Z detfl/ 1 2 m
l_<_k <1. <...<km:n kl,k ..,k

J1'32"'°'Jm l 2 27- m

,k ,...,k
deth1 2 m
j1,j2,...,Jm

i,i,...,i
detd<1 2 m) = 0. (4.2.3)

(4. 2. 2)

or, if m > n:

J13J2,000,Jm

71

Now, let

a0 = FfiF (4.2.4)

and consider any minor of order m, l _<_ m E v-l, from det?

where is given in (4.1. 2). Applying the Binet-Cauchey

formula, (4. 2. 2), twice:

igigooo,i 1,5. ,...,i
det .11.; . = 2 detZ 1.11:2 km
Jl’J2"'°’Jm lgkl<k2<m kmgn 1' 2...... m

F
k,k,eeo,k
det/O/ 1 2 m

jl’j2,...’jm

(4.2.5)
and
k,k,ooo,k k’k99993k
det 1 2 m = z det y}. l 2 m
- - ' < < < < <
J1'32"'°'Jm 1—’21 I2 lm—nF11'12"°"!m
f ,f ,...,!
det a} 1 2 m
jl,j2,...,jm 0
(4.2.6)

Since 7’17. is a nonsingular, diagonal matrix then the only non-
vanishing minors are principal minors; thus the summation in

(4. 2. 6) contains at most one non-vanishing term--corresponding

tothecasewhenl =k,1 =k,...,1 =k . Further
I l 2 2 m m
k . k
1' 2'” ' m
det = Y Y ... Y

l’ 2’”" m

(4. 2. 7)

72

and
k,k,ooo,k j’j99999j
detd' 1 2 m = detd 1 2 In
F . . . F k
Jl’J2"°"Jm kl’k2""' m '
(4.2.8)
Combining the last four relations:
i,i,...,i i,i,...,i
det l 2 m : Z Ykl Ykz o o . Ykm det 4F 1 2 m
J1,J2,...,Jm l<k<k<...<k <n k1,k2,...,km
—l 2 m— F
j’j,eoogj
detaF 1 2 m
k1k2,...,km .
(4.2.9)

Examination of (4. 2. 9) indicates that the Summation contains

a total of

F " nFl
: m' (n _ m)‘ (4. 2.10)
m ° F '

 

terms, and that each term is composed of two types of factors. The
first factor is a product of n of the F-element admittance coefficients;
for the type of F-elements considered, each admittance coefficient

is finite and non-zero, hence this factor is always finite and non-zero.
In addition, this factor involves a distinct set of m F-elements,

i. e. , no two terms in the summation involve the same set of m
F-elements. It is also noted that this factor depends solely upon

the admittance coefficients and is independent of the manner in which

the F-elements are interconnected. The second factor in each term

73

is the product of two minors from the incidence-seg matrix and
has a value of +1, -1, or zero since the value of any minor of an
incidence-seg matrix is +1, -31, or 0. 11 This factor, in contrast
with the first type, depends solely upon the manner in which the
F-elements are interconnected and is independent of the F-element
admittance coefficients. Thus connection patterns of F-elements
determine whether or not the summation in (4. 2. 9) contains non-l

vanishing terms:

Theorem 4. 2.1. The m by m submatrix, lfimfiv-l,

 

11,12,eeo,1m
. . . (4. 2.11)
Jl,J2,...,Jm

in (4. 2. 9) has term rank m if and only if there exists at least one

m-element subgraph of F-elements such that

i,i,...,i j.j.....j
d1? 1 2 m and 4F l 2 m
k1,k2,...,km k1,k2,...,km

(4. 2.12)

are both nonsingular.
4. 3. Nonsingular Submatrices of the Complete Incidence-seg
Matrix and Corresponding Subgraphs
Consider a graph G0 which is connected, i. e. a part, and

consists of e elements and v0 vertices. An inc1dence-seg
0

matrix for G is formed by mapping the element-vertex incidence
0

pattern of the graph into a matrix. The complete incidence-seg

74

matrix fla for G is a matrix of order v by e where the
o o o
typical entry aij is defined as follows:10

+1, if element e. is incident to vertex vi and oriented
away from his vertex;

-1, if element e. is incident to vertex v. and oriented
a.. . 1
13 toward this i/ertex;

0, if element ej is not incident to vertex vi.

Under this mapping each row of da corresponds to a distinct
vertex of Go and each column of 4a corresponds to a distinct
element of Go' Since the vertex and element numbers are
arbitrary it is assumed that the vertex and element numbers

correspond to the row and column indices, respectively of fla'

Let:

Vo denote the set of all vertices of Go’
0 denote the set of all elements of Go,

V denote a proper subset of V consisting of
m . . . o

m dlstlnct vertices,

E denote a proper subset of E consisting of

m o

m distinct elements, and

V(E ) denote the set of vertices incident to the
m elements in Em.

Corresponding to any m by m submatrix of da is a set of m

distinct vertices and a set of no distinct elements of GO. This

correspondence is denoted by the following notation:

' a

' i,...,i V
4.. 11'2 ... - d m (4.3.1)

jl’j2"°"jm' m

75
where

Vm : {vil’ v12"°°’vim}

Em = {ejl’ ej2,...,ejm} .

Also associated with this submatrix is a second vertex set; namely,
V(Em).

The following two theorems characterize sets of linearly

independent rows and columns of 4a:

Theorem 4. 3.1. If Vm is any subset of m distinct

vertices of Go’ lSmEVO-l, then the mby eo submatrix

v
Q < 9) (4.3.2)
a E0

, Theorem 4. 3. 2.

has rank m.

Let Em be any m-element subgraph

of Go’ limfivo-l. The V0 bym submatrix

V
0
Q < > (4.3.3)
3‘ E
m

has rank m if and only if Em contains no circuits.

Consider an arbitrary m by m submatrix of 4a, limfivo-l:

. . 0 V
11,12,00031m m
a 2 a (4.3.4)
a . . . a E
Jl’JZ’...,Jm m

76

where

Vrn = {vil'vi2"'°’vim} (4.3.5)

E = {e.l,e } . (4.3.6)

m j j2"'°’ejm

Theorems 4. 3.1 and 4. 3. 2 provide necessary conditions for the
submatrix (4. 3. 4) to be nonsingular. Theorem 4. 3. l is certainly
satisfied; if the subgraph Em contains no circuits then the Sub-
matrix, (4.3.3), of order vo bym has rank m. Therefore
there exists at least one mxm submatrix of (4. 3. 3) which is
nonsingular. However this nonsingular submatrix may or may not
be the one in (4. 3. 4). The following theorem gives necessary and
sufficient conditions, in terms of the subgraph Em and the vertex

set Vm’ such that the submatrix (4. 3. 4) is nonsingular:

Theorem 4. 3. 3. If and only if: (1) Em contains no

 

circuits, and (2) each part of Ern contains exactly one vertex
v*€ V(Em) such v*)é Vm, then the submatrix (4. 3. 4) is non-

singular.

Proof: Let Em and Vm be given, where the subgraph
Em consists of m elements, p parts, and the vertex set V(Em)
contains x vertices. Let the i-th part of Em contain mi elements

and x1 vertices, where

m1+m2+...+mp : In (4.3.7)

xl-t-x2+...+xp = x (4.3.8)

77

since a part and its complement have no elements or no vertices
in common. (a) Sufficient. Let Em contain no circuits and each
part of Em contain exactly one vertex v* 6 V(Em) such that

v* f Vm' Because Em contains no circuits, then each part of

Em contains no circuits and:

mi-Xi+l : 0 i=l,zgooo,p (40309)
01'

xi = mi+l i=1,2,...,p. (4.3.10)

Each part of Em contains exactly one vertex v* f Vm' thus each
part contains exactly mi vertices from Vm. From (4. 3. 7) it
follows that Vm is a proper subset of V(Em). Construct an
incidence-seg matrix 4i of order mi by mi for the i-th part

of Em; the omitted row corresponding to that vertex of part i which
is not a member of Vm. Since each part is a tree then the rank of
ai is mi. By proper ordering of the elements and vertices, an
incidence-seg matrix, a *, for Em can be written as a block

diagonal matrix:

. (4.3.11)

 

 

*
Hence, a is an mxm matrix and has rank m. The no rows of

* a5:
a correspond to the vertices in Vm, the m columns of a

78

correspond to the m-elements in Em, and

aa<:m) = 744*76 (4.3.12)

where W , )6 are conformable permutation matrices and thus
nonsingular. Therefore, 4a (Em) is nonsingular. (b) Necessary.
V m
Let aa (Em ) be nonsingular. Since a nonsingular matrix contains
m

no zero rows or columns, then every vertex in Vm is incident to at
least one element of Em and each element of Em is incident to
at least one vertex from V . Thus V is a subset of V(E ).

m m m
Further, the columns of this submatrix are linearly independent,

thus Em contains no circuits and
x = m+p. (4.3.13)

Therefore Vm is a proper subset of V(Em), and V(Em) must
contain exactly p distinct vertices which are not members of Vm.

There exist permutation matrices fl and 7&4 such that

- _

O. 0

“413741404 33

L P.

 

 

(4. 3. 14)
where the mi columns of “1 correspond to the elements of Em
in part i and the rows of 41 correspond to the vertices of Vm

in part i -- note that at this time the number of rows in 41 is not

79

known to be mi. Suppose that all of the mi+l vertices of part i
are members of Vm' Then 41 is a complete incidence-seg
matrix for part i and thus the rows of ai are linearly dependent.
Therefore the rows of da (Vm are linearly dependent and the
Em V
matrix is singular. As aa (ELI-11) is nonsingular then
gag}; part of Em must contain at least one vertex which is not a
member of Vm. But V(Em) contains exactly p vertices which
are not members of Vm; since each of the p parts must contain
at least one, then each part of Em must contain exactly one
vertex which is not a member of Vm' q. 8. d.

Subgraphs which contain no circuits, such as Em in
Theorem 4. 3. 3, are closely related to another class of subgraphs
which are defined as follows:32

Definition 4. 3. l. k-tree

A k-tree, Tk’ of a vo-vertex part Go is a subgraph
of Go which contains k parts, all v0 vertices of Go , and no

circuits. (Note: in this definition one must allow the possibility

that a part may consist of an isolated vertex.)

Theorem 4. 3. 4. 32 Let Go be a part with vo vertices,

 

then:
(1) A k-tree of (30 contains vo-k elements, 15k: v0;
(2) A subgraph of Go which contains vo vertices,

vO-k elements, and no circuits is a k-tree of Go.

Thus, if V(Em) = Vo then Em is a (vo-m)-tree of Go; if V(Em)

80

is a proper subset of V0, then Em differs from a (vo-m)-tree
by a set of isolated vertices--namely those vertices of V0 which

are not contained in V(Em).

Definition 4. 3. 2. Basis for a k-tree

 

The subgraph of a k-tree T consisting of the vo-k

k

elements is designated as the basis for that k-tree and denoted by

T Ev _k).

k( 0

Theorem 4. 3. 5. Let G() be a part containing vo vertices

 

then any subgraph of Go containing vo-k elements, 1_<_ k: v() ,

and no circuits is the basis for some k-tree of GO.

In order to characterize the subgraphs of Theorem 4.3. 3, which
correspond to nonsingular submatrices of the complete incidence-

seg matrix, one additional concept is required:

Definition 4. 3. 3. k-tree pair
Let G be a part containing v vertices, and V
0 O ”VG-k
and E be any subset of v -k distinct vertices and v -k
vo-k o .. 0
distinct elements of Go’ respectively. {Vvo-k’ Eve-k} is said
to be a k-tree pair if and only if Evo-k is the basis for some

k-tree Tk’ and each part of T (EV _k) contains exactly one
o

k

vertex v* such that v* is not a member of VV -k .
0

Therefore Theorem 4. 3. 3 can be restated as follows:

81

Theorem 4. 3. 6.

&a (Vin) is nonsingular if and only if { V , E }
E m m
m
is a (vo-m)-tree pair.

For a given eo -element, vo-vertex part Go it is of
interest to determine the number of (vo-m)-tree pairs that exist
for either a fixed set of m vertices of Go or a fixed set of m

elements of 60' where 1 _<_ m: vo-l .

Theorem 4. 3. 7. Let Vm be any fixed set of m distinct
vertices of Go’ 1 j m: vo-l, and let nE be the number of
distinct sets of m elements of GO, Emi , for which {Vm, Emi}

is a (vo-m)-tree pair, then

v E
nE: det{ da( m> fi;< °> }. (4.3.15)
E0 vm

Proof: Using the Binet-C auchy formula:
V V Em-
m I
det { a m Q' 0 } = Z? detd detd 1
a a V E a E a v
o m mi mi m

(4. 3.16)

V
= z {det4a< m) }‘2

(4. 3.17)

where Em ranges over all distinct m-element combinations of the

1

82

e0 elements of Go' The determinant in (4. 3.17) has the value

+1, or -1, if. and only if { Vm, Emi} 18 a (vo-m)-tree pair and

hence the result follows. The following theorem is proved in a

similar manner:

Theorem 4. 3. 8. Let Em be any fixed set of m elements

 

of Go, 1 S m : vo-l, and let nV be the number of distinct sets

of m distinct vertices of Go’ Vmi, for which {Vmi' Em} is

a (vo-m)-tree pair, then

E v
nvzdet{d’;< m) aa( °> } . (4.3.18)
vo E

m

As a direct consequence of theorem 4. 3. 2:

Corollar_y 4. 3. 9. The number nV in Theorem 4. 3. 8

 

if zero if and only if Em contains a circuit.

4. 4. Maximum Term Rank Submatrices of yand
Corresponding Subgraphs

Necessary and sufficient conditions for an arbitrary m by m
submatrix of 7’ to have term rank m are stated in Theorem 4. 2.1
in terms of nonsingular submatrices of an incidence-seg matrix.
If this theorem is combined with Theorem 4. 3. 6 these conditions
can be stated in terms of properties of subgraphs.

Let Go be a part containing nF F-elements and v0 vertices;

consider an arbitrary m by m submatrix,, 1 _<_ m : vo-l, from

the matrix yin (4.1. 2):

83

i1, 12, o o o 3 1m
. . . (4. 4.1)
J1, J2, o o o ,J
The relation (4.2. 9) establishes a correspondence between the row
and column indices in (4. 4.1) and two sets of row indices from the

incidence-seg matrix; thus one can associate two sets of m distinct

vertices from Go with the submatrix in (4. 4.1):

Vmi : {Vil’ vi2’ "" vim} (4°4°2)
and
ij = {vjl, vjz, vjm} . (4.4.3)
Theorem 4. 4.1. The mbym submatrix

 

v
< mi) (4. 4. 4)
Vm.
J

in (4. 4. 1) has term rank m if and only if there exists at least one

m-element subgraph E of G such that {V E } and
m o m

m.’
1

{Vm_.: Em} are both (vO-m)-tree pairs for CO.

V
Corollary 4. 4. 2. The m by m submatrix V(Vmi) has
m.

V
term rank m if and only if 7(ij has term rank m. J
mi

Although Theorem 4. 4. 1 relates term rank to properties
of subgraphs it is instructive to examine the stated conditions in
more detail in order to extract additional information characterizing

the type of subgraph Em meeting these requirements.

84

The basis incidence-seg matrix a]? in (4.1. 2) is derived
from the complete incidence-seg matrix 4a by deleting the row
corresponding to the reference vertex r0; thus r0 is never

contained in either Vm or Vm, . Therefore, for a given Vm

i J i
and ij , the vertex set of G0:
VO = {v1. v2. .... VVo'l' r0} . (4.4.5)

is partitioned into these proper subsets: an Vm- , and the subset
1 J
consisting of all vertices of V0 which are not contained in either

V or V The latter subset always contains at least one

mo'

mi J

member--the reference vertex r0. Although Vm. contains m
distinct vertices, as does ij , it is possible for the composition
of these two sets to vary from that of identical sets to that of disjoint
sets.

If the vertex sets VIni and Vm. are identical, then it is
necessary and sufficient that there existls an m—element subgraph
Em such that {Vmi’ Em} is a (vo-m)-tree pair: Em must
contain no circuits and each part of Em must contain exactly one

vertex which is not contained in V For a given graph Go’ and

m.°
1

a given vertex set V these conditions can be applied and it can

m-'

1
be determined whether or not one or more allowable subgraphs
exist. Alternately, one could utilize (4. 3.15) to determine nE,

the number of m-element subgraphs such that { VmJ

E } isa
v 1 m
(vb-m)-tree pair. Hence the term rank of 7(Vmi) is m if
m.
1

and only if nE )4 0.

85

If the vertex sets Vm and Vm~ are not identical, then
i J
Go must be searched for allowable m-element subgraphs such that

both {Vmi, Em} and {V Em} are (vo-m)-tree pairs.

m.'
J

Unfortunately no formula has been found from which to calculate
the number of distinct m-element subgraphs that satisfy both of
these conditions. A determinant:

det{ 4a (V311) a; (E0) }, (4.4.6)
ij

E
0

similar to that used in (4. 3. 15), can be formed and evaluated.
Application of the Binet-Cauchy formula indicates that the non-zero
terms in the expansion, +1 or -1, do correspond to allowable sub-
graphs; however, the heterogeneous pattern of signs which may occur
allow one to conclude in general that if there are t non-vanishing
terms in the expansion, then the value of the determinant might
range from +t to -t and including zero. If the value of the
determinant in (4. 4. 6) is n, then there are at least I 11' distinct
m-element subgraphs Emk such that { Vmi, Emk} and

{Vm.' Em } are both (vO-m)-tree pairs. Therefore nfiO 13

J V
sufficient for the term rank of V(Vmi) to be m, but it is not
m-
J

necessary.

Consider the type of subgraph EIn for which both { Vmi’ Em}
and { ij, Em} are (vO-m)-tree pairs when Vmi and ij
are not identical. In addition to containing no circuits, each part of

E must contain exactly one vertex which is not contained in Vm.
1

. If Vm. and

and exactly one vertex which is not contained in ij
- 1

86

Vm. are disjoint then, since each part of Em contains at least
two vertices, each part must contain exactly two vertices--one from

Vmi and one from ij. The m-element subgraph Em must

consist of m parts; each part is a single element incident to one
vertex from V and one vertex from Vm_. Thus, if Vm- and

m-
1 J 1

ij are disjoint, the m-element, m-part subgraph can be viewed

as matching the vertices of Vmi onto the vertices of ij in a
one-to-one manner? Therefore, when Vm. and Vm. are disjoint,
1
(3:1) has term rank m if and only if at least one such
matching] subgraph exists in Go'
Suppose the vertex sets Vmi and Vm. are neither identical
nor disjoint. Then the vertex set V0 in (4.4]. 5) is partitioned into

four mutually exclusive, all inclusive, non-empty subsets: SI,

82' S3, and S4--see Figure 4. 4. 1.

 

 

 

 

 

 

 

 

 

 

 

V
V ~ 0 '
. r0
S4 S3 S1 S2
m V _
Vm‘

Figure 4. 4.1. Vertex Partition.

87

Consider a subgraph Em which contains no circuits; let
Pi be any part of Em and V(Pi) be the set of vertices in Pi'
If { Vmi’ Em} is a (vo-m)-tree pair then there is exactly one

vertex a 6 V(Pi) such that a 6 Vmi; therefore

aES1 or aeS2 , (4.4.7)

and for any vertex c 6 V( Pi)’ c fi a, then c 6 Vm. :
1

C68 or C654. (4.4.8)

3
If { ij , Em} is a (yo-m)-tree pair then there is exactly one

vertex b 6 V(Pi) such that b 6 ij; therefore

b6 S2 or b6 S4, (4.4.9)
and for any vertex c 6 V(Pi)’ c )5 b , then c 6 ij:
ceS1 or C653. (4.4.10)

These conditions must all be satisfied if Em is to be an allowable
subgraph. Note that a and b are particular vertices from V(Pi)
and that c is any vertex of V(Pi)’ c )4 a, c )14 b; therefore: if

a=b, then
' . .4. .
aeS2 and C683, (411)
ifafib, then
a6S1 and b6S4 and C653. (4.4.12)

In the case where Vmi and ij are neither identical nor

disjoint and both {Vmi’ Em} , {ij, Em} are (vo-m)-tree

pairs then Ern must contain m elements and no circuits; V(Em)

88

must contain all of the vertices of Vmi' iju-and perhaps other
vertices; each part P1 of Em must also satisfy either one of
the following criteria:

Criterion A: Pi must contain exactly one vertex which

is not contained in either Vm. or Vm. , and all remaining vertices
1 J

of Pi must be contalned 1n both Vmi and ij ;
Criterion B: Pi must contain exactly one vertex which is

contained in Vm. but not contained in Vm. and exactly one vertex
1
which is contained in ij but not contained in Vmi; all remaining

vertices of P. must be contained in both Vm and Vm. .
1 “" i J

Further, if the number of vertices in S4, and hence 51’ is x1,
then Em must contain at least x1 parts.

The subgraphs of Figure 4. 4. 2 illustrate, for the case
m = Z, all possible types of two element subgraphs Ezk such that
both { VZi' EZk} and { sz, EZk} are (vo-Z)-tree pairs. The
unlabeled vertices in the Figure can be any other vertices of the
graph. For subgraphs (a) - (d): V2i = sz = { v1, v2} ; (e) - (h):
V21: {v1, v2} , V21: {v2, v3}; (1) and (j): V2.1:{v1’ v2} ,
sz = { v3, v4} . Consequently, for a connected graph G0
containing at least four vertices: 7(i’ 3 has term rank two
if and only if Go contains at least one ,of the subgraphs (e) - (h)

of Figure 4. 4. 2.

(a)

<

<

<

89

(b) (C) (d)

Figure 4. 4. 2. Allowable Subgraphs, m = 2.

90

Assuming that at least one allowable Em has been found
for a given Vmi and ij then, using criterion A and B in
conjunction with an examination of the allocation of the vertices
from Vmi, ij within the parts of Em , it is possible to
determine whether or not certain vertices can be interchanged
between Vmi, ij and still maintain the (vo-m)-tree pair
property for Em. If, for example, in determining the term rank

of :’ i) one finds at least subgraph (e) of Figure 4. 4. 2 within

60’ then all of the following submatrices also have term rank two:

76:3). 76:1) . 76:2).
7C: :) , fl :), 74: Z) . (4.4.13)

11', on the other hand, examination of Go indicates that the gag
allowable subgraph contained in G0 has the form (h) of Figure
4. 4. 2, then only the first two submatrices in (4. 4.13) have term
rank two; the term rank of the last four submatrices is less than
We.

The existence or non-existence of at least one allowable
subgraph Em for a given pair of vertex sets Vmi and ij can
be checked by direct inspection of the graph. If the graph contains
a large number of vertices and elements then this can become a

time consuming process. Various algorithms have been devised

91

and prOgrammed to utilize a digital computer to search for
numerous types of subgraphs-strees, k-Atrees, circuits, paths,
etc. ----.within a given graph. 36-40 Programs of this type could
be modified, or new programs devised, to implement a testing
process. Consequently, this aspect is not considered further
in this investigation.

In the event that all allowable subgraphs have been found--
as might well be the case when a computer search program is
used--then (4. 2. 9) can be used to evaluate the minor of without
the necessity of actually forming the matrix . On the assumption

that (V: 2) has term rank m, then two cases arise: (1) if

Vm- and ij . are identical; 1. e. aprincipal minor of 7, then

1 mJ
the non-vanishing minors of the incidence-seg matrix in (4. Z. 9)

have the same sign within each term and (4. 2. 9) becomes:

Vm
det? i = z Y(Em ) (4. 4.14)
Vm. E k

1 mk

where Y(Emk) is the product of the F-element admittance
coefficients for the elements of Emk and the summation ranges
over all Emk such that { Vmi, Emk} is a (vo-m)-tree pair;

(2) If Vrni and ij are not identical then the evaluation of the
minor is complicated by the fact that the non-vanishing minors of
the incidence-seg matrix in (4. 2. 9) can have either sign within a
given term. A formula for the signs of the non-vanishing terms has

been derived and the result is given below.

92

Let
Vmi = {Viv viz, vim} (4.4.15)
and
ij - {vj1, v52, ..., vjm} (4.4.16)
where
‘ < ° < < ' < -
1:11 12 ... lm-vol
< ‘ < ' < < ' < -
1_J1 12 ... Jm-vol
Since Vm. and Vm. are not identical, then the subsets S1 and

1 J
S4 in Figure 4. 4.1 are not empty. Let the number of vertices in

51’ and hence in S4, be x, and
s4 = {vial’ vioZ’ Viax} (4.4.17)
51 = {vflw vjpz, vax} (4.4.13)

where oi and Bi are the positional indices of these vertices within

Vm. and Vm. respectively and

1 J

pl< pz< ...< (3x.

Criterion B implies that any allowable Em must contain at least
x parts and further, each part containing a single vertex from S4
must also contain a single vertex from 51' Thus this part matches

a vertex from S4 to a correSponding vertex from 51' If “k

93

is the number of inversions needed to rearrange the vertices in S1
so that they appear in the same order as their corresponding matched

vertices in S4, then for an allowable Em

x+2a. 1+2431 )1.
data F<E:i Hdetdz< mi=k> (1) (-1) 1‘ (4.4.19)

Since only pk depends upon EInk , then (4. 2. 9) becomes

Vm. x+Z 0.1+}: [ii p. k
V E
where the summation ranges over all Emk such that {Vm., Emk}
1

and {an Emk} are both (vo-m)-tree pairs.

4. 5. From Subgraphs to Maximum Term Rank Submatrices
The preceeding discussion has assumed that the vertex sets

Vm. and Vm. were specified initially and thus it became necessary

to elxamine th: graph Go to determine whether or not it contained
at least one subgraph Emk which satisfied both (vo-m)-tree pair
conditions. However, if any subgraph Em, containing no circuits,
is selected from Co then it is a simple matter to list all the vertex
sets Vmi such that { Vmi, Em} is a (vo-m)-tree pair.
Associated with any two of these vertex sets is an m by m

73 = 4a % a; (4.5.1)

and this submatrix must have term rank m. Note that the complete

submatrix from

94

incidence-seg matrix is used in (4. 5.1) to allow for the possibility
that the subgraph contains the reference vertex r0. These results
are applicable to the matrix in (4.1. 2) if the vertex sets
containing the reference vertex are deleted from the list.

First, consider another approach to calculating the number

nv defined in Theorem 4. 3. 8:

Theorem 4. 5.1. Let Go be a part of V0 vertices and

Em any m-element subgraph which contains no circuits. If Em

contains p parts and the k-th part contains xk elements; then the

vertex set V(Em) can be decomposed into

nv : E (xk +1) (4. 5. 2)

distinct subsets Vmi of m distinct vertices such that {Vmi’ Em}
is a (vo-m)-tree pair, i = l, 2, .. ., nv.

Proof: Since Em contains no circuits, then V(Em) contains
m+p vertices and each part of Em contains xk+l vertices. Let

Vmi be any m vertex subset formed by deleting p vertices from

V(Em), one vertex from each part. This can be donein any one of

P
n = TT (x +1) different ways. Now, E contains no circuits
v k=1 k m

and each part of Em contains exactly one vertex which is not a

member of Vmi . Therefore {Vmi' Em} is a (vo-m)-tree

pair for Go'

95

Consequently, if Go is a graph of F-elements such that
the F -element admittance matrix, F’ is diagonal and nonsingular,

and Vmi, ij are any two of the vertex sets of Theorem 4. 5.1

( Vm.)

% 1

a

ij

has term rank m. Furthermore, noting that

7421:?)

J

then

has term rank m if and only if
7 (vmj)
a
Vm.
1
has term rank m, and accounting for the fact that Vm and Vm

i J
can be identical, there are a total of

nv _ 2
2(2)+nv — nV (4.5.3)

different In by m submatrices of a associated with a single
circuitless subgraph Em, and each of these submatrices has

term rank m.

Chapter 5
COMPLETE SOLUTIONS FOR THE PRIMARY
SYSTEM OF EQUATIONS

5.1. Subgraphs and Feasible Proper Partitions

The preceeding chapter provides a basis for interrelating
proper partitions of the variables within a system of holac equations
associated with the graph correlate of an electric network and
classes of subgraphs of that graph. A given partition of the
variables is a proper partition if and only if a related submatrix
has the proper dimensions and rank; this submatrix, in turn, has
the proper m rank if and only if there exists within the graph at
least one member of a particular class of subgraphs. An m by m
submatrix has rank m only if its term rank is m; consequently
the existence of a particular subgraph constitutes a necessary
condition for the corresponding partition to be a proper partition
of the variables. It is not in general a sufficient condition as
certain subsets of values for the F-element admittance coefficients,
in conjunction with certain interconnection patterns of the F-elements,
can result in the rank of the submatrix being less than its term rank.
In certain types of problems this characteristic is desirable-~for
example: balanced bridges and resonant networks, while in other
types it may or may not be desirable. In recognition of these two
possibilities a partition of the variables is said to be a feasible
proper partition if and only if the related submatrix has the proper

dimensions and term rank.

96

97

As previously noted a complete solution for a system of
holac equations can be determined in many forms--for example,
any proper partition of the variables determines a corresponding
complete solution. Although any complete solution implies all
particular solutions it is often the case that certain forms of a
complete solution are more desirable than others. The approach
considered here allows one to investigate the feasibility of a
variety of forms of a complete solution without the necessity of
actually formulating the primary system of equations. The only
complete solutions which are considered explicitly here are those
obtained directly from proper partitions of the variables.

The key issue in such an investigation is to determine
whether or not a given partition of the variables is a feasible proper
partition. If it is, then a continuation of the investigation indicates
whether or not it is also a prOper partition. The vertex subsets,
51’ 52’ $3, and S4 introduced in the preceeding chapter play a
central role in these investigations. Each non-reference vertex
of the graph is incident to exactly one N-element, thus a one -to-
one correspondence is established between the vo-l N-elements

and the vO-l non-reference vertices of the graph. Recall that

4
3
II
(n
C‘.
01

(5.1.1)

II
U)
C'.
U)

Vm (5.1. 2)

j 1 3'

and that the set 82 contains all other vertices of the graph--

98

including the reference vertex r0. Permitting S1 and S4, or
S3, to be empty allows one to consider within the same framework
the possibilities of Vmi and ij being identical, disjoint, or
neither. Consider the system of holac equations in (3. 5. 21); the

set

{J2 J Kn. 7N3} (5.1.3)

N1 ’ N2'

is a complete set of dependent variables and

19ml... 71., 7N4} (51-4)

is the corresponding complete set of independent variables for

this system of holac equations if and only if

(5.1.5)

det?(vmi) = det 31 733 /£ 0. (5.1.6)
vmj 41 7’43

Examination of the relationships among the allocation of the
N-element variables within (5.1. 3) and (5.1. 4), the row and
column indices of the submatrix whose determinant appears in
(5.1. 6), and the vertex sets S1 through S4 yields the following
conclusions:

(1) Each of the n N-elements incident to the 111 vertices

l
of S1 has both associated element variables within the

dependent set (5.1. 3). These N-elements are classified

as NO-elements;

99

(2) Each of the n N-elements incident to the n2

2
vertices of 82 (other than r0) has its associated voltage
variable within the independent set (5. 1. 4) and current
variables within the dependent set (5. l. 3). These
N-elements are classified as Ne-elements;

(3) Each of the n N-elements incident to the n3

3

vertices of S3 has its associated current variable
within the independent set (5. l. 4) and voltage variable
within the dependent set (5.1. 3). These N-elements
are classified as Nh-elements;

(4) Each of the 114 N-elements incident to the n4
vertices of S4 has both of its associated variables

within the independent set (5.1. 4). These N-elements

are classified as Neh-elements.

Thus a partition of the variables, such that n 2 n4, identifies the

l
vertex sets Sl through S4 and conversely. This information, in
conjunction with the developments of the preceeding chapter, allows
one to investigate certain properties of a complete solution for the
primary system of equations in terms of properties of the graph
without the need for explicit formulations of the equations.

The classification of the N-elements as No" Ne-, Nh-,
or Neh-elements is determined by properties of the system of
holac equations and the graph--not by consideration of the

correlating electric network. This allows one considerable freedom

in the classification of the N-elements since there are often many

100

different proper partitions of the variables for a given system of
holac equations. This represents a departure from the usual
practice in electric network theory where the inclusion of Ne- and
Nh-elements has been generally based upon the presence of
regulated voltage and current sources within the correlating
electric network. Furthermore, this classification was seldom
altered. The general absence of any device in the physical
network having terminal characteristics which correlate with

the characteristics of No- and Neh-elements has undoubtedly
been a major reason for the general lack of consideration

given to these classes of N-elements.

5. 2. Particular Solutions and Specification of Variables

Once a desired proper partition of the variables has been
determined and the corresponding complete solution for a system
of holac equations has been obtained then the variables within the
independent set can be assigned arbitrary values with no danger
of introducing inconsistencies. Each such set of values determines
a particular solution and all particular solutions can be generated
in this manner. Often it is desired to select from the multiplicity
of particular solutions that solution, or solutions, which best
satisfy some prescribed criteria. These criteria may be stated
directly in terms of the variables within the system of holac
equations and/or in terms of other secondary or derived quantities
related to these variables. The form in which these criteria are
stated is often a deciding factor in the choice of partitions to be

checked.

101

The primary variables in the systems of holac equations
considered in this investigation are the voltage and current
variables associated with each element in the graph correlate

of an electric network:

V =lV

k e =V +jV

kl (5.2.1)

kZ’
and

I-IIIjek-I +'I (522)
k‘ ke ‘k11k2 "

for element k. The real power and reactive power variables for
certain elements comprise one set of secondary variables

conunonly encountered in electric power network problems.

Again for element k:

. W -J'9
Pk'i'JQk - Vka* = lele 1‘ llkle k (5.2.3)
_ jO-k
_ IVkI llkl e (5.2.4)
where

Pk is the real power,
Qk is the reactive power, and

k is the power factor angle.

Earlier developments have shown that a complete solution for a
primary system of equations can be obtained in terms of certain
subsets of the voltage and current variables associated with the
N-elements in the graph. Thus particular solutions are obtained
by assigning specific values to these variables in terms of

magnitudes and angles, or in terms of real parts and imaginary

102

parts. If one or more of the variables within the independent set
is not assigned a specific value or is only specified in part--for
example, the magnitude is specified but not the angle-~then a
family of particular solutions is obtained. These particular
solutions contain one or more parameters which can be varied
in an attempt to satisfy additional conditions which might have
been placed upon the particular solution. Consequently, for a
particular proper partition, the N-element falling into the Ne"
or Nh-element classification can have at most two parameters,
while those in the Neh-element classification can have at most
four parameters. By the appropriate specification of the
voltage and current variables for an Neh-element it is possible
to maintain any desired interrelation between these variables--
for example, specifying the magnitudes of the voltage and
current variables and the power factor angle fixes both the

real and reactive power for that element yet neither the element
voltage nor the element current is completely specified.

One further property of a system of holac equations is
examined at this point. Consider a fixed system of holac equations;
assume that at least two proper partitions of the variables exist
and that the corresponding complete solution for the system has
been determined for each proper partition. If the variables within
the independent set of one of these proper partitions are assigned
specific values than a particular solution is obtained. Now if the
variables within the independent set of any other proper partition

are subsequently assigned the values that they assumed in this

103

first solution then the resulting particular solution is identical
with the first one obtained. In terms of the N-element classification
defined earlier this means that if a desired particular solution is
obtained with a certain pattern of No" Ne-, Nh-, and Nah-elements
then this pattern can be altered into any other allowable pattern

and it is possible to maintain the same particular solution. For
example, established criteria for the consistent location of
regulated voltage and current sources within a physical network
coincide with the conditions such that the correlating N-elements
in the graph can be classified as Ne- and Nh-elements

10’ 11’ 41 However, within the framework 0f the

respectively.
correlating graph and primary system of equations, one is not
in general restricted to this particular N-element classification.
Thus if the appropriate conditions are satisfied these particular
N-elements can be considered as either Ne- or Nh-elements,

as well as No- and Neh-elements. Consequently the use of the

NO- and Neh-element classifications in an analysis problem need

not be based upon the existence of any correlating physical device.

5. 3. Applications in the Analysis of Electric Power Networks

Although the results of the preceeding investigation are
applicable to a larger class of network problems they are
particularly well—suited for use in the analysis of electric power
networks. As discussed in Chapter 1, specifying variables plays
an important role in many phases of electric power network

analysis. The techniques developed in this investigation permit

104

one to exercise considerably more freedom in the choice of specified
variables than was possible before. At the same time one is assured
that the chosen variables can be assigned arbitrary values with no
danger of introducing inconsistencies into the system of network
equations. These techniques are based upon properties of the
primary system of equations yet the investigation can be completed
without the necessity of actually formulating'the equations. The
required properties are stated directly in terms of the graph and
thus allow one to interrelate properties of the graph and properties
of solutions to the primary system of equations.

Theoretically the results of this investigation can be applied
to any finite graph of the type considered; however there are practical
limitations on the number of vertices and elements that can be
accommodated in an effective manner. Certainly the use of a digital
computer with a large storage capacity permits one to consider
problems associated with larger and larger networks. However
this capability, in itself, it not a panacea for all the problems in
the analysis of electric networks. There are situations when it is
desirable to ”localize" the problem and yet not completely dissociate
it from its relative place within a larger problem. The results of
this investigation, coupled with a zoning concept described in the

15. 16 provide the means for a new approach to the analysis

literature
of large-scale electric networks.
In the zoning approach16 a large graph is decomposed into a

number of subgraphs or zones such that (a) each subgraph is connected

and (b) any two subgraphs are element disjoint but have certain vertices

 

105

called U-vertices, in common. For the class of graphs considered
in this discussion it is assumed that the reference vertex is a
U-vertex for each zone and that each zone contains at least one
other U-vertex distinct from the reference vertex. Once the
original graph has been zoned in this manner the zones are then
separated and an "external" set of N-elements is added to each
zone; these N-elements are incident to the U-vertices only and each
non-reference U-vertex in a zone is incident to exactly one of these
added N-elements. In addition all external N-elements in a given
zone are incident to the reference vertex (which is also a U-vertex

for that zone). Figures 5. 3.1 illustrates this for the case of two

zones.

U-vertices: v1, v2, v3, ro

(a) Identification of zone and U—vertices.

 

(b) Graph after zoning and adding external N-elements.

Figure 5. 3. 1. Illustration of Zoning Technique.

106

It can be shown16 that if the primary system of equations for the
zoned graph, Figure 5. 3.1(b), is augmented with the following

sets of auxiliary equations:

 

 

 

 

 

 

 

 

r 1 PV _ — .1 _
N1 N4 N1 N4
VNZ VNS and N2 INS , (5. 3. l)
VN3 VN6 N3 LIN6

then each solution of this augmented primary system of equations
determines exactly one solution for the primary system of
equations for the original graph, Figure 5. 3. 1(a), and conversely.
Thus the augmented primary system of equations for the zoned
graph and the primary system for the original graph are essentially
equivalent systems of equations.

The zoned graph consists of a number of separate graphs,
or zones, and for each zone a primary system of equations can
be formulated and solved. If, in addition, the auxiliary equations,
such as (5. 3.1), are satisfied then a solution of the primary system
of equations for the original graph is obtained. This suggests a
new approach to the analysis of large complex networks. If zones
are so chosen that each of the external N-elements can be classified
as Neh-elements then, since both V and I for these N-elements
can be arbitrarily specified, one is assured that the auxiliary

equations can be satisfied. Once this has been established each

zone can be analyzed independently--yet the composite of the zone

107

solutions determines a corresponding solution for the original
un-zoned graph.

This technique provides considerable flexibility in the
analysis of electric networks. For the purpose of illustration
consider the two zone case of Figure 5. 3.1 and assume that
the original graph has been zoned so that elements N1, N2, and
N3 can be classified as Neh-elements for zone 1 and that elements
N4, N5, and N6 can be classified as Neh-elements for zone 2.
Suppose that one has a particular solution for the primary
system of equations associated with the original unzoned graph.
Using standard techniques34 the V and I variables associated
with the external N-elements are calculated so that the corre-
sponding solution is maintained in the zoned graph. Actually the
entire solution for the original graph is not needed--only that
portion of the solution required to calculate the V, I variables
for these N-elements is necessary. Note that this data could
be obtained from measurements made in the actual network.
Now consider zone 1 and its associated primary system of
equations. Any solution of this primary system for which the
V and 1 variables associated with elements N1, N2, and N3
remain invariant can be combined with the existing solution for
zone 2 to obtain a new solution for the primary system for the
original graph. One is assured that the V and I variables
for N N

1, 2’ and N3 can be maintained at the desired values

since they can be classified as Neh-elements. In this manner the

108

solution for zone 1 can be varied and yet the solution for zone 2
remains invariant. Changes in the solution have been localized
or confined to zone 1. When this is applied to a multiZ-‘zone
problem the concept represents not only a reduction in the
complexity of the problem to be analyzed but also permits one
to investigate the possibilities of localizing, within prescribed
zones, changes in the operating characteristics.

One further application is considered at this time. Again
consider a zoned graph. The fact that the external N-elements
for a zone can be classified as Nah-elements implies that there
exists within the zone an equal number of No-elements; furthermore
the No- and Neh-element classifications can always be interchanged.
Thus it is possible to obtain a particular solution for the primary
system associated with this zone utilizing the maximum number
of specified conditions within the zone. This solution determines
the V, I variables associated with the No-elements incident to
the U-vertices of that zone. Then the auxiliary equations, such
as (5. 3.1), are used to transfer this condition to the Neh-elements
in the adjacent zones; in this process the effects of the first zone
upon the adjacent zones is completely determined in terms of the
V and 1 variables associated with the external N-elements.
Depending upon the F-element subgraph with a particular zone it
is also possible to interchange the No" Neh-element classifications
for subsets of the N-elements and thus it is possible to reflect

changes in the solution into selected zones.

109

5. 4. Example

A portion of an actual electric power system--the Denver
area of the Public Service Company of Colorado--is examined in
this section to illustrate the preceding developments and at the
same time to establish the feasibility of the zoning techniques
discussed in Section 5. 3. A network representation of this
system contains 33 nodes plus the ground bus, 39 transmission
line sections-~each represented by the conventional pi equivalent,
6 generators, and 24 loads. A simplified interconnection diagram
representing the transmission network is shown in Figure 5. 4. 1
and detailed nodal diagrams of the individual zones are shown in
Figures 5. 4. 3 through 5. 4. 7.

The zones in this example were chosen in a somewhat
arbitrary manner to illustrate the technique; in general the
initial choice of zones would depend upon particular characteristics
of the system under investigation. Factors which would influence
the choice include geographical distribution of the system, service
or load areas, locations of interconnections with adjacent systems,
etc. Once the zones have been defined it is necessary to determine
whether or not the external N-elements can be classified as
Neh-elements. For each zone in this example the external
N-elements can be classified as Neh-elements, i. e. both of the
V and I variables associated with each of these N-elements can
be allocated to the independent set of some prOper partition of the

variables within the primary system of equations for that zone.

110

 

.xnoafioz Gowmmflhmnmnfi MOM Ednmmwfl Gomuoofidoonofifi J .v .m oufiwfim

 

 

 

 

 

 

 

 

 

N HZON my

111

0—0 TRANSFORMER
O D BUS OR NODE

O LOAD

g GENERATION
W LINE SECTION

X

¢ CR CU ND

Uij U-VER TEX: ZONE i AND ZONEj

Figure 5. 4. 2. Key to Symbols.

112

 

.H ocoN 1 Emnwma Hmpoz .m .w .m oudmfim

 

 

 

 

 

0 E d

 

 

 

 

 

x/wix/

 

 

113

NH

 

 

 

 

 

.N oGoN I Emnwsflfl Hmpoz .v.1v.m 6.2:me

 

 

0H

 

 

 

 

 

.ND

114

 

«L

 

.m oGoN a Enhmmwfl #3002 .m J» .m ouflwwm

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(a
no

 

 

 

 

 

m.~b

 

 

(a../V
/\U\
C
as

 

 

 

 

 

115

J... ocoN n Eduwmwfl Hdpoz .ogv .m oafimfim

 

 

 

 

om

 

 

<X
wN

0H

 

 

 

 

G

ll6

 

.m osoN .. Eduwdfifl Hepoz .>.¢.m 0.“:th

 

 

 

NA

x/Fxéx/
Q Q

 

 

m.~D

 

X X X
/>\/h\

 

«Z

 

 

117

This fact establishes the feasibility of the zoning approach
discussed in Section 5. 3.

Consider the subgraph corresponding to any zone and
the set of external N-elements for that zone. The graph elements
corresponding to the transmission network are considered as
F-elements and the graph elements corresponding to the generators
are considered as N-elements. If the load admittance coefficients
are not known then the corresponding graph elements are considered
as N-elements; if a load admittance coefficient is known then the
graph element can be handled as an F-element or as an N-element
as discussed in Section 3. 5. In this example it is assumed that
all graph elements corresponding to loads are treated as N-elements.
In addition any non-reference vertex which is not a U-vertex, or
is not incident to a generator or load element, is considered to be
incident to an N-element--see Section 3. 5. When these steps have
been completed it is possible that certain non-reference vertices
are incident to more than one N-element; this is the case when
a given node is incident to both a generator and a load, or when a
U-vertex is incident to a generator and/ or load. Any such parallel
connection of N-elements is now replaced by a single N-element.
There is no loss in generality in doing this since V for the
equivalent N-element is the same as V for each of the parallel
N-elements and I for the equivalent N-element is the sum of the
1's for each of the parallel N-elements. Once this equivalent 1

has been determined then any choice of values for the 113 of the

118

parallel N-elements which yields this sum is satisfactory. (Note
that if one of the external N-elements parallels another N-element
and is subsequently replaced by a single N-element then it is
necessary to determine the I associated with the external
N-element before the auxiliary equations discussed in Section

5. 3 are used). At this point a vo-vertex zone contains a total of
Vo-l N-elements; each non-reference vertex is incident to
exactly one N-element and all N-elements are incident to the
reference vertex.

As discussed in Section 5.1 any partition of the 2(vo-l)
variables associated with this set of N-elements into two disjoint
sets of vO-l variables each, i. e. a trial classification of the
N-elements, defines the distribution of the vertices of the zone
into the sets 51’ 52’ S3, and S4 which, in turn, define the two
vertex sets Vmi and ij. If the graph contains at least one
m-element subgraph of F-elements Em such that both { Vmi,
Em} and { ij, Em} are (vo-m)-tree pairs then this
partition is a feasible proper partition and the corresponding
N-element classification is called a feasible classification. For
any feasible proper partition the investigation is continued until
all such subgraphs have been determined, then (4. 4. 20) can be
utilized to determine whether or not this feasible proper partition
is also a proper partition of the variables.

To illustrate this technique consider zone 2 as shown in

Figure 5.4. 4. The graph for this zone contains 10 vertices in

119

addition to the reference vertex. The F-element subgraph
consists of the elements corresponding to the line sections since
the generator and all loads are represented by N-elements. Note
that the single N-element incident to vertex 10 in the zone graph
represents the parallel connection of an N-element corresponding
to the load and the external N-element added to this zone by virtue
of the fact that this vertex is also a U-vertex. Let the N-elements
be identified by referring to the vertex to which the element is
incident. . The zone graph is now investigated to determine whether
or not N5, N10, N11, and N12 can be classified as Nah-elements.
Since a complete set of independent variables for this zone contains
10 variables this choice does not completely determine a trial
classification pattern. To complete the trial classification of the
N-elements let N5, N9, N10, N11, and N12 be considered as
potential Neh-elements; thus N13, N14, N15, N1 6’ and N17 must

be considered as potential No-elements. The corresponding

vertex sets are

{5, 9,10,11, 12} (5.4.1)

<1
II
(I)
ll

Si

and

V. = s {13,14,15, 16,17} (5.4.2)

SJ 1

The vertex sets V and V5j are disjoint hence any subgraph of

Si

F-elements which satisfies the 6-tree pair condition for both

vertex sets must consist of 5 elements which match V51 onto

V5j in a one-to-one manner. Any such set of 5 F-elements must

120

be included in the subgraph shown in Figure 5. 4. 8. Inspection of
this subgraph indicates the existence of exactly two 5-element
subgraphs having the desired characteristic. These subgraphs
are shown in Figure 5. 4. 9.

The existence of either subgraph insures that the
partition of variables under consideration is a feasible proper
partition. Further it is known that the expansion of det? G?)
for this zone graph contains exactly two non-zero terms.

Using (4. 4. 20) to evaluate this determinant:

V
det 51
V

-{-YYYYY +YYYY

1 3 7 8 10 1 5 Y9} (5°4°3)

= Y1Y7Y 85Y(Y 9- Y3 Y1 o). (5. 4. 4)
For the particular system under investigation
Y3 = Y and Y = Y (5. 4. 5)

5 9 10’

V
and although fi<V5i) has term rank 5, the actual rank is less
51'

than 5. Therefore this particular partition of the variables is not
a proper partition of the variables and the trial classification of
the N-elements is not acceptable.

Since the original requirement was only that elements N5,
N10, N11, and N12 be classified as Neh-elements it is possible
that another classification of the N-elements will work. Consider

the following trial classification-u-Neh: N5, N N

N10’ 11' 12‘

Ne: N9, N17;NO: N13, N14, N15, N16' The corresponding vertex

121

a Y. m

 

 

0Q e
®/Y8 Y9 ‘ Y5 @

Figure 5. 4. 8. F-Element Subgraph

 

(a) (b)

Figure 5. 4. 9. Subgraphs which Satisfy the 6-Tree
Pair Criteria.

122

sets are:

V4j = 51 = {13,14,15, 16}, (5.4.6)
52 = {9, 17, r0} . (5.4.7)
V41 = 54 = {5,10,11,12} . (5.4.8)

Again, since V4i and V4]. are disjoint, any 4-e1ement subgraph

E such that {V4i’ E4k} and {V4j’ E4k} are both 7-tree

4k

pairs must match V4i onto V4j in a one-to-one manner and thus
be contained in the F-element subgraph of Figure 5. 4. 8. Exactly

one such subgraph exists and is shown in Figure 5.4.10. The
V41)

V4j
contains only one non-vanishing term in its expansion- -therefore

F- element admittance coefficients are non-zero and detfl)

both the term rank and the rank are 4 and the partition under

consideration is a proper partition of the variables for this zone.
9 Y8 9
9 Y 9

Figure 5. 4. 10. Subgraph which Satisfies the 7-tree Pair
Criteria.

123

This result establishes that it is possible to classify

elements N , N N and N for zone 2 as N -e1ements.
5 12 eh

10’ 11'

Other proper partitions for this zone also yield the same
conclusion. In general the type of problem under consideration
dictates which proper partition or partitions are apt to be more
useful in a particular situation.

The preceding example illustrates the approach which
proceeds from a given partition of the variables to a search for
suitable subgraphs. As indicated in Section 4. 5 this process can
be revised in the sense that starting from a given circuitless
subgraph it is possible to determine a considerable number of
feasible proper partitions. This method is more direct than the
first and at the same time gives a better indication of the inter-
relation between the interconnection patterns of the F-elements
and corresponding feasible proper partitions. Of course for
certain sets of values for the F-element admittance coefficients
it is possible for a feasible proper partition to fail to qualify as
a prOper partition. To verify whether or not this is the case it
becomes necessary to examine the graph and search for additional
allowable subgraphs.

To illustrate this second approach consider zone 4--see
Figure 5. 4. 6. The zone graph contains 6 N—elements and a
complete solution for the primary system of equations is obtained
in terms of certain subsets of 6 N-element variables. The fact

that 6 variables can be selected from a set of 12 variables in

124

any one of 924 different combinations gives at least some indication
that there is potentially considerable flexibility in the choice of a
set of independent variables for the primary system of equations
for this zone. Consider the simple 3-element subgraph of

F-elements from zone 4 as shown in Figure 5. 4.11.

69 28 @

 

909

Figure 5. 4. ll. F-Element Subgraph from Zone 4.

There are eight distinct sets of three vertices for which the given

subgraph satisfies the 3-tree pair criteria:

{10, 25, 26} , {10, 25, 27}, {10.26, 29}, {10, 27. 29}.

{25, 26, 28} , {25, 27, 28}, {26,28,29} , {27, 28, 29} .
(5. 4. 9)
The reference vertex is not contained in any of those vertex sets so

there are then 64 different ways of choosing V and V . from

3i 33
this list of vertex sets and corresponding to each choice one obtains
a feasible proper partition of the variables! These results are

given in Tabulation 5. 4.1 in terms of feasible N-element classifications.

125

TABULATION 5. 4. 1.

A PARTIAL LISTING OF
FEASIBLE N-ELEMENT CLASSIFICATIONS FOR ZONE FOUR

 

VERTEX SETS

N-ELEMENT CLASSIFICATION

 

 

 

 

 

 

 

 

 

V31 Va No Ne Nh Neh

1 10.25.26 10.25.26 -- 27.28.29 10.25.26 --

2 10.25.27 27 28.29 10.25 26

3 10.26.29 29 27,28 10,26 25

4 10, 27. 29 27. 29 28 10 25. 26

5 25.26.28 28 27.29 25.26 10

6 25.27.28 27.28 29 25 10.26

7 26.28.29 28,29 27 26 10.25

8 27.28.29 27.28.29 -- -- 10.25.26

9 10.25.27 10.25.27 -- 26.28.29 10.25.27 -—
10 10.26.29 26.29 28 10 25,27
11 10.27.29 29 26.28 10.27 25
12 25.26.28 26,28 29 25 10.27
13 25.27.28 28 26.29 25.27 10
14 26.28.29 26.28.29 -- -- 10.25.27
15 27.28.29 28,29 26 27 10.25
16 10.26.29 10.26.29 —- 25.27.28 10.26.29 --
17 10.27.29 27 25.28 10.29 26
18 25.26.28 25.28 27 26 10.29
19 25.27.28 25.27.28 -- -- 10.26.29
20 26.28.29 28 25.27 26.29 10
21 27. 28, 29 27. 28 25 29 10. 26
22 10.27.29 10.27.29 —- 25.26.28 10.27.29 --
23 25.26.28 25.26.28 -- -- 10.27.29
24 25.27.28 25.28 26 27 10.29
25 26. 28, 29 26. 28 25 29 10, 27
26 27.28.29 28 25,26 27,29 10
27 25.26.28 w 25.26.28 —- 10.27.29 25.26.28 --
28 25.27.28 27 10.29 25.28 26
29 26.28.29 29 10.27 26.28 25
30 27.28.29 27.29 10 28 25.26
31 25.27.28 25.27.28 -- 10.26.29 25.27.28 --
32 26.28.29 26.29 10 28 25.27
33 27.28.29 29 10.26 27.28 25
34 26.28.29 26.28.29 -- 10.25.27 26.28.29 --
35 27.28.29 27 10,25 28,29 26
36 27.28.29 27.28.29 -- 10.25.26 27.28.29 --

 

 

 

 

126

h-element classifications are always inter-

changeable only 36 different classifications are shown.

Since the N - and N
o e

It should be noted that once it is established that a given
partition of the variables is a feasible proper partition then only
specific interrelations among the admittance coefficients of the
F-elements contained in the allowable subgraphs can result in
this partition failing to qualify as a prOper partition. Consequently
there is a good possibility that most feasible partitions are also
proper partitions. For example, within the partial listing of
Tabulation 5. 4.1 there are 16 feasible proper partitions in
which N10 (the external N-element for this zone) is classified
as an Neh-element. In each case the partition is also a proper
partition of the variables. Furthermore each of these proper
partitions determines an additional proper partition by inter-
changing the No- and Neh-element classifications. Hence of the
64 feasible proper partitions determined by the simple subgraph
of Figure 5. 4.10 at least 32 are also proper partitions of the
variables. Consequently it is possible to select from a
multiplicity of proper partitions those which are best suited

for the particular study under consideration.

Chapter 6
SUMMARY AND SUGGESTIONS FOR FURTHER
RESEARCH

6. 1. Summary

To effectively plan the current operation as well as the
future expansion of electric power systems requires a knowledge
of the operating characteristics of the existing and/or proposed
systems. Analysis of a class of power system studies utilized
in determining the electrical characteristics of a power system
indicates that these studies are essentially problems in the
analysis of electric networks. These studies differ from
problems in ”conventional“ network analysis primarily in two
aspects: (1) the size and complexity of the network under consider-
ation, and (2) the type of initial problem specification. The avail-
ability of digital computers has alleviated, but not eliminated,
difficulties associated with the size of the network. Problems
associated with the initial specification of variables are more
fundamental in nature and must be considered within the frame-
work of the network equations since it is mandatory that
inconsistencies are avoided. It is logical that a re-examination
of the variable specification aspect of these network studies should
originate at the level of the correlating graph and associated primary
system of equations since they constitute the foundation for electric

network theory.

127

128

The (1)-domain graph correlates of the network under
consideration are comprised of two general types of elements:
relation elements (F-elements) and no-relation elements (N-
elements); the latter type is characterized by a lack of any fixed
interrelation between the associated V and I variables and
furthermore neither of these variables is specified initially. The
resulting primary system of equations is homogeneous in form
and certainly consistent. Properties of subgraphs of F-elements
are subsequently utilized to define classifications of the N-elements
such that either, neither, or both of their associated variables can
be assigned arbitrary values with no danger of introducing
inconsistencies. The investigation clearly indicates that a
multiplicity of N-element classification patterns exist for a given
graph and provides the basis for new and more general approaches
to the analysis of electric networks-~particularly those problems

in which it is desired to maintain prescribed operating conditions.

6. 2. Suggestions for Further Research

The most apparent area for futher study, and the one in
which current work is directed, is the application of these techniques
to problems associated with specific power systems. As noted in
the examples of Chapter 5 there exist a multiplicity of proper
partitions, or N-element classification patterns, even in simple
examples and in general the criteria for the selection of one or
more of these allowable patterns is dictated by the system under

consideration. A similar argument holds for the choice of zones

129

within a particular system. Another important concept is implicit
in these studies and this regards instrumentation. It is conceivable
that studies of this nature will indicate a need for new concepts
and/ or techniques in instrumentation if optimal operating conditions
are to be maintained as the system size increases.

Other areas of suggested research include consideration
of graphs containing more general configurations of N-elements
and extension of the class of N-elements to include, for example,
”coupling” between N-elements. Last, but not least, is the need
for continuing investigations into the general properties of the

primary system of network equations.

10.

ll.

BIBLIOGRAPHY

Ewald, E. , and Anglund, D. W. , “Regional Integration of
Electric Power Systems, " IEEE Spectrum, Vol. 1, No. 4,
April 1964, pp. 96-101.

Stevenson, W. D. , Elements of Power Systems Analysis,
second edition, McGraw-Hill Book Company, Inc. , New
York, 1962.

Swidler, J. C. , "National Power Survey and the Public Interest, ”
Proc. American Power Conference, Vol. XXV, 1963, pp.
17-24.

Swidler, J. C. , "The Electric Power Industry in the Decades
Ahead, " Proc. American Power Conference, Vol. XXVI,
1964, pp. 34-42.

Concordia, C. , and Maginniss, F. J. , "Developments in the
Automation of System Planning During 1960, " Proc. American
Power Conference, Vol. XXIII, 1961, pp. 820-830.

Dillard, J. K., and Sels, H. K., ”System Planning--Past,
Present, and Future, " Proc. American Power Conference,
Vol. XXIV, 1962, pp. 928-938.

Fiedler, H. J., and Kirchmayer, L. K., ”Digital Computer
Control of System Operation, " Proc. American Power
Conference, Vol. XXV, 1963, pp. 868-878.

Ender, R. C.,and Galloway, C. D., "Progress in Total
System Planning--Generation, Transmission and

Distribution, '1 Proc. American Power Conference,
Vol. XXV, 1963, pp. 812-822.

Friedlander, G. D., ”Computer-controlled Power Systems, "
IEEE Spectrum, Vol. 2, No. 4, April 1%, pp. 60-81; and
Vol. 2, No. 5, May 1965, pp. 72-91.

Reed, M. B. , Foundation for Electric Network Theory, Prentice-
Hall, Inc., Englewood Cliffs, New Jersey, 1961.

Seshu, S. , and Reed, M. B. , Li__n_ear Graphs and Electrical

Networks, Addison-Wesleyr Publishing Company, Inc. ,
Reading, Massachusetts, 1961.

130

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

131

Hale, H. W., and Goodrich, R. W., “Digital Computation
of Power Flow--Some New Aspects, “ AIEE Transactions,
Vol. 78, pt. III, October 1959, pp. 919-924.

Van Ness, J. E., and Griffin, J. H., "Elimination Methods
for Load-Flow Studies, " AIEE Transactions, Vol. 80,
pt. III, June 1961, pp. 299-304.

Zabrosky, J. and Rittenhouse, J. W., Electric Power
Transmissio_n, Ronald Press Co. , New York, 1954.

 

Reed, M. B., Reed, G. B., McKinley, J. L., Polk, H. K.,
Hugo, R. V., and Martin, W. J., "A Digital Approach
to Power-System Engineering-I, -II, -III, -IV, " AIEE
Transactions, Vol. 80, pt. III, June 1961, pp. 198-225.

Reed, M. B., and Reed, G. B., A Network Reduction-
Restoration (Equivalence) Theory, Michigan State University
Press, East Lansing, Michigan, 1964.

Ward, J. B. , and Hale, H. W., "Digital Computer Solution of
Power Flow Problems, " AIEE Transactions, Vol. 75, pt. III,
June 1956, pp. 398-404.

Brown, R. J., and Tinney, W. F., "Digital Solutions for Large
Power Networks," AIEE Transactions, Vol. 76, pt. III,
June 1957, pp. 347-355.

Glimm, A. F., and Stagg, G. 5., "Automatic Calculation
of Load Flows, " AIEE Transactions, Vol. 76, pt. 111,
October 1947, pp. 817-828.

Van Ness, J. E. , ”Iteration Methods for Digital Load Flow
Studies," AIEE Transactions, Vol. 78, pt. III, August 1959,
pp. 583-588.

Dyrkacz, M. S., and Maginniss, F. J., "A New Automatic
Program for Load-Flow Studies on the IBM 704, " AIEE
Transactions, Vol. 78, pt. III, April 1959, pp. 52-62.

Carlin, H. J., and Youla, D. C., “Network Synthesis with
Negative Resistors," Proc. IRE, Vol. 49, May 1961,
pp. 907-9200

Carlin, H. J. , “Singular Network Elements, " IEEE Trans.
on Circuit Theory, Vol. CT-ll, March 1964, pp. 67-72.

Birkhoff, G. , and Mac Lane, 8. , A Survey of Modern Aliebra,
revised edition, The MacMillan-f— Company, New York, 1953.

25.

26.

27.

28.

29.

30.

31.

32.

33.

34.

35.

36.

37.

38.

132

Gantrnacher, F. R., The Theory of Matrices, Vol. 1, Chelsea
Publishing Company, New York, 1959.

Hohn, F. E., Elementary Matrix AlugebraJ The MacMillan
Company, New York, 1958.

Mirsky, L. , An Introduction to Linear Algebra, Clarendon
Press, Oxford, England, 1955.

Thrall, R. M. , and Tornheim, L., Vector Spaces and Matrices,
John Wiley and Sons, Inc. , New York, 1957.

Berge, Claude, The Theory of Graghs and Its Applications,
John Wiley and Sons, Inc. , New York, 1962.

Ore, Oystein, Theory of Graphs, American Mathematical
Society Colloquium Publications, Vol. XXXVIII, Providence,
Rhode Island, 1962.

 

Guilleman, E. A. , Introductory Circuit Theory, John Wiley and
Sons, Inc., New York, 1953.

 

Kim, W. H., and Chien, R. T., Tppological Analysis and
Smthesis of Communication Networks, Columbia University
Press, New York, 1962.

 

Reed, M. B. , and Seshu, S. , ”On Topology and Network Theory, "
Proc. U. of 111. Symposium on Circuit Analysis, May 1955,
pp. 2.1-2.16.

Seshu, S., and Balabanian, N. , Linear Network Analysis, John
Wiley and Sons, Inc. , 1959.

Weinberg, Louis, Network Analysis and Synthesis, McGraw-
Hill Book Company, New York, 1962.

Fujisawa, T. , "On a Problem of Network Topology, " IRE
Trans. on Circuit Theory, Vol. CT-6, September 1959,
pp. 261-266.

Maxwell, L. M., and Reed, G. B., "Subgraph Identification--
Segs, Circuits, and Paths, ” Proceedin 3 Eighth Midwest
Symposium on Circuit Theory, June 19 5, Colorado State
University.

Mayeda, W. , and Seshu, S. , ”Generation of Trees without
Duplication," IEEE Trans. on Circuit Theory, Vol. CT-lZ,
June 1965, pp. 181 -184.

133

39. Minty, G. J. , A Simple Algorithm for Listing all the Trees
of a Graph, " IEEE Trans. on Circuit Theory, Vol. CT-12,
March 1965, p. 120.

40. Piekarski, M. , "Listing of All Possible Trees of a Linear
Graph, ” IEEE Trans. on Circuit Theory, Vol. CT-lZ,
March 1965, pp. 124-125.

41. Reed, G. B., and Reed, M. 3., "Patterns of Driving Elements
such as Appear in Tube and Transistor Networks, ” Proc.
2nd. Midwest Symposium on Circuit Theory, Michigan State
University, December 1956, pp. 3.1-3. 16.