Латинские квадраты

[maxal]

Мапл - это и есть пакет, "пустое решение" означает, что решений нет (с точностью до багов в мапле).

[ddn]

maxal писал(а):

Мапл - это и есть пакет, "пустое решение" означает, что решений нет (с точностью до багов в мапле).

Багов в Мапле хватает.
Не рекомендую использовать оператор solve и производные от него. Находит ответ не всегда, но даже когда находит, ответ может быть неверным, даже для простейшей линейной системы.

У меня набросано несколько программок, для решения систем линейных уравнений.
Вот одна из них: процедура приведения к канонической линейной форме

> klfd:=proc(A,B,m,n)
> klf:=proc(A,B,m,n)
> local a,b,c,h,i,j,k,l,r,u;
> c:=matrix([seq([seq(convert(A[i,j],rational,exact),j=1..n),convert(B[i],rational,exact)],i=1..m)]);
> u:=vector(n+1); l:=0; j:=0; while j<n do j:=j+1; i:=l; while i<m and c[i+1,j]=0 do i:=i+1 od; if i<m then i:=i+1; l:=l+1; for k from j+1 to n+1 do h:=c[i,k]/c[i,j]; c[i,k]:=c[l,k]; c[l,k]:=h od; c[i,j]:=c[l,j]; c[l,j]:=1; for i from i+1 to m do if c[i,j]<>0 then for k from j+1 to n+1 do c[i,k]:=c[i,k]-c[i,j]*c[l,k] od fi; c[i,j]:=0 od; u[l]:=j fi od;
> i:=l; while i<m and c[i+1,n+1]=0 do i:=i+1 od;
> if i=m then a:=matrix(n,n-l); b:=vector([seq(0,i=1..n)]); u[l+1]:=n+1;
> for i from l by -1 to 1 do for j to u[i]-i do a[u[i],j]:=0 od; for k from i to l do for j from u[k]+1 to u[k+1]-1 do a[u[i],j-k]:=-c[i,j]-add(c[i,u[r]]*a[u[r],j-k],r=i+1..k) od od; b[u[i]]:=c[i,n+1]-add(c[i,u[r]]*b[u[r]],r=i+1..l);
> for k from u[i]+1 to u[i+1]-1 do for j to n-l do a[k,j]:=0 od; a[k,k-i]:=1 od od;
> for k from 1 to u[1]-1 do for j to n-l do a[k,j]:=0 od; a[k,k]:=1 od;
> RETURN([evalm(a),<seq(b[i],i=1..n)>,l]) else RETURN([[],[],n+1]) fi
> RETURN([a,b,l]) else RETURN([[],[],n+1]) fi
> end:

оставьте одну из строк с RETURN, другую удалите. Первый RETURN - для демонстрации результата, второй используйте для промежуточных расчетов. Со строками proc(A,B,m,n) поступите соответственно.

Здесь, аргументы: $A$ - матрица коэффициентов, $B$ - вектор свободных членов, $m$ - число уравнений (строк матрицы), $n$ - число переменных (столбцов матрицы); результат: $a$ - матрица коэффициентов и $b$ - вектор свободных членов для выражения переменных через свободные параметры, $l$ - число линейно независимых уравнений системы=число линейно зависимых переменных системы (если она совместна, иначе $l=n+1$), тогда $n-l$ - размерность пространства решений (число свободных параметров; равно $-1$, если система несовместна).

Пронаблюдайте:

> A:=matrix([[1,-2,0,1],[3,-1,-2,0],[2,1,-2,-1]]); B:=<-3,1,4>; m:=3; n:=4; C:=klfd(A,B,m,n); piecewise(seq(op([l=i,x[i]=add(C[1][i,j]*alpha[j],j=1..n-C[3])+C[2][i]]),i=1..n));

Вот процедурки для приведения системы уравнений магического квадрата:
здесь, аргументы: $n$ - размерность квадрата, $v$ - список векторов направлящих для пучков паралельных прямых, по которым имеет место "магическое" равенство сумм (компоненты направляющих векторов взаимно просты с $n$, либо равны $0$), $q$ - число "магических" пучков паралельных прямых, $x$ - вектор (тип name, либо vector/list of name) линейно независимых элементов магического квадрата, $s$ - имя переменной, обозначающей магическую сумму;
для простого магического (без магических диагоналей) квадрата $v=[[0,1],[1,0]]$,
для пандиагонального магического квадрата $v=[[0,1],[1,0],[1,1],[1,-1]]$;

> magkvad01:=proc(n,v,q)
> local a,b,h,i,j,k,l,m,o;
> o:=n^2+1; a:=matrix([seq([seq(0,j=1..o)],i=1..n*q)]); k:=0;
> for h to q do if v[h,2]=0 then if v[h,1]=0 then l:=0 else l:=2 fi else l:=1 fi; b:=[0,0]; for i to n do k:=k+1; for j to n do a[k,n*b[1]+b[2]+1]:=1; b:=[b[1]+v[h,1] mod n,b[2]+v[h,2] mod n] od; a[k,n^2+1]:=-1; b[l]:=b[l]+1 od od;
> RETURN(evalm(a))
> end:

результат: $a$ - матрица коэффициентов системы уравнений магического квадрата от $o=n^2+1$ переменных (элементов квадрата и, последняя по счету переменная, магической суммы), вектор свободных членов нулевой.
Пронаблюдайте:

> magkvad01(2,[[0,1],[1,0]],2);

> magkvad02:=proc(n,v,q)
> local a,b,h,i,j,k,l,m,o;
> o:=n^2+1; a:=matrix([seq([seq(0,j=1..o)],i=1..n*q)]); k:=0;
> for h to q do if v[h,2]=0 then if v[h,1]=0 then l:=0 else l:=2 fi else l:=1 fi; b:=[0,0]; for i to n do k:=k+1; for j to n do a[k,n*b[1]+b[2]+1]:=1; b:=[b[1]+v[h,1] mod n,b[2]+v[h,2] mod n] od; a[k,n^2+1]:=-1; b[l]:=b[l]+1 od od;
> RETURN(klf(a,[seq(0,i=1..n*q)],n*q,o))
> end:

результат $RET=[a,b,l]$: $a$ - матрица коэффициентов и $b$ - вектор свободных членов для выражения переменных через свободные параметры, $l$ - число линейно независимых уравнений системы=число линейно зависимых переменных системы (если она совместна, иначе $l=o+1$), тогда $o-l$ - размерность пространства решений (число свободных параметров; равно $-1$, если система несовместна).
Пронаблюдайте:

> magkvad02(2,[[0,1],[1,0]],2);

> magkvad03:=proc(n,v,q,x,s)
> local a,b,h,i,j,k,l,m,o;
> o:=n^2+1; a:=matrix([seq([seq(0,j=1..o)],i=1..n*q)]); k:=0;
> for h to q do if v[h,2]=0 then if v[h,1]=0 then l:=0 else l:=2 fi else l:=1 fi; b:=[0,0]; for i to n do k:=k+1; for j to n do a[k,n*b[1]+b[2]+1]:=1; b:=[b[1]+v[h,1] mod n,b[2]+v[h,2] mod n] od; a[k,n^2+1]:=-1; b[l]:=b[l]+1 od od;
> a:=klf(a,[seq(0,i=1..n*q)],n*q,o); b:=matrix(n,n);
> k:=0; for i to n do for j to n do k:=k+1; b[j,i]:=add(a[1][k,l]*x[l],l=1..o-a[3]-1)+a[1][k,o-a[3]]*s+a[2][k] od od;
> RETURN(evalm(b),o-a[3])
> end:

результат: $b$ - матрица элементов магического квадрата, выраженных через линейно независимые переменные, $o-a[3]$ - число линейно независимых переменных магического квадрата.
Пронаблюдайте:

> magkvad03(2,[[0,1],[1,0]],2,x,s); magkvad03(2,[[0,1],[1,0],[1,1]],3,x,s);
> magkvad03(3,[[0,1],[1,0]],2,x,s); magkvad03(3,[[0,1],[1,0],[1,1]],3,x,s); magkvad03(3,[[0,1],[1,0],[1,1],[1,-1]],4,x,s);
> magkvad03(4,[[0,1],[1,0]],2,x,s); magkvad03(4,[[0,1],[1,0],[1,1]],3,x,s); magkvad03(4,[[0,1],[1,0],[1,1],[1,-1]],4,x,s);
> magkvad03(5,[[0,1],[1,0],[1,1]],3,x,s); magkvad03(5,[[0,1],[1,0],[1,1],[1,-1]],4,x,s); magkvad03(5,[[0,1],[1,0],[1,1],[1,-1],[1,2]],5,x,s); magkvad03(5,[[0,1],[1,0],[1,1],[1,-1],[1,2],[1,-2]],6,x,s);

[Nataly-Mak]

Про Мапл слышала. А вот что значит "с точностью до багов в мапле", не знаю. Значит ли это, что точно система не имеет решения?
***
Идеальный сотовый квадрат 16-ого порядка построила только что.
Для его построения составила вспомогательный нетрадиционный сотовый квадрат (состоящий из квадратов 2х2, заполненных числами 0, 1, 2, 3), обладающий свойствами ассоциативности и пандиагональности. А затем уже по аналогии составила такой квадрат 8-ого порядка. Как я и предполагала, начальное заполнение квадрата было сделано неправильно. Поэтому вполне вероятно, что составленная система уравнений не имеет решений.
Подробности будут в статье
“Сотовые магические квадраты”.
Только что полученный результат не успела внести в статью. Хотя вспомогательный сотовый квадрат 16-ого порядка, обладающий свойствами ассоциативности и пандиагональности, там уже есть (рис. 24). Стала сейчас перечитывать статью (с целью проверки) и увидела, что это как раз такой квадрат, какой мне нужен! А составлен он был для построения совершенного сотового квадрата 16-ого порядка.

[Nataly-Mak]

Опять о латинских квадратах. Если с построением ортогональных квадратов к данному нормальному латинскому квадрату кое-что прояснилось, то с обобщёнными латинскими квадратами пока остаются вопросы.
Обобщённым латинским квадратом порядка n называется квадратная таблица n*n, среди n*n элементов которой различными будут только n штук, и любой из n различных элементов встречается ровно n раз внутри этой таблицы (определение из книги Ю. В. Чебракова).
В отличие от нормального латинского квадрата в обобщённом латинском квадрате элементы могут повторяться в строках и в столбцах.
При построении магических квадратов с помощью латинских квадратов очень часто используются именно обобщённые латинские квадраты.
Как построить ортогональный латинский квадрат, например, для такого обобщённого латинского квадрата 8-ого порядка:

0  7  2  5  5  2  7  0
1  2  7  4  4  7  2  1
2  1  4  7  7  4  1  2
3  4  1  6  6  1  4  3
4  3  6  1  1  6  3  4
5  6  3  0  0  3  6  5
6  5  0  3  3  0  5  6
7  0  5  2  2  5  0  7

Сколько ортогональных латинских квадратов можно построить для данного квадрата?
Какой-нибудь из множества разных пакетов программ умеет строить ортогональный латинский квадрат для заданного латинского квадрата? Существуют ли конкретные методы построения ортогональных латинских квадратов для случая обобщённых латинских квадратов?

[maxal]

maxal в сообщении #144895 писал(а):

Возвращаясь к вопросу о построении ортогональных латинских квадратов - это умеет делать команда MOLS из GAP'овского пакета GUAVA. Причем не только пару, но и вообще заданное количество попарно ортогональных латинских квадратов (если они существуют).

Аналогичная команда MOLS есть, кстати, и в мапле.

Еще тут всплыла такая статейка:
Brown et al. "Completion of the Spectrum of Orthogonal Diagonal Latin Squares". Lecture notes in pure and applied mathematics 139 (1992), 43-49.
в которой доказывается, что пары ортогональных диагональных латинских квадратов (из которых влёт получаются магические греко-латинские квадраты) существуют для всех порядков, за исключением 2, 3 и 6.

[Nataly-Mak]

maxal
Хорошие вы нашли результаты!
В книге Ю.В. Чебракова (Магические квадраты. Теория чисел, алгебра, комбинаторный анализ. – С. – Петербург, 1995) читаем: “… пары ортогональных диагональных латинских квадратов нельзя построить только для n = 2, 3, 6 и, возможно, 10”. Значит, до 1995 г. вопрос о существовании пар ортогональных диагональных латинских квадратов для порядка 10 оставался открытым. Правда, из данной фразы не совсем понятно, как обстояли дела с парами ортогональных диагональных латинских квадратов для других порядков n=4k+2. Надо ли понимать эту фразу так, что только с порядком 10 проблемы, а для всех остальных порядков указанной серии существование таких пар было доказано?
Ну, теперь вопрос решён окончательно. Исключение составляют только порядки 2, 3, 6, для всех остальных порядков пары ортогональных диагональных латинских квадратов существуют.
(Примечание: здесь речь идёт о классических латинских квадратах).
Тогда получается, что для построения магических квадратов порядков n=4k+2 тоже применим метод латинских квадратов.
В присланной вами статье “Completion of the Spectrum of Orthogonal Diagonal Latin Squares” (J. W. Brown и другие) приведены три пары ортогональных диагональных латинских квадратов 10-го порядка.
Вот одна из этих пар:

0 9 4 6 1 7 5 8 2 3
7 1 0 4 5 3 8 0 6 2
4 6 2 8 3 1 7 5 9 0
6 0 7 3 2 8 4 9 1 5
5 3 6 7 4 2 9 1 0 8
8 4 1 2 9 5 0 6 3 7
2 5 3 0 8 9 6 4 7 1
3 2 8 9 0 4 1 7 5 6
9 7 5 1 6 0 3 2 8 4
1 8 0 5 7 6 2 3 4 9

0 8 5 1 7 3 4 6 9 2
5 1 7 2 9 8 0 3 4 6
1 7 2 9 5 6 8 0 3 4
9 6 4 3 0 2 7 1 5 8
3 0 8 6 4 1 5 9 2 7
4 3 0 8 6 5 9 2 7 1
7 2 9 5 1 4 6 8 0 3
6 4 3 0 8 9 2 7 1 5
2 9 6 4 3 7 1 5 8 0
8 5 1 7 2 0 3 4 6 9

Для порядка 10 вообще всё очень просто получается: греко-латинский квадрат, составленный из пары ортогональных латинских квадратов, уже является готовым магическим квадратом (ну, только записанным в нетрадиционной форме, то есть он заполнен числами от 0 до 99 вместо традиционного заполнения числами от 1 до 100). Вот этот квадрат:

00 98 45 61 17 73 54 86 29 32
75 11 97 42 59 38 80 03 64 26
41 67 22 89 35 16 78 50 93 04
69 06 74 33 20 82 47 91 15 58
53 30 68 76 44 21 95 19 02 87
84 43 10 28 96 55 09 62 37 71
27 52 39 05 81 94 66 48 70 13
36 24 83 90 08 49 12 77 51 65
92 79 56 14 63 07 31 25 88 40
18 85 01 57 72 60 23 34 46 99

Кроме того, поскольку в методе латинских квадратов первый и второй вспомогательные латинские квадраты равноправны, то заодно получаем и такой магический квадрат:

00 89 54 16 71 37 45 68 92 23
57 11 79 24 95 83 08 30 46 62
14 76 22 98 53 61 87 05 39 40
96 60 47 33 02 28 74 19 51 85
35 03 86 67 44 12 59 91 20 78
48 34 01 82 69 55 90 26 73 17
72 25 93 50 18 49 66 84 07 31
63 42 38 09 80 94 21 77 15 56
29 97 65 41 36 70 13 52 88 04
81 58 10 75 27 06 32 43 64 99

Выражаю вам огромную благодарность за помощь в исследовании данного вопроса. Ещё “не переварила” всю добытую вами информацию.

[Nataly-Mak]

