based on mathematical work with Arvind Ayyer and Steven Klee

based on Sage trac#12536 with Nicolas Thiery

Construction of finite posets:

Posets can be constructed specifying the vertex set and cover relations.

Linear extensions:

Let us look at the uniform promotion graph, where there is an edge from $\pi$ to $\pi'$ labelled $i$ if $\pi' = \pi \partial_i$.

Now we consider the promotion graph, where we label an edge $\pi'=\pi \partial_i$ by $\pi_i^{-1}$.

Tsetlin library:

When $P$ is the anti-chain, that is the poset on $n$ vertices without any relations, then the promotion graph is the Tsetlin library. For the anti-chain all permutations are linear extensions (since there are no relations between the vertices). In the Tsetlin library there are operators which take a book on a shelf in position $i$ and places it at the end.

Transition matrix:

Now we go back to our previous example.

Feature we need (see Viviane Pons' talk?): eigenvalues and eigenvectors for matrices with entries that are multivariate polynomials!!

", line 1, in File "_sage_input_42.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("TS5laWdlbnZhbHVlcygp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/private/var/folders/nR/nRzFEby2FV8wW6eFUOQcgU+++TI/-Tmp-/tmp7at5Sl/___code___.py", line 2, in exec compile(u'M.eigenvalues()' + '\n', '', 'single') File "", line 1, in File "matrix2.pyx", line 5082, in sage.matrix.matrix2.Matrix.eigenvalues (sage/matrix/matrix2.c:26419) File "matrix2.pyx", line 1703, in sage.matrix.matrix2.Matrix.fcp (sage/matrix/matrix2.c:11093) File "polynomial_element.pyx", line 3013, in sage.rings.polynomial.polynomial_element.Polynomial.factor (sage/rings/polynomial/polynomial_element.c:22566) NotImplementedError }}} {{{id=16| M = M.change_ring(SR) M.eigenvalues() /// [-x0 - x1 - x2, -x0 - x2, -2*x0 - x1 - x2 - x3, -x0 - x1 - x2 - x3, 0] }}} {{{id=25| M.eigenvectors_left() /// [(-x0 - x1 - x2, [(1, (x1*x2 - x2*x3)/((x0 + x1)*x2 + (x0 + x1)*x3 + x0^2 + x0*x1), -x2/(x0 + x1), (x1*x2 - x2*x3)/((x0 + x1)*x2 + (x0 + x1)*x3 + x0^2 + x0*x1), -x2/(x0 + x1))], 1), (-x0 - x2, [(1, ((x1 - x2)*x3 + x0*x1 + x1^2)/((x0 + x1)*x2 + (x0 + x1)*x3 + x0^2 + 2*x0*x1 + x1^2), (x1 - x2)/(x0 + x1), -(x1*x2 + x2*x3)/(x0^2 + x0*x1 + x0*x2 + x0*x3), -((x0 + x1)*x2*x3 + x0*x2^2 + (x0^2 + x0*x1 + x1^2)*x2)/(x0^3 + 2*x0^2*x1 + x0*x1^2 + (x0^2 + x0*x1)*x2 + (x0^2 + x0*x1)*x3))], 1), (-2*x0 - x1 - x2 - x3, [(1, 1, -(x0 + x2 + x3)/(x0 + x1), 1, -(x0 + x2 + x3)/(x0 + x1))], 1), (-x0 - x1 - x2 - x3, [(1, x1/(x0 + x1), -(x2 + x3)/(x0 + x1), 0, -x2/(x0 + x1))], 1), (0, [(1, 1, 1, 1, 1)], 1)] }}} {{{id=26| M.eigenvectors_right() /// [(-x0 - x1 - x2, [(1, -(x0 + x1)/x1, 0, x0/x1, 0)], 1), (-x0 - x2, [(0, 1, x1/x3, -1, -x1/x3)], 1), (-2*x0 - x1 - x2 - x3, [(1, -(x0 + x1)/(x0 + x1 + x3), -(x0 + x3)/(x0 + x1 + x3), -((2*x0 + x1 + x2)*x3 + x0^2 + x0*x1 + x3^2)/((x0 + x1)*x2 + x2*x3), ((2*x0 + x1 + x2)*x3 + x0^2 + x0*x1 + x0*x2 + x3^2)/((x0 + x1)*x2 + x2*x3))], 1), (-x0 - x1 - x2 - x3, [(0, 1, -1, -1, 1)], 1), (0, [(1, (x0 + x1)/(x0 + x2), ((x0 + x1)*x2 + x0^2 + 2*x0*x1 + x1^2)/((x0 + x2)*x3 + x0^2 + 2*x0*x2 + x2^2), (x0^2 + x0*x1)/(x0*x2 + x2^2), (x0^3 + 2*x0^2*x1 + x0*x1^2 + (x0^2 + x0*x1)*x2)/(x0^2*x2 + 2*x0*x2^2 + x2^3 + (x0*x2 + x2^2)*x3))], 1)] }}} {{{id=27| for p in M.eigenvectors_right(): if p[0] == 0: print "Stationary distribution", [factor(i) for i in p[1][0]] print "Multiplicity", p[2] /// Stationary distribution [1, (x0 + x1)/(x0 + x2), (x0 + x1)*(x0 + x1 + x2)/((x0 + x2)*(x0 + x2 + x3)), (x0 + x1)*x0/((x0 + x2)*x2), (x0 + x1)*(x0 + x1 + x2)*x0/((x0 + x2)*(x0 + x2 + x3)*x2)] Multiplicity 1 }}}

We did find nice product formulas for the stationary distributions (using Maple!), which are the eigenvectors for the eigenvalues 0.

However, not all is lost for Sage ♥:

• Since Sage is open source, new features can be added.
• Thanks for Nicolas, Florent, Franco, ... there are great features regarding monoids in Sage.

Monoids:

{{{id=19| P = Poset(([1,2,3],[[1,2]]), linear_extension = True) P.show() /// }}} {{{id=24| L = P.linear_extensions() M = L.markov_chain_transition_matrix(labeling = 'source') M /// [-x0 - x1 x2 x2] [ x0 + x1 -x0 - x2 0] [ 0 x0 -x2] }}} {{{id=20| attach /Users/anne/Documents/tex/papers/poset/promotion_monoid.sage /// }}} {{{id=21| PM = PromotionMonoid(P) G = Rgraph(PM) view(G) /// }}}

This is an $\mathcal{R}$-trivial monoid. In fact, it turns out that this is always true when the poset $P$ is a rooted forest.

If not, the monoid is not $\mathcal{R}$-trivial.

{{{id=28| P = Poset(([1,2,3],[[1,2],[1,3]]), linear_extension = True) PM = PromotionMonoid(P) G = Rgraph(PM) view(G) /// }}} {{{id=37| /// }}}