# The $0$-Rook Monoid and its Representation Theory¶

Joel Gay and Florent Hivert

$\newcommand{\emptyw}{\varepsilon} \DeclareMathOperator{\code}{code} \DeclareMathOperator{\decode}{decode} \newcommand{\Z}{\mathbb{Z}} \newcommand{\un}[1]{\underline{#1}}$

## Rook vectors¶

A rook vector of size $n$ is encoded by a tuple whose element belongs to $\{0, \dots, n\}$ and such that each non zero integer appears at most one. The number of rook vector is $$\sum_{r=0}^n \binom{n}{r}^2 r!$$ ($r$ denotes the number of non zero entries).

In [1]:
# %load -s rook_number rook0.sage
@cached_function
def rook_number(n):
r"""
The number of rooks

EXAMPLES::

sage: [rook_number(i) for i in range(10)]
[1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114]
sage: rook_number(10)
234662231
sage: sum(c(10, k) for k in range(11))
234662231
"""
return sum(binomial(n, r)^2 * factorial(r) for r in range(n+1))

In [2]:
[rook_number(i) for i in range(10)]

Out[2]:
[1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114]

### Rook triangle¶

Count the rook according to the position of the first zero

Implementation using Lemma 3.28, page 19

In [3]:
# %load -s c rook0.sage
@cached_function
def c(n, k):
"""
Rook triangle : count the rook according to the position of the first zero

Alternative implementation using Lemma 3.28, page 19

EXAMPLES::

sage: [[c(n, k) for k in range(n+1)] for n in range(8)]
[[1],
[1, 1],
[3, 2, 2],
[13, 9, 6, 6],
[73, 52, 36, 24, 24],
[501, 365, 260, 180, 120, 120],
[4051, 3006, 2190, 1560, 1080, 720, 720],
[37633, 28357, 21042, 15330, 10920, 7560, 5040, 5040]]
"""
if k < 0 or k > n: return 0
if n == 0: return 1
return (c(n-1, k)*(n-k-1) + c(n-1, k-1)*k +
sum(c(n-1, k1) for k1 in range (k, n+1)))

In [4]:
[[c(n, k) for k in range(n+1)] for n in range(9)]

Out[4]:
[[1],
[1, 1],
[3, 2, 2],
[13, 9, 6, 6],
[73, 52, 36, 24, 24],
[501, 365, 260, 180, 120, 120],
[4051, 3006, 2190, 1560, 1080, 720, 720],
[37633, 28357, 21042, 15330, 10920, 7560, 5040, 5040],
[394353, 301064, 226856, 168336, 122640, 87360, 60480, 40320, 40320]]
In [5]:
# %load -s is_rook rook0.sage
def is_rook(r):
r"""
Test for rook

EXAMPLES::

sage: is_rook((0, 1, 4, 3, 2))
True
sage: is_rook((0, 1, 5, 3, 2))
True
sage: is_rook((0, 1, 6, 3, 2))
False
sage: is_rook((0, 1, 2, 3, 2))
False
sage: is_rook((0, -1, 2, 3, 0))
False
"""
n = len(r)
for i in r:
if not (0 <= i <= n):
return False
for i in range(1, n+1):
if r.count(i) > 1:
return False
return True

In [6]:
is_rook((0, 1, 4, 3, 2))

Out[6]:
True
In [7]:
is_rook((0, 1, 5, 3, 2))

Out[7]:
True
In [8]:
is_rook((0, 1, 6, 3, 2))

Out[8]:
False
In [9]:
is_rook((0, 1, 2, 3, 2))

Out[9]:
False
In [10]:
is_rook((0, -1, 2, 3, 0))

Out[10]:
False
In [ ]:


In [ ]:



We enumerate rook vector recursively as follows: from a rook of size $n-1$, we get a rook of size $n$ by

• either insert $n$ at any place
• either insert a $0$. To get each rook ony once, we choose to always insert before any other $0$.

Starting from the set of rooks of size $n-1$, one gets each rook of size $n$ exactly once.

In [11]:
# %load -s first_zero rook0.sage
def first_zero(r):
r"""
The position of the first zero

EXAMPLES::

sage: first_zero((1,2,0,2,0))
2

TESTS:

sage: for n in range(7):
....:     l = [first_zero(r) for r in rooks(n)]
....:     for k in range(n+1):
....:         assert(l.count(k) == c(n, k))
"""
if 0 in r:
return r.index(0)
else:
return len(r)

In [12]:
first_zero((1,2,0,2,0))

Out[12]:
2
In [ ]:


In [ ]:



Here is a function to generate rooks

In [13]:
def rooks_iter(n):
if n == 0:
yield ()
else:
for r in rooks(n-1):
for i in range(n):
yield r[:i]+(n,)+r[i:]
try:
fz = r.index(0)
except ValueError:
fz = n-1
for i in range(fz+1):
yield r[:i]+(0,)+r[i:]
def rooks(n):
return list(rooks_iter(n))

In [14]:
rooks(0)

Out[14]:
[()]
In [15]:
rooks(1)

Out[15]:
[(1,), (0,)]
In [16]:
rooks(2)

Out[16]:
[(2, 1), (1, 2), (0, 1), (1, 0), (2, 0), (0, 2), (0, 0)]
In [17]:
rooks(3)

Out[17]:
[(3, 2, 1),
(2, 3, 1),
(2, 1, 3),
(0, 2, 1),
(2, 0, 1),
(2, 1, 0),
(3, 1, 2),
(1, 3, 2),
(1, 2, 3),
(0, 1, 2),
(1, 0, 2),
(1, 2, 0),
(3, 0, 1),
(0, 3, 1),
(0, 1, 3),
(0, 0, 1),
(3, 1, 0),
(1, 3, 0),
(1, 0, 3),
(0, 1, 0),
(1, 0, 0),
(3, 2, 0),
(2, 3, 0),
(2, 0, 3),
(0, 2, 0),
(2, 0, 0),
(3, 0, 2),
(0, 3, 2),
(0, 2, 3),
(0, 0, 2),
(3, 0, 0),
(0, 3, 0),
(0, 0, 3),
(0, 0, 0)]

Let's perform some consistency test

In [18]:
for n in range(9):
assert(len(rooks(n)) == rook_number(n))

In [19]:
for n in range(7):
l = [first_zero(r) for r in rooks(n)]
for k in range(n+1):
assert(l.count(k) == c(n, k))

In [ ]:



## Rooks and $R$-Codes¶

In this section, we check the combinatorics of $R$-code and reduced word in $0$- and $1$-rook monoids The primary goal is to check that Definition 3.37, page 22 is correct.

### Function $m$ of Definition 3.16, page 16¶

To each word $\un{w}$ over $\Z$, we associate a nonnegative number $m(\un{w})$ defined recursively by: $m(\emptyw) = 0$ and for any word $\un{w}$ and any letter $d$, $$m(\un{w} d) := \begin{cases} -d & \text{if d\leq0\,;} \\ m(\un{w})+1 & \text{if 0<d\leq m(\un{w})+1\,;} \\ m(\un{w}) & \text{if d> m(\un{w})+1\,.} \end{cases}$$

In [20]:
# %load -s mcode_ref rook0.sage
def mcode_ref(c):
r"""
Fonction m (Definition 3.16, page 16)

EXAMPLES::

sage: mcode_ref((1, 2, 8, 3, 6, 4, 2, 7))
5
sage: mcode_ref((3, 6, 4, -4, 2, 9, 4, -3, 5, 2, 5, 3, 8))
6
sage: mcode_ref((3, 6, 4, -4, 2, 9, 4, -3))
3
sage: mcode_ref((0, 2, 1, -1, 1, 2, 5, 4))
4
"""
if not c:
return 0
d = c[-1]
if d <= 0:
return -d
mw = mcode_ref(c[:-1])
if d <= mw + 1:
return mw + 1
else:
return mw

In [21]:
mcode_ref((1, 2, 8, 3, 6, 4, 2, 7))

Out[21]:
5
In [22]:
mcode_ref((3, 6, 4, -4, 2, 9, 4, -3, 5, 2, 5, 3, 8))

Out[22]:
6
In [23]:
mcode_ref((3, 6, 4, -4, 2, 9, 4, -3))

Out[23]:
3
In [24]:
mcode_ref((0, 2, 1, -1, 1, 2, 5, 4))

Out[24]:
4

Here is a faster code. Warning ! it only agrees with the previous definition on rook vectors.

In [25]:
# %load -s mcode rook0.sage
def mcode(c):
r"""
Faster Implementation of m, only agree with m on codes

TESTS::

sage: for n in range(7):
....:     for c in codes(n):
....:         assert(mcode_ref(c) == mcode(c))
"""
n = len(c) + 1
k = 0
for i in range(1, n):
if c[-i] <= 0:
k = i
break
if k == 0:
return n-1
else :
k1 = -c[-k]
k2 = 0
for i in range(-k+1, 0):
if c[i] <= k1+k2+1:
k2 += 1
return k1 + k2

In [26]:
mcode((0, 1, 1, -1, 1, 2, 5, 4))

Out[26]:
4

### $R$-Codes¶

We now implement Definition 3.16, page 16:

A word on $\Z$ is an $R$-code if it can be obtained by the following recursive construction: the empty word $\emptyw$ is a code, and $\un{w}d$ is a code if $\un{w}$ is a code and $-m(\un{w}) \leq d \leq n$.

In [27]:
# %load -s is_code,code_iter,codes rook0.sage
def is_code(c):
r"""
Test for code (Definition 3.16, page 16)

EXAMPLES::

sage: is_code((0,))
True
sage: is_code((1,))
True
sage: is_code((2,))
False
sage: is_code((-1,))
False
sage: is_code((1, -1, -1))
True
sage: is_code((1, -1, -2))
False
"""
for i in range(0, len(c)):
if not -mcode(c[:i]) <= c[i] <= i+1:
return False
return True

def code_iter(n):
"""
Iterate on codes according to Definition 3.16, page 16

See codes for tests
"""
if n == 0:
yield ()
else:
for c in code_iter(n-1):
for i in range(n, -mcode(c)-1, -1):
yield c + (i,)

@cached_function
def codes(n):
"""
List of codes according to Definition 3.16, page 16

EXAMPLES::

sage: codes(1)
[(1,), (0,)]
sage: codes(2)
[(1, 2), (1, 1), (1, 0), (1, -1), (0, 2), (0, 1), (0, 0)]

TESTS::

sage: "|".join("".join(str(l) for l in w) for w in codes(3))
'123|122|121|120|12-1|12-2|113|112|111|110|11-1|11-2|103|102|101|100|1-13|1-12|1-11|1-10|1-1-1|023|022|021|020|013|012|011|010|01-1|003|002|001|000'
sage: for i in range(7):
....:     for c in codes(i): assert(is_code(c))
sage: for i in range(7): assert(len(codes(i)) == r(i))
"""
return list(code_iter(n))

In [28]:
is_code((0,))

Out[28]:
True
In [29]:
is_code((1,))

Out[29]:
True
In [30]:
is_code((2,))

Out[30]:
False
In [31]:
is_code((-1,))

Out[31]:
False
In [32]:
is_code((1, -1, -1))

Out[32]:
True
In [33]:
is_code((1, -1, -2))

Out[33]:
False
In [34]:
codes(1)

Out[34]:
[(1,), (0,)]
In [35]:
codes(2)

Out[35]:
[(1, 2), (1, 1), (1, 0), (1, -1), (0, 2), (0, 1), (0, 0)]
In [36]:
codes(3)

Out[36]:
[(1, 2, 3),
(1, 2, 2),
(1, 2, 1),
(1, 2, 0),
(1, 2, -1),
(1, 2, -2),
(1, 1, 3),
(1, 1, 2),
(1, 1, 1),
(1, 1, 0),
(1, 1, -1),
(1, 1, -2),
(1, 0, 3),
(1, 0, 2),
(1, 0, 1),
(1, 0, 0),
(1, -1, 3),
(1, -1, 2),
(1, -1, 1),
(1, -1, 0),
(1, -1, -1),
(0, 2, 3),
(0, 2, 2),
(0, 2, 1),
(0, 2, 0),
(0, 1, 3),
(0, 1, 2),
(0, 1, 1),
(0, 1, 0),
(0, 1, -1),
(0, 0, 3),
(0, 0, 2),
(0, 0, 1),
(0, 0, 0)]

Let's perform some consistency test

In [37]:
for i in range(7):
for c in codes(i): assert(is_code(c))

In [38]:
for i in range(7): assert(len(codes(i)) == rook_number(i))

In [39]:
for n in range(7):
for c in codes(n):
assert(mcode_ref(c) == mcode(c))

In [ ]:



### Encoding and decoding rooks¶

Definition 3.12, page 16:

For a rook $r$ of length $n$, we call the $R$-code of $r$ and denote $\code(r)$ the word of lenght $n$ on $\Z$ defined recursively by:

1. If $n=0$ then $\code(\emptyw) := \emptyw$.
2. Otherwise, if $n\in r$, then $r$ can be written uniquely $r=\un{b}n\un{e}$. Let $r':=\un{b}\un{e}$ (the subword of $r$ where the unique occurrence of $n$ is removed). Then $\code(r) := \code(r')\cdot (\ell(\un{b})+1)$.
3. Otherwise, $n\notin r$ and $r$ can be written uniquely $r=\un{b}0\un{e}$ with $0\notin \un{b}$. Let $r':=\un{b}\un{e}$ (the subword of $r$ where the first $0$ is removed). Then $\code(r) := \code(r')\cdot (-\ell(\un{b}))$.
In [40]:
# %load -s encode,decode rook0.sage
def encode(r):
r"""
Encode a rook (Definition 3.12, page 16)

EXAMPLES::

sage: encode((2, 0, 3, 0, 4))
(0, 1, 2, 4, -1)
sage: encode((0, 2, 4, 0, 1))
(1, 1, -1, 2, 0)

TESTS::

sage: for n in range(7):
....:     for c in codes(n):
....:         assert(c == encode(decode(c)))
"""
n = len(r)
r = list(r)
res = []
for i in range(n, 0, -1):
if i in r:
pos = r.index(i)
res.append(pos+1)
del r[pos]
else:
pos = r.index(0)
res.append(-pos)
del r[pos]
return tuple(res[::-1])

