1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Determine the number of Pairwise Non-Isotopic Latin Squares

  1. Oct 6, 2011 #1
    1. The problem statement, all variables and given/known data

    Basically, everything's in the title. I'm asked to find the number of pairwise non-isotopic Latin Squares.

    2. Relevant equations

    A non-isotopic Latin Square is one that cannot be created simply by permuting the rows/columns of another Latin Square.

    3. The attempt at a solution

    I also know that there is at least one (because having the first row and column as {1,2,3,4} will prevent permutation back to that same sequence.) However, I'm not quite sure how one would go about finding the rest (there are over 500 Latin Squares with an order of 4, so I'm not about to go trying them all; there must be a logical way to approach this.

    (Also, what is a *pairwise* Latin Square?)

    This is a Logic course, so I'm able to use induction, etc. to prove this. Just not quite sure where to start. Guidance would be awesome!
  2. jcsd
  3. Oct 6, 2011 #2
    A couple of comments:

    Be careful with the definitions; you are collapsing the collection of Latin Squares into equivalence classe. Define LS to be Latin Square(s):

    i) An isotopy class is a representative of a class of squares, where you define two squares S1,S2 to be equivalent, if you can get S1 from S2 by permuting the rows of S2(or viceversa). This is an equivalence relation, and so partitions the collection of all LS's into disjoint classes. As an example, if you select the integers and you want to know the possible remainders of integers when dividing by, e.g., 3, then you have 3 classes: {0,1,2}, or the class of elements that leave remainders of 0,1, or 2 . Then 12 and 9 are equivalent/isotopic, since they both leave the same remainder .

    ii)Pairwise-non-isotopic LS are any two Si,Sj that are in different classes, i.e., Si,Sj are non-isotopic if you cannot get Si from Sj by exchange of rows/columns.

    iii)Have you tried seeing what happens for the lower values 1x1(trivial) 2x2 and 3x3 ? Maybe you can detect a pattern. Have you thought how/if induction would help you go from nxn to (n+1)x(n+1)?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook