Zápisky z Algebry a analýzy v aplikacích

$p$ -adická čísla

Mějme metrický prostor $(ℚ, d)$ s metrikou $d (x, y) ≔ | x - y |$ . Tento metrický prostor není úplný – například posloupnost ${(1 + \frac{1}{n})}^{n}$ je cauchyovská, ale nemá limitu. Můžeme tedy říct, že reálná čísla jsou jeho zúplněním. Pojďme zobecnit tento pojem a následně ho vyzkoušet s trochu jinou metrikou.

Definice. Metrický prostor

(M^{*}, d^{*})

je zúplnění metrického prostoru

(M, d)

, pokud je úplný a existuje izometrie

ℐ : M \to M^{*}

taková, že

ℐ (M)

je hustá v

M^{*}

. To jest:

(\forall x, y \in M) (d (x, y) = d^{*} (ℐ (x), ℐ (y)))

(\forall x \in M^{*}) (\forall B_{x}) (B_{x} \cap M \neq ⌀)

Definice. Nechť

p \in ℙ, r \in ℚ

. Nechť

r ≕ p^{k} \cdot \frac{a}{b}

, kde

a, b, k \in ℤ, a ⟂ p, b ⟂ p

. Potom definujeme

p

-adickou absolutní hodnotu

r

jako

{| r |}_{p} ≔ p^{- k}

. Speciálně definujeme

{| 0 |}_{p} ≔ 0

Příklad.

{| 360 |}_{2} = {| 2^{3} \cdot 45 |}_{2} = \frac{1}{8}

Příklad.

{| \frac{360}{7} |}_{2} = {| 2^{3} \cdot \frac{45}{7} |}_{2} = \frac{1}{8}

Příklad.

{| \frac{360}{7} |}_{7} = {| 7^{- 1} \cdot 360 |}_{7} = 7

Příklad.

{| \frac{360}{7} |}_{11} = 1

Věta.

{| \cdot |}_{p}

splňuje axiomy absolutní hodnoty:

${| 0 |}_{p} = 0$
$(\forall r \in ℚ, r \neq 0) ({| r |}_{p} > 0)$
$(\forall r, q \in ℚ) ({| r \cdot q |}_{p} = {| r |}_{p} \cdot {| q |}_{p})$
$(\forall r, q \in ℚ) ({| r + q |}_{p} \leq {| r |}_{p} + {| q |}_{p})$

Věta.

{| \cdot |}_{p}

je nearchimédovská:

(\forall r, q \in ℚ) ({| r + q |}_{p} \leq \max {{| r |}_{p}, {| q |}_{p}})

Navíc je-li

{| r |}_{p} \neq {| q |}_{p}

, potom jde o rovnost.

Definice.

p

-adická metrika je definována jako

d_{p} (x, y) ≔ {| x - y |}_{p}

Poznámka. Díky nearchimédovskosti jde o ultrametriku, tedy platí silnější verze trojúhelníkové nerovnosti:

d_{p} (x, y) \leq \max {d_{p} (x, z), d_{p} (y, z)}

Věta. Nechť

r, q, s \in ℚ

. Potom alespoň dvě z hodnot

{| r - q |}_{p}, {| q - s |}_{p}, {| s - r |}_{p}

jsou stejné. Tedy „každý trojúhelník je rovnoramenný“.

Důkaz. Tento důkaz byl schován, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a důkaz vás zajímá, kontaktujte mě.

Věta. Je-li

r \in ℤ

, potom

{| r |}_{p} \leq 1

Důkaz. Tento důkaz byl schován, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a důkaz vás zajímá, kontaktujte mě.

Věta. Nechť

r, q \in ℚ, R \in ℝ^{+}

. Potom

q \in B_{r} (R) ⟹ B_{q} (R) = B_{r} (R)

. Tedy každý bod v kouli je její střed.

Důkaz. Tento důkaz byl schován, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a důkaz vás zajímá, kontaktujte mě.

Definice. Posloupnost

(a_{n}) \in ℚ^{ω}

p

-cauchyovská, pokud je cauchyovská v

p

-adické metrice.

Věta. Posloupnost

(a_{n}) \in ℚ^{ω}

je cauchyovská právě tehdy, pokud

(\forall ε \in ℝ^{+}) (\exists n_{0} \in ℕ) (\forall n \in ℕ, n \geq n_{0}) ({| a_{n + 1} - a_{n} |}_{p} < ε)

Důkaz.

(\Rightarrow)

Triviální.

(\Leftarrow)

Stačí opakovaně aplikovat nearchimedovskou vlastnost.

Poznámka. S normální absolutní hodnotou tato věta neplatí, protipříkladem jsou částečné součty harmonické řady.

Věta. Metrický prostor

(ℚ, d_{p})

není úplný pro

p > 3

Důkaz. Uvažujme posloupnost

a_{n} ≔ 2^{p^{n}}

. Dokážeme, že tato posloupnost je cauchyovská, ale nemá limitu. K důkazu cauchyovskosti využijeme předchozí větu. Dokážeme, že pro libovolné

n

p^{n} | (a_{n} - a_{n - 1})

, tedy

{| a_{n} - a_{n - 1} |}_{p} \leq p^{- n}

. Důkaz provedeme indukcí. Základní případ plyne z malé Fermatovy věty. Indukční krok:

a_{n + 1} - a_{n} = a_{n}^{p} - a_{n - 1}^{p} = (a_{n} - a_{n - 1}) \sum_{k = 0}^{p - 1} a_{n}^{k} \cdot a_{n - 1}^{p - 1 - k}

Levý činitel je podle indukčního předpokladu dělitelný

p^{n}

. Pravý činitel je dělitelný

p

, což se dá dokázat kongruentními úpravami a použitím umocněné malé Fermatovy věty. Nyní dokážeme, že posloupnost nemá limitu. Kdyby

\lim_{n \to \infty} a_{n} = a

, potom

a^{p} \lim_{n \to \infty} a_{n}^{p} = \lim_{n \to \infty} a_{n + 1} = a

, tedy

a \in {0, \pm 1}

. Pro dostatečně velké

n

ale máme

{| a - 2 |}_{p} \leq \max {{| a - a_{n} |}_{p}, {| a_{n} - 2 |}_{p}} \leq \frac{1}{p} < 1

což žádná z hodnot

{0, \pm 1}

nesplňuje.

Věta. Je-li posloupnost

p

-cauchyovská, potom je

p

-omezená.

Důkaz. Zvolme v definici cauchyovosti

ε ≔ 1

. Tím dostaneme takové

n_{0}

, že pro všechna

n \in ℕ, n \geq n_{0}

d_{p} (n_{0}, n) < 1

. Nechť

K ≔ \max {1, {| a_{1} |}_{p}, {| a_{2} |}_{p}, \dots, {| a_{n_{0}} |}_{p}}

. Potom zjevně pro všechna

n \in ℕ

{| a_{n} |}_{p} \leq K

Věta. Množina všech

p

-cauchyovských posloupností je uzavřená na sčítání a násobení.

Důkaz. Pro sčítání je důkaz triviální. Pro násobení použijeme nearchimedovskou vlastnost:

{| a_{n + 1} b_{n + 1} - a_{n} b_{n} |}_{p} = \max {{| a_{n + 1} |}_{p} {| b_{n + 1} - b_{n} |}_{p}, {| b_{n} |}_{p} {| a_{n + 1} - a_{n} |}_{p}}

Věta. Množina

p

-cauchyovských posloupností splňuje všechny axiomy tělesa kromě inverze na násobení.

Důkaz. Triviální. Neutrální prvek na sčítání je nulová posloupnost, neutrální prvek na násobení je jedničková posloupnost, protipříkladem k inverzi je libovolná posloupnost obsahující nulu.

