Rank-reducibility of Latin squares

106 Views Asked by At

Consider the following Latin square with rank $N= 9$: $$ \begin{bmatrix} 5 & 3 & 1 & 2 & 4 & 7 & 6 & 8 & 9 \\ 3 & 7 & 9 & 6 & 8 & 4 & 5 & 2 & 1 \\ 8 & 5 & 4 & 9 & 1 & 2 & 7 & 3 & 6 \\ 9 & 2 & 3 & 8 & 7 & 6 & 1 & 4 & 5 \\ 7 & 4 & 5 & 3 & 9 & 1 & 2 & 6 & 8 \\ 6 & 1 & 2 & 5 & 3 & 9 & 8 & 7 & 4 \\ 2 & 9 & 6 & 7 & 5 & 8 & 4 & 1 & 3 \\ 4 & 8 & 7 & 1 & 6 & 5 & 3 & 9 & 2 \\ 1 & 6 & 8 & 4 & 2 & 3 & 9 & 5 & 7 \\ \end{bmatrix}$$

This LS is rank-reducible, as it has the property that we can obtain a Latin square $L'$ with rank $N'=8$ directly from it.

The value $9$ in $L_{4,1}$ is the key to this reduction. For every row $R$, if $L_{R,C} = 9$ then $L_{R,1} = L_{4,C}$.

This allows us to remove row 4 and column 1, change each $L_{R,C} = 9$ to $L_{R,1}$ in the remaining rows, and the result will be a Latin square of rank $N=8$: $$ \begin{bmatrix} 3 & 1 & 2 & 4 & 7 & 6 & 8 & 5 \\ 7 & 3 & 6 & 8 & 4 & 5 & 2 & 1 \\ 5 & 4 & 8 & 1 & 2 & 7 & 3 & 6 \\ 4 & 5 & 3 & 7 & 1 & 2 & 6 & 8 \\ 1 & 2 & 5 & 3 & 6 & 8 & 7 & 4 \\ 2 & 6 & 7 & 5 & 8 & 4 & 1 & 3 \\ 8 & 7 & 1 & 6 & 5 & 3 & 4 & 2 \\ 6 & 8 & 4 & 2 & 3 & 1 & 5 & 7 \\ \end{bmatrix}$$ If the pivot value in $V=L_{4,1}$ was any other value than 9, we would just swap the values $V$ and $9$ throughout the square before proceeding with the reduction.

I wonder, then, are there any other cases which would allow a similarly direct construction of a reduced-rank Latin square?

1

There are 1 best solutions below

2
On

You're essentially doing transversal prolongation in reverse.

A transversal is a set of entries with one representative from each row, each column, and each symbol. We can extend a Latin square of order $n$ with a transversal to a Latin square of order $n+1$ by (a) replacing the transversal with a new symbol, (b) adding the corresponding symbols to the new margins, and (c) placing the new symbol in the intersection of the new margins.

Here's a simple example:

$\begin{bmatrix} 3 & 1 & \color{red}{\mathbf 2} \\ \color{red}{\mathbf 1} & 2 & 3 \\ 2 & \color{red}{\mathbf 3} & 1 \\ \end{bmatrix} \longmapsto \begin{bmatrix} 3 & 1 & \color{blue}{\mathbf \infty} & \color{red}{\mathbf 2} \\ \color{blue}{\mathbf \infty} & 2 & 3 & \color{red}{\mathbf 1} \\ 2 & \color{blue}{\mathbf \infty} & 1 & \color{red}{\mathbf 3} \\ \color{red}{\mathbf 1} & \color{red}{\mathbf 3} & \color{red}{\mathbf 2} & \color{blue}{\mathbf \infty} \\ \end{bmatrix} $

In your example, you've started off with a prolonged Latin square (with its rows and columns permuted), and have discovered the Latin square it was prolonged from.

This construction generalizes to $k$-plexes ($k$ representatives of each row, column, and symbol) where $k \leqslant n/2$.