Skip to content

Latin square solutions (1)

The four “Easy exercises” and six (harder) “Problems” were here. This post gives the solutions to the exercises.

Lemma 1 Given any two MOLS of order \(n\) we can derive two MOLS with one in reduced form and the other having the first row \(1,\dots,n\)

Consider the superimposed array (like the example of order 4 in the earlier post). By permuting its columns and then its rows, we can get one of the Latin squares into reduced form. Then by permuting the symbols used for the other Latin Square we can get its top row to \(1,\dots,n\). This permutation preserves both its Latin property and its orthogonality to the other Latin square. \(\Box\)

E1 Show that it is impossible to construct two MOLS of order 2.

It is obvious that the only Latin square with top row \(1,2\) is \(\left(\begin{array}{cc} 1&2\\2&1\end{array}\right)\), but this square is not orthogonal to itself because the pair \(2,2\) appears twice and the pair \(2,1\) does not appear. \(\Box\)

E2 Show that there are at most \(n-1\) MOLS of order \(n\).

Suppose there were \(n\). For each square we can permute its symbols to get the top row as \(1,\dots,n\). This will preserve the Latin property and will not affect the squares orthogonality to the other squares. Now consider the first cell in the second row. If any two squares have the same symbol \(k\) in this cell, then they are not orthogonal, because they also have the same symbol \(k\) in the cell in column \(k\) of the top row. So all squares must have a different symbol in the first cell in the second row. That means one of them must have the symbol 1, but it also has the symbol 1 in the first cell of the top row, so it is not Latin. Contradiction. \(\Box\)

E3 Find all degenerate finite projective planes, in other words, finite sets of points and lines which satisfy (A) any two distinct lines intersect in just one point, (B) any two distinct points lie on just one line, but which do not satisfy (C) there are four points, no three of which lie on the same line.

Note that any configuration of points and lines satisfying (A) and (B) has a dual configuration obtained by interchanging points and lines, but preserving “incidence” (the property of a point being on a line). So if the original configuration has a point A and a line L, then in the dual configuration the line A contains the point L if and only if point A lies on line L in the original. A configuration is self-dual if it is the same as its dual.

All degenerate configurations fall into two infinite families :

(1) a point \(P\) not lying on a line \(L\) and \(n\ge 0\) lines through \(P\), each meeting \(L\) in one point (so a total of \(n+1\) points and \(n+1\) lines. For each \(n\) this configuration is self-dual;

(2) a point \(P\) lying on a line \(L\), \(n\ge 0\) additional lines passing through \(P\) and \(m\ge 0\) additional points lying on \(L\). Both \(P\) and \(L\) are optional, so the configuration includes as special cases: the empty configuration (no lines or points); a single point \(P\) with zero or more lines passing through it; and a single line \(L\) with zero or more points on it. Every configuration in (2) is self-dual or dual to another configuration in (2).

It is obvious that configurations in (1) or (2) are degenerate since they do not satisfy (C). If we require that at most two points lie on any line, then a configuration in (1) includes at most 3 points and a configuration in (2) at most two.

It is clear that the empty configuration, a single point, a single line, and a single point lying on a single line are all covered in (2). A single point and a single line which does not contain it is covered by (1).

If a configuration includes two points, then it must also include a line \(L\) containing them. Suppose all the points in the configuration lie on \(L\). If all the lines pass through one of these points, then we have (2). (Note that if there are just two lines, then this case is also in (1). If we want to make (1) and (2) disjoint families, then in (1) we must require \(n\ne 1\)). If not, then \(L\) contains two points \(P\) and \(Q\) each with another line through them. But these lines must meet at a point \(R\) not on \(L\). Contradiction. So that exhausts possible configurations with all the points on \(L\).

So suppose we have a line \(L\) containing (at least) two points and a point \(P\) not on \(L\). Then for each point \(A\) on \(L\) there is a line containing \(P\) and \(A\), so we have (1). If we add another point not on \(L\) and not on any of the lines \(PA\), then the configuration is not degenerate. So the only case we need to consider is adding a point to one of the lines \(PA\).

If \(L\) contains only two points \(A,B\), then adding one or more additional points to \(PA\) gives another configuration in (1) (relabel \(B\) as \(P\) and the line \(PA\) as \(L\)). But if we add a point \(Q\) to \(PA\) and a point \(R\) to \(PB\) then the points \(A,B,Q,R\) satisfy (C), so the configuration is not degenerate. Similarly, if \(L\) has at least three points \(A,B,C\) and we add a point \(Q\) to \(PA\), then the lines \(QC\) and \(PB\) must intersect in a point \(R\) and the points \(A,B,Q,R\) satisfy (C). \(\Box\)

E4 Suppose that a particular line in a finite projective plane contains just \(n+1\) points with \(n\ge 2\). show that: (1) every line contains just \(n+1\) points, (2) every point is on just \(n+1\) lines, (3) there are a total of \(n^2+n+1\) points and \(n^2+n+1\) lines.

Call the particular line \(L\). Take \(P\) to be any point not on \(L\) – such a point must exist to avoid degeneracy. Any line through \(P\) must intersect \(L\) and any two distinct lines through \(P\) must meet \(L\) in two different points. Conversely, given any point on \(L\) there is a line through it and \(P\). So the number of lines through \(P\) is the same as the number of points on \(L\). Hence there are \(n+1\) lines through \(P\). Moreover, any other point \(X\) (not \(P\) or a point on \(L\)) must lie on one of the lines through \(P\), because otherwise the line \(PX\) would meet \(L\) in an additional point.

At least one of the lines through \(P\) must have a third point to avoid degeneracy. So suppose the points on \(L\) are \(A_1,\dots,A_{n+1}\) and that the additional point \(K_1\) lies on \(PA_1\). Now every line through \(K_1\) must cut \(L\) in a distinct point, so there must be exactly \(n+1\) lines through \(K_1\). There is nothing special about \(K_1\), so every on a line through \(P\) (except possibly \(P\) itself or one of the points \(A_i\)) must have exactly \(n+1\) lines through it.

Each of the \(n+1\) lines through \(K_1\) must cut the line \(PA_i\) (for \(i\ne 1\)) in a distinct point, so each of the lines \(PA_i\), except possibly, \(PA_1\) has exactly \(n+1\) points. Now \(n\ge 2\), so \(A_2,A_3\) exist and \(K_1A_2\) must meet \(PA_3\) in a point \(K_3\). By the same argument as above there are exactly \(n+1\) lines through \(K_3\) and hence exactly \(n+1\) points on \(PA_1\).

But \(P\) was any point not on \(L\). We are given that \(L\) has \(n+1\) points. Any other line must meet at least one of \(PA_1,PA_2\) in a point not on \(L\) and the argument above shows that any line through that point has exactly \(n+1\) points. That establishes (1).

We have already shown that any point \(P\) not on \(L\) has exactly \(n+1\) lines, so to establish (2) we need only show that each \(A_i\) is on exactly \(n+1\) lines. But there is a one-one correspondence between lines through \(A_i\) and points on \(PA_j\) for \(j\ne i\), so there are exactly \(n+1\) lines through \(A_i\). That establishes (2).

We have already shown that all the points line on one of the \(n+1\) lines through \(P\). Each such line has \(n\) points apart from \(P\), so the total number of points is \(n(n+1)+1=n^2+n+1\). Similarly every line apart from \(L\) itself meets \(L\) in one of the points \(A_i\). \(n\) lines (apart from \(L\) itself) pass through each \(A_i\), so there are a total of \((n+1)n+1=n^2+n+1\) lines. \(\Box\)

Post a Comment

Your email is never published nor shared. Required fields are marked *