# Support of extremal doubly stochastic arrays

Mark Etkind  Department of Mathematics, Bar-Ilan University, Ramat-Gan
5290002, Israel<EMAIL_ADDRESS>and  Nir Lev  Department of
Mathematics, Bar-Ilan University, Ramat-Gan 5290002, Israel
<EMAIL_ADDRESS>
(Date: July 17, 2022)

###### Abstract.

An $n\times m$ array with nonnegative entries is called _doubly stochastic_ if
the sum of its entries at each column is $n$ and at each row is $m$. The set
of all $n\times m$ doubly stochastic arrays is a convex polytope with finitely
many extremal points. The main result of this paper characterizes the possible
sizes of the supports of all extremal $n\times m$ doubly stochastic arrays. In
particular we prove that the minimal size of the support of an $n\times m$
doubly stochastic array is $n+m-\gcd(n,m)$. Moreover, for $m=kn+1$ we also
characterize the structure of the support of the extremal arrays.

###### Key words and phrases:

Doubly stochastic arrays, extremal matrices, Birkhoff’s theorem

###### 2010 Mathematics Subject Classification:

05B20, 05C05, 15B51

Research supported by ISF Grant No. 1044/21 and ERC Starting Grant No. 713927.

##  1\. Introduction

### 1.1.

An $n\times m$ matrix $A=(a_{ij})$ is called a _doubly stochastic array_ (with
uniform marginals) if its entries are nonnegative, $a_{ij}\geqslant 0$, and

$\sum_{i=1}^{n}a_{ij}=n,\quad 1\leqslant j\leqslant m,$ (1.1)
$\sum_{j=1}^{m}a_{ij}=m,\quad 1\leqslant i\leqslant n,$ (1.2)

that is, the sum of the entries at each column is $n$ and at each row is $m$.

For example (see [Car96, p. 65]), the two matrices

$\begin{bmatrix}3&0&0&1\\\ 0&3&0&1\\\
0&0&3&1\end{bmatrix}\quad\text{and}\quad\begin{bmatrix}1&0&0&3\\\ 2&2&0&0\\\
0&1&3&0\end{bmatrix}$ (1.3)

are $3\times 4$ doubly stochastic arrays.

We will use $\mathcal{S}_{n,m}$ to denote the set of all $n\times m$ doubly
stochastic arrays. This set is a convex polytope (of dimension $(n-1)(m-1)$)
in the linear space of all $n\times m$ matrices. Hence $\mathcal{S}_{n,m}$
coincides with the convex hull of its finitely many extremal points. We recall
that an element $A\in\mathcal{S}_{n,m}$ is _extremal_ if it cannot be
represented as a convex combination of two other elements of
$\mathcal{S}_{n,m}$ that are both different from $A$.

For _square_ $n\times n$ matrices, a classical theorem due to Birkhoff [Bir46]
characterizes the extremal doubly stochastic arrays as follows: _an array
$A\in\mathcal{S}_{n,n}$ is extremal if and only if $\frac{1}{n}A$ is a
permutation matrix_.

Let us say that two $n\times m$ matrices are _equivalent_ if one can be
transformed into the other by a permutation of rows and columns. In this
language, Birkhoff’s theorem states that up to equivalence there is only one
extremal $n\times n$ doubly stochastic array, namely, the identity matrix
times the scalar $n$.

_Nonsquare_ $n\times m$ extremal doubly stochastic arrays have been studied by
different authors, see [Car96], [Li96] and the references therein. This case
is more complicated and in general there is more than one equivalence class of
extremal arrays. For example, the two matrices in (1.3) are both extremal but
not equivalent.

### 1.2.

In [KP21, Question 7] the authors posed the following question, which arose in
connection with a tiling problem in finite abelian groups: what is the
smallest possible size of the support of a doubly stochastic $n\times m$
array?

We recall that the _support_ of an $n\times m$ matrix $A=(a_{ij})$ is the set

$\operatorname{supp}A=\\{(i,j):a_{ij}\neq 0\\}.$

In this paper we obtain a complete answer to the question above:

######  Theorem 1.1.

For all $n,m$ the minimal size of the support of an array
$A\in\mathcal{S}_{n,m}$ is equal to $n+m-\gcd(n,m)$.

This result was also obtained by M. Loukaki in [Lou22] and we acknowledge her
priority. In [KP21, Section 4] the authors established that the result holds
in the special case where either $m=kn$ or $m=kn+1$.

### 1.3.

It is known, see [Li96, Corollary 2], that an array $A\in\mathcal{S}_{n,m}$ is
extremal if and only if its support is minimal with respect to inclusion, that
is, there is no $B\in\mathcal{S}_{n,m}$ such that $\operatorname{supp}B$ is a
proper subset of $\operatorname{supp}A$. This implies that any array which
minimizes the size of the support must also be an extremal array.

For example, each one of the two $3\times 4$ matrices in (1.3) has $6=3+4-1$
nonzero entries, which is the minimal size of the support of a doubly
stochastic $3\times 4$ array. It follows that these two matrices are extremal.

One can thus pose a more general version of the question above, namely, what
are the possible sizes of the support of an extremal $n\times m$ doubly
stochastic array?

In the special case where one of $n,m$ divides the other, say, if $m=kn$, it
has been known that there is only one equivalence class of extremal $n\times
kn$ doubly stochastic arrays, and the support size of every extremal array is
$kn$, see [Car96, Proposition 4].

Our next result provides a complete answer to the question in the more
complicated case where neither one of $n,m$ divides the other. That is, the
result characterizes the possible sizes of the supports of all extremal
$n\times m$ arrays.

######  Theorem 1.2.

Assume that neither one of $n,m$ divides the other. Then any extremal array
$A\in\mathcal{S}_{n,m}$ has support size of the form

$|\operatorname{supp}A|=n+m-s$ (1.4)

where $1\leqslant s\leqslant\gcd(n,m)$. Conversely, for any integer $s$,
$1\leqslant s\leqslant\gcd(n,m)$, there exists an extremal array
$A\in\mathcal{S}_{n,m}$ whose support size is given by (1.4).

For certain special values of $n,m$ and $s$ this result was obtained in
[Lou22, Theorem 3].

### 1.4.

It follows from Theorem 1.2 that if $n,m$ are _coprime_ , then all the
extremal $n\times m$ arrays are of the same support size, namely, $n+m-1$.
Hence an array is extremal if and only if it minimizes the support size among
all the $n\times m$ doubly stochastic arrays. So in this case one can
characterize extremality by the size of the support:

######  Theorem 1.3.

Let $n,m$ be coprime. Then an array $A\in\mathcal{S}_{n,m}$ is extremal if and
only if

$|\operatorname{supp}A|=n+m-1.$ (1.5)

This result was obtained also in [Lou22] using a different approach. In the
special case where $m=kn+1$ the result was proved in [Car96, Proposition 6].

If one of $n,m$ divides the other, say, $m=kn$, then there is only one
equivalence class of extremal arrays and the support size of every extremal
array is equal to $kn$. Hence in this case an array $A\in\mathcal{S}_{n,kn}$
is extremal if and only if $|\operatorname{supp}A|=kn$.

However, for all the remaining values of $n,m$, that is, if $n,m$ are neither
coprime nor any one of them divides the other, there is no characterization of
extremality by the size of the support. One can show that the only sufficient
condition for the extremality of $A\in\mathcal{S}_{n,m}$ is
$|\operatorname{supp}A|=n+m-\gcd(n,m)$, but this condition is not necessary.

### 1.5.

A more general problem is to determine not only the possible size, but also a
structural characterization, of the support of an extremal $n\times m$ doubly
stochastic array. That is, to obtain an effective necessary and sufficient
condition for a subset $\Omega\subset\\{1,\dots,n\\}\times\\{1,\dots,m\\}$ to
be the support of some extremal $n\times m$ array.

We note that if an extremal $n\times m$ array with a given support does exist,
then it is unique, see [Li96, Theorem 1].

In this paper we solve this problem in the special case where $m=kn+1$.

######  Theorem 1.4.

Let $m=kn+1$. Then a subset
$\Omega\subset\\{1,\dots,n\\}\times\\{1,\dots,m\\}$ is the support of an
extremal array $A\in\mathcal{S}_{n,m}$ if and only if the following two
conditions hold:

  1. (i)

For each $1\leqslant i\leqslant n$, the set $\\{j:(i,j)\in\Omega\\}$ contains
exactly $k+1$ elements;

  2. (ii)

$\Omega$ does not contain any “cycle”, that is, any sequence of the form

$(i_{1},j_{1}),\;(i_{2},j_{1}),\;(i_{2},j_{2}),\;(i_{3},j_{2}),\;\dots,\;(i_{s},j_{s}),\;(i_{1},j_{s})\qquad(s\geqslant
2)$ (1.6)

where $i_{1},\dots,i_{s}$ are distinct row indices and $j_{1},\dots,j_{s}$ are
distinct column indices.

The necessity of the conditions (i), (ii) is known, see [Car96, Propositions
2, 6]. The novel part of the result is that these two conditions are also
sufficient.

For example, it is easy to check that the subset

$\Omega=\begin{bmatrix}\bullet&0&0&\bullet\\\ \bullet&\bullet&0&0\\\
0&\bullet&\bullet&0\end{bmatrix}$ (1.7)

of the $3\times 4$ array, whose elements are indicated by ‘$\bullet$’,
satisfies the conditions (i) and (ii) in Theorem 1.4 (with $n=3$ and $k=1$).
Hence $\Omega$ must be the support of some extremal array
$A\in\mathcal{S}_{3,4}$. Indeed, $A$ is the matrix on the right hand side of
(1.3).

As an application of Theorem 1.4 we find the total number of extremal
$n\times(n+1)$ doubly stochastic arrays:

######  Theorem 1.5.

The total number of extremal arrays in $\mathcal{S}_{n,n+1}$ is exactly
$n!(n+1)^{n-1}$.

### 1.6.

Loukaki posed in [Lou22, Remark 2] the following question: Do there exist two
extremal $n\times m$ doubly stochastic arrays $A,B$ whose supports are of the
least possible size $n+m-\gcd(n,m)$, and such that $A,B$ have the same set of
entries (counted with multiplicities) but $A$ and $B$ are not equivalent?

We will prove that for certain values of $n,m$ the answer is affirmative:

######  Theorem 1.6.

For any $n\geqslant 6$ there exist two extremal arrays
$A,B\in\mathcal{S}_{n,n+1}$ that have the same set of entries counted with
multiplicities, but $A$ and $B$ are not equivalent.

In fact the two arrays $A,B$ in this result are not only extremal but moreover
have supports of the least possible size, since $n$ and $n+1$ are coprime
(Theorem 1.3).

We note that the result in Theorem 1.6 does not hold for $n\leqslant 5$.

### 1.7.

The rest of the paper is organized as follows. In Section 2 we give some
preliminary background. In Section 3 we prove that the minimal size of the
support of an $n\times m$ doubly stochastic array is $n+m-\gcd(n,m)$ (Theorem
1.1). In particular we present methods for constructing doubly stochastic
arrays of minimal support size.

In Section 4 we characterize the possible sizes of the supports of all the
extremal $n\times m$ doubly stochastic arrays (Theorem 1.2). In Section 5 we
characterize the support structure of the extremal $n\times(kn+1)$ arrays
(Theorem 1.4). We then use this result in order to determine the total number
of extremal $n\times(n+1)$ arrays (Theorem 1.5).

In Section 6 we construct examples of non-equivalent extremal arrays with the
same set of entries counted with multiplicities (Theorem 1.6).

In the last Section 7 we give some motivational remarks, relating the notion
of doubly stochastic arrays to some other mathematical topics.

##  2\. Preliminaries

In this section we provide some preliminary background on doubly stochastic
arrays. First we discuss the notion of the graph associated to an $n\times m$
matrix, and then state several basic results on doubly stochastic arrays that
will be used later on.

###  2.1. The associated graph of a matrix

To every $n\times m$ matrix $A=(a_{ij})$ one can associate a weighted
(undirected) bipartite graph $G(A)=(U,V,E,w)$ defined as follows. The set of
vertices is the union of two disjoint sets $U=\\{u_{1},\dots,u_{n}\\}$ and
$V=\\{v_{1},\dots,v_{m}\\}$ (corresponding to rows and columns of $A$
respectively) which form a bipartition of the graph. The set of edges $E$
includes the edge $\\{u_{i},v_{j}\\}$ joining $u_{i}$ and $v_{j}$ if and only
if the matrix entry $a_{ij}$ is nonzero. Finally, the graph is endowed with a
weight function $w:E\to\mathbb{R}$ which assigns the (nonzero) weight $a_{ij}$
to the edge $\\{u_{i},v_{j}\\}$.

For example, Figure 2.1 shows the graphs associated to the two matrices in
(1.3).

If $x$ is any one of the vertices of the graph $G(A)$, then the sum of the
weights of all the edges incident to $x$ will be called the _weight of the
vertex $x$_.

We observe that an $n\times m$ matrix $A$ is doubly stochastic if and only if
the graph $G(A)$ has the following three properties: (i) the edges of the
graph have all positive weights; (ii) every vertex from $V$ has weight $n$;
and (iii) every vertex from $U$ has weight $m$.

$3$$3$$3$$1$$1$$1$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$u_{1}$$u_{2}$$u_{3}$

$1$$2$$3$$3$$2$$1$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$u_{1}$$u_{2}$$u_{3}$

Figure 2.1. The graphs associated to the two matrices in (1.3).

###  2.2. Basic results on extremal arrays

We collect some basic results on extremal $n\times m$ doubly stochastic arrays
that will be used in the paper.

######  Proposition 2.1 (see [Li96, Theorem 1]).

An array $A\in\mathcal{S}_{n,m}$ is extremal if and only if the two conditions
$B\in\mathcal{S}_{n,m}$, $\operatorname{supp}B=\operatorname{supp}A$ imply
that $B=A$.

######  Proposition 2.2 (see [Li96, Corollary 2]).

An array $A\in\mathcal{S}_{n,m}$ is extremal if and only if there is no array
$B\in\mathcal{S}_{n,m}$ such that $\operatorname{supp}B$ is a proper subset of
$\operatorname{supp}A$.

######  Proposition 2.3 (see [Car96, Proposition 2]).

An array $A\in\mathcal{S}_{n,m}$ is extremal if and only if the graph $G(A)$
contains no cycles.

######  Proposition 2.4.

Let $A\in\mathcal{S}_{n,m}$ be an extremal array. Then $A$ is an integer
matrix. Moreover, all the entries of $A$ are integral multiples of
$\gcd(n,m)$.

###### Proof.

Let $d=\gcd(n,m)$. Since $A$ is doubly stochastic, then for every vertex $x$
of the graph $G(A)$ the sum of the weights of all the edges incident to $x$ is
in $\mathbb{Z}d$ (since this sum is either $n$ or $m$). Hence if a vertex $x$
is incident to some edge $e$ of weight not in $\mathbb{Z}d$, then $x$ must be
incident to at least one other edge $e^{\prime}$ also of weight not in
$\mathbb{Z}d$. This implies that if $H$ is the subgraph of $G(A)$ induced by
all the edges with weights not in $\mathbb{Z}d$, then every vertex of $H$ must
have degree at least two. It follows that if $H$ is nonempty, then $H$ must
contain a cycle, which is not possible due to the extremality of the matrix
$A$ (Proposition 2.3). Thus $H$ has to be empty, that is, the weight of every
edge of $G(A)$ is in $\mathbb{Z}d$, and so all the entries of $A$ are integral
multiple of $d$. ∎

######  Proposition 2.5 (see [Car96, Proposition 4]).

If $m=kn$, then any extremal $n\times m$ doubly stochastic array is equivalent
to the block diagonal matrix

$\setcounter{MaxMatrixCols}{13}\begin{bmatrix}n&n&\cdots&n\\\
&&&&n&n&\cdots&n\\\ &&&&&&&&\ddots\\\ &&&&&&&&&n&n&\cdots&n\end{bmatrix}$
(2.1)

where in each row there are exactly $k$ nonzero entries.

The following proof is different from the one in [Car96].

###### Proof of Proposition 2.5.

By Proposition 2.4, all the entries of $A$ are integral multiples of $n$.
Since the entries are nonnegative and the sum at each column is $n$, there can
be no entry greater than $n$. Hence every nonzero entry must be equal to $n$.
Since the sum of the entries at each row is $kn$, then in each row there are
exactly $k$ nonzero entries. But in each column there can be only one nonzero
entry, since the sum at each column is $n$. Thus $A$ must be equivalent to the
matrix in (2.1). ∎

#### Remark

Notice that Birkhoff’s theorem is the case $k=1$ in Proposition 2.5.

##  3\. Arrays with minimal support size

In this section our main goal is to prove Theorem 1.1, which states that the
minimal size of the support of an $n\times m$ doubly stochastic array is
$n+m-\gcd(n,m)$.

To prove this result we will first show that the support size of any $n\times
m$ doubly stochastic array is bounded from below by the value $n+m-\gcd(n,m)$.

Then we will turn to construct examples of arrays that attain the minimal
support size. First, we will show that the problem can be reduced to the
special case when $n,m$ are _coprime_. Then, we will present two different
methods for constructing $n\times m$ doubly stochastic arrays of minimal
support size.

###  3.1. Lower bound for the support size of a doubly stochastic array

We begin by showing that an $n\times m$ doubly stochastic array cannot have
support of size smaller than $n+m-\gcd(n,m)$, which establishes the lower
bound in Theorem 1.1. In fact we will prove the following more general version
of the result, where the entries of the matrix are _not required to be
nonnegative_.

######  Theorem 3.1.

Let $A=(a_{ij})$ be an $n\times m$ complex-valued matrix satisfying (1.1) and
(1.2), that is, the sum of the entries at each column is $n$ and at each row
is $m$. Then

$|\operatorname{supp}A|\geqslant n+m-\gcd(n,m).$ (3.1)

###### Proof.

Let $G(A)=(U,V,E,w)$ be the graph of the matrix $A$, and let $r$ be the number
of connected components of $G(A)$. Since the graph has $n+m$ vertices, the
number of edges in the graph must be at least $n+m-r$ (for adding an edge to a
graph can reduce the number of connected components by at most one). So we
obtain

$|\operatorname{supp}A|=|E|\geqslant n+m-r.$ (3.2)

Let $H_{1},\dots,H_{r}$ denote the connected components of $G(A)$. For each
$1\leqslant k\leqslant r$, assume that $H_{k}$ has $n_{k}$ vertices in $U$,
and $m_{k}$ vertices in $V$. Since the sum of the weights of the edges
incident to a vertex from $U$ is $m$, and the sum of the weights of the edges
incident to a vertex from $V$ is $n$, then the sum of the weights of all the
edges of the subgraph $H_{k}$ is equal to $mn_{k}$ on one hand, and to
$nm_{k}$ on the other hand. Hence

$\frac{n_{k}}{m_{k}}=\frac{n}{m}\quad(1\leqslant k\leqslant r).$ (3.3)

Let us now write $n=dp$, $m=dq$, where $d=\gcd(n,m)$ and $p,q$ are coprime. It
follows from (3.3) that each one of $n_{1},\dots,n_{r}$ can be no smaller than
$p$. But $n_{1}+\dots+n_{r}=n$, so we must have $rp\leqslant n$, or
equivalently, $r\leqslant d$. Together with (3.2) this implies (3.1). ∎

###  3.2. Block structure of arrays with minimal support size

Now that we have established the lower bound (3.1), our next goal is to look
into the structure of the $n\times m$ doubly stochastic arrays for which an
_equality_ in (3.1) is attained. We keep using the notation and terminology
from the proof of Theorem 3.1. In particular we denote

$n=dp,\quad m=dq,\quad d=\gcd(n,m),\quad\text{$p,q$ are coprime.}$ (3.4)

Suppose that $A$ is an $n\times m$ doubly stochastic array whose support is of
size exactly $n+m-d$. Then all the inequalities in the proof above become
equalities. So the number of connected components of the graph $G(A)$ is
exactly $d$, and each connected component has exactly $p$ vertices in $U$ and
$q$ vertices in $V$. This implies that by a permutation of rows and columns we
may assume that $A$ has the structure of a block diagonal matrix consisting of
$d$ blocks of size $p\times q$ each. Moreover, for each block the sum of the
entries at each column is $n$ and at each row is $m$, so each block is equal
to the scalar $d$ times a certain $p\times q$ doubly stochastic array. That is
to say,

$A=d\times\begin{bmatrix}A_{1}\\\ &A_{2}\\\ &&\ddots\\\ &&&A_{d}\end{bmatrix}$
(3.5)

where each one of $A_{1},A_{2},\dots,A_{d}$ is a $p\times q$ doubly stochastic
array.

We also observe that the support size of each $A_{k}$ can be no smaller than
$p+q-1$, again by Theorem 3.1. So we have

$|\operatorname{supp}A|=\sum_{k=1}^{d}|\operatorname{supp}A_{k}|\geqslant
d(p+q-1)=n+m-d.$ (3.6)

Hence $|\operatorname{supp}A|=n+m-d$ implies that
$|\operatorname{supp}A_{k}|=p+q-1$ for each $1\leqslant k\leqslant d$.

It is obvious that these conditions, necessary for an $n\times m$ doubly
stochastic array to have support of size $n+m-d$, are also sufficient. That
is, suppose that we are given $d$ matrices $A_{1},A_{2},\dots,A_{d}$ such that
each $A_{k}$ is a $p\times q$ doubly stochastic array with support of size
$p+q-1$. Then the $n\times m$ matrix $A$ given by (3.5) is an $n\times m$
doubly stochastic array with support of size $n+m-d$. We have thus proved the
following:

######  Theorem 3.2.

For any $n,m$, let the numbers $d,p,q$ be defined by (3.4). Then an $n\times
m$ doubly stochastic array $A$ has support of size $n+m-d$ if and only if,
possibly after a permutation of rows and columns, $A$ has the form (3.5) where
each one of $A_{1},\dots,A_{d}$ is a $p\times q$ doubly stochastic array with
support of size $p+q-1$.

The main point of this result is that it reduces the analysis of $n\times m$
doubly stochastic arrays with minimal support size to the special case when
$n,m$ are _coprime_.

###  3.3. Constructing arrays with minimal support size

Our next goal is to prove that the lower bound (3.1) is sharp, that is, to
establish the existence of $n\times m$ doubly stochastic arrays for which an
equality in (3.1) is attained.

######  Theorem 3.3.

For any $n,m$ there exists an $n\times m$ doubly stochastic array $A$ such
that

$|\operatorname{supp}A|=n+m-\gcd(n,m).$ (3.7)

In fact we only have to prove this for coprime $n,m$, thanks to Theorem 3.2.

Below we present two different methods for constructing $n\times m$ doubly
stochastic arrays of minimal support size. We call the first one the “discrete
trapezoid method” and the second one the “Euclidean algorithm method”.

####  3.3.1. The discrete trapezoid method

Let $\mathbb{Z}_{nm}$ be the additive group of residue classes modulo $nm$,
and let $\chi_{k}$ denote the indicator function of the subset
$\\{0,1,\dots,k-1\\}$ of $\mathbb{Z}_{nm}$. We consider a function
$\tau:\mathbb{Z}_{nm}\to\mathbb{R}$ defined as the convolution

$\tau(t)=(\chi_{n}\ast\chi_{m})(t)=\sum_{s\in\mathbb{Z}_{nm}}\chi_{n}(t-s)\chi_{m}(s),\quad
t\in\mathbb{Z}_{nm}.$ (3.8)

By a straightforward calculation one can verify that

$\tau(t)=\min\\{t+1,n+m-t-1,n,m\\},\quad 0\leqslant t\leqslant n+m-2,$ (3.9)

and

$\tau(t)=0,\quad n+m-1\leqslant t\leqslant nm-1.$ (3.10)

We call $\tau$ the _discrete trapezoid_ function on the group
$\mathbb{Z}_{nm}$.

For example, in Figure 3.1 the discrete trapezoid function is shown for $n=5$,
$m=7$.

$\scriptscriptstyle 0$$\scriptscriptstyle 1$$\scriptscriptstyle
2$$\scriptscriptstyle 3$$\scriptscriptstyle 4$$\scriptscriptstyle
5$$\scriptscriptstyle 6$$\scriptscriptstyle 7$$\scriptscriptstyle
8$$\scriptscriptstyle 9$$\scriptscriptstyle 10$$\scriptscriptstyle
11$$\scriptscriptstyle 12$$\scriptscriptstyle 13$$\scriptscriptstyle
14$$\scriptscriptstyle 15$$\scriptscriptstyle 16$$\scriptscriptstyle
17$$\scriptscriptstyle 18$$\scriptscriptstyle 19$$\scriptscriptstyle
20$$\scriptscriptstyle 21$$\scriptscriptstyle 22$$\scriptscriptstyle
23$$\scriptscriptstyle 24$$\scriptscriptstyle 25$$\scriptscriptstyle
26$$\scriptscriptstyle 27$$\scriptscriptstyle 28$$\scriptscriptstyle
29$$\scriptscriptstyle 30$$\scriptscriptstyle 31$$\scriptscriptstyle
32$$\scriptscriptstyle 33$$\scriptscriptstyle 34$$\scriptstyle 1$$\scriptstyle
2$$\scriptstyle 3$$\scriptstyle 4$$\scriptstyle 5$$\scriptstyle
5$$\scriptstyle 5$$\scriptstyle 4$$\scriptstyle 3$$\scriptstyle
2$$\scriptstyle 1$ Figure 3.1. The discrete trapezoid function for $n=5$,
$m=7$.

Now assume that $n,m$ are _coprime_. We denote by $\mathbb{Z}_{n}$ and
$\mathbb{Z}_{m}$ the additive groups of residue classes modulo $n$ and $m$
respectively. By the Chinese remainder theorem there is a group isomorphism
$\varphi:\mathbb{Z}_{nm}\to\mathbb{Z}_{n}\times\mathbb{Z}_{m}$ given by
$\varphi(t)=(t\,\operatorname{mod}\,n,\,t\,\operatorname{mod}\,m)$. This
isomorphism allows us to lift the discrete trapezoid function $\tau$ to a new
function

$A:\mathbb{Z}_{n}\times\mathbb{Z}_{m}\to\mathbb{R}$ (3.11)

defined by $A(\varphi(t))=\tau(t)$, $t\in\mathbb{Z}_{nm}$. We use (3.11) as an
alternative way to represent a real $n\times m$ matrix $A$, in which the rows
of the matrix are indexed by residue classes modulo $n$, while the columns
indexed by residue classes modulo $m$.

We claim that the matrix $A$ thus constructed is doubly stochastic. To see
this, let $H_{k}$ denote the subgroup of $\mathbb{Z}_{nm}$ generated by the
element $k$. We then observe that the discrete trapezoid function $\tau$
_tiles_ the group $\mathbb{Z}_{nm}$ by translations along each one of the two
subgroups $H_{n}$ and $H_{m}$. That is to say,

$\sum_{s\in H_{n}}\tau(t-s)=m,\quad\sum_{s\in H_{m}}\tau(t-s)=n,\quad
t\in\mathbb{Z}_{nm}.$ (3.12)

This can be verified directly using the definition (3.8) of the function
$\tau$.

We next observe that the isomorphism $\varphi$ maps the subgroup $H_{n}$ of
$\mathbb{Z}_{nm}$ onto the subgroup $\\{0\\}\times\mathbb{Z}_{m}$ of
$\mathbb{Z}_{n}\times\mathbb{Z}_{m}$. Hence for each $i\in\mathbb{Z}_{n}$, the
set $\\{(i,j):j\in\mathbb{Z}_{m}\\}$ is the image under $\varphi$ of a certain
coset of $H_{n}$ in $\mathbb{Z}_{nm}$, say, the coset $a_{i}-H_{n}$. It
follows that

$\sum_{j\in\mathbb{Z}_{m}}A(i,j)=\sum_{s\in H_{n}}\tau(a_{i}-s)=m,$ (3.13)

where in the last equality we used (3.12). In a similar way, $\varphi$ maps
the subgroup $H_{m}$ onto $\mathbb{Z}_{n}\times\\{0\\}$, so for each
$j\in\mathbb{Z}_{m}$ the set $\\{(i,j):i\in\mathbb{Z}_{n}\\}$ is the image
under $\varphi$ of a coset $b_{j}-H_{m}$, and we obtain

$\sum_{i\in\mathbb{Z}_{n}}A(i,j)=\sum_{s\in H_{m}}\tau(b_{j}-s)=n,$ (3.14)

again using (3.12). Since the values of $A$ are clearly nonnegative, we
conclude from (3.13) and (3.14) that $A$ is a doubly stochastic array.

We note that the correspondence between the $n\times m$ doubly stochastic
arrays and the nonnegative functions which tile the group $\mathbb{Z}_{nm}$ by
translations along each one of the two subgroups $H_{n}$ and $H_{m}$ (where
$n,m$ are coprime) was pointed out in an earlier version of [KP21].

Finally we notice, using (3.9) and (3.10), that

$|\operatorname{supp}A|=|\operatorname{supp}\tau|=n+m-1,$ (3.15)

so that the support of $A$ is of the smallest possible size according to
Theorem 3.1.

For example, in the case $n=5$, $m=7$ we obtain the matrix

$\begin{bmatrix}1&&&1&&5\\\ &2&&&&&5\\\ 4&&3\\\ &3&&4\\\ &&2&&5\end{bmatrix}$
(3.16)

which is a $5\times 7$ doubly stochastic array that has $11=5+7-1$ nonzero
entries.

One other example is the matrix on the right hand side of (1.3), which is
obtained by the discrete trapezoid method for $n=3$, $m=4$.

####  3.3.2. The Euclidean algorithm method

We now turn to describe our second method for constructing $n\times m$ doubly
stochastic arrays of minimal support size. The same method was proposed also
in [Lou22].

Assume that $n\leqslant m$, and write

$m=kn+r,\quad k\geqslant 1,\quad 0\leqslant r\leqslant n-1.$ (3.17)

If $r=0$ then $m=kn$, and in this case we already know from Proposition 2.5
how to construct an $n\times m$ doubly stochastic array of the minimal support
size $kn$.

In the remaining case $1\leqslant r\leqslant n-1$ we proceed by induction as
follows. We first use the inductive hypothesis to find an $r\times n$ doubly
stochastic array $B$ of support size $r+n-\gcd(r,n)$. Next, let $D_{n}$ denote
the $n\times n$ identity matrix times the scalar $n$, that is, $D_{n}$ is an
$n\times n$ diagonal matrix whose main diagonal entries are all equal to $n$.
We then construct an $n\times m$ matrix $A$ given by

$A=\begin{bmatrix}D_{n}&D_{n}&\cdots&D_{n}&B^{\top}\end{bmatrix},$ (3.18)

that is, $A$ is obtained by horizontally concatenating $k$ copies of $D_{n}$
and the transpose of the matrix $B$. Then $A$ has nonnegative entries and the
sum of the entries at each column is $n$ and at each row is $m$. Hence $A$ is
an $n\times m$ doubly stochastic array.

It remains to find the size of the support of $A$. We have

$|\operatorname{supp}A|=k|\operatorname{supp}D_{n}|+|\operatorname{supp}B|=kn+r+n-\gcd(r,n).$
(3.19)

But $kn+r=m$ and $\gcd(r,n)=\gcd(n,m)$, so we conclude from (3.19) that

$|\operatorname{supp}A|=m+n-\gcd(n,m),$ (3.20)

which is indeed the smallest possible support size.

For example, applying this algorithm for $n=5$, $m=7$ yields the matrix

$\begin{bmatrix}5&&&&&2&\\\ &5&&&&&2\\\ &&5&&&2&\\\ &&&5&&&2\\\
&&&&5&1&1\end{bmatrix}$ (3.21)

which is a $5\times 7$ doubly stochastic array with support of size
$11=5+7-1$.

One more example is the matrix on the left hand side of (1.3), which is
obtained by the Euclidean algorithm method for $n=3$, $m=4$.

####  3.3.3. Remarks

In general, the discrete trapezoid method and the Euclidean algorithm method
may yield different, and in fact non-equivalent, doubly stochastic arrays. For
example, the $5\times 7$ matrices in (3.16) and (3.21), obtained by the two
different methods, are obviously not equivalent to each other.

We also point out that when performing the Euclidean algorithm method for
$n,m$ coprime, we may choose at any stage of the induction to use the discrete
trapezoid method rather than continue further with the inductive process. In
this way one can obtain more examples of $n\times m$ doubly stochastic arrays
of minimal support size.

##  4\. Extremal arrays with non-minimal support size

In this section we prove Theorem 1.2 that characterizes the possible sizes of
the supports of all extremal $n\times m$ arrays. Recall that the theorem
asserts that if neither one of $n,m$ divides the other, then any extremal
$A\in\mathcal{S}_{n,m}$ has support size of the form

$|\operatorname{supp}A|=n+m-s,$ (4.1)

where

$1\leqslant s\leqslant\gcd(n,m).$ (4.2)

Moreover, this condition is sharp, that is, for any integer $s$ satisfying
(4.2) there exists an extremal array $A\in\mathcal{S}_{n,m}$ whose support
size is given by (4.1)

(The reader is reminded that this is no longer true if one of $n,m$ does
divide the other. In fact, if $m=kn$ then every extremal array in
$\mathcal{S}_{n,kn}$ has support of size $kn$, by Proposition 2.5.)

###  4.1. Estimating the support size of an extremal array

We first show that the conditions (4.1) and (4.2) hold for any extremal
$n\times m$ doubly stochastic array.

######  Theorem 4.1.

For all $n,m$ the support size of any extremal array in $\mathcal{S}_{n,m}$ is
of the form $n+m-s$, where $1\leqslant s\leqslant\gcd(n,m)$.

###### Proof.

By Theorem 3.1 we know that every $A\in\mathcal{S}_{n,m}$ has support of size
no less than $n+m-\gcd(n,m)$. Now let $A$ be extremal, then by Proposition 2.3
the graph $G(A)$ contains no cycles. Since the graph has $n+m$ vertices, this
implies that the number of edges in the graph must be $n+m-r$, where $r$ is
the number of connected components of the graph. Hence $\operatorname{supp}A$
is of size $n+m-r$, which can be no greater than $n+m-1$. ∎

###  4.2. Constructing extremal arrays of given support size

Next we turn to prove that if neither one of $n,m$ divides the other, then the
estimate given in Theorem 4.1 is sharp. That is, we will construct examples of
extremal $n\times m$ doubly stochastic arrays whose support sizes attain all
values of the form $n+m-s$, where $1\leqslant s\leqslant\gcd(n,m)$.

######  Theorem 4.2.

Assume that neither one of $n,m$ divides the other. Then for any $s$ such that
$1\leqslant s\leqslant\gcd(n,m)$, there exists an extremal array
$A\in\mathcal{S}_{n,m}$ whose support is of size $n+m-s$.

Our proof consists of two parts. In the first part, which is the key one in
the proof, we establish the result in the special case where $\gcd(n,m)=m-n$.
Then in the second part we use the Euclidean algorithm method to extend the
result to the general case.

#### 4.2.1.

The key part of our construction is performed in the following lemma:

######  Lemma 4.3.

Let $n=dp$, $m=d(p+1)$, where $d>1$, $p>1$. Then for any $1\leqslant
s\leqslant d-1$, there is an extremal array $A\in\mathcal{S}_{n,m}$ whose
support is of size $n+m-s$.

###### Proof.

It will be more convenient to construct the matrix $B=d^{-1}\times A$ (recall
that by Proposition 2.4 all the entries of $A$ must be integral multiples of
$d$, so that $B$ would be an integer matrix). We will obtain the matrix $B$ by
constructing its associated graph $G(B)=(U,V,E,w)$. The graph $G(B)$ will be
decomposed from a system of $d$ weighted bipartite subgraphs
$G_{j}=(U_{j},V_{j},E_{j},w_{j})$, $1\leqslant j\leqslant d$, together with
additional edges that join vertices between these subgraphs.

The subgraphs $G_{1},\dots,G_{d}$ will be constructed from four basic graph
prototypes that will be now introduced. Each prototype is a weighted bipartite
graph containing no cycles and such that the edges have positive weights.
Furthermore, the weight of each $U$-vertex is $p+1$ and the weight of each
$V$-vertex is $p$, with possibly the exception of certain “special” vertices
whose weight has deficiency one. That is, a special $U$-vertex has weight $p$
and a special $V$-vertex has weight $p-1$.

The four graph prototypes are illustrated in Figures 4.1 and 4.2. The first
prototype, type I, has $p-1$ vertices in $U$ and $p$ vertices in $V$, and has
one special $V$-vertex. The second, type II, has $p+1$ vertices in $U$ and
$p+2$ vertices in $V$, and has one special $U$-vertex. Types III and IV have
$p$ vertices in $U$ and $p+1$ vertices in $V$, but type III has one special
$U$-vertex and one special $V$-vertex, while type IV has no special vertices.

$p$$1$$p-1$$2$$p-2$$p-1$$2$$p-2$$3$$p-3$$4$$\vdots$$\vdots$$v_{p}$$v_{p-1}$$v_{p-2}$$v_{p-3}$$u_{p-1}$$u_{p-2}$$u_{p-3}$$v_{1}$$v_{2}$$v_{3}$$u_{1}$$u_{2}$$u_{3}$

$p$$1$$p-1$$2$$p-2$$p$$1$$p-1$$1$$p-1$$2$$p-2$$3$$p-3$$4$$\vdots$$\vdots$$v_{p+2}$$v_{p+1}$$v_{p}$$v_{p-1}$$v_{p-2}$$v_{p-3}$$u_{p+1}$$u_{p}$$u_{p-1}$$u_{p-2}$$u_{p-3}$$v_{1}$$v_{2}$$v_{3}$$u_{1}$$u_{2}$$u_{3}$

Figure 4.1. Graph prototypes of type I (left) and type II (right).

$p$$1$$p-1$$2$$p-2$$p-1$$1$$p-1$$2$$p-2$$3$$p-3$$4$$\vdots$$\vdots$$v_{p+1}$$v_{p}$$v_{p-1}$$v_{p-2}$$v_{p-3}$$u_{p}$$u_{p-1}$$u_{p-2}$$u_{p-3}$$v_{1}$$v_{2}$$v_{3}$$u_{1}$$u_{2}$$u_{3}$

$p$$1$$p-1$$2$$p-2$$p$$1$$p-1$$2$$p-2$$3$$p-3$$4$$\vdots$$\vdots$$v_{p+1}$$v_{p}$$v_{p-1}$$v_{p-2}$$v_{p-3}$$u_{p}$$u_{p-1}$$u_{p-2}$$u_{p-3}$$v_{1}$$v_{2}$$v_{3}$$u_{1}$$u_{2}$$u_{3}$

Figure 4.2. Graph prototypes of type III (left) and type IV (right).

We now use these four graph prototypes to construct the subgraphs
$G_{1},\dots,G_{d}$ as follows. We first let $G_{1}$ be a graph of type I.
Next, for each $2\leqslant j\leqslant d-s$ we let $G_{j}$ be a graph of type
III (in the case $s=d-1$ there will be no subgraphs of type III). Then, we let
$G_{d-s+1}$ be a graph of type II. Finally, for each $d-s+2\leqslant
j\leqslant d$ we let $G_{j}$ be a graph of type IV (if $s=1$, there will be no
subgraphs of type IV).

Next, we connect the first $d-s+1$ subgraphs $G_{1},\dots,G_{d-s+1}$ by adding
edges between them as follows. For each $1\leqslant j\leqslant d-s$, we add an
edge of weight one joining the special $V$-vertex of $G_{j}$ to the special
$U$-vertex of $G_{j+1}$. In this way, the subgraphs $G_{1},\dots,G_{d-s+1}$
together with the new edges become a single connected component. Note that we
do not add any edges to the subgraphs $G_{j}$ for $d-s+2\leqslant j\leqslant
d$.

This construction yields a weighted bipartite graph $G=(U,V,E,w)$ with edges
of positive weights, that has $dp=n$ vertices in $U$ and $d(p+1)=m$ vertices
in $V$. Moreover, the weight of each $U$-vertex is $p+1$ and the weight of
each $V$-vertex is $p$, with no exceptions (since by adding the new edges we
have increased the weight of every special vertex by exactly one, so that in
the final graph the special vertices have no weight deficiency). We therefore
have $G=G(B)$ for a certain $n\times m$ matrix $B$, such that $A:=d\times B$
is an $n\times m$ doubly stochastic array.

Finally, we note that by our construction the graph $G(B)$, and hence also the
graph $G(A)$, contains no cycles. This implies that $A$ is extremal by
Proposition 2.3. Since the graph $G(A)$ has $n+m$ vertices, this also implies
that the number of edges must be $n+m-r$, where $r$ is the number of connected
components of the graph. But $G(A)$ has exactly $s$ connected components, so
that $|\operatorname{supp}A|=|E|=n+m-s$ as required. ∎

#### 4.2.2.

As an example, if $d=3$, $p=2$, $s=1$, then the proof of Lemma 4.3 yields the
$6\times 9$ doubly stochastic array

$3\times\begin{bmatrix}2&1\\\ &&2&1\\\ &1&&1&1\\\ &&&&&2&1\\\ &&&&1&&1&1\\\
&&&&&&&1&2\\\ \end{bmatrix}$ (4.3)

which is extremal and has support of the maximal size $6+9-1=14$, while we
know that the minimal support size of a $6\times 9$ doubly stochastic array is
$6+9-3=12$.

#### 4.2.3.

Next, we turn to complete the proof of Theorem 4.2 by extending the result to
all values of $n,m$ such that neither one divides the other. The argument uses
the Euclidean algorithm method to reduce the problem to the case covered by
Lemma 4.3.

###### Proof of Theorem 4.2.

Let $d=\gcd(n,m)$. If $s=d$ then the result is a consequence of Theorem 3.3,
so we may suppose that $1\leqslant s\leqslant d-1$. In particular this means
that $d>1$, that is, $n,m$ are not coprime. The construction is done by
induction.

Assume that $n\leqslant m$, and write

$m=kn+r,\quad k\geqslant 1,\quad 0\leqslant r\leqslant n-1.$ (4.4)

The remainder $r$ is an integral multiple of $d$. We observe that $r$ cannot
be zero, since $n$ does not divide $m$ by assumption. Hence we must have
$d\leqslant r\leqslant n-1$.

The induction base case is when $k=1$ and $r=d$. In this case we have $n=dp$,
$m=d(p+1)$ for some integer $p$ which must be at least two (since $n$ does not
divide $m$), and so the result follows from Lemma 4.3.

If we have either $k\geqslant 2$, or $k=1$ and $d+1\leqslant r\leqslant n-1$,
then we proceed by induction as follows. Suppose that we can find an extremal
$B\in\mathcal{S}_{n,m-n}$ of support size $m-s$. Let $D_{n}$ be the $n\times
n$ identity matrix times the scalar $n$, and let
$A=\begin{bmatrix}D_{n}&B\end{bmatrix}$ be the $n\times m$ matrix obtained by
horizontally concatenating $D_{n}$ and $B$. Then $A\in\mathcal{S}_{n,m}$ and

$|\operatorname{supp}A|=|\operatorname{supp}D_{n}|+|\operatorname{supp}B|=n+m-s.$
(4.5)

We claim that $A$ is extremal. To see this, it would suffice by Proposition
2.3 to show that the graph $G(A)$ contains no cycles. Indeed, $G(A)$ is
obtained from $G(B)$ by adding $n$ new vertices (corresponding to the columns
of $D_{n}$) where each new vertex is joined by a single new edge to some
vertex of $G(B)$ (since each column of $D_{n}$ has exactly one nonzero entry).
Then all the new vertices have degree one, i.e. they are leaves. Since $G(B)$
contains no cycles ($B$ being extremal) and since adding leaves creates no
cycle in the graph, we see that also $G(A)$ contains no cycles and $A$ is
extremal.

It remains to show that indeed there exists an extremal
$B\in\mathcal{S}_{n,m-n}$ of support size $m-s$. This would follow from the
inductive hypothesis if we can verify that (i) neither one of $n,m-n$ divides
the other; and (ii) $\gcd(n,m-n)=d$. The property (ii) is obvious, so we turn
to verify (i). But property (i) is equivalent to the assertion that
$\min\\{n,m-n\\}$ does not coincide with $d=\gcd(n,m-n)$. And indeed, if
$k\geqslant 2$ then we have $d<n<m-n$. If, on the other hand, $k=1$ and
$d+1\leqslant r\leqslant n-1$, then $m-n$ is equal to $r$, and we have
$d<r<n$. Thus in any case both (i) and (ii) are established and the existence
of $B$ follows from the inductive hypothesis. ∎

###  4.3. Remark

