A latin square of order $n$ has a weak transversal.

99 Views Asked by At

A matrix of order $n$ with no repeated element in a row or in a column has a weak transversal. In particular, a latin square of order $n$ has a weak transversal.

Proof. We prove the theorem by induction on $n$. If $n = 1$ the conclusion is trivial. Suppose that $n > 1$ and let $A$ be a matrix of order $n$ such that each row and each column contains distinct elements. Let $A'$ be the matrix obtained from $A$ by deleting the first row and the first column. By the inductive hypothesis $A'$ has a weak transversal. Without loss of generality we assume that the $n - 1$ diagonal positions of $A'$ form a weak transversal, and that the elements in these positions are $1, 1, 2, 2, \cdots , r, r, r + 1, r + 2, \cdots , r + s$ where $2r + s = n - 1$. If the element in position $(1,1)$ does not equal any of $1, 2, \cdots, r$, then the $n$ diagonal positions of $A$ form a weak transversal. Otherwise we assume without loss of generality that $1$ is in position $(1,1)$. Because row $1$ of $A$ contains distinct elements, row $1$ contains $r +1$ distinct elements $x_l , x_2, \cdots , x_r$ each of which is different from $1, 2,\cdots , r$. Because column $1$ has distinct elements, there is an element $x_i$ in row $1$ such that the element $y$ in column $1$ which is symmetrically opposite $x_i$ is different from $1, 2, \cdots , r$. Let this $x_i$ and $y$ occupy positions $(1, k)$ and $(k, 1)$, respectively. The set of $n$ positions $\{(i, i) : i \neq l, k\} \cup \{(l, k) , (k, l)\}$ is a weak transversal of $A$.


Finding difficulty to understand the fact: Without loss of generality we assume that the $n - 1$ diagonal positions of $A'$ form a weak transversal, and that the elements in these positions are $1, 1, 2, 2, \cdots , r, r, r + 1, r + 2, \cdots , r + s$ where $2r + s = n - 1$.


Ref: (Encyclopedia of Mathematics and its Applications 39) Richard A. Brualdi, Herbert J. Ryser-Combinatorial Matrix Theory (Encyclopedia of Mathematics and its Applications)-Cambridge University Press. Page: 255-256, Theorem 8.2.3

1

There are 1 best solutions below

2
On BEST ANSWER

Notice that if a matrix $M$ has a weak transversal, then you can permute the columns (or the rows) as you want, and the resulting matrix $MP$ or $PM$ still has a weak transversal.

In particular, you can swap columns to get a diagonal weak transversal.

For the rest, notice that $r$ and $s$ may also be zero, and every weak transversal has at most 2 repetition of each element inside, so $1, 1, 2, 2, \cdots , r, r, r + 1, r + 2, \cdots , r + s$ describes all possible weak transversals.