next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
GraphicalModels :: trekIdeal

trekIdeal -- the trek separation ideal of a mixed graph

Synopsis

Description

For mixed graphs, the ideal corresponding to all trek separation statements A,B,CA,CB (where A,B,CA,CB are disjoint lists of vertices of G) is generated by the r+1 x r+1 minors of the submatrix of the covariance matrix M = (s(i,j)), whose rows are in A, and whose columns are in B, and where r = #CA+#CB.

These ideals are described in more detail by Sullivant, Talaska and Draisma in "Trek Separation for Gaussian Graphical Models" Annals of Statistics 38 no.3 (2010) 1665--1685 and give all determinantal constraints on the covariance matrix of a Gaussian graphical model.

i1 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})

o1 = MixedGraph{Bigraph => Bigraph{a => {d}}   }
                                   d => {a}
                Digraph => Digraph{b => {c, d}}
                                   c => {d}
                                   d => {}
                Graph => Graph{}

o1 : MixedGraph
i2 : R = gaussianRing G

o2 = R

o2 : PolynomialRing
i3 : T = trekIdeal(R,G)

o3 = ideal (s   , s   , - s   s    + s   s   , - s   s    + s   s   , -
             a,b   a,c     a,c b,b    a,b b,c     a,c b,b    a,b b,c   
     ------------------------------------------------------------------------
     s   s    + s   s   , s   s    - s   s   )
      a,c b,c    a,b c,c   a,c b,d    a,b c,d

o3 : Ideal of R
i4 : ideal gens gb T

o4 = ideal (s   , s   )
             a,c   a,b

o4 : Ideal of R

For undirected graphs G, the trekIdeal(R,G) is the same as conditionalIndependenceIdeal(R,globalMarkov(G)). For directed graphs G, trekIdeal(R,G) is generally larger than conditionalIndependenceIdeal(R,globalMarkov(G)).

i5 : G = graph{{a,b},{b,c},{c,d},{a,d}}

o5 = Graph{a => {b, d}}
           b => {a, c}
           c => {b, d}
           d => {a, c}

o5 : Graph
i6 : R = gaussianRing G

o6 = R

o6 : PolynomialRing
i7 : T = trekIdeal(R,G);

o7 : Ideal of R
i8 : CI = conditionalIndependenceIdeal(R,globalMarkov(G));

o8 : Ideal of R
i9 : T == CI

o9 = true
i10 : H = digraph{{1,{4}},{2,{4}},{3,{4,5}},{4,{5}}}

o10 = Digraph{1 => {4}   }
              2 => {4}
              3 => {4, 5}
              4 => {5}
              5 => {}

o10 : Digraph
i11 : R = gaussianRing H

o11 = R

o11 : PolynomialRing
i12 : T = trekIdeal(R,H);

o12 : Ideal of R
i13 : CI = conditionalIndependenceIdeal(R,globalMarkov(H));

o13 : Ideal of R
i14 : T == CI

o14 = false

Caveat

trekSeparation is currently only implemented with mixedGraphs that have directed and bidirected edges.

See also

Ways to use trekIdeal :

  • trekIdeal(Ring,Digraph)
  • trekIdeal(Ring,Graph)
  • trekIdeal(Ring,MixedGraph)