Suppose that neither one of $n,m$ divides the other, and let $A$ be an
$n\times m$ doubly stochastic array with support of size $n+m-s$. If
$s=\gcd(n,m)$ then this implies that $A$ is extremal, by Theorem 1.1 and
Proposition 2.2. On the other hand, one can show that for any $1\leqslant
s\leqslant\gcd(n,m)-1$, the condition $|\operatorname{supp}A|=n+m-s$ does not
imply extremality.

##  5\. Support structure for extremal $n\times(kn+1)$ arrays

In this section we obtain a structural characterization of the support of an
extremal $n\times m$ doubly stochastic array in the special case where
$m=kn+1$. That is, for these values of $n,m$ we characterize the subsets
$\Omega\subset\\{1,\dots,n\\}\times\\{1,\dots,m\\}$ such that
$\Omega=\operatorname{supp}A$ for some extremal $n\times m$ array (Theorem
1.4).

As an application, we will construct a one-to-one correspondence between the
extremal $n\times(n+1)$ doubly stochastic arrays and the _trees on $n+1$
labeled vertices having their edges also labeled_. This will allow us to
determine the total number of extremal arrays in $\mathcal{S}_{n,n+1}$
(Theorem 1.5), as well as the number of _equivalence classes_ of these
extremal arrays.

###  5.1. Proof of Theorem 1.4

Our goal now is to prove that if $m=kn+1$, then a subset
$\Omega\subset\\{1,\dots,n\\}\times\\{1,\dots,m\\}$ is the support of an
extremal array $A\in\mathcal{S}_{n,m}$ if and only if $\Omega$ satisfies the
following two conditions:

  1. (i)

For each $1\leqslant i\leqslant n$, the set $\\{j:(i,j)\in\Omega\\}$ contains
exactly $k+1$ elements;

  2. (ii)

$\Omega$ does not contain any cycle, that is, any sequence of the form

$(i_{1},j_{1}),\;(i_{2},j_{1}),\;(i_{2},j_{2}),\;(i_{3},j_{2}),\;\dots,\;(i_{s},j_{s}),\;(i_{1},j_{s})\qquad(s\geqslant
2)$ (5.1)

where $i_{1},\dots,i_{s}$ are distinct row indices and $j_{1},\dots,j_{s}$ are
distinct column indices.

We remind the reader that if an extremal $n\times m$ array with a given
support does exist, then it is unique, due to Proposition 2.1.

####  5.1.1. Proof of the necessity of conditions (i) and (ii)

Suppose that $\Omega=\operatorname{supp}A$ where $A\in\mathcal{S}_{n,m}$ is
extremal. We first show that condition (i) must hold. In fact this follows
from [Car96, Proposition 6] but we give a different proof, based on Theorem
1.3.

Indeed, the entries of $A$ are nonnegative and the sum of the entries at each
column is $n$, so there can be no entry greater than $n$. Since the sum of the
entries at each row is $kn+1$, then in each row there must be at least $k+1$
nonzero entries. Now if there was a row with more than $k+1$ nonzero entries,
then the size of the support of $A$ would be greater than $n(k+1)=n+m-1$. But
this is not possible due to Theorem 1.3, since $n$ and $m$ are coprime. Hence
each row of $A$ contains exactly $k+1$ nonzero entries, and since
$\Omega=\operatorname{supp}A$ this establishes that condition (i) holds.

To see that condition (ii) must hold as well, we observe that if
$\Omega=\operatorname{supp}A$ then this condition means that the graph $G(A)$
contains no cycles. Hence condition (ii) follows from Proposition 2.3. ∎

####  5.1.2. Proof of the sufficiency of conditions (i) and (ii)

We now turn to prove the converse part of the result. That is, we assume that
$\Omega$ satisfies the two conditions (i) and (ii), and we will show that
there is an extremal $A\in\mathcal{S}_{n,m}$ with
$\operatorname{supp}A=\Omega$.

We will obtain the matrix $A$ by constructing its associated graph
$G(A)=(U,V,E,w)$. Let $U=\\{u_{1},\dots,u_{n}\\}$ and
$V=\\{v_{1},\dots,v_{m}\\}$ be two disjoint vertex sets constituting the
bipartition of the graph. We define the set of edges $E$ to include the edge
$\\{u_{i},v_{j}\\}$ if and only if $(i,j)\in\Omega$. Our goal now is to
construct a weight function $w$ on $E$, which assigns a positive weight to
each edge, in such a way that each vertex from $U$ has total weight $m$, while
each vertex from $V$ has total weight $n$.

Consider the unweighted graph $G=(U,V,E)$. By condition (ii), this graph
contains no cycles. Since the graph has $n+m$ vertices, this implies that the
number of edges in the graph must be $n+m-r$, where $r$ is the number of
connected components of the graph. On the other hand, it follows from
condition (i) that the size of $\Omega$, and hence also the number of edges in
the graph, is equal to $n(k+1)=n+m-1$. The number of connected components is
therefore one, which means that the graph $G$ is connected. So $G$ is both
connected and contains no cycles, that is, the graph $G$ is a tree.

For each edge $e=\\{u,v\\}$ of the graph $G$ ($u\in U$, $v\in V$) we let
$G_{e}=(U,V,E\setminus\\{e\\})$ be the subgraph of $G$ obtained by the removal
of the edge $e$. Then the graph $G_{e}$ has exactly two connected components.
We let $H_{e}$ denote the connected component of $G_{e}$ that contains the
vertex $u$. The set of vertices of $H_{e}$ is then the union of two disjoint
sets $U_{e}$ and $V_{e}$, where $U_{e}\subset U$ and $V_{e}\subset V$. We now
make the following claim:

######  Claim.

For every edge $e=\\{u,v\\}\in E$ $(u\in U,v\in V)$ we have

$|V_{e}|=k|U_{e}|.$ (5.2)

To see this, observe that by condition (i) the degree in $G$ of each vertex
from $U$ is exactly $k+1$. Hence the degree in $H_{e}$ of each vertex from
$U_{e}$ is also $k+1$, with the exception of the vertex $u$ that has degree
only $k$ (since in the graph $G_{e}$ the edge $e$ has been removed). Hence the
total number of edges in $H_{e}$ is equal to

$\sum_{u^{\prime}\in
U_{e}}\deg_{H_{e}}(u^{\prime})=(|U_{e}|-1)(k+1)+k=(k+1)|U_{e}|-1,$ (5.3)

where $\deg_{H_{e}}(u^{\prime})$ denotes the degree of the vertex $u^{\prime}$
in the graph $H_{e}$. On the other hand, observe that the graph $H_{e}$ does
not contain any cycles (since it is a subgraph of $G$), and $H_{e}$ is
connected by its definition. So the number of edges in $H_{e}$ is one less
than the number of vertices, that is, $H_{e}$ must have exactly

$|U_{e}|+|V_{e}|-1$ (5.4)

edges. Comparing (5.3) and (5.4) we conclude that (5.2) holds, which proves
the claim.

We now endow the graph $G$ with a weight function $w$ given by

$w(e):=|U_{e}|,\quad e\in E.$ (5.5)

It is obvious that this weight function is positive. Indeed, if $e=\\{u,v\\}$
($u\in U$, $v\in V$) is an edge in $E$, then the set $U_{e}$ contains at least
the vertex $u$, hence $U_{e}$ is nonempty and $w(e)$ is a positive integer.

Let us show that each vertex $v\in V$ has total weight $n$. Indeed, since the
graph $G$ is a tree (that is, $G$ is connected and contains no cycles) then
the subgraphs $H_{e}$, as $e$ goes through the edges incident to $v$, are
vertex disjoint and their union contains all the vertices of $G$ except $v$
itself. Hence the vertex sets $U_{e}$, as $e$ goes through the same edges, are
disjoint and their union is all of $U$. The total weight of the vertex $v$ is
therefore

$\sum_{e}w(e)=\sum_{e}|U_{e}|=|U|=n,$ (5.6)

where in the sum $e$ goes through the edges incident to $v$.

Next we show that each vertex $u\in U$ has total weight $m$. To see this, we
fix the vertex $u$ and recall that $u$ has degree $k+1$ in the graph $G$.
Since $G$ is a tree, it follows that a given vertex $v\in V$ belongs to
$H_{e}$ for every edge $e$ incident to $u$, with the exception of the edge $e$
that lies on the unique path connecting $u$ and $v$. Hence each vertex $v\in
V$ belongs to exactly $k$ sets $V_{e}$ as $e$ goes through the edges incident
to $u$, which yields

$\sum_{e}|V_{e}|=k|V|=km.$ (5.7)

But together with (5.2) this implies that the total weight of the vertex $u$
is

$\sum_{e}w(e)=\sum_{e}|U_{e}|=\frac{1}{k}\sum_{e}|V_{e}|=m,$ (5.8)

where in the sum $e$ goes through the edges incident to $u$, in both (5.7) and
(5.8).

We conclude that the weighted graph $G=(U,V,E,w)$ thus constructed is the
graph associated to an $n\times m$ doubly stochastic array $A=(a_{ij})$.
Moreover, $A$ is extremal, as the graph contains no cycles (Proposition 2.3).
Lastly, we notice that $\operatorname{supp}A=\Omega$, since the matrix entry
$a_{ij}$ is nonzero if and only if $\\{u_{i},v_{j}\\}$ is an edge in $E$,
which is the case if and only if $(i,j)\in\Omega$. This completes the proof of
Theorem 1.4. ∎

###  5.2. An application to extremal $n\times(n+1)$ arrays

We can now use Theorem 1.4 in order to construct a one-to-one correspondence
between the extremal $n\times(n+1)$ doubly stochastic arrays and the _trees on
$n+1$ labeled vertices having their edges also labeled_. This allows us to
find the exact total number of extremal arrays in $\mathcal{S}_{n,n+1}$
(Theorem 1.5), and also to determine the number of equivalence classes of
these extremal arrays.

#### 5.2.1.

We begin by introducing the type of trees that will be of interest to us:

######  Definition 5.1.

Let $T$ be a tree (that is, a graph which is both connected and contains no
cycles) on $n+1$ vertices. We say that $T\in\mathcal{T}_{n}$ if the vertices
of $T$ are labeled as $v_{1},\dots,v_{n+1}$, and the edges of $T$ are also
labeled (in some order) as $e_{1},\dots,e_{n}$.

We think of the edges $e_{1},\dots,e_{n}$ of the tree $T\in\mathcal{T}_{n}$ as
corresponding to the rows of an $n\times(n+1)$ matrix $A$, and of the vertices
$v_{1},\dots,v_{n+1}$ of the tree as corresponding to the columns of $A$. We
then have the following result:

######  Theorem 5.2.

To each tree $T\in\mathcal{T}_{n}$ there corresponds a unique extremal array
$A\in\mathcal{S}_{n,n+1}$ with the following property: $e_{i}$ is incident to
$v_{j}$ in $T$ if and only if $(i,j)\in\operatorname{supp}A$, for all $i,j$.
Moreover, this correspondence constitutes a bijection from the set of trees in
$\mathcal{T}_{n}$ to the set of extremal arrays in $\mathcal{S}_{n,n+1}$.

###### Proof.

