6 System of distinct representatives 6.1 Hall’s marriage theorem and SDR 6.3 Independent Sets and Covers: Konig, Egervary theorem

6.2 Latin rectangles and decomposition of doubly stochastic matrices

A $r\times n$ Latin rectangle is a $r\times n$ matrix such that each of the numbers $1,2,\ldots,n$ occurs once in each row and at most once in each column. If $r=n$ , we call it a Latin square. It was conjectured and proved that a partially completed Latin square with less than $n$ entries can be completed; see [Jukna 2011, Section 5.1] or and [Van Lint and Wilson, Chapter 17]. But we will show that a Latin rectangle can always be extended to a Latin square or equivalently, a partially filled Latin square with an empty row can always be completed.

Theorem 6.11 (Ryser 1951 ).

If $r<n$ , then any given $r\times n$ Latin rectangle can be extended to a $(r+1)\times n$ Latin rectangle.

Proof.

Let $R$ be an $r\times n$ Latin rectangle. Let $S_{j},j=1,\ldots,n$ be the set of those integers in $[n]$ that do not occur in the $j$ th column. If $S_{j}$ ’s have a SDR $s_{j},j=1,\ldots,n$ then adding $s_{1},\ldots,s_{n}$ as the $(r+1)$ th column we can get a $(r+1)\times n$ Latin rectangle.

$S_{j}$ ’s are $(n-r)$ -element subsets of $[n]$ and each element belongs to exactly $n-r$ sets. Thus, the result follows from Exercise 6.10. ∎

Our next application is the Birkhoff-von Neumann theorem which is of much use in various areas of mathematics such as convex geometry, optimal transport, probability theorey et al.

An $n\times n$ non-negative matrix $A=\{a_{ij}\}$ is called a doubly stochastic matrix if its row sum and column sums are both $1$ i.e., $\sum_{j}a_{ij}=\sum_{i}a_{ij}=1$ for all $i,j\in[n]$ . A permutation matrix is a doubly stochastic matrix with entries being $0,1$ . Equivalently, every row and column have exactly one $1$ . A matrix $A$ is a convex combination of $A_{1},\ldots,A_{m}$ if there exist non-negative numbers $\lambda_{i},i=1,\ldots,m$ with $\sum_{i}\lambda_{i}=1$ and $A=\sum_{i}\lambda_{i}A_{i}$ .

Theorem 6.12 (Birkhoff -Von Neumann theorem).

Every doubly stochastic matrix is a convex combination of permutation matrices.

Proof.

We will prove by induction on the number of (strictly) positive entries. Since every row sum and column sum is $1$ , there exist at least at $n$ non-negative entries.

Suppose that there are exactly $n$ positive entries then $A$ is a permutation matrix.

Now let $A$ have more than $n$ positive entries and result holds for any smaller number. Define the row-wise non-zero entries as

S_{i}=\{j:a_{ij}>0\},i=1,\ldots,n.

If $|\cup_{i\in I}S_{i}|<|I|$ (and say $|I|=k$ ) then all the non-zero entries in $\cup_{i\in I}S_{i}$ are in at most $k-1$ rows and hence the $k=\sum_{i\in I}\sum_{j}a_{ij}\leq(k-1)$ , a contradiction. So $S_{i}$ ’s satisfy Hall’s condition for SDR. Let $j_{i}\in S_{i}$ be the SDR.

Define permutation matrix $P_{1}=\{p_{ij}\}$ by $p_{ij}=1$ iff $j=j_{i}$ . Define $\lambda_{1}=\min_{i}a_{ij_{i}}$ . By definition of $S_{i}$ ’s, $\lambda_{1}>0$ . Consider $A_{1}=A-\lambda_{1}P_{1}$ . Again by construction of $\lambda_{1}$ and $P_{1}$ , $A$ has non-negative entries and in particular, it has at least one less positive entry than $A$ . Furthermore, is row sum and column sums are equal to $1-\lambda_{1}$ . Thus $B=(1-\lambda_{1})^{-1}A_{1}$ is a doubly stochastic matrix with strictly less positive entries than $A$ and by induction, the theorem applies to $B$ . So $B$ is a convex combination of permutation matrices $P_{2},\ldots,P_{m}$ with weights $\gamma_{2},\ldots,\gamma_{m}$ respectively. Thus $A$ is a convex combination of permutation matrices with weights $\lambda_{1},(1-\lambda_{1})\gamma_{2},\ldots,(1-\lambda_{1})\gamma_{m}$ . ∎