Geometry of Discrete Copulas
Elisa Perronea , Liam Solusb , Caroline Uhlera

arXiv:1802.06969v1 [] 20 Feb 2018

a

Laboratory for Information and Decision Systems, and Institute for Data, Systems and
Society, Massachusetts Institute of Technology, Cambridge, MA, USA
b
KTH Royal Institute of Technology, Stockholm, Sweden

Abstract
Multivariate discrete distributions are fundamental to modeling. Discrete
copulas can be used to non-parametrically construct diverse multivariate
joint distributions over random variables from estimated univariate marginals.
While directly constructing high-dimensional copulas is in general challenging, there is a wealth of techniques for bootstrapping up from estimated
bivariate copulas. Thus, it is important to have a variety of methods for
selecting bivariate discrete copulas with desirable properties. In this paper,
we show that the families of ultramodular discrete copulas and their generalization to convex discrete quasi-copulas admit representations as polytopes,
thereby opening the door for computationally efficient techniques from linear optimization for copula selection. In doing so, we draw connections
to the prominent Birkhoff and alternating sign matrix polytope in discrete
geometry and also generalize some well-known results on these polytopes.
Keywords: Discrete (quasi-)copulas, ultramodularity, transportation
polytope, alternating sign matrix polytope, Birkhoff polytope.
1. Introduction
Multivariate discrete probability distributions with ordinal or interval
support are fundamental to a wide range of applications, including health
care, weather forecasting, and image analysis. While it is straightforward to
estimate univariate marginal distributions, it is often challenging to model
multivariate and high-dimensional joint distributions. Copulas (Durante
and Sempi, 2015; Nelsen, 2006) serve as a general toolbox for constructing multivariate distributions from the estimated univariate marginals and
Email addresses: eperrone@mit.edu (Elisa Perrone), solus@kth.se (Liam Solus),
cuhler@mit.edu (Caroline Uhler)
Preprint submitted to arXiv

February 21, 2018

can be equipped with different stochastic dependence properties such as exchangeability, positive/negative association, or tail dependence. Key to the
power of copulas is Sklar’s Theorem, which states that the joint distribution
function FX of any d-dimensional random vector X = (X1 , . . . , Xd ) ∈ Rd
with univariate margins FX1 , . . . , FXd , can be expressed as
FX (x1 , . . . , xd ) = C(FX1 (x1 ), . . . , FXd (xd )),
where the function C : Range(FX1 )×· · ·×Range(FXd ) −→ R is uniquely defined and known as d-dimensional copula (Sklar, 1959). In the case of purely
discrete random vectors, Sklar’s theorem identifies the discrete copulas.
Unfortunately constructing high-dimensional copulas has been a challenging task. A standard approach is to first construct bivariate copulas
and then bootstrap up to higher-dimensions (Aas et al., 2009; Bedford and
Cooke, 2002; Kirshner, 2008; Okhrin et al., 2013). Thus, it is important to
develop techniques for the selection of bivariate discrete copulas with different properties. For example, in the context of portfolio risk optimization
(Müller and Scarsini, 2001) and risk aversion (Müller and Scarsini, 2012), a
property known as ultramodularity is particularly desirable. In this paper,
we show that discrete copulas with properties such as ultramodularity admit
polytopal representations and thus the analysis of multivariate distributions
constructed from marginal data is amenable to techniques from convex geometry. Particularly, the geometric results in this paper open the door for
the use of efficient linear optimization methods in the selection of bivariate
ultramodular discrete copulas and their generalizations.
A (convex) polytope is a bounded convex body in Rn that consists of the
points (x1 , . . . , xn ) ∈ Rn satisfying finitely many affine inequalities
a1 x1 + a2 x2 + · · · + an xn ≤ b,

(1)

where a1 , . . . , an , b ∈ Rn . A collection of such inequalities is called an
H-representation of the associated polytope. The unique irredundant Hrepresentation of a polytope P is called its minimal H-representation. If
inequality (1) is included in the minimal H-representation of P , then the
points in P on which (1) achieves equality is the associated facet of P . Thus,
the size of the minimal H-representation of P is the number of facets of P .
Polytopes are fundamental objects in the field of linear optimization, where
a key goal is to decide if a polytope has a small minimal H-representation as
to more efficiently solve the associated linear programming problem. Consequently, if a family of discrete copulas can be represented as a polytope
with few facets, then we can use efficient linear optimization techniques to
identify multivariate distributions by way of their observed marginals.
2

The space of discrete copulas in the bivariate setting (i.e., d = 2) was
studied by Aguiló et al. (2008, 2010); Kolesarova et al. (2006); Mayor et al.
(2005); Mesiar (2005); Mordelová and Kolesárová (2007). The results of
these papers collectively demonstrate that the space of bivariate discrete
copulas constructed from marginal distributions with finite state spaces of
sizes p and q correspond to the points within a special polytope known
as the generalized Birkhoff polytope (Ziegler, 1995). Klement et al. (2011)
gave a functional characterization of ultramodular copulas. In this paper,
we use their characterization to identify the minimal H-representation of
ultramodular discrete copulas as a subpolytope of the generalized Birkhoff
polytope. The number of facets of this subpolytope is quadratic in p and q,
meaning that the polytope has relatively few facets in terms of its defining
parameters. This creates space for the use of efficient linear optimization
techniques in the selection of ultramodular discrete copulas.
Bivariate copulas admit an important generalization that in turn results
in a natural generalization of the generalized Birkhoff polytope. The bivariate copulas form a poset P with partial order ≺ defined as C ≺ C 0 whenever
C(u, v) < C 0 (u, v) for all (u, v) ∈ [0, 1]2 (Durante and Sempi, 2015). However, P fails to admit desirable categorical properties. In particular, P is
not a lattice, meaning that not all pairs of copulas, C and C 0 , have both a
least upper bound and greatest lower bound with respect to ≺. The family
of functions that complete P to a lattice under ≺ are known as quasi-copulas
(Nelsen and Flores, 2005), and in the case where p = q, the bivariate discrete quasi-copulas correspond to points within a polytope known as the
alternating sign matrix polytope (Striker, 2009). In this paper, we identify
the minimal H-representations for the family of discrete quasi-copulas with
p 6= q and the subfamily of discrete quasi-copulas with convex sections residing within. Notably, we generalize a theorem of Striker (2009, Theorem
3.3) by showing that the alternating transportation polytopes (Knight, 2009)
have minimal H-representations whose size is quadratic in p and q, a result
of independent interest in discrete geometry.
The remainder of this paper is organized as follows: In Section 2, we
provide basic definitions. In Section 3, we present our first main result
(Theorem 1), in which we show that the collection of ultramodular bivariate
discrete copulas is representable as a polytope, and we identify its minimal
H-representation. The statistical significance of this result is that it allows
rephrasing the problem of selecting an ultramodular bivariate discrete copulas as an efficient linear optimization problem. Similarly, the collection of
bivariate discrete quasi-copulas is also representable as a polytope generalizing the alternating sign matrix polytope. In Section 4, we give our second
3

main result (Theorem 3), in which we identify the minimal H-representation
of this polytope, thereby generalizing a result in discrete geometry (Striker,
2009). In addition, we identify the minimal H-representation of a subpolytope corresponding to the discrete quasicopulas with convex sections. In
Section 5, we analyze alternative representations of these polytopes; i.e.,
their sets of vertices. Finally, in Section 6, we show that the most extensive
generalization of bivariate discrete copulas in the statistical literature admits a characterization in terms of the most extensive generalization of the
Birkhoff polytope in the discrete geometry literature, thereby completely
unifying these two hierarchies. Collectively, these results provide new and
potentially useful geometric perspectives on important families of discrete
copulas and quasi-copulas and introduce previously unstudied polytopes
that may be of independent interest to researchers in discrete geometry.
2. Copulas and Quasi-copulas in Discrete Geometry
In this section, we present the statistical and geometric preliminaries we
will use throughout the paper. We first recall definitions and fundamental
results for copulas and quasi-copulas. We then explicitly define the polytopes
we will study in the remaining sections. The following defines bivariate
copulas by way of functional inequalities.
Definition 1. A function C : [0, 1]2 → [0, 1] is a copula if and only if
(C1) for every u ∈ [0, 1], C(u, 0) = C(0, u) = 0 and C(u, 1) = C(1, u) = u;
(C2) for every u1 , u2 , v1 , v2 ∈ [0, 1] s.t. u1 ≤ u2 , v1 ≤ v2 , it holds that
C(u1 , v1 ) + C(u2 , v2 ) ≥ C(u1 , v2 ) + C(u2 , v1 ).

(2)

Hence bivariate copulas are functions on the unit square that are uniform on
the boundary (C1), supermodular (C2), and that capture the joint dependence of random vectors. A (coordinatewise) section of a bivariate copula is
any function given by fixing one of the two variables. A copula is ultramodular if and only if all of its coordinatewise sections are convex functions (Klement et al., 2011, 2014). The following generalizes bivariate copulas:
Definition 2. (Genest et al., 1999) A function Q : [0, 1]2 → [0, 1] is a quasicopula if and only if it satisfies condition (C1) of Definition 1 and satisfies
(Q2) Q is increasing in each component.
(Q3) Q satisfies the 1-Lipschitz condition, i.e., ∀u1 , u2 , v1 , v2 ∈ [0, 1],
|Q(u2 , v2 ) − Q(u1 , v1 )| ≤ |u1 − v1 | + |u2 − v2 |.
4

Equivalently, Genest et al. (1999) show that bivariate quasi-copulas are functions that satisfy boundary condition (C1) and are supermodular on any
rectangle with at least one edge on the boundary of the unit square.
2.1. Polytopes for Copulas and Quasi-copulas
In the following,
for po∈ Z>0 we let [p] := {1, . . . , p}, hpi := {0, 1, . . . , p},
n
p−1
1
and Ip := 0, p , . . . , p , 1 . When the marginal state spaces of a discrete
(quasi)-copula Cp,q : Ip × Iq −→ [0, 1] are of sizes p and q, respectively, we
can then define it on the domain Ip × Iq . It follows that Cp,q is representable
with a (p + 1) × (q + 1) matrix C = [cij ], where cij := Cp,q (i/p, j/q). We
can then define the set of discrete copulas on Ip × Iq , denoted by DCp,q , to
be all matrices [cij ] ∈ R(p+1)×(q+1) satisfying the affine inequalities
(c1) c0j = 0, cpj = qj ; ci0 = 0, ciq =

i
p

(c2) cij + ci−1j−1 − cij−1 − ci−1j ≥ 0

for all i ∈ hpi, j ∈ hqi;
for all i ∈ [p], j ∈ [q].

Analogously, the polytope of discrete quasi-copulas on Ip × Iq is denoted by
DQp,q and it consists of all matrices [cij ] ∈ R(p+1)×(q+1) satisfying
(q1) c0j = 0, cpj = qj ; ci0 = 0, ciq =
(q2a) 0 ≤ ci+1j − cij ≤
(q2b) 0 ≤ cij+1 − cij ≤

1
p
1
q

i
p

for all i ∈ hpi, j ∈ hqi;

for all i ∈ hp − 1i, j ∈ [q];
for all i ∈ [p], j ∈ hq − 1i.

We now recall the definitions of some classically studied polytopes in
discrete geometry and show how they relate to the polytopes DCp,q and
DQp,q . Given two vectors u := (u1 , . . . , up ) ∈ Rp>0 and v := (v1 , . . . , vq ) ∈
Rq>0 , the transportation polytope T (u, v) is the convex polytope defined in
the pq variables xij for i ∈ [p] and j ∈ [q] satisfying
xij ≥ 0,

q
X

xih = ui ,

h=1

and

p
X

x`j = vj ,

`=1

for all i ∈ [p] and j ∈ [q]. The vectors u and v are called the margins
of T (u, v). Transportation polytopes capture a number of classically studied polytopes in combinatorics (De Loera and Kim, 2014). For example,
the pth Birkhoff polytope, denoted by Bp , is the transportation polytope
T (u, v) with u = v = (1, 1, . . . , 1)T ∈ Rp , and the p × q generalized Birkhoff
polytope, denoted by Bp,q , is the transportation polytope T (u, v) where
u = (q, q, . . . , q) ∈ Rp and v = (p, p, . . . , p) ∈ Rq .
Another combinatorially-well-studied polytope that contains Bp is given
by the convex hull of all alternating sign matrices, i.e., square matrices
5

with entries in {0,1,-1} such that the sum of each row and column is 1
and the nonzero entries in each row and column alternate in sign. Striker
(2009, Theorem 2.1) proved that this polytope, known as the alternating
sign matrix polytope and denoted by ASMp , is defined by
0≤

i
X
`=1

x`j ≤ 1,

0≤

j
X

xih ≤ 1,

n
X
i=1

h=1

xij = 1,

n
X

xij = 1,

j=1

for all i, `, j, h ∈ [n]. Given margins u ∈ Rp and v ∈ Rq , ASMp was
generalized to the alternating transportation polytope A(u, v) (Knight, 2009,
Chapter 5), consisting of all p × q matrices [xij ] ∈ Rp×q satisfying
Pp
Pq
(1)
`=1 x`j = vj ;
h=1 xih = ui for i ∈ [p] and j ∈ [q],
Pi
(2) 0 ≤ `=1 x`j ≤ vj for all i ∈ [p] and j ∈ [q],
P
(3) 0 ≤ jh=1 xih ≤ ui for all i ∈ [p] and j ∈ [q].

Analogous to the generalized Birkhoff polytope, we define the generalized
alternating sign matrix polytope, denoted ASMp,q , to be the alternating
transportation polytope A(u, v) with u = (q, q, . . . , q)T ∈ Rp and v =
(p, p, . . . , p)T ∈ Rq . As shown in Proposition 1, there is an (invertible) linear
transformation taking each discrete copula [cij ] ∈ R(p+1)×(q+1) to a matrix
[bij ] ∈ Bp,q and taking each discrete quasi-copula to a matrix in ASMp,q .
In the following result we show that this linear transformation, which is
well-known in the statistical literature, is also geometrically significant.
1
Bp,q are unimodularly equivaProposition 1. The polytopes DCp,q and pq
1
lent, as are the polytopes DQp,q and pq ASMp,q .

Proof. It can be seen that there is a linear map T : R(p+1)×(q+1) −→ Rp×q
for which T (cij ) := cij + ci−1j−1 − ci,j−1 − ci−1,j for all i ∈ [p] and j ∈ [q]
1
that takes a discrete copula to a matrix in pq
Bp,q . Similarly, the linear
1
map T takes a discrete quasi-copula to a matrix in pq
A(u, v). Using the
boundary condition (c1), the map T is then an invertible transformation on
Rp×q , and if we let eij denote the standard basis vectors for Rp×q ordered
lexicographically (i.e. eij < ekr if and only if i < k or i = k and j < r), then
we see that the matrix for the map T is lower triangular and has only ones
on the diagonal when the standard basis is chosen with the lexicographic
ordering on the columns and rows. Therefore, T is unimodular.
Remark 1. Proposition 1 shows that the geometry of Bp,q and ASMp,q
completely describes the geometry of the collection of discrete copulas and
6

discrete quasi-copulas, respectively. In particular, DCp,q and Bp,q have the
same facial structure, and similarly for DQp,q and ASMp,q . In addition, for
any subpolytopes P ⊂ DCp,q and Q ⊂ DQp,q the subpolytopes T (P ) ⊂ Bp,q
and T (Q) ⊂ ASMp,q have the same facial structure, respectively.
The polytope of ultramodular discrete copulas is the subpolytope UDCp,q ⊂
DCp,q satisfying the additional constraints
2cij ≤ ci−1j + ci+1j

and

2cij ≤ cij−1 + cij+1 ,

(3)

for all i ∈ [p − 1] and j ∈ [q − 1]. These constraints correspond to convexity
conditions imposed on the associated copulas, and so we can naturally define
a similar subpolytope of DQp,q . The polytope of convex discrete quasi-copulas
is the subpolytope CDQp,q ⊂ DQp,q satisfying the above constraints (3). Via
the transformation T , we will equivalently study the polytopes UDC p,q :=
pqT (UDCp,q ) ⊂ Bp,q and CDQp,q := pqT (CDQp,q ) ⊂ ASMp,q . We end this
section with a second geometric remark.
Remark 2. It is well known that the generalized Birkhoff polytope Bp,q has
dimension (p − 1)(q − 1) (see (De Loera and
2014) for instance).
This
PKim,
Pq
p
is because each of the defining equalities i=1 xij = p and j=1 xij = q
determine precisely one more entry of the matrix. In a similar fashion, the
polytopes UDC p,q , ASMp,q , and CDQp,q and also the polytopes of discrete
(quasi)-copulas DCp,q , UDCp,q , DQp,q , and CDQp,q studied in this paper all
have dimension (p − 1)(q − 1).
3. The Polytope of Ultramodular Discrete Copulas
In our first main theorem we identify the minimal H-represesentation of
the polytope of ultramodular discrete copulas UDCp,q .
Theorem 1. The minimal H-representation of the polytope of ultramodular
discrete copulas UDCp,q consists of the (p − 2)(q − 2) + 2(p − 1)(q − 1)
inequalities:
(d1) x11 ≥ 0, and xp−1q−1 ≥

(p−1)(q−1)−1
,
pq

(d2) xij + xi+1j+1 − xij+1 − xi+1j ≥ 0

for all i ∈ [p − 2], j ∈ [q − 2] with

(i, j) ∈
/ {(1, 1), (p − 2, q − 2)},
(d3a) xij + xij+2 − 2 xij+1 ≥ 0

for all i ∈ [p − 1], j ∈ hq − 2i,

(d3b) xij + xi+2j − 2 xi+1j ≥ 0

for all j ∈ [q − 1], i ∈ hp − 2i.
7

c00

c01 c02 c03 c04 c05 c06

c07

d1

c10

c17
d2

d2

d2

d2

c20

c27
d2

d2

d2

d2

d2

d2

d2

d2

d2

c30

c37

c40

c47
d1

c50

c51 c52 c53 c54 c55 c56

c57

Figure 1: A depiction of the inequalities for the minimal H-representation of UDC5,7 . The
rectangles represent the necessary supermodularity constraints (C2), while the square dots
represent the convexity contraints (3).

Figure 1 gives a diagrammatic depiction of the inequalities constituting
the minimal H-representation of UDCp,q . An equivalent statement to Theorem 1 is that the subpolytope UDC p,q of the generalized Birkhoff polytope
Bp,q has minimal H-representation given by the inequalities
(b1) x11 ≥ 0, and xpq ≥ 0,
(b2) xi+1j+1 ≥ 0 for all i ∈ [p − 2], j ∈ [q − 2] with
(i, j) ∈
/ {(1, 1), (p − 2, q − 2)},
(b3a)

i
P

x`j+1 ≥

`=1

(b3b)

j
P

h=1

i
P

x`j for all i ∈ [p − 1], j ∈ [q − 1],

`=1

xi+1h ≥

j
P

xih for all i ∈ [p − 1], j ∈ [q − 1].

h=1

To prove that the inequalities (d1), (d2), (d3a), and (d3b) constitute the
minimal H-representation of UDCp,q , we first demonstrate that if [cij ] ∈
R(p+1)×(q+1) satisfies the boundary condition (c1) and all of (d1), (d2), (d3a),
and (d3b), then [cij ] ∈ UDCp,q . This is proven in Lemma 9 in the Appendix.
Then we show that for each inequality in the list (d1), (d2), (d3a), and (d3b)
there exists a point [cij ] ∈ R(p+1)×(q+1) failing to satisfy this inequality that
satisfies all the other inequalities. We do this by proving the analogous fact
for the subpolytope UDC p,q of Bp,q . Since the details of this argument are
technical, the complete proof is given in the Appendix.
In the following theorem and remark we show that every point in UDCp,q
can be realized as a restriction of some ultramodular bivariate copula on
8

[0, 1]2 and that any restriction of an ultramodular discrete copula is in fact
a point in UDCp,q . In particular, any point in UDCp,q can be extended to an
ultramodular copula on [0, 1]2 known as the checkerboard extension copula
(Nelsen, 2006). The proof of Theorem 2 is given in the Appendix.
Theorem 2. Given p, q ∈ Z>0 , the checkerboard extension copula of any
[cij ] ∈ UDCp,q is an ultramodular copula on the unit square.
Remark 3. The restriction C of any ultramodular copula C̃ on a nonsquare uniform grid Ip × Iq of the unit square belongs to UDCp,q . Indeed,
let us consider a copula C̃ that is ultramodular. Then the restriction C
of C̃ to the interval Ip × Iq is a discrete copula (Kolesarova et al., 2006;
Nelsen, 2006). Therefore, C belongs to DCp,q and satisfies (d1), (d2), and
(d3). Since C̃ is ultramodular, all of its horizontal and vertical sections are
univariate continuous convex functions that fulfill the Jensen inequality; i.e.,
for every u1 , u2 ∈ [0, 1], and a ∈ [0, 1]

C̃ u21 + u22 , a ≤ 12 C̃(u1 , a) + 21 C̃(u2 , a).

Inequalities (d3b) can be derived by fixing a = qj , while u1 = pi , u2 = i+2
p
for j ∈ [q − 1] and i ∈ hp − 2i. In an analogous manner, one can obtain
conditions (d3a). Hence, C ∈ UDCp,q .

Theorem 2 and Remark 3 also provide a statistical interpretation for
the polytope UDC p,q . In particular, they identify a correspondence between
1
each point in UDC p,q , normalized with a multiplicative factor pq
, and the
2
probability mass of an ultramodular bivariate copula on [0, 1] , which can
be constructed via checkerboard extension techniques. This is interesting
from a statistical perspective as the checkerboard extension copula plays an
important role in characterizing dependence among discrete random vectors and is at the base of the empirical multilinear copula process recently
introduced by Genest et al. (2014, 2017).
4. Polytopes of (Convex) Discrete Quasi-copulas
In this section, we identify the minimal H-representations for the polytope of discrete quasi-copulas DQp,q and its subpolytope of convex discrete
quasi-copulas CDQp,q . Recall from Proposition 1 that DQp,q is unimodularly
equivalent to a dilation of the generalized alternating sign matrix polytope
ASMp,q , which was originally studied in (Knight, 2009, Chapter 5). However, while the minimal H-representation for the case p = q (i.e., for the
9

polytope ASMp ) was identified in (Striker, 2009, Theorem 3.3), it was unknown for p 6= q. In this section, we identify the minimal H-representation
for ASMp,q (and hence also for DQp,q ) and also for the polytope CDQp,q .
It is shown in (Striker, 2009, Theorem 3.3) that for p ≥ 3 the polytope
ASMp has 4[(p − 2)2 + 1] facets given by the inequalities
(1) x11 ≥ 0, x1p ≥ 0, xp1 ≥ 0, and xpp ≥ 0;
Pp
Pi−1
(2)
k=1 xkj ≥ 0, and
k=i+1 xkj ≥ 0 for i, j ∈ {2, . . . , p − 1};
Pj−1
Pp
(3)
h=1 xih ≥ 0, and
h=j+1 xih ≥ 0 for i, j ∈ {2, . . . , p − 1}.

Suppose now that 3 ≤p < q and that q = kp + r for 0 ≤ r < p.Our second
main theorem of the paper generalizes Theorem 3.3 of Striker (2009).
Theorem 3. Suppose 3 ≤ p < q with q = kp+r for 0 ≤ r < p. The minimal
H-representation of the generalized alternating sign matrix polytope ASMp,q
consists of the 2((p − 1)(q − 2) + 2) + 2(p − 2)(q − k − 1) inequalities
(a1) x11 ≥ 0, x1q ≥ 0, xp1 ≥ 0, and xpq ≥ 0;
Pp
Pi−1
(a2)
`=1 x`j ≥ 0,
`=i+1 x`j ≥ 0 for i ∈ [p − 1], j ∈ {2, . . . , q − 1};
Pp
Pj−1
(a3)
h=j+1 xih ≥ 0 for i ∈ {2, . . . , p − 1}, j ∈ [q − k − 1].
h=1 xih ≥ 0,

To proof is given in the Appendix and is analogous to the approach
taken for proving Theorem 1. The natural functional generalization of ultramodular discrete copulas to the setting of quasi-copulas are convex discrete
quasi-copulas; i.e., discrete quasi-copulas admitting convex (coordinatewise)
sections. These functions are parametrized by the points [cij ] within the
polytope CDQp,q , which has the following H-representation:
Theorem 4. The minimal H-representation of the polytope of convex discrete quasi-copulas CDQp,q consists of the 2[(p − 1)(q − 1) + 1] inequalities
(v1) x11 ≥ 0,

xp−1q−1 ≥

(p−1)(q−1)−1
;
pq

(v3a) xi,j + xij+2 − 2 xij+1 ≥ 0

for all i ∈ [p − 1], j ∈ hq − 2i;

(v3b) xi,j + xi+2j − 2 xi+1j ≥ 0

for all j ∈ [q − 1], i ∈ hp − 2i.

The proof is again analogous to the proof of Theorem 1, and is given in
the Appendix. In particular, in the proof we show that the unimodularly
equivalent subpolytope CDQp,q of ASMp,q has minimal H-representation
(a1) x11 ≥ 0,

xpq ≥ 0;

10

(a3a)

i
P

x`j+1 ≥

j
P

h=1

x`j for all i ∈ [p − 1], j ∈ [q − 1];

`=1

`=1

(a3b)

i
P

xi+1h ≥

j
P

xih for all i ∈ [p − 1], j ∈ [q − 1].

h=1

Since convex discrete quasi-copulas are the natural generalization of ultramodular discrete copulas to the quasi-copula setting, we would hope that
the points [cij ] ∈ CDQp,q are, analogously, the family of points that can be
extended to convex quasi-copulas on [0, 1]2 . Indeed, this is the case:
Theorem 5. Given p, q ∈ Z>0 , the checkerboard extension of any [cij ] ∈
CDQp,q is a quasi-copula on [0, 1]2 with convex (coordinatewise) sections.
Remark 4. Following the same considerations as in Remark 3, one can
notice that the restriction C of any quasi-copula C̃ on a non-square uniform
grid Ip × Iq of the unit square belongs to CDQp,q .
Analogous to the case of ultramodular copulas, it is useful to notice that
Theorem 5 and Remark 4 identify a correspondence between each point in
1
, and the signed measure
CDQp,q , normalized with a multiplicative factor pq
of a bivariate quasi-copula with convex sections. Interestingly, the family
of quasi-copulas with convex horizontal and vertical sections has not been
studied before. Our findings suggest that further research efforts should be
made in understanding the properties of this class of quasi-copulas and its
relation to ultramodular copulas.
5. On Vertex Representations
In the previous sections we showed that two special families of discrete
copulas and discrete quasi-copulas admit representations as convex polytopes using collections of inequalities. A powerful feature of working with
convex polytopes is that they admit an alternative representation as the
convex hull of their vertices (i.e., extreme points). If S ⊂ Rp then the convex hull of S, denoted conv(S), is the collection of all convex combinations
of points in S. A point x ∈ S is called an extreme point of S provided that
for any two points a, b ∈ S for which (a + b)/2 = x, we have that a = b = x.
If P ⊂ Rp is a convex polytope, an extreme point of P is called a vertex and
the collection of all vertices of P is denoted V(P ). The Krein-Milman Theorem in convex geometry (Barvinok, 2002, Theorem 3.3) states that P can
be represented by its collection of vertices, namely P = conv(V(P )). The
collection of vertices of a convex polytope is known as its V -representation.
11

(p, q)
(3, 3)
(3, 4)
(3, 5)
(4, 4)
(4, 5)
(5, 5)

UDC
7
52
166
115
3321
22890

CDQ
7
52
138
69
2163
5447

DQ
7
118
416
42
7636
429

DC
6
96
360
24
3000
120

Table 1: The number of vertices of UDCp,q , CDQp,q , DQp,q , and DCp,q as computed
using polymake (Gawrilow and Joswig, 2000).

While having efficiently-sized minimal H-representations of convex polytopes is beneficial from a linear optimization perspective, it can also be useful
to have the V -representation of the same polytope. For example, the vertices
of the Birkhoff polytope Bp are precisely the p × p permutation matrices (see
for instance (Barvinok, 2002, Theorem 5.2)). In the setting of discrete copulas, this means that the vertices of DCp correspond to the empirical copulas
(Kolesarova et al., 2006; Mesiar, 2005), and thus all bivariate discrete copulas can be constructed by way of convex combinations of empirical copulas.
This vertex representation of DCp is known in the statistical literature: the
empirical copulas are precisely the copulas constructible from observed data
(Mesiar, 2005), which has made them fundamental in the development of
rank-based copula methods (Joe, 2014; Scaillet et al., 2007).
Thus, if a family of discrete copulas or quasi-copulas admits a representation as a polytope, it may be beneficial to identify its V -representation. At
the same time, polytopes with efficiently sized minimal H-representations
can often have a super-exponential number of vertices, meaning that it may
be difficult to learn its V -representation in its entirety. Indeed, this paradigm
appears to be the case for the polytopes UDCp,q and CDQp,q , as suggested
by the data in Table 5. While complete V -representations of UDCp,q and
CDQp,q seem out of reach, in this section we provide two constructions to
obtain families of vertices for each of these polytopes.
5.1. New Vertices by Way of Symmetry.
In the coming subsections, we will use the following fundamental theorem
from convex geometry:
Theorem 6. (Barvinok, 2002, Theorem 4.2) Let P := {x ∈ Rp : hai , xi ≤
βi for i ∈ [m]} be a polyhedron, where ai ∈ Rp and βi ∈ R for i ∈ [m]. For
u ∈ P let I(u) := {i ∈ [m] : hai , ui = βi } be the collection of inequalities that
12

are active on u. Then u is a vertex of P if and only if the set of vectors
{ai : i ∈ I(u)} linearly spans the vector space Rp . In particular, if u is a
vertex of P , then the set I(u) contains at least p indices, i.e., |I(u)| ≥ p.
The vectors βi in the above theorem are called the facet-normals or facetnormal vectors of the polyhedron P . We now apply Theorem 6 to prove a
basic symmetry statement about the vertices of UDCp,q and CDQp,q . Recall
that we think of a bivariate discrete (quasi)-copula C : Ip × Iq −→ [0, 1] as
a (p + 1) × (q + 1) matrix C = [cij ]p,q
i,j=0 whose entries are the values of C.
Given this representation for C, we can then consider its transpose C T .
Proposition 2. Suppose that C ∈ UDCp,q (C ∈ CDQp,q ), then C T ∈
UDCq,p (C T ∈ CDQq,p ). Moreover, if C is a vertex of UDCp,q (CDQp,q ),
then C T is a vertex of UDCq,p (CDQq,p ).
Proof. We here prove the statement for the polytope UDCp,q . The proof
for CDQp,q works analogously. Recall that the facet-defining inequalities for
UDCp,q are (d1), (d2), (d3a), and (d3b), which can be reorganized as:
(1) x11 ≥ 0,
(2) xp−1,q−1 ≥ (p−1)(q−1)−1
,
pq
(3) for i ∈ [p − 2] and j ∈ [q − 2],
xij + xi+1j+1 ≥ xij+1 + xi+1j ,
(4) for i ∈ [p − 1] and j ∈ [q − 1]
2xij ≤ xi−1j + xi+1j

and

2xij ≤ xij−1 + xij+1 .

By Theorem 1, the minimal H-representation of UDCp,q is given by the
inequalities (1), (2), (3), and (4) with the exception of the two inequalities
x11 + x22 ≥ x12 + x21

and

xp−2q−2 + xp−1q−1 ≥ xp−2q−1 + xp−1q−2 .

From this presentation of the minimal H-representation of UDCp,q , we can
see that if C ∈ UDCp,q then C T ∈ UDCq,p . Moreover, by Theorem 6, it
follows that if C is a vertex of UDCp,q then C T is a vertex of UDCq,p .
The vertex construction technique of Proposition 2 suggests that all vertices of UDCp,q (CDQp,q ) are derived from (quasi-)copulas C on [0, 1]2 such
that C(i/p, j/q) = C(j/q, i/p), for every i ∈ hpi and j ∈ hqi. Therefore,
the checkerboard extension (quasi)-copula constructed in the proof of Theorem 2 (Theorem 5) from the vertices of UDCp,q (CDQp,q ) is symmetric, i.e.,
13

it describes the stochastic dependence of exchangeable random variables.
Furthermore, Proposition 2 is an intuitive result whose proof provides a
nice example of how Theorem 6 can be used to study extremal discrete
copulas. Another example is provided in the following subsection.
5.2. New vertices by way of direct products.
Our second construction of families of vertices is by taking direct sums
of lower-dimensional vertices. Recall from Proposition 1 that there is a
linear map T : R(p+1)×(q+1) −→ Rp×q sending a discrete (quasi)-copula to
1
1
a matrix in pq
Bp,q (a matrix in pq
ASMp,q ). Further recall that UDC p,q =
pqT (UDCp,q ) and CDQp,q = pqT (CDQp,q ). Define the direct sum of B ∈
UDC p,q (CDQp,q ) and D ∈ UDC s,t (CDQs,t ) to be the block matrix


0p,t B
B ⊕ D :=
∈ R(p+s)×(q+t) .
D 0s,q
Indeed, if we applied the transformation R : R(p+s)×(q+t) −→ R(p+s)×(q+t)
with eij 7−→ ei(q+t−j+1) , then R(B ⊕D) is the direct sum of R(B) and R(D).
In the following, we show how to use this operation to identify vertices of
UDC p,q and CDQp,q (and equivalently UDCp,q and CDQp,q ).
Recall from Section 2 that T (u, v) denotes the transportation polytope
with marginals u ∈ Rp and v ∈ Rq , and A(u, v) denotes the alternating transportation polytope with the same marginals. The subpolytopes
UDC p,q ⊂ Bp,q and CDQp,q ⊂ ASMp,q admit a natural geometric generalization to subpolytopes UDC(u, v) ⊂ T (u, v) and CDQ(u, v) ⊂ A(u, v).
Namely, we let UDC(u, v) denote the subpolytope of T (u, v) satisfying the
additional inequalities (b3a) and (b3b), and we let CDQ(u, v) denote the
subpolytope of A(u, v) satisfying the additional inequalities (a3a) and (a3b).
In the following, for m, k ∈ Z, let mp := (m, m, . . . , m) ∈ Rp , and let
(mp , kq ) ∈ Rp+q denote the concatenation of the vectors mp and kq . We
can then make the following geometric observation.
Theorem 7. If B is a vertex of UDC p,q (CDQp,q ) and D is a vertex of
UDC s,t (CDQs,t ), then B ⊕ D is a vertex of UDC((qp , ts ), (st , pq )) (and
analgously, CDQ((qp , ts ), (st , pq ))).
The proof of this result is another application of Theorem 6 and is given
in the Appendix. In the special case where p = q and s = t, then UDC p,q and
UDC s,t are dilations of subpolytopes of Bp and Bs , respectively. Thus, we can
assume that the marginals of T (u, v) are u = v = 1p+s ∈ Rp+s . Therefore,
Theorem 7 produces vertices of UDCp+s . The proof of the following corollary
can be found in the Appendix.
14

Corollary 8. If B is a vertex of UDC p (CDQp ) and D is a vertex of UDC s
(CDQs ), then B ⊕ D is a vertex of UDC p+s (CDQp+s ).
Remark 5 (Statistical Interpretation of Vertices). Recall that given
a copula C, a patchwork copula derived from C is any copula whose probability distribution coincides with the one of C up to a finite number of
rectangles Ri in [0, 1]2 in which the probability mass is distributed differently (Durante et al., 2013). The vertices obtained via Corollary 8 correspond to a special class of patchwork (quasi)-copulas named W-ordinal
sums, which are patchworks derived from the Fréchet lower bound of copulas
W (u, v) = max{0, u + v − 1} (Mesiar and Szolgay, 2004). The (normalized)
direct sum of two vertices B ∈ UDC p (CDQp ) and D ∈ UDC s (CDQs ) is the
following block matrix


0p,s B
1
B ⊕ D := p+s
∈ R(p+s)×(p+s) .
D 0s,p
Any extension (quasi)-copula
C̃on [0, 1]2 , whose associated mass is given

p
s
by B ⊕ D, satisfies C̃ p+s
, p+s
= 0. Furthermore, any (quasi)-copula C
with C(u0 , 1 − u0 ) = 0 for 0 < u0 < 1 can be written as a W-ordinal sum
(De Baets and De Meyer, 2007). Thus, any such C̃ associated to B ⊕ D is
a W-ordinal sum.
While Corollary 8 is a useful method for constructing vertices of UDCp
and CDQp from known, lower-dimensional vertices, it is important to notice
that not all vertices of UDCp and CDQp can be captured in this fashion.
For example, as we can see in Figure 2, UDC3 has seven vertices, of which
only three arise from this direct sum construction. However, as we show in
the following subsection, Corollary 8 can be used to provide lower bounds
on the number of vertices of these polytopes.
5.3. Generating Functions for the Number of Vertices.
In this subsection we consider the special case of the polytopes UDCp,q
and CDQp,q for which p = q. For convenience, we only discuss the polytope UDCp . However, the results all hold analogously for CDQp . Corollary 8 gives a convenient way by which to partition the collection of vertices
V(UDCp ) into two disjoint collections: we call a vertex of UDCp decomposable if the corresponding vertex in UDC p admits a decomposition as a direct
sum of two lower dimensional vertices as in Corollary 8. All other vertices of

15



0
1
2
1
2



0
1
2
1
2

1
2

0
1
2





0

0

0

1

1

 13
3
1
3

0
1
2
1
2

0
1
2
1
2



1
2
1

4
1
4

1
2
1

2





1
2
1
4
1
4

1
3
1
3
1
3

0

1

1

1
2

1
4
1
4
1
2

0

0

0

1




0

0
 14
4



1
2
1

2

1
3
1

3
1
3


1

0


1
2
1
2

1
0




0
0



1
2
1

2

0

Figure 2: The edge-graph of the polytope UDC 3 , with its seven vertices, is the edge graph
of a triangulated octahedron. Indeed, UDC 3 is a four-dimensional polytope, with eight
simplicial facets and one octahedral facet. On the right is a Schlegel diagram (Ziegler,
1995) of UDC 3 as it appears when projected onto its three-dimensional, octahedral facet.

UDCp are called indecomposable. Let Dp and IDp denote the decomposable
and indecomposable vertices of UDCp , respectively, and let
X
X
X
V (x) :=
|V(U DCp )|xp , ID(x) :=
| IDp |xp , and D(x) :=
| Dp |xp ,
p≥0

p≥0

p≥0

denote the generating functions for the values |V(UDCp )|, | IDp |, and | Dp |,
respectively. As suggested by the data in Table 5, the size of the set
V(UDCp ) appears to grow super-exponentially in p. The following observation, whose proof is given in the Appendix, may be used to provide lower
bounds supporting this observed growth-rate.
Proposition 3. The number of vertices of UDCp is computable in terms of
its number of decomposable vertices by the relationship
V (x) =

D(x)2 + D(x) − 1
.
D(x)

Moreover, if M (x) ≤ D(x), is a lower-bound on the number of decomposable
vertices of UDCp then
V (x) ≥

M (x)2 + M (x) − 1
.
M (x)
16

Since a lower bound on the number of decomposable vertices can be
achieved by identifying a lower bound on the number of indecomposable
vertices in lower dimensions, it is worthwhile to investigate large families of
indecomposable extremal ultramodular discrete copulas. The identification
of sufficiently large families of such copulas could then be used to prove that
the size of the vertex representation of UDCp grows super-exponentially, as
well as serve to generate larger families of vertices of these polytopes for
statistical use by the construction given in Corollary 8.
6. Aggregation Functions & Alternating Transportation Polytopes
We end this paper with a discussion aimed at completing the evolving
parallel story between discrete bivariate copulas, the Birkhoff polytopes and
each of their generalizations. In Section 2, we highlighted the following
hierarchy of generalizations of Birkhoff polytopes:
Transportation
Birkhoff
Generalized
Polytopes
⊂
Birkhoff Polytopes
⊂
Polytopes
∩
∩
∩
Alternating Sign
Generalized Alternating
Alternating
Matrix Polytopes ⊂ Sign Matrix Polytopes ⊂ Transportation Polytopes
Analogously, we have the hierarchy of generalizations of discrete copulas:
p × p Discrete
Copulas
∩
p × p Discrete
Quasi-copulas

p × q Discrete
⊂
Copulas
∩
p × q Discrete
⊂ Quasi-copulas

⊂

?
∩

⊂

?

The main efforts of this paper were aimed at identifying polyhedral representations of subfamilies of each of these collections of functions (Sections 3
and 4) as well as a polyhedral representation of the family of p × q discrete
quasi-copulas in its entirety (Theorem 3). However, we can also extend the
correspondence between these hierarchies of generalizations in terms of a
functional generalization of copulas:
Definition 3. (Grabisch et al., 2009) A (binary) aggregation function is a
function C : [0, 1]2 → [0, 1] that satisfies the following
(A1) C(0, 0) = 0 and C(1, 1) = 1;
(A2) C(u1 , v1 ) ≤ C(u2 , v2 ), for every u1 ≤ u2 , v1 ≤ v2 ∈ [0, 1].
17

Aggregation functions naturally include copulas and quasi-copulas. In
particular, copulas are the supermodular aggregation functions with annihilator 0 and neutral element 1, and quasi-copulas are 1-Lipschitz aggregation
functions with annihilator 0 and neutral element 1. Analogous to the case of
discrete (quasi)-copulas, we can consider discrete aggregation functions Cpq
with domain Ip ×Iq , which are representable by a matrix [cij ] ∈ R(p+1)×(q+1)
where cij := Cp,q (i/p, j/q). By way of the same linear transformation used
in Proposition 1, we now observe a correspondence between discrete aggregation functions and the matrices within (alternating)
transportation
polyP
P
topes A(u, v) with homogeneous marginals, i.e., i ui = j vj = pq.
Given two vectors ũ := (ũ1 , . . . , ũp ) ∈ Rp>0 and ṽ := (ṽ1 , . . . , ṽq ) ∈ Rq>0
with ũp = ṽq = pq, we define the set SAF(ũ, ṽ) to be the matrices [cij ] ∈
R(p+1)×(q+1) satisfying
(AF1a) c0j = 0, ci0 = 0 with i ∈ hpi, j ∈ hqi;
(AF1b) cpj−1 =

ṽj−1
pq

<

ṽj
pq

= cpj , ci−1q =

ũi−1
pq

<

ũi
pq

= ciq ,

(AF2a) cij + ci−1 j−1 − ci−1 j − ci j−1 ≥ 0 for every i ∈ [p], j ∈ [q].
Note that the elements of SAF(ũ, ṽ) are discrete aggregation functions.
Indeed, given any i1 ≤ i2 ∈ hpi, and j1 ≤ j2 ∈ hpi, property (AF2a) implies
that ci2 j2 ≥ ci1 j2 ≥ ci1 j1 . The following proposition links the set SAF(ũ, ṽ) to
a transportation polytope T (u, v) with homogeneous marginals. The proof
of the following two propositions can be found in the Appendix.
Proposition 4. For a function Cpq : Ip × Iq → [0, 1], the following statements are equivalent:
(i) Cpq ∈ SAF(ũ, ṽ).
(ii) P
There is a (p×q) transportation matrix [xij ] in T (u, v), with
p
`=1 u` = pq, such that for every i ∈ hpi, j ∈ hqi
cij := Cp,q



i j
,
p q



=

j
i
1 XX
x`h .
pq

