{'fraction_non_alphanumeric': 0.039441464552238806, 'fraction_numerical': 0.007346082089552239, 'mean_word_length': 4.526824552924118, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Computing Different Realizations of Linear Dynamical Systems with Embedding Eigenvalue Assignment∗

In this paper we investigate realizability of discrete time linear dynamical systems (LDSs) in fixed state space dimension. We examine whether there exist different Θ = (A,B,C,D) state space realizations of a given Markov parameter sequence Y with fixed B, C and D state space realization matrices. Full observation is assumed in terms of the invertibility of output mapping matrix C. We prove that the set of feasible state transition matrices associated to a Markov parameter sequence Y is convex, provided that the state space realization matrices B, C and D are known and fixed. Under the same conditions we also show that the set of feasible Metzler-type state transition matrices forms a convex subset. Regarding the set of Metzler-type state transition matrices we prove the existence of a structurally unique realization having maximal number of non-zero off-diagonal entries. Using an eigenvalue assignment procedure we propose linear programming based algorithms capable of computing different state space realizations. By using the convexity of the feasible set of Metzler-type state transition matrices and results from the theory of non-negative polynomial systems, we provide algorithms to determine structurally different realization. Computational examples are provided to illustrate structural non-uniqueness of network-based LDSs.


Introduction
Many problems in computer science and engineering involve sequences of real-valued multivariate observations. It is often assumed that observed quantities are correlated with some underlying latent (state) variables that are evolving over time. Considering linear dependencies among the latent states and the observed variables leads us to linear dynamical systems. The application of linear systems is ubiquitous, ranging from dynamical systems modeling to time series analysis, including econometrics, meteorology, telecommunication, biomedical signal processing, or social network dynamics [15,23,35,30,17]. The aim of system identification is to construct parameterized models of dynamical systems by observing their input-output trajectories [22,37]. A popular and theoretically advantageous method for estimating the parameters of linear dynamical systems is the maximum likelihood method together with expectation maximization or numerical optimization [31,25,16,10]. Although the underlying mathematical representation of linear systems is simple, due to the fact that the associated optimization problem to be solved might be non-convex, estimating their parameters could be a computationally challenging task [16]. A related problem, structural identifiability examines the theoretical possibility to uniquely determine the model parameters, assuming perfect observational data [37,24,3]. It turns out that even in the case of linear dynamical systems, the underlying parameters may not be uniquely determined, i.e. different parameterizations of the same model structure may provide us with the same dynamical behavior.
One can observe a growing interest in both quantitative and qualitative examination of the underlying interconnected structure of dynamical systems [7,20,32,4,34]. There is a growing importance of large scale distributed engineering systems, such as power grids, distributed computing networks and intelligent transportation networks that are composed of smaller functional subunits. The interconnected structure corresponding to the state variables has attracted much attention in the context of physico-chemical systems such as chemically interacting species composing systems biological networks: gene regulatory networks, protein-protein interaction networks, metabolic networks and signal transduction pathways [36,38]. Analyzing the locally connected structure of social networks could help us understand how viruses and information spread across the population [5,26,28,29]. Subsystems, functional units are locally connected to each other according to some physical interaction topology encoded by their differential equation based description. The distributed, locally connected structure of dynamical systems poses important requirements towards efficient computational approaches, e.g. distributed controller synthesis methods over traditional centralized control algorithms [33,9]. It can be observed in many dynamical systems that the underlying network structure is topologically non-unique i.e., different interconnection (graph) patterns can be encoded by the same dynamical equations [1,2]. Naturally, the non-uniqueness of the network structure implies that the dynamical system is structurally nonidentifiable.
Main results: In this paper we investigate realizability and structural properties of discrete time linear time invariant dynamical systems. We examine structural implications of non-unique realizability on the interaction pattern of the state variables as they are encoded in the state transition matrix. We examine the non-uniqueness of state transition matrix of LDSs. Assuming fixed input matrix B and invertible observation matrix C we prove that the feasible set of system matrices formulate a convex set. We devote particular attention to LDSs of state transition matrices that are constrained to be of Metzler property. We prove the convexity of the feasible set of state transition matrices provided that the Metzler constraint is posed. Using the eigenvalue assignment procedure we formulate a convex optimization based procedure that can be efficiently employed to find different realizations of LDSs. Assuming the Metzler property and making use of the convexity of the feasible set of system matrices we provide algorithms capable of determining structurally different dynamically equivalent state space realizations.

Mathematical notations
The notations used in the paper are summerized in Table 1 below. the set of real numbers R n×m the set of (n × m)-dimensional real valued matrices 0 n×m (n × m)-dimensional zero matrix [A] ij the entry in the ith row of the jth column of matrix A subtraction operator acting on a set and a matrix, A A is the set given by subtracting the matrix A from all the elements of A

The studied system class and its properties
A discrete time linear dynamical system (LDS) in state space representation is given by a tuple Θ = (A, B, C, D) and the associated system of difference equations (DEs) is as follows: where A ∈ R n×n , B ∈ R n×m , C ∈ R p×n and D ∈ R p×m . x(k) ∈ R n denotes the vector of state variables, u(k) ∈ R m and y(k) ∈ R p are the input and the associated output of the system. Though the solution associated to a particular parametrization Θ and initial condition x 0 is unique, the parameters characterizing the underlying dynamics are not necessarily. There may exist distinct Θ, Θ parametrizations of the same inputoutput behavior meaning that the system is not structurally identifiable. Definition 1. A system of the form of E.q. (1) is said to be structurally (globally) identifiable, if for any admissible input u(k) and k ≥ 0 we have that where y(k|Θ) denotes the output of the system E.q. (1) parametrized by Θ.
If the condition of structural identifiability does not hold, the system is said to be structurally non-identifiable.
In case of structural non-identifiability, in order to quantitatively characterize the system, it is appealing to describe the feasible set of possible parameters. A quantitative characterization of the feasible set may help us finding realizations of favorable properties, such as sparsity.
Definition 2. It is said that a tuple Θ = (A , B , C , D ) is a (dynamically equivalent) realization of a LDS of the form E.q. (1) parametrized by Θ, if Θ provides the same input-output behavior, i.e. y(k|Θ ) = y(k|Θ) for any admissible input signal u(k), k ≥ 0.
By recursively expanding E.q. (1) one can obtain the input-output equationsa common starting point of system identification -of the following form: where the terms Y k−i−1 = CA k−i−1 B and D are called the Markov parameters of the systems which are unique descriptors of the input-output behavior and are invariant to any invertible state transformations. Since Markov parameters are unique regarding the input-output behavior, we can formulate sufficient and necessary condition of dynamical equivalence with respect to the Markov parameters as follows: a tuple Θ = (A , B , C , D ) is a dynamically equivalent realization of

Problem setup
A related problem of structural non-identifiability of LDSs is the existence of distinct, A, A ∈ R n×n state transition matrices having different patterns in their non-zero entries, i.e. structurally different state transition matrices. Assuming that E.q. (1) describes the dynamical behavior of a network-based system, the state transition matrix A can be viewed as a weighted adjacency matrix characterizing the interactions -in terms of both the interaction pattern and the magnitudes -among the components, i.e. state variables. Such a way structural non-uniqueness of a network topology can be recast as an identification problem, namely finding structurally different n-dimensional state space realizations.
In this work we concerned with the existence different realizations of LDSs and focus on the non-uniqueness and structure of the feasible state transition matrices.
Assumptions Throughout this paper we assume that a LDS is given by a state space realization Θ = (A, B, C, D) and the matrices B, C and D are fixed over all the dynamical equivalent realizations of interest. We set C to be invertible. Regarding the initial condition we assume x(0) = 0 n .
By fixing the matrices B, C and D we explicitly restrict our attention to dynamically equivalent realizations with different system matrices, but fixed input and output patterns. This is particularly important in the context of network-based dynamical systems where different state transition matrices incorporate distinct interaction patterns of the system components. We note that the invertibility of C covers the case of fully observable state variables.
Making use of the Markov parameter based description together with the above assumptions, the following constraint set can be employed in order to express dynamical equivalence of different realizations: One difficulty with respect to the above constraint set is that generally we have a countable set of Markov parameters Y = {Y k } k≥0 implying infinitely many constraints of the from E.q. (3). On the other hand, the terms CA k B are non-linear and are not convex in the entries of A -even for stable systems of nilpotent state transition matrices -which could easily make the identification problem computationally intractable.
In this paper identifiability of the above defined class of LDSs is studied. We wish to quantitatively characterize the feasible set of state transition matrices in the studied class of LDSs. We also address the problem of determining structurally different n-dimensional realizations of a LDS given by a particular initial state space realization Θ.

Embedding eigenvalue assignment procedure
In this section a static full-output feedback based approach is used for stabilizing a LDS and constructing a compressed set of closed-loop Markov parameters. The procedure detailed here is known as embedding eigenvalue procedure and applied in LDS identification to recover the Markov parameters [27,18].
Let us take a LDS of E.q. (1). By taking an arbitrary M ∈ R n×n we can reformulate Eq. (1) as follows: Then for the state equation we have Let us introduce the following matrices and new input variable Then the state space model Eq. (1) can be reformulated in the following equivalent form: Now by recursively expanding E.q. (9) the input-output behavior can be expressed as If M can be chosen so that A = A + M C is a stability matrix, then for the Markov parameters asympthotically we have In this case, E.q. (10) can be approximated as for a suitably high p ∈ N. In particular, if A + M C is set to be nilpotent, then (A + M C) n = 0 n×n holds. Note that such a stabilizing M matrix exists, if the system E.q. (1) is observable. Such a way the countable set of Markov It can be shown that the system Markov parameters Y can be uniquely recovered from that of the closed-loop system Y of E.q. (4) as follows: [27,18]: where for k ≥ 1.

Representing different realizations using a compressed set of Markov parameters
In this section we show that dynamic equivalence of n-dimensional LDS realizations can be traced back to a finite set of linear equations. We make use of the eigenvalue assignment procedure, such a way instead of a countable set of Markov parameters Y one can consider a compressed set of n Markov parameters Y of a (stabilized) closed-loop system. By an inductive proof a linear reformulation of the non-convex equations of E.q. (3) is provided. We also show the existence of a bijection between the original state space realizations and the closed-loop system realizations.
Making use of the embedding eigenvalue assignment procedure we can obtain a finite set of compressed system descriptors Y = {Y k } n−1 k=0 which is unique with respect to the closed-loop system. Finding different realizations of Y can be recast in the form of a finite set of non-linear equations: Note that the nilpotency of A implies that the nth equation is equivalent to holds for any feasible n-dimensional realization Θ = (A , B, C, D) of Y.
Proof. Let us assume that Θ = (A , B, C, D) is a dynamically equivalent realization of Y we have that By induction assume that for some k > 1 the equation Making use of Proposition 1 the constraint set defined by E.q. (3) can be equivalently reformulated as CA k B = CA A k−1 B for k ≥ 0 which are linear in A . Similarly one can formulate a finite set of linear constraints for the closed-loop system: By equipping E.q. (17) with a linear objective function c : R n×n → R, we obtain a linear program of the decision variables A , e.g.: Such a way a computational model is provided to determining dynamically equivalent realizations (A, B, C, D) of the closed-loop system Y = {CA k B} n k=1 . Furthermore, the feasible set of solutions of the linear program (18) provides all the dynamically equivalent realizations of Y. We note that in the optimization problem (18) the decision variables are the entries of the matrix A , i.e. the number of decision variables is n 2 where n is the dimension of the system. Now it can be shown that the resulted closed-loop state transition matrix A can be used to reconstruct an n-dimensional realization of the open loop system E.q. (1) described by the initial countable set of Markov parameters. for some A, M ∈ R n×n and B ∈ R n . Assume that there exists Proof. For the sake of convenience we introduce the following notations The geometrical structure of the set of feasible system matrices In this section we consider the set of feasible n-dimensional system matrices. We prove that for fixed B, C and D parameters, the set of feasible system matrices with respect to any Y Markov sequence is convex. The set of feasible system matrices is denoted as follows: Proposition 3. Let us consider a countable sequence of Markov parameters Y realizable by a state space realization (A, B, C, D) of order n and denote A(Y, B, C, D) the set of feasible n-dimensional system matrices as it is defined by E.q. (19).
Proof. Let us consider two matrices A 1 , A 2 ∈ R n×n so that (A 1 , B, C, D) and (A 2 , B, C, D) are realizations of Y. From Proposition 1 it follows that for any a ∈ (0, 1) In the sequel for the sake of convenience we use the notationÂ = aA 1 + (1 − a)A 2 . Now by induction we prove that CA k B = CÂ k B for k ≥ 1.
For l = 1 we have Using the inductive assumption CA l B = CÂ l B for general l we obtain that We have that any convex combination 6 Characterizing structurally different system realizations In this section we consider realizations of special structure in their state transition matrices. The off-diagonals are constrained to be non-negative. State transition matrices having non-negative off-diagonal entries are particularly important when the purpose is to model networks of interacting components: non-zero off-diagonal entries could represent the magnitude of interactions while negative diagonals may incorporate to information or mass leakage. Positive systems -in which all the entries of the state transition matrix are constrained to be non-negative -compose a widely-studied class of linear time invariant systems with the above structural properties [8]. Discrete time linear compartmental models -having many applications in modeling biological systems -also satisfy the above non-negativity condition [14,13]. Social networks provide an important application field of modeling discrete time dynamical systems defined on networks [26,28,29,21]. The DeGroot and Friedkin-Johnsen models are well-known discrete time linear models of opinion dynamics and information spreading in networks where the off-diagonal entries of state transition matrices are also constrained to be non-negative [6,11]. Formally, for a Markov sequence Y we restrict our attention to realizations Θ = (A, B, C, D) so that A is Metzler, i.e. [A] ij ≥ 0 for i = j. Then the feasible set of state transition matrices can be defined as follows: Note that the convexity of A p (Y, B, C, D) is guaranteed as a corollary of Proposition 3 which can be seen as follows. For any A 1 , A 2 ∈ A p (Y, B, C, D), the convex combination aA 1 + (1 − a)A 2 with a ∈ (0, 1) is a feasible state transition matrix in A(Y, B, C, D). Since a convex combination is a linear combination with nonnegative coefficients, the sign of the off-diagonal entries remain non-negative, i.e. A p (Y, B, C, D) is convex. Now with respect to the set A p (Y, B, C, D) we identify matrices having distinguished structural properties and show how they relate to all the other feasible state transition matrices.
In order to ease the discussion of structural properties state transition matrices, we introduce a simple graph-based description of LDSs with state transition matrices of Metzler-type using the analogy of influence graphs in the literature of positive systems [8]. Considering a state transition matrix A ∈ R n×n , the associated directed graph representation G(A) = (E, V ) is defined as follows. V , the set of nodes corresponds to the set of states of the associated LDS. E, the set of edges represents the influences between state variables, i.e. (i, j) ∈ E if and only if [A] ij > 0. Such a way G(A) provides a unique description of the structure of A.
In the sequel the term structure of a state transition matrix A ∈ A p (Y, B, C, D) refers to the structure (topology) of the associated directed graph representation G(A) as it is defined above.  Proof. Assume that there exists a dense state transition matrix A d ∈ A p (Y, B, C, D) so that A d has no superstructure property. Then it follows that there exists a state transition matrix A ∈ A p (Y, B, C, D) for which there is an index-pair (i, j), i = j so that [A] ij > 0, but [A d ] ij = 0. The convexity of A p (Y, B, C, D) guarantees that for any a ∈ (0, 1) the resulted matrix A = aA+(1−a)A d provides a dynamically equivalent realization with non-negative off-diagonal entries, i.e. A ∈ A p (Y, B, C, D). Such a way we obtained a state transition matrix A having more non-zero offdiagonal entries, than A d has, which is contradiction. Corollary 1. Let us consider a Markov sequence Y. For any B ∈ R n×m , C ∈ R p×n and D ∈ R p×m , there exists a structurally unique state transition matrix A d having maximal number of non-zero off-diagonal entries with respect to A p (Y, B, C, D).

Computational framework for finding structurally different realizations
In this section first we assume a state space realization Θ = (A, B, C, D) so that its respective Markov parameter sequence Y is of finite-length, i.e. CA k B = 0 n×m , k ≥ p for some finite p. Examining the realizability of finite-length Markov sequences can be motivated by a partial realization problem or realizability analysis of stable and damping systems having only a finite number of non-zero Markov parameters [27,12]. Algorithms for determining structurally different realizations of LDS with respect to A p (Y, B, C, D) are provided. Making use of the convexity of A p (Y, B, C, D), we adopt algorithms proposed for mass action law kinetic systems and show that structurally different realizations regarding the feasible set of Metzler system matrices A p (Y, B, C, D) can be efficiently obtained [1]. We prove that a dense state transition matrix A d in A p (Y, B, C, D) can be computed in polynomial time using a convex optimization based procedure. Then it can be also shown that all the structurally different realizations of A p (Y, B, C, D) can be determined by iteratively computing constrained dense realizations.
Finally we show that using the eigenvalue assignment procedure, the proposed algorithms can be extended to compute structurally different realizations of LDSs of arbitrary Markov parameter sequences.

Algorithm for computing dense realization
Here we provide an algorithm capable of finding a dense realization with respect to A p (Y, B, C, D) in polynomial time, given that Y is a finite sequence. The correctness of the algorithm follows from the convexity of A p (Y, B, C, D). First we define a subroutine denoted by FindRealization in order to determine feasible state transition matrices.
P denotes the set of ordered pairs encoding the non-zero pattern of A so that (i, j) ∈ P iff [A ] ij > 0. If feasible realization A does not exist, it returns (0 n×n , ∅).
Next we introduce Algorithm 1 (FindDenseRealization) for finding a dense dynamically equivalent realization, given a state space model Θ = (A, B, C, D).   return -1 //There is no feasible realization. 19: end if iteratively finds constrained dense realizations. Such a way all distinct structure can be obtained.
Assuming a fixed ordering of the state variables, we introduce the notation R to denote the set of binary sequences of length (n × n) − n encoding the structure of non-zero off-diagonal patterns of the system matrices. The i'th entry of R ∈ R is denoted by R[i]. An edge e is in the graph G(A) iff there exists an index i ∈ 1 . . . |E(G(A))| for which e = e i and R[i] = 1.
We introduce the array Exist of 2 |R| binary variables such that Exist[R] = 1 iff there exists a dynamically equivalent realization encoded by the sequence R ∈ R.
A stack S is employed to temporarily store tuples of the form (R, k) with R ∈ R and k ∈ N. The command 'push (R, k) into S' pushes the tuple (R, k) into S, while 'pop from S' returns the last tuple (R, k).
We say that the binary relation = k holds between the sequences R, W ∈ R The equivalence class of the relation = k for which R is a representative element is denoted by C k (R). Note that for an equivalence class more representative elements may exist. The following subroutines are employed in the algorithm: 1. FindDenseRealizationSequence(Θ = (A, B, C, D), R, k, i): computes a dense state transition matrix A d with respect to A p (Y, B, C, D), given a se-quence R ∈ R and k, i ∈ N. It returns a feasible state transition matrix A ∈ A p (Y, B, C, D) and the associated binary sequence W ∈ R so that W = k R and for every W [j] = 0 for j = k + 1, . . . i. If such a reaction does not exist returns -1.
Note that FindDenseRealizationSequence can be implemented by means of FindDenseRealization.

Extension to arbitrary LDS
This section extends the aforementioned results in order to find structurally different realizations of arbitrary LDS. We consider a LDS Θ = (A, B, C, D) so that there are no constraints on Y = {CA k B} k≥0 . Assuming that the pair (A, C) is observable, the eigenvalue assignment procedure can be employed. Then there exists M ∈ R n×n so that A = A + M is nilpotent, i.e. A n = 0.
Consider the linear program

Computational examples
In this section we provide examples to illustrate structural non-uniqueness of the non-zero off-diagonal patterns of state transition matrices associated to a Markov sequence Y. By some simple linear dynamical system models we show that the set of feasible state transition matrices A(Y, B, C, D) is not necessary unique and structurally different dynamically equivalent realizations can be computed. Throughout the section we restrict our attention to realizations with system matrices of Metzlertype.
In each example, first the system is stabilized by a full-state feedback M using the algorithm of [19] in order to obtain a closed-loop system of the form of E.q. (4) with a finite sequence of non-zero Markov parameters Y. In Example 8.1 Algorithm 1 and 2 are employed to determine all the structurally different realizations with respect to A p (Y, B, C, D). Then Proposition 2 guarantees that structurally different realizations of the open-loop system Y can be recovered by subtracting M from the closed-loop system matrices. Example 8.2 illustrate the structural non-uniqueness of a social network equipped with a linear dynamical behavior. Indirect sparsity and density constraints are employed in order to find different realizations.

Example 1
Let us consider the following system C is an (n × n)-dimensional identity matrix and D = 0 n . A full-output feedback M is obtained by the algorithm [19]. Then using Algorithm 2 we determined all the structurally different closed-loop system matrices in A p (Y, B, C, D). Finally a set of structurally different state transition matrices with respect to A p (Y, B, C, D) is computed by A p (Y, B, C, D) M . Figure 1 depicts the number of structurally different realizations as the function of the number of non-zero off-diagonal entries in the state transition matrix. Table  2 provides a set of structurally different realizations in A p (Y, B, C, D) as they are determined in the above described way.  The non-uniqueness of the network structure has important theoretical and practical consequences. It turned out that the system is structurally non-identifiable, that is the same dynamical behavior can be realized with different parameterizations. At the same time, a computational procedure is provided to test structural non-identifiability with theoretical guarantee. Non-uniqueness of the underlying network topology is a specific case of the lack of structural identifiability: the underlying dynamical behavior is realizable with different sets of interconnections of the state variables. The existence of different network structures is particularly important if the state variables have some biological, physical or chemical meaning: the same dynamical behavior (functionality) can be implemented using different relationships between the system variables.

Example 2
The Zachary karate club network is a widely studied social network representing the interactions of 34 members outside a Karate club [39]. Here we study the information flow across the network equipped with a particular weighted directed edge set as it is depicted in Figure 2. The weighted directed edges can be uniquely encoded in the form of an adjacency matrix A ∈ R 34×34 , assuming a fixed ordering of the nodes, i.e. state variables. For the entries of A see Appendix 9. With the chosen edge directions we wish to simulate the information flow from the direction of the first node, i.e. x 1 (source) to the last nodes, x 33 and x 34 (sinks).
We make use of the adjacency matrix A of the network to define the dynamics of information flow over the nodes and formulate a simple LDS of the from E.q.
(1). The adjacency matrix A defines the state transition matrix, [A] ij > 0 iff there is direct information flow from node j to node i. B ∈ R 34 is set to be zero for all the entries except for the first one which is equal to 1, i.e. In order to find a dynamically equivalent realization of the stabilized system Θ with Metzler-type state transition matrix and sparsity constraint, we solved the following optimization procedure where the entries of A correspond to the decision variables. Denoting the solution of (27) by A s , Proposition 2 guarantees thatÂ s = A s − M provides a dynamically equivalent realization of the initial system. The obtained realization (Â s , B, C) has 78 non-zero off-diagonal entries and its graph representation G(Â s ) is isomorph to that of the initial state transition matrix G(A). Next a dense realization (A d , B, C) is computed with respect to the closed-loop system Θ using Algorithm 1. Proposition 2 guarantees thatÂ d = A d −M determines a dynamically equivalent realization with respect to the initial system Θ. We found that the obtained state transition matrixÂ d contains 451 non-zero off-diagonal entries. The obtained matricesÂ s andÂ d are illustrated in Figure 3. G(A s ) and G(A d ) are isomorph to G(Â s ) and G(Â d ), respectively. Such a way we can put indirectly sparsity and density constraints to state transition matrices of LDS having arbitrary Markov parameters. However, it is important to note that the resulted state transition matricesÂ s andÂ d are not proved to be sparse and dense with respect to the initial system Θ, i.e. there may exist dynamically equivalent realizations having less or more non-zero off-diagonal entries, respectively. The existence of structurally different realizations implies that the Karate club network equipped with the above dynamical system model is structurally nonidentifiable. The particular importance of the example is that the same dynamical behavior, that is information propagation among the nodes, is feasible with structurally different network topologies. Different interconnections can provide the same emergent dynamical behavior described by a DTLTI system. The result underlines that a certain network topology, even in the case of linear systems, might not be a complete descriptor of the modeled process. Note that the initial and sparse matrices are equivalent in terms of the pattern of their non-zero off-diagonal entries, i.e. G(A) and G(Â s ) are isomorph graphs. We emphasize that sparsity, as a structural property, is understood with respect to the off-diagonal entries. The existence of structurally different state transition matrices implies that the same information propagation dynamics can emerge in structurally different networks.

Conclusion
In this paper we considered realizability of discrete time linear dynamical systems. Throughout the paper it is assumed that a LDS is given by a Markov parameter sequence Y and that the state space realization matrices B, C and D are known and fixed. Under these assumptions the existence of different realizations of Y is equivalent to the existence of distinct state transition matrices of the same dimension that provides the same sequence Y. Assuming that the state space realization matrix C is invertible, we quantitatively characterized the set of feasible state space realizations. It is proved that the set of state transition matrices A(Y, B, C, D) associated to a Markov sequence Y is convex, given B, C and D matrices. Under the same conditions it is also shown that the subset of Metzler-type system matrices A p (Y, B, C, D) is convex. Furthermore, we proved that there exists a structurally unique state transition matrix A d ∈ A p (Y, B, C, D) of maximal number of offdiagonal entries whose respective graph representation G(A d ) contains that of any other feasible state transition matrix in A p (Y, B, C, D) as subgraph.
Making use of the eigenvalue assignment procedure, we reformulated dynamical equivalence of state space realizations in terms of a finite set of linear constraints in the entries of the state transition matrix. This way we proposed a convex optimization based algorithm that can be used to find different realizations of any Markov sequence. Since the existence of different system matrices implies structural non-identifiability of the underlying dynamical system, this way non-identifiability of LDSs can be validated in fixed state space dimension in polynomial time. By making use of the convexity of A p (Y, B, C, D) and adopting results from the field of non-negative polynomial systems, we provided algorithms that can determine structurally different realizations of LDSs with respect to Metzler-type state transition matrices. Representative examples are presented in order to illustrate that dynamically equivalent realizations of LDSs are not necessary structurally unique, i.e. there may exist structurally different realizations of the same LDS even in the case of fixed B, C and D state space realization matrices.
Proof of Proposition 6.
Proof. Let us assume that there exists a sequence V ∈ R encoding a feasible state transition matrix which is not returned by the algorithm FindAllRealizations. Then consider the sequence R for which R = p V and p is maximal. If p = 0 then the encoding sequence of the dynamically equivalent dense realization is an appropriate choice for R. For i = FindNextOne(R, p) and j =FindNextOne(V, p) we have i ≤ j, since V ∈ C p (R). Moreover if i = j then it follows that p is not the maximal integer such that R = p V which is a contradiction. Let us consider the sequence W 1 returned by FindReal(R, p, i). There exists a dynamically equivalent realization encoded by W 1 , since the input constraints of FindReal(R, p, i) are fullfilled by V . For W 1 we get that j 1 = FindNex-tOne(W 1 , p) for some j 1 ∈ Z >0 . Then the inequality j 1 ≤ j must hold, since V ∈ C i (W 1 ). If j 1 = j then it would follow that R is not that sequence for which V ∈ C p (R) holds with a maximal p, i.e. j 1 = j is a contradiction. There is a step in the algorithm FindAllRealizations when the sequence W 2 is computed by FindDenseRealizationSequence(Θ = (A, B, C, D), R, p, j 1 ). For W 2 we have that V ∈ C j1 (W 2 ) which implies that j 2 ≤ j for j 2 = FindNex-tOne(R, p, j 1 ). If j = j 2 would hold, then j 2 would be the maximal integer with the sequnece W 2 for which W 2 = j2 V holds, but this is a contradiction. Continuing the above steps would lead to infinitely many valid graph structures which is a contradiction.