Talk:Latin square

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Mid Priority
 Field: Discrete mathematics
WikiProject Statistics (Rated C-class, High-importance)
WikiProject icon

This article is within the scope of the WikiProject Statistics, a collaborative effort to improve the coverage of statistics on Wikipedia. If you would like to participate, please visit the project page or join the discussion.

C-Class article C  This article has been rated as C-Class on the quality scale.
 High  This article has been rated as High-importance on the importance scale.
 


Latin squares and mathematical puzzles[edit]

I added a paragraph on a mathematical puzzle that illustrates a generalized version of Latin-square orthogonality. Cullinane 17:33, 14 August 2005 (UTC)

Explanation of reverts[edit]

User:Patrick made quite a few changes which I reverted. The main error is in the interprettation of the square as a multiplication table. In this case the rows and columns are assumed indexed by the elements of the quasigroup. It is not the first row and first column that form the index. Reduced Latin squares correspond to quasigroups with an identity element, aka loops. For quasigroups without identity, the multiplication table is not reduced. Also, it is certainly NOT true that all the quasigroups on 4 elements are groups; the discussion of squares of order 4 is inaccurate. --Zero 01:07, 22 November 2005 (UTC)

I made some clarifications and corrections:
There are 576 Latin squares of size 4. Each can be interpreted as a multiplication table of a loop (i.e., a quasigroup with an identity element) where the indexes of the first row and first column both are the identity, hence the element in the first row and column is the identity, and the first element in each row is the row index, and the first element in each column is the column index.
Rearranging the 2nd to 4th row such that the order of the row indexes is the same as that of the column indexes, the number of possibilities reduces by a factor 6 to 96. Considering that the order of the elements is only a matter of notation of the table, the number of possibilities reduces again by a factor 6 to 16. Thus for a given set {a,b,c,d} we get 16 loops, which all turn out to be groups. There are 4 versions of the Klein four-group, differing only by the choice of which of the 4 elements is the identity. Apart from that there is only one, corresponding to the fact that the permutations of the other three elements form the automorphism group of this group, i.e., all three play the same role. The remaining 12 are all versions of the cyclic group of order 4, differing by the choice of which of the 4 elements is the identity, and which of the other 3 has order 2. Apart from that there is only one, corresponding to the fact that interchanging the remaining two elements generate the automorphism group of this group.
Frankly I don't see the point of any of the above. --Zero 11:41, 22 November 2005 (UTC)
The article only gives two 4x4 examples. My text discusses all Latin squares and is obviously more comprehensive. If you have criticism, that should be much more specific (errors, unclarities, etc.).--Patrick 12:23, 22 November 2005 (UTC)
This article is primarily about the combinatorial objects called Latin squares, not so much about algebraic structures related to them. From the combinatorial point of view, there are only two types of Latin square of order 4 since the others are all paratopic to one of those. So the existing list is complete (for order 5, also). Latin square do not have row and column indices (other than row and column numbers like every matrix has); rather, those indices are what must be added to a Latin square to make it into a multiplication table. Most of what you wrote above is about loops and groups and I don't think it would improve this page. --203.113.233.38 22:53, 22 November 2005 (UTC)
But it looks like the algebraic structures are not so different from "combinatorial objects", it is a way of explaining how 576 cases reduce to 2. If you like you can present the reasoning without (quasi)group terminology.--Patrick 00:30, 23 November 2005 (UTC)
The equivalence class operations are correctly defined in the article without any reference to algebraic structures or index rows/columns. That is the correct approach in an article on Latin squares, imo. Given those definitions, a demonstration of what happens for n=4 ought to use those definitions and not go off to another domain. --Zero 09:26, 23 November 2005 (UTC)

To see how many equivalence classes of each type there are is trivial for n=4. There are 4 reduced squares - two (A,B) with 2 in the (2,2) position and one each (C,D) with 3 or 4 in the (2,2) position. Every square is isotopic to one of A,B,C,D since every square can be reduced by sorting the rows and columns.

A =\begin{matrix} 1&2&3&4\\2&1&4&3\\3&4&1&2\\4&3&2&1\end{matrix}\quad
             B =\begin{matrix} 1&2&3&4\\2&1&4&3\\3&4&2&1\\4&3&1&2\end{matrix}\quad
             C =\begin{matrix} 1&2&3&4\\2&3&4&1\\3&4&1&2\\4&1&2&3\end{matrix}\quad
             D =\begin{matrix} 1&2&3&4\\2&4&1&3\\3&1&4&2\\4&3&2&1\end{matrix}

B is isotopic to C (swap rows 2,3, columns 2,3, and symbols 2,3). C is isotopic to D (swap rows 3,4, columns 3,4, and symbols 3,4). Next note that A contains six 2x2 Latin subsquares but B,C,D contain only four. Since all the operations that define paratopism preserve Latin subsquares, A lies in a different main class from B, C, D. Therefore there are two isotopy classes and two main classes. --Zero 09:26, 23 November 2005 (UTC)

I made a separate article, Small Latin squares and quasigroups. There seems to be an error in the above: of A and B, one is isotopic to C and D. Swapping the first two columns and the last two rows of A does not preserve the reduced form.--Patrick 10:31, 23 November 2005 (UTC)
Also, three have one Latin subsquare, and one has 6. The reasoning can still be used.--Patrick 10:54, 23 November 2005 (UTC)
Sorry, it is now fixed, I hope. --Zero 11:42, 23 November 2005 (UTC)
Of the 576 Latin squares, 288 are solutions of the 2 ×2 version of Sudoku, sometimes called Shi Doku [1]. With first row abcd and first column acbd this reduces to 2.
That could be mentioned in the existing section on Sudoku squares. --Zero 11:41, 22 November 2005 (UTC)
What do you think?--Patrick 03:01, 22 November 2005 (UTC)

Name[edit]

Doesn't the name Latin Square originate from the ?first known example (from Roman times), namely the word square Sator Arepo Tenet Opera Rotas? Ben Finn 16:39, 2 April 2006 (UTC)

No, that is not a Latin square in the meaning of this article. For example, it has no "T" in the second row. As far as I have heard, the earliest known Latin squares appeared in Arabic manuscripts around the 12th century; this needs to be researched and put in the article. The name "Latin square" was coined by Euler in his paper of 1782 with a rather weak justification: he used Latin letters as the symbols. McKay 07:19, 17 May 2006 (UTC)

I believe that the term "Latin square" originates with Cayley (can't remember where I read that though), who was referring to Euler's work of 1782. Euler was using orthogonal Latin squares, one written with Latin letters and the other with Greek letters, so when Cayley wanted to talk about only one of the pair, he referred to the "Latin" square of Euler. Wcherowi (talk) 21:32, 10 August 2011 (UTC)

Donald Knuth has found references back to the 14th century for orthogonal latin squares. See [[2]]. —Preceding unsigned comment added by Neilerdwien (talkcontribs) 05:56, 5 December 2007 (UTC)

Isotopy classes of order 7[edit]

The correct value is 564, not 563. See [3] for the history of this error. This is accepted by Colbourn and Dinitz. --McKay 07:29, 12 April 2006 (UTC)

References[edit]

Where are the references for this article?

The article looks really useful for my purposes. I have found vague allusions to some of these concepts in other resources, and discovered others on my own, but this is the only resource I have found that clearly and succinctly explains all of these concepts in one place (with better notation and terminology than I have found elsewhere).

However, for me to refer to this material for my project, I need to know where it came from, so I need references. In particular, I need to know the origin of the orthogonal array representation, and the table of latin square equivalence classes.

I will try to find a journal article that introduces these concepts, and if I do I will try to remember to come back and post those references here.DonkeyKong the mathematician (in training) 04:26, 16 May 2006 (UTC)

It seems that the paper ([4]) that McKay mentioned above is a suitable reference for most of the information in this article.
I'm new to Wiki editing, so I don't know how to put references into an article. If someone else could put that reference in there that would be good. Thanks.
You can download a citation from [5] (i don't know if that's helpful)
DonkeyKong the mathematician (in training) 06:19, 16 May 2006 (UTC)

Question[edit]

If all Latin squares can be reduced, does this not mean that every quasigroup is a loop? —The preceding unsigned comment was added by 149.135.97.128 (talk) 11:08, 10 January 2007 (UTC).

No. The operations which can be used to reduce a Latin square (permutation of the rows and columns) change the quasigroup to a different quasigroup. These operations are called isotopies, so the conclusion is that every quasigroup is isotopic to a loop. It is not true that every quasigroup is a loop. McKay 02:40, 11 January 2007 (UTC)

Latin Squares and projective \ affine planes[edit]

I might be missing something, but shouldn't the article include a note (or a section) about the relation of Latin squares to projective (or affine) planes? Denes and Keedwell show a proof of this in "Latin Squares and Their Applications" (although I don't think the proof is theirs).

Gal Diskin —The preceding unsigned comment was added by 85.65.215.115 (talk) 17:23, 11 January 2007 (UTC).

Orthogonal Latin Squares[edit]

This note is a reminder for me and others that it might be worthwhile to include something about Orthogonal latin squares, as detailed e.g in [6]. The problem of constructing such matrixes and especially the impossible 6x6 matrix problem has been popularized in a number of books and articles and might make a good read. Also, in the section about error correcting codes, I committed the sin of writing "orthogonal latin squares" without defining what it means. :-] EverGreg 15:34, 13 May 2007 (UTC)

Problem with mention of orthogonal Latin squares[edit]

The article states, in its first reference to orthogonal Latin squares:

"Sets of Latin squares that are orthogonal to each other have found an application as error correcting codes in situations where communication is disturbed by more types of noise than simple white noise, such as when attempting to transmit broadband internet over powerlines. [1] [2] [3]"

Unfortunately, the word orthogonal in this sense has *not* been defined previously, which makes this mention of the word orthogonal inappropriate. Further, the word "orthogonal" *has* been used previously (unnecessarily, in my opinion) to discuss the simple ordinary representation of a Latin square as a matrix, which the article somehow feels the need to refer to as an "orthogonal array".

It is certainly a good idea to discuss orthogonal Latin squares in this article, but this must be done in such a way that the concept is defined and the terminology is clear before it starts to be used without definition.

I hope this problem can be fixed.Daqu (talk) 22:44, 20 February 2009 (UTC)

Applications for experimental design[edit]

I came here looking for how Latin squares are used in experimental design. It's mentioned in the intro, but I wonder if an expert could add a paragraph under applications. I'm at a conference and a lot of people have mentioned how they used Latin squares for randomizing their experiments, and I don't know what they mean, so I thought that might be a good thing to have here. Thanks 209.255.241.2 (talk) 16:54, 25 March 2010 (UTC)

You've got a good point. Information on this is rather fragmented on wikipedia. OK starting points are Blocking (statistics), Randomized block design and especially Hyper-Graeco-Latin square design. The bigger picture may perhaps be found in Design of experiments. None of these are the readable introductions they should have been, but hopefully they work as pointers to further reading in the literature. The gist of it is that when you do an experiment where say four variables can each take two values (high/low) you want to try every possible combination but there may not be time or money to do that. So you want to get as much info with as few experiments as possible. First you ofcourse avoid doing the same experiment twice, but you also want to avoid that two of your variables change in lockstep in each experiment, because then you wouldn't have been able to tell their effects apart. Following a latin square is one way to design a good set of experiments. EverGreg (talk) 18:17, 25 March 2010 (UTC)
I'll start adding some references on Latin squares here. When I'm done, I'll update the article. Kiefer.Wolfowitz (talk) 20:22, 22 May 2010 (UTC)

Merger proposal[edit]

An anonymous user proposed a merger. It seems straightforward to me to put Graeco-Latin square as a chapter of Latin square. In addition: As the previous discussions on this page shows, it's a problem that orthogonal latin squares are not properly defined here, they seem to tie in closely with the text. The Graeco-Latin article seems to go a long way in defining it, so this could be a good start, though the text in the Graeco-Latin article is less accessible than that of Latin square. (That is, I still don't know what "a orthogonal latin square" is, and barely what two mutually orthogonal ones are.) EverGreg (talk) 22:10, 5 April 2010 (UTC)

Don't merge There are enough subtopics of Latin square to need different articles. A basic Latin square is essentially about one factor in addition to rows or columns, a Graeco-Latin square about two or more. As for orthogonal Latin squares, they have to come in comparison of pairs: there must be at least one cell (and so implicitly exactly one out of the n2 cells) which has any particular combination of the n posible values of each of the two symbols being considered.--Rumping (talk) 16:41, 22 July 2010 (UTC)
Due to the fact that no agreement has been reached — and only two comments — in eight months, I am removing the merge templates from each page. Supertouch (talk) 00:31, 4 November 2010 (UTC)

Error in example[edit]

The examples for the two latin squares of order 5 at the end of the text are from the same main class. Correct representatives for the two main classes are given at http://cs.anu.edu.au/~bdm/data/latin.html . In one of the main classes, all ordered pairs of numbers must be at most once within the square, none of the currently given squares have this property.Random rings (talk) 12:45, 4 June 2010 (UTC)

Orthogonal array representation (refers to non-existing figure)[edit]

It says" the orthogonal array representation of the first Latin square displayed above is:" But this example refers to a square with numbers which is not displayed in the article.(maybe it has been edited out at some time) Should we change this to (1,1,A), (1,2,B) and so on? Or put back the original figure. The whole expression "the first latin square displayed above" is also a bit vague. (figure number nn might be better?)Bj norge (talk) 19:00, 14 April 2011 (UTC)

Error Correction Codes Example Unclear[edit]

Questions: 1. There are four frequencies and four time slots. What then is the meaning of 'the letter A would then be picked up as: 12 12 123 124'? 2. 'But the 1,2 case is the only one that yields a sequence matching a letter in the above table...'. Should it read 'sequence' instead of 'case'? 3. 'Again, we are able to infer from the table of encodings that it must have been the letter A being transmitted.' Is it too much to spell out *why* we are able to infer this? — Preceding unsigned comment added by Polariseke (talkcontribs) 15:54, 24 February 2012 (UTC)