def decode(c):
r"""
Decode a code (Definition 3.23, page 18)

EXAMPLE::

sage: decode((1, 1, -1, 2, 0))
(0, 2, 4, 0, 1)
sage: decode((0, 1, 2, 4, -1))
(2, 0, 3, 0, 4)
"""
res = []
for i in range(len(c)):
if c[i] > 0:
res.insert(c[i]-1, i+1)
elif c[i] == 0:
res.insert(0, 0)
else:
res.insert(-c[i], 0)
return tuple(res)

In [41]:
encode((2, 0, 3, 0, 4))

Out[41]:
(0, 1, 2, 4, -1)
In [42]:
encode((0, 2, 4, 0, 1))

Out[42]:
(1, 1, -1, 2, 0)
In [43]:
for n in range(7):
for c in codes(n):
assert(c == encode(decode(c)))

In [44]:
decode((1, 1, -1, 2, 0))

Out[44]:
(0, 2, 4, 0, 1)
In [45]:
decode((0, 1, 2, 4, -1))

Out[45]:
(2, 0, 3, 0, 4)
In [ ]:



### Action on rooks¶

In [46]:
# %load -s act_rook,act_rook_w rook0.sage
def act_rook(r, i):
r"""
Right action on a rook (Definition 3.8, page 15)

EXAMPLES::

sage: act_rook((1, 2, 3), 1)
(2, 1, 3)
sage: act_rook((1, 2, 3), 2)
(1, 3, 2)
sage: act_rook((1, 2, 3), 0)
(0, 2, 3)
sage: act_rook((3, 1, 2), 0)
(0, 1, 2)
sage: act_rook((3, 1, 2), 1)
(3, 1, 2)
sage: act_rook((3, 1, 2), 2)
(3, 2, 1)
"""
if i == 0:
return (0,) + r[1:]
elif r[i-1] >= r[i]:
return r
else:
return r[:i-1]+(r[i], r[i-1])+r[i+1:]