Definice.

ℚ_{p}

je množina tříd ekvivalence na množině

p

-cauchyovských posloupností, kde

(a_{n}) \sim (b_{n})

, pokud

\lim_{n \to \infty} {| a_{n} - b_{n} |}_{p} = 0

Definice. Nechť

[(a_{n})], [(b_{n})] \in ℚ_{p}

. Definujeme sčítání a násobení jako

[(a_{n})] + [(b_{n})] ≔ [(a_{n}) + (b_{n})]

[(a_{n})] \cdot [(b_{n})] ≔ [(a_{n}) \cdot (b_{n})]

Důkaz (korektnosti). Je nutné ověřit, že výsledek nezávisí na volbě reprezentantů. Nechť

(a_{n}) \sim (c_{n}), (b_{n}) \sim (d_{n})

. Chceme dokázat, že

(a_{n}) + (b_{n}) \sim (c_{n}) + (d_{n})

. K tomu lze použít nearchimédovskou vlastnost. Podobně pro násobení.

Věta. V

ℚ_{p}

má každý nenulový prvek inverzi, tedy jde o těleso.

Důkaz. Tento důkaz byl schován, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a důkaz vás zajímá, kontaktujte mě.

Definice. Pro všechna

a \in ℚ_{p}

definujeme

{‖ a ‖}_{p} ≔ \lim_{n \to \infty} {| a_{n} |}_{p}

. (Z předchozí věty víme, že tato limita existuje.)

Věta.

{‖ \cdot ‖}_{p}

je ultranorma.

Důkaz. Jednoduchý.

Věta.

ℚ_{p}

je zúplnění metrického prostoru

ℚ

Důkaz.

Izometrie: Triviální.
Hustota: Nechť $a \in ℚ_{p}, ε \in ℝ^{+}$ . Chceme najít takové $q \in ℚ$ , že ${‖ a - ℐ (q) ‖}_{p} < ε$ . To snadno najdeme použitím cauchyovskosti $a_{n}$ .
Úplnost: Nechť $(A_{N})$ je $p$ -cauchyovská posloupnost prvků $ℚ_{p}$ . Tedy $(\forall ε \in ℝ^{+}) (\exists N_{0} \in ℕ) (\forall M, N \in ℕ, M, N \geq N_{0}) ({‖ A_{N} - A_{M} ‖}_{p} < ε)$ Z hustoty plyne, že existuje taková posloupnost $Q_{N}$ , že $‖ A_{N} - Q_{N} ‖ < \frac{1}{N}$ . Dokážeme, že tato posloupnost je také $p$ -cauchyovská. $‖ Q_{N} - Q_{M} ‖ \leq \max {{‖ Q_{N} - A_{N} ‖}_{p}, {‖ A_{N} - A_{M} ‖}_{p}, {‖ A_{M} - Q_{M} ‖}_{p}} < ε$ Zřejmě lze definovat $Q_{N} ≕ [(q_{N})]$ . Nechť $Q ≔ (q_{1}, q_{2}, \dots)$ . Snadno dokážeme, že $\lim_{N \to \infty} Q_{N} = Q$ . Dokážeme, že také $\lim_{N \to \infty} A_{N} = Q$ . ${‖ A_{N} - Q ‖}_{p} \leq \max {{‖ A_{N} - Q_{N} ‖}_{p}, {‖ Q_{N} - Q ‖}_{P}} < ε$

Definice. Triviální absolutní hodnota racionálního čísla

x

je definována jako

{| x |}_{triv} ≔ [x \neq 0]

Poznámka. Odpovídající metrický prostor je diskrétní, tedy úplný.

Věta (Ostrowski). Všechny netriviální absolutní hodnoty v

ℚ

jsou ekvivalentní buď normální, nebo nějaké

p

-adické absolutní hodnotě. (Tedy pro každou absolutní hodnotu

{| \cdot |}^{*}

(\exists c \in ℝ^{+}) (\forall x \in ℚ) ({| x |}^{*} = {| x |}^{c}) \lor (\exists p \in ℙ, c \in ℝ^{+}) (\forall x \in ℚ) ({| x |}^{*} = {| x |}_{p}^{c})

Věta.

ℚ_{p}

stejně jako

ℝ

není algebraicky úplný prostor, tedy neplatí, že každý polynom má kořen. Můžeme ho podobně jako reálná čísla „zkomplexnit“, ale na rozdíl od komplexních čísel tím nevznikne topologicky úplný prostor, takže ho musíme opět zúplnit.

Příklad. V

p

-adickém prostoru polynom

x^{2} - p

nemá kořen.

Důkaz. Tento důkaz byl schován, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a důkaz vás zajímá, kontaktujte mě.

Věta (Monsky 1970). Je-li

n

liché číslo, potom není možné rozdělit čtverec na

n

trojúhelníků stejného obsahu.

Důkaz. Dokážeme pouze pro trojúhelníky s racionálními vrcholy, kde čtverec je jednotkový. Obarvíme body roviny

(x, y)

následujícím způsobem:

Je-li ${| x |}_{2} < 1 \land {| y |}_{2} < 1$ , bod je červený
Je-li ${| x |}_{2} \geq {| y |}_{2} \land {| x |}_{2} \geq 1$ , bod je modrý
Je-li ${| x |}_{2} < {| y |}_{2} \land {| y |}_{2} \geq 1$ , bod je zelený

Vrcholy čtverce jsou obarvené takto:

Dokážeme, že je-li

S

obsah trojúhelníku s různobarevnými vrcholy, platí

{| S |}_{2} \geq 2

S = | \frac{1}{2} \det (\begin{array}{ccc} 1 & 1 & 1 \\ x_{\overset{ˇ}{c}} & x_{z} & x_{m} \\ y_{\overset{ˇ}{c}} & y_{z} & y_{m} \end{array}) | = | \frac{x_{z} y_{m} + x_{m} y_{\overset{ˇ}{c}} + x_{\overset{ˇ}{c}} y_{z} - x_{z} y_{\overset{ˇ}{c}} - x_{m} y_{z} - x_{\overset{ˇ}{c}} y_{b}}{2} |

{| S |}_{2} = {| \frac{1}{2} |}_{2} \max {{| x_{m} |}_{2} \cdot {| y_{z} |}_{2}, \dots} = 2 \cdot {| x_{m} |}_{2} \cdot {| y_{z} |}_{2} \geq 2

Z toho speciálně plyne, že na přímce nemohou být body tří barev. Mějme nyní nějaké rozdělení čtverce na trojúhelníky. Spočtěme pro každý trojúhelník, kolik má stran s různobarevnými konci, a sečtěme tato čísla. Úvahou zjistíme, že vyjde liché číslo. Z toho plyne, že alespoň jeden trojúhelník v libovolném rozdělení má různobarevné vrcholy. Ovšem je-li

n

liché, potom

{| \frac{1}{n} |}_{2} = 1

, tedy trojúhelníky v rozdělení nemohou mít stejný obsah.

Aritmetika v $p$ -adických číslech

Definice.

p

-adická celá čísla jsou množina

ℤ_{p} ≔ {x \in ℚ_{p} | {‖ x ‖}_{p} \leq 1}

Poznámka. Zřejmě

ℤ \subset ℤ_{p}

Věta.

p

-adická celá čísla tvoří okruh.

Důkaz. Jelikož jde o podmnožinu tělesa, stačí dokázat, že je uzavřená na sčítání, násobení a negaci. Nechť

x, y \in ℤ_{p}

, potom

{‖ x + y ‖}_{p} \leq \max {{‖ x ‖}_{p}, {‖ y ‖}_{p}} \leq 1

{‖ x \cdot y ‖}_{p} = {‖ x ‖}_{p} \cdot {‖ y ‖}_{p} \leq 1

Lemma.

(\forall x \in ℤ_{p}) (\exists (B_{n}) \in ℤ^{ω}) (x = [(b_{n})])

Důkaz. Nechť

x ≕ [(a_{n})]

. Máme

1 \geq {‖ x ‖}_{p} = \lim_{n \to \infty} {| a_{n} |}_{p} ∴ (\exists n_{0}) (\forall n \geq n_{0}) ({| a_{n} |}_{p} \leq 1)

Nechť

a_{n} ≕ \frac{a}{b}, a ⟂ b

. Jelikož

{| a_{n} |}_{p} \leq 1

, máme

b ⟂ p

, tedy

b ⟂ p^{n}

. Podle Bézoutovy věty existují taková

b^{'}, p^{'}

, že

b^{'} \cdot b + p^{'} \cdot p^{n} = 1

. Zvolme

b_{n} ≔ a \cdot b

. Dokážeme, že také reprezentuje

x

{| a_{n} - b_{n} |}_{p} = {| \frac{a}{b} - a \cdot b^{'} |}_{p} = {| \frac{a}{b} |}_{p} {| 1 - b \cdot b^{'} |}_{p} \leq \frac{1}{p^{n}} \to 0

Věta ( $p$ -adický zápis čísla).

(\forall x \in ℤ_{p}) (\exists_{1} (α_{k}) \in ℤ_{p}^{ω}, (s_{n}) \in ℕ_{0}^{ω}, x = [(s_{n})]) (\forall n \in ℕ) (0 \leq s_{n} < p^{n + 1} \land s_{n} = \sum_{k = 0}^{n} α_{k} p^{k})

Důkaz. Nechť

x ≕ [(b_{n})], b_{n} \in ℤ

(to můžeme podle předchozího lemmatu). Z ní vezměme podposloupnost

(c_{n})

splňující

{| c_{n + 1} - x_{n} |}_{p} \leq \frac{1}{p^{n + 1}}

. Definujme

s_{n} ≔ c_{n} mod p^{n + 1}

{| s_{n + 1} - s_{n} |}_{p} \leq \dots \leq \frac{1}{p^{n + 1}}

Kdyby existovala nějaká jiná taková posloupnost

t_{n}

, od nějakého

n

-tého členu by se lišily a dá se ukázat, že by potom pro všechna

m \geq n

bylo

{| s_{m} - t_{m} |}_{p} = \frac{1}{p^{n}}

, tedy nemohly by reprezentovat stejné číslo.

$p$ -adický zápis můžeme rozšířit na celé $ℚ_{p}$ , jelikož každé číslo po vynásobení nějakou mocninou $p$ bude $p$ -adicky celé. To celkově znamená, že každé číslo se dá zapsat pozičním zápisem o základu $p$ , kde před tečkou může být nekonečně mnoho číslic a za tečkou je konečně mnoho číslic.

Příklad.

17 = 122_{3}

Příklad.

\frac{17}{9} = {1.22}_{3}

Příklad.

- 1 = \dots 222222_{3}

Důkaz.

S_{n} = \sum_{k = 0}^{n} 2 \cdot 3^{k}

{| S_{n} - (- 1) |}_{3} = {| 2^{n + 1} |}_{3} = 2^{- n - 1} \to 0

nebo jednodušeji

\dots 222222_{3} + 1_{3} = \dots 000000_{3}

Příklad.

- 2 = \dots 222221_{3}

Důkaz.

2 \cdot \dots 222222_{3} = \dots 222221_{3}

nebo

\dots 222222_{3} + \dots 222222_{2} = \dots 222221_{3}

Příklad.

- \frac{1}{5} = \dots 0121012101210121_{3}

Důkaz.

5 ⟂ 3 ∴ 3^{φ (5)} = 3^{4} \equiv 1 (m o d 5)

\frac{3^{4} - 1}{5} = 16 = 121_{3}

\frac{3^{8} - 1}{5} = (3^{4} + 1) \frac{3^{4} - 1}{5} = 1210121_{3}

⋮

Příklad.

\frac{1}{5} = \dots 2101210121012102_{3}

Důkaz.

\dots 0121012101210121_{3} + \dots 2101210121012102_{3} = \dots 0000000000000000_{3}

Cvičení. Najděte

2

-adické zápisy čísel

- 1, 53, - 53, - \frac{1}{3}, - \frac{2}{3}, \frac{1}{3}, \frac{2}{3}

Řešení. Toto řešení bylo schováno, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a řešení vás zajímá, kontaktujte mě.

Věta.

(\forall r \in ℚ) (| r | \cdot \prod_{p \in ℙ} {| r |}_{p} = 1)

Příklad. V

ℚ_{7}

existuje

\sqrt{2}

Důkaz.

S_{n}^{2} = {(\sum_{k = 0}^{n} α_{k} 7^{k})}^{2} = \sum_{k = 0}^{n} (\sum_{j = 0}^{k} α_{j} α_{k - j}) 7^{k}

Chceme tedy

α_{0}^{2} = 2, α_{0} \cdot α_{1} + α_{1} \cdot α_{0} = 0, α_{0} \cdot α_{2} + α_{1} \cdot α_{1} + α_{2} \cdot α_{0} = 0, \dots

Tím dostáváme nějakou soustavu kongruencí, kterou dokážeme vyřešit.

Příklad. V

ℚ_{5}

neexistuje

\sqrt{2}

Důkaz. Pokud se pokusíme udělat to samé, nepodaří se nám to, protože

2

naní kvadratický zbytek modulo

5

Věta. Nechť

p \in ℙ, k \in ℤ_{p}

. V

ℚ_{p}

existuje

\sqrt{k}

právě tehdy, pokud

k

je kvadratický zbytek modulo

p

Důkaz. Zobecnění předchozích dvou příkladů.

Cvičení. Ukažte, že existuje takové

x \in ℚ_{5}

, že

x^{2} = - 1

. Najděte posledních deset číslic.

Řešení. Toto řešení bylo schováno, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a řešení vás zajímá, kontaktujte mě.

Midyho věta

\frac{1}{7} = 0.142857142857 \dots

142 + 857 = 999

Lemma. Nechť

n \in ℕ, n ⟂ 10

. Potom

\frac{1}{n}

má čistě periodický desítkový zápis s periodou

φ (n)

Důkaz. Podle Eulerovy-Fermatovy věty máme

10^{φ (n)} \equiv 1 (m o d n)

10^{φ (n)} - 1 = a n

\frac{1}{n} = \frac{a}{10^{φ (n)} - 1}

Věta (Midy, 1836). Nechť

p \in ℙ, p \geq 7

a desítkový rozvoj

\frac{1}{p}

má periodu délky

2 m

rovnou

x y

, kde

x, y

jsou délky

m

. Potom

x + y = 10^{m} - 1

Důkaz. Zřejmě je

0 < x + y < 2 (10^{m} - 1)

. Z desítkového rozvoje máme

\frac{10^{2 m}}{p} = x \cdot 10^{m} + y + \frac{1}{p} ∴ \frac{10^{2 m} - 1}{p} = x \cdot 10^{m} + y

Na pravé straně je celé číslo, takže musí být i na levé. Z toho plyne

p | (10^{2 m} - 1) ∴ p | (10^{m} - 1) \lor p | (10^{m} + 1)

První případ nemůže nastat, protože potom by bylo

10^{m} \equiv 1 (m o d p)

, což je spor s minimalitou

m

. Máme tedy

ℕ ∋ \frac{10^{m} + 1}{p} = \frac{x \cdot 10^{m} + y}{10^{m} - 1}

x \cdot 10^{m} + y \equiv 0 (m o d 10^{m} - 1)

x + y \equiv 0 (m o d 10^{m} - 1)

Z nerovnosti poté plyne, že musí být

x + y = 10^{m} - 1

Všimněme si, že také $14 + 28 + 57 = 99$ .

Věta (Ginsberg). Nechť

p \in ℙ, p \geq 7

a desítkový rozvoj

\frac{1}{p}

má periodu délky

3 m

rovnou

x y z

, kde

x, y, z

jsou délky

m

. Potom

x + y + z = 10^{m} - 1

Důkaz. Analogicky jako v předchozím důkazu:

0 < x + y + z < 3 (10^{m} - 1)

\frac{10^{3 m} - 1}{p} = x \cdot 10^{2 m} + y \cdot 10^{m} + z

p | (10^{2 m} + 10^{m} + 1)

ℕ ∋ \frac{10^{2 m} + 10^{m} + 1}{p} = \frac{x \cdot 10^{2 m} + y \cdot 10^{m} + z}{10^{m} - 1}

x \cdot 10^{2 m} + y \cdot 10^{m} + z \equiv 0 (m o d 10^{m} - 1)

x + y + z \equiv 0 (m o d 10^{m} - 1)

Tentokrát již však samotná nerovnost k dokončení důkazu nestačí, protože by také mohlo být

x + y + z = 2 (10^{m} - 1)

. Dokážeme, že platí

x + y + z \equiv - 1 (m o d 10)

U toho se samozřejmě stačí koukat na poslední číslice, tedy chceme dokázat

x_{m} + y_{m} + z_{m} \equiv - 1 (m o d 10)

Z algoritmu pro dělení máme

\frac{10^{n}}{p} = a_{1} \dots a_{n} + \frac{r_{n}}{p}

10^{m} = p \cdot a_{1} \dots a_{n} + r_{n}

???????????????????????

r_{3 m} = 1

r_{m} + r_{2 m} + r_{3 m} \equiv 0 (m o d p) \land r_{m} + r_{2 m} + r_{3 m} \leq 2 p - 1 ∴ r_{m} + r_{2 m} + r_{3 m} = p

x_{m} + y_{m} + z_{m} = a_{m} + a_{2 m} + a_{3 m} \equiv - 1 (m o d 10)

Tedy

x + y + z

je liché číslo, tudíž to nemůže být

2 (10^{m} - 1)

a musí to být

10^{m} - 1

Obecně můžeme odvodit, že pro periodu délky $k m$ máme $\sum_{i = 1}^{k} x_{i} \equiv 0 (m o d 10^{m} - 1)$ . Ovšem už obecně neplatí, že by to byl jednonásobek. Například $1 + 4 + 2 + 8 + 5 + 7 = 27 = 3 \cdot 9 \neq 9$ .

Věta. Nechť

n \in ℕ, n ⟂ 10

. Rozdělme periodu desítkového zápisu

\frac{1}{n}

k

stejně dlouhých bloků

x_{k - 1}, \dots, x_{0}

délky

m

, kde

k \geq 2

. Nechť prvočíselný rozklad

n

\prod_{i = 1}^{r} p_{i}^{γ_{i}}

. Nechť

(\forall j) (m_{j} ∤ m)

, kde

m_{j}

je perioda desítkového zápisu

\frac{1}{p_{j}}

. Potom součet bloků je dělitelný

10^{m} - 1

Důkaz. Tento důkaz byl schován, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a důkaz vás zajímá, kontaktujte mě.

Čtverce

Magické čtverce

Definice. Magický čtverec je matice

ℝ^{n \times n}

, kde součet každého řádku, sloupce a úhlopříčky je stejný.

Definice. Normální magický čtverec je magický čtverec skládající se z čísel z

\hat{n^{2}}

. Magický čtverec, který není normální, se nazývá triviální.

Věta. Magické čtverce tvoří lineární podprostor matic

n \times n

Důkaz. Triviální.

Příklad. Doplňte do čtverce přirozená čísla tak, aby vznikl magický čtverec s minimální možnou magickou konstantou.

[\begin{array}{cccc} 14 \\ 10 & 17 \\ 10 & 9 \\ 13 \end{array}]

Řešení. Kdyby místo všech vyplněných čísel byly nuly, mohli bychom ho dvěma způsoby doplnit tak, aby vznikl magický čtverec s konstantou

1

𝖠 ≔ [\begin{array}{cccc} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{array}], 𝖡 ≔ [\begin{array}{cccc} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{array}]

Jelikož k libovolnému řešení původního čtverce můžeme přičíst libovolnou lineární kombinaci těchto čtverců, můžeme bez újmy na obecnosti předpokládat řešení ve tvaru

[\begin{array}{cccc} 14 \\ 10 & 17 \\ 10 & 9 & 0 & 0 \\ 13 \end{array}]

Z toho určíme, že magická konstanta bude

19

, a můžeme doplnit (přitom budeme řešit jednoduchou rovnici):

[\begin{array}{cccc} 13 & 14 & - 4 & - 4 \\ - 8 & 0 & 10 & 17 \\ 10 & 9 & 0 & 0 \\ 4 & - 4 & 13 & 6 \end{array}]

Abychom dostali čtverec s přirozenými čísly, stačí přičíst

9 𝖠 + 5 𝖡

[\begin{array}{cccc} 13 & 14 & 1 & 5 \\ 1 & 5 & 10 & 17 \\ 10 & 9 & 9 & 5 \\ 9 & 5 & 13 & 6 \end{array}]

Tím vzniká řešení s magickou konstantou

33

, která je tedy minimální.

Cvičení. Doplňte magický čtverec přirozenými čísly:

[\begin{array}{cccc} 6 \\ 2 & 14 \\ 7 & 10 \\ 6 \end{array}]

Řešení. Toto řešení bylo schováno, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a řešení vás zajímá, kontaktujte mě.

Latinské čtverce

Definice. Latinský čtverec je matice

{\hat{n}}^{n \times n}

, kde v každém řádku a sloupci jsou různá čísla.

Definice. Dva latinské čtverce

𝐀, 𝐁

jsou ortogonální alias řecko-latinské, pokud

𝐀 \times 𝐁

(kartézský součin prvek po prvku) obsahuje každou dvojici právě jednou.

Příklad.

[\begin{array}{cccc} α & β & γ & δ \\ γ & δ & α & β \\ δ & γ & β & α \\ β & α & δ & γ \end{array}] \times [\begin{array}{cccc} a & b & c & d \\ b & a & d & c \\ c & d & a & b \\ d & c & b & a \end{array}] = [\begin{array}{cccc} (α, a) & (β, b) & (γ, c) & (δ, d) \\ (γ, b) & (δ, a) & (α, d) & (β, c) \\ (δ, c) & (γ, d) & (β, a) & (α, b) \\ (β, d) & (α, c) & (δ, b) & (γ, a) \end{array}]

Tyto dvojice jsou různé, takže pro řád

4

ortogonální latinské čtverce existují.

Věta. Neexistují ortogonální latinské čtverce řádu

2

6

. Pro všechny ostatní řády tvaru

4 k + 2

ortogonální latinské čtverce existují.

Věta. Maximální počet vzájemně ortogonálních latinských čtverců řádu

q

q - 1

Důkaz. Sporem. Předpokládejme, že jich existuje

q

. Nechť újmy na obecnosti první řádek všech čtverců je

\begin{array}{cccc} 1 & 2 & \dots & q \end{array}

. Když se podíváme na prvky přímo pod jedničkami v levém horním rohu, které nemohou být

1

, podle holubníkového principu dosáhneme sporu.

Věta. Nechť

q = p^{n}, p \in ℙ, n \in ℕ^{+}

. Pak existuje

q - 1

dvojic ortogonálních latinských čtverců.

Důkaz. Pro

q \in ℙ

použijeme čtverce ve tvaru

{(𝐋_{k})}_{i, j} ≔ k i + j mod q

kde řádky a sloupce číslujeme od nuly a

k \in \hat{q - 1}

Poznámka. Tento postup nefunguje pro složená čísla, protože řádek, jehož index je dělitelem

q

, by vypadal stejně jako první řádek.

Obecně se použije Galoisovo těleso

GF (q) = {g_{0}, \dots, g_{q - 1}}

{(𝐋_{k})}_{i, j} ≔ g_{k} ⊙ g_{i} \oplus︎ g_{j} mod q

Cvičení. Dokažte, že pro

q = 5

lze každý částečný latinský čtverec se čtyřmi vyplněnými poli doplnit na latinský čtverec.

Dobble

Jak vytvořit karty pro hru Dobble? Chceme, aby:

na každých dvou kartách byl právě jeden společný symbol
na každé kartě byl stejný počet symbolů $q + 1$
každé dvojice symbolů byla na právě jedné kartě
každý symbol byl na právě $q + 1$ kartách

Poslední dvě podmínky ve skutečném Dobble nemusí být, ale vytváří se tím příjemná dualita.

Věta. Nechť

q = p^{n}, p \in ℙ, n \in ℕ^{+}

. Pak existuje Dobble s

q^{2} + q + 1

kartami a

q^{2} + q + 1

symboly.

Příklad.

$q$	$q^{2} + q + 1$	$q + 1$
2	7	3
3	13	4
4	21	5
5	31	6
7	57	8

Poznámka. Skutečný Dobble má jen 55 karet. Vznikl jednoduše odstraněním dvou karet ze sady 57.

Důkaz. Nechť

𝐋_{1}, \dots, 𝐋_{q - 1}

jsou vzájemně ortogonální latinské čtverce řádu

q

. Pro každá

i, j \in {2, \dots, q}

definujeme matici

𝐏_{i, j} ≔ (\begin{array}{ccc} {\vec{e}}_{{(𝐋_{j - 1})}_{i, 1}} & \dots & {\vec{e}}_{{(𝐋_{j - 1})}_{i, q}} \end{array})

Dále viz papírek.

Otevřená otázka: Existuje Dobble (alias konečná projektivní rovina) i pro jiná $q$ ?

Friendship theorem

Věta, kterou dokázal Erdős: Pokud ve skupině lidí každí dva mají právě jednoho společného známého, potom mezi nimi existuje „politik“, který zná všechny.

Věta. Nechť

G

je jednoduchý konečný graf a platí

(\forall u, v \in V (G)) (\exists_{1} s \in V_{G}) (u s \in E (G) \land v s \in E (G))

Potom

(\exists p \in V (G)) (\forall v \in V (G)) (p v \in E (G))

Poznámka. Dokonce platí, že každý takový graf je větrníkový graf.

Důkaz. Nechť pro spor žádný takový vrchol

p

neexistuje. Dokážeme, že

G

je regulární graf, tedy všechny vrcholy mají stejný stupeň. Vezměme dva nesousedící vrcholy

u, v

. Nechť

k ≔ d (u)

w_{1}, w_{2}, \dots, w_{k}

jsou vrcholy sousedící s

u

. Bez újmy na obecnosti předpokládejme, že

w_{2}

je společný soused

u, v

w_{1}

je společný soused

u, w_{2}

. Nechť dále

z_{2}, \dots, z_{k}

jsou společní sousedé

v

w_{2}, \dots, w_{k}

; podle předpokladu jsou různé a zároveň různé od

w_{2}

. Z toho už plyne, že

d (v) \geq k = d (u)

. Ze symetrie musí platit rovnost. Kdyby

u, v

sousedily, vybereme si nějaký vrchol, který nesousedí s oběma (ten musí existovat?) a použijeme tranzitivitu. Tedy

G

je regulární. Mějme opět vrchol

u

a jeho sousedy

w_{1}, \dots, w_{k}

. Můžeme spočíst

\sum_{i = 1}^{k} d (w_{i}) = k^{2}

Z toho úvahou o počítání nějak odvodíme

| V | ≕ n = k^{2} - k + 1

Nechť

𝐀

je matice sousednosti

G

. Podle předpokladu a regularity grafu by mělo platit

{(𝐀^{2})}_{i, j} = {\begin{matrix} i = j \to k \\ i \neq j \to 1 \end{matrix}

𝐀^{2} = 𝐉 + (k - 1) 𝐈

kde

𝐉

je matice se samými jedničkami. Zřejmě

σ (𝐉) = {0, n}

𝐉

je diagonalizovatelná s vlastními vektory

\vec{j}, {\vec{e}}_{1}, \dots, {\vec{e}}_{n - 1}

. Ze vztahu pro

𝐀^{2}

plyne, že

σ (𝐚^{2}) = σ (J) + (k - 1) = {k + 1, n + k - 1} = {k + 1, k^{2}}

A^{2}

je diagonalizovatelná.

𝐀

je také diagonalizovatelná, neboť je symetrická, tedy

𝐀 = 𝐗 𝐃 𝐗^{- 1}, 𝐀^{2} = 𝐗 𝐃^{2} 𝐗^{- 1}

. Tudíž

𝐃^{2} = (\begin{array}{c} k^{2} \\ k - 1 \\ ⋱ \\ k - 1 \end{array})

𝐃 = (\begin{array}{c} \pm k \\ \pm \sqrt{k - 1} \\ ⋱ \\ \pm \sqrt{k - 1} \end{array})

Víme, že

𝐀

má na diagonále nuly, tedy její stopa je nulová, tudíž i součet vlastních čísel. Bez újmy na obecnosti předpokládejme, že vlastní číslo

k

je kladné, a nechť

s, r

jsou počty kladných a záporných vlastních čísel

\pm \sqrt{k - 1}

. Tedy

k + s \sqrt{k - 1} - r \sqrt{k - 1} = 0

h ≔ \sqrt{k - 1} = \frac{k}{r - s} \in ℚ

Pokud je odmocnina racionální, potom je celá, tedy

h \in ℤ

. Také

h (s - r) = k = h^{2} + 1

Tudíž

h | h^{2} + 1

, z čehož plyne

h = 1 ∴ k = 2

. Tedy graf je kružnice. V tom už si podle hodnoty

n

najdeme spor.

Poznámka. Pro nekonečné grafy věta neplatí (mohli bychom do nekonečna přidávat společné sousedy).

Domněnka: Pokud máme graf, kde mezi každými dvěma vrcholy existuje právě jedna cesta délky $l \geq 3$ , potom v něm navopák nemůže existovat politik.

Něco s trojúhelníky

Pokud máme tři body v $ℝ^{2}$ , mohou mezi nimi být vzdálenosti $1,1,1$ ? Samozřejmě: všichni známe rovnostranný trojúhelník. A co vzdálenosti $1,1,3$ ? To podle trojúhelníkové nerovnosti nejde. Známá věta sss dokazuje, že trojúhelníková nerovnost je nutná i postačující podmínka. Například kdybychom chtěli trojúhelník se stranami $3,2,2$ , uděláme přesně tohle:

Krásně namalovaná strana trojúhelníka a průsečík dvou kružnic

Co takhle čtyři body v $ℝ^{3}$ ? Chceme, aby mezi nimi byly vzdálenosti $2,2,3,3$ . (Proč jsou jenom čtyři??? Nikdo neví.) Kdybychom chtěli, aby byly vzdálenosti $| p q | = 3, | r s | = 3$ a všechny ostatní $2$ , tak to nepůjde, přestože každá stěna splňuje trojúhelníkovou nerovnost.

Lemma. Matice

𝐀 \in ℝ^{n \times n}

je symetrická a pozitivně semidefinitní právě tehdy, pokud existuje matice

𝐗 \in ℝ^{n \times n}

taková, že

𝐀 = 𝐗^{T} 𝐗

Důkaz.

(\Leftarrow)

Pozitivní semidefinitnost:

{\vec{y}}^{T} 𝐀 \vec{y} = {\vec{y}}^{T} 𝐗^{T} 𝐗 \vec{y} = {(𝐗 \vec{y})}^{T} (𝐗 \vec{y}) \geq 0

Symetričnost:

𝐀^{T} = {(𝐗^{T} 𝐗)}^{T} = 𝐗^{T} 𝐗 = 𝐀

(\Rightarrow)

Již víme, že matici dokážeme ortogonálně diagonalizovat:

𝐀 = 𝐎 𝐃 𝐎^{T} ∴ 𝐎^{T} 𝐀 𝐎 = 𝐃 = (\begin{array}{c} λ_{1} \\ ⋱ \\ λ_{n} \end{array})

Potom stačí vzít

𝐗 ≔ 𝐃^{\frac{1}{2}} 𝐎^{T}

Věta. Nechť

𝐌 \in ℝ^{(n + 1) \times (n + 1)}

je symetrická matice s nulovou diagonálou indexovaná od nuly. Potom existují body

{\vec{p}}_{0}, \dots, {\vec{p}}_{n} \in ℝ^{n}

takové, že

(\forall i, j) (‖ p_{i} - p_{j} ‖)

právě tehdy, pokud matice

𝐆 \in ℝ^{n \times n}, G_{i, j} ≔ \frac{M_{0, i}^{2} + M_{0, j}^{2} = M_{i, j}^{2}}{2}

je pozitivně semidefinitní.

Důkaz.

(\Rightarrow)

Odvodíme si

{‖ {\vec{x}}_{i} - {\vec{x}}_{j} ‖}^{2} = {‖ {\vec{x}}_{i} ‖}^{2} + {‖ {\vec{x}}_{j} ‖}^{2} - 2 \cdot {\vec{x}}_{i} \cdot {\vec{x}}_{j} ∴ {\vec{x}}_{i} \cdot {\vec{x}}_{j} = \frac{{‖ {\vec{x}}_{i} ‖}^{2} + {‖ {\vec{x}}_{j} ‖}^{2} - {‖ {\vec{x}}_{i} - {\vec{x}}_{j} ‖}^{2}}{2}

Zvolíme-li

{\vec{x}}_{i} ≔ {\vec{p}}_{i} - {\vec{p}}_{0}

, máme

{\vec{x}}_{i} \cdot {\vec{x}}_{j} = \frac{{‖ {\vec{p}}_{i} - {\vec{p}}_{0} ‖}^{2} + {‖ {\vec{p}}_{j} - {\vec{p}}_{0} ‖}^{2} - {‖ {\vec{p}}_{i} - {\vec{p}}_{j} ‖}^{2}}{2} = \frac{M_{0, i}^{2} + M_{0, j}^{2} = M_{i, j}^{2}}{2}

(\Leftarrow)

Je-li

𝐆

pozitivně definitní, potom podle lemmatu

𝐆 = 𝐗^{T} 𝐗

. Zvolme

p_{0} ≔ 0, p_{i} ≔ {\vec{X}}_{\circ, i}

. Dosazením nějak zjistíme, že to funguje.

Příklad. Mějme matici

𝐌 ≔ (\begin{array}{cccc} 0 & \sqrt{2} & \sqrt{2} & \sqrt{2} \\ \sqrt{2} & 0 & \sqrt{2} & \sqrt{6} \\ \sqrt{2} & \sqrt{2} & 0 & \sqrt{6} \\ \sqrt{2} & \sqrt{6} & \sqrt{6} & 0 \end{array})

K ní si spočteme

𝐆 = (\begin{array}{ccc} 2 & 1 & - 1 \\ 1 & 2 & - 1 \\ - 1 & - 1 & 2 \end{array})

Mohli bychom pomocí Sylvestera zkontrolovat, že je pozitivně semidefinitní, ale stejně budeme počítat vlastní čísla, takže to nemá smysl.

\det (𝐆 - λ 𝐈) = {(2 - λ)}^{3} + 2 - 3 (2 - λ) = - λ^{3} + 6 λ^{2} - 9 λ + 4 = - {(λ - 1)}^{2} (λ - 4) ∴ σ_{𝐆} = (1,1,4)

Ortonormální vlastní vektory jsou:

\frac{1}{\sqrt{2}} (\begin{array}{c} 1 \\ - 1 \\ 0 \end{array}), \frac{1}{\sqrt{6}} (\begin{array}{c} 1 \\ 1 \\ 2 \end{array}), \frac{1}{\sqrt{3}} (\begin{array}{c} - 1 \\ - 1 \\ 1 \end{array})

Máme tedy

𝐆 = 𝐎 𝐃 𝐎^{T} ≔ (\begin{array}{ccc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} & - \frac{1}{\sqrt{3}} \\ - \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} & - \frac{1}{\sqrt{3}} \\ 0 & \frac{2}{\sqrt{6}} & \frac{1}{\sqrt{3}} \end{array}) (\begin{array}{c} 1 \\ 4 \\ 4 \end{array}) (\begin{array}{ccc} \frac{1}{\sqrt{2}} & - \frac{1}{\sqrt{2}} & 0 \\ \frac{1}{\sqrt{6}} & \frac{1}{\sqrt{6}} & - \frac{2}{\sqrt{6}} \\ - \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} \end{array})

Spočteme si

𝐗 ≔ 𝐃^{\frac{1}{2}} 𝐎^{T} ≔ (\begin{array}{c} 1 \\ 2 \\ 2 \end{array}) (\begin{array}{ccc} \frac{1}{\sqrt{2}} & - \frac{1}{\sqrt{2}} & 0 \\ \frac{1}{\sqrt{6}} & \frac{1}{\sqrt{6}} & - \frac{2}{\sqrt{6}} \\ - \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} \end{array}) = (\begin{array}{ccc} \frac{1}{\sqrt{2}} & - \frac{1}{\sqrt{2}} & 0 \\ \frac{1}{\sqrt{6}} & \frac{1}{\sqrt{6}} & - \frac{2}{\sqrt{6}} \\ - \frac{2}{\sqrt{3}} & \frac{2}{\sqrt{3}} & \frac{2}{\sqrt{3}} \end{array})

Ze sloupců matice si uděláme body a máme hotovo.

Cvičení. Najděte body

p_{0}, \dots, p_{4} \in ℝ^{4}

, jejichž vzdálenosti splňují

m_{1,0} = m_{3,0} = m_{2,4} = \sqrt{2}

m_{1,2} = \sqrt{5}

m_{1,3} = 2

m_{2,0} = m_{4,0} = m_{2,3} = 1