Pq

h=1 vh

=

(4)

`=1 h=1

A similar construction offers a correspondence between families of aggregation functions and alternating transportation polytopes with homogeneous marginals. Given two vectors ũ := (ũ1 , . . . , ũp ) ∈ Rp>0 and ṽ :=
(ṽ1 , . . . , ṽq ) ∈ Rq>0 , we define the set ASA(ũ, ṽ) to be the matrices [cij ] ∈
R(p+1)×(q+1) which satisfy conditions (AF1a), (AF1b), and
(AF2b) ci1 j1 + ci2 j2 − ci1 j2 − ci2 j1 ≥ 0 for every i1 ≤ i2 ∈ hpi, j1 ≤ j2 ∈ hqi,
and i1 = 0, or i2 = p, or j1 = 0, or j2 = q.
18

It can be shown that the elements of ASA(ũ, ṽ) are discrete aggregation
functions by following the same reasoning presented for the set SAF(ũ, ṽ).
The following proposition shows the link between the set ASA(ũ, ṽ) and an
alternating transportation polytope A(u, v).
Proposition 5. For a function Cpq : Ip × Iq → [0, 1], the following statements are equivalent:
(i) Cpq ∈ ASA(ũ, ṽ).
(ii) TherePis a (p × P
q) alternating transportation matrix [xij ] in A(u, v),
q
with h=1 vh = p`=1 u` = pq, such that for every i ∈ hpi, j ∈ hqi
cij := Cp,q



i j
,
p q



j
i
1 XX
=
x`h .
pq

(5)