def act_rook_w(r, w):
r"""
Right action of a word on a rook (Definition 3.8, page 15)

TESTS::

sage: for n in range(7):
....:     for c in codes(n):
....:         assert(act_rook_w(tuple(range(1, n+1)), code2word(c)) ==
....:                decode(c))
"""
for i in w:
r = act_rook(r, i)
return r

In [47]:
act_rook((1, 2, 3), 1)

Out[47]:
(2, 1, 3)
In [48]:
act_rook((1, 2, 3), 2)

Out[48]:
(1, 3, 2)
In [49]:
act_rook((1, 2, 3), 0)

Out[49]:
(0, 2, 3)
In [50]:
act_rook((3, 1, 2), 0)

Out[50]:
(0, 1, 2)
In [51]:
act_rook((3, 1, 2), 1)

Out[51]:
(3, 1, 2)
In [52]:
act_rook((3, 1, 2), 2)

Out[52]:
(3, 2, 1)
In [ ]:


In [ ]:



## Action on codes¶

In [53]:
# %load -s act_code,act_code_w rook0.sage
def act_code(c, t, print_rule = False):
r"""
Right action on a code (Definition 3.37, page 22)

EXAMPLES::

sage: act_code((1, 2, 3, 4, -2, 1, 2, 6, -4), 5)
(1, 2, 3, 4, -2, 1, 2, 6, -4)
"""
n = len(c)
if n == 1:
assert(t == 0)
return (0,)
cn = c[-1]
if cn >= 1:  # Pos
if t == cn:      # a
if print_rule: print "Pos.a",
return c
elif t == cn-1:  # b
if print_rule: print "Pos.b",
return c[:-1] + (cn-1,)
elif t < cn -1:  # c
if print_rule: print "Pos.c",
return act_code(c[:-1], t) + (cn,)
else:            # d
if print_rule: print "Pos.d",
return act_code(c[:-1], t-1) + (cn,)
else:        # Neg
i = -cn
if t == i:       # a
if print_rule: print "Neg.a",
return c
elif 0 < t < i:      # b
if print_rule: print "Neg.b",
return act_code(c[:-1], t) + (cn,)
elif t > i + 1:  # c
if print_rule: print "Neg.c",
return act_code(c[:-1], t-1) + (cn,)
elif t == 0:     # d
if print_rule: print "Neg.d",
return act_code_w(c[:-1], range(i)) + (0,)
else:            # e
if mcode(c[:-1]) == i:  # alpha
if print_rule: print "Neg.e.alpha",
return c
else:                   # beta
if print_rule: print "Neg.e.beta",
return c[:-1]+(-(i+1),)

def act_code_w(c, w):
r"""
Right action of a word on a code (Definition 3.37, page 22)

TESTS::

sage: for n in range(7):
....:     for c in codes(n):
....:          assert(decode(c) ==
....:                 act_rook_w(tuple(range(1, n+1)), code2word(c)))
"""
for i in w:
c = act_code(c, i)
return c

In [54]:
act_code((1, 2, 3, 4, -2, 1, 2, 6, -4), 5)

Out[54]:
(1, 2, 3, 4, -2, 1, 2, 6, -4)
In [ ]:



## Canonical word associated to a code¶

In [55]:
# %load -s code2word rook0.sage
def code2word(c):
r"""
Word associated to a code (Definition 3.33, page 21)

EXAMPLES::

sage: code2word((1, 1, -1, 2, 0))
[1, 2, 1, 0, 1, 3, 2, 4, 3, 2, 1, 0]
"""
res = []
for i, ci in enumerate(c):
if ci <= 0:
res.append(range(i, -1, -1)+range(1, -ci+1))
else:
res.append(range(i, ci-1, -1))
return flatten(res)

In [56]:
code2word((1, 1, -1, 2, 0))

Out[56]:
[1, 2, 1, 0, 1, 3, 2, 4, 3, 2, 1, 0]
In [57]:
decode((1, 1, -1, 2, 0)), act_rook_w((1, 2, 3, 4, 5), code2word((1, 1, -1, 2, 0)))