m_{1,4} = m_{3,4} = \sqrt{3}

Řešení. Toto řešení bylo schováno, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a řešení vás zajímá, kontaktujte mě.

Algebraické identity a cirkulační determinant

Definice. Algebraická identita je vzorec jako například

a^{2} + 2 a b + b^{2}

nebo

(a + b) (a^{2} - a b + b^{2})

Příklad. Vezměme cirkulační determinant řádu 3:

\det Circ (a, b, c) ≔ \det (\begin{array}{ccc} a & b & c \\ c & a & b \\ b & c & a \end{array})

Spočtěme ho nejprve pomocí Sarusova pravidla:

\det (\begin{array}{ccc} a & b & c \\ c & a & b \\ b & c & a \end{array}) = a^{3} + b^{3} + c^{3} - 3 a b c

a poté pomocí Lagrangeova pravidla:

\det (\begin{array}{ccc} a & b & c \\ c & a & b \\ b & c & a \end{array}) = \det (\begin{array}{ccc} a + b + c & a + b + c & a + b + c \\ c & a & b \\ b & c & a \end{array}) = (a + b + c) (a^{2} + b^{2} + c^{2} - a b - a c - b c)

Tím jsme získali algebraickou identitu.

Příklad. Co takhle cirkulační determinant řádu 4?

