ON THE REALIZATEON OF TIME DOMAIN MODELS OF REAL LBNEAR BELEMENT SYSTEMS } _. Thesis fog fh‘c Dogma of Ph. D. l : MmHIGAN STATE UNIVERSITY ~ l Danald Jahn Rauch 19-63 THESIS This is to cutlfg that the that entitled On the Realization of Time Domain Models of Real Linear Bielement Systems Pro-mod by Donald J. Rauch haboonnocopbdtowndlfulflllmt ofthoroqumufor .EhJ—degroo inn—Electrical Engineering Ace-w Major pots-nor D." Novempgg |I lgfi: LIBRARY Michigan State University ABSTRACT ON THE REALIZATION OF TIME DOMAIN MODELS OF REAL LINEAR BIELEMENT SYSTEMS by Donald John Rauch In recent years there has been a trend in modern engineering analysis to formulate mathematical models of physical systems as a set of linear, first deriviative-explicit differential equations. The question now arises as to whether a system graph can be synthesized from this same set of equations. This thesis deals with the realization of time-domain models of real linear bielement systems. The problems that are considered in this thesis can be classified as follows: 1. The characterization of time-domain models of real linear bielement systems, 2. The recognition of an arbitrary time domain model to be a real linear bielement system, and 3. The synthesis of a graph from an acceptable time-domain model. .From the time-domain analysis, real linear bielement systems are characterized by their associated matrices. These systems are shown to be reducible to a canonical graph. The canonical associated matrix corresponding to a maximum order star tree of a canonical graph is best described as the product of two symmetric matrices. Each of the symmetric matrices has a distinctive sign pattern and exhibits the property of diagonal dominance. All other associated matrices corresponding to arbitrary maximum order trees of a graph can be made to exhibit these same properties by the use of a similarity transformation. A necessary condition for the recognition of time-domain models of real linear bielement systems is that the associated matrix has real eigenvalues. A sufficient condition is that the eigenvalues be real distinct. Three techniques are derived for the decomposition of an arbitrary matrix into the product of two symmetric matrices. A test is also provided to determine if one of the matrices is diagonal. Abstract Donald Jehn Ranch The synthesis of a graph is accomplished by interrelating the decomposed matrix to the canonical associated matrix. Necessary and sufficient conditions are given for the synthesis of a graph with positive, negative and zero elements and for the synthesis of a graph with non-negative elements. Flow charts are developed to illustrate how an arbitrary coefficient matrix can be rec0gnized and realized as the associated matrix of a real linear bielement system. ON THE REALIZATION OF TIME DOMAIN MODELS OF REAL LINEAR BIELEMENT SYSTEMS By Donald John Raueh A THESIS submitted to Michigan State university in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Electrical Engineering 1963 G— 81. q n1 7/8; X b 4 ACKNOWLEDGEMENT The author is indebted to his thesis advisor, Dr. D. P. Brown, for the many valuable suggestions in the preparation of this thesis. Special thanks are due to Dr. Y. Tokad for his counseling during the writing of the final draft of the thesis. Finally, the author wishes to thank Dr. M. B. Reed, his committee chairman, for the encouragement and guidance throughout the entire graduate program and for his fundamental work in electrical network theory on which much of this thesis is based. * * * * * *- 11 CONTENTS LIST OF FIGURES . . . . . . . . . . . LIST OF APPENDICES} LIST OF SYMBOLS . . . . . . . . . . . I. INTRODUCTION AND ANALYSIS . 1.0 Introduction . .'. . . 1.1 Time Domain Analysis . 0 II. CHARACTERIZATION OF REAL LINEAR mmmmm 010-. o F'UJNI—‘o III. wwwww VWNI—‘O g E SYNTHESIS METHOD. err-'4:— bowl-‘0 V. CONCLUSION 5.0 Discussion of Results 5.1 Additional Prdblems . BIBLIOGRAPHY 111 Introduction . . . . . . . The Complete Graph . . . . The Classification of Real Characterization of Class 1 Systems Conclusion . . . . . . . . . . . . . . . . . . . . SYNTHESIS OF A CLASS OF REAL LINEAR BIELEMENT Introduction .'. . .‘Q . . .'. . Decomposition of a Square Matrix Synthesis of RC Graphs . . . . . Synthesis of RL Graphs . . . . . Conclusion . . . . . . . . . . . BIELEMENT SYSTEMS Linear Bielement systems. 90-.~.-.- O SYSTEMS . . ...... O O O O O O O O O O O O 0 O O 0 O 0 Introduction . . . . . . . . . . . . . . . . . . Determination of Realizable Coefficient Matrices The Synthesis Method . . . ' ' ‘ ' ' ‘ " Conclusion . . . . . . . . Page Figure 2.1.0 2.1.1 h.l.0 1+.2.o u.2.1 1+.2.2 u.2.3 u.2.u u.2.5 u.2.6 5.0.1. LIST OF FIGURES Complete graph Qi+l of c-elements with m+l vertices . . . . Star tree T8 of n+1 vertices . . . . . . . . . . . . . . . Flow chart for the determination of acceptable coefficient matrices . . . . . . . . . . . . . . . . . . . . . . . . . Flow chart of RC graph synthesis . . . . . . . . . . . . . Flow chart of RL graph synthesis . . . . . . . . . . . . . Synthesized RC graph G3 of Ex. 1 . . . . . . . . . . . . . Synthesized RC graph GM of Exs. 2 and 3 . . . . . . . . . . Path Tree T of GM . . . . . . . . . . . . . . . . . . . . J Synthesized RL graph G3 of Exs. h and 5 . . . . . . . . . . Synthesized graph Gk of Ex. 5 . . . . . . . . . . . . . . . Elemental adaptive system . . . . . . . . . . . . . . . . . iv Page 9 9 #2 1+7 1+7 #8 51 57 61 63 66 Appendix A. LIST OF APPENDICES Theorems and Definition from References . Page 71 ALc’ ARC’ ARL a 13 (A ’ (ls ac’ aT’ aci’ 0,31 0:, Q31 B B 1’ 2. Bf Bij b b-X- ijo LIST OF SYMBOLS Description Associated or coefficient matrix Associated matrices corresponding to trees Ti’ TJ Associated matrix of the ith part of a separable graph for the subtrees TJ’ Ts' Associated matrices of bielement systems ’Ts Element of A Incidence matrix Submatrices of Cl Submatrices of the incidence matrix for the i separable graph th part of a Similarity transformation between A1 and AJ Coefficient matrices f circuit matrix Submatrix of Bf Number of branches of a tree Neighborhood C matrix Diagonal matrix of branch c-elements Diagonal matrix of chord c-elements Diagonal matrix of all c-elements of a graph corresponding to tree T1, T8 c-element incident to vertices i and J c-element incident to vertex i and the reference node element of C Known value of c 13 vi Description Diagonal matrices Non-zero element of diagonal matrix Determinate of matrix Diagonal matrix Elements of a complete graph Number of elements of a graph Function Graph Diagonal matrix of the branch g-elements Diagonal matrix of the chord g-elements Diagonal matrices of all g-elements of a graph corresponding to trees Ti’ T8 Graphs having v, n+1 vertices g-element incident to vertices i and J g-element incident to vertex i and the reference node Element of R Known value of gij unit or identity matrix Jacobian L matrix Diagonal matrix of branch l-elements Diagonal matrix of chord l-elements l-element incident to vertices i and j l-element incident to vertex i and the reference node Vector Element of L vii Symbol P r P , P2, P l J Pn+1 Pij’ P38 P 11’ P22 p (ii) Q:+l’ Q541’ QIJi-o-l R R RiJ I‘ SIll’ $122 111’ S112’ S122’ 123 mm gell’ Ss12’ S822’ 823 8* V Description Jordan similarity transformation Known value of P Parts of a graph A part with n+1 vertices Permutation matrices Submatrices of PJ8 Polynomial in A Complete graphs of n+1 vertices composed entirely of c-, g-, l-elements R matrix Ratio matrix Submatrix of R Next largest integer to r* Real number Submatrix of Sf f seg matrices corresponding to trees T1, T3, T8 f seg matrix Submatrix of Sf The set of all (I; The submatrix S augmented by a unit matrix in the leading positioA ‘ 1’ S22 Submatrices of Si Submatrices of S8 subset of f seg matrix of a complete graph corresponding to a star tree viii p. A V 4 erR>fi>Ow< Description Transformation matrix Maximum order trees of graph Maximum order star tree coefficient Union of graphs Unitary matrix Jth column of V Vector Variable Known value of Xij Vector Diagonal matrix with entries of t l Diagonal matrix of eigenvalues Eigenvalue Diagonal matrix Function Submatrix of order (val, n) of S; Belongs to or is an element of ix I. INTRODUCTION AND ANALYSIS 1.0 Introduction In the last few years there has been an accelerated interest in time domain modeling of linear physical systems (1’2’3’h’5). Mathematically, these models are systems of first derivative-explicit differential equations d fix ‘ AK 1.000 where X is a vector, sometimes referred to as the state vector, and A is a real matrix. Two questions now arise: 1. Under what conditions can the matrix A of Eq. 1.0.0 be realized by a linear physical system? and 2. If A is realizable as a linear physical system, what are the element values and their interconnection pattern? These questions are a generalized form of the classical synthesis problem. However, the concept of realizing a real time model of a system is strikingly different from the classical concepts of systems synthesis whereby driving point impedances, admittances or transfer functions are realized (6’7’8’9). In Section 1.1 a complete time domain analysis of a RLC system is given and the associated matrix A of this system.is introduced. Some general pr0perties of associated matrices are also derived. In Chapter II the class of graphs considered is restricted to real linear bielement systems, that is, systems composed of g-elements (10) and lossey c- or 1-elements (10). Kbenig, Tbkad and Bacon have already considered the synthesis of LC graphs from the state model (11). Real linear bielement systems, hereafter referred to specifically as RC and RL graphs, are classified by the subgraph of the system from which the formulation tree is selected. Class 1 graphs are shown to be reducible to a canonical form. The associated matrices of a class 1 graph are then shown to be interrelated by a similarity transformation. In Chapter III the necessary and sufficient conditions for realizing A of Eq. 1.0.0 as a real linear bielement system are given. Three techniques are developed for decomposing A into a bisymmetric form, that is, the product of two symmetric matrices. A test is also developed to determine if one of these symmetric matrices is diagonal. For matrices that are realizable, a method is given for determining element values and the f seg matrix of the class 1 graph to be synthesized. From this information a graph is constructed. Necessary and sufficient conditions are also given on the bisymmetric form of A to guarantee that the synthesized graph will have no negative elements. In Chapter IV the synthesis method is described in detail and flow charts are developed to indicate the Operations in the realization of an A matrix as a real linear bielement system. Examples of the synthesis method for both RC and RL graphs are also given. 1.1 Time Domain Analysis The class of graphs considered is restricted as follows: 1. All components of the graph are to be g-elements, c-elements or l-elements. 2. The graph contains no drivers. 3. All initial conditions of the element variables are assumed to be zero. The time domain analysis of a less restrictive class of graphs has been (2) and others (1’3’h’5). The results pertinent to this dissertation follow. rigorously carried out by Brown As a direct consequence of Theorem A.l the following definition is made. Definition 1.1.0: A tree T of a connected graph G is said to be a fundamental tree if 1. As many c-elements as possible are branches of T, and 2. As many l-elements as possible are chords of T. (10) Lemma 1.1.0: The f circuit and f seg matrices corresponding to any fundamental tree T of a connected RLC graph G are FB 0 O I O O1 VI 0 O S S S ‘1 ll ll 12 I3 Bf = 321 322 o o I o , sf = o I o o 822 823 1.1.0 B B B O O I O 31 32 33 J O 533 where the columns of the unit matrices I of Bf correspond respectively to the c-, g-, and 1-elements of the cotree and the columns of the unit matrices I of Sf correspond respectively to the c-, g-, and l-elements of the tree. Proof: Follows directly from Theorem A.2. 1 Definition 1.1.1: The branch (chord) 1': g-, and c-element matrices 2 of a connected graph G are the diagonal element value matrices Ll’ G1, Cl (L2, G2, C2) where the subscript l (2) indicates the elements are branches (chords) of a tree (cotree). Lemma 1.1.1: Corresponding to any fundamental tree T of any connected RLC graph G, there exists a system of equations ggx = AX such that A = - (01+ slicesil)"l 0 0 S13 + o (L2+ Sé3LlS33)-l 'Si3 0 512(951+ SéeGils22)-lSi2 '312G2352(G1+ S22G28é2 )-ls23 1 1 1 , . . -1 -l _ t t v I 1 S23 (01* S22G2522) S22G2512 S23(G1+ 522G2822) S23 where 1. G1, Ll’ Cl Definition 1.1.2 respectively. 2. and B for i,J = 1,2,3 are given in Lemma 1.1.1. 313 in 3. The prime and -1 superscript indicate the transpose and inverse of the and G2, L2, C2 are branch element and chord element matrices of indicated submatrix respectively. Proof: The lemma results directly from Eq. 9 of reference 2. l. The matrices B and S of Lemma 1.1.0 are not necessarily in the same ij 13 positions as the B13 and S13 of Theorem A.2. 2. See Eq. 2 of reference 2. where the columns of the unit matrices I of Bf correspond respectively to the c-, g-, and l-elements of the cotree and the columns of the unit matrices I of Sf correspond respectively to the c-, g-, and l-elements of the tree. Proof: Follows directly from Theorem.A.2. 1 Definition 1.1.1: The branch (chord) 1-, g-, and c-element matrices 2 of a connected graph G are the diagonal element value matrices Ll’ G1, Cl (L2, G2, C2) where the subscript l (2) indicates the elements are branches (chords) of a tree (cotree). Lemma 1.1.1: Corresponding to any fundamental tree T of any connected RLC graph G, there exists a system of equations —x-Ax such that A = - (01+ SllC2Sil)"l O 0 513 + 0 (L2+ Sé3Lls33)’l ‘Si3 o 812(G;l+ Sé2Gl1522)-lsi2 '512G28é2(G1+ S22G25é2 )-1523 1 1 l - Sé3 (Gl+ S22G28é2)-1322G23i2 Sé3(G1+ SeeGesée)-1523 , O . where 1. G1, Ll’ Cl and G2, L2, C2 are branch element and chord element matrices of Definition 1.1.2 respectively. 2. Sid and 313 for i,J = 1,2,3 are given in Lemma 1.1.1. 3. The prime and -l superscript indicate the transpose and inverse of the indicated submatrix respectively. Proof: The lemma results directly from Eq. 9 of reference 2. l. The matrices B and S of Lemma 1.1.0 are not necessarily in the same 13 13 positions as the B and S of Theorem A.2. 13 13 2. See Eq. 2 of reference 2. Definition 1.1.2: The matrix A given by Eq. 1.1.1 is the associated matrix of the connected RLC graph G. Definition 1.1.3: Let T‘be any tree of a graph G. If the associated matrix A corresponding to the tree T exists, then T is said to be a maximum order tree. Corollary 1.1.1: Every fundamental tree is a maximum order tree. Proof: Follows directly from Lemma 1.1.1. From Lemma 1.1.1 it is convenient to introduce the following notation. Let -1 c o R R o s A = _ -1 11 12 + , 13 1.1.2 I I o L R12 R22 -813 o where — ' C ’ C1+ S11% 11’ L = L + s' L s 2 33 1 33’ -1 , -1 -1 , R R11 R12 S12(G2 + S22G1 322) S12 - B -1 -! l 1 R21 R22 S23(61+ 522G2322) S2292512 1'1°3 ‘ ' -1 _ c I S126252.2(G1+ 822G2522) S23 -1 ' S23(91+ $22G25é2) S23 Definition 1.1.h: The C matrix, L matrix, and R matrix of a connected RLC graph are defined by Eq. 1.1.3. Lemma 1.1.2: The associated matrices corresponding to the fundamental trees of bielement type connected graphs are: 1. RC Graphs ARC = ”c-1R11 2. RL Graphs ARL ‘ 'L-lR 22 3. LC Graphs -1 ' O L --S13 0 where C, L, Rll and R22 are given in Eq. 1.1.3 and S is given in Eq. 1.1.0° 13 Proof: 1., 2., and 3. are obtained from Lemma 1.1.1 by allowing the appropriate S terms of Lemma 1.1.0 to be null. 13 Lemma 1.1.3: Let D1 and D2 be diagonal matrices of order n with real positive diagonal entries. Let Si (12) be any conformable matrix, then D + S .D 83. j 1 1J 2 13 is positive definite Proof: Consider the matrix identity I ' - i . l Dl+ 3131328ij - [I 513] dlag (D1, D2) [8,3] 1.1.; By Theorem A.3, diag (Dl’DE) is positive definite. Since [I 813] is of maximum rank, the conclusion follows from Theorem A.A. Theorem 1.1.0: If the branch and chord element matrices Cl’ C2, L1’ L2, G1 and G2 have positive diagonal entries then -1 -1 . 1. (01+ s c s' ), (12+s' L s ), (02 + s: G see) and (sl+s Gls~0) are 11 2 ll 33 l 33 22 l 22 2 22 positive definite, and -1 ' -l -l , . . . . . 2. 812(G2 + S22Gl 822) 812 18 peeitive sem1defin1te. Proof: Part 1. follows directly from Lemma 1.1.3. By Theorem A.5., (G;l+sé2GilSE2)-l is positive definite. Part 2. of the theorem now follows from Theorem A.h. . . ._ 1 ml, , xul (a 12 18 of maX1mun rank, then D12(G2 + 5216 S , Corollary 1.1.0: If S J l 23 is positive definite. Proof: By Theorems 1.1.1 and A.5 (351+ S Gl 8,2)wl is positive definite. The conclusion follows from Theorem A.h. (10) l 2 P1 and P2 respectively, then A = diag (Al, A2) is the associated matrix of a Theorem 1.1.1: If A and A are the associated matrices of the parts separable RLC graph G obtained by uniting P and P2 at only one vertex. 1 Proof: From Eq. 1.1.2 for some maximum order tree T of P1 1 1 C'1 o R R o 5 A1 = - o L'1 RIl R12 + -s' 013 1.1.5 12 22 13 and for some maximum order tree T2 of P2 4:71 * «x- * A2 = - C 0.1 R 11 R 12 + O 813 1.1.6 0 L R*i2 R*22 -S*'i3 0 where C, L and [Rig] are the C matrix, L matrix and R matrix of P1 and C*, L* and. [R*iJ] are the C matrix, L matrix and R matrix of P2. 813 and 8*13 are subsets of the f seg matrices of P1 and P2 respectively. Consider uniting P1 and P2 at one vertex. TlUT2 is a maximum order tree of P1UP2' Correspondingly from Eq. 1.1.2 the associated matrix is ”5'1 -1 (:> C' r ”R11 0 R12 0 I [-0 0 S13 0 ‘ A = C* -1 0 R*ll O R*12 0 0 0 3*13 L -1 Ri2 0 R22 0 -Si3 0 0 0 L O L* ‘50 R*i2 o R*22_ _o -s*l'3o o d 1.1.7 c"1 -1 (:> R11 R12 0 o 0 S13 0 <3 7 A = L -1 Ri2 R22 0 '813 o o o c* -1 o o R*ll R*12 o o 0 3*13 _ O L* _ . go 0 R432 R*22‘ _o o 'S*1'3 o _ 1.1.8 From Eqs. 1.1.5 and 1.1.6, Eq. 1.1.8 is recognized as A = Diag (Al, A2) which completes the proof. II. CHARACTERIZATION OF REAL LINEAR BIELEMENT SYSTEMS 2.0 Introduction In this chapter the problem of characterizing time domain models of real linear bielement systems is considered.i In Section 2.1, the complete graph (12) (13) and the star tree are introduced. In Section 2.2 all connected real linear bielement systems are classified by the subgraph of the system from.which the formulation tree must be selected. In Section 2.3 the preperties of class 1 systems are developed. These systems are shown to reduce to a canonical form and all of the associated matrices of a graph are related to the canonical associated matrix by similarity transformations. The entries of the C, L, and R matrices are also formulated for the canonical system graph of class 1. 2.1 The Complete Graph Definition 2.1.0: A cgmplete graphl Qn+1 is a n+1 vertex graph such that there is one and only one element between every pair of vertices. See Fig. 2.1.0. The elements of a complete graph Qn+1 will be designated by E in general, 13 or specifically as G for a g-element complete graph, CiJ for a c-element 13 complete graph, and L for a 1-e1ement complete graph, where 32:1 for i,j = 13 1,2,...,n. For i ¥ 3, the element subscript ij implies the element is incident to vertices i and j and is oriented from vertex i to J. For i = J, E11 is defined to be the element incident to vertices i and n+1, with the orientation toward vertex n+1. Vertex n+1 is referred to as the "reference node". Furthermore, if a complete graph is composed entirely of g-elements (or c-elements, or 1-elements) it will be designated by the superscript g (or c, or 1). That is, Q§+1 is a complete graph of n+1 vertices and is composed entirely of g-elements G ., where 323i, for i, J = 1,2,...,n. iJ Theorem 2.1.0: The number of elements e in a complete graph of v vertices is mi)- 2.1.0 e: 2 <18). 1. This same definition was used by Brown and Reed 7 Proof: By induction on v. Let v = 2. The conclusion follows from Eq. 2.1.0 and Def. 2.1.0. Assume the theorem is true for v = n, for which the number of elements en is - EAEZLA' 2.1.1 en — 2 Now let v = n+1. 2.1.2 The number of elements en+l’ by definition 2.1.0, will be the number of elements in the case where v = n plus n new elements, one each from the n vertices to the n+1 vertex. Hence, en+1 = en + n, 2.1.3 or from Eq. 2.1.1 n+1 2 2 But from Eq. 2.1.2 n = v-l. Therefore, Eq. 2.1.h becomes __ V(V-l_l n+1 _ 2 ° 0 Hence, the theorem follows by induction. Property 2.1.0: Let Qm+l be a complete graph of m+l vertices. The f seg matrix corresponding to any star tree of Cm is +1 fl ‘ Y P 9 our E,r C . T . 0.. L 000 E E11 E19 2.n33 ... ITmn L12 L13 IUJ+ ° Lflnl .33 I24 L2‘) 2m inwl m Pl 0L 0 so. 0 l l 1 cool 0 O 0 see 0 00. n O l O .0. O “l A) O .000 1 1 1. 0.0 l 000 I“ O O 1 ... O O -l O ...O -l O O ... O ... W S = 3.1.5 O O O 000 l O O O ...-l O O 0 .00‘1 see”: - d where the column corresponds to the element of Qm 1 listed above th t column. Property 2.1.1: Let Sf be given b Eq. 2.1.5, then H W ' = [e 13] =8f diao ( iJ.) Sf 1. v m+1 Figure 2.1.0 Complete graph Q;+1 of e elements with m+1 vertices. —_-- I/I’ \\\\ 9 G. \ \ e ‘ \ \ \. G E 0 E E22 E11 Emm 1O vm+l Figure 2.1.1 Star tree TB of m+l vertices. 10 where diag (E13) e diag (E11E22E33...EmmEl2El3Elu...ElmE23E2uE2S...E2m...Em_l m) then_ €1J=eji==EiJfOTI>J 131,2000, m‘l m J: 2,3,..0’ m 2.106 en: E Eik’ i=1,2,...,m k=l where Eik = Elsi for i>k. 2.2 The Classification of Real Linear Bielement Systems. From Section 1.1, all RLC systems are characterized by their associated matrices. The rank of the associated matrix, by Eq. 1.1.1, determines the number of c~elements in the tree and the number of leelements in the cotree. Therefore, the rank of the associated matrix gives an indication as to the number of vertices of the graph and the composition of its tree and cotree. Since the reactive elements of a graph are assumed to be real, there is always a finite resistance or conductance associated with each reactive element, and hence there are at least as many g-elements as reactive elements in a given system graph. In the following,real linear bielement systems having associated matrices of order n are classified by the form of the subgraph from which the maximum order tree is selected. RC Graphs Let A or order n be the associated matrix of a connected RC graph G = GC U G8, where Gc and G8 are the subgraphs of e- and goelements of G respectively. From Eq. 1.1.1, there are n c-elements in the tree of G. Suppose the tree of G is composed entirely of caelements, then GC is connected and has v = n+1 vertices (10)° Suppose now that the tree contains g-elements such that GC is composed of two disjoint but individually connected subgraphs, then the number of vertices of Gc is v = n+2 (10). Suppose now the tree contains g-elements such that GC is composed of three disjoint but individually connected subgraphs, then the number of vertices Gc is v = n+3. This partitioning of Gc can be continued until Gc is composed of n parts. each of which is an individual c-element. The number of vertices in this case being v = 2n. This argument constitutes the proof of the following lemma. 11 Lemma 2.2.0: Let G a GC U‘G8 be a connected graph composed of the c-element subgraph Gc and the g—element subgraph G8. If G has an associated matrix of order n then the number of vertices of Gc and the form of Gc are characterized as follows: # of vertices Class of Gc ' Form of G 1 n+1 <::) C Gc is connected. c c c c 2 n+2 (:;> (:2) . G = l U G2 where G1 . . . . and G: are individually . . connected. 1 l i . n 2n 01].? CzZToooooCnnTo G - Cl]. U 0220.0U Cnn RL Graphs Let A.of order n be the associated matrix of a connected RL graph G = G1 U Gg where G1 and G8 are the subgraphs of 1- and g-elements of G respectively. From Eq. 1.1.1, there are n l-elements in the cotree of G. Suppose the tree of G is composed entirely of g-elements, then G8 is connected. Let the number of vertices of G1 be v. Suppose further that G1 is a complete graph. The complete graph with the least number of vertices having n elements is found by solving Eq. 2.1.0 for v. Therefore, ' l + V l + 8n. V = 2 2.200 In general, the solution of Eq. 2.3.0 is a real number r*. However, since v is the number of vertices, r* must be rounded off to the next largest integer r. The integer r, then, is the smallest number of vertices the subgraph G1 can have if A is to be of order n. The largest number of vertices of G1 is v = 2n corresponding to each l-element of the cotree being isolated from one another by g-elements. Therefore, the bounds on the number of vertices of G1 are 12 I‘S;\JS; 2(n + p) This argument constitutes the proof of the following lemma. 1 3' Lemma 2.2.1: Let G = G U GL be a connected graph composed of the l l-element subgraph G and the g-element subgraph Gg. If G has an associated l matrix of order n then the form of G6 and the bounds on the vertices of G are given as follows: ~# of vertices Class of Ge Form of Gg min max 1 r.g; vs; 2n an> : Ggis connected. . S G S 8 S 8 ’3 ° ... 3 2 1 g v< 2n+2 G2 . G - Gl U G2 where Gl and G2 are individually connected. q r 8 . 8 _ S 8 .8 8 3 r g VS 2n+h @ GD . G — Gl U G2 U C3 where Gl’ . . G% and 0% are individually . . connected. If; I f,» O, ,. 5,; .- p r g vg2(n+p) {15) G; ..... G; : G{3 2 G3’ U G2” . .U G; where (Igg) GESQ 0 0G 2 are individually '60? connected. 2.3 Characterization of Class 1 Systems. From Section 2.2, real linear bielement systems whose associated matrices of order n are classified by the form of the subgraph from which the maximum order tree is selected as classes 1, 2, ..., p, ... In this section, systems of class 1 are investigated and their characteristics developed in detail. l3 RC Graphs .r g c 8 c Lemma 2.3.0. Let Pp+l Gn+1 U Pp+l be a part such that Gn+1 is a connected c-element graph of n+1 vertices and Pg+l is a g-element part of c n+1 c 1. there exists a star tree TB of Gn+ p+1 vertices where G and Pg+l are united at p+1 vertices, ns:p. Then, 1 which is a subtree of a maximum order tree of Pp+1’ and 2. the associated matrix is 4 - _ -1 -1 ; -1 ]-1 , or A 4 c'lR -c'1s G s' r — 2322:: Select any vertex of Gfi+l and label it n+1. Label the remaining - vertices 1, 2, ..., n.» Consider the star representation T8 of the n+1 vertices of G241 given by the c-elements between vertices 1 and n+1, 2 and n+1, ..., n and n+1. Since G2+1 is connected, at least one of the c-elements, say 011’ of T8 is non-zero- .Furthermore, since Gn+1 is connected, the maximum number of c-elements in any tree of PP+l is n. T8 has n c-elements. Let the tree T31 of Pp+1 be composedof TB and T1 where T1 is a subgraph of P311' T81 is acceptable as a formulation tree by Def. 1.1.3 if only the associated matrix corresponding to TSi exists. The associated matrix corresponding to any fundamental tree by Lemma 1.1.2 is . A a -0'1R11 = - [C1 + 511C2Sii] -1812:[G£l +,Sézcilsé2] 'lsiz- 2.3.0 Since some of the elements of C can be zero, it is only necessary to show 1 that C"1 exists. By allowing the appropriate cgelements of the complete , graph Q:+l to be zero, then G:+l = Q:+1' Correspondingly, the subset S11 0 the f seg matrix of Pp+l is given by Eq. 2.1.5 for m a n. C is nonsingular by Theorem A.6 if only C is not permutable into diag (311’ K22) where K11 is a q x q matrix and K22 is a n - q x n - q matrix. Assume C is permutable into f this form. Then from Property 2.1.1, all c-elements between the vertices 1,2,..., q and q+l, q+2,..., n are zero. This is a contradiction since 63+} is connected, except if these vertices are connected through vertex n+1. If~ 1h the vertices l,2,..., q are connected through n+1 to q+1, q+2, ..., n, then K11 and K22 are to be examined individually for singularity. Applying Theorem A.6 to K11 and K22 and repeating the above argument, C is non- singular. Hence the associated matrix corresponding to Tsi exists and TS is a subtree of a maximum order tree which proves 1. of the conclusion. 2. of the conclusion follows directly from Lemma 1.1.2. Lemma 2.3.1: Consider the system of linear, nonhomogeneous, algebraic equations t.1d,1 =8... for i=l,2,eoe’ 1’1 lxi 11C 1.1. x. l . LI‘15 2.3.1 =a,,. fori. 4 "' '3. ‘ a '- I" u 6nd hr 1 MwVL ta; sin. isscCiatec matiix. rs K“ " -C‘ — ,7 ’ ' 1 un+l 11 aLd only if Gp+l Definition 2.3.1: The graph G0+1 is reduC1ble to Gn+l for p:»n if the graphs Gp+1 and Gn+1 are equ1valcnt. Corollary 2.3.0: Every part Pp+l of a RC graph of class 1 having a . i Q g ‘X‘ c-elementn sub ra h of n+1 vertices can be TCHUCCd to a dart P = Q - * Q g ‘p i n+1 Qn+1 n+1, . c 8* . . nsgp, where the complete graphs Qn4l and Qn+l are united at n+1 vertices. Proof: From Lemma 2.2.0, class 1 graphs satisfy the hypothesis of Theorem 2.3.0 and hence are reducible to Pn+1' Some of the elements of the complete “ g* and Q may be xero. n c rsnhs Q g a‘ Q ‘n +1 +1 Definition 2.3.2: A graph Pn+ - QC U Qg +1 _ Kn+l n+1 n+1 vertices and where Qn+l has a connected subgraph compos-d of non-zero 1 is said to be a canonical RC graph of class 1 where the two complete graphs are united at if and only if Pn c-elements incident to all n+1 vertices. The associated matrix corresponding to any maximum order star tree TS Of Pn+1 is said to be the canonical associated matrix of a RC graph of class 1. I -.. ’3 . \ C‘ _. ‘ f‘ —- C‘ ' '3 1 6) one: 7 V p“ Theoiem 2.,.1. Let us _ [5111 3012] - [I all! 81;]bc tat f seg matilX corresponding to a maximum order star tree TS of a canonical RC graph Gn+1 Of class 1. Then the canonical associated matrix of Gn+l is . ~l T A —- -C 31]. {uxfii that q 1 ‘ , C O I 1 : . . : C = . , 1. L LclJJ SIllCSUIll [I 811] l ' 2 3 7 O CO Slj ‘12“4' 1 : C)-.firr :1 C‘« 000 (1‘1 : (3":10. 000 \1‘ " » oooQC “ltle L1 i“° (“11’ 22’ ’Cnn) ‘“ C2 1CD (Cl2’cl3, ’ in’“2«’ ' 2n’ ) are the branch and chord c-element matrices respectively. 9. : a. —__- C“ 2. 1'8 1 R11 [glJ] s qu 2 3 where G2 = diag (Gll’G23"'"Gnn’G12’G13""’Gln’°'°’G -1 n) is the chord g-element matrix. l7 3. c = -C 13 13 for 1;; and i,j=1,2,...n 311 = 11 n 2.3.9 o = X C 11 3:1 13 ‘ fOI' i=l,2,oeen ‘ 2”: g = G . ii 3:1 13 Proof: 1. and 2. follow directly from Lemma 1.1.2. SIll and $12 of the hypothesis.are given by Eq. 2.1.5 where m=n. 3. follows from 1. and 2. and Property 2.1.1. Lemma 2.3.2: Let Si’ 83,... be the f seg matrices corresponding to the maximum order trees T1, T3,... respectively, of a connected graph G, then there exists nonsingular matrices (lid and P31 such that = ‘ s P 2. .10 (111 1 11’ 3 where 013:0;1ati and at: and ati are submatrices of the incidence matrix whose celumns correspond to the elements of the trees 'I'J (in) which rearranges the columns of SJ to have and T1, respectively, ~and PJi is a permutation matrix the same element ordering as the columns 81' Proof: Follows directly from Theorem.A.17. Theorem 2.3.2: The associated matrix of every part Ep+l of a separable RC graph of class 1 is similar to the canonical associated matrix of some canonical RC graph-of class 1 and conversely. Proof: By Corollary 2. 3. O,P p+l can be reduced to PM =Qn+1 U Qn+1 where Qi+1 and Qn*l are complete graphs united at n+1 vertices. Let AJ be the associated matrix corresponding to some maximum order tree T of P J n+l' By Lemma 2.3.0, Pn+1 has a maximum order star tree Ts' Let S and Sa be the J f seg matrices corresponding to the trees TJ and T8 respectively. By Lemma. 2.3.2, ”(193 j 38' ‘ 2.3.11 Let SS and SJ be partitioned such that the columns of the 1,1 submatrix correspond to the c-elements and the columns of the 1,2 submatrix correspond 18 to the g-elements of Pn+1° Eq. 2.3.11 becomes P11 0 Se: [Sell S1112] = 05,3[8311 8312] : 2.3.12 0 P22 where P s is partitioned to conform to the partitioning of S rearranges . P J . . J 11 the columns of 8311 corresponding to c-elements such that the leading columns 0? Sjllpll $312 corresponding to g-elements. Since for a class 1 RC graph there are no correspond to the c-elements of Ts' P22 rearranges the columns of g-elements in the tree Ts’ then P22=I. Let the branch and chord c-element matrices corresponding to the tree T be written J c =diag (01,02). 2.3.13 J Then the diagonal branch and chord c-element matrix CB corresponding to the tree TS is the same matrix as C with the elements-rearranged on the J diagonal. In fact, C = P' 2.3.1h s llcjpll' Since the g-element chord matrix G is not rearranged, then G is the same for 2 2 both trees T and T8. The associated matrix of Pn+1 corresponding to the tree J TS by Lemma 2.3.0 is A = -(s c s )‘ls G 5' 2.3.15 ' s sll s all 312 2 812. _ substituting the relations of Eqs. 2.3.12 and 2.3.1h into Eq. 2.3.15 gives -1 __ _ I I I I I I As " (asJSJllPllPllCJPllPllSjllasj) a335312G25312asJ’ 2'3'16 Since Pllpll = I and by taking the inverse of a product of square matrices, Eq. 2.3.16 becomes I'1 I '1 I I A8 = '03,; (3311035311) 8312G28312 033‘ 2.3.17 The associated matrix corresponding to the tree TJ by Lemma 2.3.0 is I ’1 I AJ = '(3311033311) 8312628312. 2.3.18 Therefore Eq. 2.3.17 is written as I -1 ! A8 = (133 A3 SJ. 2.3.19 By Definition A.2, A is similar to As which proves the theorem. J l9 Converse: The converse follows directly by solving Eq. 2.3.19 for A3' Corollary 2.3.2.0: The associated matrices Al’A2"°"AJ”"Ak"" of a part P5 +1 corresponding to the trees Tl,T2,...,T graph are similar. J,...Tk,... of a class 1 RC Proof: By Theorem 2.3.2,?the associated matrices AJ and AR are Similar to the associated matrix A8 corresponding to the star tree T8 which exists by Lemma 2.3.0. Therefore, from Eq. 2.3.19 - I' I AS - 0le Ajagj= 018k Akask 2.3.20 for all j and k. Solving Eq. 2.3.20 for A3 in terms of Ak gives awash: “1.0.1.0531 2.3.21 Therefore, by letting 03k: 03308121 23°22 Eq. 2.3.21 becomes -1 _ i I A3 _ ijikajk , 2.3.23 for all 3 and k, and by Def. A.2, Ak is similar to AJ' Corollary 2.3.2.1: The associated matrix of a connected RC graph G of class 1 is similar to the canonical associated matrix of some canoniCal RC . graph of class 1 and conversely. Proof: From Theorem 2.3.2, for each separable part P1, i=l,2,...m, =()sjA 361% ° - ' 2.3.2h By Theorem 1.1.1, the associated matrix of G is - l - _ _ - A . J .20 3 SJ . 83" 2.3.25 o'm o -m own 0 -m L A3 (183 As Cl 2 ..4 i- } — L ..1 — ..a l where diag (As’As RC graphs of class 1 at one vertex and hence isma canonical RC graph of class 1. a: ' A: ‘ 'a: JO? 0 A: O 302 ~ 0 ‘ ,...,A:) is the associated matrix of.a union of m-canonica1 Converse: The converse follows directly by solving Eq. 2.3.25 for I 2 m (118.8 (A8 ’AS’ 0 e 0 ,AS) 0 20 RL Graphs Lemma 2.3.2: Let P _ = G8 U G1 be a part such that eg is a connected p+l p+1 y. (10) P+l gnelement graph of p+1 vertices and Gv is a forrest of leelement graphs 1 . . having v vertices, where G8 and Gv are united at v vertices, vsgp. Then, p+1 1. there exists a star tree TS of G§+1 which is a maximum order tree of Pp+l’ and l G g __"I 9 2. the assoc1ated matrix of Pp+l is A _ L 823(Gl + 822G2822 8 p+1 vertices l, 2, ..., p. Consider the star representation T8 of the p+l vertices of G: -1 ) 523. Proof: Select any vertex of G and label it p+1. Label the remaining +1 given by the gmelements between vertices l and p+1, 2 and S p+1 , of T is nonezero. Furthermore, by the connectedness of G is p . Ts has p gaelements. p+l, ..., p and p+1. Since G is connected, at least one of the g-elements, say G g , the 1 maximum number of geelements in any tree of Pp+l Ts is an acceptable formulation tree by Def. 1.1.3 if only the associated matrix corresponding to Ts exists. The associated matrix corresponding to T8 by Lemma 1.1.2 is 1 ___"I A — L 82 G S 3(G1 + D22 2 22 Since some of the gnelements of TS can be zero, it is only necessary to show that (G1 + 822G2Ség) is nonsingular. By allowing the appropriate . a S S _ E guelements of the complete g1aph Qp+1 pel — Qp+l' of the f seg matrix of Pp_ is given by to be zero, then G Correspondingly, the subset S 1 . ch- 22 Eq. 2.1.5 for map. G1 + 82202822 18 non51ngular by Theorem A.6 if only it cannot be permuted into diag (K11, K29) where K - e . ’ . G - . '. “2 ' nt-b ".. ;hi- K22 is a p q x p q matrix. Assume l + S22G2822 1s permc a le info t 3 form. Then from Property 2.1.1, all guelements between the verti es 1. 2, 11 is a q x q matrix and ..., q and q+1, q+2, ..., p are zero. This is a contradiction since 8 Gp+l p+1. If the vertices l, 2, ..., q and q+l, q+2, ..., p are connected through p+l, then Kll and K22 Applying Theorem A.6 to K11 and K22 and repeating the above argument, is connected, except if these vertices are connected through vertex are to be examined individually for singularity. G1 + S22G2S22 is nonsingular. Hence, the associated matrix corresponding to TS exist, and hence, Ta is a maximum order tree of Pp+l which prove part 1. of the lemma. Part 2. of the lemma follows from Lemma 1.1.2. 21 be given by Eq. 2.1.5, then S S' is nonsingular. Lemma 2.3.3: Let S f f f Proof: From Eq. 2.1.5, P _ m -1 o o o -1 "1 m o O t- Sfo . . . . 2'3'26 . . -1 -1 o o o -1 m is a m x m matrix. By Theorem A.6, S Sf is nonsingular. f 1&1 K12 Lemma 2.3.h: Let K = , where K11 and K22 are square submatrices, I . K12 be a positive definite matrix, then K11 and K22 are positive definite. Proof: Since K is positive definite, then K11 Ki2 X1 [Xi Xé >0 2.3.27 "12 K22 X2 for all vectors X = [ ' Xé]'. Let X = 0, it then follows from Eq. 2.3.27 that 2 Xilglxl> 0 2.3.28 for all xlalo. By Definition A.l, K11 is positive definite. Similarly, by letting X =0, it then follows from Eq. 2.3.27, that 1 X2x22x2> O 2' 3'29 for X2¥O. Hence, K is positive definite by Definition A.1 which proves the lemma. 22 Theorem 2.3.3: Let Pp+1 = G: +1 U G1 be the graph of Lemma 2.3.2. Then there exists a graph Pv obtained by uniting G1 with a complete g-element graph Q? *at v verticesv such that the associated matrices of PD +1 and P; are identical. Proof: Let P +1 1 g G1 Qv where Qp+l = Gp+l and Qv= v' Select T8 of Lemma 2. 3. 2 as the tree of Pp+l° be written as the union of two complete graphs Qp +1 and The f seg matrix by Lemma 1.1.0 is 22 S8 = [I 822 823] . 2.3.30 Since there are in general more g-elements than l-elements, S8 can be partitioned as follows I O S* S* _ v 22 23 SS “' , 2.3031 * O I 852 0 l where Iv corresponds to the branches of TS which are incident to Gv' The associated matrix corresponding to TS by Lemma 2.3.2 is _ -l _ _ -l , [ , ] -1 As ” ‘L R22 ‘ L S23 G1 + S22G2S22 523 2.3.32 K -1 1 ll Kl2 I ._ .. Let [G1 + 822G2822 ] — K — Ki K where Kll is a v x v matrix. 2 22 G1 + S22G28é2 is positive definite by Theorem 1.1.0. K is positive definite by Theorem A.5. Kll is positive definite by Lemma 2.3.h. Therefore Eq. 2.3.32 is written 8* _ -l _ -1 , K11 Ki2 23 AS _ -L R22 - -L [SS3 0] , 2.3.33 ' or K12 K22 O A = -L'lR = -L‘ls*'K s* 2 3 3n 3 22 23 11 23' ° ° Now construct the graph Pv of the theorem where G: is given and the elements * * of Q5 are to be calculated. Select the tree T; from Q5 such that T; is a subtree of T8. The f seg matrix of Pv by Lemma 1.1.1 is * _ * * SS .. [Iv 522 523], 2.3.35 where SS2 and 333 are identical to the submatrices of Eq. 2.3.31. The associated matrix corresponding to T; by Lemma 2.3.2 is -1 -1 -l * - - * = _ v * * *t , . . AS - L R22 L 553 [G1 + 522G5522] $33 2 3 36 Let Eqs. 2.3.3h and 2.3.36 be equated and then premultiplied by S§3L and pOStmultiplied by S*' which gives 23 -l * *' * *' = * *' * * *' * *'. . . S23523131523823 S23523 [G1 + S22G2322] S23323 2 3 37 SS3 is given by Eq. 2.1.5 and hence by Lemma 2.3.3, S§3S§é is nonsingular. Therefore, Eq. 2.3.37 is written as G* 0 I [I 322] l e Ki: 2.3.38 * I 0 G2 852 where K11 exists since Kll was shown to be positive definite. Eq. 2.3.38 can be written as Eq. 2.3.1 and hence satisfies the hypothesis of Lemma 2.3.1. Therefore, there exists a unique set of diagonal entries GiJ diag (Cf’ G5) such that the associated matrices of PP+1 and P; are identical, thus proving the theorem. Corollary 2. 3. 3: Every part PP +1 of a BL graph of class 1 having a * l-element subgraph of v vertices can be reduced to a part PV 2 Qv U Q3 v<:p+l, where the complete graphs Qv and Qv* are united at v vvertices. Proof: By Lemma 2.2.1, class 1 graphs satisfy the hypothesis of Theorem 2. 3. 3 and hence are reducible to Pv . Some of the elements of the complete graphs Q1 and Q? may be zero. Definition 2. 3 3 A graph Pv is said to be a canonical RL_graph of class 1 if and only if Pv 4Q U'Qv where vthe two complete graphs are united at v vertices and where Qv has a connected subgraph composed of non-zero g-elements incident to all v of the vertices. The associated matrix corresponding to any maximum order star tree of Pv is said to be the canonical associated matrix of a BL graph of class 1. I I Theorem 2.3.h: Let s8 = [:5122: 823] = [I 322. 323] be the f seg matrix corresponding to a maximum 8order star tree T8 of a canonical RL graph Pv of class 1. Then the canonical associated matrix of Pv is -1 As - -L R22 such that 1. L = L = diag (L11, L 2 ...,Ln 22’ n’ L12’ L13’ where L2 is the chord l-element matrix, = I I -1 _ g [ ] "l 2. R22 52 23 [8122 GS 5122] s23 - 823 gm $23 2.3.ho where G8 = diag (G1, 62), G respectively, and l and G2 are the branch and chord g-element matrices 3' siJ = -GiJ for i¥j, i,j,=l,2,...,n n 2.3.h1 811 = 4: G13 for i=l,2,...,n * cl 0 I -1 [I 822] o = Kll 2.3.38 * *1 G2 S22 -l where K11 be written as Eq. 2.3.1 and hence satisfies the hypothesis of Lemma 2. 3. l. * iJ diag (G1, G2) such that the associated matrices of PP+l and Pv are identical, thus proving exists since K11 was shown to be positive definite. Eq. 2.3.38 can Therefore, there exists a unique set of diagonal entries G* the theorem. Corollary 2. 3 3: Every part P? +1 of a BL graph of class 1 having a * l-element subgraph of v vertices can be reduced to a part Pv = Qv U Q5 v<:p+l, where the complete graphs Qv and Qv* are united at v vvertices. Proof: By Lemma 2.2.1, class 1 graphs satisfy the hypothesis of Theorem 2. 3 3 and hence are reducible to Pv . Some of the elements of the complete graphs Q1 and Q5 *may be zero. Definition 2. 3. 3: A graph Pv is said to be a canonical RL_graph of class 1 if and only if Pv QQ U'Qv where vthe two complete graphs are united at v vertices and where ng has a connected subgraph composed of non-zero g-elements incident to all v of the vertices. The associated matrix corresponding to any maximum order star tree of Pv is said to be the canonical associated matrix of a BL graph of class 1. l l o o : = I I Theorem 2 3 h Let sS [$122l $23] [ s 22. s 23] be the f seg matrix corresponding to a maximum8 order star tree T8 of a canonical RL graph Pv of class 1. Then the canonical associated matrix of Pv is -1 As - “L R22 such that l. L = L2 = diag (L11, L22, coo, Lnn, L12, 1113,000, Lln’ coo, Ln- 1 n) , 2-3-39 where L2 is the chord l-element matrix, -1 -l t l = l 2' R22 S23 [SI22 Gs SI22] S23 32 3[gi.j] S23 ‘ 2’3"“0 where G8 = diag (G1, G2), G1 and G2 are the branch and chord g—element matrices respectively, and 3' 81J = -Gij for i¥J, i,J,=l,2,...,n 2.3.hl n s11 = 2; G13 for i=l,2,...,n 2h where 6136 Gs' Proof: 1. and 2. follow directly from Lemma 1.1.2. 8122 and 823 of the hypothesis are given by Eq. 2.1.5 where m=n. 3. follows from 2. and Property 2.1.1. Theorem 2.3.5: The associated matrix of every part Pp+l of a separable RL graph of class 1 is identical to the canonical associated matrix of some canonical RL graph of class 1 and conversely. . l 3* 1 Proof. By Corollary 2.3.3 PP+l can be reduced to Pv = Qv U'Qv where Qv T— and Q5 are complete graphs united at v vertices. Let AJ be the associated J of P§. By Lemma 2.3.2, Pv has a maximum order star tree Ts' Let SJ and S8 be the f seg matrices matrix corresponding to some maximum order tree T corresponding to T and TS respectively. By Lemma 2.3.2, 38 = (lsjsJPJS. 2.3.u2 be partitioned such that the columns of the 1,1 submatrix J Let S8 and SJ correspond to the g-elements and the columns of the 1,2 submatrix correspond to the l-elements of Pv’ Eq. 2.3.h2 becomes P11 0 [5822 8823] = 08.1[8322 8323] ’ 2'3"” O P 22 where P s is partitioned to conform to the partitioning of S . P rearranges J J 11 the columns of 8322 corresponding to g-elements such that the leading columns of S correspond to the g-elements of Ts' P rearranges the columns of J22P11 22 $323 corresponding to l-elements. Since for a class 1 RL graph, there are no l-elements in Ts’ then P22=I. Let the branch and chord g-element matrices corresponding to T be written 3 G = diag (G1,G2). 2.3.hh 3 Then, the diagonal branch and chord g-element matrix G8 corresponding to the tree TS is the same matrix as GJ with the elements rearranged on the diagonal. In fact, .... I Gs ‘ PllGJPll' 2°3°h5 Since the l-element chord matrix L for both trees T8 and TJ tree T8 by Lemma 2.3.2 is 2 is not rearranged, then L2 is the same . The associated matrix of P; corresponding to the 25 _ -l , , -1 s - 4" Ss23 [SS22GSSS22] 8823' Substituting the relations of Eqs. 2.3.h3 and 2.3.h5 into Eq. 2.3.h6 gives A 2.3.h6 _ -1 l I t V ' ' -1 As " ”L 5323053 [ 0333322P11P11G3P11P11532203,3] 0333323 2'3'” Since PllPll = I and by taking the inverse of a product of square matrices, Eq. 2.3.h7 becomes A --L’ls' [5 GS' ]"ls I 231+8 B - 323 J22 J J22 323' ° ' By Lemma 2.3.2, the right hand side of Eq. 2.3.h8 is recognized as the associated matrix of the reduced graph Pv corresponding to the tree T Hence 3. As = A3 which proves the theorem. Converse: The converse follows directly from Eq. 2.3.h8. Corollary 2.3.5.0: The associated matrices Al, A2, ..., AJ’ ..., Ak, ... of a part Pp+1 corresponding to the maximum.order trees T1, T2, ..., T3, ..., T , ... of a class 1 RL graph are identical. ; .; k Proof: By Theorem 2.3.5, the associated matrices AJ and AR are identical to the associated matrix As corresponding to the star tree T8 which exists by Lemma 2.3.2. Hence, = A = . . A8 J Ak 2 3 h9 for all 3 and k, thus proving the corollary. Corollary 2.3.5.1: The associated matrix of a connected RL graph G of class 1 is identical to the canonical associated matrix of a canonical RL graph of class 1 and conversely. Proof: From Corollary 2.3.5.0 the associated matrix for each separable Partp, i=1, 2, ...,miS A3 = A8. 2.3.50 Hence, by Theorem 1.1.1, the associated matrix of G is P A: ' FA: _ A? O A: O A = o = 0 0 2 o 3 o 51 O A? O A: _ J _ J 25 _ -l , , -1 As“ L Ss23[ Ss22GsSs22] 5323' 2'3'L‘6 substituting the relations of Eqs. 2.3.u3 and 2. 3.h5 into Eq. 2.3.46 gives -1 1 3 ! A3: “L 153353230 [0335322P11Pi1GJP11P115322033] 09.33 J23 23'” Since PllPll = I and by taking the inverse of a product of square matrices, Eq. 2.3.h7 becomes A e-L'ls' [3 GS' ]'ls . 2.3.h8 8 J23 J22 J J22 J23 By Lemma 2.3.2, the right hand side of Eq. 2.3.h8 is recognized as the Hence associated matrix of the reduced graph Pv corresponding to the tree TJ' AB = AJ which proves the theorem. Converse: The converse follows directly from Eq. 2.3.h8. Corollary 2.3.5.0: The associated matrices Al, A2, ..., AJ’ ..., Ak’ ... of a part Pp+l corresponding to the maximum order trees T1,T2, ..., T3, ..., Tk’ ... of a class 1 RL graph are identical. ; .; Proof: By Theorem 2.3.5, the associated matrices AJ and AR are identical to the associated matrix AB corresponding to the star tree T8 which exists by Lemma 2.3.2. Hence, 8 for all J and k, thus proving the corollary. Corollary 2.3.5.1: The associated matrix of a connected RL graph G of class 1 is identical to the canonical associated matrix of a canonical RL graph of class 1 and conversely. Proof: From Corollary 2.3.5.0 the associated matrix for each separable ‘I"' Part-0P , i=1, 2, .00, 11118 AJ =AS. 203-50 Hence, by Theorem 1 l 1 the associated matrix of G is FA: - FA: _ A? O A2 O A = . e 3 . . 2.3.51 0 A. O A“ t 3i 8 26 l m where diag (A8, A:,... AS) is the associated matrix of a union of m canonical RL graphs of class 1 at one vertex and hence, is a canonical RL graph of class 1. Converse: The converse follows directly from Eq. 2.3.51 2.h Conclusion. Lemmas 2.2.0 and 2.2.1 classify all connected real linear bielement systems whose associated matrix is of order n. The classification is essentially a tabulation of all possible subgraphs from which the maximum order trees of the system graph are selected. In Section 2.3, system graphs of class 1 are considered. From physical considerations, the gmelement subgraphs of class 1 systems have at least as many vertices as the c- or l-element subgraphs. By Corollaries 2.3.0 and- 2.3.3 the g-element subgraphs are reduced to an equivalent subgraph which retains only the vertices of the reactive elements of the system. The reduction of the g-element subgraph is similar to the element elimination process of Brown and Tokad(15). Furthermore, the reduction could be accomplished by using the wye-delta transformation on the graph. Since all class 1 systems reduce to the same basic structure, Definitions 2.3.2 and 2.3.3 define this structure to be a canonical graph of class 1. The canonical graph is unique in that it always has a maximum order star tree. Corresponding to the maximum order star tree, the canonical associated matrix is defined. (16) By Lemma 2.3.2, there exists an equivalence relation between the f seg matrices of a graph. As a result of this equivalence, a similarity relation is derived for the associated matrices of a class 1 graph. Theorem 2.3.2 gives the similarity relationship for class 1 RC graphs. By Theorem 2.3.5 the similarity transformation for class 1 RL graphs reduces to the identity transformation. Therefore, the associated matrix of a BL graph is independent of the formulation tree. A description of the entries in the C matrix, L matrix and R matrix for canonical RC and RL graphs is given in Theorems 2.3.1 and 2.3.h. Matrices having similar properties to the C, L and R matrix have been previously (17) (18) considered by Cederbaum and Brown . The effect of changing the orientation of elements of the graph on the canonical associated matrix is readily calculated by the use of the similarity transformation of Theorems 2.3.2 and 2.3.5. It is postulated from the results of Section 2.3 that each of the other classes of system graphs is reducible to a canOnical graph. Correspondingly, a canonical associated matrix could be defined for each class and a similarity transformation between the associated matrices derived. Finally the entries of the C, L and R matrices of each canonical graph are to be described and tabulated. This tabulation would then give all possible forms of the associated matrices of a real linear bielement system. III. SYNTHESIS OF A CLASS OF REAL LINEAR BIELEMENT SYSTEMS 3.0 Introduction In this chapter, the necessary and sufficient conditions on a given matrix such that it is realizable as a class 1 real linear bielement system, hereafter referred to as a RC or RL graph, are developed. In Section 3.1 the conditions for the decomposition of a square matrix into the product of two symmetric matrices are given. Three techniques are developed for this decomposition. A test is also derived to determine if the given matrix can be decomposed as the product of a diagonal matrix and a symmetric matrix. The results of Section 3.1 are used to determine sufficient conditions for the synthesis of RC and RL graphs in Sections 3.2 and 3.3 respectively. The analysis of Section 1.1 imposes the necessary conditions for RC and RL graph synthesis. 3.1 Decomposition of a Square Matrix. From the time domain analysis of RC and RL systems of Section 1.1, the associated matrix is always written as the product of two symmetric matrices. Therefore, it is fundamental for synthesis that a given matrix be factorable into the product of two symmetric matrices. Theorem 3.1.0: If there are n real, distinct eigenvalues of the real matrix A, then A is factorable as A = -0- R 3.1.0 where C is positive definite and R is real symmetric. Proof: Since A is real and its eigenvalues Al’ A2, ..., A n are real, distinct, there exists a nonsingular real matrix P by Theorem A.16 such that A = 2’1 P 3.1.1 whereA: diag (Al, A2, ..., An). Let Eq. 3.1.1 be rewritten as follows A = P”l(P"lP')AP -_- (P'P)-lP'AP , 3.1.2 By letting 29 and R = -P'AP 3.1.11. then A is factorable as in Eq. 3.1.0. By Theorem A.7 C is positive definite. Since P andA are real, R is real. Also, since R = R', R is symmetric by definition. Theorem 3.1.1: Let the matrix equation ol f = C . g e + a = O fora,fl, j = 1,2,ooon [0‘3] [0“] [I33] [Cw] 3.1.5 where c.. = c.., g.. = g.. and where a..'s are known constants, be written as lJ Jl lJ Jl 13 2 . . . a system of n nonlinear algebraic equations f c . . = O for ‘13 ' = 1 2 ... n QIB(CXJ’g J) a) .9 J J ) 7 in n +n variables ccx., glgj. If A has real, distinct eigenvalues and if 2 Jacobian J with respect to any of the n variables does not vanish at some 2 point (e. , g. ), then there exists n unique equations ¢q-O. Therefore A is nonsingular by Theorem A.lS. Corollary 3.2.1: If the coefficient matrix A has real, distinct, negative, non-zero eigenvalues, then there exists a canonical RC graph with A as a canonical associated matrix such that A = -C-lR where C and R are positive definite. Proof: From Theorem 3.1.0, A is factorable as ~C-lR where C is positive definite.. From Eq. 3.1.A R = -P'AP = P'(-A)P. 3.2.7 Since all the eigenvalues are distinct and nonzero, [\is diagonal and nonsingular. Therefore, R is nonsingular since P is nonsingular. Since all of the eigenvalues are negative, then (:/\) is positive definite by Theorem A.3. Hence by Theorem A.h, R is positive definite. By Def. 3.1.0, A is bisymmetric. A is nonsingular since C and R are positive definite. Therefore from Theorem 3.2.1 the conclusion of the corollary follows. Corollary 3.2.1 imposes one condition on the coefficient matrix A such that it can be decomposed into the product of two positive definite matrices. Theorem 1.1.0 and Corollary 1.1.0 indicate that the C and the R matrix being positive definite is a necessary condition for the RC graph to have non- negative elements. Necessary and sufficient conditions for which a coefficient matrix is realizable as a canonical RC graph with non-negative elements is given in the following theorem. Theorem: 3.2.2: If and only is the coefficient matrix A =[:aij] order . -l n is bysymmetric such that [ aij] — - [Cid] [gij] where 36 l. c ‘<: 0 \\ 13 for i g j i, j = 1, 2, ..., n $1345; 0 2. cli>0 f0ri=l, 2’ 000,110 gii::> 0 n 3. 2cii> Iglcik for at least one i and n 2cii;;z Egacik for all other i. n 2gii> 2 g k for at least one i and k=1 1 n 2gii > kglgik for all other 3 . A O and such that neither [c. .] nor [g ] are permutable into where 13 13 o B A and B are square, then there exists a canonical RC graph Gn+1 with non~ negative elements for which A is a canonical associated matrix. 3322:: Sufficiency: From 1., 2., and 3. of the hypothesis and by_ Theorem 2.6 [cij] and [gij] are nonsingular. Therefore, A is nonsingular. By hypothesis, A is bisymmetric, and hence, from Theorem 3.2.1, there exists a canonical RC graph Gn+l'g The element values are calculated by writing Eq. 3.2.3 as a system of nL equations. This system of equations satisfies the hypothesis of Lemma 2.3.1 in such a way that all element values are non- negative. Necessity: Follows directly from Theorem 2.3.1. 3.3 Synthesis of RL Graphs. In the synthesis of RC graphs, it was determined that the order of the associated matrix uniquely gives the number of vertices for each class of graphs. This is not the case for the RL graph. The order of the associated matrix gives only the bounds on the number of vertices v of the l-element subgraph G: of the RL graph. However, since the g-element subgraph Cg of the RL graph can be reduced to have the same vertices as Ci, the bounds on the vertices are to be used in the synthesis of RL graphs. 37' Definition 3.3.0: Let the matrix 5; of order (v-l, v(v-l)/2) be given of Eq. 2.1.5, 'by Sf 53 = sf 3.3.0 'then 8V is defined to be the set of all matrices CT of order (v-l, n) :n V (zomposed of any n columns of S3 for v = r, r+1, ..., 2n and where r is the smallest positive integer such that r(r+l)/2 > n. Lemma 3.3.0: Sv n for v = r, r+1, ..., 2n of Def. 3.3.0 is the set of ) all.submatrices S23 of the f seg matrix as given in Theorem 2.3.h for all canonical RL graphs Gv having only n nonzero l-elements distributed on the v vertices for r g v< 2n where r is the smallest integer satisfying r(r+l)/2 2 n. Proof:1 Consider S; of Eq. 3.3.0. 8; = 823 of the canonical graph Gv of the hypothesis for all v(v-l)/2 l-elements nonzero. Since only n of the l-elements are nonzero, then S ‘is composed of n of the columns of 8;. But 23 8V n is the set of all matrices CT; composed of n columns from 8;. By Lemma ) 2.2.1, the number of vertices v is bounded by r and 2n. Therefore, the conclusion follows for all Gv where rg vg 2n. Lemma 3.3.1: Let R be a real symmetric matrix of order n. If , . Det (dvR UV) ,4 0 for some dve Sv,n then R is factorable into the triple product of Eq. 2.3.h0. Proof: Let R be equated to R2 of Eq. 2.3.AO. 2 R — s' s G S' '15 3 1 - 23[ 122 s 122] 23 3'3' Let S23 of Eq. 3.3.1 be equal to‘Sv of the hypothesis. This can always be done since by Lemma 3.3.0 Sv n is the set of all 823 for a canonical RL graph ’ . CV and since by Corollary 2.3.5.1 the associated matrix of the graph is independent of the formulation tree. Let Eq._3.3.1 be premultiplied by (1; and postmultiplied by'Cfé, Therefore ddev = 0’va [5122Gssi22] -10", 03' 3.3.2 By hypothesis, Det (cvacf;) g o, and hence Eq. 3.3.2 is solved as follows I I t 'l 1 SI22GsSI22 = CTrCIr [CTch7t] CTVCT§- 3-3-3 38 From Eq. 3.3.3, 8122GSSé2 is a real, symmetric matrix. Hence, by Theorem A.lO, there exists a unitary matrix V = [:v1 v2 ... VJ ...] where vJ is the 3th column of V such that v _ 1 3122088122 _ v uv 3.3.h where LL is a diagonal matrix. Let T be the transformation of Eq. 3.2.1. Therefore, ... ' ' $122 ‘ V T 3'3'5 where SI22 is a subset of the f seg matrix of a canonical RL graph as given in Theorem 2.3.h. Eq. 3.3.h is a system of linear nonhomogeneous algebraic equations which satisfy the hypothesis of Lemma 2.3.1. Hence R is factorable into the triple product of Eq. 2.3.h0. Theorem 3.3.0: If and only if the coefficient matrix A of order n is left quasisymmetricwhere A = -L-1R and such that Det (CffRCIG) ¥ 0 for some (j £8 then there exists a canonical RL graph G for which A is the v v,n v associated matrix. Proof: Sufficiency: By hypothesis A is left quasisymmetric, therefore factorable as -L-lR where L is diagonal and R is symmetric. By Lemma 3.3.1 R is factorable into the triple product of Eq. 2.3.h0. The f seg matrix 88 corresponding to a star tree T8 is given by Ss = [3122.523 ] 3°3‘6 I22 is given by Eq. 3.3.5 and 323 = 0’v of the hypothesis. The g-element values G13 are calculated as in the proof of Lemma 3.3.1. The l-element 'values are obtained directly by setting L a L2 of Eq. 2.3.39.‘ Hence by construction, there exists a canonical RL graph Gv for which A is the where S associated matrix. Necessity: By Theorem 2.3.h, A is left quasisymmetric. Let(j; = S23. This is always possible by Lemma 3.3.0. From Eq. 2.3.h0, calculate : __ l t Det (S23R22823) — Det ((7;R(j;). By Lemma 2.3.3, 823823 is nonsingular. Hence, Det (823R2Sé3) ¥ 0 which completes the proof. Theorem 3.3.1: If and only if the coefficient matrix A or order n is left quasisymmetric where A = -L-1R such that 39 l. Det (UVR UV) ,4 O for some (j/ve Sv,n 2. L is diagonal and positive definite, and 3. For [813] = O’vaflOlvRUQJO’vO/i gij < o for 1 {j gii :>() for all i and n 2gii 2 Z gik for all 1 k3]. ~ where i, j = l, 2, ..., n, then there exists a canonical RL graph Gv with r s; v*$; 2h having non-negative elements for which A is the associated matrix. Proof: Sufficiency: The hypothesis satisfies the conditions of Theorem 3.3.0, hence there exists a canonical RL graph Gv for which A is a canonical associated matrix. By Theorem A.3, the l-elements calculated from L are positive since L is diagonal and positive definite. All other 1-elements of the Gv are zego. The g-element values ij are calculated by writing Eq. 3.3.h as a system-of n linear nonhomogeneous algebraic equations. This system of equations satisfies the hypothesis of Lemma 2.3.1 in such a way that all element values are non-negative. Necessity: Follows directly from Theorem 2.3.h when Equation 2.3.h0 is solved for [8122 GS 8&22] . This can always be done by premultiplying the equation by S and postmultiplying it by Sé3. 23 3.h Conclusion. In Section 3.1, sufficient conditions for the decomposition of a real square matrix into a bisymmetric form were given. Theorems 3.1.0, 3.1.1 and 3.1.2 give three different techniques for generating the bisymmetric form. Theorem 3.1.3 allows a given bisymmetric matrix to be tested for quasisymmetry. In Sections 3.2 and 3.3, the necessary and sufficient conditions for the synthesis of class 1 RC and RL graphs are given. Theorem 3.2.0 gives a necessary condition for any coefficient matrix to be realized as an associated matrix. The synthesis technique is given in the sufficiency proof of Theorem 3.2.1 for the RC graph and Theorem 3.3.0 for the RL graph. In Theorems 3.2.2 and 3.3.1, diagonal dominance first discussed by Burlington (20) gives the . AO necessary and sufficient conditions for the synthesis of non-negative element RC and RL graphs respectively. IV. THE SYNTHESIS METHOD h.0 Introduction. In this chapter the results of Chapter 3 are developed into a synthesis method whereby an arbitrary coefficient matrix is examined for acceptance in the class of realizable matrices and acceptable coefficient matrices are realized as real linear bielement systems. Flow charts are then develOped for the determination of acceptable coefficient matrices and for the synthesis of RC and RL graphs. To illustrate the synthesis method, five examples are carried out in detail. h.l Determination of Realizable Coefficient Matrices. Before proceeding to the actual synthesis technique, the class of coefficient matrices that can be realized as real linear bielement systems is determined. An outline of the determination procedure follows: 1. Theorem 3.2.0 imposes a necessary condition for the decomposition of the coefficient matrix A. Therefore, the first step is to test A for real eigenvalues. If the eigenvalues of A are real distinct, then Theorem 3.1.0 gives a sufficient condition for the decomposition. If the eigenvalues of A are not distinct, then the decomposition technique of Theorem 3.1.2 is applied to determine if A is bisymmetric. 2. Theorems 3.2.1 and 3.3.0 imply that if A is to be realized as a RC or RL graph then A must be a. nonsingular bisymmetric, b. nonsingular left quasisymmetric, or c. singular left quasisymmetric. Therefore, A must be tested for singularity. Theorems 3.1.3 and 3.1.h give the necessary and sufficient conditions for A to be quasisymmetric. Therefore, A must be tested for zero-symmetry and the rank of the ratio matrix must be calculated. Finally, A must be checked for left or right quasisymmetry. The procedure for determining if an arbitrary coefficient matrix is realizable as a real linear bielement system is illustrated in the flow chart of Fig. h.l.0. Example 1: Consider the coefficient matrix A given by #1 #2 Coefficient Matrix A of Order n Are The Eigenvalues of Tin2—‘ Stop A Real? Is A Nonsingular? Yes No Is A 13 A N° Sto Zero-symmetric? Zero-symmetric? P’— P Yes Yes Is The Rank Is The Rank No Sto or R _16 -A -A 0‘ C23 By letting c22-11 1 c O 12 = , A.2.AA C13 1 - 033—1 _ l .- Eq. A.2.A3 becomes ' ‘ ' 7 C11 1 C33 = 3 , A.2.A5 -522. n12- and Eq. A.2.Al becomes 811 8 2 833 2* g12 = O ' A.2.A6 513 8 ._ 823- L. 84 Eqs. A.2.AA, A.2.A5 and A.2.A6 give the entries in the C and R matrices. The element values of the RC graph G“ of Fig. A.2.3 are calculated symbolically in Eqs. A.2.3l and A.2.32. Hence, 6O "all” '0' ”611- '0‘ 022 0 G22 A C33 = 2 and G33 a 8 . A.2.A? 012 0 012 0 C13 1 013 8 -023- Ll'd IeG23J ..81 From Eq. A.2.A7, all elements are either positive or zero. Therefore, by the use of a similarity transformation of A, a positive element graph is synthesized. Example A: From Ex. A of Sect. A.l, A.can only be realized as the associated matrix of an RL graph. Since A is symmetric, a satisfactory factoring of A is L = I and R = -A. A.2.A8 The number of vertices of a canonical RL graph for which A can be the associated matrix is given by Lemma 2.2.1 as 5 3gvge. ' 1n2A9 Therefore, from Eq. 3.3.0 L11 L22 912 l 0 l A.2.50 8* = 3 0 '1 -1 and L11 L22 L33 L12 L13 L23 . l 0 0 l 1 0'1 SE = 0 l O -l O l . A.2.51 0 0 l 0 -1 -l.‘ By Def. 3.3.0, ‘7; is a matrix composed of any three columns of either 8*, Sfi, S; or 8g. Let (f; a S? and consider 61 h - D -[ 1 0 1 2 1 1 1 0 7 -5 C7§RC73 = 0 1 -1 1 3 -2 0 1 s -5 10 . A.2.52 _1 -2 34 _l -1_ The determinate of Eq. A.3.A does not vanish, and hence by Lemma 3.3.1, R is factorable into the triple product of Eq. 2.3.A0. Therefore, carrying out the Operations of Eq. 3.3.3 gives 1. 3 '1 s G s' = 5 , A.2.52 I22 8 I22 -1 2 where 8122 is given by Eq. 3.3.5. From Eqs. A.2.A8 and A.2.52, A satisfies the hypothesis of Theorem 3.3.1 and hence there exists a canonical RL graph G3 with non-negative elements for which A is the associated matrix. The f seg matrix is I I C7 11 G22 G12: L11 L22 L12 .. ... I 88 _ [sI22 : v] _ 1 o 1 l 1 0 1 A.2.53 ' O 0 1 -1 ; 0 1 -1 The g-elements are calculated from Eq. A.2.A2 by applying the conclusion of Lemma 2.2.1. Hence 1 r- q 611 F 811"512 l 1 622 = 822+812 = 3' 2 )4 e 2 0 5’4- _Gl2 3 _'312 A -1 1 The l-elements are Obtained directly from Eq. A.2.A8. Therefore, from Eqs. A.2.A8, A.2.53 and A.2.5A, a canonical RL graph 63 of Fig. A.2.5 is constructed Figure A.2.5 Synthesized RL Graph G of Exs. A and S. 3 62 Other solutions to this example can be attempted by returning to Eq. A.2.52 and using differenth;'s Obtained from SE of Eq. A.3.A. However, there are no other solutions since any C7; composed of the columns of SE Eq. A.2.52 becomes a singular matrix and hence, Eq. A.2.52 cannot be selved ! for SI22G38122° A similar statement is true for all dvesg and Uve 83. Example 5: From Ex. 5 of Sect A.l, A is quasisymmetric. Using the factoring technique of Theorem.3.1.2, a solution to LA + R = O is r1 0 0” '2A 7 111 L = o 2 0 , R s 7 23 7 . A.2.55 __0 0 3 J11 7 2A Since the order of A is three, as in Ex. A, then the bounds on the number of vertices of the RL graph Gv is given by Eq. A.2.A9 and correspondingly s; and SE are given by Eqs. A.2.50 and A.2.51 respectively. Let (7; a 8* and 3 consider ' l 0 1 F2A 7 11- _1 0-. 70 -21 (ngcj; = 0 1 -1 7 23 7 o 1 = -21 30 . _ll 7 2A_J _1 '1. A.2.56 The determinate of Eq. A.2.56 does not vanish, hence by Lemma 3.3.1, R is factorable into the triple product of Eq. 2.3.A0. Therefore carrying out the Operations of Eq. 3.3.3 gives 107 -97 s G s' = l ' A.2.57 122 8 I22 E's—9- _97 227 where $122.is given in Eq. 3.3.5. The f seg matrix is the same as in Ex. A and is given by Eq. A.2.53. The g-element values are calculated symbolically in Eq. A.2.5A and the l-elements are known from Eq. A.2.55. Hence, A - "-10“ PL " "'1' G11 11 G = 1 110 , L a 2 . A.2.58 22 iggg. 22 -612 _ _ 97 1 -L12.. _ 3 . 63 Eq. A.2.58 gives the element values for the canonical RL graph G3 of Fig. A.2.5. Another solution of Ex. 5 is obtained by returning to Eq. A.2.56 and using a new O’VE‘SE. Therefore, let and without repeating all of the details, there exists a canonical RL graph GA such that A is the associated matrix. The element values for GA of Fig. A.2.6 are F611. - 2 - “‘11- F 11 G22 3 L22 2 G33 = 102 2 , L33 - = 3 . A.2.59 G12 1 L12 0 G13 2 L13 0 -6231 _l . L L23 _ ° - Figure A.2.6 Synthesized Graph GA of Example 5. Other RL graphs can be synthesized by considering a new ave St, or $5 or 3;. This procedure, of course, can be repeated for all 6 6 S U S U S6 . Furthermore, if desired, A is realizable as the V hi3 5:3 )3 associated matrix of a canonical RC graph GA since A is nonsingular bisymmetric . 6h h.3 Conclusion. In this chapter, the synthesis method is described and illustrated in the flow charts of Figs. h.l.0, h.2.0 and h.2.1. Section h.l gives the conditions under which a coefficient matrix can be realized as the associated matrix of a real linear bielement system. Section h.2 describes the synthesis procedure whereby an acceptable coefficient matrix is decomposed and a RC or RL graph is constructed. Five examples are also given. In Ex. 1, the decomposition technique of Theorem 3.1.0 is illustrated. The method immediately synthesized a positive element graph. The same decomposition technique is used in Ex. 2. However, it is shown that only graphs with some negative elements can be synthesized. The linear decomposition technique of Theorem 3.1.2 is then applied to Ex. 2, with the results that a positive element graph is synthesized. In Ex. 3 the eigenvalues of A are negative and nondistinct. A is shown to be bisymmetric by the decomposition technique of Theorem 3.1.2. However, a positive element graph cannot be synthesized from A. A is then assumed to be the associated matrix corresponding to a maximum order path tree. The appropriate similarity transformation is made on A and the new matrix is realized as the associated matrix corresponding to a star tree of a positive element graph. In Ex. h, a singular matrix is realized as the associated matrix of a RL graph. In Ex. 5, two RL graphs are synthesized from a nonsingular left quasisymmetric coefficient matrix. Ideally, in the decomposition of a given matrix into the product of two symmetric matrices, it would be desirable to have a closed form solution to the nonlinear algebraic system of Eq. 3.1.5 in terms of n of the variables. Then by using conditions 1., 2. and 3. of Theorem 3.2.2 or conditions 2. and 3. of Theorem 3.3.1 as bounds on the solutions, an optimum decomposition should be attainable. Because of the inherent difficulty in the solution of nonlinear algebraic equations, the decomposition technique of Theorem 3.1.1 was avoided in all of the examples. V. CONCLUSION 5.0 Discussion of Results In the preceding chapters a new concept of the classical synthesis problem is developed. The problem involves the realization of time domain models of the form of Eq. 1.0.0 as real, linear, bielement systems. In this sense, the synthesized graph can be thought of as a real time model of the process described by Eq. 1.0.0. Almost all classical synthesis techniques employ the same basic approach in solving the synthesis problem. That is, each technique assumes a fundamental t0pology for the graph and then generates conditions on the mathematics such that the impedance, admittance or transfer function is realizable. Examples of this method are the Foster, Brune, Darlington, Bott-Duffin, image parameter and etc. methods (6’ 7’ 8). Guillemin(25) has stated that one of the shortcomings of this approach is the rigidness of the assumed topology of the graph. It is felt that the synthesis technique of Chapter III has overcome this Objection in part, without abandoning the basic approach entirely. This is accomplished by assuming the canonical topolOgy for the graph to be the union of complete graphs, each complete graph being composed entirely of one type of element. The use of the complete graph gives a generalized topology to the synthesis prOblem since all other topological structures such as paths, pis, tees) ladders and lattices are but special cases of the complete graph. In Chapter II, arbitrary real linear bielement systems are classified according to a subgraph of the system from which the formulation tree is selected. The fundamental properties of class 1 systems are then investigated in detail. Class 1 systems are found to be reducible to a canonical form. The associated matrix corresponding to any maximum order star tree of a canonical graph is defined to be the canonical associated matrix. The sign pattern and the magnitude of the entries in the canonical associated matrix are then calculated. All other associated matrices of a class 1 system graph are related to the canonical associated matrix by a similarity transformation. For the RC graph, this similarity transformation is found from the incidence matrix. For the RL graph, the similarity transformation 65 66 reduces to the identity transformation and hence, the associated matrix is independent of the formulation tree. In Chapter III, a necessary condition and three techniques are given for the decomposition of an arbitrary real square matrix into its 'bisymmetric form. A test is also developed to determine when a bisymmetric matrix is quasisymmetric. From these results necessary and sufficient conditions are also developed to guarantee the synthesized graph has only lion-negative elements. Theorem.3.2.0 points out the well known fact that the eigenvalues of real linear bielement systems are real, correspondingly, if the eigenvalues are negative, these systems can be classified by their transient solutions as overdamped. In Chapter IV, a synthesis method is develOped from which a digital computer program can be written. It is conceivable with the use of dynamic prOgramming techniques (23), that an optimum solution to the synthesis problem can be obtained. Since the synthesized graph can be thought of as a real time model of the process described.by Eq. 1.0.0, one application of this technique is in the area of adaptive control systems. Model In ut Gain —fi Process [ Out ut 7 Figure 5.0.1 Elemental Adaptive System. Consider the adaptive control system of Figure 5.0.0 (2h). The dynamics of the process are adaptively controlled by the use of a "model" of the system. One method of obtaining this "model" for suitable processes is as follows. First, the process is analyzed and a time domain model of the system in the form of Eq. 1.0.0 is obtained. Then this time domain model is realized by the synthesis techniques of Chapter III. If the process is 67 nonlinear, then a "model" can be synthesized by several linear approximations over the Operating range of the process. 5.1 Additional Prdblems. As with any research many additional prdblems arise which warrant further investigation. The following are five problemswhich fit in this category. In Chapter I, restrictions were made on the graph to exclude all drivers (2) and to assume all initial conditions to be zero. These restrictions should be removed and their effect on the synthesis procedure investigated. Brown has given the preliminary analysis for such an investigation. In Chapter II, only class 1 systems were considered. It was postulated in the conclusion of Chapter II that all other classes of RC and RL systems have similar properties to class 1 systems. Further investigation is needed in this area. Ideally, it would be convenient to have a canonical graph and associated matrix for each class of systems. The flow chart of Fig. h.l.0 shows that only coefficient matrices that are nonsingular left quasisymmetric can be realized as either a BC or RL network. Therefore a closer investigation of nonsingular left quasisymmetric matrices should give a new dimension to the duality concept of graphs. Another interesting problem is the relationship between classical synthesis and the synthesis of graphs from time domain models. Some research in the area has already been done Z a for at least one i ii J-i ij 73 them. fit is nonsingular. figheorem A.7: (16, p. 273) A real symmetric matrix A is positive definite if and only if there exists a real nonsingular matrix P such that A = PP'. ' Theorem A.8: (23, p. 1A7) (Implicit function theorem). Let f'a (f1,... —. _, - +k With values in En Suppose fEC' on S. Let (x0, t0) a 0 and for which the n x n de=13erminate det [:Din( E'; t6 )] ¥ 0. Then there exists a k-dimensional nQtlghborhood T of t " ’ fn) be a vector valued function defined on an open set S in En and one, and only one, vector-valued function E, defined 0 0 ‘3r1 Tb and having values in En’ such that i. 560' on To, 11. E (E6) = Eb iii. 3" (§(t); t) = 0 for every t in To. Theorem A.9: (1h, p.118) A necessary and sufficient condition that the system of m homogeneous linear equations in n unknowns, n :5 X =0, 131,2, coo,m 3:1 13 3 have a nontrivial solution is that its coefficient matrix have a rank less than the number of unknowns. Theorem A.lO: (1h, p. 228) If A is a real symmetric matrix, there exists an orthogonal matrix U such that U‘AU is a diagonal matrix whose diagonal elements are the characteristic roots of A. Theorem A.ll: (111., p. 266) The roots Al, A2, ..., An of the equation det [As/XE] = 0, where A and B are symmetric and B is positive definite, are all real. Theorem A.l2: (16, p. 313) Similar matrices have the same characteristic polynomial. Theorem A.l3: (11+, p. 255) If X'AX is positive definite, then det A>O. Theorem A.lh: (1h, p. 58) The determinant of the product of two square matrices of order n is equal to the product of their determinants. 71+ Theorem A.15: (11+, p. 65) A square matrix A has an inverse if and only if det A *0. Theorem A.l6: (22, p. 133) If the characteristic roots of a matrix A are distinct, then A is similar to a diagonal matrix. I'Lheorem A.l7: (’4, p. h-SO) Let Al and A2 represent any two cut-set matrices of a given connected graph G. Then there exists nonsingular transformations relating Al and A2. 4! LYsl‘ (a r?— 3 \3 {-5, a v t _..—