Out[57]:
((0, 2, 4, 0, 1), (0, 2, 4, 0, 1))
In [ ]:



Check that acting on the identity and decoding is the same

In [58]:
for n in range(7):
for c in codes(n):
assert(act_rook_w(tuple(range(1, n+1)), code2word(c)) == decode(c))


Check that acting on code and acting on rook commute

In [59]:
# %load -s check_act rook0.sage
def check_act(n, print_rule = False):
r"""
Check for Lemma 3.38, page 22 and Corollary 3.44, page 27

TESTS::

sage: for n in range(7): check_act(n)

sage: check_act(2, True)
Pos.c Code=(1, 2), i=0, w=[], r=(1, 2), r.i=(0, 2), c.i=(0, 2)
Pos.b Code=(1, 2), i=1, w=[], r=(1, 2), r.i=(2, 1), c.i=(1, 1)
Pos.b Code=(1, 1), i=0, w=[1], r=(2, 1), r.i=(0, 1), c.i=(1, 0)
Pos.a Code=(1, 1), i=1, w=[1], r=(2, 1), r.i=(2, 1), c.i=(1, 1)
Neg.a Code=(1, 0), i=0, w=[1, 0], r=(0, 1), r.i=(0, 1), c.i=(1, 0)
Neg.e.beta Code=(1, 0), i=1, w=[1, 0], r=(0, 1), r.i=(1, 0), c.i=(1, -1)
Neg.d Code=(1, -1), i=0, w=[1, 0, 1], r=(1, 0), r.i=(0, 0), c.i=(0, 0)
Neg.a Code=(1, -1), i=1, w=[1, 0, 1], r=(1, 0), r.i=(1, 0), c.i=(1, -1)
Pos.c Code=(0, 2), i=0, w=[0], r=(0, 2), r.i=(0, 2), c.i=(0, 2)
Pos.b Code=(0, 2), i=1, w=[0], r=(0, 2), r.i=(2, 0), c.i=(0, 1)
Pos.b Code=(0, 1), i=0, w=[0, 1], r=(2, 0), r.i=(0, 0), c.i=(0, 0)
Pos.a Code=(0, 1), i=1, w=[0, 1], r=(2, 0), r.i=(2, 0), c.i=(0, 1)
Neg.a Code=(0, 0), i=0, w=[0, 1, 0], r=(0, 0), r.i=(0, 0), c.i=(0, 0)
Neg.e.alpha Code=(0, 0), i=1, w=[0, 1, 0], r=(0, 0), r.i=(0, 0), c.i=(0, 0)

"""
for c in codes(n):
for i in range(n):
ac = act_code(c, i)
if print_rule:
print "Code=%s, i=%s, w=%s, r=%s, r.i=%s, c.i=%s"%(
c, i, code2word(c), decode(c),
act_rook(decode(c), i), act_code(c, i, True))
assert(is_code(ac))
assert(decode(ac) == act_rook(decode(c), i))

In [60]:
for n in range(7): check_act(n)

In [ ]:



We now check Example 3.50, page 28

In [61]:
c = (0, 1, 3, 2, 3, -2)
r = decode(c); r

Out[61]:
(2, 4, 0, 5, 0, 3)
In [62]:
act_code(c, 0)

Out[62]:
(0, 0, 3, 1, 3, 0)
In [63]:
decode(act_code(c, 0))

Out[63]:
(0, 4, 0, 5, 0, 3)
In [ ]:


In [ ]:



### Canonical words¶

In [64]:
# %load -s canonize,canonwords rook0.sage
def canonize(w):
r"""
Canonize a word

EXAMPLES::

sage: canonize([1, 0, 1, 0])
[0, 1, 0]
sage: canonize([1, 0, 1, 0, 2])
[0, 1, 0, 2]
sage: canonize([1, 0, 1, 2])
[1, 0, 1, 2]
sage: canonize([0, 1, 0, 1, 2])
[0, 1, 0, 2]
"""
n = max(w) + 1
res = act_code_w(tuple(range(1,n+1)), w)
return code2word(res)

def canonwords(n):
r"""
List of canonical words

EXAMPLES::

sage: canonwords(0)
[[]]
sage: canonwords(1)
[[], [0]]
sage: canonwords(2)
[[], [1], [1, 0], [1, 0, 1], [0], [0, 1], [0, 1, 0]]

TESTS::

sage: "|".join("".join(str(l) for l in w) for w in canonwords(3))
'|2|21|210|2101|21012|1|12|121|1210|12101|121012|10|102|1021|10210|101|1012|10121|101210|1012101|0|02|021|0210|01|012|0121|01210|012101|010|0102|01021|010210'
"""
return [code2word(c) for c in codes(n)]

In [65]:
canonize([1, 0, 1, 0])

Out[65]:
[0, 1, 0]
In [66]:
canonize([1, 0, 1, 0, 2])

Out[66]:
[0, 1, 0, 2]
In [67]:
canonize([1, 0, 1, 2])

Out[67]:
[1, 0, 1, 2]
In [68]:
canonize([0, 1, 0, 1, 2])

Out[68]:
[0, 1, 0, 2]
In [ ]:


In [69]:
canonwords(0)

Out[69]:
[[]]
In [70]:
canonwords(1)

Out[70]:
[[], [0]]
In [71]:
canonwords(2)

Out[71]:
[[], [1], [1, 0], [1, 0, 1], [0], [0, 1], [0, 1, 0]]
In [ ]:


In [ ]:



### The 0-Rook monoid¶

We can now compute the product in the $0$-Rook monoid

In [72]:
# %load -s prod_rook rook0.sage
def prod_rook(r1, r2):
r"""
Product in the 0-rook monoid

TESTS::

sage: for n in range(4):
....:     for r1, r2, r3 in cartesian_product(([rooks(n)]*3)):
....:         assert(prod_rook(r1, prod_rook(r2, r3)) ==
....:                prod_rook(prod_rook(r1, r2), r3))
"""
return act_rook_w(r1, code2word(encode(r2)))

In [73]:
prod_rook((0,2,1),(3,0,2))

Out[73]:
(2, 0, 1)

Let's check that it is associative:

In [74]:
for n in range(4):
for r1, r2, r3 in cartesian_product(([rooks(n)]*3)):
assert(prod_rook(r1, prod_rook(r2, r3)) == prod_rook(prod_rook(r1, r2), r3))

In [ ]:


In [75]:
# %load -s is_action_reduced rook0.sage
def is_action_reduced(w):
r"""
Test for action reduced word (Corollary 3.54, page 29)

EXAMPLES::

sage: is_action_reduced([1, 0])
True
sage: is_action_reduced([1, 1])
False
sage: is_action_reduced([1, 0, 1])
True
sage: is_action_reduced([0, 1, 0])
True
sage: is_action_reduced([1, 0, 1, 0])
True
sage: is_action_reduced([0, 1, 0, 1])
False

TESTS::

sage: for n in range(7):
....:     for c in codes(n):
....:         assert(is_action_reduced(code2word(c)))
"""
if not w:
return True
n = max(w) + 1
r = tuple(range(1, n+1))
for i in w:
newr = act_rook(r, i)
if newr == r:
return False
r = newr
return True