\begin{aligned} \det Circ (a, b, c, d) = \det (\begin{array}{cccc} a & b & c & d \\ d & a & b & c \\ c & d & a & b \\ b & c & d & a \end{array}) & = a^{4} - b^{4} + c^{4} - d^{4} - 2 a^{2} c^{2} + 2 b^{2} d^{2} - 4 a^{2} b d + 4 a b^{2} c - 4 b c^{2} d + 4 a c d^{2} \\ = (a + b + c + d) \det (\begin{array}{cccc} 1 & 1 & 1 & 1 \\ d & a & b & c \\ c & d & a & b \\ b & c & d & a \end{array}) \\ = (a + b + c + d) (a + c - b - d) \det (\begin{array}{cccc} 0 & 1 & 1 & 1 \\ - 1 & a & b & c \\ 1 & d & a & b \\ - 1 & c & d & a \end{array}) \\ = (a + b + c + d) (a + c - b - d) (a^{2} + b^{2} + c^{2} + d^{2} - 2 a c - 2 b d) \end{aligned}

Příklad. Co když do cirkulačního determinantu dosadíme za některá písmena nuly?

\det Circ (a, b, 0) = (\begin{array}{ccc} a & b & c \\ c & a & b \\ b & c & a \end{array}) = a^{3} + b^{3} = (a + b) (a^{2} - a b + b^{2})