Given a tree $T\in\mathcal{T}_{n}$, let $B=(b_{ij})$ be its $n\times(n+1)$
incidence matrix, defined by $b_{ij}=1$ if $e_{i}$ is incident to $v_{j}$, and
$b_{ij}=0$ otherwise. We then claim that $\Omega:=\operatorname{supp}B$
satisfies the conditions (i) and (ii) (with $k=1$) in Theorem 1.4. Indeed,
each edge of $T$ is incident with exactly two vertices, hence each row of $B$
contains exactly two nonzero entries, and so (i) is satisfied. To see that
(ii) holds as well, we observe that a cycle in $\Omega$ corresponds to a cycle
in the graph $T$. But since $T$ is a tree, it contains no cycles, and (ii)
follows. We can therefore use Theorem 1.4 to conclude that $\Omega$ is the
support of some extremal array $A\in\mathcal{S}_{n,n+1}$, having the property
that $e_{i}$ is incident to $v_{j}$ in $T$ if and only if
$(i,j)\in\operatorname{supp}A$, for all $i,j$. Moreover, such an $A$ is
unique, since an extremal array is uniquely determined by its support
(Proposition 2.1).

Conversely, given any extremal array $A\in\mathcal{S}_{n,n+1}$, we construct
an $n\times(n+1)$ matrix $B=(b_{ij})$ defined by $b_{ij}=1$ if
$(i,j)\in\operatorname{supp}A$, and $b_{ij}=0$ otherwise. The conditions (i),
(ii) in Theorem 1.4 ensure that $B$ is the incidence matrix of a cycle-free
graph $T$ with $n+1$ vertices labeled as $v_{1},\dots,v_{n+1}$ and with $n$
edges labeled as $e_{1},\dots,e_{n}$. This means that $T$ is a tree in
$\mathcal{T}_{n}$ with the property that $e_{i}$ is incident to $v_{j}$ in $T$
if and only if $(i,j)\in\operatorname{supp}A$, for all $i,j$. Moreover, the
incidence matrix $B$ determines the tree $T$ uniquely, which shows that the
correspondence from the set of trees in $\mathcal{T}_{n}$ to the set of
extremal arrays in $\mathcal{S}_{n,n+1}$ is indeed a bijection. ∎

#### 5.2.2.

We can now use the latter result in order to prove Theorem 1.5, which asserts
that the total number of extremal arrays in $\mathcal{S}_{n,n+1}$ is exactly
$n!(n+1)^{n-1}$.

###### Proof of Theorem 1.5.

We invoke the classical Cayley’s formula, which states that the number of
trees with $n+1$ labeled vertices (but with unlabeled edges) is $(n+1)^{n-1}$.
Notice that there are $n!$ ways to label also the edges of such a tree. Hence
the number of trees in $\mathcal{T}_{n}$ is exactly $n!(n+1)^{n-1}$. But the
set of trees in $\mathcal{T}_{n}$ has the same cardinality as the set of
extremal arrays in $\mathcal{S}_{n,n+1}$, due to Theorem 5.2, and the result
follows. ∎

Theorem 5.2 also allows us to determine the number of extremal $n\times(n+1)$
doubly stochastic arrays _up to equivalence_. Recall that two arrays are said
to be equivalent if one can be transformed into the other by a permutation of
rows and columns. Then two equivalent extremal arrays in $\mathcal{S}_{n,n+1}$
correspond through the bijection of Theorem 5.2 to two isomorphic labeled
trees, where two labeled trees are said to be isomorphic if one can be
transformed into the other by a permutation of vertex labels and edge labels.
Hence we arrive at the following conclusion:

######  Theorem 5.3.

The number of equivalence classes of the extremal arrays in
$\mathcal{S}_{n,n+1}$ is equal to the number of unlabeled trees on $n+1$
vertices.

Thus, for instance, any extremal $3\times 4$ doubly stochastic array is
equivalent to one of the two matrices in (1.3), since there are only two
unlabeled trees on $4$ vertices.

Unfortunately, no closed-form expression is known for the number of unlabeled
trees on $n+1$ vertices as a function of $n$.

##  6\. Non-equivalent extremal arrays with the same entries

The following question was posed by Loukaki in [Lou22, Remark 2]: Do there
exist two extremal arrays $A,B\in\mathcal{S}_{n,m}$, whose supports are both
of the least possible size $n+m-\gcd(n,m)$, and such that $A,B$ have the same
set of entries counted with multiplicities but $A$ and $B$ are not equivalent?

In this section we prove that the question admits an affirmative answer in
$\mathcal{S}_{n,n+1}$ for each $n\geqslant 6$, by constructing an example of
two extremal arrays $A,B$ with the properties above (Theorem 1.6). We also
observe that the same does not hold for $n\leqslant 5$.

Our strategy is based on the correspondence in Theorem 5.2 between the
extremal arrays in $\mathcal{S}_{n,n+1}$ and the trees on $n+1$ labeled
vertices having their edges also labeled. Recall that two equivalent extremal
arrays in $\mathcal{S}_{n,n+1}$ correspond to two isomorphic trees. Hence our
goal is to construct two non-isomorphic trees which induce the same multiset
of entries in the corresponding extremal arrays.

### 6.1.

Let $T$ be a tree in $\mathcal{T}_{n}$, that is, $T$ is a tree on $n+1$
vertices labeled as $v_{1},\dots,v_{n+1}$, and the edges of $T$ are also
labeled as $e_{1},\dots,e_{n}$ (recall Definition 5.1). Suppose that $i,j$ are
such that the edge $e_{i}$ is incident to the vertex $v_{j}$ in the tree $T$.
If we remove the edge $e_{i}$ from the tree then we obtain a subgraph
$G_{i}(T)$ with exactly two connected components. We denote by $H_{ij}(T)$ the
connected component of $G_{i}(T)$ that does _not_ contain the vertex $v_{j}$.

######  Theorem 6.1.

Let $T$ be a tree in $\mathcal{T}_{n}$, and let $A=(a_{ij})$ be the extremal
array in $\mathcal{S}_{n,n+1}$ which corresponds to $T$ through the bijection
of Theorem 5.2. For each $(i,j)\in\operatorname{supp}A$, the entry $a_{ij}$ is
equal to the number of vertices in the connected component $H_{ij}(T)$.

This result complements Theorem 5.2 by specifying the values of the nonzero
entries of the extremal $n\times(n+1)$ array $A$ that corresponds to a given
tree $T\in\mathcal{T}_{n}$.

###### Proof of Theorem 6.1.

Let $G(A)=(U,V,E,w)$ be the graph associated to the extremal $n\times(n+1)$
array $A$, where $U=\\{u_{1},\dots,u_{n}\\}$ and
$V=\\{v_{1},\dots,v_{n+1}\\}$. By Theorem 5.2, $(i,j)\in\operatorname{supp}A$
if and only if $e_{i}$ is incident to $v_{j}$ in the tree $T$. Hence each
vertex $u_{i}$ in the graph $G(A)$ is connected to exactly two $V$-vertices,
that constitute the endpoints of the edge $e_{i}$ in $T$. This means that the
(unweighted) graph $G(A)$ is obtained from the tree $T$ by inserting a new
vertex $u_{i}$ in the middle of each edge $e_{i}$ of $T$.

Now the matrix entry $a_{ij}$ is the weight of the edge $\\{u_{i},v_{j}\\}$ in
$G(A)$. We recall from the proof of Theorem 1.4 (with $k=1$) that the weight
of the edge $\\{u_{i},v_{j}\\}$ is equal to the number of $U$-vertices in the
connected component containing the vertex $u_{i}$ in the subgraph of $G(A)$
obtained by the removal of the edge $\\{u_{i},v_{j}\\}$. But each $U$-vertex
corresponds to the edge of the tree $T$ in the middle of which it was
inserted, so the weight of the edge $\\{u_{i},v_{j}\\}$ is also equal to the
number of edges in the connected component $H_{ij}(T)$ together with the edge
$e_{i}$ itself (which corresponds to the vertex $u_{i}$). But this number is
the same as the number of vertices in $H_{ij}(T)$, which proves our claim. ∎

### 6.2.

Consider now the two trees shown in Figure 6.1. Each tree has $7$ vertices,
but the trees are not isomorphic, since one of them has a vertex of degree $4$
while the other does not. We will show that these two trees correspond to two
non-equivalent extremal $6\times 7$ doubly stochastic arrays $A,B$ that have
the same multiset of entries.

$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{6}$$e_{5}$

$\phi(e_{1})$$\phi(e_{4})$$\phi(e_{3})$$\phi(e_{2})$$\phi(e_{5})$$\phi(e_{6})$

Figure 6.1. An example of two trees on $7$ vertices which correspond to two
non-equivalent extremal $6\times 7$ arrays with the same multiset of entries.

Let $A$ be the extremal array corresponding to the left tree in Figure 6.1.
Then by Theorem 1.4, each row of $A$ contains exactly two nonzero entries, and
by Theorem 6.1 the values of the two nonzero entries at the $i$’th row of $A$
are equal to the number of vertices in each one of the two connected
components created by the removal of the edge $e_{i}$ in the left tree.

For example, removing the edge $e_{1}$ in the left tree creates two connected
components, one containing $6$ vertices and the other consisting of a single
vertex. Hence the two nonzero values in the first row of $A$ are $6$ and $1$.

Now consider the extremal array $B$ corresponding to the right tree in Figure
6.1. Notice that we have labeled the edges of this tree as
$\phi(e_{1}),\dots,\phi(e_{6})$, namely, there is a bijection $\phi$ between
the edges of the left tree and the edges of the right tree. It is now
straightforward to verify that for each $1\leqslant i\leqslant 6$, the removal
of the edge $e_{i}$ in the left tree, or the removal of the edge $\phi(e_{i})$
in the right tree, creates two connected components whose respective number of
vertices is the same for the two trees. This implies that the $i$’th row of
$A$ contains the same two nonzero values as the $i$’th row of $B$, although
these two nonzero values may appear on different columns of $A$ and $B$.

For example, removing the edge $\phi(e_{1})$ in the right tree creates a
connected component with $6$ vertices and another component with a single
vertex. Hence the two nonzero values in the first row of $B$ are $6$ and $1$,
the same two values as in the first row of $A$.

The two extremal $6\times 7$ doubly stochastic arrays obtained from this
construction are

$\begin{bmatrix}6&1&&&&&\\\ &1&6&&&&\\\ &4&&3&&&\\\ &&&2&5&&\\\ &&&&1&6&\\\
&&&1&&&6\end{bmatrix}\quad\text{and}\quad\begin{bmatrix}6&1&&&&&\\\
&&1&6&&&\\\ &&3&&4&&\\\ &5&&&2&&\\\ &&1&&&6&\\\ &&1&&&&6\end{bmatrix},$ (6.1)

which indeed have the same two nonzero values in each row, and as a
consequence, have the same multiset of entries. On the other hand these two
arrays are not equivalent, as one of them has a column with $4$ nonzero
entries, while the other does not (which, in turn, is due to one of the trees
having a vertex of degree $4$ while the other tree not having such a vertex).

We have thus proved the case $n=6$ in Theorem 1.6.

### 6.3.

We now continue with the proof of Theorem 1.6 for all $n\geqslant 6$. It would
suffice for us to find two non-isomorphic trees $T=(V,E)$ and
$T^{\prime}=(V^{\prime},E^{\prime})$ with $n+1$ vertices each, and an edge
bijection $\phi:E\to E^{\prime}$, such that the removal of the edge $e_{i}$ in
the tree $T$, or the removal of the edge $\phi(e_{i})$ in the tree
$T^{\prime}$, creates two connected components whose respective number of
vertices is the same for the two trees.

