Н.Макарова

 

ПОСТРОЕНИЕ ВЗАИМНО ОРТОГОНАЛЬНЫХ ЛАТИНСКИХ КВАДРАТОВ ИЗ ОРТОГОНАЛЬНОГО МАССИВА

 

Доказано, что существование t взаимно ортогональных латинских квадратов порядка n эквивалентно существованию ортогонального массива ОА(t+2,n) (см., например, книгу М. Холла “Комбинаторика”, М.: Мир, 1970). Под ортогональным массивом ОА(t+2,n) понимается матрица размером (t+2)хn2, состоящая из элементов 0, 1, 2, … n-1, все строки которой взаимно ортогональны.  Взаимная ортогональность строк матрицы определяется следующим образом:

если a = (a1, a2, a3, … an^2), b = (b1, b2, b3, … bn^2) любые две строки матрицы, то каждая пара (x,y) (x, y есть любые элементы из 0, 1, 2, … n-1) встречается ровно один раз среди пар (ai,bi).

 

Чтобы лучше понять определение ортогонального массива, приведу два конкретных примера.

Пример 1. Ортогональный массив ОА(4,3) для двух ортогональных латинских квадратов 3-го порядка (рис. 1).

 

0

0

0

1

1

1

2

2

2

0

1

2

0

1

2

0

1

2

0

1

2

1

2

0

2

0

1

0

1

2

2

0

1

1

2

0

 

Рис. 1

 

Пример 2. Ортогональный массив ОА(5,4) для трёх ортогональных латинских квадратов 4-го порядка (рис. 2).

 

0

0

0

0

1

1

1

1

2

2

2

2

3

3

3

3

0

1

2

3

0

1

2

3

0

1

2

3

0

1

2

3

0

1

2

3

3

2

1

0

1

0

3

2

2

3

0

1

0

1

2

3

2

3

0

1

3

2

1

0

1

0

3

2

0

1

2

3

1

0

3

2

2

3

0

1

3

2

1

0

 

Рис. 2

 

Если известен ортогональный массив, группу взаимно ортогональных латинских квадратов построить очень легко. Покажу это на примере ортогонального массива, изображённого на рис. 2. Первые две строки сверху в ортогональном массиве – это координаты. Теперь берём первый столбец ортогонального массива. Первое число в столбце (считая сверху) – координата x, второе число в столбце – координата y; далее идут числа, записанные в ячейке с такими координатами, в первом, втором и третьем латинском квадрате соответственно. Конкретно из первого столбца имеем: в ячейке с координатами (0,0) во всех трёх латинских квадратах запишется число 0. По последнему столбцу ортогонального массива имеем: в ячейку с координатами (3,3) в первом латинском квадрате запишется число 1, во втором латинском квадрате – число 2, в третьем латинском квадрате – число 0 [система координат (x,y) имеет положительную полуось x, направленную вправо, и положительную полуось y, направленную вниз]. На рис. 3 вы видите группу из трёх взаимно ортогональных латинских квадратов 4-го порядка, построенных по данному ортогональному массиву с рис. 2.

 

0

3

1

2

 

0

2

3

1

 

0

1

2

3

1

2

0

3

1

3

2

0

1

0

3

2

2

1

3

0

2

0

1

3

2

3

0

1

3

0

2

1

3

1

0

2

3

2

1

0

 

Рис. 3

 

Теперь, когда известно, как из ортогонального массива построить сами ортогональные латинские квадраты, мне удалось построить пары ОЛК 14-го и 26-го порядков, используя описанные в указанной выше книге Холла ортогональные массивы. Покажу эти пары ОЛК, очень интересный результат! Сначала подробно опишу построение ортогонального массива по книге Холла (стр. 279).

Для построения ортогонального массива ОА(4,14) берётся следующая матрица P0 (рис. 4):

 

0

x1

x2

x3

1

0

0

0

4

4

6

9

6

1

2

8

 