Příklad.

\det Circ (a, 0, c, 0) = {(a + c)}^{2} {(a - c)}^{2} = {(a^{2} - c^{2})}^{2} = {(\det Circ (a, c))}^{2}

Definice. Nechť

T

je těleso. Kroneckerův součin matic

𝐀 \in T^{m \times n}, 𝐁 \in T^{M \times N}

𝐀 \otimes 𝐁 ≔ (\begin{array}{ccc} 𝐀_{1,1} 𝐁 & \dots & 𝐀_{1, n} 𝐁 \\ ⋮ & ⋱ & ⋮ \\ 𝐀_{m, 1} 𝐁 & \dots & 𝐀_{m, n} 𝐁 \end{array})

Příklad.

(\begin{array}{cc} 0 & 1 \\ - 1 & 3 \end{array}) \otimes (\begin{array}{cc} 0 & - 1 \\ 2 & 2 \\ 3 & 0 \end{array}) = (\begin{array}{cccc} 0 & 0 & 0 & - 1 \\ 0 & 0 & 2 & 2 \\ 0 & 0 & 3 & 0 \\ 0 & 1 & 0 & - 3 \\ - 2 & - 2 & 6 & 6 \\ - 3 & 0 & 9 & 0 \end{array})

Cvičení. Najděte explicitní vyjádření pro

{(𝐀 \otimes 𝐁)}_{i, j}

Řešení. Toto řešení bylo schováno, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a řešení vás zajímá, kontaktujte mě.

Věta. Nechť

𝐗 \in T^{m \times n}, 𝐘 \in T^{M \times N}, 𝐀 \in T^{n \times r}, 𝐁 \in T^{N \times R}

. Potom

(𝐗 \cdot 𝐀) \otimes (𝐘 \cdot 𝐁) = (𝐗 \otimes 𝐘) \cdot (𝐀 \otimes 𝐁)

Důkaz. Tento důkaz byl schován, aby se zabránilo podvádění v domácích úkolech. Pokud zrovna nemáte zapsaný tento předmět a důkaz vás zajímá, kontaktujte mě.

Věta. Nechť

𝐗, 𝐘

jsou regulární. Potom

{(𝐗 \otimes 𝐘)}^{- 1} = 𝐗^{- 1} \otimes 𝐘^{- 1}

Důkaz.

(𝐗 \otimes 𝐘) (𝐗^{- 1} \otimes 𝐘^{- 1}) = (𝐗 \cdot 𝐗^{- 1}) \otimes (𝐘 \cdot 𝐘^{- 1}) = 𝐈_{n} \cdot 𝐈_{m} = 𝐈_{m \cdot n}

Věta. Nechť

𝐀 \in T^{m \times m}, 𝐁 \in T^{n \times n}

. Potom

\det (𝐀 \otimes 𝐁) = {(\det 𝐀)}^{n} \cdot {(\det 𝐁)}^{m}

Důkaz. Nechť

𝐉_{𝐀} = 𝐗 𝐀 𝐗^{- 1}, 𝐉_{𝐁} = 𝐘 𝐁 𝐘^{- 1}

jsou Jordanovy tvary. Potom podle předchozích vět

𝐉_{𝐀} \otimes 𝐉_{𝐁} = (𝐗 \otimes 𝐘) (𝐀 \otimes 𝐁) {(𝐗 \otimes 𝐘)}^{- 1} ∴ \det (𝐉_{𝐀} \otimes 𝐉_{𝐁}) = \det (𝐀 \otimes 𝐁)

Kroneckerův součin horních trojúhelníkových matic je zřejmě horní trojúhelníková matice. Tedy pokud

λ_{1}, \dots, λ_{m}, μ_{1}, \dots, μ_{n}

jsou vlastní čísla

𝐀, 𝐁

, potom

\det (𝐀 \otimes 𝐁) = \prod_{i = 1}^{m} λ_{i}^{n} \det 𝐁 = {(\det 𝐀)}^{n} {(\det 𝐁)}^{m}

Věta.

\det Circ (\underset{k}{\underset{⏟}{c_{1}, 0, \dots, 0}}, \dots, \underset{k}{\underset{⏟}{c_{n}, 0, \dots, 0}}) = {(\det Circ (c_{1}, \dots, c_{n}))}^{k}

Důkaz. Použijeme předchozí větu na

\det (Circ (c_{1}, \dots, c_{n}) \otimes 𝐈_{k})

Diferenční a sumační počet

Máme operátor $D : 𝒞^{\infty} \to 𝒞^{\infty}$ , který každé funkci přiřadí její derivaci. Zkusme najít diskrétní analogii.

Definice. Nechť

M

je množina uzavřená na přičtení

1

. Operátor diferencování je operátor

Δ : (M \to ℂ) \to (M \to ℂ)

definovaný jako

Δ f (x) ≔ f (x + 1) - f (x)

Operátor posunutí

E : (M \to ℂ) \to (M \to ℂ)

E f (x) = f (x + 1)

Věta (linearita diference).

Δ (f + α \cdot g) = Δ f + α \cdot Δ g

Důkaz. Triviální.

Věta (diference součinu).

Δ (f \cdot g) = Δ f \cdot E g + f \cdot Δ g

Δ (f \cdot g) (x) = Δ f (x) \cdot g (x + 1) + f (x) \cdot Δ g (x)

Důkaz.

\begin{aligned} Δ (f \cdot g) (x) & = f (x + 1) g (x + 1) - f (x) g (x) \\ = f (x + 1) g (x + 1) - f (x) g (x + 1) + f (x) g (x + 1) - f (x) g (x) \\ = Δ f (x) \cdot g (x + 1) + f (x) \cdot Δ g (x) \end{aligned}

Věta (diference podílu).

Δ (\frac{f}{g}) (x) = \frac{Δ f (x) \cdot g (x) - f (x) \cdot Δ g (x)}{g (x) g (x + 1)}

Důkaz.