The construction is done by induction as illustrated in Figure 6.2. Assume
that the two trees on $n$ vertices have already been constructed. We then
insert a new edge $e_{n}$ into the left tree, between the edge $e_{n-1}$ and
the vertex common to $e_{3}$ and $e_{4}$. Similarly, we insert a new edge
$\phi(e_{n})$ into the right tree, between the edge $\phi(e_{n-1})$ and the
vertex common to $\phi(e_{2})$, $\phi(e_{3})$ and $\phi(e_{5})$. Thus we
obtain two trees on $n+1$ vertices and also extend the edge bijection $\phi$
from the previous step to these new trees.

$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{n}$$e_{5}$$e_{n-1}$$e_{6}$$\cdot$$\cdot$$\cdot$

$\phi(e_{1})$$\phi(e_{4})$$\phi(e_{3})$$\phi(e_{2})$$\phi(e_{5})$$\phi(e_{n})$$\phi(e_{n-1})$$\phi(e_{6})$$\cdot$$\cdot$$\cdot$

Figure 6.2. Constructing the two trees in the proof of Theorem 1.6.

We must show that the new bijection $\phi$ has the required property. Indeed,
observe that for each $1\leqslant i\leqslant n$, the removal of the edge
$e_{i}$ in the left tree, as well as the removal of the edge $\phi(e_{i})$ in
the right tree, creates one connected component whose number of vertices is a
certain constant $c_{i}$ which does not depend on $n$, and a second connected
component which contains the remaining $n+1-c_{i}$ vertices of the tree.

We conclude that the two trees thus constructed correspond to two extremal
$n\times(n+1)$ doubly stochastic arrays that have the same two nonzero values
in each row, and hence also the same multiset of entries. It remains only to
notice that the two trees are not isomorphic (since, as before, one of the
trees has a vertex of degree $4$ while the other does not) and therefore the
two corresponding extremal arrays are not equivalent. The theorem is therefore
proved. ∎

###  6.4. Remark

We note that the result in Theorem 1.6 does not hold for $n\leqslant 5$.
Indeed, there are only $13$ unlabeled trees on $n+1$ vertices with $1\leqslant
n\leqslant 5$ in total (see, for instance, [Har69, Appendix III]), and one can
check that no two of them correspond to two extremal doubly stochastic arrays
that have the same multiset of entries.

##  7\. Remarks

We conclude the paper with some motivational remarks, relating the notion of
doubly stochastic arrays to some other mathematical topics.

### 7.1.

The notion of an $n\times m$ doubly stochastic array admits an obvious
probabilistic interpretation. If $A\in\mathcal{S}_{n,m}$ then the matrix
$\frac{1}{nm}A$ represents a joint distribution of two random variables $X,Y$
such that $X$ is uniformly distributed in $\\{1,2,\dots,n\\}$ and $Y$
uniformly distributed in $\\{1,2,\dots,m\\}$. Thus minimizing the support size
of an array $A\in\mathcal{S}_{n,m}$ is the same as minimizing the support size
of a joint distribution over all couplings of the two random variables $X,Y$.

### 7.2.

It is also possible to give a combinatorial interpretation of the $n\times m$
doubly stochastic array as _transportation plans_ as follows. Suppose that we
are given $n$ blue bins and $m$ green bins, such that each blue bin contains
$m$ balls while the green bins are empty from balls. The problem is to move
the balls from the blue bins to the green ones, so that each green bin would
contain exactly $n$ balls. Then a transportation plan corresponds to an
integer-valued array $A=(a_{ij})$ in $\mathcal{S}_{n,m}$ where $a_{ij}$ is the
number of balls to be moved from the $i$’th blue bin to the $j$’th green bin.
If we seek to minimize the number of operations of the form “move $a_{ij}$
balls from the $i$’th blue bin to the $j$’th green bin”, then the minimal
number of operations needed to move the balls from the blue bins to the green
ones as required is $n+m-\gcd(n,m)$. This follows from Theorem 1.1 and the
fact that an array in $\mathcal{S}_{n,m}$ which minimizes the support size is
automatically integer-valued (Propositions 2.2 and 2.4).

### 7.3.

Let $G$ be a finite abelian group, and suppose that $G$ is the direct sum of
two subgroups $H_{1}$ and $H_{2}$ of sizes $n$ and $m$ respectively. A
function $f$ on the group $G$ is said to _tile_ by translations along each one
of the two subgroups $H_{1}$ and $H_{2}$ if we have

$\sum_{s\in H_{1}}f(t-s)=n,\quad\sum_{s\in H_{2}}f(t-s)=m,\quad t\in G.$ (7.1)

In [KP21, Section 4] the authors pointed out a correspondence between the
$n\times m$ doubly stochastic arrays and the _nonnegative_ functions $f$ which
tile by translations along each one of the two subgroups $H_{1}$ and $H_{2}$.
They posed the question as to what is the smallest possible size of the
support of such a function $f$. It follows from Theorem 1.1 that the answer is
$n+m-\gcd(n,m)$. In fact, Theorem 3.1 implies that the answer remains the same
even for complex-valued functions $f$ (that is, even if we do not require $f$
to be nonnegative).

## References

  * [Bir46] G. Birkhoff, Three observations on linear algebra (Spanish). Univ. Nac. Tucumán. Revista A. 5 (1946), 147–151.
  * [Car96] R. M. Caron, X. Li, P. Mikusiński, H. Sherwood, M. D. Taylor, Nonsquare “doubly stochastic” matrices. IMS Lecture Notes Monograph Series 28 (1996), 65–75.
  * [Har69] F. Harary, Graph theory. Addison-Wesley, 1969.
  * [KP21] M. N. Kolountzakis, E. Papageorgiou, Functions tiling with several lattices. J. Fourier Anal. Appl., to appear, arXiv:2106.11701.
  * [Li96] X. Li, P. Mikusiński, H. Sherwood, M. D. Taylor, In quest of Birkhoff’s theorem in higher dimensions. IMS Lecture Notes Monograph Series 28 (1996), 187–197.
  * [Lou22] M. Loukaki, Doubly stochastic arrays with small support. Preprint, arXiv:2202.00639.


Sliced Wasserstein Variational Inference We name our method as sliced
Wasserstein variational inference (SWVI). We use the following notation:
$\upsilon_{\phi}(z)$ as the variational distribution parameterized by $\phi$,
and $\mu(z)=\beta^{-1}\bar{\mu}(z)$ as the target distribution, where $\beta$
is a normalizing constant. The problem we are interested in is finding an
optimal parameter $\phi^{*}$ that minimizes sliced Wasserstein distance
between the variational distribution and the target distribution.

$\phi^{*}={\arg\min}_{\phi}\ \sw(\mu,\upsilon_{\phi})$ (1)

Eq(1) defines a minimum distance estimator wolfowitz1957minimum
basu2011statistical where we choose sliced Wasserstein distance as a specific
metric function. In some applications, the density function of
$\upsilon_{\phi}$ is not always tractable but we can still simulate samples
from it and if $\mu$ also has a sampling distribution, we solve the following
problem,

$\phi^{*}={\arg\min}_{\phi}\ \sw(\mu^{n},\upsilon^{n}_{\phi})$ (2)

where $\mu^{n}$ and $\upsilon^{n}_{\phi}$ are sampling distributions of $\mu$
and $\upsilon_{\phi}$ with $n$ observations. The optimization problem defined
in Eq(2) does not require an explicit probability density function–allowing to
design a more flexible variational distribution such as a neural network
generator and a variational program ranganath2016operator.

##  Estimation of Sliced Wasserstein Distance

Due to the intractability of the target distribution
$\mu(z)=\beta^{-1}\bar{\mu}(z)$, the main idea of SWVI is to approximate
sliced Wasserstein distance between the variational and the target
distribution using MCMC and minimize it. Unlike variational inference, MCMC
methods provide particle approximations by designing transition kernels of a
Markov chain with invariant distribution $\mu(z)$. Let $K(\cdot|\cdot)$ be a
transition kernel of MCMC, and $\mu_{0}(z)$ be the initial distribution of the
corresponding MCMC, e.g., a potential $\mu_{0}(z)$ can be chosen as
$\upsilon_{\phi}(z)$. We denote by $\mu_{t}(z)$ the marginal distribution of
the Markov chain after applying $t$ times transitions.

$\mu_{t}(z)=\int\mu_{t-1}(z^{\prime})K(z|z^{\prime})dz^{\prime}$ (3)

Given a sufficiently long run, $\mu_{t}(z)$ converges to $\mu(z)$ because of
the stationary property of Markov chain. At the current stage, one can
directly evaluate sliced Wasserstein distance $\sw(\mu,\upsilon_{\phi})$ via

$\sw(\mu,\upsilon_{\phi})=\sw(\mu_{t},\upsilon_{\phi})\text{as}t\to\infty$ (4)

Unfortunately, running a long enough MCMC chain is time consuming and it might
be difficult to diagnose the burn-in period. To solve this problem, we instead
evaluate a local distance $\sw(\mu_{t},\upsilon_{\phi})$ at every time step
$t$ of iterating MCMC algorithms. Next we update parameters $\phi$ via
gradient descent to minimize $\sw(\mu_{t},\upsilon_{\phi})$ per iteration.
Since every $\mu_{t}(z)$ is an improvement of the previous $\mu_{t-1}(z)$,
minimizing sliced Wasserstein distance guides the variational distribution
$\upsilon_{\phi}(z)$ towards the target distribution $\mu(z)$.

Note that we use particle approximations to the marginal distribution
$\mu_{t}$ by parallelizing $n$ Markov chains and we sample the same number of
particles from the variational distribution $\upsilon_{\phi}$. Hence, the
optimization problem is replaced with minimizing the sampled-based sliced
Wasserstein distance $\sw(\mu^{n}_{t},\upsilon^{n}_{\phi})$. Therefore, SWVI
defines the following sequential optimization problem

$\\{\min_{\phi}\sw(\mu^{n}_{t},\upsilon^{n}_{\phi})\\}_{t\in\mathbb{N}}$ (5)

Heuristically, we also inherit the parameter from the previous iteration such
that $\phi_{t}=\arg\min_{\phi}\sw(\mu^{n}_{t},\upsilon^{n}_{\phi_{t-1}})$. We
summarize this procedure in Algorithm 2. alg:swviSliced Wasserstein
Variational Inference (SWVI)Require: An unnormalized probability distribution
$\bar{\mu}(z)$, a Markovian transition kernel $K(z|z^{\prime})$ with invariant
distribution $\mu(z)$ and initial distribution $\mu_{0}(z)$, variational
distribution $\upsilon_{\phi}(z)$.
Initialize $\phi_{0}=\phi$ and $\mu^{n}_{0}(z)$ by sampling $n$ particles from
$\mu_{0}(z)$
for  $t=1,2\cdots T$ Apply transition kernel $K(z|z^{\prime})$ to
$\mu^{n}_{t-1}$ to get $\mu^{n}_{t}$
$\phi_{t}=\arg\min_{\phi}\sw(\mu^{n}_{t},\upsilon^{n}_{\phi_{t-1}})$ return
$\upsilon_{\phi_{T}}(z)$

##  Existence, Convergence and Consistency of SWVI

It is important to understand the convergence of SWVI while the algorithm
iterating with time $t$ and the asymptotic property if the number of Markov
chains $n$ goes to infinity. Specifically, we show that SWVI converges if the
Markov chain converges to the invariant distribution (Theorem 1) and SWVI is
consistent (Theorem 2) if the number of Markov chains goes to infinity under
some mild regularities. Inspired by bernton2019parameter
nadjahi2019asymptotic, we make the following assuamptions