In [76]:
is_action_reduced([1, 0])

Out[76]:
True
In [77]:
is_action_reduced([1, 1])

Out[77]:
False
In [78]:
is_action_reduced([1, 0, 1])

Out[78]:
True
In [79]:
is_action_reduced([0, 1, 0])

Out[79]:
True
In [80]:
is_action_reduced([1, 0, 1, 0])

Out[80]:
True
In [81]:
is_action_reduced([0, 1, 0, 1])

Out[81]:
False
In [82]:
for n in range(7):
for c in codes(n):
assert(is_action_reduced(code2word(c)))

In [ ]:


In [ ]:



# The $0$-rook monoid¶

From now on, you need sage_semigroups to be installed.

In [83]:
import sage_semigroups

Monkey patching sage.misc.sage_unittest.InstanceTester.__init__
Monkey patching sage.misc.sage_unittest.IsMethod
Monkey patching sage.misc.sage_unittest.ReturnOnError
Monkey patching sage.misc.sage_unittest.TestMethodFromIs
Monkey patching sage.misc.sage_unittest._test_method_from_is
Monkey patching sage.misc.sage_unittest.is_method
Monkey patching sage.categories.aperiodic_semigroups.AperiodicSemigroups.ElementMethods
Monkey patching sage.categories.aperiodic_semigroups.AperiodicSemigroups.ParentMethods
Monkey patching sage.categories.character_ring_functor
Monkey patching sage.categories.examples.finite_h_trivial_monoids
Monkey patching sage.categories.examples.finite_semigroups.LeftRegularBand.__init__
Monkey patching sage.categories.finite_h_trivial_semigroups
Monkey patching sage.categories.finite_j_trivial_semigroups
Monkey patching sage.categories.finite_left_regular_bands
Monkey patching sage.categories.finite_semigroups.CharacterRings.WithRealizations
Monkey patching sage.categories.finite_semigroups.CharacterRings.WithRealizations.ParentMethods
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.CharacterRings
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ElementMethods
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.character_ring
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.green_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.group_of_regular_j_class
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.groups_of_regular_j_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.h_le_on_idempotents
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.h_poset_on_idempotents
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.index_of_regular_j_class
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.is_DA
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.is_DG
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.is_aperiodic
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.is_basic
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.is_l_trivial
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.is_r_trivial
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.j_class
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.j_class_idempotents
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.j_class_index
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.j_class_representative
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.j_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.j_classes_of_idempotents
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.j_lequal
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.j_poset
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.j_poset_on_regular_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.j_transversal
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.j_transversal_of_idempotents
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.l_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.lr_class
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.lr_class_of
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.lr_regular_class
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.lr_regular_class_module
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.r_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.regular_j_class
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.regular_j_class_semigroup_generators
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.regular_j_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.ParentMethods.regular_j_classes_keys
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.character_ring
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.green_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.group_of_regular_j_class
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.groups_of_regular_j_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.h_le_on_idempotents
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.h_poset_on_idempotents
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.index_of_regular_j_class
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.is_DA
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.is_DG
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.is_aperiodic
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.is_basic
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.is_l_trivial
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.is_r_trivial
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.j_class
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.j_class_idempotents
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.j_class_index
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.j_class_representative
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.j_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.j_classes_of_idempotents
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.j_lequal
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.j_poset
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.j_poset_on_regular_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.j_transversal
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.j_transversal_of_idempotents
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.l_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.lr_class
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.lr_class_of
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.lr_regular_class
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.lr_regular_class_module
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.r_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.regular_j_class
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.regular_j_class_semigroup_generators
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.regular_j_classes
Monkey patching sage.categories.finite_semigroups.FiniteSemigroups.parent_class.regular_j_classes_keys
Monkey patching sage_semigroups.categories.finite_semigroups.FiniteSemigroups.element_class.ideal
Monkey patching sage.categories.finite_semigroups.WithRealizations.ParentMethods
Monkey patching sage.categories.h_trivial_semigroups.HTrivialSemigroups.Finite
Monkey patching sage.categories.h_trivial_semigroups.HTrivialSemigroups.Finite_extra_super_categories
Monkey patching sage.categories.j_trivial_semigroups.JTrivialSemigroups.Finite
Monkey patching sage.categories.l_trivial_semigroups.Finite.ParentMethods
Monkey patching sage.categories.l_trivial_semigroups.LTrivialSemigroups.Finite
Monkey patching sage.categories.module_functor
Monkey patching sage.categories.monoids.Monoids.ParentMethods.submonoid
Monkey patching sage.categories.monoids.Monoids.parent_class.submonoid
Monkey patching sage.categories.r_trivial_semigroups.Finite.ParentMethods
Monkey patching sage.categories.r_trivial_semigroups.RTrivialSemigroups.Finite
Monkey patching sage.categories.r_trivial_semigroups.RTrivialSemigroups.example
Monkey patching sage.categories.semigroup_modules
Monkey patching sage.categories.semigroups.Semigroups.ParentMethods.cayley_graph_cached
Monkey patching sage.categories.semigroups.Semigroups.parent_class.cayley_graph_cached
Monkey patching sage.categories.set_with_action_functor
Monkey patching sage.categories.transformation_semigroups
Monkey patching sage.monoids.automatic_semigroup.AutomaticSemigroup.__init__
Monkey patching sage.monoids.bi_hecke_monoid
Monkey patching sage.monoids.catalog
Monkey patching sage.monoids.character_ring
Monkey patching sage.monoids.free_left_regular_band
Monkey patching sage.monoids.free_partially_commutative_left_regular_band
Monkey patching sage.monoids.free_semilattice
Monkey patching sage.monoids.j_trivial_monoids
Monkey patching sage.monoids.karnofsky_rhodes_expansion
Monkey patching sage.monoids.rees_matrix_monoid
Monkey patching sage.monoids.representations
Monkey patching sage.monoids.set_compositions_monoid
Monkey patching sage.monoids.set_partitions_monoid
Monkey patching sage.monoids.sign_vectors_monoid
Monkey patching sage.monoids.transition_monoid

Loading sage-semigroups and patching its features into Sage's library:


We finaly check that the monoid defined as function and the one using words are isomorphic

