Introduction
Many statistical models for a Gaussian vector are defined by the vanishing of minors of its covariance matrix Σ \Sigma Σ , because two components are independent given a set of others exactly when an almost-principal minor of Σ \Sigma Σ is zero [4 ] . In a graphical model a missing edge stands for a conditional independence between two variables. For an undirected graph these relations amount to a zero pattern of Σ − 1 \Sigma^{-1} Σ − 1 [11 ] , while directed acyclic graphs and the wider class of ancestral graphs describe further patterns [18 ] . Since the graph is what is interpreted in applications, every relation it displays must hold for the matrix.
In practice the entries of Σ \Sigma Σ are estimated from data or elicited from experts, so they are seldom known exactly, and a sensitivity analysis studies what happens when some of them are changed. Vanishing minors are polynomial equations, which makes them fragile, and a change of one entry of Σ \Sigma Σ generally moves the matrix off the model. Some conditional independence relations are then lost, although the graph still displays them. It is therefore natural to ask which relations survive and whether some other graph describes the perturbed matrix. Both questions are purely matrix-theoretic once the perturbed matrix is written as a Schur product Δ ∘ Σ \Delta\circ\Sigma Δ ∘ Σ with a symmetric multiplier Δ \Delta Δ , since they ask how the vanishing minors of Σ \Sigma Σ compare with those of Δ ∘ Σ \Delta\circ\Sigma Δ ∘ Σ .
Sensitivity analysis for Gaussian Bayesian networks has mostly dealt with the size of the change. The conditional means and variances of such a network are rational functions of its parameters, so the effect of a change on them can be computed symbolically (Castillo and Kjærulff, 2003). The standard methods perturb the mean vector and the covariance matrix additively, then measure the effect with the Kullback–Leibler or a related divergence [8 ] , which shows how far the distribution has moved without telling which relations were lost. Model-preserving sensitivity analysis addresses the structure instead, by expressing the perturbation through a Schur multiplier that also changes further entries, chosen so that the perturbed matrix stays in the model [9 ] . Several patterns of such changes, called covariations, are known to suffice, at the cost of modifying entries that were not meant to vary. The converse situation, in which an entry is changed with no compensation, has been addressed only for measurement error. Additive noise on a variable increases its variance, which is known to destroy the relations in which that variable is conditioned on [19 ] . A decrease of a variance or a change of a covariance has no such interpretation.
The problem belongs to the algebraic study of Gaussian conditional independence. The minors that can vanish together are constrained by the gaussoid axioms [13 , 1 ] . Trek separation extends the description to rank conditions on arbitrary submatrices [21 ] and to nested determinants [5 ] . For directed acyclic graphs the hypersurface on which one such minor vanishes has been studied in connection with partial correlation testing [12 ] . These works describe the zero patterns of one matrix at a time, whereas a sensitivity analysis compares those of two. Tools for this comparison come from matrix analysis. The Schur product, also called the Hadamard product, has a long history in multivariate statistics [20 ] , and by the Schur product theorem it preserves positive semidefiniteness [10 ] . A change of one entry has rank at most two, so the Sherman–Morrison–Woodbury formula gives the new inverse [10 ] . A change of an off-diagonal entry also moves along the positive definite completions of a partial matrix, which underlie Gaussian Markov combinations [15 ] .
This paper compares the vanishing minors of Σ \Sigma Σ and of Δ ∘ Σ \Delta\circ\Sigma Δ ∘ Σ in two steps. The first asks when a multiplier keeps a minor at zero whatever matrix it is applied to. This happens exactly when the block of Δ \Delta Δ in the rows and columns of the minor has rank one, in which case the minor of Δ ∘ Σ \Delta\circ\Sigma Δ ∘ Σ is the minor of Σ \Sigma Σ times a non-zero constant. The covariation schemes of Görgen and Leonelli [9 ] are instances of this condition. The second step considers changes of variances and covariances with no covariation. Each almost-principal minor of Δ ∘ Σ \Delta\circ\Sigma Δ ∘ Σ is then a polynomial in the amounts added, with minors of Σ \Sigma Σ as coefficients, of degree at most one in each variance and at most two in each covariance. A generic change therefore only removes relations, while new ones can appear only at the roots of these polynomials. For variances the surviving relations are determined by the original structure alone. The same holds for covariances, changed one at a time, as long as no cancellation of partial covariances occurs.
On a graphical model these rules can be read off the graph itself. A change of variances turns an undirected graphical model into another one, whose graph is obtained by joining the neighbors of the perturbed vertices, and ancestral graphs admit a similar description. After a change of covariances, the surviving relations are read off the graph by separation, with each changed covariance acting as an additional edge whose two vertices can no longer separate. This rule holds for every ancestral graph, including directed acyclic graphs, where no such cancellation can occur, and it does not depend on the order in which the covariances are changed. The resulting structure, however, need not be graphical. The graph also identifies the entries that can be varied with no compensation, namely the variances of simplicial vertices and the covariances of adjacent pairs of them, in an undirected graph or in the moral graphs of the ancestral sets of a directed acyclic graph. For the other entries of a decomposable model, the multipliers that preserve it are those with a block of rank one for each edge of a junction tree.
For matrix theory the results describe the Schur multipliers that preserve a determinantal hypersurface of symmetric matrices, and they relate the perturbation of an entry to an operation on the graph of the inverse. For statistics they allow a sensitivity analysis to rest on the conditional independence structure that holds after the change. In an application to the marks of 88 students in five mathematics examinations, a change of one standard error in a single covariance leaves only four of the sixteen relations of the fitted model. All proofs are given in Appendix § 10 .
Setting and definitions
Conditional independence and minors
For Gaussian vectors conditional independence is an algebraic property of the covariance matrix. We write [ n ] = { 1 , … , n } [n] = \{1, \ldots, n\} [ n ] = { 1 , … , n } and P D n \mathrm{PD}_n PD n for the cone of symmetric positive definite n × n n \times n n × n matrices. For R , S ⊆ [ n ] R, S \subseteq[n] R , S ⊆ [ n ] the submatrix of X X X with rows in R R R and columns in S S S is denoted by X R , S X_{R,S} X R , S , abbreviated to X R X_R X R when R = S R = S R = S . When ∣ R ∣ = ∣ S ∣ |R| = |S| ∣ R ∣ = ∣ S ∣ the determinant det X R , S \det X_{R,S} det X R , S is a minor of X X X , which is principal if R = S R = S R = S and almost-principal if the two sets differ in exactly one index ([7 ] ).
Let Y = ( Y 1 , … , Y n ) Y = (Y_1, \ldots, Y_n) Y = ( Y 1 , … , Y n ) be a Gaussian vector with covariance matrix Σ = ( σ i j ) ∈ P D n \Sigma= (\sigma_{ij}) \in\mathrm{PD}_n Σ = ( σ ij ) ∈ PD n . For disjoint A , B , C ⊆ [ n ] A, B, C \subseteq[n] A , B , C ⊆ [ n ] we write A ⊥ ⊥ B ∣ C A \perp\!\!\!\perp B \mid C A ⊥ ⊥ B ∣ C when Y A Y_A Y A and Y B Y_B Y B are conditionally independent given Y C Y_C Y C . This holds exactly when Σ A ∪ C , B ∪ C \Sigma_{A\cup C,B\cup C} Σ A ∪ C , B ∪ C has rank ∣ C ∣ |C| ∣ C ∣ ([4 ] ), or equivalently when i ⊥ ⊥ j ∣ C i \perp\!\!\!\perp j \mid C i ⊥ ⊥ j ∣ C for all i ∈ A i \in A i ∈ A and j ∈ B j \in B j ∈ B . We therefore work with elementary statements ( i j ∣ C ) (ij \mid C) ( ij ∣ C ) , with i ≠ j i \ne j i = j and C ⊆ [ n ] ∖ { i , j } C \subseteq[n] \setminus\{i,j\} C ⊆ [ n ] ∖ { i , j } , which hold for Σ \Sigma Σ when i ⊥ ⊥ j ∣ C i \perp\!\!\!\perp j \mid C i ⊥ ⊥ j ∣ C . We write
a i j ∣ C ( X ) = det X i C , j C , a_{ij\mid C}(X) = \det X_{iC,jC}, a ij ∣ C ( X ) = det X i C , j C ,
where i C iC i C stands for { i } ∪ C \{i\} \cup C { i } ∪ C with i i i listed first and C C C in increasing order. Every almost-principal minor is of this form up to sign. Since det Σ C > 0 \det\Sigma_C > 0 det Σ C > 0 , with the convention det Σ ∅ = 1 \det\Sigma_{\varnothing} = 1 det Σ ∅ = 1 , the submatrix Σ i C , j C \Sigma_{iC,jC} Σ i C , j C has rank at least ∣ C ∣ |C| ∣ C ∣ , and the rank condition takes the form
( i j ∣ C ) holds for Σ ⟺ a i j ∣ C ( Σ ) = 0. (1) (ij \mid C)\text{ holds for }\Sigma\Longleftrightarrow a_{ij\mid C}(\Sigma) = 0. \tag*{(1)} ( ij ∣ C ) holds for Σ ⟺ a ij ∣ C ( Σ ) = 0. (1)
The quotient σ i j ⋅ C = a i j ∣ C ( Σ ) / det Σ C \sigma_{ij\cdot C} = a_{ij\mid C}(\Sigma) / \det\Sigma_C σ ij ⋅ C = a ij ∣ C ( Σ ) / det Σ C is the partial covariance of Y i Y_i Y i and Y j Y_j Y j given Y C Y_C Y C . The conditional independence structure of Σ \Sigma Σ is the set [ [ Σ ] ] [\![\Sigma]\!] [ [ Σ ] ] of all elementary statements that hold for Σ \Sigma Σ , so that it records the vanishing almost-principal minors of Σ \Sigma Σ .
Example 1. Let n = 4 n = 4 n = 4 and consider the covariance matrix
Σ = ( 4 1 3 1 1 4 1 1 3 1 4 1 1 1 1 1 ) . \Sigma=
\begin{pmatrix}
4 & 1 & 3 & 1 \\
1 & 4 & 1 & 1 \\
3 & 1 & 4 & 1 \\
1 & 1 & 1 & 1
\end{pmatrix}. Σ = 4 1 3 1 1 4 1 1 3 1 4 1 1 1 1 1 .
Two of its almost-principal minors are
a 12 ∣ 4 ( Σ ) = det ( σ 12 σ 14 σ 42 σ 44 ) = σ 12 σ 44 − σ 14 σ 42 = 0 , a 23 ∣ 4 ( Σ ) = σ 23 σ 44 − σ 24 σ 43 = 0. a_{12\mid4}(\Sigma) = \det
\begin{pmatrix}
\sigma_{12} & \sigma_{14} \\
\sigma_{42} & \sigma_{44}
\end{pmatrix}
= \sigma_{12}\sigma_{44} - \sigma_{14}\sigma_{42} = 0,\qquad
a_{23\mid4}(\Sigma) = \sigma_{23}\sigma_{44} - \sigma_{24}\sigma_{43} = 0. a 12 ∣ 4 ( Σ ) = det ( σ 12 σ 42 σ 14 σ 44 ) = σ 12 σ 44 − σ 14 σ 42 = 0 , a 23 ∣ 4 ( Σ ) = σ 23 σ 44 − σ 24 σ 43 = 0.
Hence Y 2 Y_2 Y 2 is conditionally independent of ( Y 1 , Y 3 ) (Y_1, Y_3) ( Y 1 , Y 3 ) given Y 4 Y_4 Y 4 . Computing the 24 almost-principal minors a i j ∣ C a_{ij\mid C} a ij ∣ C shows that exactly four vanish, so that [ [ Σ ] ] = { ( 12 ∣ 4 ) , ( 12 ∣ 34 ) , ( 23 ∣ 4 ) , ( 23 ∣ 14 ) } [\![\Sigma]\!] = \{(12 \mid4), (12 \mid34), (23 \mid4), (23 \mid14)\} [ [ Σ ] ] = {( 12 ∣ 4 ) , ( 12 ∣ 34 ) , ( 23 ∣ 4 ) , ( 23 ∣ 14 )} .
Example 2. Let n = 4 n = 4 n = 4 and let Σ \Sigma Σ have entries σ i j = 2 3 − ∣ i − j ∣ \sigma_{ij} = 2^{3-|i-j|} σ ij = 2 3 − ∣ i − j ∣ , that is,
Σ = ( 8 4 2 1 4 8 4 2 2 4 8 4 1 2 4 8 ) . \Sigma=
\begin{pmatrix}
8 & 4 & 2 & 1 \\
4 & 8 & 4 & 2 \\
2 & 4 & 8 & 4 \\
1 & 2 & 4 & 8
\end{pmatrix}. Σ = 8 4 2 1 4 8 4 2 2 4 8 4 1 2 4 8 .
Here a 13 ∣ 2 ( Σ ) = σ 13 σ 22 − σ 12 σ 23 = 2 ⋅ 8 − 4 ⋅ 4 = 0 a_{13\mid2}(\Sigma) = \sigma_{13}\sigma_{22} - \sigma_{12}\sigma_{23} = 2 \cdot8 - 4 \cdot4 = 0 a 13 ∣ 2 ( Σ ) = σ 13 σ 22 − σ 12 σ 23 = 2 ⋅ 8 − 4 ⋅ 4 = 0 , so Y 1 Y_1 Y 1 and Y 3 Y_3 Y 3 are conditionally independent given Y 2 Y_2 Y 2 . In total seven statements hold, so that the structure of this matrix is [ [ Σ ] ] = { ( 13 ∣ 2 ) , ( 13 ∣ 24 ) , ( 24 ∣ 3 ) , ( 24 ∣ 13 ) , ( 14 ∣ 2 ) , ( 14 ∣ 3 ) , ( 14 ∣ 23 ) } [\![\Sigma]\!] = \{(13 \mid2), (13 \mid24), (24 \mid3), (24 \mid13), (14 \mid2), (14 \mid3), (14 \mid23)\} [ [ Σ ] ] = {( 13 ∣ 2 ) , ( 13 ∣ 24 ) , ( 24 ∣ 3 ) , ( 24 ∣ 13 ) , ( 14 ∣ 2 ) , ( 14 ∣ 3 ) , ( 14 ∣ 23 )} .
Graphical models
A graph displays a conditional independence structure by means of separation. Only undirected graphs are needed until § 5.2 , where ancestral graphs are introduced. Let G = ( [ n ] , E ) G = ([n], E) G = ([ n ] , E ) be an undirected graph. A set C C C separates i i i from j j j if every path between them contains a vertex of C C C , and I ( G ) I(G) I ( G ) denotes the set of statements ( i j ∣ C ) (ij \mid C) ( ij ∣ C ) such that C C C separates i i i from j j j in G G G . The Gaussian graphical model of G G G is the set of positive definite matrices
M ( G ) = { Σ ∈ P D n : ( Σ − 1 ) i j = 0 whenever i ≠ j and { i , j } ∉ E } . \mathcal{M}(G) = \{\Sigma\in\mathrm{PD}_n : (\Sigma^{-1})_{ij} = 0 \text{ whenever } i \ne j \text{ and } \{i,j\} \notin E\}. M ( G ) = { Σ ∈ PD n : ( Σ − 1 ) ij = 0 whenever i = j and { i , j } ∈ / E } .
The set I ( G ) I(G) I ( G ) is defined from the graph alone. Its link with matrices is the global Markov property, by which every Σ ∈ M ( G ) \Sigma\in\mathcal{M}(G) Σ ∈ M ( G ) satisfies all the statements of I ( G ) I(G) I ( G ) [11 ] . Such a matrix is faithful to G G G if it satisfies no other statement, that is, if [ [ Σ ] ] = I ( G ) [\![\Sigma]\!] = I(G) [ [ Σ ] ] = I ( G ) . More generally, a matrix Σ ∈ P D n \Sigma\in\mathrm{PD}_n Σ ∈ PD n is Markov to a graph G G G if it satisfies all the statements of I ( G ) I(G) I ( G ) , and the matrices that are Markov to an undirected graph are those of M ( G ) \mathcal{M}(G) M ( G ) . Faithfulness is automatic when all off-diagonal entries of Σ − 1 \Sigma^{-1} Σ − 1 are non-positive, in which case Σ \Sigma Σ is faithful to the graph of the non-zero off-diagonal entries of its inverse [6 ] . We write ne ( k ) \operatorname{ne}(k) ne ( k ) for the set of neighbours of a vertex k k k and N [ k ] = ne ( k ) ∪ { k } N[k] = \operatorname{ne}(k) \cup\{k\} N [ k ] = ne ( k ) ∪ { k } .
Example 3. The matrices of Examples 1 and 2 are faithful to the graphs of Figure 1 . In the first graph vertex 4 separates 2 from the other vertices, so the inverse has zeros exactly in positions ( 1 , 2 ) (1,2) ( 1 , 2 ) and ( 2 , 3 ) (2,3) ( 2 , 3 ) . For the path the inverse is tridiagonal, with zeros in positions ( 1 , 3 ) (1,3) ( 1 , 3 ) , ( 1 , 4 ) (1,4) ( 1 , 4 ) and ( 2 , 4 ) (2,4) ( 2 , 4 ) .
Figure 1. The graphs of the two running examples, with (a) the graph of Example 1 and (b) the path of Example 2.
Multipliers and perturbations
A sensitivity analysis replaces some entries of Σ \Sigma Σ by new values. Such a change can be written as an entrywise product, which rescales several entries at once by possibly different factors, or as a sum, which adds an amount to each changed entry. We use both forms, the multiplicative one to describe which relations are preserved and the additive one to compute how the minors change.
The Schur product of two matrices of equal size is their entrywise product, Δ ∘ X = ( δ a b x a b ) \Delta\circ X = (\delta_{ab}x_{ab}) Δ ∘ X = ( δ ab x ab ) . A multiplier is a symmetric n × n n \times n n × n matrix Δ \Delta Δ with non-zero entries and positive diagonal. The diagonal must be positive because the variances of Δ ∘ Σ \Delta\circ\Sigma Δ ∘ Σ have to stay positive. The entries are non-zero so that the map Σ ↦ Δ ∘ Σ \Sigma\mapsto\Delta\circ\Sigma Σ ↦ Δ ∘ Σ is invertible, its inverse being defined by the entrywise reciprocal of Δ \Delta Δ . The map is considered on the subset of P D n \mathrm{PD}_n PD n given by
U Δ = { Σ ∈ P D n : Δ ∘ Σ ∈ P D n } U_{\Delta} = \{\Sigma\in\mathrm{PD}_n : \Delta\circ\Sigma\in\mathrm{PD}_n\} U Δ = { Σ ∈ PD n : Δ ∘ Σ ∈ PD n }
of covariance matrices whose image is again a covariance matrix. If Δ \Delta Δ is positive semidefinite, it is always the whole cone P D n \mathrm{PD}_n PD n by the Schur product theorem [10 ] . In additive form Δ ∘ Σ = Σ + D \Delta\circ\Sigma= \Sigma+ D Δ ∘ Σ = Σ + D , where D = ( Δ − J ) ∘ Σ D = (\Delta- J) \circ\Sigma D = ( Δ − J ) ∘ Σ and J J J is the all-ones matrix. Weyl’s inequality then shows that Σ ∈ U Δ \Sigma\in U_{\Delta} Σ ∈ U Δ whenever the spectral radius of D D D is smaller than the smallest eigenvalue of Σ \Sigma Σ .
The simplest multipliers change a single parameter. Writing E k l E_{kl} E k l for the matrix with a one in position ( k , l ) (k,l) ( k , l ) and zeros elsewhere, a variance is changed by Δ = J + ( δ − 1 ) E k k \Delta= J + (\delta- 1)E_{kk} Δ = J + ( δ − 1 ) E k k , which replaces σ k k \sigma_{kk} σ k k by δ σ k k \delta\sigma_{kk} δ σ k k . In additive form this is Σ + τ E k k \Sigma+ \tau E_{kk} Σ + τ E k k with τ = ( δ − 1 ) σ k k \tau= (\delta- 1)\sigma_{kk} τ = ( δ − 1 ) σ k k . A covariance is changed by Δ = J + ( δ − 1 ) ( E k l + E l k ) \Delta= J + (\delta- 1)(E_{kl} + E_{lk}) Δ = J + ( δ − 1 ) ( E k l + E l k ) , or additively by Σ + τ ( E k l + E l k ) \Sigma+ \tau(E_{kl} + E_{lk}) Σ + τ ( E k l + E l k ) with τ = ( δ − 1 ) σ k l \tau= (\delta- 1)\sigma_{kl} τ = ( δ − 1 ) σ k l . We call the added amount τ \tau τ the size of the perturbation. The admissible sizes, those for which the perturbed matrix is positive definite, form an open interval around zero because P D n \mathrm{PD}_n PD n is open and convex. An increase of a variance is always admissible, since J + ( δ − 1 ) E k k J+(\delta-1)E_{kk} J + ( δ − 1 ) E k k is positive semidefinite for δ > 1 \delta>1 δ > 1 .
Let M ⊆ P D n \mathcal{M}\subseteq\mathrm{PD}_n M ⊆ PD n be a set of covariance matrices, for instance a graphical model or the set of matrices that satisfy a given statement. A multiplier Δ \Delta Δ is called model-preserving for M \mathcal{M} M if Δ ∘ Σ ∈ M \Delta\circ\Sigma\in\mathcal{M} Δ ∘ Σ ∈ M for every Σ ∈ M ∩ U Δ \Sigma\in\mathcal{M}\cap U_\Delta Σ ∈ M ∩ U Δ . A multiplier that changes one parameter is rarely model-preserving. The approach of Görgen and Leonelli [9 ] is to add a covariation , that is, to change further entries at the same time so that the multiplier becomes model-preserving.
Example 4. In Example 1 suppose that σ 12 \sigma_{12} σ 12 is replaced by δ σ 12 \delta\sigma_{12} δ σ 12 with δ ≠ 1 \delta\ne1 δ = 1 . Then
a 12 ∣ 4 ( Δ ∘ Σ ) = δ σ 12 σ 44 − σ 14 σ 42 = δ − 1 ≠ 0. a_{12\mid4}(\Delta\circ\Sigma)=\delta\sigma_{12}\sigma_{44}-\sigma_{14}\sigma_{42}=\delta-1\ne0. a 12 ∣ 4 ( Δ ∘ Σ ) = δ σ 12 σ 44 − σ 14 σ 42 = δ − 1 = 0.
The variables Y 1 Y_1 Y 1 and Y 2 Y_2 Y 2 are no longer conditionally independent given Y 4 Y_4 Y 4 , so the perturbed matrix has left the model of the graph. Suppose instead that σ 23 \sigma_{23} σ 23 and σ 24 \sigma_{24} σ 24 are multiplied by δ \delta δ as well, which corresponds to the choice of multiplier
Δ = ( 1 δ 1 1 δ 1 δ δ 1 δ 1 1 1 δ 1 1 ) . \Delta=\begin{pmatrix}
1 & \delta& 1 & 1\\
\delta& 1 & \delta& \delta\\
1 & \delta& 1 & 1\\
1 & \delta& 1 & 1
\end{pmatrix}. Δ = 1 δ 1 1 δ 1 δ δ 1 δ 1 1 1 δ 1 1 .
Now a 12 ∣ 4 ( Δ ∘ Σ ) = δ σ 12 σ 44 − σ 14 δ σ 42 = 0 a_{12\mid4}(\Delta\circ\Sigma)=\delta\sigma_{12}\sigma_{44}-\sigma_{14}\delta\sigma_{42}=0 a 12 ∣ 4 ( Δ ∘ Σ ) = δ σ 12 σ 44 − σ 14 δ σ 42 = 0 and a 23 ∣ 4 ( Δ ∘ Σ ) = δ σ 23 σ 44 − δ σ 24 σ 43 = 0 a_{23\mid4}(\Delta\circ\Sigma)=\delta\sigma_{23}\sigma_{44}-\delta\sigma_{24}\sigma_{43}=0 a 23 ∣ 4 ( Δ ∘ Σ ) = δ σ 23 σ 44 − δ σ 24 σ 43 = 0 , so the model is preserved. The price is that two entries have changed that were not meant to.
Vanishing minors under perturbation
Multipliers that preserve a statement
Multiplying the rows and columns of a matrix by non-zero constants does not change which of its minors vanish. A multiplier acts in this way on a block X R , S X_{R,S} X R , S when Δ R , S = u v T \Delta_{R,S}=uv^{\mathsf{T}} Δ R , S = u v T has rank one, since then ( Δ ∘ X ) R , S = diag ( u ) X R , S diag ( v ) (\Delta\circ X)_{R,S}=\operatorname{diag}(u)X_{R,S}\operatorname{diag}(v) ( Δ ∘ X ) R , S = diag ( u ) X R , S diag ( v ) . The next theorem shows that this is the only mechanism.
Theorem 1. Let Δ \Delta Δ be a multiplier and ( i j ∣ C ) (ij\mid C) ( ij ∣ C ) a statement with C ≠ ∅ C\ne\varnothing C = ∅ .
(a) If rank Δ i C , j C = 1 \operatorname{rank}\Delta_{iC,jC}=1 rank Δ i C , j C = 1 , then Δ ∘ Σ \Delta\circ\Sigma Δ ∘ Σ satisfies the statement if and only if Σ \Sigma Σ does, for every Σ ∈ U Δ \Sigma\in U_\Delta Σ ∈ U Δ .
(b) If rank Δ i C , j C > 1 \operatorname{rank}\Delta_{iC,jC}>1 rank Δ i C , j C > 1 , then Δ ∘ Σ \Delta\circ\Sigma Δ ∘ Σ violates it for a dense open set of the Σ ∈ U Δ \Sigma\in U_\Delta Σ ∈ U Δ that satisfy it.
Consequently, for disjoint non-empty A A A , B B B , C ⊆ [ n ] C\subseteq[n] C ⊆ [ n ] , the multiplier Δ \Delta Δ is model-preserving for the set of matrices that satisfy A ⊥ ⊥ B ∣ C A\perp\!\!\perp B\mid C A ⊥ ⊥ B ∣ C if and only if the block Δ A ∪ C , B ∪ C \Delta_{A\cup C,B\cup C} Δ A ∪ C , B ∪ C has rank one.
A multiplier preserves a statement only when it rescales the rows and the columns of the corresponding submatrix. A statement with C = ∅ C=\varnothing C = ∅ says that σ i j = 0 \sigma_{ij}=0 σ ij = 0 and is preserved by every multiplier. Since blocks of rank one are closed under Schur products and entrywise inverses, the multipliers that preserve a given statement form a group. Covariations chosen for different parameters can thus be applied one after the other, which is how Görgen and Leonelli [9 ] vary several parameters at the same time.
Example 5. The model of the graph in Example 1 is the set of matrices that satisfy 2 ⊥ ⊥ { 1 , 3 } ∣ 4 2\perp\!\!\perp\{1,3\}\mid4 2 ⊥ ⊥ { 1 , 3 } ∣ 4 . The corresponding block of a multiplier has rows { 2 , 4 } \{2,4\} { 2 , 4 } and columns { 1 , 3 , 4 } \{1,3,4\} { 1 , 3 , 4 } . If only σ 12 \sigma_{12} σ 12 is multiplied by a factor δ \delta δ , this block takes the form
Δ 24 , 134 = ( δ 1 1 1 1 1 ) , \Delta_{24,134}=\begin{pmatrix}
\delta& 1 & 1\\
1 & 1 & 1
\end{pmatrix}, Δ 24 , 134 = ( δ 1 1 1 1 1 ) ,
@page 5/25 starts_mid=1 ends_mid=1 added amount τ \tau τ the size of the perturbation. The admissible sizes, those for which the perturbed matrix is positive definite, form an open interval around zero because P D n \mathrm{PD}_n PD n is open and convex. An increase of a variance is always admissible, since J + ( δ − 1 ) E k k J+(\delta-1)E_{kk} J + ( δ − 1 ) E k k is positive semidefinite for δ > 1 \delta>1 δ > 1 .
Let M ⊆ P D n \mathcal{M}\subseteq\mathrm{PD}_n M ⊆ PD n be a set of covariance matrices, for instance a graphical model or the set of matrices that satisfy a given statement. A multiplier Δ \Delta Δ is called model-preserving for M \mathcal{M} M if Δ ∘ Σ ∈ M \Delta\circ\Sigma\in\mathcal{M} Δ ∘ Σ ∈ M for every Σ ∈ M ∩ U Δ \Sigma\in\mathcal{M}\cap U_\Delta Σ ∈ M ∩ U Δ . A multiplier that changes one parameter is rarely model-preserving. The approach of Görgen and Leonelli [9 ] is to add a covariation , that is, to change further entries at the same time so that the multiplier becomes model-preserving.
Example 4. In Example 1 suppose that σ 12 \sigma_{12} σ 12 is replaced by δ σ 12 \delta\sigma_{12} δ σ 12 with δ ≠ 1 \delta\ne1 δ = 1 . Then
a 12 ∣ 4 ( Δ ∘ Σ ) = δ σ 12 σ 44 − σ 14 σ 42 = δ − 1 ≠ 0. a_{12\mid4}(\Delta\circ\Sigma)=\delta\sigma_{12}\sigma_{44}-\sigma_{14}\sigma_{42}=\delta-1\ne0. a 12 ∣ 4 ( Δ ∘ Σ ) = δ σ 12 σ 44 − σ 14 σ 42 = δ − 1 = 0.
The variables Y 1 Y_1 Y 1 and Y 2 Y_2 Y 2 are no longer conditionally independent given Y 4 Y_4 Y 4 , so the perturbed matrix has left the model of the graph. Suppose instead that σ 23 \sigma_{23} σ 23 and σ 24 \sigma_{24} σ 24 are multiplied by δ \delta δ as well, which corresponds to the choice of multiplier
Δ = ( 1 δ 1 1 δ 1 δ δ 1 δ 1 1 1 δ 1 1 ) . \Delta=\begin{pmatrix}
1 & \delta& 1 & 1\\
\delta& 1 & \delta& \delta\\
1 & \delta& 1 & 1\\
1 & \delta& 1 & 1
\end{pmatrix}. Δ = 1 δ 1 1 δ 1 δ δ 1 δ 1 1 1 δ 1 1 .
Now a 12 ∣ 4 ( Δ ∘ Σ ) = δ σ 12 σ 44 − σ 14 δ σ 42 = 0 a_{12\mid4}(\Delta\circ\Sigma)=\delta\sigma_{12}\sigma_{44}-\sigma_{14}\delta\sigma_{42}=0 a 12 ∣ 4 ( Δ ∘ Σ ) = δ σ 12 σ 44 − σ 14 δ σ 42 = 0 and a 23 ∣ 4 ( Δ ∘ Σ ) = δ σ 23 σ 44 − δ σ 24 σ 43 = 0 a_{23\mid4}(\Delta\circ\Sigma)=\delta\sigma_{23}\sigma_{44}-\delta\sigma_{24}\sigma_{43}=0 a 23 ∣ 4 ( Δ ∘ Σ ) = δ σ 23 σ 44 − δ σ 24 σ 43 = 0 , so the model is preserved. The price is that two entries have changed that were not meant to.
Vanishing minors under perturbation
Multipliers that preserve a statement
Multiplying the rows and columns of a matrix by non-zero constants does not change which of its minors vanish. A multiplier acts in this way on a block X R , S X_{R,S} X R , S when Δ R , S = u v T \Delta_{R,S}=uv^{\mathsf{T}} Δ R , S = u v T has rank one, since then ( Δ ∘ X ) R , S = diag ( u ) X R , S diag ( v ) (\Delta\circ X)_{R,S}=\operatorname{diag}(u)X_{R,S}\operatorname{diag}(v) ( Δ ∘ X ) R , S = diag ( u ) X R , S diag ( v ) . The next theorem shows that this is the only mechanism.
Theorem 1. Let Δ \Delta Δ be a multiplier and ( i j ∣ C ) (ij\mid C) ( ij ∣ C ) a statement with C ≠ ∅ C\ne\varnothing C = ∅ .
(a) If rank Δ i C , j C = 1 \operatorname{rank}\Delta_{iC,jC}=1 rank Δ i C , j C = 1 , then Δ ∘ Σ \Delta\circ\Sigma Δ ∘ Σ satisfies the statement if and only if Σ \Sigma Σ does, for every Σ ∈ U Δ \Sigma\in U_\Delta Σ ∈ U Δ .
(b) If rank Δ i C , j C > 1 \operatorname{rank}\Delta_{iC,jC}>1 rank Δ i C , j C > 1 , then Δ ∘ Σ \Delta\circ\Sigma Δ ∘ Σ violates it for a dense open set of the Σ ∈ U Δ \Sigma\in U_\Delta Σ ∈ U Δ that satisfy it.
Consequently, for disjoint non-empty A A A , B B B , C ⊆ [ n ] C\subseteq[n] C ⊆ [ n ] , the multiplier Δ \Delta Δ is model-preserving for the set of matrices that satisfy A ⊥ ⊥ B ∣ C A\perp\!\!\perp B\mid C A ⊥ ⊥ B ∣ C if and only if the block Δ A ∪ C , B ∪ C \Delta_{A\cup C,B\cup C} Δ A ∪ C , B ∪ C has rank one.
A multiplier preserves a statement only when it rescales the rows and the columns of the corresponding submatrix. A statement with C = ∅ C=\varnothing C = ∅ says that σ i j = 0 \sigma_{ij}=0 σ ij = 0 and is preserved by every multiplier. Since blocks of rank one are closed under Schur products and entrywise inverses, the multipliers that preserve a given statement form a group. Covariations chosen for different parameters can thus be applied one after the other, which is how Görgen and Leonelli [9 ] vary several parameters at the same time.
Example 5. The model of the graph in Example 1 is the set of matrices that satisfy 2 ⊥ ⊥ { 1 , 3 } ∣ 4 2\perp\!\!\perp\{1,3\}\mid4 2 ⊥ ⊥ { 1 , 3 } ∣ 4 . The corresponding block of a multiplier has rows { 2 , 4 } \{2,4\} { 2 , 4 } and columns { 1 , 3 , 4 } \{1,3,4\} { 1 , 3 , 4 } . If only σ 12 \sigma_{12} σ 12 is multiplied by a factor δ \delta δ , this block takes the form
Δ 24 , 134 = ( δ 1 1 1 1 1 ) , \Delta_{24,134}=\begin{pmatrix}
\delta& 1 & 1\\
1 & 1 & 1
\end{pmatrix}, Δ 24 , 134 = ( δ 1 1 1 1 1 ) ,
which has rank two. By Theorem 1 the multiplier is not model-preserving, in agreement with Example 4. The block has rank one for each of the choices
( δ δ δ 1 1 1 ) , ( δ 1 1 δ 1 1 ) , ( δ 1 1 1 δ − 1 δ − 1 ) . \begin{pmatrix} \delta& \delta& \delta\\ 1 & 1 & 1 \end{pmatrix}, \qquad
\begin{pmatrix} \delta& 1 & 1 \\ \delta& 1 & 1 \end{pmatrix}, \qquad
\begin{pmatrix} \delta& 1 & 1 \\ 1 & \delta^{-1} & \delta^{-1} \end{pmatrix}. ( δ 1 δ 1 δ 1 ) , ( δ δ 1 1 1 1 ) , ( δ 1 1 δ − 1 1 δ − 1 ) .
The first is the covariation of Example 4. The second multiplies σ 14 \sigma_{14} σ 14 by δ \delta δ instead. Both fill a whole row or column of the block with δ \delta δ , the pattern of the covariations in Görgen and Leonelli [9 ] . The third, with δ > 0 \delta> 0 δ > 0 , divides σ 34 \sigma_{34} σ 34 and σ 44 \sigma_{44} σ 44 by δ \delta δ , a covariation outside these schemes allowed by Theorem 1. With factors δ \delta δ , δ ′ \delta^{\prime} δ ′ the Schur product of the first two has rows ( δ δ ′ , δ , δ ) (\delta\delta^{\prime},\delta,\delta) ( δ δ ′ , δ , δ ) and ( δ ′ , 1 , 1 ) (\delta^{\prime},1,1) ( δ ′ , 1 , 1 ) , again of rank one.
Change of variances
From now on we write a change in the additive form of § 2.3 , which adds an amount to each changed entry and also covers a zero covariance. These amounts are the sizes of the change, forming a vector τ \tau τ . Every minor of the perturbed matrix is a polynomial in τ \tau τ , equal to the minor of Σ \Sigma Σ at τ = 0 \tau=0 τ = 0 .
Definition 2. A property of the perturbed matrix holds for generic τ \tau τ if the sizes at which it fails lie in a proper algebraic subset of the space of sizes. This subset may depend on Σ \Sigma Σ .
Such a subset is closed and has measure zero. It is finite when a single parameter changes, because a non-zero polynomial in one variable has finitely many roots. If a statement fails for Σ \Sigma Σ , its minor in the perturbed matrix is a polynomial in τ \tau τ that is non-zero at τ = 0 \tau=0 τ = 0 , so the statement fails for generic τ \tau τ . It can still hold at exceptional sizes, as at τ = − 1 \tau=-1 τ = − 1 in Example 6. Since there are finitely many statements and a finite union of proper algebraic subsets is again proper, a generic change creates no new statement. The question is then which statements of Σ \Sigma Σ it removes. For variances the answer comes from expanding each minor along the perturbed diagonal entries.
Proposition 3. Let Σ ∈ P D n \Sigma\in\mathrm{PD}_n Σ ∈ PD n , K ⊆ [ n ] K \subseteq[n] K ⊆ [ n ] , τ ∈ R K \tau\in\mathbb{R}^{K} τ ∈ R K and Σ ′ = Σ + ∑ k ∈ K τ k E k k \Sigma^{\prime} = \Sigma+ \sum_{k\in K} \tau_k E_{kk} Σ ′ = Σ + ∑ k ∈ K τ k E k k . For each statement ( i j ∣ C ) (ij \mid C) ( ij ∣ C ) ,
a i j ∣ C ( Σ ′ ) = ∑ T ⊆ K ∩ C ∏ k ∈ T τ k a i j ∣ C ∖ T ( Σ ) . (2) a_{ij\mid C}(\Sigma^{\prime}) = \sum_{T\subseteq K\cap C} \prod_{k\in T}\tau_k\,a_{ij\mid C\setminus T}(\Sigma). \tag*{(2)} a ij ∣ C ( Σ ′ ) = T ⊆ K ∩ C ∑ k ∈ T ∏ τ k a ij ∣ C ∖ T ( Σ ) . (2) Consequently, if Σ ′ ∈ P D n \Sigma^{\prime} \in\mathrm{PD}_n Σ ′ ∈ PD n it satisfies each statement of the set below, which equals [ [ Σ ′ ] ] [\![\Sigma^{\prime}]\!] [ [ Σ ′ ] ] for generic τ \tau τ ,
{ ( i j ∣ C ) ∈ [ [ Σ ] ] : ( i j ∣ C ∖ T ) ∈ [ [ Σ ] ] for all T ⊆ K ∩ C } . (3) \{(ij\mid C)\in[\![\Sigma]\!]: (ij\mid C\setminus T)\in[\![\Sigma]\!] \text{ for all } T\subseteq K\cap C\}. \tag*{(3)} {( ij ∣ C ) ∈ [ [ Σ ] ] : ( ij ∣ C ∖ T ) ∈ [ [ Σ ] ] for all T ⊆ K ∩ C } . (3)
A statement survives a change of the variance of Y k Y_k Y k when Y k Y_k Y k is not one of its conditioning variables, or when the statement holds also without conditioning on Y k Y_k Y k . For τ k > 0 \tau_k>0 τ k > 0 the matrix Σ ′ \Sigma^{\prime} Σ ′ is the covariance of the vector with Y k Y_k Y k replaced by Y k + ε k Y_k+\varepsilon_k Y k + ε k , where ε k \varepsilon_k ε k is independent noise of variance τ k \tau_k τ k . Conditioning on this noisy version does not remove the dependence explained by Y k Y_k Y k itself (Saeed et al. [19 ] ). By identity (2) , a decrease of the variance has the same effect on the statements that condition on Y k Y_k Y k .
Example 6. In Example 1 add τ \tau τ to σ 44 \sigma_{44} σ 44 . All four statements condition on Y 4 Y_4 Y 4 . Their minors vanish for Σ \Sigma Σ , so identity (2) gives the four values
a 12 ∣ 4 ( Σ ′ ) = τ σ 12 , a 12 ∣ 34 ( Σ ′ ) = τ a 12 ∣ 3 ( Σ ) , a 23 ∣ 4 ( Σ ′ ) = τ σ 23 , a 23 ∣ 14 ( Σ ′ ) = τ a 23 ∣ 1 ( Σ ) . a_{12\mid4}(\Sigma^{\prime})=\tau\sigma_{12},\qquad
a_{12\mid34}(\Sigma^{\prime})=\tau a_{12\mid3}(\Sigma),\qquad
a_{23\mid4}(\Sigma^{\prime})=\tau\sigma_{23},\qquad
a_{23\mid14}(\Sigma^{\prime})=\tau a_{23\mid1}(\Sigma). a 12 ∣ 4 ( Σ ′ ) = τ σ 12 , a 12 ∣ 34 ( Σ ′ ) = τ a 12 ∣ 3 ( Σ ) , a 23 ∣ 4 ( Σ ′ ) = τ σ 23 , a 23 ∣ 14 ( Σ ′ ) = τ a 23 ∣ 1 ( Σ ) . which are all equal to τ \tau τ . No statement survives, whatever the size. A change of σ 11 \sigma_{11} σ 11 behaves differently. The only statement that conditions on Y 1 Y_1 Y 1 is ( 23 ∣ 14 ) (23\mid14) ( 23 ∣ 14 ) , and a 23 ∣ 14 ( Σ ′ ) = a 23 ∣ 14 ( Σ ) + τ a 23 ∣ 4 ( Σ ) = 0 a_{23\mid14}(\Sigma^{\prime})=a_{23\mid14}(\Sigma)+\tau a_{23\mid4}(\Sigma)=0 a 23 ∣ 14 ( Σ ′ ) = a 23 ∣ 14 ( Σ ) + τ a 23 ∣ 4 ( Σ ) = 0 . The structure is unchanged except at τ = − 1 \tau=-1 τ = − 1 , where ( 23 ∣ 1 ) (23\mid1) ( 23 ∣ 1 ) , ( 34 ∣ 1 ) (34\mid1) ( 34 ∣ 1 ) and ( 34 ∣ 12 ) (34\mid12) ( 34 ∣ 12 ) hold in addition.
Example 7. In Example 2 add τ \tau τ to σ 22 \sigma_{22} σ 22 . Three statements are lost, since
a 13 ∣ 2 ( Σ ′ ) = τ σ 13 = 2 τ , a 14 ∣ 2 ( Σ ′ ) = τ σ 14 = τ , a_{13|2}(\Sigma')=\tau\sigma_{13}=2\tau,\qquad a_{14|2}(\Sigma')=\tau\sigma_{14}=\tau, a 13∣2 ( Σ ′ ) = τ σ 13 = 2 τ , a 14∣2 ( Σ ′ ) = τ σ 14 = τ ,
and a 13 ∣ 24 ( Σ ′ ) = τ a 13 ∣ 4 ( Σ ) = 12 τ a_{13|24}(\Sigma')=\tau a_{13|4}(\Sigma)=12\tau a 13∣24 ( Σ ′ ) = τ a 13∣4 ( Σ ) = 12 τ . The statement ( 14 ∣ 23 ) (14\mid23) ( 14 ∣ 23 ) survives because ( 14 ∣ 3 ) (14\mid3) ( 14 ∣ 3 ) holds, and the three statements that do not condition on Y 2 Y_2 Y 2 are untouched. The perturbed structure is { ( 14 ∣ 3 ) , ( 14 ∣ 23 ) , ( 24 ∣ 3 ) , ( 24 ∣ 13 ) } \{(14\mid3),(14\mid23),(24\mid3),(24\mid13)\} {( 14 ∣ 3 ) , ( 14 ∣ 23 ) , ( 24 ∣ 3 ) , ( 24 ∣ 13 )} .
Change of one covariance
When σ k l \sigma_{kl} σ k l changes, an almost-principal minor is affected only if its submatrix contains the position ( k , l ) (k,l) ( k , l ) or ( l , k ) (l,k) ( l , k ) . This requires both k k k and l l l to occur in the statement, either as endpoints or as conditioning variables, which leaves three cases to consider, depending on the roles of k k k and l l l .
Proposition 4. Let Σ ∈ P D n \Sigma\in\mathrm{PD}_n Σ ∈ PD n , k ≠ l k\ne l k = l and Σ ′ = Σ + τ ( E k l + E l k ) \Sigma'=\Sigma+\tau(E_{kl}+E_{lk}) Σ ′ = Σ + τ ( E k l + E l k ) . For every statement s = ( i j ∣ C ) s=(ij\mid C) s = ( ij ∣ C ) ,
a s ( Σ ′ ) = a s ( Σ ) + τ L s ( Σ ) − τ 2 Q s ( Σ ) , (4) a_s(\Sigma')=a_s(\Sigma)+\tau L_s(\Sigma)-\tau^2Q_s(\Sigma), \tag*{(4)} a s ( Σ ′ ) = a s ( Σ ) + τ L s ( Σ ) − τ 2 Q s ( Σ ) , (4) where L s = Q s = 0 L_s=Q_s=0 L s = Q s = 0 if k k k and l l l do not both occur in s s s . Otherwise let D = C ∖ { k , l } D=C\setminus\{k,l\} D = C ∖ { k , l } . Up to exchanging k k k with l l l or i i i with j j j , there are three cases.
(a) If { i , j } = { k , l } \{i,j\}=\{k,l\} { i , j } = { k , l } then L s = det Σ C L_s=\det\Sigma_C L s = det Σ C and Q s = 0 Q_s=0 Q s = 0 .
(b) If i = k i=k i = k and l ∈ C l\in C l ∈ C then L s = − a l j ∣ D L_s=-a_{lj\mid D} L s = − a l j ∣ D and Q s = 0 Q_s=0 Q s = 0 .
(c) If k , l ∈ C k,l\in C k , l ∈ C then Q s = a i j ∣ D Q_s=a_{ij\mid D} Q s = a ij ∣ D and
L s = det Σ D ( σ i k ⋅ D σ j l ⋅ D + σ i l ⋅ D σ j k ⋅ D − 2 σ i j ⋅ D σ k l ⋅ D ) . (5) L_s=\det\Sigma_D\left(\sigma_{ik\cdot D}\sigma_{jl\cdot D}+\sigma_{il\cdot D}\sigma_{jk\cdot D}-2\sigma_{ij\cdot D}\sigma_{kl\cdot D}\right). \tag*{(5)} L s = det Σ D ( σ ik ⋅ D σ j l ⋅ D + σ i l ⋅ D σ j k ⋅ D − 2 σ ij ⋅ D σ k l ⋅ D ) . (5) Consequently, for generic τ \tau τ with Σ ′ ∈ P D n \Sigma'\in\mathrm{PD}_n Σ ′ ∈ PD n ,
⟦ Σ ′ ⟧ = { s ∈ ⟦ Σ ⟧ : L s ( Σ ) = Q s ( Σ ) = 0 } . (6) \llbracket\Sigma'\rrbracket=\{s\in\llbracket\Sigma\rrbracket:L_s(\Sigma)=Q_s(\Sigma)=0\}. \tag*{(6)} [ [ Σ ′ ] ] = { s ∈ [ [ Σ ] ] : L s ( Σ ) = Q s ( Σ ) = 0 } . (6)
We refer to the three cases as types (a), (b) and (c). A statement of type (a) concerns the two variables whose covariance is changed. It never survives, because det Σ C > 0 \det\Sigma_C>0 det Σ C > 0 . In type (b) one endpoint is k k k while l l l is a conditioning variable. The statement survives when ( l j ∣ D ) (lj\mid D) ( l j ∣ D ) holds too, that is, when Y j Y_j Y j is also independent of Y l Y_l Y l given the rest of Y C Y_C Y C . In type (c) both k k k and l l l are conditioning variables. The statement survives when it holds without them, so that σ i j ⋅ D = 0 \sigma_{ij\cdot D}=0 σ ij ⋅ D = 0 , and when the partial covariances satisfy
σ i k ⋅ D σ j l ⋅ D + σ i l ⋅ D σ j k ⋅ D = 0. (7) \sigma_{ik\cdot D}\sigma_{jl\cdot D}+\sigma_{il\cdot D}\sigma_{jk\cdot D}=0. \tag*{(7)} σ ik ⋅ D σ j l ⋅ D + σ i l ⋅ D σ j k ⋅ D = 0. (7)
Types (a) and (b) are thus decided by the structure of Σ \Sigma Σ , as for variances. Type (c) is decided by it only if (7) can hold just with a zero factor in each product. Otherwise the two products may cancel, and survival depends on the values in Σ \Sigma Σ . The next definition excludes this.
Definition 5. A set of statements J \mathcal{J} J is cancellation-free for a pair { k , l } \{k,l\} { k , l } with k ≠ l k\ne l k = l if, for all distinct i , j ∉ { k , l } i,j\notin\{k,l\} i , j ∈ / { k , l } and all D ⊆ [ n ] ∖ { i , j , k , l } D\subseteq[n]\setminus\{i,j,k,l\} D ⊆ [ n ] ∖ { i , j , k , l } with ( i j ∣ D ) ∈ J (ij\mid D)\in\mathcal{J} ( ij ∣ D ) ∈ J and ( i j ∣ D ∪ { k , l } ) ∈ J (ij\mid D\cup\{k,l\})\in\mathcal{J} ( ij ∣ D ∪ { k , l }) ∈ J , at least one of ( i k ∣ D ) (ik\mid D) ( ik ∣ D ) , ( i l ∣ D ) (il\mid D) ( i l ∣ D ) , ( j k ∣ D ) (jk\mid D) ( j k ∣ D ) , ( j l ∣ D ) (jl\mid D) ( j l ∣ D ) belongs to J \mathcal{J} J .
Section 4 shows that the structure of every ancestral graph is cancellation-free. The statements that survive the change are then of two kinds.
Definition 6. Let J \mathcal{J} J be a set of statements, k ≠ l k\ne l k = l and ( i j ∣ C ) ∈ J (ij\mid C)\in\mathcal{J} ( ij ∣ C ) ∈ J , with D = C ∖ { k , l } D=C\setminus\{k,l\} D = C ∖ { k , l } . The statement is untouched by { k , l } \{k,l\} { k , l } if k k k and l l l do not both occur in it. It is screened by an endpoint e ∈ { i , j } ∖ { k , l } e\in\{i,j\}\setminus\{k,l\} e ∈ { i , j } ∖ { k , l } if ( e a ∣ D ) ∈ J (ea\mid D)\in\mathcal{J} ( e a ∣ D ) ∈ J for every a ∈ { i , j , k , l } ∖ { e } a\in\{i,j,k,l\}\setminus\{e\} a ∈ { i , j , k , l } ∖ { e } . The set J k l \mathcal{J}^{kl} J k l consists of the statements of J \mathcal{J} J that are untouched by { k , l } \{k,l\} { k , l } or screened by some endpoint.
The submatrix of an untouched statement does not contain σ k l \sigma_{kl} σ k l . A screened statement says that Y e Y_e Y e is independent of the other variables of { i , j , k , l } \{i,j,k,l\} { i , j , k , l } given Y D Y_D Y D . This is decided by a submatrix that does not contain σ k l \sigma_{kl} σ k l either, so it survives the change, and it implies ( i j ∣ C ) (ij \mid C) ( ij ∣ C ) .
Proposition 7. Let Σ \Sigma Σ , k k k , l l l and Σ ′ \Sigma' Σ ′ be as in Proposition 4 , and let [ [ Σ ] ] k l [\![\Sigma]\!]^{kl} [ [ Σ ] ] k l be the set of untouched and screened statements of [ [ Σ ] ] [\![\Sigma]\!] [ [ Σ ] ] . Every statement of [ [ Σ ] ] k l [\![\Sigma]\!]^{kl} [ [ Σ ] ] k l holds for Σ ′ \Sigma' Σ ′ whenever Σ ′ ∈ P D n \Sigma' \in\mathrm{PD}_n Σ ′ ∈ PD n . If [ [ Σ ] ] [\![\Sigma]\!] [ [ Σ ] ] is cancellation-free for { k , l } \{k,l\} { k , l } , then [ [ Σ ′ ] ] = [ [ Σ ] ] k l [\![\Sigma']\!] = [\![\Sigma]\!]^{kl} [ [ Σ ′ ] ] = [ [ Σ ] ] k l for generic τ \tau τ with Σ ′ ∈ P D n \Sigma' \in\mathrm{PD}_n Σ ′ ∈ PD n .
Example 8. In Example 1 add τ \tau τ to σ 12 \sigma_{12} σ 12 . The statement ( 23 ∣ 4 ) (23 \mid4) ( 23 ∣ 4 ) does not involve both Y 1 Y_1 Y 1 and Y 2 Y_2 Y 2 , so it is untouched. The statements ( 12 ∣ 4 ) (12 \mid4) ( 12 ∣ 4 ) and ( 12 ∣ 34 ) (12 \mid34) ( 12 ∣ 34 ) are of type (a), with
a 12 ∣ 4 ( Σ ′ ) = τ σ 44 = τ , a 12 ∣ 34 ( Σ ′ ) = τ det Σ 34 = 3 τ . a_{12\mid4}(\Sigma') = \tau\sigma_{44} = \tau,\qquad a_{12\mid34}(\Sigma') = \tau\det\Sigma_{34} = 3\tau. a 12 ∣ 4 ( Σ ′ ) = τ σ 44 = τ , a 12 ∣ 34 ( Σ ′ ) = τ det Σ 34 = 3 τ . The statement ( 23 ∣ 14 ) (23 \mid14) ( 23 ∣ 14 ) is of type (b) with k = 2 k=2 k = 2 and l = 1 l=1 l = 1 . Here a 23 ∣ 14 ( Σ ′ ) = − τ a 13 ∣ 4 ( Σ ) = − 2 τ a_{23\mid14}(\Sigma') = -\tau a_{13\mid4}(\Sigma) = -2\tau a 23 ∣ 14 ( Σ ′ ) = − τ a 13 ∣ 4 ( Σ ) = − 2 τ . Hence [ [ Σ ′ ] ] = { ( 23 ∣ 4 ) } [\![\Sigma']\!] = \{(23 \mid4)\} [ [ Σ ′ ] ] = {( 23 ∣ 4 )} for generic admissible τ \tau τ .
Example 9. In Example 2 add τ \tau τ to σ 23 \sigma_{23} σ 23 . The statements ( 14 ∣ 2 ) (14 \mid2) ( 14 ∣ 2 ) and ( 14 ∣ 3 ) (14 \mid3) ( 14 ∣ 3 ) are untouched, because each of them leaves out Y 2 Y_2 Y 2 or Y 3 Y_3 Y 3 . Four of the other five are of type (b) and are lost. For instance a 13 ∣ 2 ( Σ ′ ) = − τ σ 12 = − 4 τ a_{13\mid2}(\Sigma') = -\tau\sigma_{12} = -4\tau a 13 ∣ 2 ( Σ ′ ) = − τ σ 12 = − 4 τ . The statement ( 14 ∣ 23 ) (14 \mid23) ( 14 ∣ 23 ) is of type (c) with D = ∅ D = \varnothing D = ∅ . By (5) ,
a 14 ∣ 23 ( Σ ′ ) = τ ( σ 12 σ 43 + σ 13 σ 42 − 2 σ 14 σ 23 ) − τ 2 σ 14 = 12 τ − τ 2 . a_{14\mid23}(\Sigma') = \tau\left(\sigma_{12}\sigma_{43}+\sigma_{13}\sigma_{42}-2\sigma_{14}\sigma_{23}\right)-\tau^2\sigma_{14}=12\tau-\tau^2. a 14 ∣ 23 ( Σ ′ ) = τ ( σ 12 σ 43 + σ 13 σ 42 − 2 σ 14 σ 23 ) − τ 2 σ 14 = 12 τ − τ 2 . The admissible sizes are those in the interval ( − 8 , 24 / 7 ) (-8,24/7) ( − 8 , 24/7 ) , so the root τ = 12 \tau=12 τ = 12 is excluded and the statement is lost. Hence [ [ Σ ′ ] ] = { ( 14 ∣ 2 ) , ( 14 ∣ 3 ) } [\![\Sigma']\!] = \{(14 \mid2),(14 \mid3)\} [ [ Σ ′ ] ] = {( 14 ∣ 2 ) , ( 14 ∣ 3 )} for generic admissible τ \tau τ . Conditioning on either interior variable makes the two ends independent, while conditioning on both of them does not.
Several covariances can be changed one at a time, since Propositions 4 and 7 hold for every positive definite matrix. If [ [ Σ ] ] [\![\Sigma]\!] [ [ Σ ] ] and each set produced along the way are cancellation-free for the next pair, applying the rule once for each pair gives the final structure for generic sizes.
Graphical models
This section reads the results of Section 3 on a graph to which Σ \Sigma Σ is Markov or faithful.
Undirected graphs
For variances the perturbed matrix is again faithful to an undirected graph, obtained by adding edges. For K ⊆ [ n ] K \subseteq[n] K ⊆ [ n ] let G K G^K G K be the graph on [ n ] [n] [ n ] in which two vertices are adjacent whenever they are joined in G G G by a path whose interior vertices all lie in K K K . It contains G G G . For a single vertex k k k it is obtained by joining every pair of neighbours of k k k , which is the step performed when k k k is eliminated, except that k k k is kept. In general G K G^K G K is the elimination graph of the vertices of K K K , again with these vertices kept, and it does not depend on the order of elimination.
Theorem 8. Let G G G be an undirected graph, K ⊆ [ n ] K \subseteq[n] K ⊆ [ n ] and Σ ′ = Σ + ∑ k ∈ K τ k E k k ∈ P D n \Sigma'=\Sigma+\sum_{k\in K}\tau_k E_{kk}\in\mathrm{PD}_n Σ ′ = Σ + ∑ k ∈ K τ k E k k ∈ PD n . If Σ \Sigma Σ is Markov to G G G then Σ ′ \Sigma' Σ ′ is Markov to G K G^K G K , while if Σ \Sigma Σ is faithful to G G G then Σ ′ \Sigma' Σ ′ is faithful to G K G^K G K for generic τ \tau τ .
Example 10. In Example 1 vertex 4 is adjacent to all the others. The graph G { 4 } G^{\{4\}} G { 4 } is complete and no statement survives a change of σ 44 \sigma_{44} σ 44 , as found in Example 6. The neighbours of vertex 1 are adjacent, so G { 1 } = G G^{\{1\}}=G G { 1 } = G and a change of σ 11 \sigma_{11} σ 11 has no effect. In Example 2 a change of σ 22 \sigma_{22} σ 22 joins the vertices 1 and 3 (Figure 2 ). In the new graph vertex 3 still separates 4 from 1 and from 2, which gives the four statements of Example 7 without any computation.
Figure 2. Graphs after a change of one variance, (a) G { 4 } G^{\{4\}} G { 4 } for Example 1 and (b) G { 2 } G^{\{2\}} G { 2 } for Example 2.
For one covariance the perturbed structure is described by separation in G G G itself. Given k ≠ l k \ne l k = l , the set I ( G ) k l \mathcal{I}(G)^{kl} I ( G ) k l of Definition 6 consists of the untouched statements of I ( G ) \mathcal{I}(G) I ( G ) and of the screened ones, in which D = C ∖ { k , l } D = C \setminus\{k,l\} D = C ∖ { k , l } separates an endpoint e ∉ { k , l } e \notin\{k,l\} e ∈ / { k , l } from the other vertices of { i , j , k , l } \{i,j,k,l\} { i , j , k , l } . Let I 0 \mathcal{I}_0 I 0 be the set of untouched statements of I ( G ) \mathcal{I}(G) I ( G ) , and let G k l G^{kl} G k l be obtained from G G G by joining every pair of vertices of N [ k ] ∪ N [ l ] N[k] \cup N[l] N [ k ] ∪ N [ l ] , so that this set becomes a clique. Here G k l = G { k , l } G^{kl} = G^{\{k,l\}} G k l = G { k , l } exactly when k k k and l l l are adjacent.
Theorem 9. Let G G G be an undirected graph, k ≠ l k \ne l k = l and Σ ′ = Σ + τ ( E k l + E l k ) ∈ P D n \Sigma' = \Sigma+\tau(E_{kl}+E_{lk}) \in\mathrm{PD}_n Σ ′ = Σ + τ ( E k l + E l k ) ∈ PD n . If Σ \Sigma Σ is Markov to G G G then I ( G ) k l ⊆ [ [ Σ ′ ] ] \mathcal{I}(G)^{kl} \subseteq[\![\Sigma']\!] I ( G ) k l ⊆ [ [ Σ ′ ] ] . If Σ \Sigma Σ is faithful to G G G , the following two properties hold for generic τ \tau τ .
(a) [ [ Σ ′ ] ] = I ( G ) k l [\![\Sigma']\!] = \mathcal{I}(G)^{kl} [ [ Σ ′ ] ] = I ( G ) k l .
(b) The graph of the non-zero off-diagonal entries of ( Σ ′ ) − 1 (\Sigma')^{-1} ( Σ ′ ) − 1 is G k l G^{kl} G k l .
Moreover, I ( G ) k l \mathcal{I}(G)^{kl} I ( G ) k l is the smallest of the structures [ [ Σ ] ] [\![\Sigma]\!] [ [ Σ ] ] with Σ ∈ P D n \Sigma\in\mathrm{PD}_n Σ ∈ PD n that contain I 0 \mathcal{I}_0 I 0 .
Unlike a change of variances, a change of one covariance can lead to a structure that no undirected graph displays (Example 11). Theorem 9 therefore describes it as a set of statements. The statements of I 0 \mathcal{I}_0 I 0 are untouched by the perturbation. They concern the vectors ( Y a ) a ≠ k (Y_a)_{a\ne k} ( Y a ) a = k and ( Y a ) a ≠ l (Y_a)_{a\ne l} ( Y a ) a = l , whose covariance matrices do not contain σ k l \sigma_{kl} σ k l . The last part of the theorem says that nothing survives beyond what these two margins force. By part (b) the graph of the inverse gains all the edges among k k k , l l l and their neighbours. The statements displayed by G k l G^{kl} G k l hold for Σ ′ \Sigma' Σ ′ , but I ( G ) k l \mathcal{I}(G)^{kl} I ( G ) k l can be strictly larger than I ( G k l ) \mathcal{I}(G^{kl}) I ( G k l ) .
Example 11. In Example 1 take k = 1 k=1 k = 1 and l = 2 l=2 l = 2 . The statement ( 23 ∣ 4 ) (23 \mid4) ( 23 ∣ 4 ) is untouched. The statements ( 12 ∣ 4 ) (12 \mid4) ( 12 ∣ 4 ) and ( 12 ∣ 34 ) (12 \mid34) ( 12 ∣ 34 ) have no endpoint outside { 1 , 2 } \{1,2\} { 1 , 2 } . The statement ( 23 ∣ 14 ) (23 \mid14) ( 23 ∣ 14 ) is not screened, because the endpoint 3 is adjacent to 1. Hence I ( G ) 12 = { ( 23 ∣ 4 ) } \mathcal{I}(G)^{12}=\{(23 \mid4)\} I ( G ) 12 = {( 23 ∣ 4 )} , as in Example 8. Since N [ 1 ] ∪ N [ 2 ] N[1]\cup N[2] N [ 1 ] ∪ N [ 2 ] contains all vertices, G 12 G^{12} G 12 is complete. No undirected graph displays the structure { ( 23 ∣ 4 ) } \{(23 \mid4)\} {( 23 ∣ 4 )} , because in such a graph separation by { 4 } \{4\} { 4 } always implies separation by { 1 , 4 } \{1,4\} { 1 , 4 } .
In Example 2 take k = 2 k=2 k = 2 and l = 3 l=3 l = 3 . Then I 0 = { ( 14 ∣ 2 ) , ( 14 ∣ 3 ) } \mathcal{I}_0=\{(14 \mid2),(14 \mid3)\} I 0 = {( 14 ∣ 2 ) , ( 14 ∣ 3 )} . None of the other five statements is screened, since vertex 1 is adjacent to 2 and vertex 4 to 3. Hence I ( G ) 23 = I 0 \mathcal{I}(G)^{23}=\mathcal{I}_0 I ( G ) 23 = I 0 , as in Example 9, while G 23 G^{23} G 23 is complete. The two statements come from the margins ( Y 1 , Y 3 , Y 4 ) (Y_1,Y_3,Y_4) ( Y 1 , Y 3 , Y 4 ) and ( Y 1 , Y 2 , Y 4 ) (Y_1,Y_2,Y_4) ( Y 1 , Y 2 , Y 4 ) .
The next corollary uses Theorems 8 and 9 to identify the parameters that can be changed with no covariation. Recall that a vertex is simplicial if its neighbours are pairwise adjacent.
Corollary 10. Let Σ \Sigma Σ be faithful to an undirected graph G G G and let τ \tau τ be a generic admissible size. The matrix Σ + τ E k k \Sigma+\tau E_{kk} Σ + τ E k k is faithful to G G G if and only if k k k is simplicial. The matrix Σ + τ ( E k l + E l k ) \Sigma+\tau(E_{kl}+E_{lk}) Σ + τ ( E k l + E l k ) is faithful to G G G if and only if k k k and l l l are adjacent simplicial vertices of G G G .
Example 12. In Example 1 the vertices 1, 2 and 3 are simplicial. Among them only 1 and 3 are adjacent. The parameters σ 11 , σ 22 , σ 33 \sigma_{11},\sigma_{22},\sigma_{33} σ 11 , σ 22 , σ 33 and σ 13 \sigma_{13} σ 13 can therefore be varied freely, whereas a change of any other parameter alters the structure. In Example 2 only the end vertices are simplicial and they are not adjacent. Only the variances σ 11 \sigma_{11} σ 11 and σ 44 \sigma_{44} σ 44 can be varied freely, while no covariance can.
Theorems 8 and 9 give the graph that a change produces, and Corollary 10 identifies the parameters whose change leaves the graph as it is. For decomposable graphs, the junction tree also identifies the multipliers that preserve the model. An undirected graph G G G is decomposable if its maximal cliques, the maximal sets of pairwise adjacent vertices, can be arranged as the nodes of a tree T T T in which the intersection of any two of them is contained in every maximal clique on the path between them. Such a tree is called a junction tree [11 ] . Removing an edge e = { C 1 , C 2 } e = \{C_1,C_2\} e = { C 1 , C 2 } of T T T splits it into two subtrees. Let S e = C 1 ∩ C 2 S_e = C_1 \cap C_2 S e = C 1 ∩ C 2 . Let A e A_e A e be the set of vertices outside S e S_e S e that lie in a maximal clique of the first subtree, and define B e B_e B e in the same way from the second subtree. Then S e S_e S e separates A e A_e A e from B e B_e B e in G G G , and it is non-empty when G G G is connected.
Theorem 11. Let G G G be a connected decomposable graph with junction tree T T T . A multiplier Δ \Delta Δ is model-preserving for M ( G ) \mathcal{M}(G) M ( G ) if and only if the block Δ A e ∪ S e , B e ∪ S e \Delta_{A_e\cup S_e,B_e\cup S_e} Δ A e ∪ S e , B e ∪ S e has rank one for every edge e e e of $T.
Sufficiency follows from Theorem 1, because M ( G ) \mathcal{M}(G) M ( G ) is the set of matrices that satisfy A e ⊥ ⊥ B e ∣ S e A_e \perp\!\!\!\perp B_e \mid S_e A e ⊥ ⊥ B e ∣ S e for every edge e e e . Necessity does not, since the model is smaller than each of these sets.
Example 13. The graph of Example 1 has the maximal cliques { 1 , 3 , 4 } \{1,3,4\} { 1 , 3 , 4 } and { 2 , 4 } \{2,4\} { 2 , 4 } . Its junction tree has a single edge, so Theorem 11 reduces to Example 5. For the path of Example 2 the maximal cliques are { 1 , 2 } \{1,2\} { 1 , 2 } , { 2 , 3 } \{2,3\} { 2 , 3 } and { 3 , 4 } \{3,4\} { 3 , 4 } . The two edges of the junction tree give the blocks Δ 12 , 234 \Delta_{12,234} Δ 12 , 234 and Δ 123 , 34 \Delta_{123,34} Δ 123 , 34 , which both have rank one exactly when
δ 13 δ 22 = δ 12 δ 23 , δ 14 δ 22 = δ 12 δ 24 , δ 24 δ 33 = δ 23 δ 34 . \delta_{13}\delta_{22}=\delta_{12}\delta_{23}, \qquad\delta_{14}\delta_{22}=\delta_{12}\delta_{24}, \qquad\delta_{24}\delta_{33}=\delta_{23}\delta_{34}. δ 13 δ 22 = δ 12 δ 23 , δ 14 δ 22 = δ 12 δ 24 , δ 24 δ 33 = δ 23 δ 34 .
These are binomial equations, and the same binomials in the entries of Σ \Sigma Σ define the model itself (§ 7 ). The entries of Δ \Delta Δ at the vertices and edges can be chosen freely and determine all the others. If σ 12 \sigma_{12} σ 12 is multiplied by δ \delta δ , the model is preserved by multiplying σ 13 \sigma_{13} σ 13 and σ 14 \sigma_{14} σ 14 by δ \delta δ as well. If σ 22 \sigma_{22} σ 22 is multiplied by δ \delta δ , it is preserved by dividing σ 13 \sigma_{13} σ 13 and σ 14 \sigma_{14} σ 14 by δ \delta δ .
For a disconnected G G G the theorem applies to each component, with arbitrary δ a b \delta_{ab} δ ab between components.
Ancestral graphs
We now consider ancestral graphs, which contain undirected and directed acyclic graphs as special cases. A mixed graph has at most one edge between two vertices, which is undirected (a − b a-b a − b ), directed (a → b a \to b a → b ) or bidirected (a ↔ b a \leftrightarrow b a ↔ b ). A vertex a a a is an ancestor of b b b if a = b a=b a = b or there is a directed path from a a a to b b b . The graph is ancestral if it has no directed cycle, if a ↔ b a \leftrightarrow b a ↔ b implies that neither vertex is an ancestor of the other, and if no arrowhead points at a vertex of an undirected edge.
An interior vertex of a path is a collider if both adjacent edges of the path have an arrowhead at it. A path is m-connecting given C C C if none of its non-colliders is in C C C and each of its colliders is an ancestor of a vertex of C C C . Two vertices are m-separated by C C C if no path between them is m-connecting given C C C . For an undirected graph this is separation, and for a directed acyclic graph it is d-separation. We write I ( G ) \mathcal{I}(G) I ( G ) for the set of statements ( i j ∣ C ) (ij \mid C) ( ij ∣ C ) such that C C C m-separates i i i from j j j . Markov and faithful matrices are then defined as in § 2.2 .
For τ k > 0 \tau_k > 0 τ k > 0 a change of the variance of Y k Y_k Y k replaces Y k Y_k Y k by a noisy copy. On the graph this adds a child of k k k and marginalizes over k k k itself. The marginal of an ancestral graph over a set V V V of its vertices is an ancestral graph on V V V with the same m-separation statements among V V V (Richardson and Spirtes, [17 ] ). A marginal of a directed acyclic graph need not be one, so ancestral graphs are the natural class here. For K ⊆ [ n ] K \subseteq[n] K ⊆ [ n ] let G + G^+ G + be obtained from G G G by adding a new vertex k ′ k' k ′ and the edge k → k ′ k \to k' k → k ′ for each k ∈ K k \in K k ∈ K . We write G ( K ) G^{(K)} G ( K ) for the marginal of G + G^+ G + over the vertices that are not in K K K , with each k ′ k' k ′ relabelled as k k k .
For one covariance the sets I ( G ) k l \mathcal{I}(G)^{kl} I ( G ) k l and I 0 \mathcal{I}_0 I 0 are defined as in § 5.1 , with m-separation in place of separation for screened statements. The graph of the inverse of a faithful matrix is the undirected graph G a G^a G a on [ n ] [n] [ n ] in which two vertices are adjacent when they are joined in G G G by a path on which every interior vertex is a collider [17 ] . It contains the edges of G G G and equals G G G when G G G is undirected. For a directed acyclic graph it is the moral graph, in which two vertices are adjacent when they are adjacent in G G G or have a common child.
Theorem 12. Let G G G be an ancestral graph.
(a) Let K ⊆ [ n ] K \subseteq[n] K ⊆ [ n ] and Σ ′ = Σ + ∑ k ∈ K τ k E k k ∈ P D n \Sigma' = \Sigma+ \sum_{k \in K} \tau_k E_{kk} \in\mathrm{PD}_n Σ ′ = Σ + ∑ k ∈ K τ k E k k ∈ PD n . If Σ \Sigma Σ is Markov to G G G then Σ ′ \Sigma' Σ ′ is Markov to G ⟨ K ⟩ G^{\langle K\rangle} G ⟨ K ⟩ , while if Σ \Sigma Σ is faithful to G G G then Σ ′ \Sigma' Σ ′ is faithful to G ⟨ K ⟩ G^{\langle K\rangle} G ⟨ K ⟩ for generic τ \tau τ .
(b) Let k ≠ l k \ne l k = l and Σ ′ = Σ + τ ( E k l + E l k ) ∈ P D n \Sigma' = \Sigma+ \tau(E_{kl} + E_{lk}) \in\mathrm{PD}_n Σ ′ = Σ + τ ( E k l + E l k ) ∈ PD n . The conclusions of Theorem 9 hold, with ( G a ) k l (G^a)^{kl} ( G a ) k l in place of G k l G^{kl} G k l for the graph of the inverse.
By part (a) each perturbed variable becomes latent and is observed only through a noisy copy, whether its variance increases or decreases. For an undirected graph G ⟨ K ⟩ G^{\langle K\rangle} G ⟨ K ⟩ has the same separation statements as G K G^K G K . For a directed acyclic graph it is in general a mixed graph, because the children of a perturbed vertex k k k and its copy k ′ k' k ′ share the marginalized parent k k k . Its statements need not be those of any directed acyclic graph. For the graph 1 → 4 ← 3 → 5 ← 2 1 \to4 \leftarrow3 \to5 \leftarrow2 1 → 4 ← 3 → 5 ← 2 , a change of σ 33 \sigma_{33} σ 33 gives the edges 1 → 4 1 \to4 1 → 4 , 2 → 5 2 \to5 2 → 5 , 3 ↔ 4 3 \leftrightarrow4 3 ↔ 4 , 3 ↔ 5 3 \leftrightarrow5 3 ↔ 5 and 4 ↔ 5 4 \leftrightarrow5 4 ↔ 5 . A directed acyclic graph with these statements would have the same adjacencies, and ( 15 ∣ ∅ ) (15 \mid\varnothing) ( 15 ∣ ∅ ) and ( 24 ∣ ∅ ) (24 \mid\varnothing) ( 24 ∣ ∅ ) would force its edge between 4 and 5 to point both ways.
In part (b), the neighbours of a vertex of a directed acyclic graph in G a G^a G a are its parents, its children and the other parents of its children. The graph of the inverse gains every edge among k k k , l l l and these vertices. As for undirected graphs, the resulting structure need not be that of an ancestral graph.
Example 14. The matrix of Example 2 is also faithful to the directed path 1 → 2 → 3 → 4 1 \to2 \to3 \to4 1 → 2 → 3 → 4 , which has the same separation statements as the undirected path. For a change of σ 22 \sigma_{22} σ 22 the graph G + G^+ G + has the additional edge 2 → 2 ′ 2 \to2' 2 → 2 ′ . Its marginal over { 1 , 2 ′ , 3 , 4 } \{1,2',3,4\} { 1 , 2 ′ , 3 , 4 } has the edges 1 → 2 ′ 1 \to2' 1 → 2 ′ , 1 → 3 1 \to3 1 → 3 , 2 ′ ↔ 3 2' \leftrightarrow3 2 ′ ↔ 3 and 3 → 4 3 \to4 3 → 4 (Figure 3 ). Relabelling 2 ′ 2' 2 ′ as 2 gives G ⟨ { 2 } ⟩ G^{\langle\{2\}\rangle} G ⟨{ 2 }⟩ . The bidirected edge records that 2 ′ 2' 2 ′ and 3 are both children of the marginalized vertex 2. The m-separation statements of this graph are the four statements of Example 7. Adding the edge 1 → 3 1 \to3 1 → 3 to the path gives a directed acyclic graph with the same statements.
Figure 3. A change of σ 22 \sigma_{22} σ 22 in the directed path of Example 14, with (a) the graph G + G^+ G + and (b) its marginal over { 1 , 2 ′ , 3 , 4 } \{1,2',3,4\} { 1 , 2 ′ , 3 , 4 } .
For a change of σ 23 \sigma_{23} σ 23 the structure is { ( 14 ∣ 2 ) , ( 14 ∣ 3 ) } \{(14 \mid2),(14 \mid3)\} {( 14 ∣ 2 ) , ( 14 ∣ 3 )} by Example 9. No ancestral graph H H H has exactly these two statements. Indeed, we may assume that H H H is maximal, so that two vertices are adjacent unless some set m-separates them [17 ] . All pairs are then adjacent in H H H except { 1 , 4 } \{1,4\} { 1 , 4 } . If 2 is a collider on the path through 1, 2 and 4, this path is m-connecting given { 2 } \{2\} { 2 } . Otherwise it is m-connecting given { 3 } \{3\} { 3 } . Each case contradicts one of the two statements.
The parameters of a directed acyclic graph that can be changed with no covariation are found as in Corollary 10, with moral graphs in the role of the undirected graph. Write p a ( k ) pa(k) p a ( k ) for the set of parents of a vertex k k k and c h ( k ) ch(k) c h ( k ) for the set of its children. A set A A A of vertices is ancestral if it contains the parents of each of its vertices. Its moral graph has vertex set A A A , with two vertices adjacent when they are adjacent in G G G or have a common child in A A A .
Corollary 13. Let Σ \Sigma Σ be faithful to a directed acyclic graph G G G and let τ \tau τ be a generic admissible size.
(a) The matrix Σ + τ E k k \Sigma+\tau E_{kk} Σ + τ E k k is faithful to G G G if and only if k k k is simplicial in the moral graph of every ancestral set that contains k k k . This holds exactly when the vertices of ch ( k ) ∪ { k } \operatorname{ch}(k)\cup\{k\} ch ( k ) ∪ { k } are pairwise adjacent and pa ( a ) ⊆ pa ( b ) \operatorname{pa}(a)\subseteq\operatorname{pa}(b) pa ( a ) ⊆ pa ( b ) for every edge a → b a\to b a → b between two of them.
(b) The matrix Σ + τ ( E k l + E l k ) \Sigma+\tau(E_{kl}+E_{lk}) Σ + τ ( E k l + E l k ) is faithful to G G G if and only if k k k is adjacent to l l l and both are simplicial in the moral graph of every ancestral set that contains them.
A vertex without children satisfies the condition in (a), since its neighbours in a moral graph are its parents, which the moralization joins. A vertex with a single child c c c satisfies it exactly when its parents are also parents of c c c . An ancestral set that contains k k k and l l l is among those considered in (a) for each of the two vertices. Part (b) therefore holds when two adjacent vertices both satisfy the condition in (a). The converse fails, unlike for undirected graphs. In the graph with the edges 1 → 2 1\to2 1 → 2 , 2 → 3 2\to3 2 → 3 , 2 → 4 2\to4 2 → 4 , 1 → 4 1\to4 1 → 4 and 3 → 4 3\to4 3 → 4 the only statement is ( 13 ∣ 2 ) (13\mid2) ( 13 ∣ 2 ) , so σ 24 \sigma_{24} σ 24 is free although σ 22 \sigma_{22} σ 22 is not. The direction of the edges matters, as the next example shows.
Example 15. Reverse the last edge of the directed path of Example 14. The graph 1 → 2 → 3 ← 4 1\to2\to3\leftarrow4 1 → 2 → 3 ← 4 has a collider at 3 3 3 , and the matrix
Σ = ( 1 1 1 0 1 2 2 0 1 2 4 1 0 0 1 1 ) \Sigma=
\begin{pmatrix}
1&1&1&0\\
1&2&2&0\\
1&2&4&1\\
0&0&1&1
\end{pmatrix} Σ = 1 1 1 0 1 2 2 0 1 2 4 1 0 0 1 1 is faithful to it. It is the covariance matrix of Y 1 = ε 1 Y_1=\varepsilon_1 Y 1 = ε 1 , Y 2 = Y 1 + ε 2 Y_2=Y_1+\varepsilon_2 Y 2 = Y 1 + ε 2 , Y 3 = Y 2 + Y 4 + ε 3 Y_3=Y_2+Y_4+\varepsilon_3 Y 3 = Y 2 + Y 4 + ε 3 and Y 4 = ε 4 Y_4=\varepsilon_4 Y 4 = ε 4 with independent standard normal errors. Its structure is
[ [ Σ ] ] = { ( 13 ∣ 2 ) , ( 13 ∣ 24 ) , ( 14 ∣ ∅ ) , ( 14 ∣ 2 ) , ( 14 ∣ 23 ) , ( 24 ∣ ∅ ) , ( 24 ∣ 1 ) } . [\![\Sigma]\!]=\{(13\mid2),(13\mid24),(14\mid\varnothing),(14\mid2),(14\mid23),(24\mid\varnothing),(24\mid1)\}. [ [ Σ ] ] = {( 13 ∣ 2 ) , ( 13 ∣ 24 ) , ( 14 ∣ ∅ ) , ( 14 ∣ 2 ) , ( 14 ∣ 23 ) , ( 24 ∣ ∅ ) , ( 24 ∣ 1 )} . The vertices 1 1 1 and 4 4 4 have a single child but no parents, while 3 3 3 has no children. By Corollary 13 the parameters σ 11 \sigma_{11} σ 11 , σ 33 \sigma_{33} σ 33 , σ 44 \sigma_{44} σ 44 and σ 34 \sigma_{34} σ 34 are free. For the path of Example 2 only σ 11 \sigma_{11} σ 11 and σ 44 \sigma_{44} σ 44 are free (Example 12). The variance σ 22 \sigma_{22} σ 22 is not free, because the parent 1 1 1 of vertex 2 2 2 is not a parent of its child 3 3 3 . Adding τ \tau τ to it gives a 13 ∣ 2 ( Σ ′ ) = τ σ 13 = τ a_{13\mid2}(\Sigma')=\tau\sigma_{13}=\tau a 13 ∣ 2 ( Σ ′ ) = τ σ 13 = τ . The statements ( 13 ∣ 24 ) (13\mid24) ( 13 ∣ 24 ) and ( 14 ∣ 23 ) (14\mid23) ( 14 ∣ 23 ) are lost in the same way. The four statements that remain say that Y 4 Y_4 Y 4 is independent of ( Y 1 , Y 2 ) (Y_1,Y_2) ( Y 1 , Y 2 ) . They are the m-separation statements of the graph G ⟨ { 2 } ⟩ G^{\langle\{2\}\rangle} G ⟨{ 2 }⟩ of Theorem 12 (a), which has the edges 1 → 2 1\to2 1 → 2 , 1 → 3 1\to3 1 → 3 , 2 ↔ 3 2\leftrightarrow3 2 ↔ 3 and 4 → 3 4\to3 4 → 3 . A change of σ 23 \sigma_{23} σ 23 leaves the same four statements. The moral graph has the edges 1 − 2 1-2 1 − 2 , 2 − 3 2-3 2 − 3 , 2 − 4 2-4 2 − 4 and 3 − 4 3-4 3 − 4 . Every vertex is thus a neighbour of 2 2 2 or of 3 3 3 , so the graph of the inverse becomes complete.
Several covariances
Theorems Theorems 8 and 12 (a) change several variances at once, but Theorems 9 and 12 (b) change a single covariance. This section treats several covariances changed together. For an ancestral graph the structure stays cancellation-free after each change, so the outcome can again be read from the graph. Let P P P be a set of pairs of distinct vertices, the positions of the changed covariances, and let V ( P ) V(P) V ( P ) be the set of vertices of these pairs. For a statement s = ( i j ∣ C ) s=(ij\mid C) s = ( ij ∣ C ) let P s P_s P s consist of the pairs of P P P whose vertices both occur in s s s , either as endpoints or in C C C .
The rule is read in an undirected graph G s G_s G s attached to each statement s s s of an ancestral graph G G G . A vertex is anterior to s s s if it occurs in s s s or is the first vertex of a path that ends at a vertex of s s s and whose edges are undirected or directed towards that end. The vertices of G s G_s G s are those anterior to s s s . Two of them are adjacent in G s G_s G s if they are joined in G G G by a path through such vertices on which every interior vertex is a collider. In particular, vertices adjacent in G G G are adjacent in G s G_s G s . A set C C C m-separates i i i from j j j in G G G if and only if it separates them in G s G_s G s [17 ] .
If G G G is undirected, G s G_s G s consists of the connected components of G G G that meet s s s . If G G G is a directed acyclic graph, G s G_s G s is the moral graph of the smallest ancestral set containing s s s [11 ] .
Let I ( G ) P \mathcal{I}(G)^P I ( G ) P be the set of statements s = ( i j ∣ C ) s=(ij\mid C) s = ( ij ∣ C ) such that C ∖ V ( P s ) C\setminus V(P_s) C ∖ V ( P s ) separates i i i from j j j in G s + P s G_s+P_s G s + P s , the graph obtained from G s G_s G s by adding the pairs of P s P_s P s as edges. When all vertices occur in s s s , the graph G s G_s G s is the graph G a G^a G a of § 5.2 .
Theorem 14. Let G G G be an ancestral graph, P P P a set of pairs and
Σ ′ = Σ + ∑ { k , l } ∈ P τ k l ( E k l + E l k ) ∈ P D n . \Sigma'=\Sigma+\sum_{\{k,l\}\in P}\tau_{kl}(E_{kl}+E_{lk})\in\mathrm{PD}_n. Σ ′ = Σ + { k , l } ∈ P ∑ τ k l ( E k l + E l k ) ∈ PD n . If Σ \Sigma Σ is Markov to G G G then I ( G ) P ⊆ ⟦ Σ ′ ⟧ \mathcal{I}(G)^P\subseteq\llbracket\Sigma'\rrbracket I ( G ) P ⊆ [ [ Σ ′ ] ] . If Σ \Sigma Σ is faithful to G G G , the following hold for generic τ \tau τ .
(a) ⟦ Σ ′ ⟧ = I ( G ) P \llbracket\Sigma'\rrbracket=\mathcal{I}(G)^P [ [ Σ ′ ] ] = I ( G ) P .
(b) The graph of the non-zero off-diagonal entries of ( Σ ′ ) − 1 (\Sigma')^{-1} ( Σ ′ ) − 1 is ( G a + P ) V ( P ) (G^a+P)^{V(P)} ( G a + P ) V ( P ) .
A changed covariance that lies inside a statement acts as an additional edge, and its two vertices can no longer be used to separate. A pair of P P P with a vertex outside the statement plays no role, because the corresponding minor does not contain the changed entry. For a single pair the theorem reduces to the rules of Theorems 9 and 12(b) for one covariance. The first claim holds for all sizes because a statement of I ( G ) P \mathcal{I}(G)^P I ( G ) P follows from the rank of a submatrix of Σ \Sigma Σ without changed entries.
For an undirected graph the rule can be read in G G G itself. A statement survives when C ∖ V ( P s ) C\setminus V(P_s) C ∖ V ( P s ) separates i i i from j j j in G + P s G+P_s G + P s . For a directed acyclic graph the pairs of P s P_s P s are added to a moral graph, which depends on the statement through the ancestors of its vertices.
The theorem describes how perturbations compose. The covariances of P P P can be changed one at a time in any order, with the same final structure. This structure is contained in the intersection of those obtained from each change alone, and it can be strictly smaller. Changes that preserve the structure can be combined, so free parameters can be changed together and the matrix stays faithful to G G G for generic sizes. Other variances can be included as well, since a change of variances leaves the matrix faithful to an ancestral graph, to which the theorem applies.
Example 16. In Example 2 let P = { { 1 , 2 } , { 3 , 4 } } P=\{\{1,2\},\{3,4\}\} P = {{ 1 , 2 } , { 3 , 4 }} . By Theorem 9 a change of σ 12 \sigma_{12} σ 12 alone leaves the statements ( 14 ∣ 3 ) (14\mid3) ( 14 ∣ 3 ) , ( 14 ∣ 23 ) (14\mid23) ( 14 ∣ 23 ) , ( 24 ∣ 3 ) (24\mid3) ( 24 ∣ 3 ) and ( 24 ∣ 13 ) (24\mid13) ( 24 ∣ 13 ) . A change of σ 34 \sigma_{34} σ 34 alone leaves ( 13 ∣ 2 ) (13\mid2) ( 13 ∣ 2 ) , ( 13 ∣ 24 ) (13\mid24) ( 13 ∣ 24 ) , ( 14 ∣ 2 ) (14\mid2) ( 14 ∣ 2 ) and ( 14 ∣ 23 ) (14\mid23) ( 14 ∣ 23 ) . The statement ( 14 ∣ 23 ) (14\mid23) ( 14 ∣ 23 ) survives either change but not both. All four vertices occur in it, so P s = P P_s=P P s = P and the set C ∖ V ( P s ) C\setminus V(P_s) C ∖ V ( P s ) is empty, while G + P = G G+P=G G + P = G is connected. Each of the other six statements contains one of the two pairs, and for each of them C ∖ V ( P s ) C\setminus V(P_s) C ∖ V ( P s ) is empty as well. Hence ⟦ Σ ′ ⟧ = ∅ \llbracket\Sigma'\rrbracket=\varnothing [ [ Σ ′ ] ] = ∅ for generic sizes, and the graph of the inverse is complete. The directed path of Example 14 leads to the same conclusion, because its graphs G s G_s G s are paths as well. In Example 1 the parameters σ 11 \sigma_{11} σ 11 , σ 22 \sigma_{22} σ 22 , σ 33 \sigma_{33} σ 33 and σ 13 \sigma_{13} σ 13 are free by Example 12. Changing all four at once leaves ⟦ Σ ⟧ \llbracket\Sigma\rrbracket [ [ Σ ] ] unchanged.
Sensitivity of the examination marks model
The results are now applied to a covariance matrix estimated from data, whose parameters are known only up to sampling error. Their standard errors give a natural scale for the size of a change. Mardia et al. [14 ] report the marks of 88 students in five examinations. These are mechanics, vectors, algebra, analysis and statistics, numbered from 1 to 5 in this order. Whittaker [22 ] selected for these data the graph G G G of Figure 4 , in which algebra separates the first two examinations from the last two. Its model is the set of matrices that satisfy { 1 , 2 } ⊥ ⊥ { 4 , 5 } ∣ 3 \{1,2\}\perp\!\!\!\perp\{4,5\}\mid3 { 1 , 2 } ⊥ ⊥ { 4 , 5 } ∣ 3 . The maximum likelihood estimate Σ ^ \hat{\Sigma} Σ ^ in this model [11 ] , shown in Figure 4 , agrees with the sample covariance matrix on the cliques { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } and { 3 , 4 , 5 } \{3,4,5\} { 3 , 4 , 5 } . Its other entries are σ ^ a b = σ ^ a 3 σ ^ 3 b / σ ^ 33 \hat{\sigma}_{ab}=\hat{\sigma}_{a3}\hat{\sigma}_{3b}/\hat{\sigma}_{33} σ ^ ab = σ ^ a 3 σ ^ 3 b / σ ^ 33 . All off-diagonal entries of Σ ^ − 1 \hat{\Sigma}^{-1} Σ ^ − 1 are non-positive, so the matrix is faithful to G G G (Fallat et al., [6 ] ). Its structure consists of the sixteen statements ( a b ∣ C ) (ab \mid C) ( ab ∣ C ) in which a a a is 1 or 2, b b b is 4 or 5, and the conditioning set C C C contains the vertex 3.
Figure 4. The graph selected by Whittaker [22 ] for the marks of 88 students in five examinations, and the maximum likelihood estimate Σ ^ \hat{\Sigma} Σ ^ in its model, rounded to one decimal.
The model has eleven parameters, the five variances and the six covariances on the edges. Under normality the standard error of an estimated covariance is approximately ( ( σ i i σ j j + σ i j 2 ) / n ) 1 / 2 \left((\sigma_{ii}\sigma_{jj}+\sigma_{ij}^{2})/n\right)^{1/2} ( ( σ ii σ j j + σ ij 2 ) / n ) 1/2 with n = 88 n=88 n = 88 . This is 15 per cent of the estimate for each variance. For the covariances it ranges from 18 to 22 per cent. In relative terms the least precise parameter is the covariance of mechanics and algebra, estimated as σ ^ 13 = 100.4 \hat{\sigma}_{13}=100.4 σ ^ 13 = 100.4 with a standard error of 22.3. By Corollary 10 six parameters can be varied with no covariation. All vertices but 3 are simplicial. The adjacent pairs among them are { 1 , 2 } \{1,2\} { 1 , 2 } and { 4 , 5 } \{4,5\} { 4 , 5 } . The free parameters are thus σ 11 \sigma_{11} σ 11 , σ 22 \sigma_{22} σ 22 , σ 44 \sigma_{44} σ 44 , σ 55 \sigma_{55} σ 55 , σ 12 \sigma_{12} σ 12 and σ 45 \sigma_{45} σ 45 . By § 5.3 they can be changed together, and the sixteen statements remain when each of the six is moved by one standard error. The five parameters that involve algebra are not free.
Suppose that σ 13 \sigma_{13} σ 13 is increased by one standard error, τ = 22.3 \tau=22.3 τ = 22.3 . By Theorem 9 the perturbed matrix satisfies only the four statements ( 24 ∣ 3 ) (24 \mid3) ( 24 ∣ 3 ) , ( 24 ∣ 35 ) (24 \mid35) ( 24 ∣ 35 ) , ( 25 ∣ 3 ) (25 \mid3) ( 25 ∣ 3 ) and ( 25 ∣ 34 ) (25 \mid34) ( 25 ∣ 34 ) , in which mechanics does not occur. The graph of its inverse is complete. Proposition 4 (b) gives a 14 ∣ 3 ( Σ ′ ) = − τ σ ^ 34 a_{14\mid3}(\Sigma')=-\tau\hat{\sigma}_{34} a 14 ∣ 3 ( Σ ′ ) = − τ σ ^ 34 and a 15 ∣ 3 ( Σ ′ ) = − τ σ ^ 35 a_{15\mid3}(\Sigma')=-\tau\hat{\sigma}_{35} a 15 ∣ 3 ( Σ ′ ) = − τ σ ^ 35 . Given algebra, the partial correlation of mechanics becomes − 0.165 -0.165 − 0.165 with analysis and − 0.145 -0.145 − 0.145 with statistics. For comparison, the four sample partial correlations given algebra between the two groups of examinations are at most 0.093. In this respect the perturbed matrix is further from the model than the sample covariance matrix itself. The covariation of Theorem 1 that keeps the model multiplies σ 14 \sigma_{14} σ 14 and σ 15 \sigma_{15} σ 15 by the same factor as σ 13 \sigma_{13} σ 13 , here 1.22, which fills the first row of the block Δ 123 , 345 \Delta_{123,345} Δ 123 , 345 .
A change of σ 33 \sigma_{33} σ 33 affects every statement. The graph G { 3 } G^{\{3\}} G { 3 } is complete, so by Theorem 8 none of the sixteen statements survives. Identity (2) gives a a b ∣ 3 ( Σ ′ ) = τ σ ^ a b a_{ab\mid3}(\Sigma')=\tau\hat{\sigma}_{ab} a ab ∣ 3 ( Σ ′ ) = τ σ ^ ab for a ∈ { 1 , 2 } a\in\{1,2\} a ∈ { 1 , 2 } and b ∈ { 4 , 5 } b\in\{4,5\} b ∈ { 4 , 5 } . With an increase of one standard error, τ = 16.8 \tau=16.8 τ = 16.8 , the four partial correlations given algebra lie between 0.07 and 0.09. With a decrease of the same size they lie between − 0.16 -0.16 − 0.16 and − 0.12 -0.12 − 0.12 . A noisy algebra mark thus fails to separate the two groups. Theorem 14 covers joint changes. If the three parameters of mechanics, σ 11 \sigma_{11} σ 11 , σ 12 \sigma_{12} σ 12 and σ 13 \sigma_{13} σ 13 , are changed together, the structure is again that of 2 ⊥ ⊥ { 4 , 5 } ∣ 3 2 \perp\!\!\!\perp\{4,5\}\mid3 2 ⊥ ⊥ { 4 , 5 } ∣ 3 , since no changed position lies inside a statement that omits mechanics. A change of σ 13 \sigma_{13} σ 13 and σ 34 \sigma_{34} σ 34 leaves only ( 25 ∣ 3 ) (25\mid3) ( 25 ∣ 3 ) .
Discussion
A Schur multiplier preserves the vanishing of an almost-principal minor of a symmetric matrix for structural reasons only through a block of rank one, and the same blocks along a junction tree describe the multipliers that preserve a decomposable graphical model. Beyond these cases the almost-principal minors of a perturbed covariance matrix are explicit polynomials in the size of the perturbation, which determines its conditional independence structure. For graphical models a change of variances is an operation on the graph, whereas a change of covariances yields a structure that is read from the graph by a separation rule but need not be the structure of any graph. Covariation schemes were introduced to keep a perturbed covariance matrix inside a given model ([9 ] ). They fill a row, a column or the whole of the relevant block of the multiplier with the same factor. Theorem 1 shows that these are instances of one condition, a block of rank one, and that nothing else works for a single statement. Standard sensitivity analyses compare the original and the perturbed distribution through a divergence, which does not show whether the latter still belongs to the model. In general it does not, and our results give its conditional independence structure. In the examination marks, a change of one standard error in a single covariance induces partial correlations between the two groups that are larger in absolute value than those observed in the sample.
The results also connect with the algebraic description of Gaussian graphical models. By Theorem 11 the model-preserving multipliers of a decomposable graph are defined by binomial equations, the 2 × 2 2 \times2 2 × 2 minors of the blocks. When every separator is a single vertex, as for trees, the same binomials in the entries of Σ \Sigma Σ define the model, whose vanishing ideal is then toric ([16 ] ). For larger separators the model needs minors of higher order, and the relation between these equations and those of the multipliers remains an open question.
From the point of view of matrix theory, the results concern the pattern of vanishing principal and almost-principal minors of a symmetric matrix ([2 , 7 ] ) under the simplest perturbations. A change of a diagonal entry acts on the graph of the inverse by joining neighbours, as in one step of an elimination, while keeping the vertex. A change of an off-diagonal entry moves along the positive definite completions of a partial matrix ([15 ] ), and the relations that survive are those forced by the two principal submatrices that the completions share. For several such entries, a relation survives only when the rank of an unchanged submatrix forces it.
Three limitations remain. First, after a change of covariances the rules give the whole structure only for faithful matrices. A matrix that is only Markov to the graph keeps the statements given by the rules, but it may keep others too. Without a graph, the rule needs a cancellation-free structure, and otherwise the outcome depends on the partial covariances. Second, a model can impose equations that are not conditional independence statements. In Example 1 no statement survives a change of σ 44 \sigma_{44} σ 44 , yet the tetrad σ 21 σ 43 − σ 41 σ 23 = 0 \sigma_{21}\sigma_{43}-\sigma_{41}\sigma_{23}=0 σ 21 σ 43 − σ 41 σ 23 = 0 holds on the whole model and does not involve σ 44 \sigma_{44} σ 44 . The perturbed matrices thus form a smaller set than those satisfying the surviving statements, which we have not characterized. Third, model-preserving multipliers are characterized only for decomposable graphs. For other graphs, rank-one blocks for the defining statements are sufficient, but their necessity is open.
Funding
This work was funded by grant PID2023-153222OB-I00 of the Agencia Estatal de Investigación.
Statement on AI use
The author used the generative AI tool Claude (Anthropic) in preparing this article. The tool assisted in the formulation of the results, the development of the proofs, their verification and the polishing of their presentation. It also supported writing, exposition and proofreading. The author checked all the proofs and takes full responsibility for the content.
Proofs
Two properties of Gaussian vectors are used throughout. First, if A ⊥ ⊥ B ∣ D A \perp\!\perp B \mid D A ⊥ ⊥ B ∣ D holds for Σ \Sigma Σ , then ( a b ∣ D ∪ A ′ ∪ B ′ ) ∈ [ [ Σ ] ] (ab \mid D \cup A' \cup B') \in[[\Sigma]] ( ab ∣ D ∪ A ′ ∪ B ′ ) ∈ [[ Σ ]] for all a ∈ A a \in A a ∈ A , b ∈ B b \in B b ∈ B , A ′ ⊆ A ∖ { a } A' \subseteq A \setminus\{a\} A ′ ⊆ A ∖ { a } and B ′ ⊆ B ∖ { b } B' \subseteq B \setminus\{b\} B ′ ⊆ B ∖ { b } [4 ] . Second, for k ∉ D ∪ { i , j } k \notin D \cup\{i,j\} k ∈ / D ∪ { i , j } the partial covariances given D D D and D ∪ { k } D \cup\{k\} D ∪ { k } satisfy the recursion
σ i j ⋅ D k = σ i j ⋅ D − σ i k ⋅ D σ j k ⋅ D σ k k ⋅ D , (8) \sigma_{ij\cdot Dk} = \sigma_{ij\cdot D} - \frac{\sigma_{ik\cdot D}\,\sigma_{jk\cdot D}}{\sigma_{kk\cdot D}}, \tag*{(8)} σ ij ⋅ D k = σ ij ⋅ D − σ k k ⋅ D σ ik ⋅ D σ j k ⋅ D , (8)
where σ k k ⋅ D = det Σ D k / det Σ D > 0 \sigma_{kk\cdot D} = \det\Sigma_{Dk}/\det\Sigma_D > 0 σ k k ⋅ D = det Σ D k / det Σ D > 0 is the partial variance of Y k Y_k Y k given Y D Y_D Y D .
Proof of Theorem 1
Throughout, s = ( i j ∣ C ) s = (ij \mid C) s = ( ij ∣ C ) with C ≠ ∅ C \ne\varnothing C = ∅ . Expanding the minor along the row of i i i and the column of j j j isolates the entry σ i j \sigma_{ij} σ ij . The other entries of this row and column are u = ( σ i c ) c ∈ C u = (\sigma_{ic})_{c\in C} u = ( σ i c ) c ∈ C and v = ( σ c j ) c ∈ C v = (\sigma_{cj})_{c\in C} v = ( σ c j ) c ∈ C , so that
a s ( Σ ) = σ i j det Σ C − u T adj ( Σ C ) v , (9) a_s(\Sigma) = \sigma_{ij}\det\Sigma_C - u^{\mathsf T}\operatorname{adj}(\Sigma_C)v, \tag*{(9)} a s ( Σ ) = σ ij det Σ C − u T adj ( Σ C ) v , (9)
where adj \operatorname{adj} adj is the adjugate. The multiplier rescales u u u by D u = diag ( δ i c ) c ∈ C D_u = \operatorname{diag}(\delta_{ic})_{c\in C} D u = diag ( δ i c ) c ∈ C and v v v by D v = diag ( δ c j ) c ∈ C D_v = \operatorname{diag}(\delta_{cj})_{c\in C} D v = diag ( δ c j ) c ∈ C .
(a) If Δ i C , j C = a b T \Delta_{iC,jC} = ab^{\mathsf T} Δ i C , j C = a b T then ( Δ ∘ Σ ) i C , j C = diag ( a ) Σ i C , j C diag ( b ) (\Delta\circ\Sigma)_{iC,jC} = \operatorname{diag}(a)\Sigma_{iC,jC}\operatorname{diag}(b) ( Δ ∘ Σ ) i C , j C = diag ( a ) Σ i C , j C diag ( b ) . Hence a s ( Δ ∘ Σ ) a_s(\Delta\circ\Sigma) a s ( Δ ∘ Σ ) is a s ( Σ ) a_s(\Sigma) a s ( Σ ) times the product of the entries of a a a and b b b , which is not zero.
(b) Let M s M_s M s be the set of Σ ∈ P D n \Sigma\in\mathrm{PD}_n Σ ∈ PD n with a s ( Σ ) = 0 a_s(\Sigma) = 0 a s ( Σ ) = 0 . Since det Σ C > 0 \det\Sigma_C > 0 det Σ C > 0 , by (9) the entry σ i j \sigma_{ij} σ ij of a matrix in M s M_s M s is a rational function of its other entries. A relatively open subset of M s ∩ U Δ M_s \cap U_\Delta M s ∩ U Δ thus corresponds to an open set of values of these entries. The matrices of M s ∩ U Δ M_s \cap U_\Delta M s ∩ U Δ for which Δ ∘ Σ \Delta\circ\Sigma Δ ∘ Σ satisfies the statement are the zeros of a s ( Δ ∘ Σ ) a_s(\Delta\circ\Sigma) a s ( Δ ∘ Σ ) , which form a relatively closed set. Suppose that this set has an interior point. Expanding a s ( Δ ∘ Σ ) a_s(\Delta\circ\Sigma) a s ( Δ ∘ Σ ) as in (9) and substituting σ i j \sigma_{ij} σ ij gives
δ i j det ( Δ C ∘ Σ C ) u T adj ( Σ C ) v = det Σ C u T D u adj ( Δ C ∘ Σ C ) D v v \delta_{ij}\det(\Delta_C \circ\Sigma_C)u^{\mathsf T}\operatorname{adj}(\Sigma_C)v = \det\Sigma_C\,u^{\mathsf T}D_u\operatorname{adj}(\Delta_C \circ\Sigma_C)D_vv δ ij det ( Δ C ∘ Σ C ) u T adj ( Σ C ) v = det Σ C u T D u adj ( Δ C ∘ Σ C ) D v v
on an open set of values of u u u , v v v and Σ C \Sigma_C Σ C . Both sides are polynomials, so the equality holds everywhere. The matrices of the two bilinear forms in u u u and v v v therefore coincide. Put a symmetric matrix X X X with non-zero entries in place of Σ C \Sigma_C Σ C , such that X X X and Δ C ∘ X \Delta_C \circ X Δ C ∘ X are invertible. The relation adj ( M ) = det ( M ) M − 1 \operatorname{adj}(M) = \det(M)M^{-1} adj ( M ) = det ( M ) M − 1 then turns the equality of these matrices into δ i j X − 1 = D u ( Δ C ∘ X ) − 1 D v \delta_{ij}X^{-1} = D_u(\Delta_C \circ X)^{-1}D_v δ ij X − 1 = D u ( Δ C ∘ X ) − 1 D v . Inverting gives δ i j Δ C ∘ X = D v X D u \delta_{ij}\Delta_C \circ X = D_vXD_u δ ij Δ C ∘ X = D v X D u , whose entry in position ( c , d ) (c,d) ( c , d ) yields δ i j δ c d = δ c j δ i d \delta_{ij}\delta_{cd} = \delta_{cj}\delta_{id} δ ij δ c d = δ c j δ i d . Every entry of Δ i C , j C \Delta_{iC,jC} Δ i C , j C is thus the product of an entry in the column of j j j and one in the row of i i i , divided by δ i j \delta_{ij} δ ij . The block has rank one, contrary to the assumption. The set therefore has empty interior, so its complement is a dense open subset of the matrices of U Δ U_\Delta U Δ that satisfy the statement.
For the last claim, recall that A ⊥ ⊥ B ∣ C A \perp\!\perp B \mid C A ⊥ ⊥ B ∣ C holds for Σ \Sigma Σ if and only if ( i j ∣ C ) (ij \mid C) ( ij ∣ C ) does for all i ∈ A i \in A i ∈ A and j ∈ B j \in B j ∈ B . If the block Δ A ∪ C , B ∪ C \Delta_{A\cup C,B\cup C} Δ A ∪ C , B ∪ C has rank one, so has each Δ i C , j C \Delta_{iC,jC} Δ i C , j C , and part (a) applies. Conversely, if every Δ i C , j C \Delta_{iC,jC} Δ i C , j C has rank one, each entry of the block equals δ x c 0 δ c 0 y / δ c 0 c 0 \delta_{xc_0}\delta_{c_0y}/\delta_{c_0c_0} δ x c 0 δ c 0 y / δ c 0 c 0 for a fixed c 0 ∈ C c_0 \in C c 0 ∈ C , so the block has rank one. A block of larger rank thus contains some Δ i C , j C \Delta_{iC,jC} Δ i C , j C of rank larger than one. Consider the matrices Σ \Sigma Σ in which the variables outside { i , j } ∪ C \{i,j\}\cup C { i , j } ∪ C are independent of each other and of the remaining ones. Such a matrix satisfies A ⊥ ⊥ B ∣ C A \perp\!\perp B \mid C A ⊥ ⊥ B ∣ C as soon as it satisfies ( i j ∣ C ) (ij \mid C) ( ij ∣ C ) . By part (b), applied to the principal submatrix indexed by { i , j } ∪ C \{i,j\}\cup C { i , j } ∪ C , some of these matrices are mapped to a matrix that violates ( i j ∣ C ) (ij \mid C) ( ij ∣ C ) . □ \square □
Proofs of Propositions 3, 4 and 7
The three propositions share one argument, an expansion of the minor a s ( Σ ′ ) a_s(\Sigma') a s ( Σ ′ ) along the changed entries, so they are proved together. The expansion gives identity (2) for Proposition 3 3 3 and identity (4) for Proposition 4 4 4 . Proposition 7 7 7 then combines (4) with the recursion (8) .
Proof of Proposition 3. The perturbation adds τ k \tau_k τ k to the entry ( k , k ) (k,k) ( k , k ) of Σ i C , j C \Sigma_{iC,jC} Σ i C , j C for each k ∈ K ∩ C k \in K \cap C k ∈ K ∩ C . Expanding the determinant by multilinearity in these rows gives one term for each T ⊆ K ∩ C T \subseteq K \cap C T ⊆ K ∩ C , in which the rows in T T T are replaced by τ k \tau_k τ k times a unit vector. The Laplace expansion along them deletes the rows and columns in T T T . No sign appears, because the same indices are deleted on both sides, which gives (2) . If ( i j ∣ C ) (ij \mid C) ( ij ∣ C ) belongs to the set (3) , all the coefficients vanish and the statement holds for Σ ′ \Sigma' Σ ′ . Otherwise (2) is a non-zero polynomial, because its monomials in τ \tau τ are distinct, so the statement fails for generic τ \tau τ . As there are finitely many statements, the last claim follows.
Proof of Proposition 4. If k k k , l l l do not both occur in s s s , the block Σ i C , j C \Sigma_{i_C,j_C} Σ i C , j C contains neither position ( k , l ) (k,l) ( k , l ) nor ( l , k ) (l,k) ( l , k ) . In cases (a) and (b) it contains exactly one of them. The identity is then the expansion along that entry. In case (c) it contains both. The coefficient of τ \tau τ is the sum of the two cofactors,
L s = det Σ i k D , l j D + det Σ i l D , k j D . L_s = \det\Sigma_{ik_D,lj_D} + \det\Sigma_{il_D,kj_D}. L s = det Σ i k D , l j D + det Σ i l D , k j D .
with rows and columns taken in the order written. The coefficient of τ 2 \tau^2 τ 2 is minus the minor obtained by deleting the rows and columns k k k , l l l . Taking Schur complements with respect to Σ D \Sigma_D Σ D turns each cofactor into det Σ D \det\Sigma_D det Σ D times a 2 × 2 2 \times2 2 × 2 determinant of partial covariances, and the sum is (5) . Identity (6) follows, because the polynomial (4) is identically zero exactly when s ∈ ⟦ Σ ⟧ s \in\llbracket\Sigma\rrbracket s ∈ [ [ Σ ] ] and L s ( Σ ) = Q s ( Σ ) = 0 L_s(\Sigma) = Q_s(\Sigma) = 0 L s ( Σ ) = Q s ( Σ ) = 0 , while otherwise s s s fails for generic τ \tau τ .
Proof of Proposition 7. A statement of ⟦ Σ ⟧ \llbracket\Sigma\rrbracket [ [ Σ ] ] that does not contain both k k k and l l l is untouched. Its minor is the same for Σ \Sigma Σ as for Σ ′ \Sigma' Σ ′ . Let s = ( i j ∣ C ) ∈ ⟦ Σ ⟧ s = (ij \mid C) \in\llbracket\Sigma\rrbracket s = ( ij ∣ C ) ∈ [ [ Σ ] ] be a statement in which both occur. By (4) it holds for Σ ′ \Sigma' Σ ′ at every size if L s ( Σ ) = Q s ( Σ ) = 0 L_s(\Sigma) = Q_s(\Sigma) = 0 L s ( Σ ) = Q s ( Σ ) = 0 , and fails for generic τ \tau τ otherwise. We compare this condition with being screened for the three types of Proposition 4.
Type (a). The statement has no endpoint outside { k , l } \{k,l\} { k , l } , so it is not screened, and L s = det Σ C ≠ 0 L_s = \det\Sigma_C \ne0 L s = det Σ C = 0 .
Type (b). Let s = ( k j ∣ C ) s = (kj \mid C) s = ( k j ∣ C ) with l ∈ C l \in C l ∈ C , so that D = C ∖ { l } D = C \setminus\{l\} D = C ∖ { l } . Here Q s = 0 Q_s = 0 Q s = 0 , and L s = 0 L_s = 0 L s = 0 means that ( l j ∣ D ) (lj \mid D) ( l j ∣ D ) holds. By the recursion (8) the statements ( k j ∣ C ) (kj \mid C) ( k j ∣ C ) and ( l j ∣ D ) (lj \mid D) ( l j ∣ D ) both hold if and only if ( j k ∣ D ) (jk \mid D) ( j k ∣ D ) and ( j l ∣ D ) (jl \mid D) ( j l ∣ D ) both hold, that is, when the statement is screened by j j j .
Type (c). Write x = σ i j ⋅ D x = \sigma_{ij \cdot D} x = σ ij ⋅ D , a = σ i k ⋅ D a = \sigma_{ik \cdot D} a = σ ik ⋅ D , b = σ i l ⋅ D b = \sigma_{il \cdot D} b = σ i l ⋅ D , c = σ j k ⋅ D c = \sigma_{jk \cdot D} c = σ j k ⋅ D , d = σ j l ⋅ D d = \sigma_{jl \cdot D} d = σ j l ⋅ D , p = σ k k ⋅ D p = \sigma_{kk \cdot D} p = σ k k ⋅ D , q = σ l l ⋅ D q = \sigma_{ll \cdot D} q = σ l l ⋅ D and r = σ k l ⋅ D r = \sigma_{kl \cdot D} r = σ k l ⋅ D . By Proposition 4 the conditions L s = Q s = 0 L_s = Q_s = 0 L s = Q s = 0 amount to x = 0 x = 0 x = 0 and a d + b c = 0 ad + bc = 0 a d + b c = 0 . If it is screened by i i i then x = a = b = 0 x = a = b = 0 x = a = b = 0 , and if by j j j then x = c = d = 0 x = c = d = 0 x = c = d = 0 . Both conditions then hold. This proves the first claim. It also shows that, for generic τ \tau τ , a statement of type (a) or (b) holds for Σ ′ \Sigma' Σ ′ only if it is screened. The statements that fail for Σ \Sigma Σ fail for Σ ′ \Sigma' Σ ′ for generic τ \tau τ by Proposition 4. It remains to show that, if ⟦ Σ ⟧ \llbracket\Sigma\rrbracket [ [ Σ ] ] is cancellation-free, a statement of type (c) with x = 0 x = 0 x = 0 and a d + b c = 0 ad + bc = 0 a d + b c = 0 is screened. Since s s s holds for Σ \Sigma Σ and x = 0 x = 0 x = 0 , two applications of the recursion (8) give
a c q − ( a d + b c ) r + b d p = 0. (10) acq - (ad + bc)r + bdp = 0. \tag*{(10)} a c q − ( a d + b c ) r + b d p = 0. (10)
The statements ( i j ∣ D ) (ij \mid D) ( ij ∣ D ) and ( i j ∣ D ∪ { k , l } ) (ij \mid D \cup\{k,l\}) ( ij ∣ D ∪ { k , l }) both hold for Σ \Sigma Σ , so one of a , b , c , d a,b,c,d a , b , c , d vanishes because ⟦ Σ ⟧ \llbracket\Sigma\rrbracket [ [ Σ ] ] is cancellation-free. By symmetry in i , j i,j i , j and in k , l k,l k , l we may assume a = 0 a = 0 a = 0 . Then b c = 0 bc = 0 b c = 0 and (10) reduces to b d p = 0 bdp = 0 b d p = 0 . If b = 0 b = 0 b = 0 it is screened by i i i . Otherwise c = d = 0 c = d = 0 c = d = 0 and it is screened by j j j .
Proofs for undirected graphs
Proof of Theorem 8. Let i ≠ j i \ne j i = j and C ⊆ [ n ] ∖ { i , j } C \subseteq[n] \setminus\{i,j\} C ⊆ [ n ] ∖ { i , j } . We first show that C C C separates i i i from j j j in G K G^K G K if and only if C ∖ K C \setminus K C ∖ K separates them in G G G . Take a path from i i i to j j j in G G G that avoids C ∖ K C \setminus K C ∖ K and delete its vertices in C ∩ K C \cap K C ∩ K . Consecutive remaining vertices are joined in G G G by a path with interior in K K K , so they are adjacent in G K G^K G K . This gives a path in G K G^K G K that avoids C C C . Conversely, replace each edge of a path in G K G^K G K that avoids C C C by a path in G G G with interior in K K K . The resulting walk avoids C ∖ K C \setminus K C ∖ K , since the inserted paths have interior in K K K . Separation by a set implies separation by every larger set. Hence C ∖ K C \setminus K C ∖ K separates i i i from j j j in G G G if and only if ( i j ∣ C ∖ T ) ∈ I ( G ) (ij \mid C \setminus T) \in\mathcal{I}(G) ( ij ∣ C ∖ T ) ∈ I ( G ) for all T ⊂ K ∩ C T \subset K \cap C T ⊂ K ∩ C . By the first step this is the case exactly when ( i j ∣ C ) ∈ I ( G K ) (ij \mid C) \in\mathcal{I}(G^K) ( ij ∣ C ) ∈ I ( G K ) . If Σ \Sigma Σ is Markov to G G G , the coefficients in (2) vanish for the statements of I ( G K ) \mathcal{I}(G^K) I ( G K ) , which thus hold for Σ ′ \Sigma' Σ ′ . If Σ \Sigma Σ is faithful to G G G , the set (3) is I ( G K ) \mathcal{I}(G^K) I ( G K ) and Proposition 3 applies.
Proof of Theorem 9. If Σ \Sigma Σ is Markov to G G G then I ( G ) ⊆ [ [ Σ ] ] \mathcal{I}(G) \subseteq[\![\Sigma]\!] I ( G ) ⊆ [ [ Σ ] ] , hence I ( G ) k l ⊆ [ [ Σ ] ] k l \mathcal{I}(G)^{kl} \subseteq[\![\Sigma]\!]^{kl} I ( G ) k l ⊆ [ [ Σ ] ] k l , because both properties only ask that certain statements lie in the set. Proposition 7 then gives the first claim.
(a) The set I ( G ) \mathcal{I}(G) I ( G ) is cancellation-free. Indeed, if D D D separates i i i from j j j then k k k lies in the connected component of at most one of them after deleting D D D , so D D D separates k k k from i i i or from j j j . Proposition 7 therefore applies to a faithful matrix, for which [ [ Σ ] ] = I ( G ) [\![\Sigma]\!] = \mathcal{I}(G) [ [ Σ ] ] = I ( G ) .
(b) The vertices i i i and j j j are non-adjacent in the graph of ( Σ ′ ) − 1 (\Sigma')^{-1} ( Σ ′ ) − 1 if and only if ( i j ∣ C ) ∈ I ( G ) k l (ij \mid C) \in\mathcal{I}(G)^{kl} ( ij ∣ C ) ∈ I ( G ) k l for C = [ n ] ∖ { i , j } C = [n] \setminus\{i,j\} C = [ n ] ∖ { i , j } . Here D = [ n ] ∖ { i , j , k , l } D = [n] \setminus\{i,j,k,l\} D = [ n ] ∖ { i , j , k , l } , and D D D separates a vertex e e e from the rest of { i , j , k , l } \{i,j,k,l\} { i , j , k , l } if and only if e e e is adjacent to none of them in G G G . The pair { k , l } \{k,l\} { k , l } is of type (a) and becomes adjacent. A pair { k , j } \{k,j\} { k , j } with j ≠ l j \ne l j = l stays non-adjacent if and only if j j j is adjacent to neither k k k nor l l l in G G G . A pair { i , j } \{i,j\} { i , j } disjoint from { k , l } \{k,l\} { k , l } stays non-adjacent if and only if it is non-adjacent in G G G and one of i , j i,j i , j has no neighbour in { k , l } \{k,l\} { k , l } . These are the non-adjacencies of G k l G^{kl} G k l .
For the last claim, I ( G ) k l \mathcal{I}(G)^{kl} I ( G ) k l contains I 0 \mathcal{I}_0 I 0 and is the structure of the positive definite matrix Σ ′ \Sigma' Σ ′ by part (a). Let Σ ′ ′ ∈ P D n \Sigma'' \in\mathrm{PD}_n Σ ′′ ∈ PD n with I 0 ⊆ [ [ Σ ′ ′ ] ] \mathcal{I}_0 \subseteq[\![\Sigma'']\!] I 0 ⊆ [ [ Σ ′′ ] ] and let ( i j ∣ C ) ∈ I ( G ) k l (ij \mid C) \in\mathcal{I}(G)^{kl} ( ij ∣ C ) ∈ I ( G ) k l be screened by e e e . The statements ( e a ∣ D ) (ea \mid D) ( e a ∣ D ) with a ∈ { i , j , k , l } ∖ { e } a \in\{i,j,k,l\} \setminus\{e\} a ∈ { i , j , k , l } ∖ { e } belong to I ( G ) \mathcal{I}(G) I ( G ) . Since k k k and l l l do not both occur in any of them, they hold for Σ ′ ′ \Sigma'' Σ ′′ . Hence Y e Y_e Y e is independent of the other variables indexed by { i , j , k , l } \{i,j,k,l\} { i , j , k , l } given Y D Y_D Y D , and the first property recalled at the beginning of this appendix gives ( i j ∣ C ) ∈ [ [ Σ ′ ′ ] ] (ij \mid C) \in[\![\Sigma'']\!] ( ij ∣ C ) ∈ [ [ Σ ′′ ] ] .
Proof of Corollary 10. An undirected graph is determined by its separation statements. By Theorem 8 the first claim amounts to G { k } = G G^{\{k\}} = G G { k } = G , that is, to k k k being simplicial. By Theorem 9(b) the second claim requires G k l = G G^{kl} = G G k l = G . Equivalently N [ k ] ∪ N [ l ] N[k] \cup N[l] N [ k ] ∪ N [ l ] is a clique, that is, k k k and l l l are adjacent simplicial vertices.
For sufficiency let ( i j ∣ C ) ∈ I ( G ) (ij \mid C) \in\mathcal{I}(G) ( ij ∣ C ) ∈ I ( G ) involve both k k k and l l l . Put D = C ∖ { k , l } D = C \setminus\{k,l\} D = C ∖ { k , l } . If a set C ′ C' C ′ separates i i i from j j j and m ∈ C ′ m \in C' m ∈ C ′ is simplicial, then C ′ ∖ { m } C' \setminus\{m\} C ′ ∖ { m } separates them as well. Indeed, a path from i i i to j j j that avoids C ′ ∖ { m } C' \setminus\{m\} C ′ ∖ { m } passes through m m m , whose two neighbours on the path are adjacent, so leaving m m m out gives a path that avoids C ′ C' C ′ . Hence D D D separates i i i from j j j . The adjacent vertices k k k and l l l lie outside D D D , hence in one connected component of G G G after deleting D D D . This component does not contain both i i i and j j j . An endpoint outside { k , l } \{k,l\} { k , l } is therefore separated by D D D from the other vertices of { i , j , k , l } \{i,j,k,l\} { i , j , k , l } , so the statement is screened and I ( G ) k l = I ( G ) \mathcal{I}(G)^{kl} = \mathcal{I}(G) I ( G ) k l = I ( G ) .
Proof of Theorem 11
Throughout, G G G is a connected decomposable graph with junction tree T T T , and S e S_e S e , A e A_e A e , B e B_e B e are as in § 5.1 . We call Δ A e ∪ S e , B e ∪ S e \Delta_{A_e \cup S_e, B_e \cup S_e} Δ A e ∪ S e , B e ∪ S e the block of the edge e e e . Three facts about junction trees are used ([11 ] ). The maximal cliques that contain a given vertex form a subtree of T T T . Every set S e S_e S e is non-empty and separates A e A_e A e from B e B_e B e , while A e ∪ B e ∪ S e = [ n ] A_e \cup B_e \cup S_e = [n] A e ∪ B e ∪ S e = [ n ] . If C C C is a leaf of T T T with neighbour C ′ C' C ′ , the vertices of C ∖ C ′ C \setminus C' C ∖ C ′ lie in no other maximal clique, and deleting them from G G G gives a connected decomposable graph with junction tree T − C T - C T − C .
The proof has five steps. Step 1 shows that M ( G ) \mathcal{M}(G) M ( G ) is defined by the statements A e ⊥ B e ∣ S e A_e \perp B_e \mid S_e A e ⊥ B e ∣ S e , which gives sufficiency by Theorem 1. Necessity is proved by induction on the number of maximal cliques, removing a leaf C C C of T T T . Step 2 shows that the multiplier restricted to the remaining vertices is model-preserving for the smaller graph. Steps 3 and 4 show that the block of the edge that joins C C C to T − C T-C T − C has rank one. In particular the rows of the removed vertices are proportional to what remains, which is used in Step 5 for the blocks of the other edges.
Step 1. A matrix Σ ∈ P D n \Sigma\in\mathrm{PD}_n Σ ∈ PD n lies in M ( G ) \mathcal{M}(G) M ( G ) if and only if it satisfies A e ⊥ B e ∣ S e A_e \perp B_e \mid S_e A e ⊥ B e ∣ S e for all edges e e e of T T T . Necessity is the global Markov property. For sufficiency let i i i and j j j be non-adjacent. No maximal clique contains both, so the subtree of the maximal cliques that contain i i i is disjoint from that of the maximal cliques that contain j j j . Let e e e be the first edge of the path of T T T that leads from the first subtree to the second. The two subtrees lie on different sides of e e e , and neither i i i nor j j j belongs to S e S_e S e . Up to exchanging the two sides, i ∈ A e i \in A_e i ∈ A e and j ∈ B e j \in B_e j ∈ B e . The first property recalled at the beginning of this appendix then gives ( i j ∣ [ n ] ∖ { i , j } ) ∈ [ [ Σ ] ] (ij \mid[n] \setminus\{i,j\}) \in[\![\Sigma]\!] ( ij ∣ [ n ] ∖ { i , j }) ∈ [ [ Σ ] ] , that is, ( Σ − 1 ) i j = 0 (\Sigma^{-1})_{ij} = 0 ( Σ − 1 ) ij = 0 . If every block has rank one, Theorem 1 shows that Δ \Delta Δ preserves each statement A e ⊥ B e ∣ S e A_e \perp B_e \mid S_e A e ⊥ B e ∣ S e , so it is model-preserving for M ( G ) \mathcal{M}(G) M ( G ) . Conversely, let Δ \Delta Δ be model-preserving for M ( G ) \mathcal{M}(G) M ( G ) . We show by induction on the number of maximal cliques that every block has rank one. With one maximal clique there is nothing to prove. Otherwise let C C C be a leaf of T T T with neighbour C ′ C' C ′ . Put S = C ∩ C ′ S=C\cap C' S = C ∩ C ′ , R = C ∖ S R=C\setminus S R = C ∖ S and V ′ = [ n ] ∖ R V'=[n]\setminus R V ′ = [ n ] ∖ R . Let G ′ G' G ′ be the graph obtained from G G G by deleting R R R , with junction tree T ′ = T − C T'=T-C T ′ = T − C . Recall that a block with non-zero entries has rank one exactly when all its 2 × 2 2\times2 2 × 2 minors vanish.
Step 2. The multiplier Δ V ′ \Delta_{V'} Δ V ′ is model-preserving for M ( G ′ ) \mathcal{M}(G') M ( G ′ ) . Let Σ 1 ∈ M ( G ′ ) \Sigma_1\in\mathcal{M}(G') Σ 1 ∈ M ( G ′ ) be such that Δ V ′ ∘ Σ 1 \Delta_{V'}\circ\Sigma_1 Δ V ′ ∘ Σ 1 is positive definite. Let Σ \Sigma Σ be the matrix in which the variables of V ′ V' V ′ have covariance Σ 1 \Sigma_1 Σ 1 , while those of R R R have unit variance and are independent of all the others. Then Σ ∈ M ( G ) ∩ U Δ \Sigma\in\mathcal{M}(G)\cap U_\Delta Σ ∈ M ( G ) ∩ U Δ , so Δ ∘ Σ ∈ M ( G ) \Delta\circ\Sigma\in\mathcal{M}(G) Δ ∘ Σ ∈ M ( G ) . This matrix is block diagonal, hence the inverse of its block Δ V ′ ∘ Σ 1 \Delta_{V'}\circ\Sigma_1 Δ V ′ ∘ Σ 1 vanishes at the non-edges of G ′ G' G ′ . By the induction hypothesis the blocks of Δ V ′ \Delta_{V'} Δ V ′ for the edges of T ′ T' T ′ have rank one.
Step 3. The block Δ C , C ′ \Delta_{C,C'} Δ C , C ′ has rank one. Let r ∈ R r\in R r ∈ R and j ∈ C ′ ∖ S j\in C'\setminus S j ∈ C ′ ∖ S . Consider the matrices that satisfy ( r j ∣ S ) (rj\mid S) ( r j ∣ S ) in which the variables outside { r , j } ∪ S \{r,j\}\cup S { r , j } ∪ S are mutually independent and independent of the remaining ones. They belong to M ( G ) \mathcal{M}(G) M ( G ) , because the vertices of { r } ∪ S \{r\}\cup S { r } ∪ S are pairwise adjacent and so are those of { j } ∪ S \{j\}\cup S { j } ∪ S . Every matrix of M ( G ) \mathcal{M}(G) M ( G ) satisfies ( r j ∣ S ) (rj\mid S) ( r j ∣ S ) , since S S S separates r r r from j j j . Hence Δ \Delta Δ maps none of these matrices to one that violates this statement. By Theorem 1(b), applied to the principal submatrix indexed by { r , j } ∪ S \{r,j\}\cup S { r , j } ∪ S , the block Δ r S , j S \Delta_{rS,jS} Δ r S , j S has rank one. As in the last part of the proof of Theorem 1, the block with rows R ∪ S = C R\cup S=C R ∪ S = C and columns ( C ′ ∖ S ) ∪ S = C ′ (C'\setminus S)\cup S=C' ( C ′ ∖ S ) ∪ S = C ′ then has rank one.
Step 4. The block of the edge { C , C ′ } \{C,C'\} { C , C ′ } has rank one. This block is Δ C , V ′ \Delta_{C,V'} Δ C , V ′ . Fix s 0 ∈ S s_0\in S s 0 ∈ S , which indexes both a row and a column of it. The block has rank one as soon as
δ c y δ s 0 s 0 = δ c s 0 δ s 0 y for all c ∈ C and y ∈ V ′ . (11) \delta_{cy}\delta_{s_0s_0}=\delta_{cs_0}\delta_{s_0y}\qquad\text{for all }c\in C\text{ and }y\in V'. \tag*{(11)} δ cy δ s 0 s 0 = δ c s 0 δ s 0 y for all c ∈ C and y ∈ V ′ . (11)
For y ∈ C ′ y\in C' y ∈ C ′ this holds by Step 3. Let y ∉ C ′ y\notin C' y ∈ / C ′ , and let e ′ e' e ′ be the first edge of the path of T ′ T' T ′ from C ′ C' C ′ to the nearest maximal clique that contains y y y . The maximal cliques that contain y y y form a subtree that avoids C ′ C' C ′ , so they all lie beyond e ′ e' e ′ , and y ∉ S e ′ y\notin S_{e'} y ∈ / S e ′ because S e ′ ⊆ C ′ S_{e'}\subseteq C' S e ′ ⊆ C ′ . Up to transposition, the block of e ′ e' e ′ in Δ V ′ \Delta_{V'} Δ V ′ therefore has the vertices of C ′ C' C ′ among its rows and y y y among its columns.
Let first c ∈ S c\in S c ∈ S and take t ∈ S e ′ t\in S_{e'} t ∈ S e ′ . The rows c , s 0 c,s_0 c , s 0 and the columns y , t y,t y , t belong to the block of e ′ e' e ′ , which has rank one by Step 2, so δ c y δ s 0 t = δ c t δ s 0 y \delta_{cy}\delta_{s_0t}=\delta_{ct}\delta_{s_0y} δ cy δ s 0 t = δ c t δ s 0 y . Since t ∈ C ′ t\in C' t ∈ C ′ , Step 3 gives δ c t δ s 0 s 0 = δ c s 0 δ s 0 t \delta_{ct}\delta_{s_0s_0}=\delta_{cs_0}\delta_{s_0t} δ c t δ s 0 s 0 = δ c s 0 δ s 0 t . Multiplying the two equalities and cancelling δ c t δ s 0 t \delta_{ct}\delta_{s_0t} δ c t δ s 0 t yields (11) .
Let now c = r ∈ R c=r\in R c = r ∈ R . We use a matrix of the model in which Y r Y_r Y r depends on the other variables only through Y s 0 Y_{s_0} Y s 0 . Let G ′ ′ G'' G ′′ be obtained from G G G by deleting the edges between r r r and the vertices other than s 0 s_0 s 0 . It is connected, because the neighbours of r r r in G G G are pairwise adjacent, and M ( G ′ ′ ) ⊆ M ( G ) \mathcal{M}(G'')\subseteq\mathcal{M}(G) M ( G ′′ ) ⊆ M ( G ) . Let N N N be the adjacency matrix of G ′ ′ G'' G ′′ . For small ε > 0 \varepsilon>0 ε > 0 the matrix Σ ‾ = ( I − ε N ) − 1 = ∑ m ≥ 0 ε m N m \overline{\Sigma}=(I-\varepsilon N)^{-1}=\sum_{m\geq0}\varepsilon^mN^m Σ = ( I − εN ) − 1 = ∑ m ≥ 0 ε m N m belongs to M ( G ′ ′ ) \mathcal{M}(G'') M ( G ′′ ) and has positive entries. It also lies in U Δ U_\Delta U Δ , as it tends to the identity matrix when ε → 0 \varepsilon\to0 ε → 0 . In G ′ ′ G'' G ′′ the vertex s 0 s_0 s 0 separates r r r from all other vertices, so σ r x = ρ σ s 0 x \sigma_{rx}=\rho\sigma_{s_0x} σ r x = ρ σ s 0 x for every x ≠ r x\ne r x = r , with ρ = σ r s 0 / σ s 0 s 0 > 0 \rho=\sigma_{rs_0}/\sigma_{s_0s_0}>0 ρ = σ r s 0 / σ s 0 s 0 > 0 .
The matrix Δ ∘ Σ \Delta\circ\Sigma Δ ∘ Σ belongs to M ( G ) \mathcal{M}(G) M ( G ) , in which S S S separates r r r from y y y , hence a r y ∣ S ( Δ ∘ Σ ) = 0 a_{ry\mid S}(\Delta\circ\Sigma)=0 a r y ∣ S ( Δ ∘ Σ ) = 0 . In the submatrix ( Δ ∘ Σ ) r S , y S (\Delta\circ\Sigma)_{rS,yS} ( Δ ∘ Σ ) r S , y S the row of r r r has the entries ρ δ r x σ s 0 x \rho\,\delta_{rx}\sigma_{s_0x} ρ δ r x σ s 0 x and the row of s 0 s_0 s 0 has the entries δ s 0 x σ s 0 x \delta_{s_0x}\sigma_{s_0x} δ s 0 x σ s 0 x , for x ∈ { y } ∪ S x\in\{y\}\cup S x ∈ { y } ∪ S . By Step 3, δ r x = λ δ s 0 x \delta_{rx}=\lambda\delta_{s_0x} δ r x = λ δ s 0 x for x ∈ S x\in S x ∈ S , where λ = δ r s 0 / δ s 0 s 0 \lambda=\delta_{rs_0}/\delta_{s_0s_0} λ = δ r s 0 / δ s 0 s 0 . After subtracting λ ρ \lambda\rho λ ρ times the row of s 0 s_0 s 0 from the row of r r r , the only entry of the row of r r r that can be non-zero is the one in the column of y y y . Expanding the determinant along this row gives
0 = a r y ∣ S ( Δ ∘ Σ ) = ρ ( δ r y − λ δ s 0 y ) σ s 0 y det ( Δ ∘ Σ ) S . 0=a_{ry\mid S}(\Delta\circ\Sigma)=\rho\left(\delta_{ry}-\lambda\delta_{s_0y}\right)\sigma_{s_0y}\det(\Delta\circ\Sigma)_S. 0 = a r y ∣ S ( Δ ∘ Σ ) = ρ ( δ r y − λ δ s 0 y ) σ s 0 y det ( Δ ∘ Σ ) S .
Since ρ \rho ρ , σ s 0 y \sigma_{s_0y} σ s 0 y and det ( Δ ∘ Σ ) S \det(\Delta\circ\Sigma)_S det ( Δ ∘ Σ ) S are positive, δ r y = λ δ s 0 y \delta_{ry}=\lambda\delta_{s_0y} δ r y = λ δ s 0 y , which is (11) for c = r c=r c = r .
Step 5. The block of every other edge has rank one. Let e ′ e' e ′ be an edge of T ′ T' T ′ . Up to transposition, its block in Δ \Delta Δ is its block in Δ V ′ \Delta_{V'} Δ V ′ with the rows of R R R added, and the latter has rank one by Step 2. By (11) the row of r ∈ R r\in R r ∈ R is, on the columns in V ′ V' V ′ , a multiple of the row of s 0 s_0 s 0 . This row already belongs to the block because s 0 ∈ C ′ s_0\in C' s 0 ∈ C ′ , so the rank remains equal to one. □ \square □
Proof of Theorem 12
Part (a) compares the set (3) with m-separation in G + G^{+} G + . Part (b) follows the proof of Theorem 9 once I ( G ) \mathcal{I}(G) I ( G ) is known to be cancellation-free, which is Lemma 15. Two facts are used [17 ] . For disjoint D , M ⊆ [ n ] D, M \subseteq[n] D , M ⊆ [ n ] there is an ancestral graph on V = [ n ] ∖ ( D ∪ M ) V = [n] \setminus(D \cup M) V = [ n ] ∖ ( D ∪ M ) whose m-separation statements are the ( a b ∣ B ) (ab \mid B) ( ab ∣ B ) with a , b ∈ V a,b \in V a , b ∈ V , B ⊆ V B \subseteq V B ⊆ V and ( a b ∣ B ∪ D ) ∈ I ( G ) (ab \mid B \cup D) \in\mathcal{I}(G) ( ab ∣ B ∪ D ) ∈ I ( G ) . Moreover, every ancestral graph has a faithful Gaussian distribution.
Lemma 15. Let G G G be an ancestral graph. Then the set I ( G ) \mathcal{I}(G) I ( G ) of its m-separation statements is cancellation-free for every pair { k , l } \{k,l\} { k , l } of distinct vertices.
Proof. Let i , j , k , l i,j,k,l i , j , k , l be distinct. Let D ⊆ [ n ] ∖ { i , j , k , l } D \subseteq[n] \setminus\{i,j,k,l\} D ⊆ [ n ] ∖ { i , j , k , l } be such that ( i j ∣ D ) (ij \mid D) ( ij ∣ D ) and ( i j ∣ D ∪ { k , l } ) (ij \mid D \cup\{k,l\}) ( ij ∣ D ∪ { k , l }) belong to I ( G ) \mathcal{I}(G) I ( G ) . Marginalizing and conditioning gives an ancestral graph H H H on { i , j , k , l } \{i,j,k,l\} { i , j , k , l } whose m-separation statements are the ( a b ∣ B ) (ab \mid B) ( ab ∣ B ) with ( a b ∣ B ∪ D ) ∈ I ( G ) (ab \mid B \cup D) \in\mathcal{I}(G) ( ab ∣ B ∪ D ) ∈ I ( G ) . In H H H the set ∅ \varnothing ∅ m-separates i i i from j j j , and so does { k , l } \{k,l\} { k , l } . Suppose that no pair { a , b } \{a,b\} { a , b } with a ∈ { i , j } a \in\{i,j\} a ∈ { i , j } and b ∈ { k , l } b \in\{k,l\} b ∈ { k , l } is m-separated by ∅ \varnothing ∅ , so that each of these pairs is joined by a path without colliders. The vertices i , j i,j i , j are not adjacent, and they are not both adjacent to k k k . Otherwise the path i , k , j i,k,j i , k , j would be m-connecting given ∅ \varnothing ∅ if k k k is a non-collider on it, and given { k , l } \{k,l\} { k , l } if k k k is a collider. The same holds for l l l , so no path joining these pairs contains both i i i and j j j .
Case 1: i i i and k k k are adjacent. Then j j j is not adjacent to k k k , and their only possible collider-free path is j , l , k j,l,k j , l , k . So l l l is adjacent to j j j and to k k k , as a non-collider between them. Hence i i i is not adjacent to l l l . Their only collider-free path is i , k , l i,k,l i , k , l , on which k k k is a non-collider. The path i , k , l , j i,k,l,j i , k , l , j then has no collider, which contradicts the m-separation of i i i and j j j by ∅ \varnothing ∅ .
Case 2: i i i and k k k are not adjacent. Their only possible collider-free path is i , l , k i,l,k i , l , k , so l l l is adjacent to both, as a non-collider. Then j j j is not adjacent to l l l , and likewise k k k is a non-collider on the path j , k , l j,k,l j , k , l . The path i , l , k , j i,l,k,j i , l , k , j has no collider, again a contradiction.
Proof of Theorem 12. (a) For a statement s s s on [ n ] [n] [ n ] let s ′ s' s ′ be obtained by replacing each k ∈ K k \in K k ∈ K that occurs in s s s by k ′ k' k ′ , and let J K \mathcal{J}_{K} J K be the set (3) with I ( G ) \mathcal{I}(G) I ( G ) in place of [ [ Σ ] ] [\![\Sigma]\!] [ [ Σ ] ] . By the definition of G ⟨ K ⟩ G^{\langle K\rangle} G ⟨ K ⟩ , a statement s s s belongs to I ( G ⟨ K ⟩ ) \mathcal{I}(G^{\langle K\rangle}) I ( G ⟨ K ⟩ ) exactly when s ′ ∈ I ( G + ) s' \in\mathcal{I}(G^{+}) s ′ ∈ I ( G + ) . We show that this is the case if and only if s ∈ J K s \in\mathcal{J}_{K} s ∈ J K . The two claims then follow as in the proof of Theorem 8. If Σ \Sigma Σ is Markov to G G G , the coefficients in (2) vanish for every s ∈ J K s \in\mathcal{J}_{K} s ∈ J K . If Σ \Sigma Σ is faithful, the set (3) is J K \mathcal{J}_{K} J K and Proposition 3 applies.
If s ∉ J K s \notin\mathcal{J}_{K} s ∈ / J K then s ′ ∉ I ( G + ) s' \notin\mathcal{I}(G^{+}) s ′ ∈ / I ( G + ) . Let s = ( i j ∣ C ) s = (ij \mid C) s = ( ij ∣ C ) . For some T ⊆ K ∩ C T \subseteq K \cap C T ⊆ K ∩ C a path in G G G between i i i and j j j is m-connecting given C ∖ T C \setminus T C ∖ T . Extend it by the edge i → i ′ i \to i' i → i ′ if i ∈ K i \in K i ∈ K and likewise for j j j . Its non-colliders are outside C ∖ T C \setminus T C ∖ T , hence outside the conditioning set of s ′ s' s ′ , which contains no vertex of K K K . Each of its colliders is an ancestor of some c ∈ C ∖ T c \in C \setminus T c ∈ C ∖ T , and c c c or c ′ c' c ′ is in the conditioning set of s ′ s' s ′ . The extended path is therefore m-connecting in G + G^{+} G + .
If s ∈ J K s \in\mathcal{J}_{K} s ∈ J K then s ′ ∈ I ( G + ) s' \in\mathcal{I}(G^{+}) s ′ ∈ I ( G + ) . Take a Gaussian vector faithful to G + G^{+} G + . The m-separation statements among the vertices of [ n ] [n] [ n ] are the same in G + G^{+} G + and in G G G , so the covariance matrix Σ 0 \Sigma_{0} Σ 0 of the components indexed by [ n ] [n] [ n ] is faithful to G G G . Each k ′ k' k ′ is m-separated from all other vertices by k k k . Hence Y k ′ = β k Y k + ε k Y_{k'} = \beta_{k}Y_{k} + \varepsilon_{k} Y k ′ = β k Y k + ε k with β k ≠ 0 \beta_{k} \ne0 β k = 0 , where the ε k \varepsilon_{k} ε k are independent of each other and of the components indexed by [ n ] [n] [ n ] . Up to a rescaling of the coordinates in K K K , which does not affect the structure, the covariance matrix of the components indexed by ( [ n ] ∖ K ) ∪ { k ′ : k ∈ K } ([n] \setminus K) \cup\{k' : k \in K\} ([ n ] ∖ K ) ∪ { k ′ : k ∈ K } is Σ 0 + ∑ k ∈ K τ k E k k \Sigma_{0} + \sum_{k \in K}\tau_{k}E_{kk} Σ 0 + ∑ k ∈ K τ k E k k with τ k > 0 \tau_{k} > 0 τ k > 0 . All coefficients in (2) vanish for s s s , so s ′ s' s ′ holds for this vector and s ′ ∈ I ( G + ) s' \in\mathcal{I}(G^{+}) s ′ ∈ I ( G + ) .
(b) The proof of Theorem 9 uses the graph in two places only. Its part (a) needs I ( G ) \mathcal{I}(G) I ( G ) to be cancellation-free for { k , l } \{k,l\} { k , l } , which holds by Lemma 15. Its part (b) uses that, for D = [ n ] ∖ { i , j , k , l } D = [n] \setminus\{i,j,k,l\} D = [ n ] ∖ { i , j , k , l } , the statements ( e a ∣ D ) (ea \mid D) ( e a ∣ D ) with a ∈ { i , j , k , l } ∖ { e } a \in\{i,j,k,l\} \setminus\{e\} a ∈ { i , j , k , l } ∖ { e } all belong to I ( G ) \mathcal{I}(G) I ( G ) exactly when e e e is adjacent to none of these vertices in G G G . For an ancestral graph this holds with G a G^{a} G a in place of G G G . Indeed, for a matrix faithful to G G G both conditions say that the row of e e e in its inverse vanishes at these positions, and G a G^{a} G a is the graph of this inverse. The rest of that proof, including the minimality of I ( G ) k l \mathcal{I}(G)^{kl} I ( G ) k l , applies unchanged with ( G a ) k l (G^{a})^{kl} ( G a ) k l in place of G k l G^{kl} G k l .
Proof of Corollary 13
Here G G G is a directed acyclic graph, M A M_A M A is the moral graph of an ancestral set A A A and A s A_s A s is the smallest ancestral set that contains the vertices of a statement s s s . Thus G s = M A s G_s = M_{A_s} G s = M A s , and s = ( i j ∣ C ) s = (ij \mid C) s = ( ij ∣ C ) belongs to I ( G ) \mathcal{I}(G) I ( G ) exactly when C C C separates i i i from j j j in M A s M_{A_s} M A s (§ 5.3 ). If A ′ ⊆ A A' \subseteq A A ′ ⊆ A are ancestral sets, then M A ′ M_{A'} M A ′ is a subgraph of M A M_A M A . The property of simplicial vertices shown in the proof of Corollary 10 is also used.
(a) Let k k k be simplicial in M A M_A M A for every ancestral set A A A that contains it, and let s = ( i j ∣ C ) ∈ I ( G ) s = (ij \mid C) \in\mathcal{I}(G) s = ( ij ∣ C ) ∈ I ( G ) with k ∈ C k \in C k ∈ C . By the property of simplicial vertices C ∖ { k } C \setminus\{k\} C ∖ { k } separates i i i from j j j in M A s M_{A_s} M A s , hence in the subgraph M A t M_{A_t} M A t for t = ( i j ∣ C ∖ { k } ) t = (ij \mid C \setminus\{k\}) t = ( ij ∣ C ∖ { k }) , so that t ∈ I ( G ) t \in\mathcal{I}(G) t ∈ I ( G ) . Hence the set (3) is I ( G ) \mathcal{I}(G) I ( G ) .
Conversely, let u u u , v v v be neighbours of k k k in some M A M_A M A that are not adjacent there. Then k k k has a child in A A A , since a vertex without children in A A A has only its parents as neighbours in M A M_A M A , which are pairwise adjacent. Let s = ( u v ∣ C ) s = (uv \mid C) s = ( uv ∣ C ) with C = A ∖ { u , v } C = A \setminus\{u,v\} C = A ∖ { u , v } and t = ( u v ∣ C ∖ { k } ) t = (uv \mid C \setminus\{k\}) t = ( uv ∣ C ∖ { k }) . Then A s = A t = A A_s = A_t = A A s = A t = A , as k k k has a child in A A A . Hence s ∈ I ( G ) s \in\mathcal{I}(G) s ∈ I ( G ) , while t ∉ I ( G ) t \notin\mathcal{I}(G) t ∈ / I ( G ) since u , k , v u,k,v u , k , v is a path in M A M_A M A , and s s s is lost by Proposition 3.
For the second description, suppose first that the vertices of ch ( k ) ∪ { k } \operatorname{ch}(k) \cup\{k\} ch ( k ) ∪ { k } are pairwise adjacent with pa ( a ) ⊆ pa ( b ) \operatorname{pa}(a) \subseteq\operatorname{pa}(b) pa ( a ) ⊆ pa ( b ) for every edge a → b a \to b a → b between two of them. Let A A A be an ancestral set that contains k k k and let W W W consist of k k k together with its children in A A A . As G G G is acyclic, some b ∈ W b \in W b ∈ W is a child of all other vertices of W W W . A neighbour x ≠ b x \ne b x = b of k k k in M A M_A M A lies in W W W or is a parent of some a ∈ W a \in W a ∈ W , and in both cases x ∈ pa ( b ) x \in\operatorname{pa}(b) x ∈ pa ( b ) by the inclusions between the sets of parents. The neighbours of k k k other than b b b are thus parents of b b b , hence pairwise adjacent in M A M_A M A and adjacent to b b b .
Conversely, let k k k be simplicial in every such moral graph. Two children a a a , b b b of k k k have no common child in the smallest ancestral set A A A that contains them, since it would be an ancestor of one of them. Being neighbours of k k k in M A M_A M A , they are adjacent in G G G . Let now a → b a \to b a → b be an edge between two vertices of ch ( k ) ∪ { k } \operatorname{ch}(k) \cup\{k\} ch ( k ) ∪ { k } and A A A the smallest ancestral set containing b b b . Then b b b is a child of k k k without children in A A A . A parent y ≠ k y \ne k y = k of a a a is a neighbour of k k k in M A M_A M A , as a parent of k k k or of its child a a a . Hence y y y and b b b are adjacent in M A M_A M A , thus in G G G for lack of a common child in A A A , and y ∈ pa ( b ) y \in\operatorname{pa}(b) y ∈ pa ( b ) as y y y is an ancestor of b b b .
(b) Let P = { { k , l } } P = \{\{k,l\}\} P = {{ k , l }} . Suppose that k k k is adjacent to l l l and that both are simplicial in M A M_A M A for every ancestral set A A A containing them. Let s = ( i j ∣ C ) ∈ I ( G ) s = (ij \mid C) \in\mathcal{I}(G) s = ( ij ∣ C ) ∈ I ( G ) be a statement in which both occur. Then G s + P s = M A s G_s + P_s = M_{A_s} G s + P s = M A s , in which C C C separates i i i from j j j . So does C ∖ { k , l } C \setminus\{k,l\} C ∖ { k , l } , by the property of simplicial vertices. The other statements belong to I ( G ) P \mathcal{I}(G)^P I ( G ) P if and only if they belong to I ( G ) \mathcal{I}(G) I ( G ) . Hence I ( G ) P = I ( G ) \mathcal{I}(G)^P = \mathcal{I}(G) I ( G ) P = I ( G ) , and Σ ′ \Sigma' Σ ′ is faithful to G G G by Theorem 14(a).
Conversely, let Σ ′ \Sigma' Σ ′ be faithful to G G G . If k k k were not adjacent to l l l , the parents of one of them would d-separate them ([11 ] ), and this statement of type (a) fails for Σ ′ \Sigma' Σ ′ by Proposition 4. Suppose that k k k , say, has neighbours u u u , v v v in some M A M_A M A with k , l ∈ A k,l \in A k , l ∈ A that are not adjacent there. Let C = A ∖ { u , v } C = A \setminus\{u,v\} C = A ∖ { u , v } and s = ( u v ∣ C ) s = (uv \mid C) s = ( uv ∣ C ) . Then s ∈ I ( G ) s \in\mathcal{I}(G) s ∈ I ( G ) is a statement in which k k k and l l l both occur, with G s + P s = M A G_s + P_s = M_A G s + P s = M A . The path u , k , v u,k,v u , k , v avoids C ∖ { k , l } C \setminus\{k,l\} C ∖ { k , l } , so s ∉ I ( G ) P s \notin\mathcal{I}(G)^P s ∈ / I ( G ) P , which contradicts Theorem 14(a). □
Proof of Theorem 14
The claim for a Markov matrix follows directly from the rank of an unchanged submatrix. For a faithful matrix the proof changes one covariance at a time and applies Proposition 7 at each step. For the step from P P P to P ′ = P ∪ { { k , l } } P' = P \cup\{\{k,l\}\} P ′ = P ∪ {{ k , l }} , Lemma 17(a) shows that I ( G ) P \mathcal{I}(G)^P I ( G ) P is cancellation-free, and Lemma 17(b) that the statements kept by Proposition 7 are those of I ( G ) P ′ \mathcal{I}(G)^{P'} I ( G ) P ′ . Both lemmas rest on Lemma 16, which collects properties of the graphs G s G_s G s .
Throughout, G G G is an ancestral graph, and the definitions of § 5.3 are used with a set U U U of vertices in place of the indices of a statement. Thus G U G_U G U has the vertices anterior to U U U , two of them being adjacent if they are joined in G G G by a path through such vertices on which every interior vertex is a collider. A vertex anterior to a vertex that is anterior to U U U is itself anterior to U U U . Recall that G G G has no directed cycle and that a vertex with an arrowhead has no undirected edge ([17 ] ). Consequently, if a vertex w w w without undirected edges is anterior to a vertex b ≠ w b \ne w b = w , a directed path leads from w w w to b b b . Indeed, the path leaves w w w by a directed edge, so the next vertex has an arrowhead, hence no undirected edge, and the same applies to each vertex in turn.
Lemma 16. Let U ⊆ U ′ U \subseteq U' U ⊆ U ′ and U ′ ′ U'' U ′′ be sets of vertices.
(a) If all vertices of U ′ ′ U'' U ′′ are anterior to U ′ U' U ′ , then G U ′ ′ G_{U''} G U ′′ is a subgraph of G U ′ G_{U'} G U ′ .
(b) Let u u u be a vertex of G U G_U G U and u v uv uv an edge of G U ′ G_{U'} G U ′ that is not an edge of G U G_U G U . Then some vertex b ∈ U ′ b \in U' b ∈ U ′ is not anterior to U U U and is joined to u u u by a path in G U ∪ { b } G_{U \cup\{b\}} G U ∪ { b } , none of whose vertices other than u u u is anterior to U U U .
(c) Let l l l be a vertex with an undirected edge. Then every edge of G U ∪ { l } G_{U \cup\{l\}} G U ∪ { l } that meets a vertex anterior to U U U has both of its endpoints anterior to U U U .
(d) Let l l l be a vertex without undirected edges that is not anterior to U ′ U' U ′ , and let U 1 , U 2 ⊆ U ′ U_1, U_2 \subseteq U' U 1 , U 2 ⊆ U ′ . If x m x_m x m is adjacent to l l l in G U m ∪ { l } G_{U_m \cup\{l\}} G U m ∪ { l } for m = 1 , 2 m = 1, 2 m = 1 , 2 , then x 1 = x 2 x_1 = x_2 x 1 = x 2 or x 1 x_1 x 1 is adjacent to x 2 x_2 x 2 in G U ′ ∪ { l } G_{U' \cup\{l\}} G U ′ ∪ { l } .
Proof. (a) The vertices anterior to U ′ ′ U'' U ′′ are anterior to U ′ U' U ′ , and a path through the former is a path through the latter, so every edge of G U ′ ′ G_{U''} G U ′′ is an edge of G U ′ G_{U'} G U ′ .
(b) Let ρ \rho ρ be a path from u u u to v v v in G G G through vertices anterior to U ′ U' U ′ on which every interior vertex is a collider. Some vertex of ρ \rho ρ is not anterior to U U U , since u v uv uv is not an edge of G U G_U G U . Let w w w be the first one. As w w w is anterior to U ′ U' U ′ , it is the first vertex of a path that ends in U ′ U' U ′ with edges undirected or directed towards that end. Let b b b be the first vertex of U ′ U' U ′ on this path, possibly w w w itself. No vertex between w w w and b b b on this path is anterior to U U U , because w w w is not.
The vertices u u u and w w w are adjacent in G U ∪ { b } G_{U \cup\{b\}} G U ∪ { b } , since the part of ρ \rho ρ between them passes through vertices anterior to U U U . Consecutive vertices of the path from w w w to b b b are adjacent in G G G and anterior to b b b , hence adjacent in G U ∪ { b } G_{U \cup\{b\}} G U ∪ { b } . Together they form the required path from u u u to b b b .
(c) Suppose that some edge of G U ∪ { l } G_{U \cup\{l\}} G U ∪ { l } joins a vertex anterior to U U U to one that is not, and let ρ \rho ρ be a corresponding path in G G G between these two vertices. Let w w w be the first vertex of ρ \rho ρ that is not anterior to U U U and y y y the vertex before it. The edge between y y y and w w w is neither undirected nor directed from w w w to y y y , as w w w would be anterior to U U U . It therefore has an arrowhead at w w w , and w w w has no undirected edge. Since w w w is anterior to U ∪ { l } U \cup\{l\} U ∪ { l } but not to U U U , it is anterior to l l l . Then w = l w = l w = l or a directed path leads from w w w to l l l . In both cases l l l has an arrowhead, which an ancestral graph forbids for a vertex with an undirected edge.
(d) For m = 1 , 2 m = 1, 2 m = 1 , 2 let ρ m \rho_m ρ m be a path from x m x_m x m to l l l in G G G through vertices anterior to U m ∪ { l } U_m \cup\{l\} U m ∪ { l } on which every interior vertex is a collider. Its last edge has an arrowhead at l l l . Indeed, it is not undirected, and if it were directed away from l l l its other vertex would be a child of l l l anterior to U m ∪ { l } U_m \cup\{l\} U m ∪ { l } . This child is not anterior to U m U_m U m , as l l l would then be anterior to U ′ U' U ′ . So it is anterior to l l l and has an arrowhead. A directed path from it to l l l then closes a directed cycle.
Let x 1 ≠ x 2 x_1 \ne x_2 x 1 = x 2 and let y y y be the first vertex of ρ 1 \rho_1 ρ 1 that lies on ρ 2 \rho_2 ρ 2 . Follow ρ 1 \rho_1 ρ 1 from x 1 x_1 x 1 to y y y and then ρ 2 \rho_2 ρ 2 from y y y to x 2 x_2 x 2 . This is a path through vertices anterior to U ′ ∪ { l } U' \cup\{l\} U ′ ∪ { l } . Each of its interior vertices other than y y y is a collider on ρ 1 \rho_1 ρ 1 or on ρ 2 \rho_2 ρ 2 . If y y y is an interior vertex, its two edges on the new path have arrowheads at y y y , because y y y equals l l l or is a collider on the path concerned. Hence x 1 x_1 x 1 and x 2 x_2 x 2 are adjacent in G U ′ ∪ { l } G_{U' \cup\{l\}} G U ′ ∪ { l } . □
For a statement t = ( a b ∣ B ) t=(ab \mid B) t = ( ab ∣ B ) let Γ t \Gamma_t Γ t be the graph obtained from G t + P t G_t + P_t G t + P t by deleting the vertices of B ∖ V ( P t ) B \setminus V(P_t) B ∖ V ( P t ) . Then t ∈ I ( G ) t \in\mathcal{I}(G) t ∈ I ( G ) exactly when a a a and b b b lie in different connected components of Γ t \Gamma_t Γ t . If every index of t t t occurs in a statement u u u , then P t ⊆ P u P_t \subseteq P_u P t ⊆ P u and G t G_t G t is a subgraph of G u G_u G u by Lemma 16(a).
Lemma 17. Let G G G be an ancestral graph and P P P a set of pairs.
(a) The set I ( G ) P \mathcal{I}(G)^P I ( G ) P is cancellation-free for every pair { k , l } \{k,l\} { k , l } .
(b) Let { k , l } ∉ P \{k,l\} \notin P { k , l } ∈ / P and P ′ = P ∪ { { k , l } } P' = P \cup\{\{k,l\}\} P ′ = P ∪ {{ k , l }} . A statement of I ( G ) P \mathcal{I}(G)^P I ( G ) P in which both k k k and l l l occur and that is screened in I ( G ) P \mathcal{I}(G)^P I ( G ) P belongs to I ( G ) P ′ \mathcal{I}(G)^{P'} I ( G ) P ′ .
Proof. (a) Let i , j , k , l i,j,k,l i , j , k , l be distinct and D ⊆ [ n ] ∖ { i , j , k , l } D \subseteq[n] \setminus\{i,j,k,l\} D ⊆ [ n ] ∖ { i , j , k , l } . Suppose that s 0 = ( i j ∣ D ) s_0=(ij\mid D) s 0 = ( ij ∣ D ) and s 2 = ( i j ∣ D ∪ { k , l } ) s_2=(ij\mid D\cup\{k,l\}) s 2 = ( ij ∣ D ∪ { k , l }) belong to I ( G ) P \mathcal{I}(G)^{P} I ( G ) P . For a ∈ { i , j } a\in\{i,j\} a ∈ { i , j } and b ∈ { k , l } b\in\{k,l\} b ∈ { k , l } put t a b = ( a b ∣ D ) t_{ab}=(ab\mid D) t ab = ( ab ∣ D ) . Assume that none of these four statements belongs to I ( G ) P \mathcal{I}(G)^{P} I ( G ) P , so that Γ t a b \Gamma_{t_{ab}} Γ t ab contains a path π a b \pi_{ab} π ab from a a a to b b b . We call b ∈ { k , l } b\in\{k,l\} b ∈ { k , l } paired if it belongs to a pair of P s 2 P_{s_2} P s 2 . A contradiction is reached in four steps.
Step 1. The vertices k k k and l l l are not both paired. Suppose they are. The vertices deleted in Γ s 2 \Gamma_{s_2} Γ s 2 are then those of D ∖ V ( P s 2 ) D\setminus V(P_{s_2}) D ∖ V ( P s 2 ) , and they are deleted in every Γ t a b \Gamma_{t_{ab}} Γ t ab . Hence Γ t a b \Gamma_{t_{ab}} Γ t ab is a subgraph of Γ s 2 \Gamma_{s_2} Γ s 2 , in which π i k \pi_{ik} π ik and π j k \pi_{jk} π j k join i i i to j j j , contrary to the assumption s 2 ∈ I ( G ) P s_2\in\mathcal{I}(G)^{P} s 2 ∈ I ( G ) P .
Step 2. An unpaired vertex b b b is not anterior to D ∪ { i , j } D\cup\{i,j\} D ∪ { i , j } . The pairs of P t a b P_{t_{ab}} P t ab avoid b b b , so they belong to P s 0 P_{s_0} P s 0 . If b b b were anterior to D ∪ { i , j } D\cup\{i,j\} D ∪ { i , j } , the graph G t a b G_{t_{ab}} G t ab would be a subgraph of G s 0 G_{s_0} G s 0 by Lemma 16(a), and Γ t a b \Gamma_{t_{ab}} Γ t ab a subgraph of Γ s 0 \Gamma_{s_0} Γ s 0 . The paths π i b \pi_{ib} π ib and π j b \pi_{jb} π j b would join i i i to j j j in Γ s 0 \Gamma_{s_0} Γ s 0 , contrary to s 0 ∈ I ( G ) P s_0\in\mathcal{I}(G)^{P} s 0 ∈ I ( G ) P .
Step 3. For an unpaired vertex b b b some walk from i i i to j j j in G s 2 + P s 2 G_{s_2}+P_{s_2} G s 2 + P s 2 avoids b b b and D ∖ V ( P s 2 ) D\setminus V(P_{s_2}) D ∖ V ( P s 2 ) . The path π a b \pi_{ab} π ab starts at a vertex anterior to D ∪ { a } D\cup\{a\} D ∪ { a } and ends at b b b , which is not. The pairs of P t a b P_{t_{ab}} P t ab lie inside D ∪ { a } D\cup\{a\} D ∪ { a } , so some edge of π a b \pi_{ab} π ab is an edge of G t a b G_{t_{ab}} G t ab that leaves the vertices anterior to D ∪ { a } D\cup\{a\} D ∪ { a } . By Lemma 16(c) the vertex b b b has no undirected edge. Let x a x_a x a be the vertex before b b b on π a b \pi_{ab} π ab , which is adjacent to b b b in G t a b G_{t_{ab}} G t ab . By Lemma 16(d) the vertices x i x_i x i and x j x_j x j are equal or adjacent in G D ∪ { i , j , b } G_{D\cup\{i,j,b\}} G D ∪ { i , j , b } , a subgraph of G s 2 G_{s_2} G s 2 . Joined by this edge, the part of π i b \pi_{ib} π ib before b b b and that of π j b \pi_{jb} π j b form a walk ω b \omega_b ω b from i i i to j j j in G s 2 + P s 2 G_{s_2}+P_{s_2} G s 2 + P s 2 . It avoids b b b as well as the vertices of D ∖ V ( P s 2 ) D\setminus V(P_{s_2}) D ∖ V ( P s 2 ) .
Step 4. Conclusion. By Step 1 some b ∈ { k , l } b\in\{k,l\} b ∈ { k , l } is unpaired. If the other vertex of { k , l } \{k,l\} { k , l } is paired, ω b \omega_b ω b is a walk in Γ s 2 \Gamma_{s_2} Γ s 2 , a contradiction. Otherwise k k k and l l l are both unpaired. By Steps 2 and 3 neither is anterior to D ∪ { i , j } D\cup\{i,j\} D ∪ { i , j } or has an undirected edge. Since G G G has no directed cycle, at most one of them is anterior to the other. Say k k k is not anterior to l l l . Then k k k lies in neither G t i l G_{t_{il}} G t i l nor G t j l G_{t_{jl}} G t j l , so ω l \omega_l ω l avoids k k k and is a walk in Γ s 2 \Gamma_{s_2} Γ s 2 , again a contradiction.
(b) Let s = ( i j ∣ C ) s=(ij\mid C) s = ( ij ∣ C ) be screened by e e e , and put D = C ∖ { k , l } D=C\setminus\{k,l\} D = C ∖ { k , l } . We may assume e = i e=i e = i . Let T = { j , k , l } ∖ { i } T=\{j,k,l\}\setminus\{i\} T = { j , k , l } ∖ { i } and t a = ( i a ∣ D ) t_a=(ia\mid D) t a = ( ia ∣ D ) for a ∈ T a\in T a ∈ T . The indices that occur in s s s are those of { i } ∪ T ∪ D \{i\}\cup T\cup D { i } ∪ T ∪ D . The pairs of P ′ P' P ′ inside s s s are those of P s P_s P s together with { k , l } \{k,l\} { k , l } , so the separating set of s s s with respect to P ′ P' P ′ is the set D ∖ V ( P s ) D\setminus V(P_s) D ∖ V ( P s ) .
Let P 0 P_0 P 0 be the set of pairs of P P P inside D ∪ { i } D\cup\{i\} D ∪ { i } and Γ 0 \Gamma_0 Γ 0 the graph obtained from G D ∪ { i } + P 0 G_{D\cup\{i\}}+P_0 G D ∪ { i } + P 0 by deleting D ∖ V ( P 0 ) D\setminus V(P_0) D ∖ V ( P 0 ) . For every a ∈ T a\in T a ∈ T it is a subgraph of Γ t a \Gamma_{t_a} Γ t a , because P 0 ⊆ P t a P_0\subseteq P_{t_a} P 0 ⊆ P t a and G D ∪ { i } G_{D\cup\{i\}} G D ∪ { i } is a subgraph of G t a G_{t_a} G t a .
Suppose that s ∉ I ( G ) P ′ s\notin\mathcal{I}(G)^{P'} s ∈ / I ( G ) P ′ . Adding the edge { k , l } \{k,l\} { k , l } to G s + P s G_s+P_s G s + P s then gives a graph with a path π \pi π from i i i to j j j that avoids D ∖ V ( P s ) D\setminus V(P_s) D ∖ V ( P s ) . Let π 0 \pi_0 π 0 be the longest initial part of π \pi π that is a path in Γ 0 \Gamma_0 Γ 0 and contains no vertex of T T T . Let u u u be its last vertex and v v v the next vertex of π \pi π . We show that i i i is joined to some a ∈ T a\in T a ∈ T in Γ t a \Gamma_{t_a} Γ t a , which contradicts t a ∈ I ( G ) P t_a\in\mathcal{I}(G)^{P} t a ∈ I ( G ) P .
Case 1: u v uv uv is not an edge of G D ∪ { i } + P 0 G_{D\cup\{i\}}+P_0 G D ∪ { i } + P 0 . It is not the edge { k , l } \{k,l\} { k , l } , because u ∉ T u\notin T u ∈ / T . If it is a pair of P s P_s P s , then u ∈ D ∪ { i } u\in D\cup\{i\} u ∈ D ∪ { i } and v v v is some a ∈ T a\in T a ∈ T . The pair lies inside D ∪ { i , a } D\cup\{i,a\} D ∪ { i , a } , and π 0 \pi_0 π 0 followed by it joins i i i to a a a in Γ t a \Gamma_{t_a} Γ t a . Otherwise u v uv uv is an edge of G s G_s G s that is not an edge of G D ∪ { i } G_{D\cup\{i\}} G D ∪ { i } . Lemma 16(b) provides a vertex o o o of s s s that is not anterior to D ∪ { j } D\cup\{j\} D ∪ { j } , hence a ∈ T a\in T a ∈ T , and a path from u u u to a a a in G t a G_{t_a} G t a . Its vertices other than u u u are not anterior to D ∪ { j } D\cup\{j\} D ∪ { j } , so they lie neither in D D D nor on π 0 \pi_0 π 0 . Following π 0 \pi_0 π 0 and then this path, we join i i i to a a a in the graph Γ t a \Gamma_{t_a} Γ t a .
Case 2: u v uv uv is an edge of G D ∪ { i } + P 0 G_{D\cup\{i\}}+P_0 G D ∪ { i } + P 0 . By the choice of π 0 \pi_0 π 0 , either v ∈ T v\in T v ∈ T or v ∈ D ∖ V ( P 0 ) v\in D\setminus V(P_0) v ∈ D ∖ V ( P 0 ) . In the first case π 0 \pi_0 π 0 followed by u v uv uv joins i i i to v v v in Γ t v \Gamma_{t_v} Γ t v . In the second case v v v belongs to a pair of P s P_s P s , as π \pi π avoids D ∖ V ( P s ) D\setminus V(P_s) D ∖ V ( P s ) . The other vertex of this pair is not in D ∪ { i } D\cup\{i\} D ∪ { i } , so it is some a ∈ T a\in T a ∈ T . The pair lies inside D ∪ { i , a } D\cup\{i,a\} D ∪ { i , a } , hence v ∈ V ( P t a ) v\in V(P_{t_a}) v ∈ V ( P t a ) . Following π 0 \pi_0 π 0 , the edge u v uv uv and this pair, we join i i i to a a a in Γ t a \Gamma_{t_a} Γ t a . ∎
Proof of Theorem 14. We first prove the claim for a Markov matrix Σ \Sigma Σ . Let s = ( i j ∣ C ) ∈ I ( G ) P s=(ij\mid C)\in\mathcal{I}(G)^{P} s = ( ij ∣ C ) ∈ I ( G ) P and D = C ∖ V ( P s ) D=C\setminus V(P_s) D = C ∖ V ( P s ) . Let A A A consist of the indices of s s s outside D D D that lie in the connected component of i i i in Γ s \Gamma_s Γ s , and let B B B consist of the other indices of s s s outside D D D . Then i ∈ A i\in A i ∈ A and j ∈ B j\in B j ∈ B . For a ∈ A a\in A a ∈ A and b ∈ B b\in B b ∈ B the set D D D separates a a a from b b b in G s G_s G s , hence in its subgraph G D ∪ { a , b } G_{D\cup\{a,b\}} G D ∪ { a , b } , so that ( a b ∣ D ) ∈ I ( G ) (ab\mid D)\in\mathcal{I}(G) ( ab ∣ D ) ∈ I ( G ) by the criterion recalled in Section 4.3. Hence A ⊥ ⊥ B ∣ D A\mathbin{\perp\mkern-10mu\perp}B\mid D A ⊥ ⊥ B ∣ D holds for Σ \Sigma Σ and Σ A ∪ D , B ∪ D \Sigma_{A\cup D,B\cup D} Σ A ∪ D , B ∪ D has rank ∣ D ∣ |D| ∣ D ∣ .
A pair of P P P with both vertices in A ∪ B ∪ D A\cup B\cup D A ∪ B ∪ D belongs to P s P_s P s . Its vertices are adjacent in Γ s \Gamma_s Γ s , so both lie in A A A or both lie in B B B . The submatrix therefore contains no changed entry, and A ⊥ ⊥ B ∣ D A\perp\!\!\!\perp B\mid D A ⊥ ⊥ B ∣ D holds for Σ ′ \Sigma' Σ ′ . Since C = D ∪ ( A ∖ { i } ) ∪ ( B ∖ { j } ) C=D\cup(A\setminus\{i\})\cup(B\setminus\{j\}) C = D ∪ ( A ∖ { i }) ∪ ( B ∖ { j }) , the first property recalled in this appendix gives s ∈ [ [ Σ ′ ] ] s\in[[\Sigma']] s ∈ [[ Σ ′ ]] .
(a) Let Σ \Sigma Σ be faithful to G G G . We use induction on the number of pairs. For P = ∅ P=\varnothing P = ∅ the claim is the faithfulness of Σ \Sigma Σ , because I ( G ) ∅ = I ( G ) \mathcal{I}(G)^{\varnothing}=\mathcal{I}(G) I ( G ) ∅ = I ( G ) by the same criterion. Let P ′ = P ∪ { { k , l } } P'=P\cup\{\{k,l\}\} P ′ = P ∪ {{ k , l }} with { k , l } ∉ P \{k,l\}\notin P { k , l } ∈ / P , and let Σ 1 \Sigma_1 Σ 1 be obtained from Σ \Sigma Σ by a change of the covariances of P P P such that [ [ Σ 1 ] ] = I ( G ) P [[\Sigma_1]]=\mathcal{I}(G)^P [[ Σ 1 ]] = I ( G ) P . By Lemma 17(a) this set is cancellation-free for { k , l } \{k,l\} { k , l } . Proposition 7 then describes the structure of Σ 1 + τ ( E k l + E l k ) \Sigma_1+\tau(E_{kl}+E_{lk}) Σ 1 + τ ( E k l + E l k ) for generic admissible τ \tau τ . It consists of the statements of I ( G ) P \mathcal{I}(G)^P I ( G ) P that are untouched or screened. An untouched statement belongs to I ( G ) P ′ \mathcal{I}(G)^{P'} I ( G ) P ′ , since P P P and P ′ P' P ′ have the same pairs inside it. A screened one does so by Lemma 17(b). With the first claim, the structure is I ( G ) P ′ \mathcal{I}(G)^{P'} I ( G ) P ′ .
Consequently, for every statement s ∉ I ( G ) P ′ s\notin\mathcal{I}(G)^{P'} s ∈ / I ( G ) P ′ the minor a s a_s a s of the matrix perturbed at the pairs of P ′ P' P ′ is a non-zero polynomial in the sizes. Claim (a) for P ′ P' P ′ thus holds for generic sizes.
(b) Apply (a) to the statements ( i j ∣ C ) (ij\mid C) ( ij ∣ C ) with C = [ n ] ∖ { i , j } C=[n]\setminus\{i,j\} C = [ n ] ∖ { i , j } , for which P s = P P_s=P P s = P and G s = G a G_s=G^a G s = G a . The set C ∖ V ( P ) C\setminus V(P) C ∖ V ( P ) fails to separate i i i from j j j in G a + P G^a+P G a + P exactly when a path with interior in V ( P ) V(P) V ( P ) joins them, that is, when they are adjacent in ( G a + P ) V ( P ) (G^a+P)^{V(P)} ( G a + P ) V ( P ) . □ \square □