Orthogonality of ordinary squares

Task number: 3902

An ordinary square of order \(n\) is an array \(n \times n \) with elements from the set \(\{1{,}2,\ldots,n\}\).

The orthogonality of ordinary squares is defined in the same way as for Latin squares (i.e. \( A \) is orthogonal to \( B \) if and only if \((a_{ij},b_{ij})=(a_{k\ell},b_{k\ell}) \Rightarrow (i,j)=(k,\ell)\)).

Prove that there exists a set of \(t\) mutually orthogonal Latin squares of order \( n \) if and only if when there is a set of \(t+2 \) mutually orthogonal ordinary squares of order \(n\).

  • Hint

    Find transformations that convert one set of squares to another.

  • Solution

    If we have \(t\) pairwise orthogonal Latin squares, then by adding a square with constant rows and a square with constant columns we get \(t+2\) ordinary squares.

    Newly added are orthogonal to each other. For any prescribed pair of symbols, the position of the row is determined from the first added and the position of the column from the second.

    A square with constant lines is orthogonal to Latin squares. For any prescribed pair of symbols, the position of the line is determined from the added one and in the Latin square, each symbol appears exactly once in this line.

    The orthogonality of the second added square can be proved in the same way, only the columns are used instead of the rows.

    For the opposite implication, the squares need to be transformed into a set containing the two. If we use some permutation on all \(n^2\) fields of an ordinary square, we get an ordinary square again. In addition, if we use the same permutation on all squares, the mutual orthogonality is preserved.

    Now it suffices to find a permutation such that one of the squares has constant rows and the other has constant columns. Orthogonality to these two means that the symbols are not repeated in either the row or the column.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Proving or derivation task
Cs translation
Send comment on task by email