Loading [MathJax]/jax/element/mml/optable/GreekAndCoptic.js

Telegraph systems on networks and port-Hamiltonians. Ⅱ. Network realizability

  • Received: 01 March 2021 Revised: 01 October 2021
  • Primary: 35R02, 05C50; Secondary: 35F46, 05C90

  • Hyperbolic systems on networks often can be written as systems of first order equations on an interval, coupled by transmission conditions at the endpoints, also called port-Hamiltonians. However, general results for the latter have been difficult to interpret in the network language. The aim of this paper is to derive conditions under which a port-Hamiltonian with general linear Kirchhoff's boundary conditions can be written as a system of 2×2 hyperbolic equations on a metric graph Γ. This is achieved by interpreting the matrix of the boundary conditions as a potential map of vertex connections of Γ and then showing that, under the derived assumptions, that matrix can be used to determine the adjacency matrix of Γ.

    Citation: Jacek Banasiak, Adam Błoch. Telegraph systems on networks and port-Hamiltonians. Ⅱ. Network realizability[J]. Networks and Heterogeneous Media, 2022, 17(1): 73-99. doi: 10.3934/nhm.2021024

    Related Papers:

    [1] M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer . On algebraic graph theory and the dynamics of innovation networks. Networks and Heterogeneous Media, 2008, 3(2): 201-219. doi: 10.3934/nhm.2008.3.201
    [2] Regino Criado, Julio Flores, Alejandro J. García del Amo, Miguel Romance . Structural properties of the line-graphs associated to directed networks. Networks and Heterogeneous Media, 2012, 7(3): 373-384. doi: 10.3934/nhm.2012.7.373
    [3] Valérie Dos Santos, Bernhard Maschke, Yann Le Gorrec . A Hamiltonian perspective to the stabilization of systems of two conservation laws. Networks and Heterogeneous Media, 2009, 4(2): 249-266. doi: 10.3934/nhm.2009.4.249
    [4] Alexandre M. Bayen, Alexander Keimer, Nils Müller . A proof of Kirchhoff's first law for hyperbolic conservation laws on networks. Networks and Heterogeneous Media, 2023, 18(4): 1799-1819. doi: 10.3934/nhm.2023078
    [5] Steinar Evje, Kenneth H. Karlsen . Hyperbolic-elliptic models for well-reservoir flow. Networks and Heterogeneous Media, 2006, 1(4): 639-673. doi: 10.3934/nhm.2006.1.639
    [6] Alessandro Gondolo, Fernando Guevara Vasquez . Characterization and synthesis of Rayleigh damped elastodynamic networks. Networks and Heterogeneous Media, 2014, 9(2): 299-314. doi: 10.3934/nhm.2014.9.299
    [7] Dilip Sarkar, Shridhar Kumar, Pratibhamoy Das, Higinio Ramos . Higher-order convergence analysis for interior and boundary layers in a semi-linear reaction-diffusion system networked by a $ k $-star graph with non-smooth source terms. Networks and Heterogeneous Media, 2024, 19(3): 1085-1115. doi: 10.3934/nhm.2024048
    [8] Nathaniel J. Merrill, Zheming An, Sean T. McQuade, Federica Garin, Karim Azer, Ruth E. Abrams, Benedetto Piccoli . Stability of metabolic networks via Linear-in-Flux-Expressions. Networks and Heterogeneous Media, 2019, 14(1): 101-130. doi: 10.3934/nhm.2019006
    [9] José Ignacio Alvarez-Hamelin, Luca Dall'Asta, Alain Barrat, Alessandro Vespignani . K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases. Networks and Heterogeneous Media, 2008, 3(2): 371-393. doi: 10.3934/nhm.2008.3.371
    [10] Alessia Marigo, Benedetto Piccoli . A model for biological dynamic networks. Networks and Heterogeneous Media, 2011, 6(4): 647-663. doi: 10.3934/nhm.2011.6.647
  • Hyperbolic systems on networks often can be written as systems of first order equations on an interval, coupled by transmission conditions at the endpoints, also called port-Hamiltonians. However, general results for the latter have been difficult to interpret in the network language. The aim of this paper is to derive conditions under which a port-Hamiltonian with general linear Kirchhoff's boundary conditions can be written as a system of 2×2 hyperbolic equations on a metric graph Γ. This is achieved by interpreting the matrix of the boundary conditions as a potential map of vertex connections of Γ and then showing that, under the derived assumptions, that matrix can be used to determine the adjacency matrix of Γ.



    In this paper we study systems of linear hyperbolic equations on a bounded interval, say, (0,1), sometimes referred to as port-Hamiltonians, see for example [14], and the role is played by the boundary conditions coupling the incoming and outgoing Riemann invariants determined by the system at the endpoints x=0 and x=1. In particular, we consider the set of equations

    t(υϖ)=(C+00C)x(υϖ),0<x<1,t>0, (1a)
    Ξ(υ(0,t),ϖ(1,t),υ(1,t),ϖ(0,t))T=0,t>0, (1b)
    υ(x,0)=˚υ(x),ϖ(x,0)=˚ϖ(x)0<x<1, (1c)

    where υ and ϖ are the Riemann invariants flowing from 0 to 1 and from 1 to 0, respectively, C+ and C are m+×m+ and m×m diagonal matrices with positive entries and, with 2m=m++m, Ξ is a 2m×4m matrix relating outgoing υ(0),ϖ(1) and incoming υ(1),ϖ(0) boundary values so that (1b) can be written as

    Ξout(υ(0,t),ϖ(1,t))T+Ξin(υ(1,t),ϖ(0,t))T=0,t>0. (2)

    An important class of such problems arises from dynamical systems on metric graphs. Let Γ be a graph with r vertices {vj}1jr=:Υ and m edges {ej}1jm (identified with (0,1) through a suitable parametrization). The dynamics on each edge ej is described by

    tpj+Mjxpj=0,0<x<1,t>0,1jm, (3)

    where pj=(pj1,pj2)T and Mj=(Mjlk)1k,l2 are defined on [0,1] and Mj(x) is a strictly hyperbolic real matrix for each x[0,1] and 1jm. System (3) is complemented with initial conditions and suitable transmission conditions coupling the values of pj at the vertices which the edges ej are incident to. Then, (1) can be obtained from (3) by diagonalization so that (suitably re-indexed) υ and ϖ are the Riemann invariants (see [7,Section 1.1]) of p=(pj)1jm.

    Such problems have been a subject of intensive research, both from the dynamics on graphs, [1,10,5,4,11,17,19], and the 1-D hyperbolic systems, [7,21,15,14], points of view. However, there is hardly any overlap, as there seems to be little interest in the network interpretation of the results in the latter, while in the former the conditions on the Riemann invariants seem to be "difficult to adapt to the case of a network", [11,Section 3].

    The main aim of this paper, as well as of the preceding one [2] is to bring together these two approaches. In [2] we have provided explicit formulae allowing for a systematic conversion of Kirchhoff's type network transmission conditions to (1b) in such a way that the resulting system(1) is well-posed. We also gave a proof of the well-posedness on any Lp, 1p<, which, in contrast to [21], is purely based on an operator semigroup approach. For notational clarity, we focused on 2×2 hyperbolic systems on each edge but the method works equally well for systems of arbitrary (finite) dimension. In this paper we are concerned with the reverse question, that is, to determine under what assumptions on Ξ, (1) describes a network dynamics given by 2×2 hyperbolic systems on each edge, coupled by Kirchhoff's transmission conditions at incident vertices.

    To briefly describe the content of the paper, we observe that if the matrix Ξ={ξij}1i2m,1j4m in (1b) describes transmission conditions at the vertices of a graph, say Γ, on whose edges we have 2×2 systems of hyperbolic equations, then we should be able to group the indices j into pairs {j,j"} corresponding to the edges of Γ on which we have 2×2 systems for the components j and j" of (υ,ϖ). Thus, in a sense, the columns of Ξ determine the edges of Γ. It follows that it is easier to split the reconstruction of Γ into two steps and first build a digraph Γ, where each column index j of Ξ is associated with an arc, say εj, on which we have a first order system for either υj or ϖj. Thus, the main problem is to construct vertices of Γ (and Γ) which should be somehow determined by a partition of the row indices of Ξ. To do this, we observe that the coefficients of Ξ represent a map of connections of the edges in the sense that, roughly speaking, if ξij0 and ξik0, then arcs εj and εk are incident to the same vertex and, if they are incoming to it, then they cannot be incoming to any other vertex. A difficulty here is that while for the flow to occur from, say, εj to εk, these arcs must be incident to the same vertex but the converse may not hold, that is, for εj incoming to and εk outgoing from the same v, the flow from εj may not enter εk but go to other outgoing arcs. To avoid such a case, in this paper we formulate conditions ensuring that the flow connectivity at each vertex is the same as the graph connectivity. This assumption yields a relatively simple criterion for the reconstruction of Γ, which is that

    ^(^Ξout)T^Ξin

    is the adjacency matrix of a line graph (where for a matrix A, ˆA is obtained by replacing non-zero entries of A by 1.) This, together with some technical assumptions, allows us to apply the theory of [13], see also [6,Theorem 4.5.1], to construct first Γ and then Γ in such a way that (2) can be localized at each vertex of Γ in a way which is consistent with (1a).

    The main idea of this paper is similar to that of [3]. However, [3] dealt with first order problems with (2) solved with respect to the outgoing data. Here, we do not make this assumption and, while(1) technically is one-dimensional, having reconstructed Γ, we still have to glue together its pairs of arcs to obtain the edges of Γ in such a way that the corresponding pairs of solutions of (1a) are Riemann invariants of 2×2 systems on Γ. Another difficulty in the current setting is potential presence of sources and sinks in Γ. Their structure is not reflected in the line graph, [3], and reconstructing them in a way consistent with a system of 2×2 equations on Γ is technically involved.

    The paper is organized as follows. In Section 2 we briefly recall the notation and relevant results from [2]. Section 3 contains the main result of the paper. In Appendix we recall basic results on line graphs in the interpretation suitable for the considerations of the paper.

    We consider a network represented by a finite, connected and simple (without loops and multiple edges) metric graph Γ with r vertices {vj}1jr=:Υ and m edges {ej}1jm. We denote by Ev the set of edges incident to v, let Jv={j;ejEv} and |Ev|=|Jv| be the valency of v. We identify the edges with unit intervals through sufficiently smooth invertible functions lj:ej[0,1]. In particular, we call v with lj(v)=0 the tail of ej and the head if lj(v)=1. On each edge ej we consider the system (3). Let λj<λj+ be the eigenvalues of Mj,1jm (the strict inequality is justified by the strict hyperbolicity of Mj). The eigenvalues can be of the same sign as well as of different signs. In the latter case, we have λj<0<λj+. By fj±=(fj±,1,fj±,2)T we denote the eigenvectors corresponding to λj±, respectively, and by

    Fj=(fj+,1fj,1fj+,2fj,2),

    the diagonalizing matrix on each edge. The Riemann invariants uj=(uj1,uj2)T,1jm, are defined by

    uj=(Fj)1pjandpj=(fj+,1uj1+fj,1uj2fj+,2uj1+fj,2uj2). (4)

    Then, we diagonalize (3) and, discarding lower order terms, we consider

    tuj=Ljxuj=(λj+00λj)xuj, (5)

    for each 1jm.

    Remark 1. We refer an interested reader to [7,Section 1.1] for a detailed construction of the Riemann invariants for a general 1D hyperbolic system and the explanation of the name.

    The most general linear local boundary conditions at vΥ are given by

    Φvp(v)=0, (6)

    where p=((pj1,pj2)1jm)T and the real matrix Φv is given by

    Φv:=(ϕj1v,1φj1v,1ϕj|Jv|v,1φj|Jv|v,1ϕj1v,kvφj1v,kvϕj|Jv|v,kvφj|Jv|v,kv),  (7)

    where Jv={j1,,j|Jv|} and kv is a parameter determined by the problem. The difficulty with such a formulation is that it is not immediately clear what properties Φv should have to ensure well-posedness of the hyperbolic problem for which (6), vΥ, serve as boundary conditions. There are various ways tackling this difficulty. For example, in [20,11] conditions are imposed directly on Φv to ensure specific properties, such as dissipativity, of the resulting initial boundary value problem. However, we follow the paradigm introduced in [7,Section 1.1.5.1] and require that at each vertex all outgoing data must be determined by the incoming data. Since for a general system (3) it is not always obvious which data are outgoing and which are incoming at a vertex, we write (6) in the equivalent form using the Riemann invariants u=F1p, as

    Ψvu(v):=ΦvF(v)u(v)=0. (8)

    For Riemann invariants, we can define their outgoing values at v as follows.

    Definition 2.1. Let vΥ. The following values ujk(v),jJv,k=1,2, are outgoing at v.

    If
    none
    none

     | Show Table
    DownLoad: CSV

    Denote by the number of positive eigenvalues on . Then, we see that for a given vertex with valence the number of outgoing values is given by

    (9)

    Definition 2.2. We say that is

    ● a sink if either and or and for all ;

    ● a source if either and or and for all ;

    ● a transient (or internal) vertex if it is neither a source nor a sink.

    We denote the sets of sources, sinks and transient vertices by and , respectively.

    We observe that if , then (so that no boundary conditions are imposed at a sink), while if , then .

    A typical example of (8) is Kirchhoff's law that requires that the total inflow rate into a vertex must equal the total outflow rate from it. Its precise formulation depends on the context, we refer to [8,Chapter 18] for a detailed description in the context of flows in networks. Since it provides only one equation, in general it is not sufficient to ensure the well-posedness of the problem. So, we introduce the following definition.

    Definition 2.3. We say that satisfies a generalized Kirchhoff conditions at if, for (8) is satisfied for some matrix with given by (9).

    To realize the requirement that the outgoing values should be determined by the incoming ones, we have to analyze the structure of . Let us introduce the partition

    (10)

    where if if and if . This partition induces the corresponding partition of each as

    We also consider another partition where if and if . Then, we can give an alternative expression for as

    (11)

    Then, by [2,Lemma 3.6],

    is outgoing if and only if

    is outgoing if and only if

    is outgoing if and only if

    is outgoing if and only if

    We introduce the block diagonal matrix

    (12)

    where

    Further, by we denote the contraction of ; that is, the matrix obtained from by deleting zero columns, and then define as the analogous contraction of .

    In a similar way, we extract from the outgoing boundary values by

    and As above, we define to be the vector in obtained by discarding the zero entries in , as described above and, similarly, is the vector in obtained from .

    Proposition 1. [2,Proposition 3.8] The boundary system (8) at is equivalent to

    (13)

    and hence it uniquely determines the outgoing values of at as defined by Definition 2.1 if and only if

    (14)

    In this case,

    (15)

    To pass from (3) with Kirchhoff's boundary conditions at each vertex to(1) we have to write the former in a global form. Assuming the vertices in are ordered as , we define and and write (8) as

    (16)

    We note that the function values that are incoming at do not influence any outgoing data. However, to keep the track of all vertex values, we extend with zero columns corresponding to edges coming to sinks and denote such an extended matrix by . Since, by the hand shake lemma, we have and by [2,Section 3.2] also is a matrix. In the same way, we can provide a global form of (13), splitting (16) as

    (17)

    where and extended by zero columns corresponding to the incoming functions at the sinks, , and is extended by incoming values at the sinks.

    Using the adopted parametrization and the formalism of Definition 2.1, we only need to distinguish between functions describing the flow from to and from to . Accordingly, we group the Riemann invariants into parts corresponding to positive and negative eigenvalues and rename them as:

    (18)

    where and are the sets of indices with at least 1 positive eigenvalue, and at least 1 negative eigenvalue of , respectively. In (respectively ) the indices from (respectively ) appear twice so that we rearrange them in some consistent way to avoid confusion. For instance, we can take and and there are bijections between and , and , and , and and , respectively. We emphasize that such a renumbering is largely arbitrary and different ways of doing it result in just re-labelling of the components of(1) without changing its structure.

    In this way, we converted into a multi digraph with the same vertices , in such a way that each edge of was split into two arcs parametrized by where on each arc corresponds to the same vertex in and the same is valid for . Conversely, if we have a multi digraph where all edges appear in pairs and each two edges joining the same vertex are parametrized concurrently, then we can collapse to a graph . We note that this approach originates from [16].

    Using this construction, the second order hyperbolic problem (3), (17) was transformed into first order system (1) with (17) written in the form (2). However, it is clear that (1) can be formulated with an arbitrary matrix . Thus, we arrive at the main problem considered in this paper:

    how to characterize matrices that arise from so that (1) describes a network dynamics?

    For a graph , let us consider the multi digraph constructed above. The sets of vertices are the same for and . For of we can talk about incoming and outgoing arcs which are determined by and the signs of and , as in Definition 2.1. We denote by and the (ordered) sets of indices of arcs incoming and outgoing from in , respectively. We note that , the number of the outgoing conditions. With this notation, the matrix can be split into two matrices

    Since no outgoing value should be missing, we adopt the following

    Assumption 1. No column or row of is identically zero.

    These matrices provide some insight into how the arcs are connected by the flow which is an additional feature, superimposed on the geometric structure of the incoming and outgoing arcs at the vertex. In principle, these two structures do not have to be the same, that is, it may happen that the substance flowing from , is only directed to some of the outgoing arcs. An extreme case of such a situation is when both and are completely decomposable, see [9], with blocks in both matrices having the same row indices. Then, from the flow point of view, can be regarded as several nodes of the flow network, which are not linked with each other. Such cases, where the geometric structure at a vertex is inconsistent with the flow structure, may generate problems in determining the graph underlying transport problems. Thus in this paper we adopt assumptions ensuring that the map of the flow connections given by the matrices and coincides with the geometry at . We begin with the necessary definitions.

    Definition 3.1. Let . We say that an arc , flow connects to if and for some

    Using this idea, we define a connectivity matrix by

    Remark 2. We observe that

    ● the above definition implies that for and to be flow connected, and must be incident to the same vertex;

    can be interpreted as the adjacency matrix of the bipartite line digraph constructed from the incoming and outgoing arcs at where the connections between arcs are defined by flow connections, see [9,Section 3].

    For an arbitrary matrix by we denote the matrix with every nonzero entry of replaced by 1.

    Lemma 3.2. If is a transient vertex, then

    (19)

    Proof. Denote Then, if and only if

    This occurs if and only if there is such that both and which is equivalent to flow connecting with , that is, .

    Let be a source (as we do not impose boundary conditions on sinks). As above, we need to ensure that the flow from a source cannot be split into several isolated subflows. Though here we do not have inflows and outflows, we use a similar idea to that for transient vertices.

    Definition 3.3. Let . We say that and , are flow connected if there is such that and

    As before, we construct a connectivity matrix where

    (20)

    Note that, contrary to an internal vertex, here the connectivity matrix is symmetric. We also do not stipulate that so that is always flow connected to itself and hence, by Assumption 1, each entry of the diagonal of is 1. From this, we get a result similar to Lemma 3.2.

    Lemma 3.4. If is a source,

    (21)

    Proof. As before, let Then, if and only if

    Certainly, by Assumption 1, For , this occurs if and only if there is such that both and which is equivalent to and being flow connected, that is, .

    We adopt an assumption that the structure of flow connectivity is the same as of the geometry at the vertex. Thus, if is an internal vertex and and , then flow connects to . In particular, we have

    Assumption 2. For all ,

    We observe that the dimension of is .

    If , then we assume that the outflow from cannot be separated into independent subflows, that is, that the arcs outgoing from cannot be divided into groups such that no arc in any group is flow connected to an arc in any other. Equivalently, for each two arcs and , there is a sequence such that and , are flow connected. Indeed, if such a division was possible, then it would be impossible to find such a sequence between indices and in different groups as some pair would have to connect arcs from these different groups. Conversely, if for some arcs and there is no such a sequence, then we can build two groups of indices containing and , respectively, by considering all indices for which such sequences can be found. Clearly, no arc in the first group is flow connected to any arc in the second as otherwise there would be a sequence connecting and . By Lemma 3.4, can be considered as the adjacency matrix of the graph with vertices given by and the edges determined by the flow connectivity (20). Moreover, is symmetric, which shows that the assumption described at the beginning of this paragraph is equivalent to

    Assumption 3. For all is irreducible.

    Remark 3. Assumption 3 is weaker than requiring each two arcs from to be flow connected. Then we would have

    Proposition 2. Let . If the system (8), that is,

    (22)

    contains a Kirchhoff's condition

    (23)

    with for all and some , then Assumption 2 is satisfied.

    Proof. Condition (23) ensures that each entry of the -th row of both and is 1 and thus the product of each column of with each column of is non-zero, which yields Assumption 2.

    Example 1. Consider the model of [20], analysed in the framework of our approach in [2,Example 5.12], i.e.,

    (24)

    for where for all . For a given vertex we define if and if and In this case for any and thus for any vertex we need boundary conditions. We focus on with . Then, we split into of dimension and its orthogonal complement of dimension and require that

    that is, denoting and ,

    (25)

    where is a basis in and is a basis in It is clear that, in general, boundary conditions (25) do not satisfy Assumption 2. Consider such that each incident to is parameterised so as so that each is outgoing and each is incoming. If we take and for , we obtain

    Thus and are both the identity matrices and Assumption 2 is not satisfied.

    On the other hand, the Kirchhoff condition,

    (26)

    see [20,Eqn (4)], satisfies the assumption of Proposition 2, as we have

    where we used [2,Eqn 5.2]. Hence, by Proposition 2, Assumption 2 is satisfied.

    Example 2. Let us consider the linearized Saint-Venant system,

    (27)

    see [2,Example 1.2], assuming that on each edge we have . Then, we have

    (28)

    We use the flow structure of [11,Example 5.1], shown in Fig. 1, and focus on where we need boundary conditions which were given as

    Figure 1. 

    Starlike network of channels

    .

    In terms of the Riemann invariants, they can be written as

    and it is clear that Assumption 2 is satisfied.

    Figure 2. 

    The reconstructed multi digraph . It is seen that it cannot describe a flow on as and must flow in the same direction

    .
    Figure 3. 

    The reconstructed multi digraph for (46), (47)

    .
    Figure 4. 

    A network realizing the flow (48), (49)

    .

    For a matrix let us denote by the columns of and by its rows. Then, we often write

    (29)

    that is, we represent the matrix as a row vector of its columns or a column vector of its rows. In particular, we write

    For any vector , we define .

    Definition 3.5. We say that the problem (1) is graph realizable if there is a graph and a grouping of the column indices of into pairs such that (1a) describes a flow along the edges of , which satisfies generalized Kirchhoff's condition at each vertex of . In other words, (1) is graph realizable if there is a graph and a matrix such that (1a), (1c) can be written, after possibly permutating rows and columns of as (5), (17).

    Before we formulate the main theorem, we need to introduce some notation. Let us recall that we consider the boundary system (2), i.e.,

    Let us emphasize that in this notation, the column indices on the left and right hand side correspond to the values of the same function. To shorten notation, let us renumber them as . As noted in Introduction, appropriate pairs of the columns would determine the edges of the graph that we try to reconstruct, hence the first step is to identify the possible vertices of . For this, first, we will try to construct a multi digraph on which (2) can be written in the form (17) for . Roughly speaking, this corresponds to and being composed (up to permutations) of non-communicating blocks corresponding to the vertices. Here, each should correspond to an arc and the column on the left hand side corresponds to the outflow along from a unique vertex, while the column on the right hand side corresponds to the inflow along to a unique vertex. The vertices of should be then determined by a suitable partition of the rows of (and of ).

    In the second step we will determine additional assumptions that allow to be collapsed into a graph on which (2) can be written in the form (17).

    Since we do not want (2) to be under- or over-determined, we adopt

    Assumption 4. For all ,

    Our strategy is to treat and as the outgoing and incoming incidence matrices of a multi digraph with vertices 'smeared' over subnetworks of flow connections. Thus we have

    Assumption 5. The matrix

    is the adjacency matrix of the line graph of a multi digraph.

    For , let and be groups of row and column indices, respectively, potentially outgoing from (respectively incoming to) a vertex, see Appendix A. We introduce

    and adopt

    Assumption 6. For all there exists such that

    In the next proposition we shall show that and determine a partition of the row indices into sets that can be used to define vertices. The idea is that if supports of columns of or overlap, the arcs determined by these columns must be incident to the same vertex.

    Proposition 3. If Assumptions 4, 5 and 6 are satisfied, then the sets

    (30)

    where

    (31)
    (32)

    form a partition of the row indices of both and such that if for any , for some , then and if for any , for some , then

    Since the proof is quite long, we first present its outline.

    Step 1. Reconstruct a multi digraph from the adjacency matrix of its line graph.

    Step 2. Identify the rows of which are zero in and which correspond to sources and associate them with vertices.

    Step 3. Associate other rows of which are zero in with appropriate vertices.

    Step 4. Associate remaining rows with vertices and construct a possible partition of the row indices.

    Step 5. Check that the constructed partition has the required properties.

    Proof. Step 1. By Assumption 5, is the adjacency matrix of for some multi digraph . As explained in Appendix A, we can reconstruct with the transient vertices defined in a unique way and admissible sources and sinks. Let us fix such a construction. Then, we have the sets and of incoming and outgoing arcs determining any transient vertex. Further, we have (possibly) the sets and that group the arcs incoming to sink(s) and outgoing from source(s), respectively. Since represents all arcs, the same decomposition is valid for and , that is, we have subdivisions and of the columns of and , respectively, and hence the correspondence of the columns with the vertices. Thus, we have to show that (30) is a partition of the rows of and satisfying the conditions of the proposition.

    Let us recall that the entry of is defined by

    and if a row of is zero, that is, it represents a source, then there is a zero row in . Indeed, since, by Assumption 4, , there is a nonzero entry, say, and thus we must have for any . So, to every zero row in there corresponds a zero row in . However, there may be other zero rows in .

    Step 2. To determine the rows in , corresponding to sources, we consider Assumption 6. First, we note that any of that assumption, if it exists, is determined in a unique way as the sets are not overlapping. Next, we observe that if and , then . Indeed, if and , then which implies Thus we can define the set

    For any and we have as otherwise there would be a nonzero product for some as for each . Then, let there be such that for some . This means, by Assumption 6, that and hence . Consider any nonzero element of say, . By the above argument, . If , then . If not, for some which contradicts Assumption 6. Thus, satisfies the first part of the statement. The second part is void as there is no with Therefore, all indices that is, such that determine a source as there is no connection to any inflow.

    Step 3. Now, consider the indices . Then, again by Assumption 6, for any there is a unique such that , that is, such an belongs to the vertex determined by . This determines a partition of corresponding to the vertices (recall that there are no zero rows in and so each row must belong to a vertex).

    Step 4. Next, we associate the remaining rows in and with the vertices. Consider and for some and defined by (A.2). The non-zero entries of , where and , occur whenever . Hence, the rows with indices must belong to a vertex through which the incoming arc communicates with the outgoing arc . Since all nonzero entries in and , respectively, reflect non-zero outflow along and inflow along , respectively, and must belong to the same vertex. Since the same is true for any indices from and , plausible partitions of row indices of and defining vertices are

    We first observe that if and determine the same transient vertex, then

    (33)

    Indeed, let . Then, there is such that . Since , there is such that and thus . Hence, and consequently . The converse can be proved in the same way by using Assumption 4 since if then, by construction, must belong to a support of some and thus cannot be in . As we see, if contains rows with , then these rows satisfy . If we add the indices of such rows to with determining the same vertex as , then such an extended will be equal to and thus we use can use (30) to denote the partition of into .

    Step 5. We easily check that this partition satisfies the conditions of the proposition. We have already checked this for . So, let for some , then there is such that . Clearly, by the construction of . If , then by Assumption 6 and hence . If , then for some but then also and hence , yielding and consequently Similarly, if , then there is for some . But then, immediately from the definition, by (33).

    We note that (30) does not contain rows corresponding to sinks and they must be added following the rules described in Appendix A. With such an extension, we consider the multi digraph , determined by

    (34)

    where the association is defined in (A.2). By construction, if we take the triple , , it determines a transient vertex, the outgoing arcs given by the indices of columns in and the incoming arcs given by the indices of columns in . Similarly, the pair determines the sources and all outgoing arcs, while the set of incoming arcs is empty. Thus, if we denote by and the submatrices of and consisting of the rows with indices in and columns in and , respectively, with an obvious modification for , then (2) decouples into (or ) independent systems

    (35)

    This system can be seen as a Kirchhoff system on the multi digraph but we need to collapse to a graph on which (35) can be written as (17). We observe that the question naturally splits into two problems – one is about collapsing the graph, while the other is about grouping the components of into pairs compatible with the parametrization of .

    Let be the adjacency matrix of , with Assumptions 4 and 6 satisfied. As in Appendix A, we can construct outgoing and incoming incidence matrices and but these are uniquely determined only if there are no sources and sinks. However, we have an additional piece of information about sources.

    If we grouped all sources into one node, as before Proposition 5, then, by Lemma 3.4, the flow connectivity in this source would be given by

    However, such a matrix would not necessarily satisfy Assumption 3. Thus, we separate the arcs into non-communicating groups, each determining a source satisfying Assumption 3. For this, by simultaneous permutations of rows and columns, can be written as

    (36)

    where may equal 1. Since the simultaneous permutation of rows and columns is given as where is a suitable permutation matrix, [18,p. 140], we see that is a symmetric matrix, along with . By [12,Sections III 1 and Ⅲ 4], is irreducible if and only if it cannot be transformed by simultaneous row and column permutations to the form (36) with (since is symmetric, all off-diagonal blocks must be zero). Then, can be reduced to the canonical form, [12,Section Ⅲ,Eq. (68)], in which each is irreducible. If (36) is in the canonical form, then we say that allows for sources, each satisfying Assumption 3. The indices of the columns contributing to the blocks define the non-communicating sources in , which we denote , . Finally, define by

    For the sinks, it is simpler as there is no constraining information from (2). We have columns with indices in corresponding to sinks. These are zero columns in but the columns with these indices in have nonempty supports and thus we can determine from which vertices they are outgoing. Let us denote

    (37)

    For each we consider a partition

    (38)

    where into non-overlapping sets , . Then, we define sinks as the heads of the arcs with indices from ; we have sinks. Then, as above, define by

    Remark 4. We expect to be even numbers and (38) to represent a partition of into pairs so that

    Then, as in Remark 5, the incoming and outgoing incidence matrices are

    which, by a suitable permutation of columns moving the sources and the sinks to the last positions, can be written as

    (39)

    respectively. Both matrices have columns and rows. Hence, as shown in Remark 5, the adjacency matrix of the full multi digraph is given by

    (40)

    where the dimensions of the blocks in the first row are, respectively, , and , in the second row, , and and in the last one, , and . Thus, if is in the block then will be in the block .

    Consider a nonzero pair of entries of . If, say, , then it means that the -th row of and -th row of have entry 1 in the same columns, that is, there are exactly arcs coming from to . Similarly, if , then there are exactly arcs coming from to . Conversely, if there are arcs from to and arcs from to , then In particular, if and only if there are two arcs between and running either concurrently or countercurrently. Since the columns of and are indexed in the same way as that of and , the pair determines the rows and of and thus the indices

    (41)

    of columns of (and of ). Finally, we are ready to formulate the main result of this paper.

    Theorem 3.6. System (2) is graph realizable with generalized Kirchhoff's conditions satisfying Assumptions 1 and 2 for and Assumption 3 for if and only if, in addition to Assumptions 4, 5 and 6, there is a partition (38) such that defined by (40) satisfies

    1. for any , and is in one of the following form:

    (42)

    2. if determines the indices and according to (41), then

    (43)

    Proof. Necessity. Let us consider the Kirchhoff system (17). By construction, both matrices and are in block diagonal form with equal row dimensions of the blocks. We consider the problem already transformed to . We note that each arc's index must appear twice in – once in and once in (if there are sinks, the indices of incoming arcs will correspond to the zero columns). Further, whenever column indices and appear in the blocks of and , respectively, then is incoming to, while is outgoing from the same vertex (and not any other). Thus, by Assumption 2, the matrix

    is block diagonal with blocks of the form except for zero rows corresponding to the sources and zero columns corresponding to the sinks. However, in general, the column indices in and do not correspond to the indices of the arcs they represent. Precisely, if and only if there is a vertex for which the arc is incoming and is outgoing, where and are the indices of the arcs that correspond to the columns and of and , respectively. To address this, we construct and as

    where and are permutation matrices, so that in both matrices the column indices correspond to . Hence

    is a matrix where the indices of both the columns and the rows correspond to . Since did not have loops, it is clear that for all It is also clear that any two columns (or rows) of are either equal or orthogonal and this property is preserved by permutations of columns and of rows. Hence, by Proposition 4, is the adjacency matrix of a line digraph and hence Assumption 5 is satisfied. Since the arcs' connections given by and are the same, we see that is equal to the adjacency matrix of the line graph of . Therefore, the transient vertices determined by are the same as in (and hence in ). On the other hand, as we know, does not determine the structure of sources and sinks in . The fact that Assumption 4 is satisfied is a consequence of Assumption 1. For Assumption 6, we recall, see Appendix A, that the sets group together the indices representing arcs outgoing from a single vertex, thus they correspond to the blocks in the matrix and therefore Assumption 6 is satisfied, even for any . Next, since has been constructed from , the structure of the blocks in corresponding to sources ensures that, after permutations, their entries will coincide with and thus (36) will hold with the blocks in (36) exactly corresponding to the sources in on account of Assumption 3. Similarly, in the sinks are determined and thus we have groupings of pairs of the arcs (a partition of the set of indices corresponding to arcs incoming to sinks) coming from transient vertices or sources to sinks and thus the constructions (39) and (40) are completely determined. Then, we observe that whenever we have a source , then the arcs outgoing from must be coming in pairs with a single pair coming from to any other possible vertex, meaning that the respective entry in must be either or Similar argument holds for the sinks. Since the problem comes from a graph, by construction, the orientation of the flows is consistent with the parametrization.

    Sufficiency. Given (2), we have flows defined on Assumptions 4, 5 and 6 ensure, by Proposition 3, the existence of a multi digraph on which (2) can be localized to decoupled systems at vertices and written as (35). Precisely speaking, Assumption 5 associates the indices of incoming components of the solution at a vertex with incoming arcs and similarly for the indices of the outgoing components. Therefore, if an arc runs from to , then the flow occurs from to , that is, if , then the flow on is given by with at and at and analogous statement holds for . In other words, the index of the arc running from to determines the orientation of the parametrization: and if and and if

    Now, (42) ensures that there are no loops at vertices and that between any two vertices there are either two arcs or none. If is an entry in , or , then or and, by the dimensions of the blocks, and , respectively. On the other hand, if is an entry in , then it can take any value or and the equals or , , respectively. Thus, double arcs indexed, say, by between vertices could be combined into edges of an undirected graph (with no loops and multiple edges). However, in this way we construct a combinatorial graph which does not take into account that if and are combined into one edge of , their orientations must be the same. Thus, if determines the pair of indices according to (43), then both arcs and of run from to and the components and of the solution flow concurrently along . By assumption, or . In the first case, we associate with 0 and with 1 and we have on , in agreement with the orientation. Otherwise, we associate with 1 and with 0 and we have on . On the other hand, if then, by assumption, either and or and and the components and flow countercurrently. Again, in the first case, and running from to requires to be associated with 0 and with 1, while and running from to also requires to be associated with 0 and with 1. Thus, we have on . Otherwise, we associate with 1 and with 0 and we have on .

    Finally, the assumption in the first case of assumption (43) ensures that the resulting system is hyperbolic on each edge.

    Example 3. Let us consider the system

    (44)

    where with boundary conditions

    (45)

    Thus,

    Thus, there is a multi digraph for which is the adjacency matrix of . There is no sink and to determine the structure of the sources, we observe that

    This matrix is irreducible and thus we have one source. Therefore

    and consequently

    Further,

    hence, by (41),

    To reconstruct , we see that and should be combined into a single edge . However, since the flow along runs from 1 to 0 and hence should correspond to 1 in the parametrization, while to 0. On the other hand, runs also from 1 to 0 but from to and hence should correspond to 1, while to 0. This contradiction is in agreement with the violation of assumption (43) as but in the corresponding , both and belong to .

    Consider a small modification of (44), (45),

    (46)

    , with the last two boundary conditions of (45) accordingly changed to

    (47)

    The matrices and are the same as above and thus the multi digraph is the same as before. However, this time on we have the flow , occurring from 0 to 1 and thus and can be combined with a parametrization running from at to at . Assuming , , we identify and write (46) as a system of hyperbolic systems on a graph of the form

    (48)

    with boundary conditions at

    (49)

    Consider a digraph (possibly with multiple arcs but with no loops) and its line graph . For both and we consider their adjacency matrices and . The matrix is always binary, with zeroes on the diagonal. Not any binary matrix is the adjacency matrix of a line graph, see [3,6]. In fact, we have

    Proposition 4. [6,Thm. 2.4.1] A binary matrix is the adjacency matrix of a line digraph of a multi digraph if and only if all diagonal entries are 0 and any two columns (equivalently rows) of are either equal or orthogonal (as vectors).

    For our analysis, it is important to understand the reconstruction of from a matrix satisfying the above conditions. As in (29), we write

    If for some we have then it means that join and thus they must be incident to the same vertex and all for which (and thus all for ) are outgoing from . We further observe that all zero rows can be identified with source(s). Similarly, zero columns correspond to sinks. If for some , then connects a source to a sink.

    Using the adjacency matrix of a line digraph, we cannot determine how many sources or sinks the original graph could have without additional information. We can lump all potential sources and sinks into one source and one sink, we can have as many sinks and sources as there are zero columns and rows, respectively, or we can subdivide the arcs into some intermediate arrangement. We describe a construction with one source and one sink and indicate its possible variants.

    We introduce and, inductively, and the process terminates at such that . In the same way, and and the process terminates at such that . In other words, and represent the vertices of through incoming and outgoing arcs, respectively. If there are any zero rows in , then we swap the corresponding set with the last set . In this way, represents all arcs outgoing from sources (if they exist). For this construction, we represent them as coming from a single source but other possibilities are allowed, see Remark 5. Similarly, if there are any zero columns, we swap the corresponding set with , that is, represents the arcs incoming to sink(s). Then, we denote

    (A.1)

    Thus, we see that the number of internal (or transient) vertices, that is, which are neither sources nor sinks is . For such vertices it is important to note that, in general, and do not represent the same vertex. To combine and into the same vertex, we have, for ,

    (A.2)

    With this notation, we present a more algorithmic way of reconstructing from . First, we collapse equal rows of into a single row of and equal columns of into a single column and then take the transpose to get . Mathematically, let be a set of indices such that consists of exactly one point for each and ordered by the order of . Similarly, let be a set of indices such that consists of exactly one point for each We order consistently with , namely, if and are the -th indices in and , respectively, then and with related to by (A.2), that is, determines the same vertex . As mentioned above, possible zero rows correspond to the highest indices. With this, we define

    (A.3)

    We see now that each row of corresponds to a vertex and each column of corresponds to an incoming arc. If there are zero rows in , there is a zero row at the bottom of showing the presence of a (single) source. The presence of a sink is indicated by zero columns in . Similarly, each row of corresponds to a vertex with arcs outgoing from it represented by nonzero entries in this row, in columns with indices corresponding to the indices of the arcs. If there are zero columns in , they appear as a zero row in , which represents a (single) sink. Possible sources are visible in as zero columns. However, what is important is that even though we lumped all sources and sinks into one single source and a single sink, the zero columns in and keep track of the arcs going into the sink or out of the source, respectively. Unless there are no sources and sinks, and are not the incoming and outgoing incidence matrices of a graph (for the definition of these, see e.g. [3]). Indeed, does not contain sinks that, clearly, are part of the incoming incidence matrix. Similarly, does not include sources. If we keep our requirement that there is only one sink and one source, then we add one row to and one to to represent the sink and the source, respectively. We use convention that, if both the sink and the source are present, the source is the last but one row and the sink is the last one. To determine the entries we use the required property of the incidence matrices, that there is exactly one non-zero entry in each column (expressing the fact that each arc has a unique tail and a unique head). Thus, we put 1 in the added rows in any column that was zero in (resp. ). We denote such extended matrices by and . It is easy to see that the following result is true.

    Proposition 5. and are, respectively, incoming and outgoing incidence matrices of a multi digraph having as the adjacency matrix of .

    Proof. Since each column of and contains 1 only in one row, we can construct a multi digraph from them using as its adjacency matrix. Since we allow to be a multi digraph, the entries of give the number of arcs joining the vertices. A entry in is given by and, by construction, is a row in belonging to and is a column in corresponding to . Nonzero entries in correspond to the arcs incoming to and nonzero entries in correspond to the arcs outgoing from so the value of is the number of nonzero entries occurring at the same places in both vectors and thus the number of arcs from to .

    The adjacency matrix is determined as . The entries of this product are given by . Since each column has only one nonzero entry (equal to 1), the product will be either 0 or 1. It is 1 if and only if there is (exactly one) such that the entry 1 appears as the -th coordinate of both and Now, by construction, if and only if and if and only if where the correspondence between and is determined by (A.2). This is equivalent to .

    Remark 5. Assume that has zero rows and zero columns. We cannot identify the numbers of sinks and sources from without additional information. Above, we lumped all sources and all sinks into one source and one sink, respectively, but sometimes we require more flexibility. As we know, the zero rows in become zero columns in associated with the arcs outgoing from sources. In a similar way, the zero columns in stay to be zero columns in associated with the arcs incoming to sinks. We can group these arcs in an arbitrary way, with each group corresponding to a source or a sink, respectively. Assume we wish to have sources and sinks. Then, we build the corresponding matrix by adding zero rows for the sources to and rows corresponding to sinks, which will consist of zeroes everywhere apart from the columns that were zero columns in ; in these columns we put 1s in such a way that each column contains only one nonzero entry (and zeroes elsewhere). Then, columns having 1 in a particular row will represent the arcs incoming to a given sink. In exactly the same way we extend , by creating zero rows for the sinks and rows for the sources. In this way, we construct the following incoming and outgoing incidence matrices, respectively, and that, by a suitable permutation of columns, can be written as

    where is the required permutation matrix and, in both cases, the first group of columns have indices corresponding to (resp. ), the second group corresponds to the arcs incoming from the sources to the transient vertices, the third group combines arcs connecting sources and sinks and the last group corresponds to the sinks fed by the transient vertices. We observe that the number of columns in each group in and is the same. Since

    as , see [18,p. 140], for such a digraph we have

    (A.4)

    Example 4 Consider the networks and presented on Fig. 5. We observe that grouping of sources and sinks does not affect the line graph, see Fig. 6. To illustrate the discussion above, we have

    (A.5)
    Figure 5. 

    Multi digraphs with 3 sources and two sinks and with all sources and all sinks grouped into a single source and a single sink

    .
    Figure 6. 

    The line digraph for both and

    .

    Then,

    (A.6)

    and we see that there are two transient (internal) vertices and with arcs and incoming to and arcs and are incoming to The last row in corresponds to source(s) with outgoing arcs and . We also note that the zero columns in correspond to arcs and that are incoming to sinks. To build , we first collapse the identical columns of and take the transpose. We see from that the first row of the transpose corresponds to the incoming arcs and and thus also to vertex of Hence, there is no need to re-order the rows and so (A.3) gives

    (A.7)

    The last row corresponds to sinks and the zero columns inform us that arcs and emanate from sources.

    If we want to reconstruct the original graph with one source and one sink, then

    and

    which describes the right multi digraph in Fig. 5. On the other hand, we can consider two sinks (maximum number, as there are two zero columns in ) and, say, three sources. Then,

    and

    which describes the left multi digraph in Fig. 5.

    It is easily seen that both digraphs have the same line digraph, shown on Fig. 6, whose adjacency matrix is .



    [1]

    F. Ali Mehmeti, Nonlinear Waves in Networks, vol. 80 of Mathematical Research, Akademie-Verlag, Berlin, 1994.

    [2]

    J. Banasiak and A. Bƚoch, Telegraph systems on networks and port-Hamiltonians. I. Boundary conditions and well-posednes, Evol. Eq. Control Th., 2021.

    [3] Some transport and diffusion processes on networks and their graph realizability. Appl. Math. Lett. (2015) 45: 25-30.
    [4] Semigroup approach to diffusion and transport problems on networks. Semigroup Forum (2016) 93: 427-443.
    [5] Asymptotic behaviour of flows on reducible networks. Netw. Heterog. Media (2014) 9: 197-216.
    [6]

    J. Bang-Jensen and G. Z. Gutin, Digraphs: Theory, Algorithms and Applications, Springer Science & Business Media, London, 2008.

    [7]

    G. Bastin and J.-M. Coron, Stability and Boundary Stabilization of 1-D Hyperbolic Systems, vol. 88, Springer, 2016.

    [8]

    A. Bátkai, M. Kramar Fijavž and A. Rhandi, Positive Operator Semigroups. From Finite to Infinite Dimensions, vol. 257 of Operator Theory: Advances and Applications, Birkhäuser, Cham, 2017.

    [9] Bigraphs versus digraphs via matrices. J. Graph Theory (1980) 4: 51-73.
    [10] The semigroup approach to transport processes in networks. Phys. D (2010) 239: 1416-1421.
    [11]

    M. K. Fijavž, D. Mugnolo and S. Nicaise, Linear hyperbolic systems on networks: Well-posedness and qualitative properties, ESAIM Control Optim. Calc. Var., 27 (2021), Paper No. 7, 46 pp.

    [12]

    F. R. Gantmacher, Applications of the Theory of Matrices, Interscience Publishers, Inc., New York; Interscience Publishers Ltd., London, 1959.

    [13]

    R. Hemminger and L. Beineke, Line graphs and line digraphs, in Selected Topics in Graph Theory I (eds. L. Beineke and R. Wilson), Academic Press, London, 1978,271–305.

    [14] -semigroups for hyperbolic partial differential equations on a one-dimensional spatial domain. J. Evol. Equ. (2015) 15: 493-502.
    [15]

    B. Jacob and H. J. Zwart, Linear Port-Hamiltonian Systems on Infinite-Dimensional Spaces, vol. 223 of Operator Theory: Advances and Applications, Birkhäuser/Springer Basel AG, Basel, 2012.

    [16] The flow approach for waves in networks. Oper. Matrices (2012) 6: 107-128.
    [17]

    P. Kuchment, Quantum graphs: An introduction and a brief survey, in Analysis on Graphs and its Applications, vol. 77 of Proc. Sympos. Pure Math., Amer. Math. Soc., Providence, RI, 2008,291–312.

    [18]

    C. D. Meyer, Matrix Analysis and Applied Linear Algebra, vol. 71, SIAM, Philadelphia, 2000.

    [19]

    D. Mugnolo, Semigroup Methods for Evolution Equations on Networks, Understanding Complex Systems, Springer, Cham, 2014.

    [20] Control and stabilization of hyperbolic systems on graphs. Math. Control Relat. Fields (2017) 7: 53-72.
    [21] Well-posedness and regularity of hyperbolic boundary control systems on a one-dimensional spatial domain. ESAIM Control Optim. Calc. Var. (2010) 16: 1077-1093.
  • This article has been cited by:

    1. Jacek Banasiak, Adam Błoch, Telegraph systems on networks and port-Hamiltonians. Ⅲ. Explicit representation and long-term behaviour, 2022, 11, 2163-2480, 2165, 10.3934/eect.2022016
    2. Adam Bobrowski, Elżbieta Ratajczyk, Pairs of complementary transmission conditions for Brownian motion, 2024, 388, 0025-5831, 4317, 10.1007/s00208-023-02613-x
  • Reader Comments
  • © 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1144) PDF downloads(219) Cited by(2)

Figures and Tables

Figures(6)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog