Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can we find two mutually orthogonal diagonal latin squares of orders $4$ and $8$? A diagonal Latin square is a Latin square of order $n$ where the symbols $1$ thru $n$ fil both the forward diagonal and the back diagonal? It'd be great if you could show me the actual MOLS as well as the methodology.

share|improve this question
    
I added an 8x8 example to my answer. –  Jyrki Lahtonen Jul 27 '12 at 13:23

3 Answers 3

This may also be of interest. From the two 4x4 squares given in a previous answer, two 8x8 squares can be grown.

If we transpose the symbols thus;

Identical squares, different symbols

The two squares are different only by the chosen symbols the cells contain.

a) Place the two latin squares side by side to give a rectangle.

b) Then swap rows 2 and 4 with the transposed rows 2 and 4 to give;

Rectangle 1/2 square

c) Then take the resulting rectangle from b) and copy it backwards below the rectangle resulting from b).

Then we get;

8x8 square from 4x4 latin square

The same process may be performed again and again from the resulting squares, swapping each even numbered rows.

share|improve this answer

$$\matrix{1&3&4&2\cr4&2&1&3\cr2&4&3&1\cr3&1&2&4\cr}\qquad\matrix{2&3&1&4\cr4&1&3&2\cr3&2&4&1\cr1&4&2&3\cr}$$

share|improve this answer

Let $F$ be a field of 8 elements (this would work for 4 as well). It is a standard fact that for non-zero elements $\alpha\in F$, the formula $L_\alpha(x,y)=x+\alpha y$ produces a latin square. Furthermore, $L_\alpha$ and $L_{\alpha'}$ are MOLS, if $\alpha\neq\alpha'$. The diagonal consists of the elements $L(x,x)$, but to get a specific back-diagonal we need to use a specific ordering. The following will work. Start placing elements of $F$ into a linearly ordered list. We append elements to both ends of the list as follows. When we put a new element $x$ to become the first entry, we immediately follow up by putting $1+x=1-x$ to the end of the list. We then use this ordering for both rows and columns. If we do it this way, the other diagonal consists of elements $L(x,1+x)$.

So the main diagonal of $L_\alpha$ has the elements $L_\alpha(x,x)=(\alpha+1)x$. This list contains all the elements of $F$, iff $\alpha+1\neq0$, in other words, iff $\alpha\neq1$. The other diagonal of $L_\alpha$ has the elements $L_\alpha(x,1+x)=\alpha+(\alpha+1)x$. These are also all distinct, iff $\alpha\neq1$.

Therefore we get two MOLS with all the entries occuring on both diagonals by selecting two distinct non-zero and non-1 values for $\alpha$, and by using an ordering of the field elements of a given type. As the field contains either 4 or 8 elements, there are at least two choices for $\alpha$ remaining, so we succeed.


Let us give an example of a pair of $8\times8$ MOLS. We start by constructing the field of 8 elements. To that end I declare $\alpha$ to be a root of the primitive polynomial $x^3+x+1\in \mathbb{F}_2[x]$. Then we have $\alpha^3=\alpha+1$, $\alpha^4=\alpha^2+\alpha$, $\alpha^5=\alpha^2+\alpha+1$, $\alpha^6=\alpha^2+1$ (and, of course, $\alpha^7=1$).

An ordering of the type describe above would then be $x_0=0$, $x_1=\alpha$, $x_2=\alpha^2$, $x_3=\alpha^4$, $x_4=x_3+1=\alpha^5$, $x_5=x_2+1=\alpha^6$, $x_6=x_1+1=\alpha^3$, $x_7=x_0+1=1$.

The latin square $L_{\alpha}(i,j)=x_i+\alpha x_j, 0\le i,j\le 7,$ then has the entries (the version lists entries as elements of $\mathbb{F}_8$, in the latter version I replaced these with their subscripts from the chosen ordering): $$ L_{\alpha}=\pmatrix{ 0&\alpha^2&\alpha^3&\alpha^5&\alpha^6&1&\alpha^4&\alpha\cr \alpha&\alpha^4&1&\alpha^6&\alpha^5&\alpha^3&\alpha^2&0\cr \alpha^2&0&\alpha^5&\alpha^3&1&\alpha^6&\alpha&\alpha^4\cr \alpha^4&\alpha&\alpha^6&1&\alpha^3&\alpha^5&0&\alpha^2\cr \alpha^5&\alpha^3&\alpha^2&0&\alpha&\alpha^4&1&\alpha^6\cr \alpha^6&1&\alpha^4&\alpha&0&\alpha^2&\alpha^3&\alpha^5\cr \alpha^3&\alpha^5&0&\alpha^2&\alpha^4&\alpha&\alpha^6&1\cr 1&\alpha^6&\alpha&\alpha^4&\alpha^2&0&\alpha^5&\alpha^3\cr}, $$ or $$ L_{\alpha}=\pmatrix{ 0&2&6&4&5&7&3&1\cr 1&3&7&5&4&6&2&0\cr 2&0&4&6&7&5&1&3\cr 3&1&5&7&6&4&0&2\cr 4&6&2&0&1&3&7&5\cr 5&7&3&1&0&2&6&4\cr 6&4&0&2&3&1&5&7\cr 7&5&1&3&2&0&4&6\cr}. $$ Similarly we get that $$ L_{\alpha+1}=\pmatrix{ 0&3&4&7&1&2&5&6\cr 1&2&5&6&0&3&4&7\cr 2&1&6&5&3&0&7&4\cr 3&0&7&4&2&1&6&5\cr 4&7&0&3&5&6&1&2\cr 5&6&1&2&4&7&0&3\cr 6&5&2&1&7&4&3&0\cr 7&4&3&0&6&5&2&1\cr}. $$ The general theory tells us that $L_\alpha$ and $L_{\alpha+1}$ are MOLS. We observe that, in accordance with the earlier part of the solution, they both have the required extra property. We also observe that the two MOLS share the same set of columns. This is built in to the method of construction.

share|improve this answer
    
Alternatively we could arrange the other diagonal to have entries $L(x,\gamma-x)=L(x,\gamma+x)$ for any non-zero "pairwise sum $\gamma\in F$". Also note that this is specific to characteristic two. In other characteristics we might place zero in the middle and pair up $x$ and $-x$. –  Jyrki Lahtonen Jul 19 '12 at 17:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.