\begin{aligned} Δ (\frac{f}{g}) (x) & = \frac{f (x + 1)}{g (x + 1)} - \frac{f (x)}{g (x)} \\ = \frac{f (x + 1) g (x) - f (x) g (x + 1)}{g (x) g (x + 1)} \\ = \frac{f (x + 1) g (x) - f (x) g (x) + f (x) g (x) - f (x) g (x + 1)}{g (x) g (x + 1)} \\ = \frac{Δ f (x) \cdot g (x) - f (x) \cdot Δ g (x)}{g (x) g (x + 1)} \end{aligned}

Definice. Padající faktoriál je

x^{m} ≔ \prod_{i = 0}^{m - 1} (x - i)

Věta.

x^{m} = x^{m - 1} (x - m + 1)

Věta (diference padajícího faktoriálu).

Δ x^{m} = m x^{m - 1}

Věta (pevný bod diference).

Δ 2^{x} = 2^{x}

Důkaz. Triviální.

Věta (diference sinu).

Δ \sin (α x) = α \sin \frac{α}{2} \cos (α (x + \frac{1}{2}))

Definice. Operátor neurčité sumace je operátor

\sum

takový, že

F (x) = \sum f (x) δ x ⟺ Δ F (x) = f (x)

Definice. Operátor určité sumace je operátor

\sum

definovaný jako

\sum_{a}^{b} f (x) δ x ≔ \sum_{x = a}^{b - 1} f (x)

Věta (základní věta sumačního počtu). Nechť

F (x) = \sum f (x) δ x

. Potom

\sum_{a}^{b} f (x) δ x = F (b) - F (a)

Důkaz.

\sum_{a}^{b} f (x) δ x = \sum_{x = a}^{b - 1} Δ F (x) = \sum_{x = a}^{b - 1} (F (x + 1) - F (x)) = F (b) - F (a)

Pomocí sumačního počtu se dají snadno počítat sumy polynomů. Stačí polynom vyjádřit v bázi sestávající z padajících faktoriálů a sesumit po složkách.

Příklad.

\sum_{k = 1}^{n} k^{3} = \sum_{1}^{n + 1} (x^{3} + 3 x^{2} + x^{1}) δ x = {[\frac{x^{4}}{4} + 3 \frac{x^{3}}{3} + \frac{x^{2}}{2}]}_{1}^{n + 1} = \dots = {(\frac{n (n + 1)}{2})}^{2}

Příklad.

\sum_{k = 1}^{n} \cos (α k) = \sum_{1}^{n + 1} \cos (α x) δ x = \frac{{[\sin (α (x - \frac{1}{2}))]}_{1}^{n + 1}}{2 \sin \frac{α}{2}}

Věta (sumace per partes).

\sum_{a}^{b} f \cdot Δ g δ x = {[f \cdot g]}_{a}^{b} - \sum_{a}^{b} Δ f \cdot E g δ x

\sum_{a}^{b} f (x) \cdot Δ g (x) δ x = {[f (x) \cdot g (x)]}_{a}^{b} - \sum_{a}^{b} Δ f (x) \cdot g (x + 1) δ x

Příklad.

\sum_{k = 1}^{n} k q^{k} = \sum_{1}^{n + 1} x q^{x} δ x = {[\frac{x q^{x}}{q - 1}]}_{1}^{n + 1} - \sum_{1}^{n + 1} \frac{q}{q - 1} q^{x} = \frac{q^{2}}{{(q - 1)}^{2}} (q^{n} - 1)

Poznámka. Na rozdíl od integrálu se dvě různé neurčité sumace nemusí lišit jen o konstantu. Například

\sum 0 δ x

může být libovolná funkce s periodou

1

. Pro posloupnosti už to však platí.

Definice. Záporný padající faktoriál je dán vztahem

x^{- m} ≔ {(\prod_{i = 1}^{m} (x - i))}^{- 1}

Poznámka. Předchozí věty o padajícím faktoriálu stále platí.

Příklad.

\sum_{k = 1}^{n} \frac{1}{k (k + 1) (k + 2)} = \sum_{k = 0}^{n - 1} \frac{1}{(k + 1) (k + 2) (k + 3)} = \sum_{0}^{n} x^{- 3} δ x = {[\frac{x^{- 2}}{- 2}]}_{0}^{n}

Věta.

Δ^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) {(- 1)}^{n - k} E^{k}

Δ^{n} f (x) = \sum_{k = 0}^{n} (\binom{n}{k}) {(- 1)}^{n - k} f (x + k)

Důkaz. Plyne přímo ze vztahu

Δ = E - I

a binomické věty.

Věta.

E^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) Δ^{k}

f (x + n) = \sum_{k = 0}^{n} (\binom{n}{k}) Δ^{k} f (x)

Důkaz. Plyne přímo ze vztahu

E = Δ + I

a binomické věty.

Definice. Newtonův polynom (jakási analogie MacLaurinova polynomu) funkce

f

P_{n} (x) ≔ \sum_{k = 0}^{n} \frac{Δ^{k} f (0)}{k!} x^{k} = \sum_{k = 0}^{n} (\binom{x}{k}) Δ^{k} f (0)

Věta.

(\forall k \in {0, \dots, n}) (Δ^{k} f (0) = Δ^{k} P_{n} (0))

Důkaz. Analogicky jako u Taylorova polynomu.

Věta. Newtonův polynom „dobře aproximuje“ funkci:

(\forall l \in {0, \dots, n}) (P_{n} (l) = f (l))

Důkaz.

\begin{aligned} P_{n} (l) & = \sum_{k = 0}^{n} (\binom{l}{k}) \sum_{i = 0}^{k} (\binom{k}{i}) {(- 1)}^{k - i} f (i) \\ = \sum_{k = 0}^{l} (\binom{l}{k}) \sum_{i = 0}^{k} (\binom{k}{i}) {(- 1)}^{k - i} f (i) \\ = \sum_{i = 0}^{l} f (i) \sum_{k = i}^{l} {(- 1)}^{k - i} \frac{k! \cdot l!}{i! \cdot (k - i)! \cdot k!} \\ = \sum_{i = 0}^{l} (\binom{l}{i}) f (i) \sum_{k = i}^{l} {(- 1)}^{k - i} (\binom{l - i}{k - i}) \\ = \sum_{i = 0}^{l} (\binom{l}{i}) f (i) \sum_{k = i}^{l} {(1 - 1)}^{l - i} \\ = \sum_{i = 0}^{l} (\binom{l}{i}) f (i) \sum_{k = i}^{l} δ_{l, i} \\ = f (l) \end{aligned}

Definice. Newtonova řada (analogie Maclaurinovy řady) funkce

f

P_{n} (x) ≔ \sum_{n = 0}^{\infty} \frac{Δ^{n} f (0)}{n!} x^{n} = \sum_{n = 0}^{\infty} (\binom{x}{n}) Δ^{k} f (0)

Věta.

(\forall c \in (0,2)) (c^{x} = \sum_{n = 0}^{\infty} {(c - 1)}^{n} (\binom{x}{n}))

Důkaz. Plyne z Maclaurinovy řady funkce

{(1 + y)}^{α}

Zápisky z Algebry a analýzy v aplikacích

$p$ -adická čísla

Aritmetika v $p$ -adických číslech

Základní věta algebry

Midyho věta

Čtverce

Magické čtverce

Latinské čtverce

Dobble

Friendship theorem

Něco s trojúhelníky

Algebraické identity a cirkulační determinant

Wythoffova hra

Diferenční a sumační počet

Zápisky z Algebry a analýzy v aplikacích

p-adická čísla

Aritmetika v p-adických číslech

Základní věta algebry

Midyho věta

Čtverce

Magické čtverce

Latinské čtverce

Dobble

Friendship theorem

Něco s trojúhelníky

Algebraické identity a cirkulační determinant

Wythoffova hra

Diferenční a sumační počet

$p$ -adická čísla

Aritmetika v $p$ -adických číslech