In [84]:
# %load -s Rook0 rook0.sage
def Rook0(n):
r"""
The 0-rook monoid

EXAMPLES::

sage: Mon = Rook0(4)
sage: Mon.fun((3,1,2,4))
3124

TESTS::

sage: TestSuite(Mon).run()
"""
rk  = rooks(n)
fun = FiniteSetMaps(rk, action="right")
gen = { i : fun.from_dict({r : act_rook(r, i) for r in rk}) for i in range(n) }
monoid = fun.submonoid(gen, category = Semigroups().JTrivial().Finite())

one = tuple(range(1, n+1))

# print a function by the image of the identity
def print_el(el):
return "".join(str(i) for i in el.lift()(one))
monoid.element_class._repr_ = print_el
monoid.element_class._latex_ = print_el
monoid.rename("Rook monoid of rank %s as functions"%n)

# retrieve an element from the image of the identity
dct = { el.lift()(one) : el for el in monoid }
monoid.fun = dct.get

return monoid

In [85]:
TestSuite(Rook0(4)).run(verbose=True)

running ._test_an_element() . . . pass
running ._test_aperiodic() . . . pass
running ._test_associativity() . . . pass
running ._test_cardinality() . . . pass
running ._test_category() . . . pass
running ._test_elements() . . .
Running the test suite of self.an_element()
running ._test_category() . . . pass
running ._test_eq() . . . pass
running ._test_new() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . pass
pass
running ._test_elements_eq_reflexive() . . . pass
running ._test_elements_eq_symmetric() . . . pass
running ._test_elements_eq_transitive() . . . pass
running ._test_elements_neq() . . . pass
running ._test_enumerated_set_contains() . . . pass
running ._test_enumerated_set_iter_cardinality() . . . pass
running ._test_enumerated_set_iter_list() . . . pass
running ._test_eq() . . . pass
running ._test_j_trivial() . . . pass
running ._test_new() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_one() . . . pass
running ._test_pickling() . . . pass
running ._test_prod() . . . pass
running ._test_r_trivial() . . . pass
running ._test_some_elements() . . . pass
running ._test_symbol() . . . pass

In [86]:
Mon = Rook0(4)
Mon.fun((3,1,2,4))

Out[86]:
3124
In [ ]:


In [ ]:



We check that the product of two functions is the same as the product computed previously by the reduced word and code algorithm:

In [103]:
# %load -s check_isom rook0.sage
def check_isom(n):
r"""
Checking for ismorphism

TESTS::

sage: for i in range(5): check_isom(i)
"""
Mon = Rook0(n)
one = tuple(range(1,n+1))
assert len(Mon) == len(rooks(n)), "Wrong cardinality"
for m1 in Mon:
m1v = m1.lift()(one)
for m2 in Mon:
m2v = m2.lift()(one)
assert (m1*m2).lift()(one) == prod_rook(m1v, m2v)

In [104]:
for i in range(5):
print "Checking %d"%(i)
check_isom(i)

Checking 0
Checking 1
Checking 2
Checking 3
Checking 4

In [ ]:



Using the $\mathcal(J)$-trivial monoid theory to compute the reprensentation theory of the $0$-rooks monoids:

In [89]:
n = 3; Mon = Rook0(n); one = tuple(range(1,n+1))

In [90]:
idm = sorted(Mon.idempotents(),
key=lambda x : x.lift()(one)[::-1])[::-1]
idm, Mon.cartan_matrix(idempotents=tuple(idm))

Out[90]:
(
[1 0 0 0 0 0 0 0]
[0 1 1 0 1 0 0 0]
[0 1 3 0 2 1 1 0]
[0 0 0 1 0 1 1 0]
[0 1 2 0 2 0 0 0]
[0 0 1 1 0 2 2 0]
[0 0 1 1 0 2 3 0]
[123, 023, 213, 003, 132, 032, 321, 000], [0 0 0 0 0 0 0 1]
)
In [91]:
latex(idm), latex(Mon.cartan_matrix(idempotents=tuple(idm)))

Out[91]:
(\left[123, 023, 213, 003, 132, 032, 321, 000\right],
\left(\begin{array}{rrrrrrrr}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 3 & 0 & 2 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\
0 & 1 & 2 & 0 & 2 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 2 & 2 & 0 \\
0 & 0 & 1 & 1 & 0 & 2 & 3 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
\end{array}\right))
In [92]:
Mon.quiver()

Out[92]:
In [ ]:



# $\mathcal{R}$-Order of the $0$-Rook Monoid¶

In [93]:
Rook0(2).cayley_graph(side="right").plot()

Out[93]:
In [113]:
Rook0(3).cayley_graph(side="right").plot()

Out[113]:
In [114]:
Gr = Rook0(3).cayley_graph(side="right")
Gr.remove_loops()
Gr.plot()

Out[114]:
In [115]:
# %load -s rook_lattice rook0.sage
def rook_lattice(n):
r"""
The right rook lattice

We take the monoid convention, where 1 is the largest element

Examples::

sage: rook_lattice(3).cardinality()
34
sage: rook_lattice(3).is_lattice()
True
sage: rl2 = rook_lattice(2)
sage: matrix([[1 if rl2.le(r1, r2) else 0
....:          for r1 in rooks(2)] for r2 in rooks(2)])
[1 1 1 1 1 1 1]
[0 1 1 1 0 0 1]
[0 0 1 1 0 0 1]
[0 0 0 1 0 0 1]
[0 0 0 0 1 1 1]
[0 0 0 0 0 1 1]
[0 0 0 0 0 0 1]

TESTS::

sage: TestSuite(rook_lattice(3)).run()
"""
one = tuple(range(1, n+1))
Gr = Rook0(n).cayley_graph(side="right")
Gr.remove_loops()
Gr.relabel(lambda f : f.lift()(one))
Gr = Gr.reverse()
return LatticePoset(Gr)

In [116]:
rook_lattice(3).plot()

Out[116]:
In [117]:
[rook_lattice(n).is_lattice() for n in range(6)]

Out[117]:
[True, True, True, True, True, True]
In [118]:
rl = rook_lattice(3)

In [119]:
rl2 = rook_lattice(2)
matrix([[1 if rl2.le(r1, r2) else 0
for r1 in rooks(2)] for r2 in rooks(2)])

Out[119]:
[1 0 1 1 0 0 1]
[1 1 1 1 1 1 1]
[0 0 1 1 0 0 1]
[0 0 0 1 0 0 1]
[0 0 0 0 1 0 1]
[0 0 0 0 1 1 1]
[0 0 0 0 0 0 1]

## rook triples¶

In [122]:
# %load -s support,Delta,inversion,Z,rook_triple rook0.sage
def support(r):
r"""
The support of a rook (Definition 4.6, page 33)

Examples::

sage: support([3,1,0,2])
frozenset({1, 2, 3})
sage: support((4,1,0,2))
frozenset({1, 2, 4})
"""
return frozenset(r) - frozenset({0})

@cached_function
def Delta(n):
r"""
The upper diagonal set

\Delta:=\{(b, a)\ \mid\ n\geq b>a>0\}

EXAMPLES::

sage: Delta(3)
frozenset({(2, 1), (3, 1), (3, 2)})
sage: Delta(4)
frozenset({(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)})
sage: Delta(frozenset({1, 3, 4}))
frozenset({(3, 1), (4, 1), (4, 3)})

sage: Delta(frozenset({1, 2, 3, 8}))
frozenset({(2, 1), (3, 1), (3, 2), (8, 1), (8, 2), (8, 3)})
"""
if isinstance(n, (int, Integer)):
return frozenset((b,a) for b in range(1, n+1) for a in range(1, b))
else:
S = sorted(list(n))
n = len(S)
S = [None] + S  # Delta uses 1 based indexes
return frozenset((S[i],S[j]) for (i,j) in Delta(n))

def inversion(r):
r"""
The inversion set of a rook (Definition 4.1, page 33)

EXAMPLES::

sage: inversion((3,1,0,2))
frozenset({(3, 1), (3, 2)})
sage: inversion((3,1,5,0,2))
frozenset({(3, 1), (3, 2), (5, 2)})
sage: inversion((3,1,5,0,2,4))
frozenset({(3, 1), (3, 2), (5, 2), (5, 4)})
"""
r = [x for x in r if x != 0]
res = [(r[j], r[i]) for i in range(len(r)) for j in range(i) if r[j] > r[i]]
return frozenset(res)

def Z(r):
r"""
The zero-after number of a rook (Definition 4.6, page 33)

EXAMPLES::

sage: Z((3,1,5,0,2))
{1: 1, 2: 0, 3: 1, 5: 1}
sage: Z((3,0,5,0,2))
{2: 0, 3: 2, 5: 1}
"""
S = support(r)
r = list(r)
res = dict()
for a in S:
i = r.index(a)
res[a] = r[i:].count(0)
return res

def rook_triple(r):
r"""
The rook triple associate to a rook (Definition 4.6, page 33)

EXAMPLES::

sage: rook_triple((2,0,5,4,0,0,1))
(frozenset({1, 2, 4, 5}),
frozenset({(2, 1), (4, 1), (5, 1), (5, 4)}),
{1: 0, 2: 3, 4: 2, 5: 2})
"""
return (support(r), inversion(r), Z(r))

In [123]:
rook_triple((2,0,5,4,0,0,1))

Out[123]:
(frozenset({1, 2, 4, 5}),
frozenset({(2, 1), (4, 1), (5, 1), (5, 4)}),
{1: 0, 2: 3, 4: 2, 5: 2})

## recovering a rook from its triple¶

In [125]:
# %load -s from_inversion,from_rook_triple rook0.sage
@cached_function
def from_inversion(S, inv):
r"""
A word from its support and inversion set

EXAMPLES::

sage: from_inversion( frozenset({1, 2, 4, 5}),
....:     frozenset({(2, 1), (4, 1), (5, 1), (5, 4)}))
[2, 5, 4, 1]

sage: from_inversion(frozenset([1, 2, 3]), frozenset([(3, 1)]))
Traceback (most recent call last):
...
TypeError: Digraph is not acyclic; there is no topological sort.

sage: from_inversion(frozenset({1, 2, 3, 8}),
....:                frozenset({(2, 1), (3, 1), (3, 2)}))
[3, 2, 1, 8]
"""
from sage.graphs.linearextensions import LinearExtensions
d = DiGraph()
for (b,a) in Delta(S):
assert a in S
assert b in S
if (b,a) in inv:
else:
return d.topological_sort()

def from_rook_triple((Sr, Ir, Zr), n):
r"""
Recovering a rook from its rook triple (Proposition 4.8, page 33)

EXAMPLE::

sage: from_rook_triple(
....:    (frozenset({1, 2, 4, 5}),
....:     frozenset({(2, 1), (4, 1), (5, 1), (5, 4)}),
....:     {1: 0, 2: 3, 4: 2, 5: 2}), 7)
(2, 0, 5, 4, 0, 0, 1)

TESTS::

sage: n = 5
sage: for r in rooks(n):
....:     assert r == from_rook_triple(rook_triple(r), n)
"""
res = []
oldZ = n-len(Sr)
for l in from_inversion(Sr, Ir):
assert Zr[l] <= oldZ
res.extend([0]*(oldZ-Zr[l]))
res.append(l)
oldZ = Zr[l]
res.extend([0]*oldZ)
return tuple(res)

In [126]:
from_rook_triple(
(frozenset({1, 2, 4, 5}),
frozenset({(2, 1), (4, 1), (5, 1), (5, 4)}),
{1: 0, 2: 3, 4: 2, 5: 2}), 7)

Out[126]:
(2, 0, 5, 4, 0, 0, 1)
In [128]:
for n in range(7):
for r in rooks(n):
assert r == from_rook_triple(rook_triple(r), n)


## Comparing two rooks¶

In [131]:
# %load -s leqI rook0.sage
def leqI(r, u):
r"""
Comparing rooks (Definition \reff{def-rook-order})

We check for Theorem 4.16, page 35::

sage: n = 4
sage: Mon = Rook0(n)
sage: rl = rook_lattice(n)
sage: for r1 in rooks(n):
....:     for r2 in rooks(n):
....:         assert leqI(r1, r2) == rl.le(r1, r2)
"""
(Su, Iu, Zu) = rook_triple(u)
(Sr, Ir, Zr) = rook_triple(r)
if not Sr.issubset(Su):
return False
for (b, a) in Iu:
if b in Sr and (b, a) not in Ir:
return False
for l in Sr:
if not Zu[l] <= Zr[l]:
return False
return True

In [132]:
for n in range(5):
Mon = Rook0(n)
rl = rook_lattice(n)
for r1 in rooks(n):
for r2 in rooks(n):
assert leqI(r1, r2) == rl.le(r1, r2)

In [142]:
# %load -s invdict,transitive_closure,max_compatible_set,min_dual_compatible_set,interS2 rook0.sage
def invdict(I):
r"""
Iversion as a dict

EXAMPLES::

sage: invdict(frozenset({(6,5), (4,3), (5,3), (6,3)}))
{4: {3}, 5: {3}, 6: {3, 5}}
"""
import collections
res = collections.defaultdict(set)
for (b, a) in I:
return dict(res)

def transitive_closure(I):
"""
Trasitive Closure:

EXAMPLES::

sage: transitive_closure(frozenset([(3,2), (2,1)]))
frozenset({(2, 1), (3, 1), (3, 2)})
sage: transitive_closure(frozenset([(4,3),(3,2), (2,1)]))
frozenset({(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)})
"""
return frozenset([(a,b) for (a,b,_) in
DiGraph(list(I)).transitive_closure().edges()])