Assumption A.1. For any sequence of probability measures
$\\{\mu_{t}\\}_{t\in\mathbb{N}}$, e.g., marginal probability densities yield
by Markov chains, $\\{\mu_{t}\\}_{t\in\mathbb{N}}$ converges in sliced
Wasserstein distance to $\mu$, i.e. $\lim_{t\to\infty}\sw(\mu_{t},\mu)=0$,
$\mathbb{P}$-almost surely.
Assumption A.2. The map $\phi\to\upsilon_{\phi}$ is continuous, i.e.,
$\lim_{k\to\infty}||\phi_{k}-\phi||=0$ implies weak convergence of
$\upsilon_{\phi_{k}}$ to $\upsilon_{\phi}$.
Assumption A.3. For any data generating processes
$\\{\mu_{t}^{n}\\}_{n\in\mathbb{N}}$, we have
$\lim_{n\to\infty}\sw(\mu_{t}^{n},\mu_{t})=0$. For
$\lim_{n\to\infty}||\phi_{n}-\phi||=0$, we have
$\lim_{n\to\infty}\sw(\upsilon_{\phi_{n}}^{n},\upsilon_{\phi})=0$,
$\mathbb{P}$-almost surely.
Assumption A.4. For some $\epsilon>0$ with
$\epsilon^{*}=\inf_{\phi}\sw(\mu_{t},\upsilon_{\phi})$,
$B_{\epsilon}=\\{\phi\in\mathcal{H}:\sw(\mu_{t},\upsilon_{\phi})\leq\epsilon^{*}+\epsilon\\}$
is bounded.

Note that all infimum are taken with $\phi\in\mathcal{H}$ where $\mathcal{H}$
is a parameteric space. A.1 indicates the convergence of Markov chain in the
metric space. Indeed, it also implies weak convergence
$\\{\mu_{t}\\}_{t\in\mathbb{N}}\to\mu$ in $\mathcal{Q}_{p}(\mathcal{X})$. This
is a corollary from nadjahi2020statistical where if $p$-Wasserstein distance
metrizes weak convergence then the sliced $p$-Wasserstein metrizes weak
convergence as well. We refer to villani2009optimal for the study of weak
convergence with Wasserstein distance. A straightforward result is that
Langevin dynamic is a gradient flow of KL divergence in Wasserstein Space
jordan1998variational and liu2019understanding generalizes it to other MCMC
algorithms. Under Assumption A.1 and A.2,

$\lim_{t\to\infty}\inf_{\phi}\sw(\mu_{t},\upsilon_{\phi})=\inf_{\phi}\sw(\mu,\upsilon_{\phi})$
(6)

Under Assumption A.2, A.3 and A.4

$\lim_{n\to\infty}\inf_{\phi}\sw(\mu^{n}_{t},\upsilon^{n}_{\phi})=\inf_{\phi}\sw(\mu_{t},\upsilon_{\phi})$
(7)

and the existence of minimum

$\arg\min_{\phi}\sw(\mu_{t},\upsilon_{\phi})\neq\emptyset$

If Markov chains evolve with time and the number of chains goes to infinity,
we have

$\lim_{t\to\infty}\lim_{n\to\infty}\inf_{\phi}\sw(\mu^{n}_{t},\upsilon^{n}_{\phi})=\inf_{\phi}\sw(\mu,\upsilon_{\phi})$
(8)

Theorem 1 indicates that the sequential optimization problem of SWVI
converges. The proof is analogous to nadjahi2019asymptotic where the sequence
of probability measures here is constructed by Markov chains. Theorem 2 is
similar to Corollary 6.11 by [villani2009optimal] where if $\mu^{n}$ and
$\upsilon^{n}$ weakly converge in $\mathcal{Q}_{p}(\mathcal{X})$ to $\mu$ and
$\upsilon$, then
$\lim_{n\to\infty}\mathcal{W}_{p}(\mu^{n},\upsilon^{n})=\mathcal{W}_{p}(\mu,\upsilon)$.
Corollary 3 is a direct result from Theorem 1 and 2. Here we prove the infimum
of the sequence $\\{\sw(\mu^{n}_{t},\upsilon^{n}_{\phi})\\}_{n\in\mathbb{N}}$
converges to the infimum of $\sw(\mu_{t},\upsilon_{\phi})$ in Appendix A.

##  Burn-in Diagnosis

SWVI utilizes MCMC to explore the target space. Hence the convergence of the
corresponding Markov chain influences the accuracy of the variational
approximation. Burn-in diagnosis of MCMC is a hard problem in the machine
learning and statistics community. Several attempts are proposed to assess the
convergence such as estimating marginal densities and using couplings to
estimate an upper bound of Wasserstein distance biswas2019estimating.

We show that our method does not suffer from the problem of determining the
burn-in period of Markov Chain. Sliced Wasserstein distance itself can monitor
the convergence of MCMC. Without of the loss of generality, we assume that the
burn-in period $t<M$ for some $M\in\mathbb{N}$ such that,

$\sw(\mu_{t+1},\upsilon_{\phi})\approx\sw(\mu_{t},\upsilon_{\phi})\approx\sw(\mu,\upsilon_{\phi})\text{,for}t\geq
M,\text{forall}\phi$ (9)

This implies that $\min_{\phi}\sw(\mu_{t},\upsilon_{\phi})$ becomes stationary
for $t\geq M$. That is to say once the loss function achieves the minimum with
a tolerance, SWVI congerves. We show the loss curves of our method of fitting
2D Gaussian distributions (corresponds to experiment 4.1) in Figure 2 and
compare it with 2-Wasserstein distance where it is tractable (we use sinkhorn
divergence [cuturi2013sinkhorn] as approxiamted 2-Wasserstein distance for
mixture distributions).

[width=0.2675]bi1.png [width=0.233]bi2.png [width=0.233]bi3.png
[width=0.233]bi4.png

Figure : Loss curves of fitting Gaussian distributions. (a) Mean-field
Gaussian approximations. (b)-(d) Full Gaussian approximations where (c) and
(d) has a target bi-modal Gaussian mixtures. Compared with 2-Wasserstein
(Sinkhorn approximations in (c) and (d)) distances between Gaussians. SWVI
curves have empirically similar convergence rates to the convergence described
by 2-Wasserstein distances

##  Stochastic Optimization

The sampled-based sliced Wasserstein distance
$\sw(\mu^{n}_{t},\upsilon^{n}_{\phi})$ can be estimated by drawing samples
respectively from $\mu_{t}(z)$ (via MCMC) and $\upsilon_{\phi}(z)$. Suppose
that $\\{z_{i}\\}_{i=1,2\cdots n}\sim\upsilon_{\phi}(z)$ and
$\\{z^{\prime}_{i}\\}_{i=1,2\cdots n}\sim\mu_{t}(z)$. Sliced Wasserstein
distance is then approximated by

$\sw(\mu^{n}_{t},\upsilon^{n}_{\phi})\approx\mathcal{L}(\\{z_{i}\\},\\{z^{\prime}_{i}\\})$
(10)

Here we rewrite the approximate distance as a function
$\mathcal{L}(\cdot,\cdot)$ of two sets of samples according to Algorithm 1. In
order to optimize the parameter of the variational distribution
$\upsilon_{\phi}(z)$, we still need to reparameterize samples
$\\{z_{i}\\}_{i=1,2\cdots n}$. This can be done by an amortized sampler that
can be either a parametric probability distribution or a flexible neural
network generator. The amortized sampler is written as
$z(\phi)=g_{\phi}(\epsilon),\text{}\epsilon\sim r(\epsilon)$, where
$r(\epsilon)$ is a noise distribution and $g_{\phi}$ is a parametric model. We
can use chain rule to obtain the gradient estimation of Eq(10),

$\nabla_{\phi}\mathcal{L}(\\{z_{i}\\},\\{z^{\prime}_{i}\\})=\sum_{i=1}^{n}\nabla_{z_{i}}\mathcal{L}(\\{z_{i}\\},\\{z^{\prime}_{i}\\})\nabla_{\phi}z_{i}(\phi).$
(11)

This can be implemented easily via back-propagation. We also find it is
helpful to warm-up MCMC by a few steps and then applies SWVI iteration. The
only difference of such lagged procedure is that SWVI starts at a better
initial distribution of MCMC. The practical implementation of SWVI is
summarized in Algorithm 3 alg:swvi2Practical Implementation of SWVIRequire: An
unnormalized probability distribution $\bar{\mu}(z)$, a Markovian transition
kernel $K(z|z^{\prime})$ with invariant distribution $\mu(z)$ and initial
distribution $\mu_{0}(z)$, variational distribution $\upsilon_{\phi}(z)$,
learning rate $\alpha$ and warm-up lag $L$.
Initialize $\phi_{0}=\phi$ and $\mu^{n}_{0}(z)$ by sampling $n$ particles from
$\mu_{0}(z)$
for $t=1,2,\cdots L-1$ Only run MCMC, i.e., apply kernel $K(z|z^{\prime})$ to
$\mu^{n}_{t-1}$ to get $\mu^{n}_{t}$ for $t=L,L+1\cdots T$ Apply transition
kernel $K(z|z^{\prime})$ to $\mu^{n}_{t-1}$ to get $\mu^{n}_{t}$ with
corresponding particles $\\{z^{\prime}_{i}\\}_{i=1,2\cdots n}\sim\mu_{t}(z)$
Draw $\\{z_{i}\\}_{i=1,2\cdots n}\sim\upsilon_{\phi_{t}}(z)$ with
reparameterization Update parameter
$\phi_{t+1}=\phi_{t}-\alpha\nabla_{\phi}\mathcal{L}(\\{z_{i}\\},\\{z^{\prime}_{i}\\})$
return  $\upsilon_{\phi_{T}}(z)$

##  Related Work

To the best of our knowledge, we first introduce sliced Wasserstein distance
into variational inference. Sliced Wasserstein has been widely studied in
generative modeling deshpande2018generative, kolouri2018sliced2,
bonet2021sliced as a measurement of the discrepancy of model distributions and
data. [ambrogioni2018wasserstein] combines orginal Wasserstein distances with
variational inference where they introduce a new class of discrepancies that
includes $f$-divergence allowing for variational inference problems. On the
other hand, many alternative objectives to (reverse) KL divergence has been
proposed in VI problems. For example, Stein discrepancy ranganath2016operator,
liu2016stein, forward KL divergence jerfel2021variational,
prangle2019distilling, bornschein2014reweighted, dieng2017variational,
$\alpha$\- divergence li2016renyi and f-divergences wan2020f. Since our
methods uses MCMC to estimate the metric function. This is similar to some
previous works utilize the advantages of MCMC methods to improve variational
inference. The authors of ruiz2019contrastive proposes to use MCMC samples to
estimate a new objective function to ELBO. The authors of
naesseth2020markovian estimates the gradient of forward KL divergence via
runing MCMC. Similar to our work, The authors of li2017approximate uses
’teacher-student’ framework where MCMC samples teach the variational
distribution to how to improve via minimizing different objectives. Another
line of research to enrich the approximating families of VI is normalizing
flows rezende2015variational. Compared to our method, normalizing flows
require manually design a bijective function whereas SWVI can use a simple non
invertible neural net.