An r × n Latin Rectangle [LR] based on 1, …, n is a 2-dimensional array of r rows and n columns, where r < n, such that each entry is one of the integers 1, …, n and each of these integers occurs at most once in each row and at most once in each column.
Is it true that every r × n LR can be extended to an n × n LR (a Latin square [LS])? Why or why not?
Okay so my way of checking this is to first see what conditions need to be met that would make a LR unable to conform to a LS.
I will be making an assumption that the only case we need to worry about is the case where r = n-1 because that is the most confined example. And to convert every other example where r < n-1 to a LS is just a series of steps more trivial than the final step of the r=n-1 case.
So lets say we start with LR that is (n-1)xn.
In this case each column contains (n-1) unique integers from a set of n integers. Each column also has 1 available slot left as well as one possible integer left that can fill it. The only way this rectangle can't become a LS is if two of those columns have the same set of unique integers, or in other words, if two columns are missing the same integer. This would invalidate the last row and disqualify it as a LS.
Okay so how can we check this? First I looked at a concrete example. n=4 and column_1=[1, 2, 3]T (where T is meant to show that this is a column not a row)
So I want to try to make a another column with the same 3 integers and then use that as a base to create a valid LR. There are two valid columns: [2, 3, 1]T and [3, 1, 2]T.
Lets take that first valid column, so our base is:
[1, 2]
[2, 3]
[3, 1]
Now each row has two open spots as well as two missing integers. The problem that becomes apparent though, is that you have three rows that are missing a 4 but only two available columns to place them. And this happens regardless of which valid column_2 you choose, if that column_2 contains the same (n-1) integers.
This proves that it is impossible to create an rxn LR that cannot be converted into a LS, if given r=n-1. I would argue that based on the assumption mentioned earlier, this proves that every r × n LR can be extended to an n × n Latin square
Now if you need more convincing, you'd need to see if its possible to create an (n-1)xn LR, starting with an (r < n-1)xn LR. If you could show that, then it would show that it's possible to create a LR that gets to the point where no more valid rows can be added.
I looked into this as well and started with: n=5, r=3, and column_1=[1, 2, 3]T.
We have the same two valid columns, so I went with the same base and extended the first row using the trivial case of 1 to n in order:
[1, 2] [1, 2, 3, 4, 5]
[2, 3] -> [2, 3]
[3, 1] [3, 1]
Our options for filling this in are limited, and the valid ways are no different from each other. Two rows have three missing ints. each row is missing an int that is "unrestrained", meaning it can be in any column. Both rows contain two ints that only have two available columns. That leaves us with two valid solutions that don't differ in any meaningful way for our purposes. So I went with this:
[1, 2, 3, 4, 5]
[2, 3, 4, 5, 1]
[3, 1, 5, 4, 2]
Now can we turn this into an r=n-1xn LR? More precisely, can we turn it into a LR that contains two columns with the same (n-1) integers in them? Right now we only have two columns containing the same integers. (this is what I meant by "two valid solutions that don't differ in any meaningful way" both solutions don't change the fact that the only two columns with the same three integers are our first two columns)
To prove this case can't get to a valid LS we have to be able to add a single row while also adding the same integer to columns 1 and 2. This is obviously impossible, because it requires a row with two of the same integer and therefore not a valid LR. Therefore, no r < (n-1)xn can become a valid (n-1)xn LR that also contains two columns with the same (n-1) unique integers in them.
TL;DR Every r×n LR can be extended to an n×n Latin square, because it is impossible to create a valid (n-1)xn LR that can't be turned into a valid LS. And it's impossible to create a valid r < (n-1)xn LR that can be turned into a valid (n-1)xn LR that also contains two columns with the same (n-1) unique integers in them.