Magické čtverce

Úkol: Magické čtverce jsou čtvercové matice čísel, jejichž součty po řádkách se rovnají sobě navzájem a také součtům ve sloupcích, případně též součtům po diagonále.

a)
Uvažujte prostor $ M_1$ reálných matic $ 3\times 3$ takových, že součty v řádkách i sloupcích se rovnají. Určete dimenzi tohoto prostoru a najděte libovolnou bázi.

b)
Prostor $ M_2$ obsahuje matice z $ M_1$ s dodatečnou podmínkou, že i součty po diagonálách se rovnají součtům v řádkách či sloupcích. Určete dimenzi $ M_2$ a nalezněte vhodnou bázi.

c)
Nalezněte pravý magický čtverec $ 3\times 3$, v němž se každé číslo z množiny $ 1,\dots,9$ vyskytuje právě jednou. Ukažte, že rotacemi a zrcadleními lze získat více magických čtverců, než je dimenze $ M_2$ z minulého bodu. Vysvětlete tento fakt. Pokud Vaše odpověď bude obsahovat spojení ,,lineární kombinace'', zvolte za bázi $ \dim(M_2)-1$ pravých magických čtverců a matici se samými pětkami a zapište všechny ostatní pravé magické čtverce jako lineární kombinaci prvků této báze.

d)
Pokud přejdeme od čtverců $ 3\times 3$ ke čtvercům $ 4\times 4$ nebo obecněji $ n\times n$ (a požadujeme stále to, co v bodech a,b), jaká bude dimenze?


Řešení:


a) V prvním úkolu označme nejdříve součet v libovolné řádce nebo sloupci $ s$. Pišme do první řádky $ a,b$ a poslední položka řádky pak musí být $ s-a-b$. Do druhé řádky pišme $ d,e$ a poslední položka je nutně $ s-d-e$. Třetí řádka je pak také jednoznačně určena a obecný prvek $ M_1$ má tvar

$\displaystyle {M}=\tb{ccc}a&b&s-a-b\\ d&e&s-d-e\\ s-a-d&s-b-e&
 a+b+d+e-s..$ (22)

Lehce zkontrolujeme, že pro libovolnou volbu pěti čísel $ a,b,d,e,s$ splňuje $ {M}$ podmínky $ M_1$. Zároveň jsme zapsali nejobecnější řešení, protože ke každému vyjádření nových položek pomocí starých jsme byli přinuceni. Tudíž dimenze $ M_1$ je rovna pěti. Za bázi lze zvolit například pět matic, které dostaneme dosazením jednotky za jednu proměnnou a nul za ostatní proměnné z množiny $ \{a,b,d,e,s\}$, tedy

$\displaystyle A_1=\left(\begin{array}{ccccccccccccc} 1&\phantom{-}0&-1\cr 0&0&0...
...}{ccccccccccccc} 0& 0& 0\cr 1&\phantom{-} 0&-1\cr -1& 0& 1\end{array}\right),
$

$\displaystyle A_4=\left(\begin{array}{ccccccccccccc} 0& 0& 0\cr 0& 1&-1\cr 0&-1...
...}{ccccccccccccc} 0& 0& 1\cr 0&\phantom{-}0& 1\cr 1& 1&-1\end{array}\right)\,.
$

Dodejme na závěr, že se v pravděpodobnostních úlohách vyskytují takzvané bistochastické matice, což jsou čtvercové matice (například $ 3\times 3$), které mají součty prvků v každém řádku i sloupci rovné jedné. Všechny takové matice tvoří čtyřdimenzionální afinní prostor, neboli je lze zapsat ve tvaru

$\displaystyle B=A_5+\alpha_1A_1+\alpha_2A_2+\alpha_3A_3+\alpha_4A_4\df=A_5+L\,.
$

Afinní prostor v prostoru $ V$ je tedy ,,vektorový podprostor $ U\subset V$ plus jeden prvek $ \vec{v}\in V$''; v našem případě tvoří matice $ A_1,A_2,A_3,A_4$ bázi $ U$ a matice $ A_5$ je prvek $ \vec{v}$$ V$. Pokud $ \vec{v}\notin U$ (jako v našem případě), pak tento afinní prostor není vektorovým podprostorem $ V$. Názorně (v  {\bb R}$ ^n$) si jej lze představit jako ,,posunutý vektorový podprostor''.


b) V dalším úkolu, v prostoru $ M_2$, požadujeme ještě navíc

$\displaystyle \nonumber a+e+a+b+d+e-s=s,\qquad
s-a-d+e+s-a-b=s,$

což jsou dvě nezávislé rovnice, z nichž lze například vyjádřit $ d,e$. Obecná matice je pak určena třemi nezávislými čísly $ a,b,s$, dimenze $ M_2$ je tedy rovna třem. Bázi lze zvolit podobně jako v minulém bodě. Pro $ (a,b,s)$ rovno postupně $ (1,0,0)$, $ (0,1,0)$ a $ (0,0,1)$ vyjde

$\displaystyle B_1=\left(\begin{array}{ccccccccccccc} 1&\;0&-1\cr-2& 0& 2\cr 1& ...
...{2}{3}\cr
-\frac{1}{3}& \frac{2}{3}&\frac{2}{3}\end{array}\right)\hskip-1pt.
$


c) Když v pravém magickém čtverci zapíšeme čísla $ 1,\dots,9$, součet všech čísel bude $ 9\cdot (1+9)/2=45$, jinak řečeno součet v každé řádce musí být roven $ 15$. Průměrné číslo v každé řádce nebo sloupci či diagonále pak musí být $ 5$ a můžeme ukázat, že i uprostřed musí být číslo $ 5$. Například tak, že dvakrát součet součtů po obou diagonálách plus součet prostřední řady a součet prostředního sloupce (celkem $ 6\cdot 15=90$) je roven součtu součtů na čtyřech hranách ( $ 4\cdot 15=60$) plus šestkrát prostřední číslo ( $ 6\cdot p=30$).

Na protějších stranách od čísla $ 5$ musíme napsat páry čísel, jejichž součet je roven $ 10$. Jde jen o to, kam napíšeme $ 1-9$, $ 2-8$ atd. Začneme třeba s jednotkou uprostřed nějaké hrany. Intuice nás potom vede k tomu, že dvojku napíšeme co možná nejdále od jednotky a zbytek magického čtverce je již určen jednoznačně (viz první matice níže v rovnici (23); pokud bychom dvojku umístili do některé ze dvou zbývajících poloh, čtverec bychom nedokončili -- zkuste si). Každý takový magický čtverec lze otočit do 4 různých světových stran a od každého otočení lze pořídit zrcadlovou kopii, celkem máme 8 tvarů magických čtverců. Výše jsme ale ukázali, že dimenze prostoru všech magických čtverců je rovna třem. Důvod je v tom, že každý prvek $ M_2$ (např. každý otočený magický čtverec) lze psát jako lineární kombinaci základních čtverců (z $ M_2$)

$\displaystyle {M}'=
 A\tb{ccc}8&1&6\\ 3&5&7\\ 4&9&2.+
 B\tb{ccc}6&1&8\\ 7&5&3\\ 2&9&4.+
 C\tb{ccc}5&5&5\\ 5&5&5\\ 5&5&5..$ (23)

Všech 8 otočení a zrcadlení pravého magického čtverce získáme z (23) volbou (první dva čtverce jsou přímo z (23) a další dva jsou jejich středově souměrné obrazy)

$\displaystyle \nonumber \begin{array}{rcll}
(A,B,C)&=&(1,0,0), (0,1,0),&
(-1,...
...,\frac12), &
(-\frac54,\frac34,\frac32), (\frac34,-\frac54,\frac32)\end{array}$

Všimněte si, že $ A+B+C=1$ ve všech případech, což je nutné k zachování součtu 45 všech čísel. Nezapomeňte také, že pravé magické čtverce netvroří vektorový prostor (zkuste schválně dva pravé magické čtverce sečíst).


d) Prostor obecných matic $ n\times n$ má dimenzi $ n^2$, ovšem máme $ 2n-2$ podmínek14 definujících $ M_1$ a další $ 2$ podmínky definující $ M_2$, celková dimenze $ M_2$ je tedy $ n^2-2n=n(n-2)$. Pro větší čtverce tedy očekáváme, že bude existovat více magických čtverců a podmínky nebude těžké splnit.

$ \ast$LM$ \ast$