maxal
Вот смотрю на статью, которую вы мне прислали и, разумеется, ничего не понимаю. Перевести эту статью в Гугле не умею (это возможно?). Отправила статью для перевода брату, но это надо дня два подождать.
Так вот, смотрю… Там много всякого разного написано про порядки, это я понимаю. Но что именно написано, не понимаю. Далее: приведён латинский квадрат 5-го порядка (правда, не диагональный) и потом, как мне кажется, с помощью этого квадратика и составляется квадрат 10-го порядка. Там какие-то формулы…
Одним словом: не могли бы вы сказать, не приведён ли в данной статье метод составления диагональных латинских квадратов 10-го порядка с помощью латинского квадрата 5-го порядка?
Далее: что известно о других порядках n=4k+2? Вы писали, что доказано существование пар ортогональных диагональных латинских квадратов для всех порядков, кроме 2, 3, 6. Значит, все пары указанной серии порядков существуют. О них есть какие-то статьи? Может быть, продолжение данной статьи. Как я поняла, то, что вы прислали, это часть статьи, потому что там стоит пункт 4. Правильно?
shwedka
Вас тоже прошу подключиться к поиску статей, в которых строятся пары ортогональных диагональных латинских квадратов указанной серии порядков. Очень интересно узнать, есть ли общий алгоритм составления таких пар.
P.S. Для всех: статья Brown et al. "Completion of the Spectrum of Orthogonal Diagonal Latin Squares". Lecture notes in pure and applied mathematics 139 (1992), 43-49", о которой идёт речь, находится здесь:
http://ifolder.ru/9391205

[Nataly-Mak]

Ещё одно интересное продолжение метода латинских квадратов – для построения магических квадратов порядка n = 4k, k = 1,2,3 …
В книге Ю.В. Чебракова рассматривается построение совершенных магических квадратов методом обобщённых латинских квадратов (стр. 119-120). А вот построение просто магических квадратов данной серии порядков методом латинских квадратов я не встречала нигде. Это странно! Почему такой универсальный метод не был рассмотрен применительно к данной серии порядков? Нет этого ни в книге М.М. Постникова, ни в книге Ю.В. Чебракова. Не встречала также в Сети. Может быть, просмотрела?
А ведь здесь всё точно так же основывается на применении пары ортогональных диагональных латинских квадратов. И снова надо знать, как составлять такие пары. Ну, для порядка 4 не составляет никакого труда построить пару ортогональных диагональных латинских квадратов вручную. Вот эта пара.

0 1 2 3
2 3 0 1
3 2 1 0
1 0 3 2

0 1 2 3
3 2 1 0
1 0 3 2
2 3 0 1

Понятно, что это нормализованная пара. Помещая в первой строке любую другу перестановку, мы получим 24 варианта таких пар ортогональных диагональных латинских квадратов.
Магический квадрат, построенный с помощью данной пары латинских квадратов, будет такой:

1 6 11 16
12 15 2 5
14 9 8 3
7 4 13 10

Для порядка 8, конечно, вручную строить пару ортогональных диагональных латинских квадратов уже сложно. Но для данного порядка такие пары строит Мапл. Вот одна из пар ортогональных диагональных латинских квадратов порядка 8.

0 1 2 3 4 5 6 7
2 3 0 1 6 7 4 5
4 5 6 7 0 1 2 3
6 7 4 5 2 3 0 1
5 4 7 6 1 0 3 2
7 6 5 4 3 2 1 0
1 0 3 2 5 4 7 6
3 2 1 0 7 6 5 4

0 1 2 3 4 5 6 7
3 2 1 0 7 6 5 4
6 7 4 5 2 3 0 1
5 4 7 6 1 0 3 2
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
7 6 5 4 3 2 1 0
4 5 6 7 0 1 2 3

Мапл выдаёт 15 пар ортогональных диагональных латинских квадратов. Все они нормализованные. Из каждой такой пары можно получить 40320 вариантов. Следовательно, методом латинских квадратов можно построить 604800 магических квадратов 8-го порядка. А если учесть, что первый и второй вспомогательные латинские квадраты равноправны, то это количество удваивается.
Вот магический квадрат, построенный из приведённой пары ортогональных диагональных латинских квадратов:

1 10 19 28 37 46 55 64
20 27 2 9 56 63 38 45
39 48 53 62 3 12 17 26
54 61 40 47 18 25 4 11
42 33 60 51 14 5 32 23
59 52 41 34 31 24 13 6
16 7 30 21 44 35 58 49
29 22 15 8 57 50 43 36

Вообще-то Мапл выдаёт группу взаимно ортогональных латинских квадратов порядка 8, которая состоит из 7 квадратов. Один их них не является диагональным. Понятно, что из 6 квадратов можно составить 15 пар. Однако остаётся открытым вопрос: является ли такая группа ортогональных квадратов единственной?
А для порядка 12, как я поняла, Мапл не умеет строить ортогональные латинские квадраты. Или я неправильно поняла?
maxal, вы, кажется, писали, что Мапл умеет строить ортогональные латинские квадраты для порядков равных простому числу или степени простого числа. Правильно? Значит, для порядка 12 он не умеет строить такие квадраты. А кто тогда умеет? А для порядка 16 уже умеет. То есть для всех степеней 2 мы сможем построить в Мапле группы ортогональных латинских квадратов. А как быть с теми порядками, которые не являются степенью 2?

[Aleks-Sid]

Nataly-Mak

Правильно ли я Вас понял: нужно найти в общем случае (то есть для всей группы 4k+2) два любых латинских квадрата?
Или же нужно, чтобы еще эти ЛК были обязательно ортогональными?

[Nataly-Mak]

Нужно составить пару таких латинских квадратов, которые не только ортогональные, но ещё и диагональные. В противном случае магический квадрат не построится.
О том, как я поработала Маплом, читайте здесь:
http://www.natalimak1.narod.ru/aspekty.htm

[maxal]

Nataly-Mak в сообщении #165291 писал(а):

Вообще-то Мапл выдаёт группу взаимно ортогональных латинских квадратов порядка 8, которая состоит из 7 квадратов. Один их них не является диагональным. Понятно, что из 6 квадратов можно составить 15 пар. Однако остаётся открытым вопрос: является ли такая группа ортогональных квадратов единственной?

Не является. Считайте, что эта группа выбрана неким случайным образом.

Nataly-Mak в сообщении #165291 писал(а):

maxal, вы, кажется, писали, что Мапл умеет строить ортогональные латинские квадраты для порядков равных простому числу или степени простого числа. Правильно? Значит, для порядка 12 он не умеет строить такие квадраты. А кто тогда умеет?

Поняли правильно, но только он строит не просто ортогональные, а (некоторую) группу попарно ортогональных квадратов. Строить подобные группы для других порядков - сложная задача. Например, построения такых групп из 3 квадратов 14-го порядка и из 4-х 20-го удостоились отдельных статей.
Но у вас, как я понимаю, стоит более простая задача - вам нужны всего лишь пары (а не группы из большего числа) ортогональных квадратов, но зато диагональные. Тут надо в деталях читать статью Брауна и компании...

Nataly-Mak в сообщении #165234 писал(а):

Одним словом: не могли бы вы сказать, не приведён ли в данной статье метод составления диагональных латинских квадратов 10-го порядка с помощью латинского квадрата 5-го порядка?
Далее: что известно о других порядках n=4k+2? Вы писали, что доказано существование пар ортогональных диагональных латинских квадратов для всех порядков, кроме 2, 3, 6. Значит, все пары указанной серии порядков существуют. О них есть какие-то статьи?

Мне сейчас некогда в ней разбираться. Но вообще утверждение о существовании пар ортогональных диагональных латинских квадратов для всех порядков, кроме 2, 3, 6 - это в точности цитата из статьи Брауна и Ко. Значит, либо в ней самой все это доказано, либо недостающую часть доказательства можно найти в цитируемой в этой статье литературе.

[shwedka]

Про латинские квадраты литература огромная, около полутора тысяч статей.
Из последнего, возможно, пригодится
Bell, Jordan; Stevens, Brett Constructing orthogonal pandiagonal Latin squares and panmagic squares from modular $n$-queens solutions. J. Combin. Des. 15 (2007), no. 3, 221--234.
Maenhaut, Barbara; Wanless, Ian M.; Webb, Bridget S. Subsquare-free Latin squares of odd order. European J. Combin. 28 (2007), no. 1, 322--336. --- лень дальше перечислять

А еще целый набор книг


Laywine, Charles F.; Mullen, Gary L. Discrete mathematics using Latin squares. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1998. xviii+305 pp. ISBN: 0-471-24064-8

- есть в электронной форме. Могу выложить.

Dénes, J.; Keedwell, A. D. Latin squares. New developments in the theory and applications. With contributions by G. B. Belyavskaya, A. E. Brouwer, T. Evans, K. Heinrich, C. C. Lindner and D. A. Preece. With a foreword by Paul Erdős. Annals of Discrete Mathematics, 46. North-Holland Publishing Co., Amsterdam, 1991. xiv+454 pp. ISBN: 0-444-88899-3

Belousov, V. D.; Belyavskaya, G. B. {\cyr Latinskie kvadraty, kvazigruppy i ikh prilozheniya}. (Russian) [Latin squares, quasigroups and their applications] ``Shtiintsa'', Kishinev, 1989. 80 pp. ISBN: 5-376-00074-5

{\cyr Kvazigruppy i latinskie kvadraty}. (Russian) [Quasigroups and Latin squares] Edited by I. I. Valutsè and G. B. Belyavskaya. Mat. Issled. No. 71 (1983). ``Shtiintsa'', Kishinev, 1983. pp. 1--140.


Dénes, J.; Keedwell, A. D. Latin squares and their applications. Academic Press, New York-London, 1974. 547 pp.

Vajda, S. The mathematics of experimental design: Incomplete block designs and Latin squares. Griffin's Statistical Monographs & Courses, No. 23 Hafner Publishing Co., New York 1967 viii+110 pp.

[Aleks-Sid]

Nataly-Mak

Цитата:

Для порядка 8, конечно, вручную строить пару ортогональных диагональных латинских квадратов уже сложно.

Ничего подобного!
Теперь я немного освоился с темой. Задача, очевидно, сузилась до группы только 4k+2 , поскольку для всех других четных групп я в последней статье нашел конкретные пути к построению двух латинских квадратов, дающих не просто МК, а даже ИСМК. Вот примеры (терпеть не могу нулей и поэтому записываю каждое число на единицу больше):
n = 8

1 8 1 8 1 8 1 8
6 3 6 3 6 3 6 3
4 5 4 5 4 5 4 5
7 2 7 2 7 2 7 2
7 2 7 2 7 2 7 2
4 5 4 5 4 5 4 5
6 3 6 3 6 3 6 3
1 8 1 8 1 8 1 8

1 6 4 7 7 4 6 1
8 3 5 2 2 5 3 8
1 6 4 7 7 4 6 1
8 3 5 2 2 5 3 8
1 6 4 7 7 4 6 1
8 3 5 2 2 5 3 8
1 6 4 7 7 4 6 1
8 3 5 2 2 5 3 8

n = 12

1 12 1 12 1 12 1 12 1 12 1 12
3 10 3 10 3 10 3 10 3 10 3 10
8  5 8  5 8  5 8  5 8  5 8  5
7  6 7  6 7  6 7  6 7  6 7  6
9  4 9  4 9  4 9  4 9  4 9  4
11 2 11 2 11 2 11 2 11 2 11 2
11 2 11 2 11 2 11 2 11 2 11 2
9  4 9  4 9  4 9  4 9  4 9  4
7  6 7  6 7  6 7  6 7  6 7  6
8  5 8  5 8  5 8  5 8  5 8  5
3 10 3 10 3 10 3 10 3 10 3 10
1 12 1 12 1 12 1 12 1 12 1 12

 1  3  8 7 9 11 11 9 7 8  3  1
12 10  5 6 4  2  2 4 6 5 10 12
 1  3  8 7 9 11 11 9 7 8  3  1
12 10  5 6 4  2  2 4 6 5 10 12
 1  3  8 7 9 11 11 9 7 8  3  1
12 10  5 6 4  2  2 4 6 5 10 12
 1  3  8 7 9 11 11 9 7 8  3  1
12 10  5 6 4  2  2 4 6 5 10 12
 1  3  8 7 9 11 11 9 7 8  3  1
12 10  5 6 4  2  2 4 6 5 10 12
 1  3  8 7 9 11 11 9 7 8  3  1
12 10  5 6 4  2  2 4 6 5 10 12

Для образования любых ЛГ порядков 8k и 8k+4 мне никаких Маплов не требуется, все легко строится с помощью Рис. 13 статьи http://renuar911.narod.ru/ideal_sov.html (хочешь - вручную, хочешь по программке из 5 команд).

Цитата:

maxal, вы, кажется, писали, что Мапл умеет строить ортогональные латинские квадраты для порядков равных простому числу или степени простого числа. Правильно? Значит, для порядка 12 он не умеет строить такие квадраты. А кто тогда умеет?

Ответ самый короткий и скромный в мире: - я.

Думаю, я смогу за 2-3 дня найти общий принцип создания ЛК, описывающих простой МК порядка одинарной четности. Если, конечно, коллеги не возражают и за положительный результат скажут мне "спасибо".

shwedka
А нет ли публикаций о латинских квадратах порядка 4k+2? Может, мне тогда не придется напрягать мозжечок, изобретая веник.

[Nataly-Mak]

Aleks-Sid
Вы забыли, коллега, что речь идёт о КЛАССИЧЕСКИХ ЛАТИНСКИХ КВАДРАТАХ! Надо внимательно читать сообщения. В своём сообщении о ЛК 10-го порядка я это замечание сделала. Вы же тут настроили обобщённых ЛК. Вы хоть знаете разницу между классическими и между обобщёнными ЛК?
Обобщённые ортогональные ЛК я тоже умею строить. Они и в книжки Чебракова есть (см. стр. 119; там строится совершенный магический квадрат 8-го порядка). Так что не изобрели ли вы опять велосипед? Книжка Чебракова вышла в свет в 1995 г. Метод Чебракова для построения совершенных магических квадратов подробно изложен мной в статье
http://www.klassikpoez.narod.ru/latsov.htm
А вот вы мне постройте пару ортогональных диагональных КЛАССИЧЕСКИХ ЛК порядка 12 или порядка 14 или порядка 20.
Такие пары для порядка 16 я вчера построила во время просмотра телефильма. Очень большое удовольствие получила! Теперь знаю, как строить такие квадраты для порядков, которые являются степенью числа 2.
shwedka
Спасибо за литературу.
Ох! Прошу прощения. Не уточнила, что меня интересуют статьи не просто о латинских квадратах, а о построении ортогогальных ЛК и кроме того свеженькие - после 1992 г. Построение пар ортогональных диагональных ЛК для нечётных порядков не вызывает никакого труда. Для чётно-чётных порядков остались трудными для меня порядки, не являющиеся степенью 2, для порядков n=4k+2 сложно всё, кроме найденного уже порядка 10.
maxal
Спасибо за исчерпывающий ответ.

Добавлено спустя 33 минуты 17 секунд:

maxal писал(а):

Строить подобные группы для других порядков - сложная задача. Например, построения такых групп из 3 квадратов 14-го порядка и из 4-х 20-го удостоились отдельных статей.

Так значит, есть уже ортогональные квадраты 14-го и 20-го порядка? А среди них есть диагональные? Очень интересно! Пожалуйста, дайте (если возможно) ссылки на эти статьи. Так хочется на эти квадраты взглянуть.
Всё правильно вы говорите: для моей задачи построения магических квадратов достаточно всего одной пары ортогональных диагональных латинских квадратов (для любого порядка). Но если строится группа (как, например, в случае с Маплом), то ведь из группы взаимно ортогональных латинских квадратов можно выбрать два диагональных.

[maxal]

Nataly-Mak в сообщении #165565 писал(а):

Так значит, есть уже ортогональные квадраты 14-го и 20-го порядка? А среди них есть диагональные? Очень интересно! Пожалуйста, дайте (если возможно) ссылки на эти статьи. Так хочется на эти квадраты взглянуть.

Соответсвующие статьи могу выслать, но там не приводится квадратов в явном виде - вероятно, лишь описывается алгоритм их построения - в детали я пока не вникал.

Nataly-Mak в сообщении #165565 писал(а):

Всё правильно вы говорите: для моей задачи построения магических квадратов достаточно всего одной пары ортогональных диагональных латинских квадратов (для любого порядка). Но если строится группа (как, например, в случае с Маплом), то ведь из группы взаимно ортогональных латинских квадратов можно выбрать два диагональных.

Можно, но только если они там есть - а этого никто не гарантирует. Если повезет, то диагональные латинские квадраты в группе найдутся, но могут и не найтись.