Рис. 4

 

 Далее строятся матрицы P1, P2, P3 путём циклической перестановки строк в матрице P0. Матрица A0 = (P0,P1,P2,P3). Матрицы Ai (i = 1, 2, …, 10) получаются из матрицы A0 прибавлением i по модулю 11 к каждому числу в A0 (за исключением неизвестных x1, x2, x3). Матрица A = (A0, A1, A2,…,A10). Матрица B есть ОА(4,3) относительно x1, x2, x3. Наконец, матрица E есть матрица размером 4х11, i-ый столбец которой содержит на каждом месте i.

Искомый ортогональный массив ОА(4,14) = (E,A,B).

На этом Холл заканчивает построение ортогонального массива. Я продолжу подробнее. Сначала покажу матрицу Е. Это очень простая матрица (рис. 5):

 

0

1

2

3

4

5

6

7

8

9

10

0

1

2

3

4

5

6

7

8

9

10

0

1

2

3

4

5

6

7

8

9

10

0

1

2

3

4

5

6

7

8

9

10

 

Рис. 5

 

На рис. 6 вы видите ОА(4,3) относительно x1, x2, x3, это матрица В.

 

x1

x1

x1

x2

x2

x2

x3

x3

x3

x1

x2

x3

x1

x2

x3

x1

x2

x3

x1

x2

x3

x2

x3

x1

x3

x1

x2

x1

x3

x2

x2

x1

x3

x3

x2

x1

 

Рис. 6

 

Осталось показать матрицы Ai, из которых образуется матрица А. Не буду показывать все матрицы  Ai, покажу только первые три матрицы (рис. 7–9) и последнюю матрицу (рис. 10). Все остальные матрицы строятся аналогично.

 

Матрица А0

 

0

x1

x2

x3

1

0

0

0

4

4

6

9

6

1

2

8

1

0

0

0

4

4

6

9

6

1

2

8

0

x1

x2

x3

4

4

6

9

6

1

2

8

0

x1

x2

x3

1

0

0

0

6

1

2

8

0

x1

x2

x3

1

0

0

0

4

4

6

9

 

Рис. 7

 

Матрица А1

 

1

x1

x2

x3

2

1

1

1

5

5

7

10

7

2

3

9

2

1

1

1

5

5

7

10

7

2

3

9

1

x1

x2

x3

5

5

7

10

7

2

3

9

1

x1

x2

x3

2

1

1

1

7

2

3

9

1

x1

x2

x3

2

1

1

1

5

5

7

10

 

Рис. 8

 

Матрица А2

 

2

x1

x2

x3

3

2

2

2

6

6

8

0

8

3

4

10

3

2

2

2

6

6

8

0

8

3

4

10

2

x1

x2

x3

6

6

8

0

8

3

4

10

2

x1

x2

x3

3

2

2

2

8

3

4

10

2

x1

x2

x3

3

2

2

2

6

6

8

0

 

Рис. 9

 

Матрица А10

 

10

x1

x2

x3

0

10

10

10

3

3

5

8

5

0

1

7

0

10

10

10

3

3

5

8

5

0

1

7

10

x1

x2

x3

3

3

5

8

5

0

1

7

10

x1

x2

x3

0

10

10

10

5

0

1

7

10

x1

x2

x3

0

10

10

10

3

3

5

8

 

Рис. 10

 

Всё готово для построения ОА(4,14). На рис. 11 вы видите фрагмент этого массива. Понятно, что эта матрица имеет размер 4х196.

 

0

1

2

3

4

5

6

7

8

9

10

0

x1

x2

x3

1

0

0

0

5

0

1

7

x1

x1

x1

x2

x2

x2

x3

x3

x3

0

1

2

3

4

5

6

7

8

9

10

1

0

0

0

4

4

6

9

10

x1

x2

x3

x1

x2

x3

x1

x2

x3

x1

x2

x3

0

1

2

3

4

5

6

7

8

9

10

4

4

6

9

6

1

2

8

0

10

10

10

x1

x2

x3

x2

x3

x1

x3

x1

x2

0

1

2

3

4

5

6

7

8

9

10

6

1

2

8

0

x1

x2

x3

3

3

5

8

x1

x3

x2

x2

x1

x3

x3

x2

x1

 

Рис. 11

 

По готовому ортогональному массиву очень просто построить пару ОЛК 14-го порядка. Как это делается, показано в начале статьи. На рис. 12 показан первый латинский квадрат из этой пары ОЛК, а на рис. 13 – второй латинский квадрат.

 

0

x3

10

x1

x2

7

1

8

2

5

3

4

6

9

4

1

x3

0

x1

x2

8

2

9

3

6

5

7

10

7

5

2

x3

1

x1

x2

9

3

10

4

6

8

0

5

8

6

3

x3

2

x1

x2

10

4

0

7

9

1

1

6

9

7

4

x3

3

x1

x2

0

5

8

10

2

6

2

7

10

8

5

x3

4

x1

x2

1

9

0

3

2

7

3

8

0

9

6

x3

5

x1

x2

10

1

4

x2

3

8

4

9

1

10

7

x3

6

x1

0

2

5

x1

x2

4

9

5

10

2

0

8

x3

7

1

3

6

8

x1

x2

5

10

6

0

3

1

9

x3

2

4

7

x3

9

x1

x2

6

0

7

1

4

2

10

3

5

8

10

0

1

2

3

4

5

6

7

8

9

x1

x2

x3

9

10

0

1

2

3

4

5

6

7

8

x2

x3

x1

3

4

5

6

7

8

9

10

0

1

2

x3

x1

x2

 

Рис. 12

 

0

3

x3

10

9

x2

4

x1

7

6

5

1

2

8

6

1

4

x3

0

10

x2

5

x1

8

7

2

3

9

8

7

2

5

x3

1

0

x2

6

x1

9

3

4

10

10

9

8

3

6

x3

2

1

x2

7

x1

4

5

0

x1

0

10

9

4

7

x3

3

2

x2

8

5

6

1

9

x1

1

0

10

5

8

x3

4

3

x2

6

7

2

x2

10

x1

2

1

0

6

9

x3

5

4

7

8

3

5

x2

0

x1

3

2

1

7

10

x3

6

8

9

4

7

6

x2

1

x1

4

3

2

8

0

x3

9

10

5

x3

8

7

x2

2

x1

5

4

3

9

1

10

0

6

2

x3

9

8

x2

3

x1

6

5

4

10

0

1

7

3

4

5

6

7

8

9

10

0

1

2

x1

x2

x3

4

5

6

7

8

9

10

0

1

2

3

x3

x1

x2

1

2

3

4

5

6

7

8

9

10

0

x2

x3

x1

 

Рис. 13

 

Вам ничего не напоминает это построение? Это же очень похоже на алгоритм построения пары ОЛК 10-го порядка! Посмотрите: тоже есть латинский подквадрат 3-го порядка, есть переменные x1, x2, x3.

Закономерности заполнения квадратов очевидны: заполнение в угловом квадрате 11х11 идёт по диагонали, числа записываются в порядке возрастания, после числа 10 пишется число 0. При достижении краёв квадрата диагональ продолжается с другого края квадрата (как если бы квадрат был свёрнут в трубочку по вертикальной или по горизонтальной оси).

Понятно, что переменные x1, x2, x3 могут принимать значения 11, 12, 13 в любой комбинации. Значит, можно построить 6 подобных пар ОЛК. На рис. 14 – 15 показана одна из этих пар с такими значениями переменных: x1 = 11, x2 = 12, x3 = 13.

 

0

13

10

11

12

7

1

8

2

5

3

4

6

9

4

1

13

0

11

12

8

2

9

3

6

5

7

10

7

5

2

13

1

11

12

9

3

10

4

6

8

0

5

8

6

3

13

2

11

12

10

4

0

7

9

1

1

6

9

7

4

13

3

11

12

0

5

8

10

2

6

2

7

10

8

5

13

4

11

12

1

9

0

3

2

7

3

8

0

9

6

13

5

11

12

10

1

4

12

3

8

4

9

1

10

7

13

6

11

0

2

5

11

12

4

9

5

10

2

0

8

13

7

1

3

6

8

11

12

5

10

6

0

3

1

9

13

2

4

7

13

9

11

12

6

0

7

1

4

2

10

3

5

8

10

0

1

2

3

4

5

6

7

8

9

11

12

13

9

10

0

1

2

3

4

5

6

7

8

12

13

11

3

4

5

6

7

8

9

10

0

1

2

13

11

12

 

Рис. 14

 

0

3

13

10

9

12

4

11

7

6

5

1

2

8

6

1

4

13

0

10

12

5

11

8

7

2

3

9

8

7

2

5

13

1

0

12

6

11

9

3

4

10

10

9

8

3

6

13

2

1

12

7

11

4

5

0

11

0

10

9

4

7

13

3

2

12

8

5

6

1

9

11

1

0

10

5

8

13

4

3

12

6

7

2

12

10

11

2

1

0

6

9

13

5

4

7

8

3

5

12

0

11

3

2

1

7

10

13

6

8

9

4

7

6

12

1

11

4

3

2

8

0

13

9

10

5

13

8

7

12

2

11

5

4

3

9

1

10

0

6

2

13

9

8

12

3

11

6

5

4

10

0

1

7

3

4

5

6

7

8

9

10

0

1

2

11

12

13

4

5

6

7

8

9

10

0

1

2

3

13

11

12

1

2

3

4

5

6

7

8

9

10

0

12

13

11

 

Рис. 15

 

Кроме того, можно варьировать латинские подквадраты 3-го порядка (на рис. 14-15 подквадраты выделены жёлтым цветом). Понятно, что эти подквадраты тоже должны быть ортогональны. Следует отметить, что варьирование латинских подквадратов 3-го порядка даёт существенно новые, неизоморфные пары ОЛК.

 

Итак, пара ОЛК 14-го порядка получена. Очевидно, что латинские квадраты в этой паре не диагональные (и суммы чисел в диагоналях не равны 91), поэтому пара не пригодна для построения магических квадратов. Надо её преобразовать. Первый латинский квадрат преобразовываю с помощью такой трансформации тождественной перестановки чисел:

 

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

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

 

Полученный в результате этого преобразования латинский квадрат изображён на рис. 16.

 

0

2

10

11

12

7

1

8

13

5

3

4

6

9

4

1

2

0

11

12

8

13

9

3

6

5

7

10

7

5

13

2

1

11

12

9

3

10

4

6

8

0

5

8

6

3

2

13

11

12

10

4

0

7

9

1

1

6

9

7

4

2

3

11

12

0

5

8

10

13

6

13

7

10

8

5

2

4

11

12

1

9

0

3

13

7

3

8

0

9

6

2

5

11

12

10

1

4

12

3

8

4

9

1

10

7

2

6

11

0

13

5

11

12

4

9

5

10

13

0

8

2

7

1

3

6

8

11

12

5

10

6

0

3

1

9

2

13

4

7

2

9

11

12

6

0

7

1

4

13

10

3

5

8

10

0

1

13

3

4

5

6

7

8

9

11

12

2

9

10

0

1

13

3

4

5

6

7

8

12

2

11

3

4

5

6

7

8

9

10

0

1

13

2

11

12

 

Рис. 16

 

Преобразовываю второй латинский квадрат с помощью такой трансформации тождественной перестановки чисел:

 

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

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

 

На рис. 17 вы видите преобразованный второй латинский квадрат.

 

0

10

13

2

9

11

4

12

7

6

5

1

3

8

6

1

4

13

0

2

11

5

12

8

7

3

10

9

8

7

3

5

13

1

0

11

6

12

9

10

4

2

2

9

8

10

6

13

3

1

11

7

12

4

5

0

12

0

2

9

4

7

13

10

3

11

8

5

6

1

9

12

1

0

2

5

8

13

4