def max_compatible_set(S, I):
"""
Maximal I-compatible set (Definition 4.12, page 34)

precondition: S is supposed transitively closed

EXAMPLES::

sage: max_compatible_set(frozenset({1,2,4,5}), frozenset({(4,3), (5,3)}))
frozenset({1, 2})
sage: max_compatible_set(frozenset({1,2,4,5,6}),
....:     frozenset({(6,5), (4,3), (5,3), (6,3)}))
frozenset({1, 2})
"""
I = invdict(I)
res = set()
for b in S:
if b not in I or I[b].issubset(S):
return frozenset(res)

def min_dual_compatible_set(S, I, n):
"""
Minimal I-compatible set (Definition 4.21, page 38)

precondition: S is supposed transitively closed

EXAMPLES::

sage: min_dual_compatible_set(frozenset({1,2,4,5}),
....:     frozenset({(4,3), (5,3)}), 5)
frozenset({1, 2, 3, 4, 5})
sage: min_dual_compatible_set(frozenset({5}),
....:     frozenset({(6,5), (4,3), (5,3), (6,3)}), 7)
frozenset({5, 7})
sage: min_dual_compatible_set(frozenset({3}),
....:     frozenset({(6,5), (4,3), (5,3), (6,3)}), 7)
frozenset({3, 7})
sage: min_dual_compatible_set(frozenset({2}),
....:     frozenset({(6,5), (4,3), (5,3), (6,3)}), 7)
frozenset({2, 3, 4, 5, 6, 7})
"""
res = set(S)
for a in S:
for b in range(a+1, n+1):
if (b, a) not in I:
return frozenset(res)

def interS2(I0, S):
r"""
Intersection of an inversion set and a support

EXAMPLES::

sage: interS2(frozenset([(2,1), (4,2), (3,2)]),
....:         frozenset([3,2]))
frozenset({(3, 2)})
sage: interS2(frozenset([(2,1), (4,2), (3,2)]),
....:         frozenset([3,2,1]))
frozenset({(2, 1), (3, 2)})
"""
I = set()
for (b, a) in I0:
if b in S and a in S:
return frozenset(I)

In [143]:
# %load -s inf rook0.sage
def inf(u, v):
"""
The inf of the rook lattice (Theorem 4.18, page 36)

EXAMPLES::

sage: inf((3,1,0,5,2), (2,1,5,3,4))
(0, 3, 2, 1, 0)

sage: inf((2,4,1,0), (2,1,3,4))
(2, 4, 1, 0)
sage: inf((2,4,1,0), (2,1,4,3))
(0, 2, 1, 0)
sage: inf((2,4,1,0), (3,1,4,2))
(4, 2, 1, 0)

TESTS::

sage: n = 4
sage: Mon = Rook0(n)
sage: rl = rook_lattice(n)
sage: for u in rooks(n):
....:     for v in rooks(n):
....:         assert inf(u, v) == rl.meet(u, v)
"""
n = len(u)
assert n == len(v)
(Su, Iu, Zu) = rook_triple(u)
(Sv, Iv, Zv) = rook_triple(v)
I0 = transitive_closure(Iu | Iv)
S = max_compatible_set(Su & Sv, I0)
I = interS2(I0, S)
Idict = invdict(I)
Z = dict()
for x in S:
Zx = max(Zu[x], Zv[x])
for i in Idict.get(x, []):
Zx = max(Zx, Zu.get(i, 0), Zv.get(i, 0))
Z[x] = Zx
return from_rook_triple((S, I, Z), n)

In [144]:
inf((3,1,0,5,2), (2,1,5,3,4))

Out[144]:
(0, 3, 2, 1, 0)
In [145]:
inf((2,4,1,0), (2,1,3,4))

Out[145]:
(2, 4, 1, 0)
In [146]:
inf((2,4,1,0), (2,1,4,3))

Out[146]:
(0, 2, 1, 0)
In [147]:
inf((2,4,1,0), (3,1,4,2))

Out[147]:
(4, 2, 1, 0)
In [148]:
n = 4
Mon = Rook0(n)
rl = rook_lattice(n)
for u in rooks(n):
for v in rooks(n):
assert inf(u, v) == rl.meet(u, v)

In [150]:
# %load -s inversion_set_bar,sup rook0.sage
def inversion_set_bar(Su, Iu):
r"""
Complement of an inversion set

EXAMPLES::

sage: inversion_set_bar(frozenset({4}),
....:     frozenset({(6,5), (4,3), (5,3), (6,3)}))
{(4, 1), (4, 2), (4, 3)}
"""
IBu = set(Delta(Su) - Iu)
for b in Su:
for a in range(1, b):
if a not in Su:
return IBu

def sup(u, v):
r"""
The sup of the rook lattice (Theorem 4.22, page 38)

EXAMPLES::

sage: sup((3,1,0,5,2), (2,1,5,3,4))
(1, 2, 3, 4, 5)

sage: sup((2,4,1,0), (2,1,3,4))
(2, 1, 3, 4)
sage: sup((2,4,1,0), (2,1,4,3))
(2, 1, 3, 4)
sage: sup((2,4,1,0), (3,1,4,2))
(3, 1, 2, 4)

TESTS::

sage: n = 4
sage: Mon = Rook0(n)
sage: rl = rook_lattice(n)
sage: for u in rooks(n):
....:     for v in rooks(n):
....:         assert sup(u, v) == rl.join(u, v)
"""
n = len(u)
assert n == len(v)
(Su, Iu, Zu) = rook_triple(u)
IBu = inversion_set_bar(Su, Iu)
(Sv, Iv, Zv) = rook_triple(v)
IBv = inversion_set_bar(Sv, Iv)
I0 = Delta(n) - transitive_closure(IBu | IBv)
S = min_dual_compatible_set(Su | Sv, I0, n)
I = interS2(I0, S)
Idict = invdict(I)
Z = dict()
for x in S:
Zx = min(n - len(S), Zu.get(x, n), Zv.get(x, n))
for i in frozenset(range(x)) - Idict.get(x, set()):
Zx = min(Zx, Zu.get(i, n))
Zx = min(Zx, Zv.get(i, n))
Z[x] = Zx
return from_rook_triple((S, I, Z), n)

In [151]:
sup((3,1,0,5,2), (2,1,5,3,4))

Out[151]:
(1, 2, 3, 4, 5)
In [152]:
sup((2,4,1,0), (2,1,3,4))

Out[152]:
(2, 1, 3, 4)
In [153]:
sup((2,4,1,0), (2,1,4,3))

Out[153]:
(2, 1, 3, 4)
In [154]:
sup((2,4,1,0), (3,1,4,2))

Out[154]:
(3, 1, 2, 4)
In [155]:
n = 4
Mon = Rook0(n)
rl = rook_lattice(n)
for u in rooks(n):
for v in rooks(n):
assert sup(u, v) == rl.join(u, v)

In [ ]: