1| Nil/NHWWV‘M f MN I V WW I J I W {NW/UH 136 O N .h. '—l I m (ZN SIGN PATTERNS 0F BRANCH MAYRECES AN?) ELGRAFH REALEZAUQN Thesls for the Degree of DH. D. T‘KECEEGAI'J STATE UI‘EI‘V’ERSETY ”avid Paui Brown 1961 This is to certify that the thesis entitled On Sign Patterns of Branch Matrices and R-Graph Realization presented by David Paul Brown has been accepted towards fulfillment of the requirements for Ph. D degree mElectrical Engineering Date 91'?/ ‘6 0-169 LIBRARY Michigan State University PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE 6/01 0 lCIRC/DaleDue,p65~p is ABSTRACT ON SIGN PATTERNS OF BRANCH MATRICES AND R-GRAPH REALIZATION by David Paul Brown This thesis deals with prOperties of sign patterns of the entries in the coefficient matrix of the branchinode-pair‘) equations, branch smatrix, for any graph, and the realization of a given matrix as the branch matrix of an R-graph. - In the second section, properties of sign patterns are classified as to those fixed by: (1) element orientations per se; (2) element orientations determined by their being contained in subgraphs. The main result in (l) is that if the branch orientation of a tree of a part is changed, then there is a row and column sign change of the entries in the correSponding branch matrix for diagonal element matrix, and conversely. This result is based on the relationship between the s-orientation of any two f—segs and the s-orientations of the corresponding common elements. ‘In (2), a subgraph consisting of any two branches, b1 and bj' contained in a path-in- tree is considered. . The fact that the p- and e-orientation of bi and bj coincide is shown to imply that the s-orientation of the elements common to the f-segs corresponding to b1 and bj are the same, and conversely. A set of pairs of branches, each pair having coincident p- and e-orientations is shown to imply that all branches of the set are contained in a path-in- tree with coincident p- and e-orientations. . The situation when the p- and e-orientations do not coincide is also considered. The Specific character of a subgraph of the tree corresponding to a branch matrix containing a principal submatrix with all positive or all negative entries is then David Paul Brown obtained. The complete tree form is determined for the case of all positive or all negative entries in the branch matrix. The necessary and sufficient conditions on a given matrix such that it is realizable as an R-graph consisting of the union of a complete graph and Lagrangian tree are determined in the fourth section. Formulas for corresponding element values and a process to determine the orientation of the tree are also given. ‘It is found that the conditions for realization are fixed by the tree form associated with the branch matrix. A Using the tree transformation matrix of the third section, necessary and sufficient conditions for realization are determined for an arbitrary tree. The detailed form of the conditions for realization are given for a tree in the form of a path. vFor the case of a five vertex complete graph, the conditions fixed by the three tree forms are given in detail. ON SIGN PATTERNS OF BRANCH MATRICES AND R-GRAPH REALIZATION By David Paul Brown 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 1961 ACKNOWLEDGMENT The author is greatly indebted to Dr. M. B. .Reed for his constant guidance in preparing this thesis and for funda- mental work in electrical network theory on which much of this thesis is based. Some of the ideas in this thesis were developed under the sponsorship of the National" Science Foundation grant No. (3-9735. ************* ii Ws‘w'“, TABLECH‘CONTENTS Page I. INTRODUCTION ........................ 1 II. SICN pATTERN' OF BRANCH MATRIX ............ 3 III. TREE TRANSFORMATION MATRIX ............. 16 IV. SYNTHESIS OF R-GRAPHS ......... ‘ ......... 22 LIST OF REFERENCES ...................... 38 APPENDIX ........................... . 4o I . INT RODU CTION The problem of determining restrictions on matrices with constant entries such that they are coefficient matrices of some system of equations determined from a graph has been considered by many investi- gators. A method of realizing symmetric matrices with constant entries as R-networks has been given by W..Cauer [1]. Here the requirement that the given matrix be positive-semidefinite leads to networks containing ideal transformers. The well-known condition of dominance, discussed by Burington [Z], is sufficient for synthesis of R-networkS' without ideal transformers. For networks without ideal transformers, Cederbaum [3, 4] has shown that a necessary condition for synthesis of short circuit admittance matrices is that they are paramount. This result is based on properties discussed by Talbot [5]. 'As a method of realizing matrices, Cederbaum [6, 7] has given a procedure to decompose a matrix into a triple product of matrices, where the center matrix, which is diagonal, is pre- and po st-multiplied by a unimodular matrix and its transpose reSpectively. Slepian and Weinberg [8] have summarized this area of network synthesis and raised many questions. ‘A recent discussion of synthesis of networks without ideal transformers has also been given by Guillemin [9]. The problem of characterizing the patterns of the signs of the entries Of certain types of matrices has recently been considered. In particular, using matrix algebra, Cederbaum [7] has determined some elementary sign properties of the entries in a matrix triple product, the center matrix, which is diagonal, being pre- and post-multiplied by a unimodular matrix and its transpose respectively. These results have been associ- ate-d with the realization of IOOp-resistance matrices by So [10]. Some discussion Of Sign patterns relevant to synthesis has been given by Slepian and Weinberg [8]. Biorci and Civalleri [11] have recently develOped a procedure to realize a restricted class of short circuit admittance matrices based on forming the graph from the signs Of the entries in the given matrix. In this thesis the matrix triple productflflej /: [Gij] is con- sidered, where )j f = [7A ] is the fundamental f-seg matrix discussed by Reed [12, 13] and. fie is an element matrix containing constant entries. Although the properties of the f-seg matrix are the same as the cut set matrix [14], the definitions Of the correSponding 'subgraphs, i. e. the seg [15] and the cut set [14], are logically different. Because Of the clarity of the seg concept, it is used in the following discussion. The Objective of Section II is to determine the relationship between the sign pattern Of the branch matrix, J )Zj (2)3 ', and the orientation of the elements of the corresponding connected graph P(part). It is also shown that the sign pattern of the branch matrix or principal submatrices of the branch matrix is fixed by the orientation of elements of specific types of subgraphs. In Section IV, the necessary and sufficient conditions on a matrix such that it is a branch matrix correSponding to an R-graph are determined. Equations to calculate the element values associated with the graph are also given. The conditions for realization associated with a branch matrix are fixed by the possible tree forms of the part. Therefore, the totality of necessary and sufficient conditions can be obtained by cataloging the conditions fixed by each tree form. These results are Obtained using the tree transformation matrix of Section III. A list of symbols, which are used repeatedly, is given in the Appendix. II. SIGN PATTERN OF BRANCH MATRIX 2. 1 Introduction The sign pattern of Med ' is investigated in terms Of its dependence on the orientation of elements in a graph. The following theorems, which are based on the seg and f-seg matrix, indicate that the elements in the cotree of a graph do not effect the sign pattern and that the branch orientations are the controlling factors. The Operation of cross-sign change, Definition 2. l, is used to describe the general pattern Of signs as a function of branch orientations. Some results not directly related to the sign patterns have been included as corollaries. The orientation of any two branches, bi and bj' is shown to fix the Sign of the i, j entry of ”Jfie )3 ' for ”e diagonal with non-negative entries. This result is used to determine the signs of the entries in the branch matrix as a function of the orientation of pairs of branches which are contained in a path-in-tree and conversely. For the case of a path and Lagrangian tree, the complete sign pattern is determined. Definition 2. 1: A cross-sign change of a matrix a is the Operation of changing the sign Of each (non-zero) entry in the i-row and i-column. Theorem 2.1: For any matrix a = [aij] , consider a sequence n of K different cross-sign changes. If a ij 7! 0, i 7! j, then the number of entries in “which change Sign as a result of the K cross-sign changes is ZK(n-K). Proof: Each cross-sign change changes the sign of 2(n-l) entries Of a . Entries common to two cross-sign changes are changed in sign twice, i. e. they do not change Sign. The number of entries in imrow and i-column common to K cross—sign changes is x14.» x2 + . . . + xK—I where xi, i: 1, Z, . . . , K-l, is the number of entries in i-row and i—column common to one cross-sign change. Since x, = 2, 1 K-1 2 x. = 2(K-1). . 1 1:1 Therefore, the number of entries in the i—row and i-column which change sign as a result of K cross—sign changes is 2(n-l) - 2(K—1)= 2(n~K). Since there are K similar patterns, the total number of entries which change sign is the sum of 2(n—K) for each row and column, that is ZK(n-K). Corollary 2.1: Consider any matrix a: [a, Ij]n' Ifa,,>0 (a,.<0), 13 1_] i 7? j, then the maximum possible number of negative (positive) off-diagonal entries as a result of cross-sign changes is -—- if n is even 2 if n is odd. Proof: It is only necessary to find the maximum of ZK(n-K), since this is the number of off—diagonal entries which are negative (positive) d as a result of K cross—sign changes. Since dK (ZK[n-K]) = 2n—4K = 0, Kmax = 121' if n is even and nil if n is odd. Substituting these values of K in 2K(n-K) gives the conclusion. 2. 2 Sign Pattern Fixed by Certain Elements For any tree T, Si and S_ are any two f-segs defined by branches bi and bj respectively, and )3 f = [ I/L j ] where = [Sij]' Theorem 2. 2. 1: If and only if Si and Sj contain common elements (ChOI‘dS) C, then the X-vertex set of C when C is in Si is the X- or NX—vertex set of C when C is in Si. Proof: Sufficiency: Suppose C contains only one chord c1, then c1 is an X-NX element in Si and also in Sj and the theorem applies. 1 Suppose C contains two or more chords ck. By Theorem 15 [15], bi is in the f-circuit defined by ck and so is bj. Consider the vertex segregation defined by bj. By Theorem 14 [15], there is a path-in-tree in the X-vertex set (NX-vertex set) between any two X-vertices (any two NX-vertices) which contains only X-vertices (NX-vertices). Because Si is an f-seg, bj is an X-element (NX-element), hence there is a path-in-tree containing only NX-vertices (X-vertices) and does not contain bj. Suppose the X-vertex set of C in‘Si is neither the X- nor NX-vertex set of C in Sj. Then there is a path-in-tree between a vertex in the X-set Of Si and a vertex in the NX-set of S, and this path does not contain both bi and b,. By the initial argument If} the proof of this theorem, there is a path-iiI-tree between the same pair of vertices which contains bi and bj. This implies a circuit in tree and contradicts the hypothesis. Necessity: Assume one element of C, is not common to Si and ck, S_, i. e. , if Ck is in Si’ it is not in Sj. Hence ck is not an X-NX-element in 8,. Since this conclusion is independent of the X or NX labeling of J vertices, the theorem follows. Corollary 2. 2. 1: All elements of C have the same (opposite) bi and b, defined 8- orientation. Proof: The X-vertices corresponding to bi are all X- or all NX- vertices corresponding to bj. Therefore the conclusion follows from the definition of S- orientation. Theorem 2. 2. 2: If and only if the S, and S. orientations of all 1 elements of C are the same (Opposite), then S, s, =+1 (S. .- 1PJP 1PJP where p corresponds to elements Of C and i 7’ j. Proof: There are four and only four cases for elements in C as shown in Figure 1. e e a \P x \ J 1 S. S. S. S. 1 j 1 J s, s, = +1 3, s, = -l 1P JP 1P JP 6 e S S. S "S. 1 J 1 J Fig. l--Possible orientation patterns. Hence, the theorem follows. Corollary 2. 2. 2.1: Suppose Si and S, have at least two common elements . ~ If (1 s, s, =+1 2-1, then s, s, =+1 3-1 ) 1P Jq ( ) 1q JP ( ) (Z) s, s. = +1 (2-1), then s, s, = +1 (2-1) 1P 1‘1 JP Jq where p and q correspond to elements of C and i 7’ j. Proof: By Theorem 2. 2. 2, either 5, s, = +1 and s, s, = +1 or —'—' 1P JP 1‘1 Jq S. S. = -1 and S. S. = -1. However, in either case s, s. s. s, = +1 1P JP 1‘1 Jq 1P JP 1‘1 Jq Grou in the terms as s. s. s, s, = +1, 1 of corollar follows. pg (lpJququ) () Y The second part of the corollary follows from the following: ( )( +1. 5. s. s. s. )= 1P 1‘1 JP Jq Corollary 2. 2.. 2. 2.: The determinant of any submatrix of )3 Of the form ?, s, “T FE. 5.1 1P 1C1 1P JP or is +1, -1 or O. S, s, s, s. LJP Jq LJq lq Proof: Either Si and S, have common elements or not. If they have common elements, all entries in the submatrices of hypothesis could be non-zero. Since each entry in the submatrices is +1 or -1, each product nd is can have a value of +1 or -1. By 5.5. ’S.S. a S. S. -S. S. 1P Jq 1C1 JP 1P 1‘1 JP Jq Corollary 2. 2. 2. 1, the products associated with either submatrix are equal. Hence, for this case, the value of the determinants is O. For all other cases one or more of the entries in the submatrices is zero. Since the remaining entries can only have the value +1 or -1, the conclusion follows . Corollary 2. 2.2. 3: Let fie Of/j/ge J v = [G] be diagonal U with positive entries. (1) If and only if the Si and Sj orientations of all elements of C are the same (Opposite), then C3ij > 0 (<0), i #j (2) G,, > O. 11 . 1' 28. s, g , the corollary follows from Theorem J P 1P JP PP Proof: Since G. 1 Theorem 2. 2. 3: If bi is a branch of any tree T of P, then corres- ponding to a change in the orientation of b, there is a cross-sign change : i Of flT Jfie Ad? ° Proof: If the orientation of b. is changed, then every entry in the 1 i~row of )j changes sign. Therefore, every non—zero entry in the i-row of Ajfie also changes Sign. Hence, in the product (jfl 6))! ' every non-zero entry in the i-row and i—column changes Sign. Corollary 2., Z. 3: 1G,.) is invariant through changes in orientation . l} Of branches of T. Proof: Direct consequence of Theorem 2. 2. 3 and Definition 2.1. Theorem 2. 2. 4: If bi is a branch of any tree of P, then correspond- ing to a change in the orientation of bi there is a cross-sign change of fi : Jfl Xi ', fl diagonal, and conversely. T e e Proof: The first part of the theorem follows from Theorem 2. 2. 3 for the case of diagonal fle' ~ For i 3! j, entries gpp which appear in Gij = gsipsjpgpp correspond to elements which are common to Si and Sj' and therefore by Corollary 2. 2. 1 all these elements have S-Orientations which are the same or Opposite. In addition, from Theorem 2. 2. 2, sipsjp = +1 for all p or -1 for all p. Therefore, if Gij is changed in sign, then each Sipsjp in the defining sum must change sign. For this to be the case, the orientation Of either bi or b. must have been changed. A change in the Sign of the entries in the i-row and i-column of W implies a change in the orien- T tation of bi since sip' for all p, are the only entries of J common to all terms. 2. 3 Sign Pattern Fixed by Certain Subgraphs Theorem 2. 3. 1: Any two branches bi and bj Of a tree are contained in some path-in-tree PT. Proof: Let the vertices of b, and b, be v, , v, and v, , v. 1 j 11 12 jl jZ respectively. Since the tree is connected there is a path between any pair of vertices. In particular, there is a path p with end vertices vi1 m.) Fa] _ and VjZ' Either p contains both branches, one branch or neither branch. In the first case the theorem is true. Hence assume both branches are not contained in p. Since an element is a path, there is a path with end vertices vi1 and vi2 and a path with end vertices vjl and VjZ' .These paths do not form a circuit. Therefore from properties of a path there is a path-in-tree containing both branches. Theorem 2. 3. 2: If and only if for some path-in-tree the p- and e-orientations of bi and bj coincide, then the Si and Sj orientations of all elements of C are the same. ~ Proof: Sufficiency: By the definition of f-seg orientation and hypothesis, bi and bj have e-, p- and s-orientations which coincide. Let Ki be the compliment of bi in tree which contains the X-vertex of bi' By definition of f-seg, the vertices of K1 are X-vertices of Si. There is one and only one path-in-tree, P', between the X-vertex of bj and the NX-vertex of bi' This implies that every vertex of P' is an X-vertex of Sj° Therefore every X-vertex of Si is an X-vertex of Si. This implies the conclusion. -Necessity: By hypothesis b1 and bj are e-oriented from X- to NX- vertex sets of Si and Sj respectively. By Theorem 15 [15] b1 and bj are in the f-circuit defined by any element of C. .Therefore bi and bj are contained in a path-in-tree P'. »Let the elements of P' be p-oriented Opposite the f- circuit orientation. .Therefore bi and bj are p-oriented from the X- to NX-vertex sets of Si and S, respectively. Hence the con- J clusion follows. Corollary 2. 3. 2: With the same hypothesis, 8. s, = +1 1P JP where p corresponds to elements Of C and i 51 j. 10 Proof: Direct consequence of Theorem 2. 2. 2 and Theorem 2. 3. 2. Theorem 2. 3. 3: If bi and bj have coincident p- and e-orientations in some PT’ then b1 and b, have coincident p- and e-orientations in every PT. Proof: By hypothesis, bi and bj are contained in some path-in- tree PT. .From prOperties of a path, there is a subpath of PT’ PTI’ which contains bi and bj as end elements. Every path-in-tree which contains b1 and bj contains PTl' . The theorem follows from the method of p-orienting the elements. Theorem 2. 3.4: Consider a set of r branches Br. If and only if each pair bi and b, of Br have coincident p- and e-orientations for some J path-in-tree, then the branches B1. are contained in a path-in-tree with coincident p- and e-orientations. Proof: Sufficiency: ' It is only necessary to Show that the branches Br are contained in a path-in-tree since then the hypothesis fixes the p- and e-orientation of the conclusion. By induction on r. For r = 2, the hypothesis and conclusion are the same. Therefore consider r = 3, where the branches of B1. are bl, b2 and b3. Suppose b1, b2 and b3 are not contained in a path-in-tree. Therefore by hypothesis and properties of paths, each branch is con- tained in a path-in-tree and these paths form a star with common vertex vx. Also by hypothesis, e-orienting any branch, b1, fixes the p- and e—orientations of the other branches. Thus the p- and e-orientation arrows of b; and b3 are pointing toward or away from vx. By Theorem 2. 3. 3, this is true for every path containing b1 and b2 and for every path containing b1 and b3. This implies that the p- and e-orientations of b; and b3, for any path-in-tree containing b2 and b3 do not coincide. The conclusion follows for r = 3. 11 Suppose the theorem is true for r = k, and the branches of B are k b1, b2, . . . , bk' If the theorem is not true for r = k+ 1, bk+ 1 is contained in a path-in-tree which has a terminal vertex vX that is one of the non-terminal vertices of every path-in-tree containing b1, b2, . . . , b k. By hypothesis, e-orienting any branch, b1, fixes the p- and e-orientations of all branches. The p- and e-orientation of the branches, b and bi' k l bi + 1, . . . , bk are pointing toward or away from vX for b1 Elk + 1. This implies a contradiction of hypothesis for the p- and e-orientation of the branches bk + 1 and bj’ j = i, i+ 1, . . . , k, do not coincide for any path-in-tree. The necessity follows from the fact that a path-in-tree which con- tains the branches b1, b2, . . . , br’ . has subpaths containing any pair of branches bi and bj. Corollary 2. 3. 4: ' Consider any v-vertex part and tree T. With the same hypothesis and r = v - 1, T is a path whose branches have coinci- dent p- and e-orientations. , Proof: Direct consequence of Theorem 2. 3.4. Theorem 2. 3. 5: Consider fie diagonal with non-negative entries. If and only if fiT = [Gij] contains a principal submatrix of order r with positive entries, then r branches of T define f—segs with common elements and are contained in a path-in-tree with coincident p- and e- orientations . Proof: Sufficiency: Any entry in the submatrix of hypothesis is of the form ES 5 g Terms in this sum correspond to elements common p ip 110 1313' to S, and 5,, i 7! j, and therefore, all non-zero products Sipsjp are +1 or 1 J s, s, = +1 for at least 1P JP one p. In addition, Corollary 2. 3. 2 implies that the branches bi and bj all are -1. Since the sum is positive and gpp Z O, 12 defining Si and Sj respectively, are contained in some path-in-tree with coincident p- and e-orientations. This statement is true for all pairs of branches associated with off-diagonal entries of the submatrix of hypothe- sis, i.e. b1 and bj for Iii < j _<_ 2, 3, . . . , r. Therefore by Theorem 2, 3.4, the conclusion follows. Necessity: All entries in fl associated with the r branches of T hypothesis have the form ES, 3, g . Since all f-segs defined by the P 1P JP PP branches have common elements, each entry is non-zero. By hypothesis and Corollary 2. 3. 2, all non-zero sipsjpz +1. .Thus the conclusion follows since g > 0. PP — Corollary 2. 3. 5: Consider fie diagonal with non-negative entries. If and only if for fiT =‘ [Gij]. Gij > 0, then (1) T is a path (2) all branches of T define f-segs with common elements and have coincident p- and e-orientations. Proof: This follows from Theorem 2. 3. 5. Theorem 2. 3. 6: If and only if for some path-in-tree the p- and e-orientations of bi and bj are not coincident, then the S, and‘SJ. orien- 1 tations of all elements of C are opposite. Proof: This is the contrapositive form of Theorem 2. 3. 2. Corollary 2. 3. 6: With the same hypothesis, ss -1 ip jp— where p corresponds to elements of C and i 7! j. Proof: Direct consequence of Theorem 2. 2. 2 and Theorem 2. 3. 6. 13 Theorem 2. 3. 7: If bi and b, do not have coincident p- and e-orien- tations in some PT’ then bi and bj do not have coincident p» and e-orien- tations for every PT. Proof: Similar to Theorem 2. 3. 3, for PT contains a subpath PT1 which has b, and bj as end elements. Since every path-in—tree which 1 contains bi and bj contains PTl’ the conclusion follows. Theorem 2. 3. 8: If and only if each pair bi and bj of B do not have r coincident p- and e-orientations for some path-in-tree, then there exist paths-in-tree, pi, such that (1) each pi contains one and only one branch of Br (2) some one vertex vx is a terminal vertex of each pi (3) the e-orientation of the bi are all toward or all away from vX. Proof: Sufficiency: It is only necessary to show that (1) and (2) of the conclusion are satisfied for then the hypothesis fixes the e-orientations of the conclusion. By induction on r. For r = 2, the hypothesis and conclusion are the same. Therefore consider r = 3 where the branches of Br are b1, b2 and b3. Suppose the branches b1, b2 and b3 do not satisfy (1) and (2) of the conclusion. The only situation that can exi‘st is that bl, b2, and b3 are contained in a path-in-tree. By hypothesis, arbitrarily e-orienting any branch, b1, fixes the p- and e-orientation of b2 and b3. Since b2 and b3 have the same p- and therefore e-orientations, the hypothesis is contra- dicted. Therefore the conclusion follows for r = 3. Suppose the theorem is true for r = k and that the branches of B k are b1, b2, . . . , bk' If the theorem is not true for r = k + l, bk + 1 is contained in one of the pi. By hypothesis, e-orienting any branch, b1, fixes the p- and e-orientations of all branches. The p- and e-orientation of bi and bk + are the same for b1 not bi or b . This fact contra- 1 k + l dicts the hypothesis. Hence the conclusion follows. l4 Necessity: By hypothesis, any pair of branches bi and bj is contained in a path-in-tree containing vx. The e-orientation of b1 and bj are both toward or both away from vx. Therefore from the method of p-orienting the elements Of a path the conclusion follows. Corollary 2. 3. 8: Consider any v-vertex part and tree T. With the same hypothesis and r = v - 1, T is a Lagrangian tree whose branches are e-oriented toward or away from the common vertex. Proof: Direct consequence Of Theorem 2. 3. 8. Theorem 2. 3. 9: Consider >86 diagonal with non-negative entries. If and only if 6 T = [Gij] contains a principal submatrix or order r with negative entries, then r branches of T define f-segs with common elements and satisfy (1), (2) and (3) of Theorem 2. 3. 8. . Proof: Sufficiency: Similar to Theorem 2. 3. 5 for any entry of the submatrix of hypothesis, gsipsjpg p' has terms which correspond to P elements common to S1 and Sj' i a! j. By hypothesis and the fact that all non-zero products 3, s_ equal +1 or all equal -1, s, s, = -1 for at 1P JP 1P JP least one p. - Corollary 2. 3.6 implies that the branches b1 and bj defining Si and Sj respectively, are contained in some path-in-tree with p- and e-orientations that do not coincide. This is true for all pairs of branches b1 and b_ where 1_<_i < j :2, 3, . . . , r, i.e. all branches associated J with Off-diagonal entries Of the submatrix of hypothesis. Therefore by Theorem 2. 3. 8, the conclusion follows. ~Necessity: All entries in fiT associated with the r branches of hypothesis, Es. s, g , are non-zero since the f-segs defined by these P 1P JP PP branches have common elements. By Corollary 2. 3. 6 and hypothesis all non-zero s. s, = -1. Since g > O, the conclusion follows. 1P JP P— 15 Corollary 2. 3. 9: Consider fie diagonal with nonwnegative entries. T ij whose branches define f—segs with common elements and are e-oriented If and only if for g = [G .], Gij < 0, i 3! j, then T is a Lagrangian tree toward or away from the common vertex. » Proof: This follows from Theorem 2. 3. 9. III. TREE TRANSFORMATION MATRIX 3.1 Basic Properties A v-vertex connected graph, a part, is the union Of a tree, T, and the complement of T, a cotree, G. Any part will be designated as P = GUT or P. = GUTi when reference is made to a specific tree. Definition 3. 1: Consider a v-vertex part P = TiUT, where Ti and J T are any two v- -vertex trees, and consider Tj the tree and Ti the cotree of P. Let the corresponding f- seg matrix be [u jijl] where the columns of u correspond to T and the columns of jij correspond to Ti' The submatrix )J ij is called the tree transformation matrix from T1 to Tj. For any part P = GUT, let Q = [ Q T a G] be the incidence matrix where the columns Of QT correspond to the tree T and the columns Of a G correspond to the cotree of P. Lemma 3.1.1: ForP= Tij’UT jij: QJTj-Il aTi Proof: Since the f-seg matrix Jf and the incidence matrix satisfy the relation [12]: infoH (2TH CZT 61G]: QT’la, the conclusion follows. Lemma 3. 1. Z: The tree transformation matrix, jij’ is non- det )1“ =_t 1- 1.1 l6 singular, and 17 j“ correspond to a tree, )3 ,, ij 1.1 '1 Proof: Since the columns of exists [14]. For any tree T, a T is square, therefore by Lemma 3.1 -1 det jij = det a,” det aTi' The conclusion follows since det a T _+_ l [14]. Theorem 3.1. 1: For any part Pi GUTi and Pj = GUTj with f-seg matrices [ u Ii] and [% jj] reSpectively, ‘MJ9j : >A?ij.) : )& e Iagonal and gij _ 0 (1) Gijf- 0, i 7! j, for branches of TL oriented from (or toward) the common vertex; all other Gij Sign patterns are deducible from alterations in orientation of branches of TL. 22 v0 ' Q1 v-lO .2 o j+1 La. (b) Fig. 2-«(a) V-vertex complete graph. (b) Lagrangian tree, TL. 24 = = . > . (Z) [Gji‘ IGijl gi,j-i for j 1 v—i Gii: j}; gij+ g1,i-1+ g2,i-2+' ' ' I gi.1,1 fori=1, 2,. . . , v-l. Proof: The elements of PL are to be oriented as follows: all ele- ments incident to vertex No. 1 are to be oriented toward vertex 1; all elements incident to vertex No. 2 not already considered are to be oriented toward vertex 2; etc. For this arrangement, the f—seg matrix, f’ has the following form: 1 [I o o . o 1 1 l 1 1 o o o o 0 .j 2 0 l O . . . 0 -1 0 0 . . . 0 0 1 1 l . . . 1 l . 3 0 0 1 0 0 -1 O 0 0 -1 0 0 O 0 0 v-1 0 0 0 1 0 O O -1 0 0 O 0 -1 0 ...l where the columns of )j correspond to elements 11, 12, . . . , 1 v-l; __ _ . . . ,. 21, 22, . . . , 2v 2, . . . v11. Since fie Is d1agona1,)/)&e>/ 1s symmetric and has entries shown by (gijE 0 for i E 0 or j_<_ 0) G . = - . . .2 h > . ij gi,j-1 J 1 v-i (4.2.1) C'ii: j_i;gij+ g1,i.1 + g2,1.2+ ' ' ' + gi.1,1 for i = l, 2, . . . , v-l. This result proves (2). For the assumed orientation pattern all off-diagonal entries are non—positive. By Theorem 2. 2.4, the signs of these entries are affected 0/? by changing branch orientations by way of cross-sign changes of ' which proves (1). Ex??? 6"__ I 25 Theorem 4. 2. 2: Let [u j ] be the fmseg matrix for PL = G UTL v . . , = . of Figure 2. For the matrix J fiegijhf [Gij(gij)] written as xcwfsrg h ' = W ere 7CC. [611612 G1,v—1622 C'23 GZ,v-1 G33 G3,v--l . d '= Gv-l,v-1] an 1g [gllglz g1,v—1g.21g22 gz, v-2 g3,1 g3,v_3 . . . gv_1,1], is non-SIngular. Proof: Orient the elements of P as in the proof of Theorem 4.2.1. L The form of the entries in Jfle (gi 9% ' is given in (4. 2.1) and there» fore for this orientation pattern the deJtailed form of Ms is given in (4.2.2). [— _ a 11 QZI a22 Q31 a 32 Q33 “ aiz an . . . ii Qv-I,IOv-l,20v-l,3 a v-1,i . . .QV-1,V-l (4.2.2) The square submatrices, __ I—1 1 l l -l O . . . O 0 a .= 0 -1 . . . 0 0 , iylv-l, i1 26 are of order v-i and a = [1]. The submatrices a ij’ i) j. -l -l are of the order v-i x v-jfandvcontain all zero entries except for +1 in the (1, i-j) position. By the‘Laplace Expansion [17] with the first v-l columns, the determinant of (4. 2. 2) is given by the product of the determinants of the square diagonal submatrices each of which is non-singular. Therefore, for the assumed orientation pattern, )j s is non- singular. The form of jfie (gijU/ ' for any other orientation pattern of elements of P can be Obtained through the use of cross-sign changes. L The Operation of cross- sign change changes only the sign of off-diagonal entries in Jfle (gi j“)! Therefore if ’X’G 1corresponds to e(gij) )J ' after any number of cross- sign changes, then I] JAG where U is diagonal with +1 and -1 entries. .The transformation matrix U [17] is necessarily non- singular. Since 7C0 :J/s xg’ XGI: Ujs xg’ The matrix st is non- singular since it is gthe product of two non- singular matrices which proves the theorem. Corollary 4. 2.2: Let [Gij(g ij)] be a matrix obtained from )6; (gij))f'= Gij (gij)] by interchanging rows 1 and j and columns ° I 1 and j. Writing [Gij I:(gij)] as 1 : )fsl kg — l l I I l I Where ’X'Gl [G11G1['2 ' Gl, v-1C’22C'23" ‘ Gz, v—1G33" G3, v-l l Gv-1,v-l]and ’X'g:['g11g12 ' g1,v-1g21g.22 g2,v-2g31 g3,v-3 . gV_1 1], $1 is non-singular. Proof: The Operation of interchanging rows 1 and j and columns i andj of [G] interchanges G . and G .forp= 1, 2, . . . , i-l, i+l, . . . 1.1 P1 PJ j-l, j+1, . . . , v-l, j > i, and Gii and ij. ‘All other entries of [Gij] 27 remain fixed. Thus fX’Gl Theorem 4. 2. 2, by interchanging certain rows, that is 316 where I] is a non-singular transformation [17]. By Theorem 4. 2. 2, 1G1: :7 J5 ’X'g and M51 = 3% s is non-singular since it is the product of non-singular matrices. can be Obtained from fit/G, defined in 4. 3 Necessary and Sufficient Conditions for R-Graph Synthesis In the following theorems, it is assumed that fiL’ of order v-l, is the coefficient matrix of the branch equations, branch matrix, for PL == GVUTL as shown in Figure 2 for diagonal fie. Branch matrices for other parts Pi =GV UTi are designated as ”i and for the parts Pia: GVUTio. and P1"ifi - GVUlTiP, as fiio and am respectively. Theorem 4. 3. 1: Consider any fill = [Gij]v 1 and the branches of TL oriented from (or toward) the common vertex. If and only if (1) Gij_<_0 foriyfj (2) Gfi_>_0 fori=:1, 2, . . . , v-l, v-l ZG,,>0 i=1 1"" then gij 2. 0. Proof: Sufficiency: The )fi L(Gi j) of hypothesis is in terms of G 1j and jg e(gij))j ' of Theorem 4.12.11Jis in terms of gi, Furthermore (I) of Theorem 4.2.1 permits by cross- sign changes alteJring’Jj&'(giJ )x )j ' into ML fl e(gij))JL ' in correlation with TL oriented as the TL t h h d - ' )5; J]. L” )JL' 0 w 1c fiL correSpon 5 Since and e(gij) correspond to identical TL(Orientation and form), these matrices are equal. Therefore 28 fiLKhj) : XL 27 4&1?)ij This last equation can be written as 10:11ng h I - . ... °-° °°° W ere 1G $611612 G1 v-1622623 GZ,V-IG33 (33,le G v-1.v-1] and [Xg' =[gg11 12 “g1,v-1gz1g22 g2,v~2g31 g3,174 . gv 1 1]. By Theorem 4. 2. 2, s is non- singular and therefore the solution is: H— __ K - g11 G1.2 g12 '613 gl,v-2 "G1,v~1 v-l gl,v-l 2 GI. i=1 3 g21 "G23 gzz : 'Gz4 (4.3.1) gZ,v-3 -GZ,V-1 V-l g G . 2,v 2 j=1 21 Val gv-l,l ,2 Gv-1,J L J .351 29 That all entries on the right side of (4. 3. 1) which are not sums are non-negative follows from (1) of hypothesis. All entries which are sums are non—negative by (2) of hypothesis. Necessity: Since the equation KG = )J s ”)L g as defined in the sufficiency part of the proof is independent of the values of Gij and gij’ (4. 3.1) applies to‘this proof. From (4. 3.1) for gij>0, (1) and (2) of hypothesis follow. Corollary 4. 3. 1: Consider anyfi L = [Gij]v 1. If and only if (1) )5 L can be chanted to the canonical form, c = [Gcij]’ by a finite number of cross-sign changes, > (2) Gii _ 0 v-l fori=l,2,...,v-1. Gci' _>_ 0 i=1 J then gij _>_ 0. Proof: Sufficiency: By (1) of hypothesis change fl L to canonical form )2] c' By Theorem 2. 2.4 and (1) of Theorem 4.2.1, We .corres- ponds to T with all branches oriented from (or toward) the common L vertex. Therefore Theorem 4. 3. 1 implies the conclusion. Necessity: Change orientation of the branches of TL and apply corresponding finite set of cross-sign changes to )ZTL until all branches are oriented from common vertex. This process produces a matrix satisfying Theorem 4. 3. 1. Therefore hypothesis of corollary follows. Definition 4. 3. l: A symmetric matrix fl: [Gij]n is an R-matrix if (1)” can be changed to the canonical form, fie = [Gcij]’ by a finite number of cross-sign changes, 3O 2 > ()Gii—O fori=1, 2, . . . ,n. v—l G i.__>_0 i=1 CJ Theorem 4. 3. 2: Consider any fiLa: [G ] and the branches of ij v-l TL oriented from (or toward) the common vertex. If and only if a. (l)Gij:0 foriafj (2) G.. _>_ O n fori=l,2,...,v-1, v-1 2 G.. _>_ O i=1 ‘3 then gij _>_ 0. Proof: Sufficiency: Let )1 L 6 be the tree transformation matrix 0. of Figure 2b with branches oriented from from TLa of hypothe81s to TLB or toward the common vertex. The branch matrix for the part of Figure l is j LQB fl La )1 'LaB by Corollary 3. 1.1.1. The possible forms of Lafi are g1ven in Lemma 3. 2. If )1 LaB: :l: u , the theorem follows from Theorem 4. 3.1. For all other cases, jLafijLaJILQB = <-— v_1 ———.-—I G11 012 G1,m-1 {-213 Glj C"1,m+1 G1,v-1 V-l G12 G2.2 G.2,m-1 j-_Z1G2j GZ,m+l G2,v-l v-l v-l v-l v-lv-l v-l v-l ~261. -ZG2. -ZJG . Z Z Gm. -ZG. m+1 -ZG. v-l j=1 J j=1 J j=1 m" m=lj=1 3:1 3’ j=1 3' v-l coo - . 0.0 G G1,v-1 G2,v-1 Gm-l,v-1 j_ZIG_],V-1 Clm+1,v-1 v-1,v-1 31 From (1) and (2) of hypothesis, off-diagonal entries of this last matrix are non-positive and diagonal entries are non-negative. 'lI'he sum v— of the entries in any row n 7! m is -G and in row n = m, is ,§ G , nm J: m3 and by hypothesis, these terms are non-negative. Therefore by Theorem 4. 3. 1, the conclusion follows. Necessity: Let be any branch matrix for the part of Figure 2 LB with the branches of TLB oriented from or toward the common vertex. By hypothesis, fl satisfies the properties of Theorem 4. 3. 1. L I By Corollary 3.1.1.1, J Lfia ”L5 jLBa is the branch matrix for TLC: of hypothesis. Since MLaB of Lemma 3. 2 satisfied )jLaB )Jiagf u ’1 1:043 : M14311 and in general it follows that j LGB : j Lsa' The conclusion follows then by the same argument as used above. 11 4. 3. 2: 'd fl . ' j ' Coro ary Cons1 er any Lo. If and only if Lu is an R-matrix, then gij : 0. Proof: Any possible )6“ Lu can be obtained from a canonical [L — o. by cross-sign changes which correlate with altering the orientations of a TLa which has all orientations from or toward the common vertex, to a TLu with some other pattern of orientation. Therefore, a set of cross- sign changes exists which alters flL into a canonical form and also a alters the orientations of TLa into orientation pattern of TL of Theorem (1 4. 3. 2. Therefore from Theorem 4. 3. 2, the conclusion follows. 32 Theorem 4. 3. 3: Consider any)&i and )flL (1’ the tree trans- formation matrix from T1 to TLa' If and only if; iLo. fli J! iLa is an R-matrix, then gi, >_ 0. -:Proof Since fii is the branch matrix for Pi’ Corollary 3.1.1.1 implies that j iLa fli j iLa is the branch matrix for PLO. . Hence by Corollary 4. 3. 2 the conclusion follows. Corollary 4. 3. 3: Consider any/1&1: Gij]v landjiLa’th tree transformation matrix from T. to T with branches oriented from o. I or toward the common vertex. If and only if, for ’diLa fli J] iLa : [f (G..)] mn 13 v-1’ 1 f < O f 1 ) mn(Gij) _ or m a! n > (2) fmnmij) _ o form: 1, 2, ..., v-l, v--1f Jrli(G J.)_>_0 n=1f then gij _>_ 0. * Proof: The conclusion follows from Theorem 4. 3. 3. Theorem 4.3.4: Consider anyflL and jL i’ the tree transform- a a ation matrix from TLa to Ti. If and only if La is an R- matrix, then all gi, ij associated withaj Laifi La)! Lai are non- negative. Proof: Since fiLa is the branch matrix for PLo,’ Corollary 3. 1. 1. 1 implies that J Lai fiLLQ )j Lai_ =fii is the branch matrix for Pi' -1 Lai iaL conclusion. Since , Theorem 4. 3. 3 and hypothesis implies the Corollary 4. 3. 4: Consider any)Z7i andfij. If and only if all g 11 associated with)&i are non— —negative, then all g ij Jassociated withfij a r e non- negative. 33 I Proof: By Theorem 4.3.3, )J iLo. flij iLu is an'R-matrix. ByCorollary 3.1.1.1 and Theorem 3.2.2, )3 1L“ $1 j iLa = JiLa(/fijflj )Ji'j) Jim: Jingug jija' Therefore the conclusion follows from Theorem 4. 3. 4. Theorem 4. 3. 5: Iffi in = [Giot] andfi 1‘3 = [G3] with rows corresponding to same branches, then . , fling iajo. = [fmn(G:j)] and/J mm 527 113 X? 113113 . [fmn(cfj)]. Proof: This follows from Theorem 3. 2. 1. 4.4 Discussion of Results The sufficiency part of Corollary 4. 3. l is actually a synthesis procedure. A given matrix muSt satisfy (1) and (2) of Corollary 4. 3. 1, that is, be an R-matrix, for it to be realized as the R-graph P . To test a matrix, first simply form, if possible, the canonical form c' The next step is to apply (2.) to J27 c' If both conditions are satisfied, the matrix can be realized as PL and the element values can be determined from (4. 3. 1). The branch orientations can be determined from Theorem 4. 3.1 and Theorem 2. 2.4. By definition 4.1. 2, Gcij = -IGijl for i 7! j, the second relation in (2) of Corollary 4. 3. 1 has the following form. v-l ZG..> ElG..I,i=1,Z, ...,v-l 11— j=1 1] This is the well-known condition of dominance discussed by Burington [2]. That the second relation in (2) of Corollary 4. 3. 1 is that of dominance stems from the fact that the branch equations are identical to the incidence equations for the Lagrangian tree. ~It is not necessary to consider a Lagrangian tree to determine the necessary and sufficient conditions as in TheOrem 4. 3. 1. A procedure similar to that of Theorem 4. 3.1 with a 34 different tree form leads to different expressions [18]. In addition the method implied by Theorem 4. 3. 3 and Corollary 4. 3. 3 can be used to determine the necessary and sufficient conditions for synthesis. For example, the tree transformation matrix from TP to TL, where TP is a path with the e- and pnorientations of all elements coincident and the elements of TL are all oriented toward or away from the common vertex, p—l O O O O O O O —1 H Therefore, showing only the entries above and including the main diagonal, )JPLflPJ'PL: 11- 12'G11 13' 12 G1,v-1'Gl,v—2 (G 2,v-1'Gl,v-1' 2,v-2'G1,v-z) v- 1, v- 1+Gv-Z, v-Z—ZGv-Zv-l By applying (1) and (Z) of Corollary 4. 3. 3, the following conditions are obtained. (1) Gij _>_ 0 for all (i, j) (2)112“: o AY'Z - A?“ > o 1 1 — fori=1, Z, ..., v—1 1 1+1 35 whereAij= G_,- G, _fori;{1, Aj= G .andAv 50. 1 13 1-1,_] 1 13 v-1 These conditions are necessary and sufficient for the realization of a given matrix as PP with the elements of TP oriented so that the e- and p-orien- tations coincide. For an arbitrary orientation pattern the matrix must satisfy (1) and (2) after a finite number of corss-sign changes. If a matrix 127 is to be realized as a v-vertex complete graph by means of a specified tree form Ti' the necessary and sufficient conditions which must be satisfied are implied by Theorem 4. 3. 3. Iffi does not satisfy these conditions, it still may be realized in the required form. Since the row order has not been specified, different arrangements of the entries corresponding to different row orders of must be considered. * Interchanging row i and j and then column i and j of corresponds to interchanging row i and j ofj . The conditions can then be applied to the new branch matrix. If all such matrices do not satisfy the conditions, then the given matrix cannot be realized in the required form. If only the matrix is given, the necessary and sufficient conditions for realization corresponding to each different tree form can be determined and applied to the given matrix or a matrix obtained from the original by interchanging rows 1 and j and columns 1 and j. If the matrix satisfies the conditions associated with any tree form, it can be realized with a part consisting of the union of the particular tree form and a v-vertex complete graph. By considering only the sign pattern of the given matrix, the form of a subgraph of the corresponding tree can be determined by the results of Section 2. 3. For the case that all off—diagonal entries have the same sign, the complete tree can be determined: all positive and all negative correspond to path and Lagrangian trees respectively. By applying cross— sign changes to a given matrix, if the off—diagonal entries are not all positive or all not negative, then the matrix cannot be realized as a path or Lagrangian tree. 36 The necessary and sufficient conditions for realization with a com- plete graph containing five vertices in terms of the three different tree forms are given in Table 1. A necessary condition which is easily checked is the sign requirement indicated. Only one form is indicated since all other sign patterns can be obtained using cross-sign changes. 4. 5 Additional Problems Particular sign patterns of submatrices of a given matrix have been shown to fix the form of subgraphs of the corresponding tree. An extension of this result would be to determine the form of the tree (if it exists) corresponding to an arbitrary arrangement of signs in the given matrix. The necessary and sufficient conditions for realization of a given matrix of order v- 1, as a one part, v vertex graph have been determined. The point of view in the technique used to determine such conditions can be enlarged by proving Theorem 4. 2. Z for an arbitrary tree. Necessary and sufficient conditions for graphs of more than v vertices and multiple part graphs are additional extensions of the above results. 4.9- ..‘3- - 37 Table 1. --:Necessary and Sufficient Conditions for CS. Sign Pattern Tree Form (G.. > 0) 11— Conditions On [Gij]4 . > > > 1 C311—(3'12—(313—61430’ > G44 — G34 3 G24 3- G14 3 0' 2' G2.2 ' G233 G12 ' C'13: 0’ G33 ’ G343 G.23 " G.243 G13 ‘ G1130' 1.0 -G >O,G1-G >0, 11 12— 3 23— > .. G12_0, and (314 (32430. all other , + + > . G <0 17,3. 2 Cu G23 G24.- (31.7.J'G13Jr "— ’ > + + 13 G'14—0’ C'33 623 G3430’ G44+G34+G24:0. 10. 11. 12. LIST OF REFERENCES . Cauer, W. , Synthesis of Linear Communication Networks, Vol. I and II, McGraw-Hill Book Company, Inc., 173-178, 1958. . Burington, R. S., R-matrices and equivalent networks, J. Math. -Phys., Vol. 16, No. 2, 85-103, 1937. .7 Cederbaum, I. , Conditions for the impedance and admittance of N- ports without ideal transformers, Proc. 1. E. E. ,- Part C, Monograph 276R, 1958. . Cederbaum, - I. , On networks without ideal transformers, I. R. E. Trans. on Circuit Theory, Vol.—CY-3, 179-182, 1956. . Talbot, A. , Some fundamental properties of networks without mutual inductance, Proc. I.E.E., Part C, Monograph 118R, 1955. .1 Cederbaum, ' I. , Matrices all of whose elements and subdeterminants are +1, -1, 0. J. Math. Phys. Vol. 36, 351-361, 1958. . Cederbaum, ~ I. , Application of matrix algebra to network theory, I.R. E. Trans. on Circuit Theory, Vol- CT-6, Special suppl. , 127-137, 1959. . Slepian, P. and Weinberg, L. , Applications of paramount and dominant matrices, Proc. N.E.C., Vol. 14, 611-630, 1958. . Guillemin, - E. A. , On the analysis and synthesis of single element- kind networks, I.R.E..Trans. on Circuit Theory, Vol. CT-7, 303-312, 1960. ‘ So, Hing-Cheong. ,v Realization of loop-resistance matrices, Interim Technical Report No. 17,1 Contract No.1DA-ll-022-ORD-1983, U. of 111., 1960. ,Biorci, G. and Civalleri, P. P., On the synthesis of resistive N-port networks, I.R.E. Trans. on Circuit Theory, Vol..CT-8, 1961. Reed, M. B. ,- Foundation for Electric Network Theory, Prentice- Hall,‘ Inc. , 1961. 38 . _ 1... 1:. R~i.'!=t ‘ ”- ‘ 16. 17. 18. 39 . Reed, M. B., Class Notes for E. E. 861, 2, 3, E. E. Dept., Michigan State U. , 1961. . Seshu, S. , and Reed, M. B. , Linear Graphs and Electrical Networks, Addison Wesley Company, Inc. , 1961. . Reed, M. B., The seg: A new class of subgraphs, I.R.E. Trans. on Circuit Theory, Vol. CT—8, 1961. Darlington, S. , A survey of network realization techniques, I. R. E. Trans. on Circuit Theory, Vol. CT—2, 291, 1955. Hohn, F. E. , Elementary Matrix Algebra, The Macmillan Company, 1958. Brown, D. P. , and Tokad, Y. , On the synthesis of R-networks, I.R.E. Trans. on Circuit Theory, Vol. CT—8, 1961. m fihkao ,_.. GD *6 "U ..0 51°50 54% Ho 1—3 (D O 0 0'0 HI LII. ij APPENDIX LIST OF SYM BOLS Desc ription Number of vertices of a graph Trees of a graph Cotree of a graph Connected graphs (Parts) Elements of a tree (branches) Elements of a cotree (chords) f-segs Elements common to f—segs f-seg matrix Unit matrix Non unit submatrix of f-seg matrix Element matrix Branch matrix Canonical form of branch matrix Entries of branch matrix Entries of element matrix 40 “ '57". .._ Gummy LIBRARY IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII .1111111111111111111111