Identifiability of VAR(1) model in a stationary setting Bixuan Liu Abstract We consider a classical First-order Vector AutoRegressive (VAR(1)) model, where we interpret the autoregressive interaction matrix as influence relationships among the components of the VAR(1) process that can be encoded by a weighted directed graph. A majority of previous work studies the structural identifiability of the graph is based on time series observations and therefore relies on dynamical information. By constract, this work aims to incorporate the sampling insufficiency problem in ecological research, that is, due to limited resources, time-series observations are often unavailable and what we have in practice is independently, identically distributed data sampled from the stationary distribution, making classical time-series methods inapplicable. Within this framework, we assume that an equilibrium of VAR(1) exists, and study instead the identifiability of the graph from the stationary distribution, meaning that we seek a way to reconstruct the influence graph underlying the dynamic network using only static information. Importantly, the graph associated to the support of the autoregressive interaction matrix of the VAR(1) model does not coincide with the graphical model of the stationary distribution, making standard tools developed for Gaussian Graphical Models (GGMs) irrelevent. Therefore, this paper applies an approach from algebraic statistics that characterizes models using the Jacobian matroids associated with the parametrization of the models. We successfully derive easily applicable sufficient graphical conditions under which different graphs yield distinct steady-state distributions through the lens of maximal class, a concept that is initially introduced by this paper. Additionally, we illustrate how our results could be applied to characterize networks inspired by ecological research. Keywords: model identifiability, vector autoregressive models (VAR), algebraic matroids MSC 2020: 62R01, 62H22, 62A09 1 Introduction VAR(1) model. This paper considers a classical First-order Vector AutoRegressive (VAR(1)) model: \left\{\begin{array}[]{l}X_{0}=\epsilon_{0},\\ X_{t}=\Lambda^{T}X_{t-1}+\epsilon_{t}\hskip 9.24994pt\mbox{for }t\in\mathbb{N},\\ \end{array}\right. (1) where X_{t} and \epsilon_{t} are random vectors in \mathbb{R}^{n} for some n\in\mathbb{N} . \epsilon_{t} is independent of X_{t-1} , and (\epsilon_{t})_{t\in\mathbb{N}} are i.i.d.. \Lambda=\left(\lambda_{ij}\right)\in M_{n}\left(\mathbb{R}\right) , i.e., it is a deterministic n\times n matrix with values in \mathbb{R} , which we call the interaction matrix. Each element \lambda_{ij} represents the direct influence of the i^{\mbox{th}} coordinate of X_{t-1} on the j^{\mbox{th}} coordinate of X_{t} . In this paper, the error term \epsilon_{t} is centered with covariance matrix \omega I_{n} , where I_{n}\in M_{n}(\mathbb{R}) is the identity matrix, and \omega\in\mathbb{R}^{+} is a positive constant. If the eigenvalues of \Lambda are all smaller than 1 in absolute value, then as t goes to infinity, x_{t} converges in distribution to a centered distribution with covariance matrix \Sigma=\left(\sigma_{ij}\right)\in M_{n}(\mathbb{R}) ( [ 3 ] ). \Sigma satisfies ( [ 29 ] ): \Sigma=\Lambda^{T}\Sigma\Lambda+\omega I_{n}. (2) Apply the vec operator ( [ 20 , Section 10.2] ) on both sides, ( 2 ) is equivalent to: \mbox{vec}\left(\Sigma\right)=\left(I_{n}-\Lambda^{T}\otimes\Lambda^{T}\right)^{-1}\mbox{vec}\left(\omega I_{n}\right), (3) where \otimes is the matrix tensor product ( [ 29 ] ). ( 3 ) indicates that \Sigma is unique given a unique set of parameters \Lambda and \omega . Problem statement. This paper studies the identifiability of the VAR(1) model in a stationary setting, that is, whether different parameters ( \Lambda and \omega ) produce the same \Sigma , using ( 2 ). We restrict the problem to the identifiability of the support of \Lambda , i.e., the location of its non-zero elements, which corresponds to the reconstruction of the underlying graph structure. Importantly, the properties of Gaussian Graphical Models (GGMs) (see [ 17 ] for an introduction) are inapplicable to our setting because the graphical model of the stationary distribution is the graph corresponding to the support of the inverse of the covariance matrix \Sigma^{-1} , and it is not the one induced by the support of \Lambda . For instance, in Section 2.2 , Example 1 shows that \Sigma^{-1} , which is computable from \Sigma , can have full support (i.e., all elements are non-zero) even when \Lambda does not. For this reason, our work does not study conditional independence relations as in GGMs. Instead, different methods are needed to treat our problem. To be more precise about the graphical model, we consider in this paper, the VAR(1) model ( 1 ) is associated with a directed graph G=\left(V,\mathfrak{E}_{G}\right) with node set V=\left\{1,2,\cdots,n\right\} , each corresponding to one of the components of X_{t} , and edge set \mathfrak{E}_{G} consists of ordered pairs \left(i,j\right) or i\rightarrow j , which represents the direct influence among components of X_{t} . For any i,j\in\left[n\right] , an edge \left(i,j\right) in \mathfrak{E}_{G} indicates \lambda_{ij}\neq 0 , meaning that there is a direct effect of the i^{\mbox{th}} coordinate of X_{t-1} on the j^{\mbox{th}} coordinate of X_{t} . Figure 1 shows an example of a graphical VAR(1) model with 4 nodes, and the corresponding graph G . Because \Lambda is deterministic, i.e., it does not change over time, the dynamic model in (a) is encoded by the graph G in (b) for simplicity. Throughout the paper, we assume that G is a reflexive directed graph , that is, (i,i)\in\mathfrak{E}_{G},\ \forall i\in[n] . This convention is natural in many real-life scenarios such as ecological networks where we expect the evolution of species to be dependent on itself. (a) The graphical VAR(1) model (b) The encoded graph G Figure 1: Example of a graphical VAR(1) model and the encoded graph G Motivation. The motivation of this paper can be found in ecological research. Ecosystems are often modeled by dynamical systems. For example, in the model of Robert May ( [ 19 ] ), the linearization of the dynamics of abundancies or densities of n interacting species around their equilibrium leads to the system: \frac{\mathrm{d}X}{\mathrm{d}t}=AX, (4) where A is a deterministic n\times n matrix that represents interactions among species through various mechanisms such as competition, predation or facilitation. The equation ( 1 ) can be seen as a stochastic and discrete in time version of ( 4 ). VAR(1) models can also arise when we consider the (vectorial) fluctuation process X_{t} associated with individual-based models converging to Lotka-Volterra ordinary differential equations. The fluctuation process is then shown to satisfy a continuous time version of ( 1 ) with a noise having a diagonal covariance matrix (see [ 1 ] for more precisions). More importantly, it is reasonable to start from a basic and classical model also because, as pointed out later in this section, the study of dynamical system with only information from a steady state is a subject rarely explored. The reason for which we are particularly considering a stationary setting lies in the sampling insufficiency problem of ecological research. It is a central topic for ecologists to reconstruct the dynamic interaction network, such as the support of \mathbf{A} in ( 4 ) or the support of \Lambda in ( 1 ), from the abundance data captured in the ecosystem, since studying the dynamic influence among species is crucial to understanding the evolution of the abundances of species and thus helps to prevent extinction. However, as pointed out by [ 18 ] , fine-scale replication sampling such as time-series sampling is generally too costly and are often sacrificed in practice. Instead, the limited resources (manpower, time, money) are used to cover as much ground as possible during each sampling campaign. Consequently, a considerable amount of abundance data available covers a large number of locations but each of them is sampled only once, making classical time-series analysis inapplicable. For example, [ 6 ] inferred a global ocean cross-domain plankton co-occurrence network with one-time-samplings of 200 stations. It is true that there are cases where each of the sampling sites is sampled multiple times, but the temporal gap between each sampling campaign is generally too large. For instance, [ 30 ] sampled for plant–aphid–ant interactions on 18 forest islands once a year from 2020 to 2021. There are also researches that collect data regularly, e.g. monthly, for each sampling site, but the data points are not enough to conduct classical time-series analysis, such as [ 23 ] , which collected plant and humming bird abundance over 19 sites monthly but only over a little more than a year. To resolve the sampling insufficiency problem and potentially make the planning of sampling campaigns easier for ecologists, we seek for a way to reconstruct the dynamic interaction network of an ecosystem with only i.i.d. samples of a final stationary distribution of the dynamical system, instead of time-series observations. As a first step of solving this problem, this paper assumes that we have the final state of the VAR(1) model, i.e., the matrix \Sigma in ( 2 ), from which we try to recover the dynamic interaction network, i.e., the support of \Lambda . Although in practice, we will have i.i.d. observations from the stationary distribution and never the true \Sigma , it is worth verifying that the network is identifiable with the true \Sigma , because if not, it’s highly unlikely to be identifiable with real data. Related work. To the best of our knowledge, the identifiability of VAR(1) parameters in a stationary setting has rarely been explored in the existing literature. A majority of previous work that has dealt with the identifiability of the VAR(1) model, and achieved significant and systematic results, relied on observations that were sampled as time series (e.g. [ 12 ] , [ 26 ] ). This is reasonable because the parameters involve dynamic interactions among the components of the random process X_{t} , making it natural to expect that it should only be inferred from dynamic data. Nevertheless, there is a literature that deals with the identifiability of the interaction matrix \Lambda of VAR(1) in a stationary setting. [ 29 ] provides a necessary identifiability condition based on the number of parameters to estimate by counting the parameters. However, this condition only excludes a small subset of cases where the interaction matrix is not identifiable, while we are more interested in sufficient conditions for identifiability. In contrast to the comparatively limited existing literature on stationary VAR(1) models, the structural identifiability of two closely related, yet distinct, classes of models – linear structural equation models (SEMs) and continuous Lyapunov models (LMs) – have been more extensively studied and remain an active area of research. This line of work typically relies on algebraic-statistical methods, for which a comprehensive introduction can be found in [ 25 ] . A linear structural equation model (SEM) specifies a random vector X through the system X=\Lambda^{T}X+\epsilon,\ \epsilon\sim\mathcal{N}(0,\Omega), where \Lambda is a deterministic matrix representing the direct effects among random variables. When I-\Lambda is invertible, the system has a unique solution X=(I-\Lambda)^{-T}\epsilon . Consequently, X is Gaussian with covariance matrix \Sigma . Its inverse, the precision matrix K , satisfies K=\Sigma^{-1}=(I-\Lambda)\Omega^{-1}(I-\Lambda)^{T}. (5) The parameter identifiability of linear SEMs has been extensively studied; see, for instance, [ 10 ] for a review of recent developments. Important contributions include [ 9 ] , which establishes generic identifiability results for graphs allowing directed cycles, and [ 5 ] , which studies identifiability in the presence of latent variables. A continuous-time linear model, more precisely an Ornstein-Uhlenbeck process , describes a stochastic process \{X_{t}\}_{t\geq 0} as the solution of the stochastic differential equation dX_{t}=\Lambda^{T}X_{t}\,dt+\Omega^{1/2}\,dW_{t}, where W_{t} is a standard n -dimensional Brownian motion. If \Lambda is stable, namely if all eigenvalues of \Lambda have strictly negative real parts, then the process admits a unique stationary distribution. It is centered Gaussian with covariance matrix \Sigma , which is characterized by the continuous Lyapunov equation \Lambda^{T}\Sigma+\Sigma\Lambda+\Omega^{1/2}\Omega^{T/2}=0. (6) The identifiability of the drift matrix \Lambda from the stationary covariance matrix \Sigma has received substantial attention. Recent contributions include [ 2 ] , which characterizes model equivalence classes for acyclic continuous LMs; [ 21 ] , which proves generic parameter identifiability of \Lambda given any connected graph in a non-Gaussian setting; and [ 8 ] , which provides sparsity conditions ensuring global identifiability of \Lambda . It is worth noting that the results on continuous LMs do not directly imply analogous results in our setting because the stationary covariance equation is different. Continuous LMs correspond to ( 6 ), whereas stationary VAR(1) models satisfy ( 2 ). For instance, literatures in continuous LM like [ 2 , 8 ] define the model as the set of covariance matrices \Sigma satisfying the continuous Lyapunov equation ( 6 ), and study the algebraic properties of this set. Replacing this equation by the stationary VAR(1) covariance equation changes the underlying parametrization map, and hence the algebraic structure of the resulting model. Therefore, establishing results in our setting requires a separate analysis. One of the most recently developed method to test generic identifiability of a parametrized statistical model is through distinguishing the Jacobian matroid of the parametrization map. [ 15 ] develop an algorithm to numerically study the Jacobian matroid and apply it to phylogenetics models, while [ 9 ] treat the problem in a theoretical manner where they characterize mathematically properties of the Jacobian matroid of a linear SEM and successfully derive graphical conditions for generic identifiability. However, the Jacobian matroid is specific to the parametrization map of the model. Results obtained for phylogenetic models or linear SEMs therefore do not directly imply analogous statements for stationary VAR(1) models, nor do they yield generic identifiability results in our setting. Our contribution. Our work takes the same starting point as in Drton’s work ( [ 9 ] ) and seeks to achieve graphical conditions for generic identifiability of VAR(1) from its steady state. Our main contributions include 1. Targeting the unexplored problem of structural identifiability of VAR(1) from stationary information alone. Although VAR(1) models are fundamental in multivariate time-series analysis, the extent to which their directed interaction graphs can be recovered from stationary information has received limited attention. Our work provides, to the best of our knowledge, one of the first systematic identifiability results for stationary VAR(1) graph models, clarifying when the underlying dynamic structure can be inferred without access to time-series data. 2. Addressing a more complex identifiability setting induced by discrete-time dynamics. Although our problem of recovering \Lambda from the stationary covariance matrix \Sigma is closely related to identifiability problems for linear SEMs and continuous LMs, the VAR(1) setting is substantially more difficult. This difficulty arises from the equation ( 2 ) – also known as the discrete Lyapunov equation, whose structure differs fundamentally from the corresponding equations in these two models. Unlike linear SEMs ( 5 ), it does not yield a convenient expression for either \Sigma or \Sigma^{-1} without introducing an inverse depending on \Lambda . On the other hand, while in continous LM, \Sigma admits a compact integral representation in terms of \Lambda and \Omega ( [ 28 , Proposition 2.1] ), this representation is replaced by an infinite series of Kronecker product of \Lambda as written in ( 8 ) in the discrete case. This more intricate structure, inherent to discrete-time dynamics, makes the analysis of structural identifiability considerably more challenging. 3. New illustration of trek rule. One of our main results (Theorem 2 ) characterizes the non-zero pattern in a generic covariance matrix \Sigma with the existence of a specific graphical structure that we call “maximal classes”, which can be viewed as sets of nodes that receive information from a common ”source” in a directed graph (formal definition and relevant reconstruction algorithms are provided in later sections). A maximal class is also a maximal set of nodes that are pairwise connected by treks ( [ 24 , Definition 2.6] ) with the same top. This zero pattern, or the trek rule , also exists in linear SEM ( [ 10 , Theorem 4.2] ) and continuous LM ( [ 28 , Corollary 2.3] ). Our work validate it in VAR(1), offering an additional insight into its generality. 4. Practical graphical identifiability conditions and ecological insight. We propose easily verifiable graphical conditions for generic identifiability, showing in particular that graphs with different maximal classes generically yield distinct stationary distributions. These conditions are also interpretable, since maximal classes serve as a bridge between dynamical network and the corresponding stationary distribution. We illustrate the applicability of our results through examples inspired by ecological networks. Outline. The rest of this paper is organized as follows: Section 2 formally defines the statistical model and introduces the definitions and testing criteria for global and generic identifiability with an overview of the main results of this paper in the end. Section 3 introduces results on the Jacobian structure of the parametrization of the model. Section 4 presents the concept of “maximal classes” for directed graphs and its relationship with the support of the covariance matrix \Sigma , which is the core of this study. Section 5 introduces two sufficient conditions of generic identifiability based on maximal classes, one of which is only valid for characterizing models with the same dimension, while the other one can be extended to models with any dimension. A result that allows us to calculate the dimension of the model for reflexive graphs with no reciprocal edges, is also provided to make the two conditions applicable. Section 6 is an illustration of how our results could be applied in ecological research. 2 Identifiability of the VAR(1) model in a stationary setting In this section, we start with introducing the parametrization and statistical model of our settings, then define global and generic identifiability, along with the identifiability criteria used throughout this paper. Finally, we provide an overview of our main results, i.e., sufficient conditions for generic identifiability. The definition and criteria for identifiability are based on the concept of a generic point . We define a point in a set as generic if it does not lie within a proper (i.e., strictly included) algebraic subvariety of the set. In concrete terms, a generic point is any point in the set except for those that satisfy a specific non-trivial polynomial equation. Because such proper algebraic subvarieties have Lebesgue measure zero, another interpretation is that a parameter value sampled from a continuous probability distribution is generic with probability one. 2.1 Problem settings Given a VAR(1) model ( 1 ) and the associated directed graph G=\left(V,\mathfrak{E}_{G}\right) , where V=[n]=\{1,2,\cdots,n\} , define the set of interaction matrices M_{G} associated to a graph G as: M_{G}:=\left\{\Lambda=\left(\lambda_{ij}\right)\in M_{n}\left(\mathbb{R}\right)\mid\rho(\Lambda)<1,\mbox{ and }\lambda_{ij}=0\mbox{ if }\left(i,j\right)\notin\mathfrak{E}_{G}\right\}, where \rho(\cdot) is the spectral radius, and the condition \rho(\Lambda)<1 ensures the existence of the equilibrium. The parameter space is then M_{G}\times\mathbb{R}^{+} , corresponding to elements of \Lambda and \omega . Next, we formally define the model. Definition 1 . For the stationary VAR(1) model corresponding to a graph G , define \mathbf{M}_{G} the following set of matrices: \mathbf{M}_{G}=\left\{\Sigma\mid\Sigma=\phi_{G}\left(\Lambda,\omega\right),\Lambda\in M_{G},\omega\in\mathbb{R}^{+}\right\}, where \displaystyle\phi_{G}:M_{G}\times\mathbb{R}^{+} \displaystyle\rightarrow M_{n}\left(\mathbb{R}\right) \displaystyle\left(\Lambda,\omega\right) \displaystyle\mapsto\Sigma,\mbox{ s.t. }\Sigma=\Lambda^{T}\Sigma\Lambda+\omega I_{n} is the parametrization map defined by ( 2 ). By abuse of notation, we call the set \mathbf{M}_{G} the stationary VAR(1) model . Remark 1 (Structural Properties) . We highlight two structural characteristics of the parameter space M_{G}\times\mathbb{R}^{+} and the model \mathbf{M}_{G} : 1. Nested structure: The definition of M_{G} allows for edge weights to vanish (i.e., \lambda_{ij}=0 for (i,j)\in\mathfrak{E}_{G} ). Consequently, the parameter space of any subgraph G^{\prime}\subset G is naturally embedded within M_{G} . This inclusion property extends to the models (i.e., \mathbf{M}_{G^{\prime}}\subseteq\mathbf{M}_{G} ), ensuring a continuous transition between the model \mathbf{M}_{G} and its sub-models. 2. Error structure: The covariance matrix of the error term in ( 1 ) is assumed to be diagonal with identical values \omega . While this assumption is central to our calculations, the underlying framework is generalizable to other diagonal matrices with distinct entries. However, the calculations do not extend to non-diagonal matrices. We adopted the identical diagonal assumption to minimize the number of parameters to estimate, allowing us to focus specifically on the reconstruction of \Lambda . In this paper, we study the identifiability of a finite family of stationary VAR(1) models, i.e., assume that we are given a finite list of possible graphs, we try to see under what conditions they yield different stationary distributions, and in particular different stationary covariance relationships. This is particularly useful in ecological research where we could have prior information about the network, and were able to reduce the network to a finite list of candidates. Besides, as illustrated in Example 1 below, identifiability of the underlying graph from the covariance matrix \Sigma in a conventional sense is not achieved because there exist two networks that yield the same stationary distribution. For a finite family of stationary VAR(1) models, we characterize them by studying the dimension of the intersection of the images of the parametrization map, in the sense that two models are generically identifiable if they only intersect in a set with smaller dimension (detailed definitions of identifiability introduced in the next section). The dimension of the model \mathbf{M}_{G} is defined as follows: {\operatorname{dim}}\left(\mathbf{M}_{G}\right):={\operatorname{dim}}\left(\overline{\mathbf{M}_{G}}\right), where \overline{\mathbf{M}_{G}} denotes the Zariski closure of \mathbf{M}_{G} in the ambient affine space of symmetric positive definite matrices. The dimension on the right hand side is the usual Krull dimension of this algebraic variety. Since the parametrization map is a rational function, i.e., it is a quotient of polynomials, (proof in Appendix C ), the dimension of \overline{\mathbf{M}_{G}} is the rank of the (transpose of the) Jacobian matrix of the parametrization map evaluated at a generic point . At regular points of the model, the algebraic dimension coincides with the local dimension of \mathbf{M}_{G} viewed as a smooth manifold. A brief review of relevant notions from Zariski topology is provided in Appendix A . The next section presents the definitions for global and generic identifiability. 2.2 Global and generic identifiability Definition 2 . Given a family of stationary VAR(1) models \left\{\mathbf{M}_{k}\right\}_{k=1}^{K} and associated graphs \left\{G_{k}=\left(V,\mathfrak{E}_{G_{k}}\right)\right\}_{k=1}^{K} , where K\in\mathbb{N} , then the model, i.e., the discrete parameter k is globally identifiable if for any distinct pair \left(k_{1},k_{2}\right) of values from 1 to K , \mathbf{M}_{k_{1}}\cap\mathbf{M}_{k_{2}}=\emptyset . In fact, global identifiability is a highly restrictive property of the models. There exist cases where models with different underlying graphs, i.e., different supports of \Lambda , yield the same \Sigma (see Example 1 ). Example 1 . Consider the case where n=3 , and the following two interaction matrices, which represent different graphs: \Lambda_{1}=\left[\begin{array}[]{ccc}0.50&0.70&0\\ 0&0.90&0\\ 0&0.80&0.40\end{array}\right],\hskip 9.24994pt\Lambda_{2}=\left[\begin{array}[]{ccc}0.50&0.67&-0.01\\ 0&0.94&0.02\\ 0&0&0.38\end{array}\right] and if we let \omega in both cases equals to 1 , then by ( 2 ), both models yield the following covariance matrix: \Sigma=\left[\begin{array}[]{ccc}1.33&0.85&0\\ 0.85&22.85&0.60\\ 0&0.60&1.19\end{array}\right]. Therefore, we focus instead on a less restrictive definition of identifiability, called generic identifiability , which is widely used in the field of algebraic statistics. It allows the images of parametrization maps to intersect only in a set with Lebesgue measure zero. Definition 3 . Let \left\{\mathbf{M}_{k}\right\}_{k=1}^{K} be a family of stationary VAR(1) models as in Definition 2 . Then the discrete parameter k is generically identifiable if for any distinct pair \left(k_{1},k_{2}\right) of values from 1 to K , {\operatorname{dim}}\left(\mathbf{M}_{k_{1}}\cap\mathbf{M}_{k_{2}}\right)<\min\left\{{\operatorname{dim}}\left(\mathbf{M}_{k_{1}}\right),{\operatorname{dim}}\left(\mathbf{M}_{k_{2}}\right)\right\}. The geometric interpretation of Definition 3 is that a family of models are generically identifiable if the intersection of any two models in the family is a Lebesgue measure zero subset of both models. But this definition also implies that in some circumstances, models with different dimensions are not generically identifiable, which is not desired. Instead, the following definition of generic identifiability is used. Definition 4 . Let \left\{\mathbf{M}_{k}\right\}_{k=1}^{K} be a family of stationary VAR(1) models as above. Then the discrete parameter k is generically identifiable if for each pair \left(k_{1},k_{2}\right) of values of k , where k_{1}\neq k_{2} , {\operatorname{dim}}\left(\mathbf{M}_{k_{1}}\cap\mathbf{M}_{k_{2}}\right)<\max\left\{{\operatorname{dim}}\left(\mathbf{M}_{k_{1}}\right),{\operatorname{dim}}\left(\mathbf{M}_{k_{2}}\right)\right\}. Definition 4 states that the models in the family are generically identifiable from each other if the intersection of any two models in the family is a Lebesgue measure zero subset of the union of the models. This definition yields a simple criterion: two stationary VAR(1) models \mathbf{M}_{1} , \mathbf{M}_{2} are generically identifiable if {\operatorname{dim}}\left(\mathbf{M}_{1}\right)\neq{\operatorname{dim}}\left(\mathbf{M}_{2}\right). This property is one of the main tools that we used in this paper to test generic identifiability. Note that it does not imply that two models whose graphs are nested are generically identifiable, because as illustrated by the third row of Table 1 at the end of the paper, adding one edge to a graph might not change the dimension of the corresponding model. On the other hand, this property indicates that if we find a way to access the dimensions of the models, we can focus on the identifiability of models with the same dimension, in which case Definitions 3 and 4 are equivalent. In fact, there exist many tools to test generic identifiability [ 25 , Chapter 16] . This paper applies one of them that uses the Jacobian matroid derived from the parametrization of the model, developed by [ 9 ] . The following section provides an introduction to this method. 2.3 Identifiability criteria Before introducing the tools to test generic identifiability, we present some necessary algebraic notions. Definition 5 . Let \phi be a \mathcal{C}^{1} map from \mathbb{R}^{d} to \mathbb{R}^{p} : \phi\left(\theta_{1},\cdots,\theta_{d}\right)=\left(\phi_{1}\left(\bm{\theta}\right),\cdots,\phi_{p}\left(\bm{\theta}\right)\right) . Then the Jacobian matrix of this map is: \mathbf{J}_{\phi}=\left(\frac{\partial\phi_{i}}{\partial\theta_{j}}\right),1\leq i\leq p,1\leq j\leq d. Next we define the Jacobian matrix for the stationary VAR(1) model, which is the transpose of the usual Jacobian matrix of the parametrization map. Definition 6 . Let \mathbf{M}_{G} be a stationary VAR(1) model, and \phi_{G} in Definition 1 parametrizes \mathbf{M}_{G} . Then the Jacobian matrix of the model is \mathbf{J}_{G}=\left(\frac{\partial\phi_{j}}{\partial\theta_{i}}\right),1\leq i\leq E_{G}+1,1\leq j\leq\frac{n(1+n)}{2}, where E_{G} is the number of edges in G , \phi_{j} ’s are the distinct entries of \Sigma , and \theta_{i} ’s are the entries of \Lambda and \omega . Now we introduce the Jacobian matroid, the main object used to characterize models. To do so, we first introduce the linear matroid associated with a matrix. The general definition of a matroid is omitted here, as it is not necessary for the tools used in this paper. We refer the interested readers to [ 25 ] for further details. Definition 7 . Let A\in M_{m\times n}\left(\mathbb{R}\right) be a matrix, then the linear matroid of A is the pair \left\{E,\mathcal{I}\right\} , where E=\{1,\cdots,n\} , representing the n columns of A , and \mathcal{I}=\left\{S\subseteq E\mid A^{S}\mbox{ are linearly independent}\right\}, where A^{S} represents the set of columns of A corresponding to the coordinates S . Example 2 . Let A=\left[\begin{array}[]{cccc}2&0&2&4\\ 0&1&1&0\\ 0&0&1&0\\ 4&0&4&8\end{array}\right], then the linear matroid of A is \left\{E,\mathcal{I}\right\} , where E=\left\{1,2,3,4\right\} , representing the 4 columns of A respectively, and \mathcal{I}=\left\{\emptyset,\left\{1\right\},\left\{2\right\},\left\{3\right\},\left\{4\right\},\left\{1,2\right\},\left\{1,3\right\},\left\{2,3\right\},\left\{2,4\right\},\left\{3,4\right\},\left\{1,2,3\right\},\left\{2,3,4\right\}\right\}. Note that \left\{1,4\right\} is not included in the matroid because the first and the fourth column of A are not independent, which also excludes \left\{1,2,4\right\} , \left\{1,3,4\right\} and \left\{1,2,3,4\right\} . Definition 8 . The Jacobian matroid of a stationary VAR(1) model \mathbf{M}_{G} , denoted as \mathcal{J}\left(\mathbf{M}_{G}\right) , is the linear matroid of the Jacobian matrix. By abuse of notation, we identify \mathcal{J}\left(\mathbf{M}_{G}\right) with \mathcal{I} in Definition 7 , representing the set of linearly independent columns sets of the Jacobian matrix. Next, we introduce the criteria for generic identifiability based on Jacobian matroids. The criterion is extensively introduced in [ 25 ] and [ 15 ] . Proposition 1 . [ 15 , Proposition 10] Let \mathbf{M}_{1} and \mathbf{M}_{2} be two stationary VAR(1) models corresponding to graphs G_{1} and G_{2} with the same set of nodes. Without loss of generality, assume that {\operatorname{dim}}\left({\mathbf{M}_{1}}\right)\geq{\operatorname{dim}}\left({\mathbf{M}_{2}}\right) . If there exists a subset S of the coordinates such that S\in\mathcal{J}\left(\mathbf{M}_{2}\right)\backslash\mathcal{J}\left(\mathbf{M}_{1}\right), then {\operatorname{dim}}\left(\mathbf{M}_{1}\cap\mathbf{M}_{2}\right)<\min\left\{{\operatorname{dim}}\left(\mathbf{M}_{1}\right),{\operatorname{dim}}\left(\mathbf{M}_{2}\right)\right\} . In Section 5.2 , we will prove that the dimension of a stationary VAR(1) model. i.e., the rank of the Jacobian matrix, is calculable for a subset of graphs. Therefore, we can focus specially on the identifiability of models with the same dimension, in which case the role of the two models are equivalent. Proposition 1 then indicates that two models \mathbf{M}_{1} , \mathbf{M}_{2} with the same dimension are generically identifiable if there exists a subset S of the coordinates such that S\in\mathcal{J}\left(\mathbf{M}_{1}\right)\backslash\mathcal{J}\left(\mathbf{M}_{2}\right)\mbox{ or }S\in\mathcal{J}\left(\mathbf{M}_{2}\right)\backslash\mathcal{J}\left(\mathbf{M}_{1}\right). Definition 4 and Proposition 1 will be the main tools used throughout this paper to test generic identifiability. 2.4 Main results In this paper, we introduce maximal classes for directed graphs (formally defined in Section 4 ). We demonstrate that maximal classes are strongly related to the zero columns of the Jacobian matrix of the model (Proposition 4 ), based on which we conclude that among models with the same dimension, two models with different sets of maximal classes are generically identifiable (Theorem 3 ). For a general family of models, where dimensions may not coincide, we give a more restrictive sufficient condition for generic identifiability based on maximal classes in Theorem 4 . Finally, we derive a formula to calculate the dimension of the model for a class of reflexive graphs with no reciprocal edges (Theorem 5 ), which enables us to characterize more models since different dimensions indicate generic identifiability by Definition 4 . A summary and illustration of all the results in this paper are presented in Table 1 at the end of Section 5 . 3 Jacobian Structure of VAR(1) in the Stationary Setting In order to study the Jacobian matroid of the model, we need to calculate the Jacobian matrix. The goal of this section is to provide an explicit formula for the Jacobian matrix \mathbf{J}_{G} for any directed graph G . Starting by deriving the Jacobian matrix for complete graphs, we then define a projection that maps it to that of any graphs, and in the end, we present a simplified formula for \mathbf{J}_{G} based on the projection. For any stationary VAR(1) model \mathbf{M}_{G} , the Jacobian matrix \mathbf{J}_{G} is a matrix of size \left(E_{G}+1\right)\times\left(n(n+1)\right)/2 , where E_{G}=|\mathfrak{E}_{G}| is the number of edges in G . Each row of \mathbf{J}_{G} corresponds to \lambda_{ij} where (i,j)\in\mathfrak{E}_{G} or \omega , and each column corresponds to \sigma_{ab} where a\leq b\in[n] . Note that we only consider a\leq b because \sigma_{ab}=\sigma_{ba} for all a,b\in[n] . Consider a stationary VAR(1) model \mathbf{M}_{\overline{G}} with \overline{G}=\left(V,\mathfrak{E}_{\overline{G}}\right) complete, i.e., \mathfrak{E}_{\overline{G}}=\left\{(i,j)\mid i,j\in[n]\right\} . Denote the Jacobian matrix of this model as \mathbf{J} , which is of size \left(n^{2}+1\right)\times\left(n(n+1)\right)/2 . Define an ”extended” Jacobian matrix \overline{\mathbf{J}} , which is \mathbf{J} with additional columns that correspond to \sigma_{ab} where a>b\in[n] , meaning that \overline{\mathbf{J}} is of size \left(n^{2}+1\right)\times n^{2} . The following lemma provides a formula for this \overline{\mathbf{J}} . Lemma 1 . Let \mathbf{M}_{G} be a stationary VAR(1) model with G complete, and P_{i,j}\in M_{n}\left(\mathbb{R}\right) for all i,j\in[n] be the identity matrix switching the i^{th} and j^{th} columns. Then the extended Jacobian matrix \overline{\mathbf{J}} satisfies: \overline{\mathbf{J}}=\overline{\mathbf{J}}\left(\Lambda\otimes\Lambda\right)+B, (7) where B=\left[\begin{array}[]{c}\left(\Sigma\Lambda\otimes I_{n}\right)\left(I_{n^{2}}+\mathbf{P}\right)\\ \mbox{vec}\left(I_{n^{2}}\right)^{T}\end{array}\right], and \mathbf{P}=\prod_{i\geq 1}\prod_{j>i}P_{\left(i-1\right)n+j,\left(j-1\right)n+i}. Proof. The proof is given in Appendix D . ∎ In Lemma 1 , P_{\left(i-1\right)n+j,\left(j-1\right)n+i} is the identify matrix exchanging the i^{th} and j^{th} columns of the j^{th} and i^{th} blocks, and hence \mathbf{P} is just the indentity matrix exchanging columns n(n-1)/2 times. The following example is a visualization of the function of \mathbf{P} . Example 3 . When n=3 , \mathbf{P} does the following: for all a,\cdots,i\in\mathbb{R} , \displaystyle\left(\left[\begin{array}[]{ccc}a&b&c\\ d&e&f\\ g&h&i\end{array}\right]\otimes I_{3}\right)\mathbf{P} \displaystyle=\left[\begin{array}[]{ccccccccc}a&&&b&&&c&&\\ &a&&&b&&&c&\\ &&a&&&b&&&c\\ d&&&e&&&f&&\\ &d&&&e&&&f&\\ &&d&&&e&&&f\\ g&&&h&&&i&&\\ &g&&&h&&&i&\\ &&g&&&h&&&i\\ \end{array}\right]\mathbf{P}=\left[\begin{array}[]{ccccccccc}a&b&c&&&&&&\\ &&&a&b&c&&&\\ &&&&&&a&b&c\\ d&e&f&&&&&&\\ &&&d&e&f&&&\\ &&&&&&d&e&f\\ g&h&i&&&&&&\\ &&&g&h&i&&&\\ &&&&&&g&h&i\\ \end{array}\right] Let \mathbf{M}_{G} be a stationary VAR(1) model with G=\left(V,\mathfrak{E}_{G}\right) , possibly not complete. Define again a corresponding extended Jacobian matrix \overline{\mathbf{J}}_{G} , which is \mathbf{J}_{G} with additional columns that correspond to \sigma_{ab} where a>b\in[n] . Then, \overline{\mathbf{J}}_{G} is of size \left(E_{G}+1\right)\times n^{2} . Now we introduce a projection from \overline{\mathbf{J}} to \overline{\mathbf{J}}_{G} , which will then be used to derive an explicit expression of \overline{\mathbf{J}}_{G} . Definition 9 . Let \mathbf{M}_{G} be a stationary VAR(1) model with G=\left(V,\mathfrak{E}_{G}\right) not necessarily complete, and \overline{\mathbf{J}} be the extended Jacobian matrix for a complete graph. Define the projection \displaystyle\psi_{G}:M_{\left(n^{2}+1\right),n^{2}}\left(\mathbb{R}\right) \displaystyle\rightarrow M_{\left(E_{G}+1\right),n^{2}}\left(\mathbb{R}\right) \displaystyle\overline{\mathbf{J}} \displaystyle\mapsto\psi_{G}\left(\overline{\mathbf{J}}\right), as follows: \psi_{G} removes from \overline{\mathbf{J}} all rows in that correspond to \lambda_{ij} such that \left(i,j\right)\notin\mathfrak{E}_{G} . In the remaining entries, all parameters \lambda_{ij} with \left(i,j\right)\notin\mathfrak{E}_{G} are set to zero. Under this definition, we have \psi_{G}\left(\overline{\mathbf{J}}\right)=\overline{\mathbf{J}}_{G}. The proof is given in Appendix E . By applying this projection to both sides of ( 7 ), we get \overline{\mathbf{J}}_{G}=\overline{\mathbf{J}}_{G}\left(\Lambda\otimes\Lambda\right)+\psi_{G}(B), where B is defined in Lemma 1 . We next illustrate how to apply this equation to calculate the extended Jacobian matrix of a specific graph. Example 4 . Consider a stationary VAR(1) model \mathbf{M}_{G} with a directed graph G=\left(V,\mathfrak{E}_{G}\right) , where V=\left\{1,2,3\right\} and \mathfrak{E}_{G}=\left\{\left(1,1\right),\left(2,2\right),\left(3,3\right),\left(1,3\right),\left(2,1\right)\right\} . The graph and the corresponding interaction matrix are given below. \Lambda=\left[\begin{array}[]{ccc}\lambda_{11}&0&\lambda_{13}\\ \lambda_{21}&\lambda_{22}&0\\ 0&0&\lambda_{33}\end{array}\right]. In this case, all computations can be explicit: \Sigma\Lambda=\left[\begin{array}[]{ccc}\sigma_{11}\lambda_{11}+\sigma_{12}\lambda_{21}&\sigma_{12}\lambda_{22}&\sigma_{11}\lambda_{13}+\sigma_{13}\lambda_{33}\\ \sigma_{21}\lambda_{11}+\sigma_{22}\lambda_{21}&\sigma_{22}\lambda_{22}&\sigma_{21}\lambda_{13}+\sigma_{23}\lambda_{33}\\ \sigma_{31}\lambda_{11}+\sigma_{32}\lambda_{21}&\sigma_{32}\lambda_{22}&\sigma_{31}\lambda_{13}+\sigma_{33}\lambda_{33}\end{array}\right]. Then the extended Jacobian matrix \overline{\mathbf{J}}_{G} satisfies: \overline{\mathbf{J}}_{G}=\overline{\mathbf{J}}_{G}A+\psi_{G}\left(B\right), where \displaystyle A \displaystyle=\Lambda\otimes\Lambda \displaystyle=\left[\begin{array}[]{ccc}\begin{array}[]{ccc}\lambda_{11}^{2}&0&\lambda_{11}\lambda_{13}\\ \lambda_{11}\lambda_{21}&\lambda_{11}\lambda_{22}&0\\ 0&0&\lambda_{11}\lambda_{33}\end{array}&\mathbf{0}&\begin{array}[]{ccc}\lambda_{11}\lambda_{13}&0&\lambda_{13}^{2}\\ \lambda_{13}\lambda_{21}&\lambda_{13}\lambda_{22}&0\\ 0&0&\lambda_{13}\lambda_{33}\end{array}\\ \begin{array}[]{ccc}\lambda_{21}\lambda_{11}&0&\lambda_{21}\lambda_{13}\\ \lambda_{21}^{2}&\lambda_{21}\lambda_{22}&0\\ 0&0&\lambda_{21}\lambda_{33}\end{array}&\begin{array}[]{ccc}\lambda_{22}\lambda_{11}&0&\lambda_{22}\lambda_{13}\\ \lambda_{22}\lambda_{21}&\lambda_{22}^{2}&0\\ 0&0&\lambda_{22}\lambda_{33}\end{array}&\mathbf{0}\\ \mathbf{0}&\mathbf{0}&\begin{array}[]{ccc}\lambda_{33}\lambda_{11}&0&\lambda_{33}\lambda_{13}\\ \lambda_{33}\lambda_{21}&\lambda_{33}\lambda_{22}&0\\ 0&0&\lambda_{33}^{2}\end{array}\end{array}\right], and \displaystyle\psi_{G}\left(B\right)=\left[\begin{array}[]{cccc}2\left(\sigma_{11}\lambda_{11}+\sigma_{12}\lambda_{21}\right)&\sigma_{12}\lambda_{22}&\sigma_{11}\lambda_{13}+\sigma_{13}\lambda_{33}&\sigma_{12}\lambda_{22}\\ 0&0&\sigma_{11}\lambda_{11}+\sigma_{12}\lambda_{21}&0\\ 2\left(\sigma_{21}\lambda_{11}+\sigma_{22}\lambda_{21}\right)&\sigma_{22}\lambda_{22}&\sigma_{21}\lambda_{13}+\sigma_{23}\lambda_{33}&\sigma_{22}\lambda_{22}\\ 0&\sigma_{21}\lambda_{11}+\sigma_{22}\lambda_{21}&0&\sigma_{21}\lambda_{11}+\sigma_{22}\lambda_{21}\\ 0&0&\sigma_{31}\lambda_{11}+\sigma_{32}\lambda_{21}&0\\ 1&0&0&0\end{array}\right. \displaystyle\left.\begin{array}[]{ccccc}0&0&\sigma_{11}\lambda_{13}+\sigma_{13}\lambda_{33}&0&0\\ 0&\sigma_{12}\lambda_{22}&\sigma_{11}\lambda_{11}+\sigma_{12}\lambda_{21}&\sigma_{12}\lambda_{22}&2\left(\sigma_{11}\lambda_{13}+\sigma_{13}\lambda_{33}\right)\\ 0&0&\sigma_{21}\lambda_{13}+\sigma_{23}\lambda_{33}&0&0\\ 2\sigma_{22}\lambda_{22}&\sigma_{21}\lambda_{13}+\sigma_{23}\lambda_{33}&0&\sigma_{21}\lambda_{13}+\sigma_{23}\lambda_{33}&0\\ 0&\sigma_{32}\lambda_{22}&\sigma_{31}\lambda_{11}+\sigma_{32}\lambda_{21}&\sigma_{32}\lambda_{22}&2\left(\sigma_{31}\lambda_{13}+\sigma_{33}\lambda_{33}\right)\\ 1&0&0&0&1\end{array}\right]. In this example, if \left(I_{n^{2}}-A\right) is invertible, then we will have an explicit formula for \overline{\mathbf{J}}_{G} . From previous arguments, it’s clear that if \left(I_{n^{2}}-\Lambda\otimes\Lambda\right) is invertible, we would be able to define \overline{\mathbf{J}}_{G} as a function of \Lambda and \omega . In fact, the parameters such that the matrix \left(I_{n^{2}}-\Lambda\otimes\Lambda\right) is not invertible has Lebesgue measure zero (proof in Appendix F ). Because of the generic settings, we can always assume that \left(I_{n^{2}}-\Lambda\otimes\Lambda\right) is invertible. This argument of generality and will be applied several times in the following sections. We now have an explicit formula for the extended Jacobian matrix. Theorem 1 . Let \mathbf{M}_{G} be a stationary VAR(1) model. Then the extended Jacobian matrix is generically: \overline{\mathbf{J}}_{G}=\psi_{G}(B)\left(I_{n^{2}}-\Lambda\otimes\Lambda\right)^{-1}, where B is defined in Lemma 1 . Proof. This is a direct result of previous arguments of this section. ∎ Theorem 1 enables us to calculate the extended Jacobian matrix \overline{\mathbf{J}}_{G} for any directed graph G , meaning that we can also calculate the Jacobian matrix \mathbf{J}_{G} , since \overline{\mathbf{J}}_{G} is just \mathbf{J}_{G} with additional columns that are identical to a subset of columns of \mathbf{J}_{G} . Recall that the Jacobian matroid is the set of coordinates of columns that are linearly independent. In the next section, we introduce maximal classes , which will later be used to study the Jacobian matroid. 4 Maximal classes In this section, we introduce the definition and properties of maximal classes and demonstrate that they are closely related to the zero entries of the covariance matrix \Sigma . We also provide an algorithm for computing the set of maximal classes from a given graph (Algorithm 2 in Appendix K ), together with a heuristic procedure for the inverse problem: reconstructing possible graphs from a prescribed set of maximal classes (Algorithm 3 in Appendix K ). Combined with Algorithm 1 , which reconstructs the set of maximal classes from the support of \Sigma , these algorithms provide a first step toward graph reconstruction for stationary VAR(1) models and suggest directions for future work. 4.1 Definition and properties Recall that a Strongly Connected Component (SCC) of a directed graph is a subgraph in which every node is reachable from every other node by a directed path. By abuse of notation, we also use SCC to refer to the set of nodes in such a subgraph. An SCC may consist of a single node. The in-degree of a node v in a directed graph is the number of edges directed into v . We extend this notion to SCCs as follows. Let G=(V,\mathfrak{E}_{G}) be a directed graph and C\subset V be an SCC of G , the in-degree of the SCC is the number of edges entering C from outside, namely {\operatorname{deg}}^{-}(C)=|\left\{\left(v,v^{\prime}\right)\in\mathfrak{E}_{G}\mid v^{\prime}\in C,v\in V\backslash C\right\}|. Throughout the paper, the in-degree of either a node or an SCC is understood to exclude self-loops. An SCC with in-degree zero plays a distinguished role: when the graph is viewed as a network, such a component can be interpreted as a source feeding the rest of the network. We therefore call any SCC with in-degree zero a source of the graph. A maximal class is the maximal set of descendants generated by such a source, as formalized below. Definition 10 . Let S be a source of a directed graph and let i\in S . The maximal class associated with S , denoted by \mathcal{MC}_{[i]} , is set of all nodes reachable from i by a directed path. \mathcal{MC}_{[i]}=\{j\in V:\text{there exists a directed path from }i\text{ to }j\}. Equivalently, \mathcal{MC}_{[i]} is the maximal set of descendants of the source S . The nodes in S are called source nodes. Example 5 . (a) G_{1} (b) G_{2} Figure 2: Example of directed graphs The SCCs of the graph G_{1} in Figure 2 are: \left\{1,2,3\right\},\{4\},\{5\},\{6\}, It’s clear that \left\{1,2,3\right\} and \{5\} have in-degree zero, and hence are the sources. Therefore, the set of maximal classes is: \left\{\left\{\mathbf{1},\mathbf{2},\mathbf{3},4,6\right\},\left\{4,\mathbf{5},6\right\}\right\}, where the nodes in bold are source nodes of the respective maximal classes. In other words, there are two maximal classes in this graph: \mathcal{MC}_{[1]}=\mathcal{MC}_{[2]}=\mathcal{MC}_{[3]}=\{1,2,3,4,6\}\mbox{, and }\mathcal{MC}_{[5]}=\{4,5,6\}. Note that SCCs have also been used to analyze cyclic graphical models; for example, [ 5 , Section 6] use them to decompose cyclic structural causal models into feedback blocks that can be collapsed into solution functions under suitable unique-solvability conditions. Although our use of SCCs is different, this connection highlights the broader relevance of SCC-based decompositions in graphical models with cycles. MC is closely related to the concept of trek in linear SEM and continuous LM. Definition 11 . [ 10 , Definition 4.1] A trek \tau from node i to node j is a semi-walk from i to j of the form (a) i\leftarrow i_{l}\leftarrow\cdots\leftarrow i_{1}\leftarrow i_{0}\longleftrightarrow j_{0}\rightarrow j_{1}\rightarrow\cdots\rightarrow j_{r}\rightarrow j, or (b) i\leftarrow i_{l}\leftarrow\cdots\leftarrow i_{1}\leftarrow i_{0}\longrightarrow j_{1}\rightarrow\cdots\rightarrow j_{r}\rightarrow j. A trek has a left- and a right-hand side, denoted \operatorname{left}(\tau) and \operatorname{right}(\tau) , respectively. We have \operatorname{left}(\tau)=\{i_{0},\ldots,i_{l},i\} and \operatorname{right}(\tau)=\{j_{0},\ldots,j_{r},j\} in case (a), and \operatorname{left}(\tau)=\{i_{0},\ldots,i_{l},i\} and \operatorname{right}(\tau)=\{i_{0},j_{1},\ldots,j_{r},j\} in case (b). In case (b), the top node i_{0} belongs to both sides. Both the left- and the right- hand side are allowed to contain no edges. Under this definition, a maximal class is a maximal set of nodes that are pairwise connected by treks with the same top, or source node. Indeed, for any directed graph G=(V,\mathfrak{E}_{G}) and any two nodes i,j\in V , the following statements are equivalent 1. i and j belong to the same maximal class; 2. there exists a trek between i and j ; 3. either there exists a node k\in V\setminus\{i,j\} such that directed paths from k to i and from k to j both exist, or there exists a directed path from i to j or from j to i . That said, we still formulate our results in terms of maximal classes because, as shown in the following sections, they capture precisely the information encoded by the support of a generic \Sigma and by the locations of zero columns in the Jacobian matrix; treks do not play this role directly. An MC contains less information about the graph than a trek: it is an unordered set of nodes, whereas a trek is specified by a directed semi-path. For example, in the graphs shown in Figure 2 , swapping nodes 4 and 6 in G_{1} yields G_{2} . This operation leaves the MCs unchanged, while changing the trek between nodes 5 and 6 . More importantly, the collection of maximal classes does not determine the graph uniquely, whereas the full collection of treks is sufficient to reconstruct the graph. The following proposition proves the uniqueness of the set of maximal classes for any graph, which is a fundamental property of maximal classes. Proposition 2 . Let G be any directed graph, then the set of maximal classes associated with G is unique. Proof. First, two maximal classes of a graph cannot have the same source. This is because by definition 10 , a maximal class is the set of all nodes reachable by the source, and if two maximal classes have the same source, then they must be the same maximal class. Moreover, for any directed graph G , the set of sources is unique since the in-degree of any node or SCC is uniquely defined. Therefore, each source generates a unique maximal class. Hence, the set of maximal classes is unique. ∎ Using the uniqueness of maximal classes, we provide Algorithm 2 in Appendix K to compute them from a given graph. The algorithm first identifies the strongly connected components, and then, for each SCC with in-degree zero, extracts the corresponding maximal class by depth-first search. Conversely, to reconstruct graphs associated with a given set of maximal classes, we also provide a heuristic procedure in Algorithm 3 in Appendix K . 4.2 Maximal class and the support of \Sigma In this section, we describe the relationship between maximal classes and the covariance matrix \Sigma and propose an explicit procedure to reconstruct the set of maximal classes from the support of \Sigma . We start with a Lemma on the values of the parameter \Lambda . Lemma 2 . Let \mathbf{M}_{G} be a stationary VAR(1) model, and \lambda_{ij}^{[k]}=\left(\Lambda^{k}\right)_{ij} , for all k\in\mathbb{N} , then generically \Lambda\in M^{P}\cap M^{S}, where \displaystyle M^{P}:= \displaystyle\left\{\Lambda\in M_{n}\left(\mathbb{R}\right)\mid\forall i,j\in V,\exists\mbox{ a directed path in }G\mbox{ from }i\mbox{ to }j\right. \displaystyle\left.\Rightarrow\exists K\in\mathbb{N},s.t.\lambda_{ij}^{\left[k\right]}\neq 0,\forall k>K\right\}, \displaystyle M^{S}:= \displaystyle\left\{\Lambda\in M_{n}\left(\mathbb{R}\right)\mid\forall i,j\in V,\sum_{k=0}^{+\infty}\sum_{a=1}^{n}\lambda_{ai}^{\left[k\right]}\lambda_{aj}^{\left[k\right]}=0\Leftrightarrow\forall k\in\mathbb{N},a\in\left[n\right],\lambda_{ai}^{\left[k\right]}\lambda_{aj}^{\left[k\right]}=0,\right. \displaystyle\left.\mbox{and }\sum_{s=1}^{n}\sum_{k=0}^{+\infty}\sum_{l=1}^{n}\lambda_{li}^{\left[k\right]}\lambda_{ls}^{\left[k\right]}\lambda_{sj}=0\Leftrightarrow\forall k\in\mathbb{N},s,l\in\left[n\right],\lambda_{li}^{\left[k\right]}\lambda_{ls}^{\left[k\right]}\lambda_{sj}=0\right\}. Proof. The proof is given in Appendix G . ∎ In fact, M^{P} is a set of matrices \Lambda such that for all i,j\in[n] , if there exists a directed path from i to j , then after a certain power, the corresponding coefficient \lambda_{ij} stays non-zero. M^{S} is a set of matrices \Lambda such that the infinite sum of certain elements equals zero is equivalent to requiring that each part of the sum equals zero individually. In other words, we prevent cancellations among elements of different powers of \Lambda in this set. Because we consider generic properties of the parameters, we assume that \Lambda\in M^{S}\cap M^{P} . It is reasonable because Lemma 2 implies that M_{G}\backslash\left(M^{S}\cap M^{P}\right) has Lebesgue measure zero. This type of genericity argument was already used in Section 3 . The assumption is needed to establish the relationship between maximal classes and the support of \Sigma in Theorem 2 , and to derive the Jacobian support characterization in Lemma 3 . The necessity for this restriction arises from the infinite-series representation of the stationary covariance in the discrete-time setting as shown in ( 8 ); in contrast, no such assumption is needed for deriving similar results in linear SEMs ( [ 10 , Theorem 4.2] ) or continuous LMs ( [ 28 , Corollary 2.3] ). Theorem 2 . Let \mathbf{M}_{G} be a stationary VAR(1) model with corresponding directed graph G=\left(V,\mathfrak{E}_{G}\right) , then for any two nodes i,j\in[n] , \sigma_{ij}=\sigma_{ji}=0 if and only if i and j do not belong to the same maximal class of G . Proof. For all s,t\in\left\{1,\cdots,n\right\} , let \lambda_{st}^{\left[k\right]}=\left(\Lambda^{k}\right)_{st} . Assume i and j do not belong to the same maximal class, i.e., by definition, there is no directed path between i and j , and additionally, they don’t have the same ”ancestor”. Therefore, by the properties of matrix multiplication, for all k\in\mathbb{N} , \lambda_{ij}^{\left[k\right]}=\lambda_{ji}^{\left[k\right]}=0, and for all l\neq i,j\in\left[n\right] , \lambda_{li}^{\left[k\right]}=0\mbox{ or }\lambda_{lj}^{\left[k\right]}=0. In Section 3 we argued that \left(I_{n^{2}}-\Lambda\otimes\Lambda\right) was generically invertible, which implies that \left(I_{n^{2}}-\Lambda^{T}\otimes\Lambda^{T}\right) is generically invertible since \left(I_{n^{2}}-\Lambda^{T}\otimes\Lambda^{T}\right) is just the transpose of \left(I_{n^{2}}-\Lambda\otimes\Lambda\right) . Hence, from ( 3 ), \displaystyle\mbox{vec}\left(\Sigma\right)=\left(I_{n^{2}}-\Lambda^{T}\otimes\Lambda^{T}\right)^{-1}\mbox{vec}\left(\omega I_{n}\right)=\omega\left(\sum_{k=0}^{+\infty}\left(\Lambda^{T}\otimes\Lambda^{T}\right)^{k}\right)\mbox{vec}\left(I_{n}\right) (8) \displaystyle=\omega\left(\sum_{k=0}^{+\infty}\left(\Lambda^{T}\right)^{k}\otimes\left(\Lambda^{T}\right)^{k}\right)\mbox{vec}\left(I_{n}\right)=\omega\left(\sum_{k=0}^{+\infty}\left(\Lambda^{k}\right)^{T}\otimes\left(\Lambda^{k}\right)^{T}\right)\mbox{vec}\left(I_{n}\right) \displaystyle=\omega\sum_{k=0}^{+\infty}\left[\begin{array}[]{ccccccc}\lambda_{11}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}&\cdots&\lambda_{i1}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}&\cdots&\lambda_{j1}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}&\cdots&\lambda_{n1}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}\\ \vdots&\ddots&\vdots&\ddots&\vdots&\ddots&\vdots\\ \lambda_{1i}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}&\cdots&\lambda_{ii}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}&\cdots&0&\cdots&\lambda_{ni}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}\\ \vdots&\ddots&\vdots&\ddots&\vdots&\ddots&\vdots\\ \lambda_{1j}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}&\cdots&0&\cdots&\lambda_{jj}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}&\cdots&\lambda_{nj}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}\\ \vdots&\ddots&\vdots&\ddots&\vdots&\ddots&\vdots\\ \lambda_{1n}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}&\cdots&\lambda_{in}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}&\cdots&\lambda_{jn}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}&\cdots&\lambda_{nn}^{\left[k\right]}\left(\Lambda^{k}\right)^{T}\\ \end{array}\right]\left[\begin{array}[]{c}1\\ 0\\ \vdots\\ 0\\ 1\\ \vdots\\ 0\\ \vdots\\ 1\end{array}\right], where the second equality is true because the \rho(\Lambda)<1 implies \rho(\Lambda^{T}\otimes\Lambda^{T})<1 . Therefore, \sigma_{ij}=\omega\sum_{k=0}^{+\infty}\sum_{l=1}^{n}\lambda_{li}^{\left[k\right]}\lambda_{lj}^{\left[k\right]}=0=\sigma_{ji}, On the other hand, by Lemma 2 , if for i,j\in V , \sigma_{ij}=\sigma_{ji}=0 , then generically \lambda_{li}^{\left[k\right]}\lambda_{lj}^{\left[k\right]}=0 for all k\in\mathbb{N} and l\in V . Therefore, there is no directed path between i and j , and they do not have the same ancestor. Thus, they do not belong to the same maximal class. ∎ Theorem 2 shows that the maximal classes of the underlying graph are encoded in the support pattern of \Sigma . We now make this correspondence explicit and turn it into a reconstruction procedure. Before stating the result, we introduce the following notation: For all i\in[n] , define the set of nodes that belong to the same maximal class as i : \mathcal{C}_{i}:=\{j\mid j\in[n],i,j\mbox{ belong to the same maximal class}\}. And from Theorem 2 , \mathcal{C}_{i}=\{j\mid j\in[n],\sigma_{ij}\neq 0\}. Note that for all i\in[n] , \mathcal{C}_{i} exists, but may not be a maximal class. For example, in G_{1} of Figure 2 , \mathcal{C}_{4}=\{1,2,3,4,5,6\} is not a maximal class, while \mathcal{C}_{5}=\{4,5,6\} is a maximal class. The following theorem identifies the maximal classes as specific subsets determined by the support of \Sigma . Proposition 3 . Let \mathbf{M}_{G} be a stationary VAR(1) model. Then the set of maximal classes \mathfrak{MC} satisfies \mathfrak{MC}=\mathfrak{C}\backslash\mathfrak{C}^{\prime}, where \displaystyle\mathfrak{C} \displaystyle=\left\{\mathcal{C}_{i}\mid i\in[n]\right\}, \displaystyle\mathfrak{C}^{\prime} \displaystyle=\left\{\mathcal{C}_{i}\in\mathfrak{C}\mid i\in[n],\mbox{ and }\exists k,l\in\mathcal{C}_{i}\ s.t.\ \sigma_{kl}=0\right\}. Proof. First, we prove that \mathfrak{MC}\subseteq\mathfrak{C} . Consider \mathcal{MC}\in\mathfrak{MC} , there exists a source node i\in[n] , s.t. \mathcal{MC}=\mathcal{MC}_{[i]} . By Theorem 2 , for all j\in\mathcal{MC}_{[i]},\sigma_{ij}\neq 0 , hence j\in\mathcal{C}_{i} . Therefore, \mathcal{MC}_{[i]}\subseteq\mathcal{C}_{i}. Assume \exists j\in\mathcal{C}_{i}\backslash\mathcal{MC}_{[i]} , then one of the following circumstances is true: 1. There exists a directed path from i to j , then j\in\mathcal{MC}_{[i]} , which is a contradiction. 2. There exists a directed path from j to i , then {\operatorname{deg}}^{-}(i)\neq 0 , which means that the source of \mathcal{MC}_{[i]} is a SCC containing i . Hence either j belongs to the SCC, then j\in\mathcal{MC}_{[i]} , which is a contradiction, or j does not belong to the SCC, then the in-degree of the SCC is non-zero, i.e., the SCC containing i is not the source of \mathcal{MC}_{[i]} , which is also a contradiction. 3. There exists another node c\in[n] s.t. there are paths from c to i , and from c to j respectively, then {\operatorname{deg}}^{-}(i)\neq 0 , which means that the source of \mathcal{MC}_{[i]} is a SCC containing i . Hence either c belongs to the SCC, then j\in\mathcal{MC}_{[i]} , which is a contradiction, or c does not belong to the SCC, then the in-degree of the SCC is non-zero, i.e., the SCC containing i is not the source of \mathcal{MC}_{[i]} , which is also a contradiction. Therefore \mathcal{MC}_{[i]}=\mathcal{C}_{i}. This proves that \mathfrak{MC}\subseteq\mathfrak{C} . On the other hand, consider \mathcal{C}_{i}\in\mathfrak{C}^{\prime} such that \mathcal{C}_{i}\notin\mathfrak{MC} . Then \mathcal{C}_{i} is not a maximal class, because it contains two nodes that do not belong to the same maximal class by definition. Therefore \mathfrak{MC}\subseteq\mathfrak{C}\backslash\mathfrak{C}^{\prime}. Let \mathcal{C}_{i}\in\mathfrak{C}\backslash\mathfrak{C}^{\prime} for certain i\in[n] and assume that \mathcal{C}_{i}\notin\mathfrak{MC} . We know that i must belong to one maximal class in \mathfrak{MC} . Denote the maximal class containing i as \mathcal{MC}_{i} . Then by Theorem 2 , \mathcal{MC}_{i}\subseteq\mathcal{C}_{i}. Assume k\in\mathcal{C}_{i}\backslash\mathcal{MC}_{i} . Note that |\mathcal{MC}_{i}|>1 because the graph is weakly connected. Then \exists l\neq i\in\mathcal{MC}_{i} s.t. \sigma_{kl}=0 , because otherwise k belongs to the same maximal class with every node in \mathcal{MC}_{i} , in particular with the source node, meaning that k\in\mathcal{MC}_{i} , which is a contradiction. However, k,l\in\mathcal{C}_{i} , and \sigma_{kl}=0 means that \mathcal{C}_{i}\in\mathfrak{C}^{\prime} , which is also a contradiction. Therefore, \mathcal{MC}_{i}=\mathcal{C}_{i}, contradicting the fact that \mathcal{C}_{i}\notin\mathfrak{MC} . In conclusion, \mathfrak{MC}=\mathfrak{C}\backslash\mathfrak{C}^{\prime}. ∎ Algorithm 1 is then obtained via applying the criterion in Proposition 3 . Algorithm 1 Algorithm for the reconstruction of maximal classes via the support of \Sigma Input: \mbox{supp}(\Sigma) Output: the list of maximal classes of G : \mathfrak{MC} 1: \mathfrak{MC}\leftarrow an empty list of lists 2: for all nodes i\in[n] do 3: \mathcal{C}_{i}\leftarrow\{j\mid j\in[n],\sigma_{ij}\neq 0\} 4: add \mathcal{C}_{i} to \mathfrak{MC} 5: for all k,l\in[n]\ s.t.\ kn_{c}^{\prime} . We only introduce the proof for the first case, since the proof of the second case resembles the first one. For a complete proof of the second case, see Appendix J . Now, assume n_{r}\leq n_{c}^{\prime} , and the goal is to prove that under this condition, rank\left(\mathbf{J}_{G}\right)=n_{r} . For this, Lemmas 5 - 8 are needed. They transform the rank of the Jacobian matrix to that of another matrix that is derived from the graph, and prove that this matrix is full rank generically, based on a special graphical structure that exists in all graphs in this case. Let \mathfrak{E}_{G}^{\prime} be the set of edges excluding self-loops, and E_{G}^{\prime}=|\mathfrak{E}_{G}^{\prime}| . Define the set of pairs of nodes such that they are not directly connected by one edge, but belong to the same maximal class: \mathfrak{C}_{G}^{mc}:=\left\{\{k,l\}\mid k,l\in[n],(k,l),(l,k)\notin\mathfrak{E}_{G}^{\prime},\mbox{ and }k,l\mbox{ belong to the same maximal class}\right\}, and denote the cardinality of \mathfrak{C}_{G}^{mc} as C_{G}^{mc} . Under Assumption 1 , the following lemma introduces a necessary and sufficient condition for n_{r}\leq n_{c}^{\prime} . Lemma 5 . Let \mathbf{M}_{G} be a stationary VAR(1) model that satisfies Assumption 1 , then n_{r}\leq n_{c}^{\prime} if and only if there exist two nodes k,l\in\left[n\right] , s.t. \{k,l\}\in\mathfrak{C}_{G}^{mc} . Proof. Assume \forall k,l\in[n] , \{k,l\}\notin\mathfrak{C}_{G}^{mc} . Then either (k,l) or (l,k)\in\mathfrak{E}_{G} or k,l do not belong to the same maximal class, i.e., (\Sigma\Lambda)_{kl}=(\Sigma\Lambda)_{lk}=0 . In this case, n_{c}^{\prime}=E_{G} because for all pairs of nodes i,j\in[n] , (\Sigma\Lambda)_{ij}\neq 0 if and only if \left(i,j\right) or \left(j,i\right)\in\mathfrak{E}_{G} (but never at the same time because of Assumption 1 ). Since n_{r}=E_{G}+1 , n_{r}>n_{c}^{\prime} , which contradicts the premise. ∎ Lemma 5 indicates that under Assumption 1 , the graphs that don’t satisfy n_{r}\leq n_{c}^{\prime} are the ones such that there are at least two maximal classes, and the undirected subgraph of each maximal class is complete. Next, we introduce a new matrix B_{G} derived from the Jacobian matrix. And it will be shown in Lemma 6 that the Jacobian matrix is full rank if the matrix B_{G} is full rank. Definition 12 . Let \mathbf{M}_{G} be a stationary VAR(1) model that satisfies the condition n_{r}\leq n_{c}^{\prime} . Then consider a square matrix of size E_{G}^{\prime}+1 , where the rows correspond to \lambda_{ij} , s.t. \left(i,j\right)\in\mathfrak{E}_{G}^{\prime} , and \omega , and the columns correspond to \sigma_{S} , where S=\left\{\{i,j\}\mid(i,j)\in\mathfrak{E}_{G}^{\prime}\right\}\cup\{\{k,l\}\},\mbox{ for any }\{k,l\}\in\mathfrak{C}_{G}^{mc}. This matrix, denoted as B_{G} , is defined as \displaystyle B_{G}^{\left[\lambda_{ij},\sigma_{ab}\right]} \displaystyle=\delta_{ja}\left[\left(\Sigma\Lambda\right)_{ib}\left(\Sigma\Lambda\right)_{jj}-\left(\Sigma\Lambda\right)_{ij}\left(\Sigma\Lambda\right)_{jb}\right]+\delta_{jb}\left[\left(\Sigma\Lambda\right)_{ia}\left(\Sigma\Lambda\right)_{jj}-\left(\Sigma\Lambda\right)_{ij}\left(\Sigma\Lambda\right)_{ja}\right]; \displaystyle B_{G}^{\left[\omega,\sigma_{ab}\right]} \displaystyle=\left(\Sigma\Lambda\right)_{ab}\left(\Sigma\Lambda\right)_{aa}^{-1}+\left(\Sigma\Lambda\right)_{ba}\left(\Sigma\Lambda\right)_{bb}^{-1}, where a,b\in[n] and \{a,b\}\in S . Note that given a directed graph G , B_{G} might not be unique, because when C_{G}^{mc}>1 , there are multiple options for S . Example 9 . Consider a stationary VAR(1) model \mathbf{M}_{G} with a corresponding directed graph G=\left(V,\mathfrak{E}_{G}\right) , where V=\left\{1,2,3\right\} and \mathfrak{E}_{G}=\left\{\left(1,2\right),\left(2,3\right)\right\} . Here there exists only one B_{G} , which is \displaystyle B_{G}= \displaystyle\left[\begin{array}[]{cc}\left(\Sigma\Lambda\right)_{11}\left(\Sigma\Lambda\right)_{22}-\left(\Sigma\Lambda\right)_{12}\left(\Sigma\Lambda\right)_{21}&\left(\Sigma\Lambda\right)_{13}\left(\Sigma\Lambda\right)_{22}-\left(\Sigma\Lambda\right)_{12}\left(\Sigma\Lambda\right)_{23}\\ 0&\left(\Sigma\Lambda\right)_{22}\left(\Sigma\Lambda\right)_{33}-\left(\Sigma\Lambda\right)_{23}\left(\Sigma\Lambda\right)_{32}\\ \left(\Sigma\Lambda\right)_{12}\left(\Sigma\Lambda\right)_{11}^{-1}+\left(\Sigma\Lambda\right)_{21}\left(\Sigma\Lambda\right)_{22}^{-1}&\left(\Sigma\Lambda\right)_{23}\left(\Sigma\Lambda\right)_{22}^{-1}+\left(\Sigma\Lambda\right)_{32}\left(\Sigma\Lambda\right)_{33}^{-1}\end{array}\right. \displaystyle\left.\begin{array}[]{c}0\\ \left(\Sigma\Lambda\right)_{21}\left(\Sigma\Lambda\right)_{33}-\left(\Sigma\Lambda\right)_{23}\left(\Sigma\Lambda\right)_{31}\\ \left(\Sigma\Lambda\right)_{13}\left(\Sigma\Lambda\right)_{11}^{-1}+\left(\Sigma\Lambda\right)_{31}\left(\Sigma\Lambda\right)_{33}^{-1}\end{array}\right]. Lemma 6 . Let \mathbf{M}_{G} be a stationary VAR(1) model that satisfies Assumption 1 and the condition n_{r}\leq n_{c}^{\prime} . Then \mbox{rank}\left(\mathbf{J}_{G}\right)=n_{r} if there exists a B_{G} that is full rank, i.e., \mbox{rank}\left(B_{G}\right)=E_{G}^{\prime}+1 . Sketch of proof. By Lemma 4 , \mbox{rank}\left(\mathbf{J}_{G}\right)=\mbox{rank}\left(\psi_{G}(B)\right) , and therefore it is sufficient to prove that \mbox{rank}\left(\psi_{G}(B)\right)=n_{r} . Consider a \left(E_{G}+1\right)\times\left(E_{G}+1\right) submatrix of \psi_{G}\left(B\right) , where the columns correspond to the set \left\{\sigma_{ij}\mid i,j\in\left[n\right],(i,j)\mbox{ or }(j,i)\in\mathfrak{E}_{G}\right\}\cup\left\{\sigma_{kl}\right\}, where \left\{k,l\right\}\in\mathfrak{C}_{G}^{mc} . Note that \mathfrak{C}_{G}^{mc}\neq\emptyset by Lemma 5 . In fact, this submatrix is a block matrix after reordering rows and columns. Apply the the Guttman rank additivity formula (see [ 13 ] ), this matrix is full rank if and only if B_{G} is full rank, up to a multiplication of a diagonal matrix with non-zero diagonals. For complete proof, see Appendix I . ∎ Next, we prove that under Assumption 1 and the condition n_{r}\leq n_{c}^{\prime} , B_{G} is generically full rank, i.e., the Jacobian matrix \mathbf{J}_{G} is full rank. Lemma 7 . Let \mathbf{M}_{G} be a stationary VAR(1) model that satisfies the condition n_{r}\leq n_{c}^{\prime} and Assumption 1 . Then there exists three nodes: k,a,l\in\left[n\right] s.t. one of the following circumstances holds: 1. \left(k,a\right),\left(a,l\right)\in\mathfrak{E}_{G}^{\prime} and \left(k,l\right),\left(l,k\right)\notin\mathfrak{E}_{G}^{\prime} . 2. \left(a,k\right),\left(a,l\right)\in\mathfrak{E}_{G}^{\prime} and \left(k,l\right),\left(l,k\right)\notin\mathfrak{E}_{G}^{\prime} . Proof. From Lemma 5 , we know that there exist two nodes k,l\in[n] such that \{k,l\}\in\mathfrak{C}_{G}^{mc} , i.e., (k,l),(l,k)\notin\mathfrak{E}_{G}^{\prime} , but k and l belong to the same maximal class. This ensures the existence of the triplets. ∎ The following lemma states that the set of values such that B_{G} is not full rank has zero Lebesgue measure. We keep the proof in the main text because it again aligns with the generic settings of this paper, and uses the existence of the ”triplet” structure introduced in Lemma 7 , which is technical and insightful. Lemma 8 . Let \mathbf{M}_{G} be a stationary VAR(1) model that satisfies Assumption 1 and n_{r}\leq n_{c}^{\prime} . Define a subset M_{G}^{B} of M_{G} : M_{G}^{B}:=\left\{\Lambda\in M_{G}\mid\det\left(B_{G}\right)=0\right\}, then \mu_{G}\left(M_{G}^{B}\right)=0, where \mu_{G} is the Lebesgue measure defined on \mathbb{R}^{E_{G}} , with E_{G} denoting the number of edges of graph G . Proof. First, we prove that the function \displaystyle f_{G}:M_{G}\times\mathbb{R}^{+} \displaystyle\rightarrow\mathbb{R} \displaystyle\left(\Lambda,\omega\right) \displaystyle\mapsto\det\left(B_{G}\right) is rational. From Appendix C , we know that the parametrization map \displaystyle\phi_{G}:M_{G}\times\mathbb{R}^{+} \displaystyle\rightarrow M_{n}\left(\mathbb{R}\right) \displaystyle\left(\Lambda,\omega\right) \displaystyle\mapsto\Sigma,\mbox{ s.t. }\mbox{vec}\left(\Sigma\right)=\left(I_{n}-\Lambda^{T}\otimes\Lambda^{T}\right)^{-1}\mbox{vec}\left(\omega I_{n}\right), is rational, i.e., \Sigma is a matrix whose elements are rational functions with respect to the elements of \Lambda and \omega . Therefore, \left(\Sigma\Lambda\right) is also a matrix whose elements are rational functions. By definition, the elements of B_{G} are the elements of \left(\Sigma\Lambda\right) after summations, multiplications, and inversions. Hence, they are also rational. Since the determinant is also a result of summations and multiplications of the elements of the matrix, f_{G} is rational, i.e., \exists g,h\in\mathbb{R}\left[\left(\lambda_{ij}\mid\left(i,j\right)\in\mathfrak{E}_{G}\right),\omega\right] polynomials s.t. f_{G}=\frac{g}{h}. Next, we prove that the set of parameters such that h=0 has Lebesgue measure zero. Recall from ( 3 ), for all i,j\in\left[n\right] , \displaystyle\left(\Sigma\Lambda\right)_{ij} \displaystyle=\sum_{k=1}^{n}\sigma_{ik}\lambda_{kj}=\sum_{k=1}^{n}\left(\mbox{vec}\left(\Sigma\right)\right)_{\left(k-1\right)n+i}\lambda_{kj} \displaystyle=\omega\sum_{k=1}^{n}\sum_{l=1}^{n}\left(I_{n^{2}}-\Lambda^{T}\otimes\Lambda^{T}\right)^{-1}_{\left(k-1\right)n+i,\left(l-1\right)n+l}\lambda_{kj}. Since \left(I_{n^{2}}-\Lambda^{T}\otimes\Lambda^{T}\right)^{-1}=\frac{1}{\det\left(I_{n^{2}}-\Lambda^{T}\otimes\Lambda^{T}\right)}\mbox{adj}\left(I_{n^{2}}-\Lambda^{T}\otimes\Lambda^{T}\right), \left(\Sigma\Lambda\right)_{ij}=\frac{P}{Q}, where \mbox{adj}(\cdot) is the adjugate matrix, P\in\mathbb{R}\left[\left(\lambda_{ij}\mid\left(i,j\right)\in\mathfrak{E}_{G}\right),\omega\right] , and Q=\det\left(I_{n^{2}}-\Lambda^{T}\otimes\Lambda^{T}\right)\in\mathbb{R}\left[\lambda_{ij}\mid\left(i,j\right)\in\mathfrak{E}_{G}\right] . Therefore \exists m\in\mathbb{N} s.t. h=Q^{m}\prod_{i=1}^{n}\left(\Sigma\Lambda\right)_{ii}. From the fact that \left(\Sigma\Lambda\right)_{ii}\neq 0 for all i\in\left[n\right] , h=0\Leftrightarrow Q=0\Leftrightarrow\det\left(I_{n^{2}}-\Lambda^{T}\otimes\Lambda^{T}\right)=0\Leftrightarrow\det\left(I_{n^{2}}-\Lambda\otimes\Lambda\right)=0. Therefore, \mu_{G}\left(\left\{\Lambda\in M_{G}\mid h=0\right\}\right)=\mu_{G}\left(\left\{\Lambda\in M_{G}\mid\left(I_{n^{2}}-\Lambda\otimes\Lambda\right)\mbox{ is not invertible}\right\}\right)=0. Finally, we prove that the set of parameters such that g=0 has Lebesgue measure zero. Since \det\left(B_{G}\right) is rational, it’s sufficient to prove that for any directed graph G=\left(V,\mathfrak{E}_{G}\right) that satisfies the premises, there exists \Lambda_{0}\in M_{G} , s.t. \det\left(B_{G_{0}}\right)\neq 0 , where B_{G_{0}} is B_{G} with \Lambda=\Lambda_{0} . From Lemma 7 , there exists three nodes a,k,l\in\left[n\right] , s.t. either \left(k,a\right),\left(a,l\right)\in\mathfrak{E}_{G}^{\prime} and \left(k,l\right),\left(l,k\right)\notin\mathfrak{E}_{G}^{\prime} (Case 1 ), or \left(a,k\right),\left(a,l\right)\in\mathfrak{E}_{G}^{\prime} and \left(k,l\right),\left(l,k\right)\notin\mathfrak{E}_{G}^{\prime} (Case 2 ). In both scenarios, k,l belong to the same maximal class. Consider B_{G} with rows correspond to \lambda_{ij} , where \left(i,j\right)\in\mathfrak{E}_{G}^{\prime} and \omega , and columns correspond to \sigma_{ab} , where \left(a,b\right)\in\mathfrak{E}_{G}^{\prime} , and \sigma_{kl} . We discuss the two cases separately. Case 1 . Consider \Lambda_{0}=\left(\lambda_{ij}^{0}\right) that satisfies: \lambda_{ij}^{0}=\left\{\begin{array}[]{lcl}\lambda_{ij}^{0}\neq 0&,&i=j\mbox{ or }\left(i,j\right)=\left(k,a\right)\mbox{ or }\left(i,j\right)=\left(a,l\right)\\ 0&,&\mbox{otherwise}\end{array}\right., then \left(\Sigma_{0}\Lambda_{0}\right)_{ij}\neq 0\Leftrightarrow i=j\mbox{ or }\left\{i,j\right\}\in\left\{\left\{k,a\right\},\left\{a,l\right\},\left\{k,l\right\}\right\}. Order the rows and columns of B_{G} such that the rows correspond to \lambda_{ka} , \lambda_{al} , \omega and \lambda_{ij} , and the columns correspond to \sigma_{ka} , \sigma_{al} , \sigma_{kl} and \sigma_{ij} respectively, where \left(i,j\right) represents all the edges in \mathfrak{E}_{G}^{\prime} other than \left(k,a\right) and \left(a,l\right) . Note that the columns are ordered along with the corresponding rows. Consider the matrix B_{G_{0}} , which is defined as B_{G} with \Lambda=\Lambda_{0} , and define it as a block matrix: B_{G_{0}}=\left[\begin{array}[]{cc}A&B\\ C&D\end{array}\right], where A is a 3\times 3 matrix consisting of the first three rows and columns of B_{G_{0}} . Then \displaystyle A= \displaystyle\left[\begin{array}[]{ccc}\left(\Sigma_{0}\Lambda_{0}\right)_{kk}\left(\Sigma_{0}\Lambda_{0}\right)_{aa}-\left(\Sigma_{0}\Lambda_{0}\right)_{ka}\left(\Sigma_{0}\Lambda_{0}\right)_{ak}&\left(\Sigma_{0}\Lambda_{0}\right)_{kl}\left(\Sigma_{0}\Lambda_{0}\right)_{aa}-\left(\Sigma_{0}\Lambda_{0}\right)_{ka}\left(\Sigma_{0}\Lambda_{0}\right)_{al}&0\\ 0&\left(\Sigma_{0}\Lambda_{0}\right)_{aa}\left(\Sigma_{0}\Lambda_{0}\right)_{ll}-\left(\Sigma_{0}\Lambda_{0}\right)_{al}\left(\Sigma_{0}\Lambda_{0}\right)_{la}&\left(\Sigma_{0}\Lambda_{0}\right)_{ak}\left(\Sigma_{0}\Lambda_{0}\right)_{ll}-\left(\Sigma_{0}\Lambda_{0}\right)_{al}\left(\Sigma_{0}\Lambda_{0}\right)_{lk}\\ \left(\Sigma_{0}\Lambda_{0}\right)_{ka}\left(\Sigma_{0}\Lambda_{0}\right)_{kk}^{-1}+\left(\Sigma_{0}\Lambda_{0}\right)_{ak}\left(\Sigma_{0}\Lambda_{0}\right)_{aa}^{-1}&\left(\Sigma_{0}\Lambda_{0}\right)_{al}\left(\Sigma_{0}\Lambda_{0}\right)_{aa}^{-1}+\left(\Sigma_{0}\Lambda_{0}\right)_{la}\left(\Sigma_{0}\Lambda_{0}\right)_{ll}^{-1}&\left(\Sigma_{0}\Lambda_{0}\right)_{kl}\left(\Sigma_{0}\Lambda_{0}\right)_{kk}^{-1}+\left(\Sigma_{0}\Lambda_{0}\right)_{lk}\left(\Sigma_{0}\Lambda_{0}\right)_{ll}^{-1}\end{array}\right]. For all \left(i,j\right)\in\mathfrak{E}_{G}^{\prime} , s.t. \left\{i,j\right\}\notin\left\{\left\{a,k\right\},\left\{a,l\right\},\left\{k,l\right\}\right\} , it’s clear that B_{G_{0}}^{\left[\omega,\sigma_{ij}\right]}=\left(\Sigma_{0}\Lambda_{0}\right)_{ij}\left(\Sigma_{0}\Lambda_{0}\right)_{ii}^{-1}+\left(\Sigma_{0}\Lambda_{0}\right)_{ji}\left(\Sigma_{0}\Lambda_{0}\right)_{jj}^{-1}=0. And \displaystyle B_{G_{0}}^{\left[\lambda_{ka},\sigma_{ij}\right]}= \displaystyle\delta_{ai}\left[\left(\Sigma_{0}\Lambda_{0}\right)_{kj}\left(\Sigma_{0}\Lambda_{0}\right)_{aa}-\left(\Sigma_{0}\Lambda_{0}\right)_{ka}\left(\Sigma_{0}\Lambda_{0}\right)_{aj}\right] \displaystyle+\delta_{aj}\left[\left(\Sigma_{0}\Lambda_{0}\right)_{ki}\left(\Sigma_{0}\Lambda_{0}\right)_{aa}-\left(\Sigma_{0}\Lambda_{0}\right)_{ka}\left(\Sigma_{0}\Lambda_{0}\right)_{ai}\right]. When a=i , we know that j\neq a,k,l , so \left(\Sigma_{0}\Lambda_{0}\right)_{kj}=\left(\Sigma_{0}\Lambda_{0}\right)_{aj}=0 , thus \delta_{ai}\left[\left(\Sigma_{0}\Lambda_{0}\right)_{kj}\left(\Sigma_{0}\Lambda_{0}\right)_{aa}-\left(\Sigma_{0}\Lambda_{0}\right)_{ka}\left(\Sigma_{0}\Lambda_{0}\right)_{aj}\right]=0 . Similarly, \delta_{aj}\left[\left(\Sigma_{0}\Lambda_{0}\right)_{ki}\left(\Sigma_{0}\Lambda_{0}\right)_{aa}-\left(\Sigma_{0}\Lambda_{0}\right)_{ka}\left(\Sigma_{0}\Lambda_{0}\right)_{ai}\right]=0 . Therefore, B_{G_{0}}^{\left[\lambda_{ka},\sigma_{ij}\right]}=0 , i.e. B=\mathbf{0}. Use a similar argument, we have C=\mathbf{0}. Therefore, B_{G_{0}} is in fact a block diagonal matrix: B_{G_{0}}=\left[\begin{array}[]{cc}A&\mathbf{0}\\ \mathbf{0}&D\end{array}\right]. Note that \det\left(D\right) is again rational. Let \Lambda_{0}^{\prime}=2I_{n} , then D with \Lambda_{0}=\Lambda_{0}^{\prime} , denoted as D^{\prime} is diagonal, and all the elements on the diagonal are non-zero. So \det\left(D^{\prime}\right)\neq 0 . Therefore, the set of values of \Lambda_{0} such that \det\left(D\right)=0 has Lebesgue measure zero, i.e., \det\left(D\right)\neq 0 , generically. On the other hand, let \Lambda_{0} satisfies: \lambda_{ij}^{0}=\left\{\begin{array}[]{lcl}2&,&i=j\mbox{ or }\left(i,j\right)=\left(k,a\right)\mbox{ or }\left(i,j\right)=\left(a,l\right)\\ 0&,&\mbox{otherwise}\end{array}\right., then \det\left(A\right)\neq 0 . This implies that \det(A)\neq 0 generically. Because the union of finitely many Lebesgue measure zero sets has Lebesgue measure zero, we conclude that \det\left(B_{G_{0}}\right)=\det\left(A\right)\det\left(D\right)\neq 0 generically. Case 2 . Let G_{0}=\left(V,\mathfrak{E}_{G_{0}}\right) where \mathfrak{E}_{G_{0}}=\left\{\left(a,k\right),\left(a,l\right)\right\}, and \lambda_{ij}^{0}=\left\{\begin{array}[]{lcl}2&,&i=j\mbox{ or }\left(i,j\right)=\left(a,k\right)\mbox{ or }\left(i,j\right)=\left(a,l\right)\\ 0&,&\mbox{otherwise}\end{array}\right.. Then using similar arguments as in Case 1, we can prove that \det\left(B_{G_{0}}\right)\neq 0 . Combining all the arguments above, we can conclude that the set of values of \Lambda such that \det\left(B_{G}\right)=0 has Lebesgue measure zero. ∎ Proof of case 1 in Theorem 5 . This is a direct result of Lemmas 6 and 8 . ∎ In conclusion, for graphs without reciprocal edges, the rank of the Jacobian matrix (the dimension of the model) is calculable. As explained in Section 2.2 , models with different dimensions are generically identifiable. With Theorem 5 , the dimensions are known for a subset of models that satisfies Assumption 1 . One interpretation of this result is that for a family of models \left\{\mathbf{M}_{k}\right\}_{k=1}^{K} that satisfy Assumption 1 and the condition n_{r}