A note on embedding latin rectangles

Summary

Introduction

The well-known theorem of H. J. Ryser [12] giving necessary and sufficient conditions for an r × s latin rectangle on 1, …, n to be embedded in an n × n latin square on 1, …, n was used by T. Evans [2] (and independently by S. K. Stein) to show that an incomplete n × n latin square on 1, …, n can be completed to a 2n × 2n latin square on 1, …, 2n. A similar, but somewhat more complicated, pair of theorems concerning symmetric latin squares was proved by A. Cruse [1].

The purpose of this note is to give alternative and, in my opinion, simpler proofs of the theorem of Ryser and the analogous theorem of Cruse. Ryser's theorem generalizes M. Hall's theorem [31 that an r × n latin rectangle on 1, …, n can be embedded in an n × n latin square on 1, …, n, but the methods of proof seem to be rather dissimilar. The proof of RyserTs theorem which is given here is very obviously a simple generalization of the original proof of M. Hall's theorem.

There are still some open problems in this area (see [5], [71), so it is possible that the existence of these alternative proofs may help towards the solution of some of these problems.