`=1 h=1

Remark 6. Propositions 4 and 5 together offer a natural completion for the
question marks in our above hierarchy on generalizations of discrete copulas
that fits nicely within the current literature on copula functions. We note
however, that the correspondence captured in these propositions does not
capture all p × q (alternating) P
transportation
polytopes, but only those with
P
homogeneous marginals; i.e., i ui = j vj = pq. For example, this generalized correspondence does not encompass the (alternating) transportation
polytopes containing the polytopes considered in Theorem 7. To the best of
the authors’ knowledge there does not yet exist a generalization of discrete
copulas in the statistical literature that corresponds to the entire family of
p × q alternating transportation polytopes.
7. Discussion
There has recently been an increasing interest in exploiting tools from
the field of discrete geometry to shed light on well-known stochastic problems (Krause et al., 2017; Embrechts et al., 2016; Fiebig et al., 2017). In this
work, we unified the theoretical analysis of discrete copulas and their generalizations with the existing theory on generalizations of the Birkhoff polytope in the discrete geometry literature. Bivariate discrete copulas and their
generalizations discussed in this paper admit representations as polytopes
corresponding to generalizations of the Birkhoff polytope. We furthered
this connection by identifying the minimal H-representations of subfamilies
of bivariate discrete copulas (and their generalizations). We showed that
the families of p × q ultramodular bivariate discrete copulas and of p × q
19

bivariate convex discrete quasi-copulas admit polyhedral representations as
subpolytopes of the p × q generalized Birkhoff polytope and the p × q generalized alternating sign matrix polytope, respectively. Along the way, we
also generalized well-known results on alternating sign matrix polytopes by
computing the minimal H-representation of the p×q generalized alternating
sign matrix polytope. The sizes of each minimal H-representation presented
within this paper is quadratic in p and q, which opens the door to efficient
linear optimization techniques for bivariate copula selection. In addition, we
presented new methods for constructing irreducible elements of each of these
families of p × p (quasi)-copulas by constructing families of vertices for the
associated polytopes. Finally, we ended by connecting the most extensive
generalization of discrete copulas in the statistical literature (i.e., aggregration functions) with the most extensive generalization of Birkhoff polytopes
in the discrete geometry literature (i.e., alternating transportation polytopes), thereby completely unifying the two hierarchies of generalizations.
The geometric findings presented in this paper allow determining whether
a given arbitrary nonnegative matrix is the probability mass of an ultramodular bivariate copula. An interesting line for future research is to build
on our results to construct statistical tests of ultramodularity for bivariate
copulas in the same fashion as symmetry tests (Genest et al., 2012; Jasson,
2005). The extension results of Theorem 2 and Theorem 5, together with
the vertex constructions presented in Section 5, suggest alternative ways to
obtain ultramodular bivariate copulas and convex quasi-copulas which could
be used as smooth approximators of analytically unfeasible (quasi)-copulas.
A natural follow-up to this research is to define the geometry of multivariate discrete copulas with the property of ultramodularity. This would
allow an efficient approximation of popular multivariate families of copulas
such as Extreme Value (Capéraà et al., 1997; Gudendorf and Segers, 2010),
Archimedean (Genest et al., 2011), and Archimax (Capéraà et al., 2000;
Charpentier et al., 2014), which relate to the ultramodular ones (SamingerPlatz et al., 2017). Finally, it would be interesting to consider also other
types of stochastic dependence for discrete copulas such as multivariate total
positivity (Colangelo et al., 2006; Müller and Scarsini, 2005).
Acknowledgments
Elisa Perrone was supported by an FWF Schrödinger Fellowship (J 3968N32). Liam Solus was supported by an NSF Mathematical Sciences Postdoctoral Fellowship (DMS-1606407). Caroline Uhler was supported by NSF
(DMS-1651995), ONR (N00014-17-1-2147), and a Sloan Fellowship.
20

References
K. Aas, C. Czado, A. Frigessi, and H. Bakken. Pair-copula constructions
of multiple dependence. Insurance: Mathematics and Economics, 44(2):
182–198, 2009. 2
I. Aguiló, J. Suñer, and J. Torrens. Matrix representation of discrete quasicopulas. Fuzzy Sets and Systems, 159(13):1658–1672, 2008. 3
I. Aguiló, J. Suñer, and J. Torrens. Matrix representation of copulas and
quasi-copulas defined on non-square grids of the unit square. Fuzzy Sets
and Systems, 161(2):254–268, 2010. 3
A. Barvinok. A Course in Convexity, volume 54. American Mathematical
Society, Providence, RI, 2002. 11, 12
T. Bedford and R. M. Cooke. Vines–a new graphical model for dependent
random variables. Annals of Statistics, 30:1031–1068, 2002. 2
P. Capéraà, A.-L. Fougères, and C. Genest. A nonparametric estimation
procedure for bivariate extreme value copulas. Biometrika, 84(3):567–
577, 1997. 20
P. Capéraà, A.-L. Fougères, and C. Genest. Bivariate distributions with
given extreme value attractor. Journal of Multivariate Analysis, 72(1):
30–49, 2000. 20
A. Charpentier, A.-L. Fougères, C. Genest, and J. Nešlehová. Multivariate
Archimax copulas. Journal of Multivariate Analysis, 126(Supplement C):
118–136, 2014. 20
A. Colangelo, M. Scarsini, and M. Shaked. Some positive dependence
stochastic orders. Journal of Multivariate Analysis, 97(1):46–78, 2006.
20
B. De Baets and H. De Meyer. Ortogonal grid constructions of copulas.
IEEE Transactions on Fuzzy Systems, 15(6):1053–1062, 2007. 15
J. A. De Loera and E. D. Kim. Combinatorics and geometry of transportation polytopes: An update. In Discrete Geometry and Algebraic
Combinatorics, volume 625 of Contemporary Mathematics, pages 37–76.
American Mathematical Society, Providence, RI, 2014. 5, 7
F. Durante and C. Sempi. Principles of Copula Theory. CRC/Chapman &
Hall, Boca Raton, FL, 2015. 1, 3
21

F. Durante, J. Fernández Sánchez, and C. Sempi. Multivariate patchwork
copulas: A unified approach with applications to partial comonotonicity.
Insurance: Mathematics and Economics, 53(3):897–905, 2013. 15
P. Embrechts, M. Hofert, and R. Wang. Bernoulli and tail-dependence compatibility. The Annals of Applied Probability, 26(3):1636–1658, 2016. 19
U.-R. Fiebig, K. Strokorb, and M. Schlather. The realization problem for
tail correlation functions. Extremes, 20(1):121–168, 2017. 19
E. Gawrilow and M. Joswig. polymake: a framework for analyzing convex
polytopes. In Polytopes—combinatorics and computation (Oberwolfach,
1997), volume 29 of DMV Seminars, pages 43–73. 2000. 12
C. Genest, J. J. Quesada Molina, J. A. Rodrı́guez Lallena, and C. Sempi. A
Characterization of Quasi-copulas. Journal of Multivariate Analysis, 69
(2):193–205, 1999. 4, 5
C. Genest, J. Nešlehová, and J. Ziegel.
Inference in multivariate
Archimedean copula models. TEST, 20(2):223–256, 2011. 20
C. Genest, J. Nešlehová, and J.-F. Quessy. Tests of symmetry for bivariate
copulas. Annals of the Institute of Statistical Mathematics, 64(4):811–834,
2012. 20
C. Genest, J. G. Nešlehová, and B. Rémillard. On the empirical multilinear
copula process for count data. Bernoulli, 20(3):1344–1371, 2014. 9
C. Genest, J. G. Nešlehová, and B. Rémillard. Asymptotic behavior of the
empirical multilinear copula process under broad conditions. Journal of
Multivariate Analysis, 159:82 – 110, 2017. 9
M. Grabisch, J.-L. Marichal, R. Mesiar, and E. Pap. Aggregation Functions
(Encyclopedia of Mathematics and Its Applications). Cambridge University Press, 1st edition, 2009. 17
G. Gudendorf and J. Segers. Extreme-value copulas. In P. Jaworski, F. Durante, W. K. Härdle, and T. Rychlik, editors, Copula Theory and Its Applications: Proceedings of the Workshop Held in Warsaw, 25-26 September
2009, pages 127–145. Springer Berlin Heidelberg, 2010. 20
S. Jasson. L’asymétrie de la dépendance, quel impact sur la tarification?
Technical report, AXA Group Risk Management, Paris, France, 2005. 20

22

H. Joe. Dependence Modeling with Copulas. Chapman and Hall/CRC, Boca
Raton, FL, 2nd edition, 2014. 12
S. Kirshner. Learning with tree-averaged densities and distributions. In
J. C. Platt, D. Koller, Y. Singer, and S. T. Roweis, editors, Advances in
Neural Information Processing Systems 20, pages 761–768. 2008. 2
E. P. Klement, M. Manzi, and R. Mesiar. Ultramodular aggregation functions. Information Sciences, 181(19):4101–4111, 2011. 3, 4
E. P. Klement, M. Manzi, and R. Mesiar. Ultramodularity and copulas.
Rocky Mountain Journal of Mathematics, 44(1):189–202, 2014. 4
V. Knight. Alternating Sign Matrices and Polytopes. PhD thesis, 2009. 3,
6, 9
A. Kolesarova, R. Mesiar, J. Mordelova, and C. Sempi. Discrete Copulas.
IEEE Transactions on Fuzzy Systems, 14(5):698–705, 2006. 3, 9, 12
D. Krause, M. Scherer, J. Schwinn, and R. Werner. Membership testing for
bernoulli and tail-dependence matrices. Working Paper, 2017. 19
G. Mayor, J. Suñer, and J. Torrens. Copula-like operations on finite settings.
IEEE Transanctions on Fuzzy Systems, 13(4):468–477, 2005. 3
R. Mesiar. Discrete copulas-what they are. In Proceedings of EUSFLATLFA Conference (Barcelona, Spain), pages 927–930. 2005. 3, 12
R. Mesiar and J. Szolgay. W-ordinals sum of copulas and quasi-copulas.
In Proceedings of MAGIA 2004 Conference (Kocǒvce, Slovak Republic),
pages 78–83. 2004. 15
J. Mordelová and A. Kolesárová. Some results on discrete copulas. In
Proceedings of the Fourth International Summer School on Aggregation
operatos (Ghent, Belgium), pages 145–150, 2007. 3
A. Müller and M. Scarsini. Stochastic comparison of random vectors with
a common copula. Mathematics of Operations Research, 26(4):723–740,
2001. 2
A. Müller and M. Scarsini. Archimedean copulae and positive dependence.
Journal of Multivariate Analysis, 93(2):434–445, 2005. 20

23

A. Müller and M. Scarsini. Fear of loss, inframodularity, and transfers.
Journal of Economic Theory, 147(4):1490–1500, 2012. Inequality and
Risk. 2
R. B. Nelsen. An Introduction to Copulas (Springer Series in Statistics).
Springer, 2nd edition, 2006. 1, 9, 34
R. B. Nelsen and M. U. Flores. The lattice-theoretic structure of sets of
bivariate copulas and quasi-copulas. Comptes Rendus Mathematique, 341
(9):583–586, 2005. 3
O. Okhrin, Y. Okhrin, and W. Schmid. On the structure and estimation
of hierarchical Archimedean copulas. Journal of Econometrics, 173(2):
189–204, 2013. 2
J. J. Quesada Molina and C. Sempi. Discrete quasi-copulas. Insurance:
Mathematics and Economics, 37(1):27–41, 2005. ISSN 0167-6687. 40
S. Saminger-Platz, E. P. Klement, J. De Jesús Arias-Garcı́a, and R. Mesiar.
Characterizations of bivariate conic, extreme value, and Archimax copulas. Dependence Modeling, 5(1):45–58, 2017. 20
O. Scaillet, A. Charpentier, and J.-D. Fermanian. The estimation of copulas
: theory and practice, pages 35–64. Copulas: from theory to application
in finance. Risk Books, London, 2007. 12
A. Sklar. Fonctions de répartition à n dimensions et leurs marges. Publications de l’Institut de Statistique de Paris, 8:229–231, 1959. 2
J. Striker. The Alternating Sign Matrix Polytope. The Electronic Journal
of Combinatorics, 16(1):R41, 2009. 3, 4, 6, 10
G. M. Ziegler. Lectures on Polytopes. Springer-Verlag, 1995. 3, 16

Appendix A: Proofs for Section 3
Lemma 9. Suppose that [cij ] ∈ R(p+1)×(q+1) satisfies all of (d1), (d2), (d3a),
and (d3b) as well as the equalities
c0k = 0, cpk =

k
h
, ch0 = 0, chq = for all h ∈ hpi, k ∈ hqi.
q
p

Then [cij ] ∈ UDCp,q .
24

Proof. To prove the result, we consider C = [cij ] ∈ R(p+1)×(q+1) that satisfies
all of the inequalities (d1), (d2), (d3a), and (d3b) together with the equalities
stated in the lemma. To show C ∈ UDCp,q , we must check that C satisfies
the inequalities (c1). That is, we must show that the following inequalities
are valid on C.
i.

c11 + c22 − c12 − c21 ≥ 0;

ii.

cp−2q−2 + cp−1q−1 − cp−2q−1 − cp−1q−2 ≥ 0;

iii. (a) c1j+1 − c1j ≥ 0, (b) ci+1 1 − ci1 ≥ 0;
for all i ∈ hp − 1i, j ∈ hq − 1i
iv. (a) cp−1j+1 − cp−1j ≤ 1q , (b) ci+1q−1 − ciq−1 ≤ p1 ;
for all i ∈ hp − 1i, j ∈ hq − 1i
C satisfies conditions (d3a) and (d3b), respectively for (i, j) = (2, 0) and
(i, j) = (0, 2). Moreover, c11 ≥ 0. Therefore, inequality i. can be obtained
from
2(c11 + c22 ) ≥ 2c22 ≥ 2(c12 + c21 ).
From inequalities (d1), it holds that cp−1q−1 ≥ − p1 +
q ≥ p, we then have that
cp−1q−1 ≥ max{− 1q +

q−1
1
q , −p

+

p−1
p }

q−1
q .

Assuming

p−2
= max{ q−2
q , p }.

From (d3a) and (d3b) for (i, j) = (p − 2, q − 2), we recover inequality ii:




q−2
2 cp−2 q−2 + cp−1 q−1 ≥ 2 cp−2 q−2 + p−2
+
≥
2
c
+
c
p−2 q−1
p−1 q−2 .
p
q

The inequalities iii.(a) and iv.(a) can be obtained by combining conditions
(d1) and (d3a). Indeed, for iii.(a) we have that
c1j+2 − c1j+1 ≥(d3a) c1j+1 − c1j ≥ . . . ≥ c12 + c11 ≥ c11 ≥(d1) 0.
Similarly, for iv.(a) we have that
1
q

≥(d1) cp−1q − cq−1q−1 ≥(d3a) cp−1j+2 − cp−1j+1 ≥ cp−1j+1 − cp−1j .

In an analogous manner one can derive iii.(b) and iv.(b).

25

7.1. Proof of Theorem 1.
We here prove that the inequalities in the list (b1), (b2), (b3a), and
(b3b) are the minimal H-representation of the polytope UDC p,q . To do this,
(ij)
(ij)
we identify (p × q)-matrices Mpq = [bij ], and Hpq = [hij ] for i ∈ [p] and
j ∈ [q] such that
(11)

Case (b1). for every p and q, Mpq satisfies all inequalities in the list
(b1), (b2), (b3a), and (b3b) except for inequality of the type b11 ≥ 0.
Case (b2). for every i = 2, . . . , p − 1 and j = 2, . . . , q − 1, except for
(ij)
(i, j) = {(2, 2), (p − 1, q − 1)}, Mpq satisfies all inequalities in the list
(b1), (b2), (b3a), and (b3b) but one of the type bij ≥ 0.
j
k
(ij)
Case (b3a). for every i ∈ [p − 1] and 1 ≤ j ≤ q+1
, Hpq satisfies
2
all inequalities in the list (b1), (b2), (b3a), and (b3b) except for one
j
j
P
P
of the type
bi+1h ≥
bih .
h=1

h=1

The matrices that we shall identify satisfying each of these cases are, collectively, sufficient to prove that every inequality in the list (b1), (b2), (b3a),
and (b3b) is needed to bound the polytope UDC p,q . Indeed, let us assume
(ij)
Mpq = (bij ) to be a matrixjthatksatisfies (b1), (b2),j (b3a),
k and (b3b), but
for bîĵ ≥ 0 with î ∈ {2, . . . ,
(p−î+1,q−ĵ+1)

trix Mpq
(ij)
Mpq

p+1
2

} and ĵ ∈ {2, . . . ,

q+1
2

}. Then the ma-

= (bp−î+1 q−ĵ+1 ) obtained by flipping the original matrix

= (bij ) as follows


bpq

bpq−1


. . . bp1
. . . bp−11 

.. 
. 

bp−1q bp−1q−1

(p−î+1,q−ĵ+1)
Mpq
= .
 ..
b1q
b1q−1 . . .

b11

satisfies all of the constraints but for bp−î+1 q−ĵ+1 ≥ 0. We indicate this
transformation with bFij . In an analogous manner, one can obtain all of the
remaining cases among inequalities (b3a). Moreover, matrices that satisfy
all the inequalities of UDC p,q except for one of the (b3b)-type can be obtained
by transposing the ones of case (b3a) above.
We now present the matrices corresponding to cases (b1), (b2), and (b3a)
listed above. The inequalities considered in each of these three cases are further subdivided into the following subcases. Following the list of subcases
26

for each case, we present the matrices satisfying all inequalities in the list
(b1), (b2), (b3a), and (b3b) with the exception of the inequality corresponding to the given subcase. When considered together with Lemma 9, these
subcases and their corresponding matrices complete the proof.
The subcases of case (b1) are the following:
A. b11 < 0 with p, q ≥ 4.
The following is
listed above.

−1

1


h

A.  p−4 1


2

2

the associated list of matrices for the subcases of case (b1)
1

1

0

1

1

1

1

1


2 2

1 2


1 1.

1 0


2 |{z}
1
0 0
q−4

The subcases of case (b2) are the following:

B1. b23 < 0 with p = 4 and q = 5;
 
B2. b2j < 0 with 3 ≤ j ≤ 2q , for p ≥ 4, q ≥ 6;
B3. b



q+1
2 2

< 0, with p ≥ 4, q ≥ 7, q odd;

B4. b32 < 0, with p = 5, q ≥ 4;
 
B5. b3j < 0, with 3 ≤ j ≤ 2q , and p = 4, q ≥ 4;
 
B6. b3j < 0, with 3 ≤ j ≤ 2q , and p = 5, q ≥ 6;
B7. b



q+1
3 2

< 0, with p = 5, q ≥ 5 q odd;

 
, 3 ≤ j ≤ 2q , and p ≥ 6, q ≥ 6;
 
< 0, with 3 ≤ i ≤ p2 , and p ≥ 6, q ≥ 7, q odd;

B8. bij < 0, with 3 ≤ i ≤
B9. b  q+1 
i

2

p
2

B10. b p+1  < 0, with 3 ≤ j ≤
2

j

q
2

, and p ≥ 7, q ≥ 6, p odd;

B11. b p+1  q+1  < 0, with p, q ≥ 7, p and q odd;
2

2

27

B12. b42 < 0, with p = 5, q ≥ 5;
B13. bp−12 < 0, with p ≥ 6, q ≥ 6;
 
B14. bp−1 j < 0, with 3 ≤ j ≤ 2q , p ≥ 5, q ≥ 6, and p odd;
 
 
B15. bp−i+1 j < 0, with 2 ≤ i ≤ p2 , 2 ≤ j ≤ 2q , p ≥ 6, q ≥ 6, p odd;
The following
listed above.

0 0
2 2
3 3
B1. 
4 4
3 3
2 2


is the associated list of matrices for the subcases of case (b2)
1

2 2


2 2

0 0

0 0

− 31

0

7
3

1
0


2
0

3

h

1
B2.  p−4 1

4

2
3

2
2
|{z}


0

1

2
3

− 13

1

1

4
3

4
3

2

2

j−3

0

0


2
0

3

h

1
B3.  p−4 1

4

2
3

2
2
|{z}




0

1

2
3

− 13

1

1

4
3

7
3

2

1

1

1

1

1

1

2

1

1

1
0
|{z}
q−4

1

1

1

2


2
2


1

0

0




2 


1
1
1 

1
2
0 

1
0
0
|{z}
|{z}
q−2j

j−3

0 1
0 1

3
1
B4. 
2 −2
3
3
2
2
2 2

1

2 2

j−1

2




2 


1 1
1 

0 0
0 

0 0 |{z}
0
2 2

j−3

28



0

1

1

1

2

2



 0
1+y 1+y 1+y 1
2 



B5. 
 2
−y
x
1+x 1
0  where


0
0
0
2
1
2
|{z}
|{z}
|{z}
y=



0

0

1

i−3

2 


1
2
1 

1
1
0 

0
0
1
|{z}
|{z}
1

j−1

2

2



0

j−1

q−2j

0

2



2

q−2j

1

and

2 


2 −1 2
1 

2 2 0
0 

1 1 0 |{z}
0

j−3

h

0

1

1

j−2


0
0
0
0


1
B7. 
1
1
2

3 |{z}
2

1
q − 2j + 2
1

 0
0 1


1
3
B6. 
2 −2
 1
 2
3
3

2
2
2 2
2
|{z}



j−2

q−2j

j−1

1

j−2

0



2
0

3


2
0

3


1
− 31
B8. 

h

 p−2i 1
1


1
1


h

i−1
2
2
|{z}


2


4
1
2
2

3


4
1
2
2

3


4
1
1
2
3


1
1
1
1


1
2
1
0


1
0 |{z}
0
0
|{z}
1

2

2

j−2

29

x=

q − 2j + 1
.
q − 2j + 2



h

0

i−1

0



2
0

3

h

B9. 
1
 p−2i 1

4
2

3

h

i−1
2
2
|{z}

0

1

2
3

− 13

1

1

4
3

7
3

2

1

j−3








B10. 






i−3






B11. 






i−2





i−1

h

0

0

0
0

2
3
2
3

1

− 31

2
|{z}

2

0

0 0

0

1 1

h
h

j−1



2



2 


1 


0 


0
|{z}
j−1

1

2

1

4
3
4
3
7
3

2





2 


1
2 


1
1 


0 |{z}
0
1
|{z}
j−1

q−2j

1

2 2

1

1 1

2





2 


1
1 1 −1 2 2
1 


2
1 1 3 0 0
0 

h

i−2 2
0
|{z} 2 2 1 0 0 |{z}
j−3

0

1

0 1


B12. 
0 1
5 −1
2
2
5
2

5
2

j−3


1 1 2
1
1 1 2


1
1 2 1

1
2 1 0

1
0 0 0
|{z}
1

q−5

30



0

1

1


0 1
1



0 1
1


0 1
1
B13. 

h

1
 p−6 1 1


3 −1
1

3 3 |{z}
1
q−6



0



0



1


h
B14. 
 p−5 1


2


2
|{z}

1 1 1 2


1 1 1 2

1 1 2 1


1 1 2 1


1 1 1 1

2 2 0 0

0 0 0 0

0

1

1

1

2

1

1

1

1

1

0 1+y 1+y 1+y

1

1

1

1

1

2

−y

x

2

2

1
|{z}

j−2



h

i−2



0

1

1+x 1
0

0

q−2j

1




2 


1 

 where

1 

0 


0
|{z}
j−2

1
y=
q − 2j + 2
0

2

and

2

2

x=

q − 2j + 1
.
q − 2j + 2







0
1
1
1
2 





0
1+x
1
1+y
2 



h
B15. 
 where
 p−2i 1
x
1
1+y
1 




2
−y
1
1+y
1 



h


i−1
2
2
1
0
0
|{z}
|{z}
|{z}
j−1

q−2j

y=

j−1

1
p − 2i + 2

and

x=

The subcases for case (b3a) are the following:
C1.

j
P

h=1

b2h <

j
P

h=1

b1h

1≤j≤

j

q−1
2

k

31

,

p − 2i + 1
.
p − 2i + 2

C2.

ĵ
P

ĵ
P

b2h <

i
P

ĵ
P

bi+1 h <

ĵ
P

bi+1h <

ĵ
P

bi+1h <

i
P

bph <

h=1

C8.

ĵ
P
ĵ
P

k

, q odd;

q
2 , q even;

bih with 1 ≤ j ≤

ĵ
P

bih ĵ =

ĵ
P

bih ĵ =

j
P

j

q+1
2

k

bph <

ĵ
P

h=1

ĵ
P

q−1
2

k
, 2≤i≤p−2

q
2 , 2 ≤ i ≤ p − 2; q even;

bp−1h with 1 ≤ j ≤

bp−1h with ĵ =

h=1

bph <

j

, 2 ≤ i ≤ p − 2; q odd;

h=1

h=1

C9.

j
P

h=1

h=1

C7.

q+1
2

b1h with ĵ =

h=1

h=1

C6.

j

h=1

h=1

C5.

ĵ =

h=1

h=1

C4.

b1h

h=1

h=1

C3.

ĵ
P

b2h <

bp−1h with ĵ =

h=1

j

j

q+1
2

q−1
2

k

k

, q, p ≥ 4;

, q, p ≥ 4 q odd;

q
2 , q, p ≥ 4 q even.

The following is the associated list of matrices for the subcases of case (b3a)
listed above.


1
1
0
1
2
2
2


0
0 1
1
2 



h


C1.  p−4 1
1 1
1
1 


3
3

2
1
0 
2
2




2
2
|{z}
j−1

0


0


h

C2.  p−4 1


2

2
|{z}
ĵ−3

1

1
|{z}

q−2j−1

0 1 1 1

0
|{z}
j

2




2 


1 1 1 1
1 

1 1 2 1
0 

2 2 1 0 |{z}
0
1 0 0 2

ĵ−2

32



0


0


h

C3.  p−4 1


2

2
|{z}


ĵ−1

0

1 1


2 


1 1
1 

1 1
0 

2 0 |{z}
0
0 2

ĵ−1

1
2

h

 i−1 1
1


1
1
C4. 
2
h

 p−i−2 1
1

2
2
|{z}




1

1

1

3
2

1

1

1

1

1
|{z}

q−2j−1

0

0 2

1

1 1

1

2 0

1

1 1

1

1 2

2
1 0
|{z}
ĵ−1

0

h

 i−2 1


1
C6. 
h

 p−i−1 1

2
|{z}


1
2

j−1

h

 i−2



h
C5. 

 p−i−2




0 2

ĵ−3

2

0

1

1

1

1

1

1
2
3
2

1
1
|{z}

j




1 

2 0
1 


1 1
1 

1 1 |{z}
0
1




1 

1 


1 

0
|{z}

ĵ−1


0
0


h

1
C7.  p−4 1

5

2
2

3
2
2
|{z}
j−1

2


2
3

1
1


1
1


1
1

1
0

0
0
|{z}

1 1

ĵ−1

0



2

q−2j−1

2




2 


1 

0 

0
|{z}
j

33



0

1


3
0

2

h

C8.  p−4 1
1


2
1

1
2
2
|{z}
ĵ−1



0


0


h

C9.  p−4 1


2

2
|{z}
ĵ−1

2

2




2 


1
1 

0
0 

1
0
2 |{z}
3
2

ĵ−2

0 2

2




2 


1 1
1 

2 0
0 

1 1 |{z}
0
1 1

ĵ−1

Together with Lemma 9, these subcases and their corresponding matrices
complete the proof of the theorem.

7.2. Proof of Theorem 2.
Every C ∈ UDCp,q is a discrete copula on Ip × Iq . Thus, according to
(Nelsen, 2006, Lemma 2.3.5), the checkerboard extension C̃ of C which is
defined as
C̃(u, v) = (1−λu )(1−µv )ci,j +(1−λu )µv ci,j+1 +λu (1−µv )ci+1,j +λu µv ci+1,j+1
where

i
p

≤u≤

λu =

(

i+1 j
p , q

≤v≤

j+1
q ,

(u − pi )p u >
1
u=

i
p
i
p

and
and

µv =

(

(v − qj )q v >
1
v=

j
q
j
q

is a copula on [0, 1]2 , whose restriction on Ip × Iq is C. We now show
that for any C ∈ UDCp,q , C̃ is an ultramodular copula; i.e., C̃ has convex
horizontal and vertical (coordinatewise) sections. We here focus on any
arbitrary horizontal section Ca : u 7→ C̃(u, a) with a ∈ [0, 1] and prove
that it is a convex function. The same argument can be used to prove the
convexity of an arbitrary vertical section. Ca is a p-piecewise continuous
function. Therefore, to prove its convexity it is sufficient to show the Jensen
convexity, i.e., for u1 , u2 ∈ [0, 1]


Ca u21 + u22 ≤ 12 Ca (u1 ) + 21 Ca (u2 ).
(6)
34

j
Without loss of generality, we assume qj < a < j+1
q and define µa = (a− q ) q.
We then proceed by induction on the number M of intervals that contain
[u1 , u2 ]. To do this, we consider a few cases.
u1
u2
CASE M=1. Let us consider pi < u1 , u2 < i+1
p , and u3 = 2 + 2 , for
i ∈ hp − 1i. By definition, λ1 = pu1 − i and λ2 = pu2 − i. Hence,

λ3 =

pu1
2

pu2
2

+

−i=

λ1
2

+

λ2
2

By construction, we can then express Eq.(6) as follows.
Ca (u3 ) = (1 − λ3 )(1 − µa )ci,j + (1 − λ3 )µa ci,j+1
+λ3 (1 − µa )ci+1,j + λ3 µa ci+1,j+1
=

Ca (u1 )
2

+

Ca (u2 )
2

CASE M=2. Let us consider
Then,

Ca (u1 )
2
Ca (u1 )
2

+

i
p

< u1 <

i+1
p

< u2 <

i+2
p

for i ∈ hp − 1i.

Ca (u2 )
2

can be written as

1
2)
+ Ca (u
=
(1
−
µ
)
a
2
2 −

λ1
2







λ1
1
µa ci,j+1
2 − 2
+ λ21 (1 − µa )ci+1,j + µa λ21 ci+1,j+1
+ 21 (1 − µa )ci+1,j + 12 (1 − µa )ci+1,j+1
+(1 − µa ) λ22 (ci+2,j − ci+1,j )
+µa λ22 (ci+2,j+1 − ci+1,j+1 )

ci,j +

pu1
pu2
If pi < u3 < i+1
p , then λ3 = 2 + 2 − i =
inequalities (d3a) and (d3b), we have that

λ1
2

+

λ2
2

+ 21 . Thus, from

ci+2,j+1 − ci+1,j+1 ≥ ci+1,j+1 − ci,j+1 ≥ ci+1,j − ci,j .
Thus, it follows that
Ca (u1 )
2

+

Ca (u2 )
2

h


i
(1 − µa ) 12 − λ21 − (1 − µa ) λ22 ci,j
h 

i
+ µa 21 − λ21 − µa λ22 ci,j+1
h
i
+ (1 − µa ) λ21 + 12 (1 − µa ) + (1 − µa ) λ22 · ci+1,j
h
i
+ µa λ21 + 12 µa + µa λ22 ci+1,j+1

= Ca u21 + u22
≥

35

pu1
pu2
λ1
λ2
i+2
1
Assuming i+1
p < u3 < p . One has λ3 = 2 + 2 − i = 2 + 2 − 2 .
Conditions (d3a) and (d3b) imply the following inequalities for k ∈ {j, j +1}

ci,k ≥ 2 ci+1,k − ci+2,k
The result can therefore be derived as follows.
h

i
Ca (u1 )
Ca (u2 )
λ1
λ2
1
+
≥
(1
−
µ
)
1
−
λ
+
+
−
ci+2,j+1
a
1
2
2
2
2
2
h

i
+ (1 − µa ) − 12 + λ21 + λ22 ci+2,j
h 
i
+ µa 1 − λ1 + λ21 + 21 − λ22 ci+1,j+1
i
h 
+ µa − 12 + λ21 + λ22 ci+2,j+1

= Ca u21 + u22

CASE M = N ≤ p. Let us assume the result is true for N − 1 intervals.
In order to prove that Ca is convex, we only need to show that the last two
intervals of the partition attach in a convex way. Therefore, we can restrict
ourselves to the situation where N p−2 < u1 < N p−1 < u2 < Np . The thesis
follows from case M=2.
Appendix B: Proofs for Section 4

Lemma 10. Suppose that 3 ≤ p < q with q = kp + r for 0 ≤ r < p
and that [cij ] ∈ R(p+1)×(q+1) satisfies all of (a1), (a2), and (a3). Then
[cij ] ∈ ASMp,q .
Proof. Recall that for p < q with q = pk + r with 0 ≤ r < p the alternating
sign matrix polytope ASMp,q is defined by the collection of inequalities
Pp
Pq
1.
`=1 x`j = p;
h=1 xih = q for i ∈ [p] and j ∈ [q],
Pi
2. 0 ≤ `=1 x`j ≤ p for all i ∈ [p] and j ∈ [q],
P
3. 0 ≤ jh=1 xih ≤ q for all i ∈ [p] and j ∈ [q].

Using the equalities (1), we can transform the inequalities (2) and (3) into
the two families
P
2(a). 0 ≤ i`=1 x`j for all i ∈ [p] and j ∈ [q],
P
2(b). 0 ≤ p`=i+1 x`j for all i ∈ [p] and j ∈ [q],
P
3(a). 0 ≤ jh=1 xih for all i ∈ [p] and j ∈ [q], and
P
3(b). 0 ≤ qh=j+1 xih for all i ∈ [p] and j ∈ [q].
36

By symmetry, it suffices to determine which inequalities among 2(a) and 3(a)
are necessary and then take their symmetric opposites from among 2(b) and
3(b) as well.
Notice first that
P since the full column sums are always equal to q > 0,
then the equality p`=1 x`j = 0 yields the empty set. Thus, the case when
i = p for j ∈ [q] is not facet-defining. Similarly, this is true for the case
when j = q and iP
∈ [p]. Next notice that the inequalities x`1 ≥ 0 for all
` ∈ [p] imply that i`=1 x`j ≥ 0 for i ∈ {2, . . . , p − 1}. Thus, the inequalities
of type 2(a) are not facet-defining when i ∈ {2, . . . , p − 1} and j = 1.
Similarly, the inequalities of type 3(a) are not facet-defining when i = 1 and
j ∈ {2, . . . , q − 1}. Thus, we now know that the minimal H representation
of ASMp,q is contained within the collection of inequalities
P
2(a). 0 ≤ i`=1 x`j for all i ∈ {1, . . . , p − 1} and j ∈ {2, . . . , q − 1},
P
2(b). 0 ≤ p`=i+1 x`j for all i ∈ {1, . . . , p − 1} and j ∈ {2, . . . , q − 1},
P
3(a). 0 ≤ jh=1 xih for all i ∈ {2, . . . , p − 1} and j ∈ {1, . . . , q − 1}, and
P
3(b). 0 ≤ qh=j+1 xih for all i ∈ {2, . . . , p − 1} and j ∈ {1, . . . , q − 1}.

To complete
the proof, it remains to show that the inequalities of type
Pj
x
3(a)
h=1 ih ≥ 0 are redundant (i.e. not facet-defining) whenever i ∈
{2, . . . , p − 1} and j ∈ {q − k, . . . , q − 1}. Notice first that when p ≤ q and
[cij ] ∈ ASMp,q then cij ≤ p for all i ∈ [p] and j ∈ [q]. To see this fact,
recall that ASMp,q is defined by the inequalities listed inP(1), (2), and (3)
above. So, if there existed some cij > p, then since 0 ≤ i=1
`=1 c`j , it would
P
follow that i`=1 c`j > p, which contradicts the above inequalities defining
ASMp,q .
all h ∈ [q] then
Pq Now, let i ∈ {2, . . . , p − 1}. Since xih ≤ q = pk + r forP
q
x
≤
q
for
all
j
∈
{q
−
k,
.
.
.
,
q
−
1}.
Thus,
since
h=j+1 ih
h=1 xih = q, it
Pj
follows that h=1 xih ≥ 0, as desired.
Notice that for the symmetry argument to work, we must not apply it
to the corner inequalities; i.e., x11 ≥ 0, x1p ≥ 0, x1q ≥ 0 and xpq ≥ 0. Thus,
these inequalities are counted separately from the rest within (a1). This
completes the proof.
Given Lemma 10, to prove Theorem 3 it remains to show that for each
inequality in the list (a1), (a2), and (a3), there exists a point [cij ] ∈ Rp×q
satisfying all inequalities in the list with the exception of the chosen one.
7.3. Proof of Theorem 3.
By Lemma 10, we know that the minimal H-representation of ASMp,q
for p 6= q is contained within the collection of inequalities (a1), (a2) and
37

(a3). We here prove that inequalities (a1), (a2) and (a3) are exactly the
minimal H-representation of ASMp,q for p 6= q.
To do this, it suffices to show that for each inequality in the list there
exists a matrix [cij ] ∈ Rp×q that does not satisfy the chosen inequality but
satisfies all other inequalities among (a1), (a2), and (a3). The matrices are
given as follows.
For the inequalities in (a1), the matrix


1
1 3
h−1


1
1 1
 p−3 1

 ∈ Rp×q


1
1
2
0


3 |{z}
1
0 0
q−3

can be seen to satisfy all inequalities among (a1), (a2), and (a3) with
the exception of x11 ≥ 0. By permuting the columns of this matrix and
flipping the matrix horizontally, we see the desired matrices for the other
inequalities listed in (a1).
Pi For the conditions listed in (a1), the analogous matrix for the inequality
`=1 x`2 ≥ 0 is the matrix


A
1i×(q−i−2)
∈ Rp×q ,
1(p−i−1)×(i+2) 1(p−i−1)×(q−i−2)

where A is the block matrix B C ∈ R(i+1)×(i+2) , with B, C as follows



1(i−1)×1 0(i−1)×1
1i×i + Ii
B= 2
∈ R(i+1)×i .
−1  ∈ R(i+1)×2 , C =
01×i
0
i+2


Permuting the columns and flipping this matrix horizontally then recovers the matrices
for the other inequalities listed in (a2). Similarly, for the
P
inequality jh=1 x2h ≥ 0 listed in (a3), we use the matrix


A
13×(q−2j+2)
∈ Rp×q ,
1(p−3)×(2j−2) 1(p−3)×(q−2j+2)
where A is the block
are

2 2

B= 0 0
1 1


matrix B C D


··· 2
0


··· 0 , C = 2
··· 1
1
38

∈ R3×(2j−2) , where B, C, and D

0 ··· 0
2 · · · 2 ∈ R3×(j−2) ,
1 ··· 1

and




2 0
C = −1 3 ∈ R3×2 .
2 0

Here, permuting the rows and flipping the matrix along its vertical axis produces the remaining desired matrices. Collectively, these matrices combined
with Lemma 10 complete the proof.

Lemma 11. Suppose that [cij ] ∈ R(p+1)×(q+1) satisfies all of (v1), (v3a),
and (v3b) as well as the equalities
c0k = 0, cpk =

k
h
, ch0 = 0, chq = for all h ∈ hpi, k ∈ hqi.
q
p

Then [cij ] ∈ CDQp,q .
Proof. Let us consider C = [cij ] ∈ R(p+1)×(q+1) that satisfies all of the
inequalities (v1), (v3a), and (v3b) as well as those equalities stated in the
lemma. Then C satisfies the equalities (q1). The proof of Lemma 9 also
shows that C meets the following requirements for i ∈ hp−1i and j ∈ hq −1i.
a

(1) c1,j+1 − c1,j ≥ 0,

(2) ci+1,1 − ci,j ≥ 0

b. (1) cp−1,j+1 − cp−1,j ≤ 1q , (2) ci+1,q−1 − ci+1,q−1 ≤

1
p

Conditions iv.(a) and (b) of Lemma 9 are equivalent to
cp,j+1 − cp−1,j+1 ≥ cp,j − cp−1,j

and

ci+1,p − ci+1,p−1 ≥ ci,p − ci,p−1 .

Hence, from iv.(b) of Lemma 9 it results the following chain of inequalities.
cp−1,q − cp−1,q−1 ≥ . . . ≥ ci+2,q − ci+2,q−1 ≥ ci,q − ci,q−1 ≥ . . . ≥ c1,q − c1,q−1 .
Now, combining the last relationships with (v1) and (v3b), one obtains that
for every i ∈ [p − 1], j ∈ [q − 1]
1
q

≥(v1) cp−1,q − cp−1,q−1 ,
≥iv.(b) ci,q − ci,q−1 ,
≥(v3b) ci,j+1 − ci,j ,
≥ ci,j − ci,j−1 ,
≥(v1) 0,

which proves (q2b). Conditions (q2a) can be derived analogously. Therefore,
C ∈ CDQp,q .
39

7.4. Proof of Theorem 4.
By Lemma 11, we know that the minimal H-representation of CDQp,q
is contained within the collection of inequalities (a1),(a3a), and (a3b). We
here show that the inequalities in the list (a1),(a3a), and (a3b) are exactly
the minimal H-representation of CDQp,q . In particular, we identify (p × q)(ij)
(ij)
matrices Mpq = [bij ], and Hpq = [hij ] for i ∈ [p] and j ∈ [q] such that
(11)

Case (a1). for every p and q, Mpq satisfies all inequalities in the list
(a1), (a3a), and (a3b) except for inequality of the type b11 ≥ 0.
j
k
(ij)
Case (a3a). for every i ∈ [p − 1] and 1 ≤ j ≤ q+1
, Hpq satisfies all
2
inequalities in the list (a1), (a3a), and (a3b) except for one inequality
j
j
P
P
of the type
bi+1h ≥
bih .
h=1

h=1

As shown in Theorem 1’s proof, the matrices we shall identify suffice to
prove the thesis as the other inequalities of (a1), (a3a), and (a3b) can be
(11)
(ij)
obtained from Mpq and Hpq via suitable transformations.
To obtain the thesis it is sufficient to notice that the polytope CDQpq
contains UDC pq . Thus, the matrices A and C1 to C9 of Theorem 1’sj proof
k
(11)

(ij)

.
are of the type Mpq and Hpq for every i ∈ [p − 1] and 1 ≤ j ≤ q+1
2
Hence the inequalities (a1),(a3a), and (a3b) are all needed to bound CDQpq .

7.5. Proof of Theorem 5.
Lemma11 shows each C ∈ CDQp,q to be a discrete quasi-copula. According to (Quesada Molina and Sempi, 2005, Theorem 2.3) the checkerboard
extension C̃ of C defined as
C̃(u, v) = (1−λu )(1−µv )ci,j +(1−λu)µv ci,j+1 +λu (1−µv )ci+1,j +λu µv ci+1,j+1
where

i
p

≤u≤
λu =

i+1 j
p , q

(

≤v≤

j+1
q ,

(u − pi )p u >
1
u=

i
p
i
p

and
and µv =

(

(v − qj )q v >
1
v=

j
q
j
q

is a quasi-copula on [0, 1]2 whose restriction on Ip × Iq is C. Following the
same arguments of the proof of Theorem 2, one can check that any arbitrary
horizontal section Ca : u 7→ C̃(u, a), with a ∈ [0, 1], is a convex function.
This also works analogously for any arbitrary vertical section.

40

Appendix C: Proofs for Section 5
Lemma 12. Let τ : Rp×q −→ Rp×q denote the linear map taking the standard basis vectors {eij : i ∈ [p], j ∈ [q]} to
P
Pi
i

for i ∈ [p − 1], j ∈ [q − 1],

k=1 ekj+1
`=1 ekj −


Pq e − Pq e
for i ∈ [p − 1], j = q,
ik
k=1 i+1k
τ (eij ) := Pk=1
Pj
j

for i = p, j ∈ [q − 1],

k=1 ep−1k −
k=1 epk


e
for i = p, j = q.
pq

Then τ is an invertible map with determinant (−1)q−1 q p−2 .

Proof. To prove this lemma we will use the matrix representation of τ and
observe that it has a desirable block form from which we can deduce the
claimed statements. Let M = [mij ] denote that matrix representation of
τ with respect to the standard basis vectors ordered lexicographically from
smallest-to largest along both the rows and columns. (Recall that the lexicographic ordering states that eij < est if and only if i < s or i = s and
j < t.) Define the matrices Dn , Fn , Rn , Kn and Ln by


if i = j or j = n,
1
dij := −1 if i + 1 = j,


0
otherwise,


if i = j and j < n,
1
rij := −1 if i + 1 = j,


0
otherwise,
(
1 if i ≤ j and j < n,
kij :=
0 otherwise,


if i = j = n,
1
fij := −1 if i ≤ j and j < n,


0
otherwise,
(
−1 if j = n,
`ij :=
0
otherwise,
Let Mk denote the block matrix consisting of rows kq + 1, . . . , (k + 1)q for
k = 0, 1, . . . , p − 1. Then for k ∈ [p − 3]

Mk = 0q · · · 0q Lq Dq Rq · · · Rq 0q ,
| {z }
| {z }
k−1 times

p−k−2 times

41

and
M0 = Dq Rq · · ·
Mp−2 = 0q 0q · · ·
Mp−1 = 0q 0q · · ·


Rq 0q ,


0q Lq Dq Kq ,

0q Lq Fq .

e n, R
en , K
e n , and Fen where
Now define the matrices D


1 if i = j and j < n,
e
dij := i if j = n,


0 otherwise,
(
1 if i = j and j < n,
reij :=
0 otherwise,


j if i ≥ j and j < n,
e
kij := i if i < j and j < n,


0 otherwise,


−1 + qj if i ≥ j and j < n,



j
if i < j and j < n,
e
fij := q

1
if i = j = n,



0
otherwise.

Via row reduction, we can reduce M0 to

f0 := D
eq R
eq · · ·
M


eq 0q ,
R

f0 to reduce M1 to
and so we can use the final row of M


f1 := 0q D
eq R
eq · · · R
e q 0q .
M

It then follows by induction that for k = 2, . . . , p − 3 the matrix Mk is
reducible to


fk := 0q · · · 0q D
eq R
eq · · · R
eq 0q ,
M

and that the blocks Mp−2 and Mp−1 , respectively, are reducible to


fp−2 := 0q · · · 0q D
eq K
e q , and
M


fp−1 := 0q · · · 0q Feq .
M
42

From here, basic row reductions can
the upper triangular matrix

−1 −1 · · ·
 0 −1

 ..
..
..
 .
.
.


.
..


0
0 ···
0
0 ···

be applied to reduce the block Feq to

−1 −1 −1
−1 −1 −1

..
.. 
.
. 

..
..  .
..
.
.
. 

0 −1 −1
1
0
0
q

We may then compute the determinant of M to be
det(M ) = det(Feq ) ·

p−2
Y

k=0

e q ) = (−1)q−1 q p−2 .
det(D

In particular, since det(M ) 6= 0, we conclude that τ is invertible.
7.6. Proof of Theorem 7.
In the following, we work with the polytope UDC p,q . However, the same
argument works for CDQp,q . So as to apply Theorem 6, we must show that
(p+s)(q+t) facet-defining inequalities of UDC((qp , ts ), (st , pq )) with linearly
independent facet-normals are active on B ⊕ D. Notice that since B and
D are submatrices of B ⊕ D, then the pq and st (respectively) inequalities
that are active on each of B and D and have linearly independent normal
vectors all yield active inequalities on B ⊕ D that have linearly independent
normal vectors. There are also pt inequalities of the form
i
X
k=1

ekj −

i
X

ekj−1 ≥ 0

k=1

that are active on the submatrix 0p,t of B ⊕ D, and there are sq inequalities
contained in the list
P
P
(1) Pik=1 eki − Pik=1 ekj+1 ≤ 0 for i ∈ [p + s − 1], j ∈ [q + t − 1],
q
(2)
eik − qk=1 ei+1k ≤ 0 for i ∈ [p + s − 1],
Pk=1
Pj
j
(3)
k=1 ep+s−1k −
k=1 ep+sk ≤ 0 for j ∈ [q + t − 1],
(4) epq ≥ 0,

that are active on the submatrix 0s,q of B ⊕ D. These can be seen to have
linearly independent facet-normals from those given by the submatrices B
and D. Moreover, by Lemma 12, all such inequalities have linearly independent facet-normals from one another. Thus, we conclude that B ⊕ D is a
vertex of UDC((qp , ts ), (st , pq )).

43

7.7. Proof of Corollary 3.
To prove this corollary, we first recall that a (weak) composition of a
positive integer p ∈ Z>0 with k parts is a sum c1 + c2 + · · · + ck = p,
in which the order of the summands c1 , . . . , ck ∈ Z>0 matters. It follows
that if C ∈ Rp×p is a decomposable vertex of UDCp , then there exists a
composition c1 + c2 + · · · + ck = p such that there are indecomposable
matrices C1 ∈ IDc1 , . . . , Ck ∈ IDck such that
C = C1 ⊕ · · · ⊕ Ck .
It then follows that
D(x) =

X
k≥0

=

X


k
X

| ID` |x`  ,
`≥0

(ID(x))k ,

k≥0

=

X

(V (x) − D(x))k ,

k≥0

=

1
.
1 + D(x) − V (x)

From this it is quick to conclude that
V (x) =

D(x)2 + D(x) − 1
.
D(x)

In a similar fashion, the inequality follows.



Appendix D: Proofs for Section 6
7.8. Proof of Proposition 4.
(i) ⇒ (ii) We consider Cpq ∈ SAF(ũ, ṽ). For every i ∈ hpi, j ∈ hqi, we can
take Cpq to a (p × q) matrix [xij ] through the following linear transformation
xij = pq(cij + ci−1 j−1 − ci−1 j − ci j−1 ).
We here show that the new constructed matrix [xij ] lies in the transportation polytope T (u, v) whose margins are the vectors u ∈ Rp and v ∈ Rq ,
such that for every i ∈ [p], ui := ũi − ũi−1 , and j ∈ [q], vj := ṽj − ṽj−1 .
Indeed, condition (AF2) implies that xij ≥ 0 for every i ∈ hpi, j ∈ hqi. By
44

Pq
construction, one has that
Pp h=1 xih = pq(ciq − ci−1 q ) = ũi − ũi−1 = ui .
Similarly, it follows that `=1 x`j = vj . Hence, the thesis.
(i) ⇐ (ii) We here verify that every Cpq defined as in equation (4) belongs
p
q
to the set SAF(ũ, ṽ), with margins given by the vectors
Pi ũ ∈ R and ṽ ∈ R ,
whose values are defined for every i ∈ [p], as ũi := `=1 u` , and for j ∈ [q],
P
as ṽj := jh=1 vh . Clearly, any such matrix Cpq satisfies condition (AF2).
Since the empty sum equals zero by convention, (AF1a) holds as well. It
remains to show the validity of (AF1b). From equation (4), one has that
cpj

j
p
j
j+1
1 XX
1 X
1 X
=
x`h =
vh <
vh = cp j+1
pq
pq
pq
`=1 h=1

h=1

h=1

A similar argument applied to the columns completes the proof.



7.9. Proof of Proposition 5.
(i) ⇒ (ii) We consider Cpq ∈ ASA(ũ, ṽ). For every i ∈ hpi, j ∈ hqi, we can
take Cpq to a (p × q) matrix [xij ] through the following linear transformation
xij = pq(cij + ci−1 j−1 − ci−1 j − ci j−1 ).
The new constructed matrix [xij ] lies in the alternating transportation polytope A(u, v) whose margins are the vectors u ∈ Rp and v ∈ Rq , such that
for every i ∈ [p], ui := ũi − ũi−1 , and j ∈ [q], vj := ṽj − ṽj−1 . According
to Proposition 4’s proof, one can derive the marginal P
constraints of [xij ]
from (AF1a) and (AF1b). It remains to verify that 0 ≤ i`=1 x`j ≤ vj , and
P
0 ≤ jh=1 xih ≤ ui , for every i ∈ hpi, j ∈ hqi. It is useful to observe that
Pi
Pi
`=1 (c`j + c`−1 j−1 − c`−1 j − c`j−1 ) = pq(cij − ci j−1 ). We now
`=1 x`j = pq
notice that for every i ∈ hpi and j P
∈ hqi, one has (cij −ci j−1 −c0j +c0j−1 ) ≥ 0,
from (AF2b) and (AF1a). Hence i`=1 x`j ≥ 0. Moreover, from (AF2b) and
(AF1b),
Pi one has (ci j−1 −cij −cpj−1 +cpj ) ≥ 0. Thus, cij −ci j−1 ≤ cpj −cpj−1
and `=1 x`j ≤ ṽj − ṽj−1 = vj . The remaining conditions on the row sums
can be derived in a similar fashion.
(i) ⇐ (ii) We now prove that every Cpq defined as in equation (5) belongs
p
q
to the set ASA(ũ, ṽ), with margins given by the vectors
Pi ũ ∈ R and ṽ ∈ R ,
whose values are defined for every i ∈ [p], as ũi := `=1 u` , and for j ∈ [q],
P
as ṽj := jh=1 vh . Conditions (AF1a) and (AF1b) can be derived according
to Proposition 4’s proof. We notice that ci1 j1 + ci2 j2 − ci1 j2 − ci2 j1 can be
expressed as
j1
i1 X
X
`=1 h=1

x`h +

j2
i2 X
X
`=1 h=1

x`h −

j2
i1 X
X
`=1 h=1

45

x`h −

j1
i2 X
X
`=1 h=1

x`h .

Pi2
Hence, the above
`=1 (x` j1 +1 + . . . + x` j2 ), when
Pp formulation becomes
i1 = 0, and
(x
+
.
.
.
+
x
),
if i2 = p. In either case, the
` j1 +1
` j2
`=i1 +1
sums are nonnegative. In similar way, one can derive the cases j2 = q and
j1 = 0.


46