10

11

6

7

3

11

2

12

3

1

0

6

9

13

5

4

7

8

10

5

11

0

12

10

3

1

7

2

13

6

8

9

4

7

6

11

1

12

4

10

3

8

0

13

9

2

5

13

8

7

11

3

12

5

4

10

9

1

2

0

6

3

13

9

8

11

10

12

6

5

4

2

0

1

7

10

4

5

6

7

8

9

2

0

1

3

12

11

13

4

5

6

7

8

9

2

0

1

3

10

13

12

11

1

3

10

4

5

6

7

8

9

2

0

11

13

12

 

Рис. 17

 

Теперь оба латинских квадрата являются нетрадиционными магическими квадратами с магической константой 91. Из этой пары можно построить два магических квадрата, меняя местами латинские квадраты. На рис. 18 показан один из этих магических квадратов. Это первый магический квадрат 14-го порядка, построенный методом латинских квадратов (из пары ортогональных классических латинских квадратов).

 

1

39

154

157

178

110

19

125

190

77

48

58

88

135

63

16

33

14

155

171

124

188

139

51

92

74

109

150

107

78

186

34

28

156

169

138

49

153

66

95

117

3

73

122

93

53

35

196

158

170

152

64

13

103

132

15

27

85

129

108

61

36

56

165

172

12

79

118

147

184

94

195

100

141

115

76

37

70

159

179

26

133

8

46

194

101

55

116

2

127

91

38

84

160

173

148

23

67

174

54

113

69

137

18

142

106

31

98

161

9

192

75

162

175

68

128

83

145

193

4

121

29

112

24

45

90

126

163

176

82

144

97

6

47

25

136

30

185

57

105

32

140

164

177

96

11

111

21

62

187

143

43

72

120

151

5

20

189

50

65

80

87

99

114

130

167

180

42

131

146

7

22

191

52

59

71

86

102

123

182

41

166

44

60

81

89

104

119

134

149

10

17

183

40

168

181

 

Рис. 18

 

Начальная цепочка в этом магическом квадрате не представляет никакой определённой формы. Но магический квадрат построен! И значит, метод латинских квадратов работает для этого порядка, а также и для всех следующих чётных порядков (для нечётных порядков метод латинских квадратов уже исследован и показан в предыдущих статьях). Всё дело только в умении строить пару ОЛК и если эти латинские квадраты не диагональные, то преобразовывать их так, чтобы получить нужные суммы в диагоналях.

 

Далее в книге Холла приведён пример построения ортогонального массива для пары ОЛК 26-го порядка. Исходная матрица для этого построения показана на рис. 19.

 

0

0

0

0

x1

x2

x3

3

6

2

1

0

0

0

8

20

12

16

20

17

8

12

16

7

2

19

6

21

 

Рис. 19

 

Дальше всё делается совершенно аналогично построению ортогонального массива для латинских квадратов 14-го порядка. Чтобы построить пару ОЛК 26-го порядка, мне оказалось достаточно одной матрицы A0. Показываю эту матрицу на рис. 20.

 

0

0

0

0

x1

x2

x3

3

6

2

1

0

0

0

8

20

12

16

20

17

8

12

16

7

2

19

6

21

3

6

2

1

0

0

0

8

20

12

16

20

17

8

12

16

7

2

19

6

21

0

0

0

0

x1

x2

x3

8

20

12

16

20

17

8

12

16

7

2

19

6

21

0

0

0

0

x1

x2

x3

3

6

2

1

0

0

0

12

16

7

2

19

6

21

0

0

0

0

x1

x2

x3

3

6

2

1

0

0

0

8

20

12

16

20

17

8

 

Рис. 20

 

Ортогональные латинские квадраты сразу даю для конкретных значений переменных: x1 = 23, x2 = 24, x3 = 25. Готовые латинские квадраты из полученной пары ОЛК изображены на рис. 21-22.

 

Первый латинский квадрат 26-го порядка

 

0

23

1

22

7

16

12

2

9

19

25

24

3

18

21

13

6

14

4

11

5

10

15

20

17

8

16

1

23

2

0

8

17

13

3

10

20

25

24

4

19

22

14

7

15

5

12

6

11

21

18

9

12

17

2

23

3

1

9

18

14

4

11

21

25

24

5

20

0

15

8

16

6

13

7

22

19

10

8

13

18

3

23

4

2

10

19

15

5

12

22

25

24

6

21

1

16

9

17

7

14

0

20

11

15

9

14

19

4

23

5

3

11

20

16

6

13

0

25

24

7

22

2

17

10

18

8

1

21

12

9

16

10

15

20

5

23

6

4

12

21

17

7

14

1

25

24

8

0

3

18

11

19

2

22

13

20

10

17

11

16

21

6

23

7

5

13

22

18

8

15

2

25

24

9

1

4

19

12

3

0

14

13

21

11

18

12

17

22

7

23

8

6

14

0

19

9

16

3

25

24

10

2

5

20

4

1

15

21

14

22

12

19

13

18

0

8

23

9

7

15

1

20

10

17

4

25

24

11

3

6

5

2

16

7

22

15

0

13

20

14

19

1

9

23

10

8

16

2

21

11

18

5

25

24

12

4

6

3

17

5

8

0

16

1

14

21

15

20

2

10

23

11

9

17

3

22

12

19

6

25

24

13

7

4

18

14

6

9

1

17

2

15

22

16

21

3

11

23

12

10

18

4

0

13

20

7

25

24

8

5

19

24

15

7

10

2

18

3

16

0

17

22

4

12

23

13

11

19

5

1

14

21

8

25

9

6

20

25

24

16

8

11

3

19

4

17

1

18

0

5

13

23

14

12

20

6

2

15

22

9

10

7

21

10

25

24

17

9

12

4

20

5

18

2

19

1

6

14

23

15

13

21

7

3

16

0

11

8

22

1

11

25

24

18

10

13

5

21

6

19

3

20

2

7

15

23

16

14

22

8

4

17

12

9

0

18

2

12

25

24

19

11

14

6

22

7

20

4

21

3

8

16

23

17

15

0

9

5

13

10

1

6

19

3

13

25

24

20

12

15

7

0

8

21

5

22

4

9

17

23

18

16

1

10

14

11

2

11

7

20

4

14

25

24

21

13

16

8

1

9

22

6

0

5

10

18

23

19

17

2

15

12

3

3

12

8

21

5

15

25

24

22

14

17

9

2

10

0

7

1

6

11

19

23

20

18

16

13

4

19

4

13

9

22

6

16

25

24

0

15

18

10

3

11

1

8

2

7

12

20

23

21

17

14

5

22

20

5

14

10

0

7

17

25

24

1

16

19

11

4

12

2

9

3

8

13

21

23

18

15

6

23

0

21

6

15

11

1

8

18

25

24

2

17

20

12

5

13

3

10

4

9

14

22

19

16

7

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

0

1

2

3

23

24

25

17

18

19

20

21

22

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

24

25

23

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

0

1

25

23

24

 

Рис. 21

 

Второй латинский квадрат 26-го порядка

 

0

4

16

23

13

18

24

12

7

3

2

17

8

11

22

25

20

10

15

14

9

5

1

19

6

21

2

1

5

17

23

14

19

24

13

8

4

3

18

9

12

0

25

21

11

16

15

10

6

20

7

22

7

3

2

6

18

23

15

20

24

14

9

5

4

19

10

13

1

25

22

12

17

16

11

21

8

0

12

8

4

3

7

19

23

16

21

24

15

10

6

5

20

11

14

2

25

0

13

18

17

22

9

1

18

13

9

5

4

8

20

23

17

22

24

16

11

7

6

21

12

15

3

25

1

14

19

0

10

2

20

19

14

10

6

5

9

21

23

18

0

24

17

12

8

7

22

13

16

4

25

2

15

1

11

3

16

21

20

15

11

7

6

10

22

23