Matematika Universitas — Tahun 2 · Bachelor Year 2

17Ruang Afin

Ruang vektor punya satu titik istimewa — yakni titik asalnya — yang tak diinginkan geometri. Sebuah ruang afin adalah ruang vektor yang telah melupakan titik asalnya: sebab titik dan vektor menjadi jenis yang berbeda, yang dikaitkan penggeseran. Bab pendek ini membangun kamusnya (yakni titik, barisentrum, subruang dan pemetaan afin), pandangan afin atas kecembungan, dan perkakas penggolongan yang dipakai pada bab geometri berikutnya.

17.1 Titik dan vektor

Definisi 17.1

Sebuah ruang afin yang diarahkan ruang vektor real $E$ adalah himpunan tak kosong $\mathcal{E}$ dengan pemetaan $(A, B) \mapsto \vect{AB} \in E$ yang memenuhi

\vect{AB} + \vect{BC} = \vect{AC} \quad \text{(Chasles)}, \qquad \text{untuk tiap } A,\ B \mapsto \vect{AB} \text{ merupakan bijeksi } \mathcal{E} \to E .

Kita menulis $B = A + u$ bagi titik tunggal dengan $\vect{AB} = u$ . Adapun dimensi $\mathcal{E}$ adalah $\dim E$ . Setiap ruang vektor merupakan ruang afin atas dirinya sendiri (dengan $\vect{AB} = B - A$ ); dan setiap pemilihan titik asal $O \in \mathcal{E}$ mengenali $\mathcal{E}$ dengan $E$ lewat $M \mapsto \vect{OM}$ .

Contoh 17.2 (Sebuah ruang afin tanpa titik asal yang alami)

Bidang penyelesaian $\mathcal E = \{(x, y, z) \in \R^3 : x + y + z = 1\}$ bukan subruang vektor (sebab $0 \notin \mathcal E$ ), tetapi ia ruang afin yang diarahkan $E = \{x + y + z = 0\}$ : sebab untuk $A, B \in \mathcal E$ selisih $\vect{AB} = B - A$ mendarat di $E$ (karena jumlahnya saling meniadakan), Chasles diwarisi dari $\R^3$ , dan $B \mapsto \vect{AB}$ bijektif ke $E$ . Tak ada titik $\mathcal E$ yang diistimewakan — sebab sembarang pemilihan “titik asal” $O \in \mathcal E$ sama saja berhasil, dan semua pengenalan $M \mapsto \vect{OM}$ hanya berselisih penggeseran. Inilah keadaan yang khas: himpunan penyelesaian masalah linear yang tak homogen (yakni sistem linear, persamaan diferensial linear pada Bab 16) bersifat afin, tak pernah linear, dan slogan “penyelesaian khusus ditambah kernel” persis merupakan pernyataan $\mathcal F = A + F$ pada definisi berikutnya.

Definisi 17.3 (Barisentrum)

Misalkan $(A_i, \lambda_i)_{i \leq k}$ titik terbobot dengan $\sum\lambda_i \neq 0$ . Adapun barisentrum $G = \operatorname{bar}\bigl((A_i, \lambda_i)\bigr)$ adalah titik tunggal dengan

\sum_i \lambda_i\, \vect{GA_i} = 0 \qquad\text{setara dengan}\qquad \vect{OG} = \frac{1}{\sum\lambda_i}\sum_i \lambda_i\,\vect{OA_i} \quad (\text{sembarang } O).

Barisentrum bersifat asosiatif (sebab subkelompok titiknya boleh diganti barisentrum parsialnya dengan bobot yang dijumlahkan) dan invarian terhadap penskalaan ulang semua bobotnya.

Bukti keberadaan dan rumusnya. Tetapkan $O$ lalu tulis $s = \sum_i\lambda_i \neq 0$ . Menurut Chasles,

\sum_i\lambda_i\,\vect{GA_i} = 0 \iff \sum_i\lambda_i\bigl(\vect{GO} + \vect{OA_i}\bigr) = 0 \iff s\,\vect{OG} = \sum_i\lambda_i\,\vect{OA_i},

yang menentukan $G = O + \frac1s\sum_i\lambda_i\vect{OA_i}$ secara tunggal. Ketakbergantungannya pada $O$ : sebab untuk titik asal lain $O'$ ,

\frac1s\sum_i\lambda_i\,\vect{O'A_i} = \frac1s\sum_i\lambda_i\bigl(\vect{O'O} + \vect{OA_i}\bigr) = \vect{O'O} + \frac1s\sum_i\lambda_i\,\vect{OA_i} = \vect{O'G} :

yakni titik $G$ yang sama. Keasosiatifannya: pecahlah himpunan indeksnya menjadi $I \sqcup J$ dengan $s_I = \sum_{i\in I}\lambda_i \neq 0$ , lalu misalkan $G_I$ barisentrum $(A_i, \lambda_i)_{i\in I}$ , sehingga $\sum_{i\in I}\lambda_i\vect{OA_i} = s_I\,\vect{OG_I}$ . Maka

s\,\vect{OG} = \sum_{i\in I}\lambda_i\vect{OA_i} + \sum_{j\in J}\lambda_j\vect{OA_j} = s_I\,\vect{OG_I} + \sum_{j\in J}\lambda_j\vect{OA_j} :

jadi $G$ adalah barisentrum $(G_I, s_I)$ bersama $(A_j, \lambda_j)_{j\in J}$ , seperti diklaim. Penskalaan ulangnya: mengganti tiap $\lambda_i$ dengan $t\lambda_i$ (dengan $t \neq 0$ ) mengalikan $s$ dan jumlah terbobotnya dengan $t$ , jadi $\vect{OG}$ tak berubah. ∎

Catatan 17.4 (Jebakan yang sering muncul)

Dua jebakan mengelilingi definisinya. Pertama, bila bobotnya berjumlah nol, maka tak ada barisentrum: sebab pemetaan $O \mapsto \sum\lambda_i\vect{OA_i}$ lalu tak bergantung pada $O$ dan mendefinisikan sebuah vektor, bukan titik — misalnya $(A, -1;\ B, 1)$ menyandikan $\vect{AB}$ . Jadi melacak yang mana dari kedua objek itu yang dihasilkan sebuah perhitungan adalah separuh dari kebersihan barisentrik. Kedua, bobotnya hanya bermakna hingga sebuah faktor tak nol bersama; jadi rumus seperti “koordinat $G$ adalah $\lambda_1, \dots, \lambda_k$ ” mengandaikan sebuah penormalan (biasanya $\sum\lambda_i = 1$ ), dan lupa menormalkannya adalah sumber baku bagi nisbah yang salah pada sebuah gambar.

Definisi 17.5 (Subruang afin; pemetaan afin)

Sebuah subruang afin adalah himpunan $\mathcal{F} = A + F = \{A + u : u \in F\}$ dengan $F$ sebuah subruang vektor (yakni arahnya); setara dengan itu, sebuah himpunan tak kosong yang stabil terhadap barisentrum. Adapun subruang afin $\R^n$ persis merupakan himpunan penyelesaian sistem linear $MX = B$ (lewat Tahun ke-1: penyelesaian khusus ditambah kernel). Sebuah pemetaan $f \colon \mathcal{E} \to \mathcal{E}'$ disebut afin apabila ia memelihara barisentrum — setara dengan apabila

f(A + u) = f(A) + \varphi(u)

bagi sebuah pemetaan linear (yang tunggal) $\varphi = \vec f$ , yakni bagian linearnya. Pemetaan afin $\R^n$ : yaitu $X \mapsto MX + C$ . Komposisinya bersifat afin dengan bagian linear yang dikomposisikan; dan $f$ bijektif bila dan hanya bila $\vec f$ bijektif.

Bukti kesetaraannya bagi pemetaan. Bila $f(A + u) = f(A) + \varphi(u)$ : maka untuk barisentrum $G$ milik $(A_i, \lambda_i)$ , dengan menguraikan setiap titiknya dari $A$ , $f(G) = f(A) + \varphi(\vect{AG})$ dan $\varphi(\vect{AG}) = \frac{\sum\lambda_i\varphi(\vect{AA_i})}{\sum\lambda_i}$ : jadi $f(G)$ adalah barisentrum petanya. Sebaliknya, tetapkan $A$ lalu definisikan $\varphi(u) = \vect{f(A)\,f(A + u)}$ . Kehomogenannya: sebab $A + tu = \operatorname{bar}\bigl(A, 1-t;\ A + u, t\bigr)$ untuk setiap $t$ yang real, jadi pemeliharaan barisentrumnya (dengan bobot real sembarang, sebagaimana dihipotesiskan) memberi $\varphi(tu) = t\,\varphi(u)$ secara langsung. Keaditifannya: sebab $A + u + v = \operatorname{bar}\bigl(A + 2u, \tfrac12;\ A + 2v, \tfrac12\bigr)$ , jadi $\varphi(u + v) = \tfrac12\varphi(2u) + \tfrac12\varphi(2v) = \varphi(u) + \varphi(v)$ , dengan memakai kehomogenannya. Karena itu $\varphi$ bersifat linear. ∎

Catatan 17.6

Buktinya memakai barisentrum dengan bobot real yang sembarang: sebab langkah kehomogenannya mengambil $t$ di luar $\intcc01$ . Bila sebuah pemetaan hanya diandaikan memelihara barisentrum berbobot taknegatif — yakni setara dengan memelihara titik tengah dan ruas — maka kelinearan pemetaan vektornya tak lagi gratis: sebab kita hanya memperoleh kelinearan atas $\Q$ , dan sebuah hipotesis kekontinuan diperlukan untuk menyimpulkannya, persis seperti pada Latihan 17.5. Jadi membedakan “memelihara semua barisentrum” dari “memelihara kombinasi cembung” adalah kehalusan kecil tetapi nyata pada kosakata afinnya.

Contoh 17.7 (Geometri barisentrum yang klasik)

Titik berat segitiga $ABC$ adalah barisentrum $G = \operatorname{bar}(A,1; B,1; C,1)$ . Keasosiatifannya bersama titik tengah $A' = \operatorname{bar}(B, 1; C, 1)$ menunjukkan

G = \operatorname{bar}(A, 1;\ A', 2) :

jadi $G$ terletak pada garis berat $AA'$ pada dua pertiganya — dan demikian pula bagi dua garis berat lainnya: sehingga ketiga garis beratnya berkonkuren, dalam satu baris kalkulus barisentrik.

Contoh 17.8 (Bimedian sebuah segi empat)

Misalkan $ABCD$ sembarang segi empat (bidang atau bukan!) lalu tinjaulah bimediannya: yakni ruas yang menghubungkan titik tengah sisi berhadapannya, $M_{AB}M_{CD}$ dan $M_{BC}M_{DA}$ . Perkenalkanlah barisentrum $G$ milik $(A,1; B,1; C,1; D,1)$ lalu kelompokkanlah bobotnya lewat dua cara:

G = \operatorname{bar}\bigl(M_{AB}, 2;\ M_{CD}, 2\bigr) = \operatorname{bar}\bigl(M_{BC}, 2;\ M_{DA}, 2\bigr) :

jadi $G$ adalah titik tengah kedua bimediannya — sehingga kedua bimediannya selalu saling membagi dua, dan segi empat yang dibentuk keempat titik tengahnya adalah jajaran genjang (yang diagonalnya adalah bimediannya). Jadi tanpa analisis kasus, tanpa koordinat, dan hujahnya bertahan tanpa berubah bagi segi empat yang bersilang di $\R^3$ , tempat bukti berbasis gambar sudah akan peka: sebab keasosiatifannya tak peduli pada dimensinya.

Contoh 17.9 (Menggolongkan sebuah pemetaan afin, dari awal sampai akhir)

Misalkan $f(x, y) = (2x - 1,\ 3y - 4)$ pada $\R^2$ . Bagian linearnya adalah $\varphi = \operatorname{diag}(2, 3)$ , yang spektrumnya $\{2, 3\}$ menghindari $1$ : jadi menurut kriteria titik tetap yang dibuktikan di bawah (Proposisi 17.17), $f$ punya tepat satu titik tetap, yang ditemukan dengan menyelesaikan

x = 2x - 1, \qquad y = 3y - 4 \qquad\Longrightarrow\qquad \Omega = (1, 2).

Setelah dipusatkan ulang di $\Omega$ (tetapkan $x = 1 + u$ , $y = 2 + v$ ):

f(1 + u,\ 2 + v) = (1 + 2u,\ 2 + 3v) :

dalam kerangka di $\Omega$ , $f$ adalah bagian linearnya, yakni sebuah pemuaian anisotropik yang meregang $2$ kali mendatar dan $3$ kali tegak dari pusat $(1, 2)$ . Pelajaran umumnya: sebuah pemetaan afin adalah “pemetaan linear ditambah data lokasi”, dan data lokasinya runtuh menjadi satu titik asal yang terpilih baik setiap kali $1$ bukan nilai eigennya. Sebaliknya, menggeser titik asalnya secara buruk justru menciptakan suku tetapnya: jadi geometri afin adalah seni memilih tempat menaruh $0$ .

Catatan 17.10 (Metode: kekonkurenan dan kesegarisan lewat barisentrum)

Contoh Contoh 17.7 adalah sebuah wujud resep umum. Untuk membuktikan bahwa tiga cevian sebuah segitiga berkonkuren, pamerkanlah satu sistem terbobot $(A, \alpha; B, \beta; C, \gamma)$ lalu pakailah keasosiatifannya lewat tiga cara: sebab mengelompokkan $(B, C)$ menunjukkan barisentrumnya terletak pada cevian dari $A$ , mengelompokkan $(C, A)$ pada cevian dari $B$ , dan mengelompokkan $(A, B)$ pada yang ketiga. Untuk garis beratnya, sistem $(A, 1; B, 1; C, 1)$ mengerjakan semuanya; sedangkan untuk cevian yang memotong sisinya dengan nisbah yang ditentukan, bobotnya dibaca dari nisbahnya. Untuk membuktikan tiga titik segaris, tulislah satu sebagai barisentrum dua lainnya (Latihan 17.2), atau pakailah kriteria determinan pada Latihan 17.11. Kedua resepnya mengganti kecerdikan geometri dengan tata buku bobot — dan persis untuk itulah kalkulus barisentrik ada.

17.2 Kecembungan, secara afin

Definisi 17.11

Sebuah himpunan bagian $C$ pada ruang afin disebut cembung apabila ia memuat setiap barisentrum berbobot taknegatif atas titiknya — setara dengan itu, setiap ruas $\intcc{A}{B} = \{\operatorname{bar}(A, 1-t; B, t) : t \in \intcc{0}{1}\}$ di antara titiknya. Adapun bungkus cembung $\operatorname{conv}(S)$ adalah himpunan semua barisentrum berbobot taknegatif atas titik $S$ — yakni himpunan cembung terkecil yang memuat $S$ .

Contoh 17.12 (Epigraf itu himpunan cembung)

Daerah $C = \{(x, y) : y \geq x^2\}$ di atas parabolanya bersifat cembung: sebab untuk $(x_1, y_1), (x_2, y_2) \in C$ dan $t \in \intcc01$ , ketaksamaan kecembungan fungsi kuadratnya memberi

\bigl((1-t)x_1 + tx_2\bigr)^2 \leq (1-t)x_1^2 + tx_2^2 \leq (1-t)y_1 + ty_2 ,

jadi barisentrumnya tetap di atas parabolanya. Adapun perhitungannya bersifat umum: $\{y \geq f(x)\}$ cembung persis ketika $f$ merupakan fungsi cembung — jadi himpunan cembung dan fungsi cembung (Bab 8) adalah dua wajah satu gagasan, dengan epigrafnya sebagai kamusnya. Inilah alasan geometris mengapa garis penyangga ada bagi fungsi cembung, yakni fakta yang kelak membuktikan ketaksamaan Jensen pada Bab 22.

Contoh 17.13 (Pembangun yang mubazir bagi sebuah bungkus cembung)

Misalkan $S = \{(0,0), (2,0), (2,2), (0,2), (1,1)\}$ . Titik kelimanya adalah barisentrum

(1,1) = \operatorname{bar}\bigl((0,0), \tfrac12;\ (2,2), \tfrac12\bigr),

jadi ia sudah terletak di bungkus keempat lainnya: sehingga $\operatorname{conv}(S)$ adalah bujur sangkar dengan keempat pojoknya sebagai titik sudutnya. Secara umum, titik $S$ yang merupakan barisentrum berbobot taknegatif atas titik lain milik $S$ dapat dihapus tanpa mengubah bungkusnya; sedangkan titik yang tak pernah dapat dihapus (di sini keempat pojoknya) adalah titik ekstrem bungkusnya. Menentukannya adalah perhitungan barisentrum yang murni: misalnya $(2,0)$ tak dapat dituliskan sebagai $\operatorname{bar}$ titik sisanya dengan bobot yang taknegatif, karena koordinat pertamanya akan memaksa seluruh bobotnya ke titik yang $x = 2$ , lalu koordinat keduanya gagal. Jadi pertanyaan kecembungan menyusut, berulang kali, menjadi menyelesaikan sistem terbobot yang kecil.

Teorema 17.14 (Carathéodory)

Pada ruang afin berdimensi $n$ , setiap titik $\operatorname{conv}(S)$ adalah barisentrum atas paling banyak $n + 1$ titik $S$ .

Bukti. Misalkan $G = \operatorname{bar}(A_0, \lambda_0; \dots; A_k, \lambda_k)$ dengan $\lambda_i > 0$ , $\sum\lambda_i = 1$ , dan $k + 1 > n + 1$ titik. Adapun $k$ vektor $\vect{A_0A_i}$ (untuk $i \geq 1$ ) bergantungan (sebab $k > n$ ): jadi $\sum_{i\geq1}\mu_i \vect{A_0A_i} = 0$ secara tak trivial; lalu dengan menetapkan $\mu_0 = -\sum_{i\geq1}\mu_i$ , kita memperoleh bobot $(\mu_i)$ dengan $\sum\mu_i = 0$ dan $\sum \mu_i\,\vect{OA_i} = 0$ (untuk sembarang $O$ ), yang tak semuanya nol. Maka untuk setiap $t$ yang real bobot $\lambda_i - t\mu_i$ tetap berjumlah $1$ dan, karena $\sum_i\mu_i\vect{OA_i} = 0$ ,

\sum_i(\lambda_i - t\mu_i)\,\vect{OA_i} = \sum_i\lambda_i\,\vect{OA_i} :

jadi keduanya menghasilkan titik $G$ yang sama. Kini geserlah $t$ dari $0$ : suatu $\mu_i$ bersifat positif (sebab jumlahnya nol dan tak semuanya nol), jadi

t^* = \min\Bigl\{\frac{\lambda_i}{\mu_i} : \mu_i > 0\Bigr\}

terdefinisi baik dan positif. Di $t = t^*$ : untuk indeks dengan $\mu_i > 0$ berlaku $\lambda_i - t^*\mu_i \geq 0$ berkat keminimalannya, dengan kesamaan pada indeks yang meminimumkannya; sedangkan untuk indeks dengan $\mu_i \leq 0$ berlaku $\lambda_i - t^*\mu_i \geq \lambda_i > 0$ . Jadi semua bobotnya tetap taknegatif dan sekurangnya satu telah mati: sehingga $G$ dituliskan ulang sebagai barisentrum atas titik yang lebih sedikit. Ulangilah selama lebih dari $n + 1$ titik tersisa. ∎

Contoh 17.15

Pada bidangnya (dengan $n = 2$ ): setiap titik bungkus cembung sebuah himpunan berhingga terletak di sebuah segitiga yang titik sudutnya di himpunan itu — yakni isi geometris Carathéodory, yang dipakai dalam pengoptimalan dan peluang (yakni campuran) sekaligus.

Contoh 17.16 (Menjalankan algoritma Carathéodory)

Tulislah pusat bujur sangkar pada Contoh 17.13 dengan keempat pojoknya $A_1 = (0,0)$ , $A_2 = (2,0)$ , $A_3 = (2,2)$ , $A_4 = (0,2)$ :

(1,1) = \operatorname{bar}\bigl(A_1, \tfrac14;\ A_2, \tfrac14;\ A_3, \tfrac14;\ A_4, \tfrac14\bigr),

yakni empat titik pada dimensi $2$ — satu terlalu banyak. Adapun resep buktinya meminta bobot $(\mu_i)$ dengan $\sum\mu_i = 0$ dan $\sum\mu_i\vect{OA_i} = 0$ : di sini $\mu = (1, -1, 1, -1)$ berhasil (sebab kedua diagonalnya berbagi titik tengahnya). Menggeser $\lambda_i \mapsto \lambda_i - t\mu_i$ menjaga barisentrumnya tetap untuk setiap $t$ ; lalu nilai terterima yang ekstrem $t = \frac14$ membuat bobotnya $(0, \tfrac12, 0, \tfrac12)$ , yang membunuh $A_1$ dan $A_3$ sekaligus:

(1,1) = \operatorname{bar}\bigl(A_2, \tfrac12;\ A_4, \tfrac12\bigr),

yakni penyajian lewat dua titik — bahkan lebih baik daripada tiga yang dijamin teoremanya, karena pusatnya kebetulan terletak pada sebuah ruas di antara pembangunnya. Adapun algoritmanya sepenuhnya mekanis: carilah sebuah kebergantungan, geserlah sampai sebuah bobot mati, lalu ulangi.

17.3 Perkakas penggolongan afin

Proposisi 17.17 (Titik tetap pemetaan afin)

Misalkan $f$ endomorfisma afin sebuah ruang afin berdimensi hingga dengan bagian linear $\varphi$ . Bila $1 \notin \operatorname{Sp}(\varphi)$ , maka $f$ punya tepat satu titik tetap $\Omega$ , dan dalam pemvektoran di $\Omega$ , $f$ adalah bagian linearnya. (Adapun penggeseran, dengan $\varphi = \mathrm{id}$ dan tanpa titik tetap, merupakan halangan dasarnya.)

Bukti. Tetapkan $O$ lalu tulis $f(O + x) = f(O) + \varphi(x)$ . Titik $O + x$ bersifat tetap bila dan hanya bila $O + x = f(O) + \varphi(x)$ , yakni

(\mathrm{id} - \varphi)(x) = \vect{O f(O)} .

Pada dimensi hingga, $\mathrm{id} - \varphi$ terbalikkan bila dan hanya bila $0$ bukan nilai eigen $\mathrm{id} - \varphi$ , yakni bila $1 \notin \operatorname{Sp}\varphi$ — dan pada kasus itu persamaan pada displainya punya tepat satu penyelesaian $x^*$ , yang memberi titik tetap tunggal $\Omega = O + x^*$ . Adapun pemusatan ulangnya: untuk sembarang vektor $u$ ,

f(\Omega + u) = f(\Omega) + \varphi(u) = \Omega + \varphi(u),

jadi dalam kerangka bertitik asal $\Omega$ pemetaannya berbunyi $u \mapsto \varphi(u)$ : yakni linear murni. Sedangkan ketika $1 \in \operatorname{Sp}\varphi$ , entah tak ada titik tetap (sebab persamaan pada displainya boleh jadi tak terselesaikan, seperti untuk penggeseran) atau justru seluruh subruang afin titik tetapnya ada (tambahkanlah sembarang vektor eigen bernilai eigen $1$ pada sebuah penyelesaian): jadi ketunggalannya persis merupakan syarat spektralnya. ∎

Contoh 17.18 (Isometri bidang, dirampungkan)

Sebuah isometri afin bidang Euklides punya bagian linear di $O(2)$ : yakni sebuah perputaran $R_\theta$ atau sebuah pencerminan (lewat jilid Tahun ke-1). Bila $\theta \neq 0$ : maka $1 \notin \operatorname{Sp} R_\theta$ , jadi pemetaannya merupakan perputaran terhadap satu pusat yang tunggal (Proposisi 17.17). Bila bagian linearnya sebuah pencerminan: maka entah sebuah pencerminan pada sebuah sumbu (jika titik tetapnya ada) atau sebuah pencerminan geser (yakni pencerminan yang dikomposisikan dengan penggeseran sepanjang sumbunya, tanpa titik tetap). Bersama penggeserannya, inilah penggolongan lengkap isometri bidang.

Catatan 17.19 (Isometri bidangnya, sekilas)

Mengumpulkan kasusnya: identitas; penggeseran (dengan $\vec f = \mathrm{id}$ , tanpa titik tetap kecuali yang trivial); perputaran (dengan bagian linear $R_\theta$ dan $\theta \neq 0$ : yakni satu pusat); pencerminan (dengan bagian linear sebuah pencerminan, dan sebuah garis titik tetap); pencerminan geser (dengan bagian linear yang sama, tanpa titik tetap). Jadi empat keluarga ditambah identitasnya, yang masing-masing dikenali lewat dua data belaka: yakni bagian linearnya dan himpunan titik tetapnya — inilah pola Proposisi 17.17 yang dibuat menyeluruh.

Contoh 17.20 (Sebuah pencerminan geser, tertangkap basah)

Misalkan $f(x, y) = (y + 1,\ x + 1)$ . Bagian linearnya $(x, y) \mapsto (y, x)$ adalah pencerminan pada diagonal $y = x$ , jadi $1 \in \operatorname{Sp}\vec f$ dan Proposisi 17.17 membisu. Titik tetapnya akan menuntut $x = y + 1$ dan $y = x + 1$ sekaligus: yang mustahil — jadi tak ada, sehingga $f$ bukan pencerminan. Adapun mengkuadratkannya menyelesaikan penggolongannya:

f\bigl(f(x, y)\bigr) = f(y + 1,\ x + 1) = (x + 2,\ y + 2),

yakni penggeseran sebesar $(2, 2)$ : jadi $f$ adalah pencerminan geser yang bersumbu garis $y = x$ (yang digeser sepantasnya: sebab titik tengah $M$ dan $f(M)$ selalu terletak pada $y = x + {}$ konstanta, di sini $y = x$ , seperti diperiksa pada $M = (0, 0) \mapsto (1,1)$ ) dengan vektor geser $(1, 1)$ , yakni separuh $f \circ f$ . Bandingkan dengan Latihan 17.6, tempat bagian linear yang sama tetapi konstanta yang berbeda menghasilkan pencerminan yang jujur: jadi dengan hadirnya nilai eigen $1$ , suku tetapnya memutuskan segalanya.

Contoh 17.21 (Rekursi afin itu dinamika afin)

Rekursi klasik $u_{n+1} = au_n + b$ (dengan $a \neq 1$ ) mengiterasikan pemetaan afin $f(x) = ax + b$ pada garisnya, yang bagian linearnya $a$ menghindari nilai eigen $1$ : jadi ada satu titik tetap tunggal $\omega = \frac{b}{1-a}$ , lalu memusatkan ulang di sana (yakni kasus berdimensi satu proposisi di atas) mengubah $f$ menjadi perkalian dengan $a$ :

u_{n+1} - \omega = a\,(u_n - \omega) \qquad\Longrightarrow\qquad u_n = \omega + a^n(u_0 - \omega) .

Untuk $u_{n+1} = \frac{u_n}2 + 3$ : berlaku $\omega = 6$ dan $u_n = 6 + (u_0 - 6)2^{-n} \to 6$ . Adapun resep yang diajarkan bagi rekursi semacam itu pada Bab 7 — yakni “kurangkan titik tetapnya” — persis merupakan pemvektoran sebuah pemetaan afin di titik tetapnya; sedangkan kekonvergenannya untuk $\abs a < 1$ adalah gejala kontraksi yang diubah Bab 4 menjadi teorema titik tetap Banach. Jadi satu gagasan, tiga bab.

Contoh 17.22 (Menemukan pusat sebuah perputaran)

Misalkan $f(x, y) = (-y + 2,\ x)$ . Bagian linearnya adalah $\varphi(x, y) = (-y, x)$ : yakni perputaran bersudut $\frac\pi2$ , yang spektrumnya $\{\iu, -\iu\}$ menghindari $1$ . Menurut Proposisi 17.17 ada tepat satu titik tetap: sebab $x = -y + 2$ dan $y = x$ memberi $x = 1$ dan $y = 1$ , jadi $\Omega = (1, 1)$ , dan $f$ adalah perputaran berpusat $(1, 1)$ dan bersudut $\frac\pi2$ . Pelajaran umumnya: ketika $1 \notin \operatorname{Sp}\vec f$ , menggolongkan $f$ berharga satu sistem linear — sebab geometrinya seluruhnya ada pada bagian linearnya, dan aritmetikanya seluruhnya pada penentuan pusatnya.

Catatan 17.23 (Di mana bahasa afin dipakai berikutnya)

Barisentrum dan pemetaan afin adalah tata bahasa bab geometri berikutnya: sebab garis dan bidang singgung adalah objek afin (Bab 18 dan 19), sebuah penggantian peubah afin mengalikan luas dan volumenya dengan $\abs{\det \vec f}$ (Bab 20), dan nilai harapan adalah barisentrum dengan bobot yang diberikan sebuah hukum peluang, dan itulah sebabnya kecembungan mengatur ketaksamaan Jensen (Bab 22). Adapun pada jilid Tahun ke-3 kosakata kecembungan yang sama mengusung kajian norma $L^p$ dan ketaksamaan integral.

Catatan 17.24 (Pandangan ke depan di dalam jilid ini)

Dua benang meninggalkan bab ini. Benang afinnya: yakni garis singgung (Bab 18) dan bidang singgung (Bab 19) merupakan subruang afin yang dilekatkan pada objek nonlinear, dan penggolongan kuadrik pada bab permukaan berjalan atas persamaan pusat bab ini $A\Omega = -b$ . Adapun benang cembungnya lebih panjang: sebab kecembungan setengah bidang dan cakram menggerakkan teori Helly pada soal akhir pekan; kecembungan fungsi memberi ketaksamaan Jensen (Bab 22); dan teorema terakhir buku ini — yakni kriteria kepunahan bagi proses bercabang (Bab 23) — diputuskan oleh kedudukan sebuah kurva cembung terhadap diagonalnya, yakni gambaran yang termasuk bab ini sebanyak ia termasuk peluang. Barisentrumnya kembali di sana pula: sebab nilai harapan adalah barisentrum dengan bobot peluang.

17.4 Latihan

Latihan 17.1 ★

Pada $\R^3$ , apakah yang berikut merupakan subruang afin? Berikanlah arah dan dimensinya. $\{x + y + z = 1\}$ ; $\;\{x + y + z = 1,\ x - z = 3\}$ ; $\;\{x^2 + y^2 = 1\}$ ; dan himpunan penyelesaian $MX = B$ bagi sebuah sistem yang serasi.

Solusi

Solusi Latihan 17.1.

$\{x + y + z = 1\}$ : bidang afin, berarah bidang vektor $\{x + y + z = 0\}$ , dan berdimensi $2$ . Menambahkan $x - z = 3$ : garis afin (sebab dua persamaannya bebas), berarah $\{x + y + z = 0,\ x = z\} = \operatorname{Vect}\bigl((1, -2, 1)\bigr)$ dan berdimensi $1$ . $\{x^2 + y^2 = 1\}$ : sebuah silinder — yang tak stabil terhadap barisentrum (sebab titik tengah $(1,0,0)$ dan $(-1,0,0)$ adalah titik asalnya, di luar silindernya): jadi tak afin. Adapun sistem serasi $MX = B$ : yakni subruang afin $X_0 + \ker M$ berdimensi $\dim\ker M$ , seperti diingatkan pada Definisi 17.5.

Latihan 17.2 ★

Buktikan bahwa tiga titik berbeda $A, B, C$ pada sebuah ruang afin bersifat segaris bila dan hanya bila $C$ merupakan barisentrum $A$ dan $B$ , yakni bila vektor $\vect{AB}, \vect{AC}$ bergantungan. Lalu turunkan tata buku bobot bergaya Menelaus: bila $C = \operatorname{bar}(A, 1 - t; B, t)$ , tentukanlah letak $C$ untuk $t = \frac12$ , $t = 2$ , dan $t = -1$ .

Solusi

Solusi Latihan 17.2.

$C = \operatorname{bar}(A, 1-t; B, t)$ berarti $\vect{AC} = t\,\vect{AB}$ : jadi keberadaan $t$ semacam itu persis merupakan kebergantungan $\vect{AC}$ dengan $\vect{AB} \neq 0$ , yakni kesegarisan. Adapun letaknya: $t = \frac12$ : titik tengahnya; $t = 2$ : melewati $B$ , sejauh jarak $B$ dari titik itu (sebab $\vect{AC} = 2\vect{AB}$ ); dan $t = -1$ : cerminan $B$ terhadap $A$ .

Latihan 17.3 ★

Misalkan $f$ pemetaan afin $\R^2$ yang diberikan $f(X) = MX + C$ dengan $M = \frac12\begin{pmatrix} 1 & 1\\ 1 & 1\end{pmatrix}$ dan $C = (1, 0)^{\mathsf T}$ . Tentukan peta $f$ , titik tetapnya (bila ada), dan $f \circ f$ .

Solusi

Solusi Latihan 17.3.

Matriks $M$ adalah matriks proyeksi ke $\operatorname{Vect}(1,1)$ sepanjang $(1,-1)$ (periksa $M^2 = M$ ). Peta $f$ : yakni $\{MX + C\} = C + \operatorname{im} M$ , jadi garis afin lewat $(1,0)$ yang diarahkan $(1,1)$ . Titik tetapnya: $X = MX + C$ , yakni $(I - M)X = C$ ; tetapi $C = (1, 0)^{\mathsf T}$ dan $\operatorname{im}(I - M) = \operatorname{Vect}(1,-1)$ ; apakah $(1,0)$ ada di dalamnya? Sebab $(1, 0) = \alpha(1,-1)$ memaksa $\alpha = 1$ dan $0 = -1$ : jadi tidak. Sehingga tak ada titik tetap. Dan

f(f(X)) = M(MX + C) + C = MX + MC + C = f(X) + MC, \qquad MC = \tfrac12(1,1)^{\mathsf T} :

jadi $f\circ f$ adalah $f$ yang disusul penggeseran sepanjang garis petanya — sehingga $f$ merupakan “proyeksi geser”: yakni proyeksi ke garisnya yang dikomposisikan dengan sebuah geseran.

Latihan 17.4 ★★

(Keasosiatifan beraksi) Pada segitiga $ABC$ , misalkan $I, J, K$ membagi $BC$ , $CA$ , $AB$ dengan nisbah $\vect{BI} = \frac13\vect{BC}$ , $\vect{CJ} = \frac13\vect{CA}$ , dan $\vect{AK} = \frac13\vect{AB}$ . Nyatakanlah $I, J, K$ sebagai barisentrum lalu hitunglah barisentrum $(I,1;J,1;K,1)$ : apa yang kautemukan, dan mengapa itu dapat diramalkan?

Solusi

Solusi Latihan 17.4.

$I = \operatorname{bar}(B, 2; C, 1)$ (sebab $\vect{BI} = \frac13\vect{BC}$ menempatkan $I$ lebih dekat ke $B$ : jadi bobot $2$ pada $B$ dan $1$ pada $C$ — periksa: $\vect{BI} = \frac{1}{3}\vect{BC}$ ). Demikian pula $J = \operatorname{bar}(C, 2; A, 1)$ dan $K = \operatorname{bar}(A, 2; B, 1)$ . Menjumlahkan ketiga sistem terbobotnya, barisentrum $(I, 1; J, 1; K, 1)$ (yang masing-masing berbobot total $3$ , jadi gantilah $I$ dengan sistemnya, dan seterusnya) adalah

\operatorname{bar}\bigl(A, 1 + 2;\ B, 2 + 1;\ C, 1 + 2\bigr) = \operatorname{bar}(A, 1; B, 1; C, 1) = G ,

yakni titik berat $ABC$ : jadi segitiga $IJK$ punya titik berat yang sama — dan itu dapat diramalkan, karena konstruksinya memperlakukan $A, B, C$ secara siklik sedangkan titik beratnya adalah satu-satunya titik tetap kesimetrian siklik bobotnya.

Latihan 17.5 ★★

Buktikan bahwa pemetaan $f \colon \R^n \to \R^n$ yang memelihara titik tengah (yakni $f\bigl(\frac{A+B}{2}\bigr) = \frac{f(A) + f(B)}{2}$ ) dan bersifat kontinu pastilah afin. (Tunjukkan bahwa pemetaan vektornya $u \mapsto f(O + u) - f(O)$ bersifat aditif lewat titik tengahnya, lalu homogen atas $\Q$ , lalu homogen atas $\R$ berkat kekontinuannya — yakni strategi kepadatan yang sama seperti untuk persamaan fungsional Cauchy pada jilid Tahun ke-1; turunkanlah ulang langkah yang diperlukan di sini.)

Solusi

Solusi Latihan 17.5.

Tetapkan $g(u) = f(O + u) - f(O)$ (sambil bekerja di $\R^n$ yang divektorkan di $O$ ), dengan $g(0) = 0$ .

Keaditifannya: sebab $\frac{(O + u) + (O + v)}{2} = O + \frac{u + v}{2}$ , jadi pemeliharaan titik tengahnya memberi $g\bigl(\frac{u+v}{2}\bigr) = \frac{g(u) + g(v)}{2}$ ; lalu dengan $v = 0$ : $g(u/2) = g(u)/2$ ; sehingga bila digabung, $g(u + v) = 2g\bigl(\frac{u+v}{2}\bigr) = g(u) + g(v)$ .

Kehomogenan atas $\Q$ : keaditifannya memberi $g(nu) = ng(u)$ (untuk $n \in \N$ , secara induktif), lalu $g(-u) = -g(u)$ (dengan menjumlahkan), lalu $g(\frac pq u) = \frac pq g(u)$ (terapkan $q$ , lalu pakailah keinjektifan penskalaannya).

Kehomogenan atas $\R$ : untuk $t \in \R$ , ambillah bilangan rasional $t_n \to t$ : maka $g(t_nu) = t_ng(u)$ , lalu kekontinuan $g$ (yang diwarisi dari $f$ ) melewatkan limitnya: sehingga $g(tu) = tg(u)$ . Karena itu $g$ bersifat linear dan $f = f(O) + g$ : jadi afin.

Latihan 17.6 ★★

Golongkanlah pemetaan afin $f(x, y) = (y + 1,\; x - 1)$ pada bidang Euklides: yakni bagian linearnya, titik tetapnya, dan sifat geometrisnya (pencerminan? geser?). Hitunglah $f \circ f$ lalu simpulkan.

Solusi

Solusi Latihan 17.6.

Bagian linearnya $\varphi(x,y) = (y, x)$ : yakni pencerminan pada diagonal $y = x$ (yang ortogonal, berdeterminan $-1$ ). Titik tetapnya: $(x, y) = (y + 1, x - 1)$ menyusut menjadi satu persamaan tunggal $y = x - 1$ (sebab kedua komponennya setara): jadi setiap titik garis $y = x - 1$ bersifat tetap. Sehingga $f$ menetapkan garis itu titik demi titik: jadi $f$ adalah pencerminan pada sumbu itu (yakni isometri dengan sebuah garis titik tetap dan bagian linear berupa pencerminan). Secara konsisten, $f \circ f(x,y) = f(y+1, x-1) = (x - 1 + 1, y + 1 - 1) = (x, y)$ : jadi sebuah involusi, sebagaimana mestinya bagi sebuah pencerminan.

Latihan 17.7 ★★★

(Radon) Misalkan $A_1, \dots, A_{n+2}$ titik pada sebuah ruang afin berdimensi $n$ . Buktikan bahwa keduanya dapat dipecah menjadi dua kelompok yang saling lepas dan bungkus cembungnya berpotongan. (Seperti pada bukti Carathéodory, carilah bobot $\mu_i$ yang tak semuanya nol, dengan $\sum\mu_i = 0$ dan $\sum\mu_i\vect{OA_i} = 0$ ; lalu pisahkanlah bobot positif dan negatifnya kemudian normalkanlah kedua ruasnya.)

Solusi

Solusi Latihan 17.7.

Adapun $n + 1$ vektor $\vect{A_1A_i}$ (untuk $i \geq 2$ ) bergantungan pada dimensi $n$ : jadi ada $\mu_i$ yang tak semuanya nol dengan $\sum_{i\geq2} \mu_i\vect{A_1A_i} = 0$ ; lalu tetapkan $\mu_1 = -\sum_{i \geq 2}\mu_i$ , sehingga $\sum_{i}\mu_i = 0$ dan $\sum_i \mu_i\,\vect{OA_i} = 0$ untuk setiap $O$ , dengan tak semua $\mu_i$ nol. Pecahlah indeksnya: $P = \{i : \mu_i > 0\}$ dan $N = \{i : \mu_i < 0\}$ , yang keduanya tak kosong (sebab $\mu_i$ berjumlah nol dan tak semuanya nol). Dengan $s = \sum_{i\in P}\mu_i = -\sum_{i \in N}\mu_i > 0$ :

\operatorname{bar}\bigl(A_i, \tfrac{\mu_i}{s}\bigr)_{i \in P} = \operatorname{bar}\bigl(A_i, \tfrac{-\mu_i}{s}\bigr)_{i \in N},

(sebab kedua ruasnya sama dengan titik $X$ yang $\vect{OX} = \frac1s\sum_{i\in P}\mu_i\vect{OA_i}$ , menurut hubungannya): jadi sebuah titik bersama kedua bungkus cembungnya, dengan kelompok indeks yang saling lepas.

Latihan 17.8 ★★★

Misalkan $f$ endomorfisma afin $\R^n$ dengan $f \circ f = f$ . Buktikan bahwa $f$ adalah proyeksi afin ke subruang afin $\operatorname{Fix}(f) = \operatorname{im} f$ sepanjang arah $\ker\vec f$ , dan bahwa sebaliknya semua proyeksi semacam itu bersifat idempoten. (Tunjukkanlah lebih dulu bahwa $\operatorname{im} f$ terdiri atas titik tetap.)

Solusi

Solusi Latihan 17.8.

Peta = titik tetapnya: sebab untuk $Y = f(X)$ berlaku $f(Y) = f(f(X)) = f(X) = Y$ : jadi setiap titik petanya bersifat tetap; dan sebaliknya titik tetapnya adalah peta. Karena itu $\mathcal{F} = \operatorname{im} f = \operatorname{Fix}(f)$ tak kosong, dan ia sebuah subruang afin (sebab peta sebuah pemetaan afin), dengan arah $\operatorname{im}\vec f$ .

Struktur proyeksinya: $\vec f$ bersifat idempoten (sebab $\vec{f\circ f} = \vec f^{\,2} = \vec f$ ), jadi $E = \operatorname{im}\vec f \oplus \ker \vec f$ (Contoh 3.18). Untuk sembarang titik $X$ , tinjaulah vektor $\vect{f(X)\,X}$ ; lalu dengan menerapkan $\vec f$ :

\vec f\bigl(\vect{f(X)\,X}\bigr) = \vect{f(f(X))\,f(X)} = 0 \qquad (f \circ f = f),

jadi $\vect{f(X)\,X} \in \ker\vec f$ . Karena itu $X = f(X) + \vect{f(X)X}$ memamerkan $X$ sebagai titik $\mathcal{F}$ yang digeser sebuah vektor $\ker\vec f$ : sehingga $f$ persis merupakan proyeksi ke $\mathcal{F}$ sepanjang $\ker\vec f$ . Sebaliknya proyeksi semacam itu jelas memenuhi $f \circ f = f$ .

Latihan 17.9 ★

Misalkan $G = \operatorname{bar}(A, 1;\ B, 2;\ C, 3)$ pada segitiga $ABC$ . Dengan memakai keasosiatifannya, tunjukkanlah bahwa garis $AG$ memotong $BC$ di $M = \operatorname{bar}(B, 2;\ C, 3)$ , lalu tentukan letak $G$ pada ruas $\intcc AM$ ; tentukan pula letak perpotongan $BG$ dengan $CA$ .

Solusi

Solusi Latihan 17.9.

Misalkan $M = \operatorname{bar}(B, 2;\ C, 3)$ , yang berbobot total $5$ . Keasosiatifannya memberi $G = \operatorname{bar}(A, 1;\ M, 5)$ , jadi $\vect{AG} = \frac56\,\vect{AM}$ : sehingga $G$ terletak pada ruas $\intcc AM$ pada lima perenamnya dari $A$ . Karena $A \notin (BC)$ , garis $(AG) = (AM)$ memotong $(BC)$ di titik tunggal $M$ , dengan $\vect{BM} = \frac35\,\vect{BC}$ . Demikian pula, dengan $N = \operatorname{bar}(C, 3;\ A, 1)$ (yang berbobot total $4$ dan $\vect{CN} = \frac14\,\vect{CA}$ ), keasosiatifannya memberi $G = \operatorname{bar}(B, 2;\ N, 4)$ : jadi garis $(BG)$ memotong $(CA)$ di $N$ , dan $\vect{BG} = \frac46\,\vect{BN} = \frac23\,\vect{BN}$ .

Latihan 17.10 ★★

Untuk $\lambda \neq 0$ , homoteti $h_{\Omega, \lambda}$ adalah pemetaan afin yang menetapkan $\Omega$ dengan bagian linear $\lambda\,\mathrm{id}$ . Buktikan bahwa komposisi $h_{\Omega', \mu} \circ h_{\Omega, \lambda}$ merupakan homoteti bernisbah $\lambda\mu$ ketika $\lambda\mu \neq 1$ , dan sebuah penggeseran ketika $\lambda\mu = 1$ ; lalu pada kasus $\lambda = \mu = -1$ (yakni dua pencerminan titik), hitunglah vektor geserannya.

Solusi

Solusi Latihan 17.10.

Vektorkanlah di sebuah titik asal $O$ lalu tulislah titiknya sebagai vektor: $h_{\Omega, \lambda}(x) = \omega + \lambda(x - \omega)$ dengan $\omega = \vect{O\Omega}$ . Komposisi $g = h_{\Omega', \mu} \circ h_{\Omega, \lambda}$ bersifat afin dengan bagian linear $\mu\lambda\,\mathrm{id}$ . Bila $\lambda\mu \neq 1$ : maka $1 \notin \operatorname{Sp}(\lambda\mu\,\mathrm{id})$ , jadi Proposisi 17.17 menghasilkan titik tetap tunggal $\Omega''$ dan, setelah divektorkan di sana, $g = \lambda\mu\,\mathrm{id}$ : yakni homoteti $h_{\Omega'', \lambda\mu}$ . Sedangkan bila $\lambda\mu = 1$ bagian linearnya adalah identitasnya, jadi $g$ merupakan penggeseran; dan setelah diuraikan,

g(x) = \omega' + \mu\bigl(\omega + \lambda(x - \omega) - \omega'\bigr) = x + (1 - \mu)\,\omega' + \mu(1 - \lambda)\,\omega .

Untuk $\lambda = \mu = -1$ (yakni pencerminan titik) vektornya adalah $2\omega' - 2\omega = 2\,\vect{\Omega\Omega'}$ : jadi komposisi pencerminan titik pada $\Omega$ lalu $\Omega'$ adalah penggeseran sebesar $2\,\vect{\Omega\Omega'}$ .

Latihan 17.11 ★★

(Menelaus) Pada segitiga $ABC$ , misalkan $A' \in (BC)$ , $B' \in (CA)$ , $C' \in (AB)$ , yang semuanya berbeda dari titik sudutnya, lalu definisikan $\alpha, \beta, \gamma$ lewat $\vect{A'B} = \alpha\,\vect{A'C}$ , $\vect{B'C} = \beta\,\vect{B'A}$ , dan $\vect{C'A} = \gamma\,\vect{C'B}$ . Buktikan bahwa $A', B', C'$ bersifat segaris bila dan hanya bila $\alpha\beta\gamma = 1$ . (Tulislah tiap titiknya sebagai barisentrum dua titik sudut; lalu tunjukkan bahwa tiga titik segaris bila dan hanya bila baris koordinat barisentriknya terhadap $(A, B, C)$ membentuk matriks $3 \times 3$ yang singular.)

Solusi

Solusi Latihan 17.11.

Syarat $\vect{A'B} = \alpha\,\vect{A'C}$ persis mengatakan $1\cdot \vect{A'B} - \alpha\,\vect{A'C} = 0$ , yakni $A' = \operatorname{bar}(B, 1;\ C, -\alpha)$ (yang berbobot total $1 - \alpha \neq 0$ karena $B \neq C$ ); demikian pula $B' = \operatorname{bar}(C, 1;\ A, -\beta)$ dan $C' = \operatorname{bar}(A, 1;\ B, -\gamma)$ .

Kriteria kesegarisannya. Berikanlah tiap titik $P$ baris barisentrik ternormalkannya $p = (p_A, p_B, p_C)$ dengan $p_A + p_B + p_C = 1$ , terhadap $(A, B, C)$ . Bila $\sum_i c_i p_i = 0$ dengan $(c_1, c_2, c_3) \neq 0$ untuk tiga titik $P_1, P_2, P_3$ , maka menjumlahkan entrinya memberi $\sum c_i = 0$ , dan $\sum_i c_i \vect{OP_i} = \sum_j \bigl(\sum_i c_ip_{ij}\bigr)\vect{OV_j} = 0$ : jadi $P_i$ bergantungan secara afin, yakni segaris. Sebaliknya sebuah kebergantungan afin $(t_i)$ memberi $w = \sum t_ip_i$ yang entrinya berjumlah $0$ dan $\sum_j w_j\vect{OV_j} = 0$ ; lalu dengan menguraikannya dari $A$ : $w_B \vect{AB} + w_C\vect{AC} = 0$ , jadi $w = 0$ berkat kebebasan afin $(A, B, C)$ : sehingga barisnya bergantungan secara linear. Karena itu kesegarisannya menyusut menjadi lenyapnya determinan $3 \times 3$ , dan menskalakan barisnya dengan faktor tak nol $1 - \alpha$ , $1 - \beta$ , $1 - \gamma$ tak mengubah apa pun:

\det\begin{pmatrix} 0 & 1 & -\alpha\\ -\beta & 0 & 1\\ 1 & -\gamma & 0\end{pmatrix} = 1 - \alpha\beta\gamma .

Karena itu $A', B', C'$ segaris bila dan hanya bila $\alpha\beta\gamma = 1$ : itulah teorema Menelaus.

Latihan 17.12 ★★★

Buktikan bahwa bungkus cembung himpunan bagian kompak $K$ milik $\R^n$ bersifat kompak. (Menurut Teorema 17.14, $\operatorname{conv}(K)$ adalah peta sebuah himpunan kompak oleh pemetaan yang kontinu.) Tunjukkanlah lewat sebuah contoh di $\R^2$ bahwa bungkus cembung himpunan yang tertutup tak harus tertutup.

Solusi

Solusi Latihan 17.12.

Misalkan $\Delta = \{\lambda \in \R^{n+1} : \lambda_i \geq 0,\ \sum\lambda_i = 1\}$ : yang tertutup dan terbatas di $\R^{n+1}$ , sehingga kompak, sedangkan $K^{n+1}$ kompak sebagai hasil kali berhingga. Pemetaan

\Phi \colon \Delta \times K^{n+1} \to \R^n, \qquad \Phi(\lambda, x_0, \dots, x_n) = \sum_{i=0}^n \lambda_i x_i

bersifat kontinu, dan Teorema 17.14 mengatakan persis bahwa $\operatorname{conv}(K) = \Phi(\Delta \times K^{n+1})$ : yakni peta kontinu sebuah himpunan kompak (Teorema 4.16), sehingga kompak.

Untuk himpunan yang tertutup: ambillah $S = (\R \times \{0\}) \cup \{(0, 1)\}$ , yang tertutup di $\R^2$ . Sebuah kombinasi cembung yang menaruh bobot $t$ pada $(0,1)$ dan $1 - t$ pada titik sumbunya berkoordinat kedua $t$ , jadi

\operatorname{conv}(S) = \bigl(\R \times \intco01\bigr) \cup \{(0,1)\}

(sebab untuk $0 \leq t < 1$ berlaku $(x, t) = t\,(0,1) + (1-t)\,\bigl(\tfrac x{1-t}, 0\bigr)$ ). Adapun titik $(1, 1) = \lim_{t \to 1}(1, t)$ bersifat lekat tetapi tak ada di bungkusnya: jadi tak tertutup.

17.5 Soal: dari Radon ke Helly, titik penyeimbang dan teorema Jung

Kedua tipe Radon bagi empat titik bidang pada posisi umum: yakni satu titik di dalam segitiga yang lain (dengan pemartisian \A_4\ \A_1, A_2, A_3\), atau posisi cembung, tempat titik Radonnya (jingga) adalah perpotongan kedua diagonalnya. — Kedua tipe Radon bagi empat titik bidang pada posisi umum: yakni satu titik di dalam segitiga yang lain (dengan pemartisian $\{A_4\} \mid \{A_1, A_2, A_3\}$ ), atau posisi cembung, tempat titik Radonnya (jingga) adalah perpotongan kedua diagonalnya.

Soal 17.1

Soal akhir pekan — teorema Helly dan dua panennya

Lema Radon (Latihan 17.7) mengatakan bahwa $n + 2$ titik pada ruang afin berdimensi $n$ selalu terpecah menjadi dua kelompok yang bungkus cembungnya berpotongan. Soal ini mengubah satu fakta aljabar linear itu menjadi rantai teorema geometri kombinatorik: yakni teorema perpotongan Helly, teorema titik penyeimbang (yakni sebuah median dua dimensi), dan teorema peliputan Jung. Di sepanjang soal ini, bidangnya adalah $\R^2$ dengan struktur Euklides biasanya, dan $\det$ adalah determinan dalam basis kanoniknya.

Bagian I — Koordinat barisentrik. Titik $A_0, \dots, A_k$ disebut bebas secara afin apabila vektor $\vect{A_0A_1}, \dots, \vect{A_0A_k}$ bebas secara linear.

Tunjukkan bahwa kebebasan afinnya tak bergantung pada pemilihan titik pangkalnya $A_0$ , dan bahwa ia setara dengan: setiap kali dua keluarga bobot, yang masing-masing berjumlah $1$ , mendefinisikan barisentrum $(A_0, \dots, A_k)$ yang sama, maka bobotnya berimpit.
Misalkan $(A, B, C)$ bebas secara afin pada bidangnya. Tunjukkan bahwa setiap titik $M$ menerima satu tripel tunggal $(\alpha, \beta, \gamma)$ dengan $\alpha + \beta + \gamma = 1$ dan $M = \operatorname{bar}(A, \alpha; B, \beta; C, \gamma)$ — yakni koordinat barisentriknya.
Buktikan rumus determinannya

$\alpha = \frac{\det(\vect{MB}, \vect{MC})}{\det(\vect{AB}, \vect{AC})}, \qquad \beta = \frac{\det(\vect{MC}, \vect{MA})}{\det(\vect{AB}, \vect{AC})}, \qquad \gamma = \frac{\det(\vect{MA}, \vect{MB})}{\det(\vect{AB}, \vect{AC})} :$

jadi koordinat barisentriknya adalah nisbah luas bertanda.
Adapun garis $BC$ , $CA$ , $AB$ merupakan garis koordinat $\{\alpha = 0\}$ , $\{\beta = 0\}$ , $\{\gamma = 0\}$ . Tunjukkan bahwa $M$ terletak di segitiga tertutup $\operatorname{conv}\{A, B, C\}$ bila dan hanya bila $\alpha, \beta, \gamma \geq 0$ , dan bahwa ketiga garisnya memotong bidangnya menjadi tepat tujuh daerah, yang digolongkan tanda $(\alpha, \beta, \gamma)$ (dengan pola tanda $(-, -, -)$ yang mustahil).
Misalkan $u \colon \R^2 \to \R$ pemetaan afin (yakni sebuah bentuk afin). Tunjukkan $u(M) = \alpha\,u(A) + \beta\,u(B) + \gamma\,u(C)$ , bahwa himpunan aras sebuah bentuk afin yang tak tetap berupa garis, bahwa setiap garis muncul demikian, dan bahwa setengah bidang tertutup $\{u \geq c\}$ bersifat cembung.

Bagian II — Pemartisian Radon, diperhalus. Sebuah keluarga berisi $n + 2$ titik $\R^n$ disebut pada posisi umum apabila setiap $n + 1$ di antaranya bebas secara afin. Adapun sebuah kebergantungan afin bagi $(A_1, \dots, A_{n+2})$ adalah keluarga $(\mu_i)$ dengan $\sum_i \mu_i = 0$ dan $\sum_i \mu_i\,\vect{OA_i} = 0$ untuk satu (sehingga setiap) titik asal $O$ .

Hitunglah sebuah kebergantungan afin tak nol bagi keempat titik $A_1 = (0,0)$ , $A_2 = (3,0)$ , $A_3 = (0,3)$ , $A_4 = (1,1)$ ; lalu berikan pemartisian Radonnya beserta titik Radonnya.
Tunjukkan bahwa untuk titik pada posisi umum, ruang vektor kebergantungan afinnya berdimensi tepat $1$ , dan bahwa kebergantungan tak nol tak punya koefisien yang lenyap.
Turunkan bahwa pemartisian Radon bagi $n + 2$ titik pada posisi umum bersifat tunggal (hingga pertukaran kedua bloknya), dengan tiap bloknya berupa himpunan indeks tempat $\mu_i$ bertanda tetap.
Untuk empat titik bidang pada posisi umum, tunjukkanlah dikotominya: entah pemartisiannya bertipe $(1, 3)$ — yakni satu titik di dalam segitiga ketiga lainnya — atau bertipe $(2, 2)$ : yakni keempat titiknya berada pada posisi cembung dan ruas yang menghubungkan kedua pasangannya (yakni diagonalnya) berpotongan, di titik Radonnya.
Kerjakanlah pertanyaan 6 untuk bujur sangkar satuan $(0,0)$ , $(1,0)$ , $(1,1)$ , $(0,1)$ : yakni kebergantungannya, pemartisiannya, dan titik Radonnya.

Bagian III — Teorema Helly pada bidang.

Misalkan $C_1, C_2, C_3, C_4$ himpunan bagian cembung $\R^2$ , yang setiap tiganya punya titik bersama. Pilihlah $x_i \in \bigcap_{j \neq i} C_j$ lalu terapkan lema Radon pada $x_1, \dots, x_4$ : tunjukkanlah bahwa titik Radonnya termasuk keempat himpunannya. (Sebab untuk tiap $k$ , blok yang tak memuat $x_k$ terdiri atas titik $C_k$ .)
(Helly) Misalkan $C_1, \dots, C_m$ (dengan $m \geq 3$ ) himpunan bagian cembung $\R^2$ , yang setiap tiganya berpotongan. Buktikan $\bigcap_{i=1}^m C_i \neq \emptyset$ , secara induktif atas $m$ : gantilah $C_{m-1}$ dan $C_m$ dengan $C_{m-1} \cap C_m$ lalu periksalah hipotesisnya bagi keluarga barunya lewat pertanyaan 11.
Tiga contoh tandingan, satu bagi tiap hipotesisnya: (a) ketiga rusuk tertutup sebuah segitiga berpotongan berpasangan tetapi tak punya titik bersama (jadi $3$ tak dapat diturunkan menjadi $2$ ); (b) keempat himpunan $S_i = \{x_1, \dots, x_4\} \setminus \{x_i\}$ , bagi empat titik pada posisi umum, memenuhi hipotesis perpotongan bertiganya tetapi tak memenuhi kesimpulannya (jadi kecembungannya berperan); (c) setengah bidang tertutup $H_k = \intco{k}{+\infty} \times \R$ dengan $k \in \N$ berpotongan berpasangan dan bertiga tetapi $\bigcap_k H_k = \emptyset$ (jadi keluarga tak hingga menuntut kekompakan).
(Helly kompak) Misalkan $(K_i)_{i \in I}$ sembarang keluarga himpunan bagian kompak cembung $\R^2$ , yang setiap tiganya berpotongan. Dengan memakai pertanyaan 12 dan sifat Borel–Lebesgue (Teorema 4.20), tunjukkanlah $\bigcap_{i \in I} K_i \neq \emptyset$ .
(Panen pertama) Misalkan $S$ himpunan berhingga titik pada bidang dan $r > 0$ . Tunjukkan: bahwa bila setiap tiga titik $S$ terletak pada suatu cakram tertutup berjari-jari $r$ , maka $S$ terletak pada satu cakram tertutup berjari-jari $r$ . (Terapkan Helly pada cakram $\overline D(p, r)$ dengan $p \in S$ .)

Bagian IV — Teorema titik penyeimbang. Sebuah titik penyeimbang bagi himpunan berhingga $S$ berisi $n$ titik pada bidang adalah titik $c$ (yang tak harus di $S$ ) sedemikian sehingga setiap setengah bidang tertutup yang memuat $c$ memuat sekurangnya $n/3$ titik $S$ .

(Dimensi $1$ ) Untuk bilangan real $x_1 \leq \dots \leq x_n$ , tunjukkan bahwa mediannya $c = x_{\lceil n/2 \rceil}$ memenuhi: bahwa setiap setengah garis tertutup yang memuat $c$ memuat sekurangnya $n/2$ di antara $x_i$ .
(Lema pencacahan) Bila $A, B, C$ himpunan bagian $S$ dengan $\abs A, \abs B, \abs C > \tfrac{2n}3$ , tunjukkanlah $A \cap B \cap C \neq \emptyset$ .
Misalkan $m = \floor{2n/3} + 1$ dan misalkan $\mathcal F$ keluarga (yang berhingga) berisi bungkus cembung $\operatorname{conv}(T)$ dengan $T \subseteq S$ dan $\abs T = m$ . Tunjukkan bahwa setiap tiga anggota $\mathcal F$ punya titik bersama, lalu turunkan dari Helly sebuah titik $c$ yang bersama bagi semuanya.
Buktikan bahwa $c$ ini merupakan titik penyeimbang $S$ : itulah teorema titik penyeimbang. (Sebab bila sebuah setengah bidang tertutup lewat $c$ memuat kurang dari $n/3$ titik, maka komplemen terbukanya akan memuat sebuah himpunan $T$ berisi $m$ titik, sehingga $\operatorname{conv}(T)$ akan menghindari $c$ .)
Ketajamannya: misalkan $n = 3k$ lalu tempatkanlah $k$ titik pada masing-masing tiga cakram berjari-jari kecil $\varepsilon$ yang berpusat di titik sudut sebuah segitiga besar. Tunjukkan bahwa untuk setiap titik $c$ pada bidangnya ada setengah bidang tertutup yang memuat $c$ dan memuat paling banyak $n/3$ titik $S$ , jadi konstanta $1/3$ tak dapat diperbaiki. (Sebab di antara ketiga arah dari $c$ ke pusat cakramnya, dua di antaranya bersudut paling banyak $2\pi/3$ .)

Bagian V — Teorema Jung dan rangkuman.

(Lema segitiga) Misalkan $P, Q, R$ tiga titik dengan jarak berpasangan $\leq 1$ . Tunjukkan bahwa ketiganya terletak pada cakram tertutup berjari-jari $1/\sqrt3$ . (Bila suatu sudutnya $\geq \pi/2$ , ambillah cakram bergaris tengah sisi terpanjangnya, dengan memakai rumus garis berat $\norm{RM}^2 = \tfrac12\norm{RP}^2 + \tfrac12\norm{RQ}^2 - \tfrac14\norm{PQ}^2$ ; sedangkan bila segitiganya lancip, batasilah jari-jari lingkar luarnya $a/(2\sin \widehat A)$ lewat sudut terbesarnya, yang terletak di $\intco{\pi/3}{\pi/2}$ .)
(Jung) Turunkan: bahwa setiap himpunan bagian kompak bidang yang berdiameter $\leq 1$ termuat pada sebuah cakram tertutup berjari-jari $1/\sqrt3$ .
Ketajamannya: untuk segitiga sama sisi $A_1A_2A_3$ bersisi $1$ dengan titik berat $G$ , buktikanlah kesamaan Leibniz $\sum_i \norm{\vect{OA_i}}^2 = 3\norm{\vect{OG}}^2 + \sum_i \norm{\vect{GA_i}}^2$ untuk setiap titik $O$ , lalu simpulkan bahwa sembarang cakram yang memuat ketiga titik sudutnya berjari-jari $\geq 1/\sqrt3$ , dengan kesamaan hanya bagi cakram lingkar luarnya.
(Helly di $\R^n$ ) Nyatakan lalu buktikan teorema Helly di $\R^n$ : bahwa bila berhingga banyak himpunan cembung sedemikian sehingga setiap $n + 1$ di antaranya berpotongan, maka semuanya berpotongan. (Lema Radon Latihan 17.7 menangani $n + 2$ himpunan; lalu berinduksilah seperti pada pertanyaan 12.)
Rangkuman. Rangkailah rantainya

$\text{kebergantungan afin} \Rightarrow \text{Radon} \Rightarrow \text{Helly} \Rightarrow \text{titik penyeimbang dan Jung},$

dengan menunjukkan dalam satu kalimat masing-masing: di mana aljabar linear masuk, di mana tanda bobotnya masuk, di mana kecembungannya masuk, dan langkah tunggal mana yang memakai dimensi bidangnya. Lalu konstanta $3$ (pada Helly), $1/3$ (titik penyeimbang) dan $1/\sqrt3$ (Jung) menjadi apa di $\R^n$ ? (Nyatakan saja tanpa bukti.)

Solusi

Solusi Soal 17.1.

1. Pangkalkan ulang di $A_j$ : sebab untuk $i \neq j$ , $\vect{A_jA_i} = \vect{A_0A_i} - \vect{A_0A_j}$ . Bila $\sum_{i \neq j} c_i\vect{A_jA_i} = 0$ , maka menguraikannya memberi $\sum_{i \notin \{0, j\}} c_i\,\vect{A_0A_i} - \bigl(\sum_{i\neq j} c_i\bigr)\vect{A_0A_j} = 0$ ; jadi kebebasan $\vect{A_0A_i}$ memaksa $c_i = 0$ untuk $i \notin \{0, j\}$ , lalu $c_0 = 0$ : sehingga kebebasan di $A_j$ . Adapun kesetaraannya: dua keluarga bobot $(\lambda_i)$ dan $(\lambda_i')$ yang berjumlah $1$ dengan barisentrum yang sama memberi, dengan $\nu = \lambda - \lambda'$ : $\sum\nu_i = 0$ dan (dengan titik asal $A_0$ ) $\sum_{i \geq 1}\nu_i\,\vect{A_0A_i} = 0$ , jadi $\nu = 0$ di bawah kebebasannya. Sebaliknya sebuah hubungan tak trivial $\sum_{i\geq1}\mu_i \vect{A_0A_i} = 0$ , yang dilengkapi $\mu_0 = -\sum_{i\geq1} \mu_i$ , memungkinkan kita menambahkan $t(\mu_i)$ pada sembarang keluarga bobot tanpa menggerakkan barisentrumnya: jadi ketaktunggalan.

2. Pasangan $(\vect{AB}, \vect{AC})$ adalah basis $\R^2$ : tulislah $\vect{AM} = \beta\,\vect{AB} + \gamma\,\vect{AC}$ (secara tunggal) lalu tetapkan $\alpha = 1 - \beta - \gamma$ ; sebab syarat barisentrumnya di titik asal $A$ berbunyi persis $\vect{AM} = \beta\,\vect{AB} + \gamma\,\vect{AC}$ . Adapun ketunggalannya adalah pertanyaan 1.

3. Dari $\alpha\vect{MA} + \beta\vect{MB} + \gamma\vect{MC} = 0$ dan Chasles, berlaku $\vect{MA} = -\beta\,\vect{AB} - \gamma\,\vect{AC}$ . Dengan $D = \det(\vect{AB}, \vect{AC})$ :

\begin{align*} \det(\vect{MB}, \vect{MC}) &= \det(\vect{MA} + \vect{AB},\ \vect{MA} + \vect{AC})\\ &= \det(\vect{MA}, \vect{AC}) + \det(\vect{AB}, \vect{MA}) + D = -\beta D - \gamma D + D = \alpha D, \end{align*}

dengan memakai kebilinearannya beserta $\det(\vect{MA}, \vect{AC}) = -\beta D$ dan $\det(\vect{AB}, \vect{MA}) = -\gamma D$ . Adapun kedua rumus lainnya menyusul lewat perhitungan yang sama dengan peran yang dipermutasikan secara siklik.

4. Menurut definisinya, $\operatorname{conv}\{A, B, C\}$ adalah himpunan barisentrum berbobot taknegatif; jadi setelah menormalkan bobotnya agar berjumlah $1$ lalu memanggil ketunggalannya (pertanyaan 2), $M \in \operatorname{conv}\{A,B,C\}$ bila dan hanya bila $\alpha, \beta, \gamma \geq 0$ . Tiap koordinatnya merupakan fungsi afin atas $M$ (lewat pertanyaan 3: yakni determinan $2\times2$ yang satu kolomnya afin dalam $M$ ), jadi tiap syarat tanda terbukanya mendefinisikan setengah bidang yang terbuka. Adapun pola $(-,-,-)$ bertentangan dengan $\alpha + \beta + \gamma = 1$ ; sedangkan ketujuh pola sisanya terwujud: skalakanlah sebuah tripel yang menghormati tandanya dengan sekurangnya satu entri $+$ agar jumlahnya (yang positif) menjadi $1$ — misalnya $(-1, 1, 1)$ , $(3, -1, -1)$ , $(\frac13, \frac13, \frac13)$ , beserta permutasinya.

5. Sebuah pemetaan afin memelihara barisentrum (Definisi 17.5), jadi $u(M) = \alpha u(A) + \beta u(B) + \gamma u(C)$ . Dengan menulis $u(x, y) = ax + by + c$ dan $(a, b) \neq (0,0)$ : maka $\{u = c'\}$ merupakan garis, dan setiap garis $ax + by = c'$ merupakan himpunan aras semacam itu. Bila $u(M), u(N) \geq c$ dan $t \in \intcc01$ , maka $u\bigl(\operatorname{bar}(M, 1-t; N, t)\bigr) = (1-t)u(M) + tu(N) \geq c$ : jadi setengah bidangnya cembung.

6. Syarat $\sum\mu_i = 0$ , $3\mu_2 + \mu_4 = 0$ , $3\mu_3 + \mu_4 = 0$ memberi (dengan mengambil $\mu_4 = 3$ ) kebergantungan $(\mu_1, \mu_2, \mu_3, \mu_4) = (-1, -1, -1, 3)$ . Tandanya terpecah sebagai $\{A_4\} \mid \{A_1, A_2, A_3\}$ , lalu setelah tiap sisinya dinormalkan dengan $3$ :

A_4 = \operatorname{bar}\bigl(A_1, \tfrac13;\ A_2, \tfrac13;\ A_3, \tfrac13\bigr) = (1,1),

yakni titik berat segitiganya: jadi titik Radonnya adalah $A_4$ itu sendiri, yang memang terletak di dalam segitiga $A_1A_2A_3$ .

7. Pemetaan linear $\Phi \colon \R^{n+2} \to \R \times \R^n$ dengan $\mu \mapsto (\sum\mu_i,\ \sum\mu_i\vect{OA_i})$ berrank $\leq n + 1$ , jadi $\dim\ker \Phi \geq 1$ . Andaikan dua kebergantungan bebas $\mu, \mu'$ ada, maka kombinasi yang sesuai $\nu = \mu'_{n+2}\mu - \mu_{n+2}\mu'$ (atau $\mu$ itu sendiri bila kedua koefisien terakhirnya lenyap) akan menjadi kebergantungan tak nol dengan $\nu_{n+2} = 0$ ; lalu dengan membatasinya ke $A_1, \dots, A_{n+1}$ dan memangkalkan ulang di $A_1$ , ada $\nu_i \neq 0$ dengan $i \geq 2$ (sebab satu bobot tak nol saja tak dapat berjumlah nol), yang memberi hubungan tak trivial $\sum_{i\geq2}\nu_i\vect{A_1A_i} = 0$ : jadi $n+1$ titiknya akan bergantungan secara afin, yang melawan posisi umumnya. Karena itu $\dim\ker \Phi = 1$ . Adapun hujah pembatasan yang sama menunjukkan bahwa kebergantungan tak nol tak punya koefisien yang lenyap.

8. Misalkan $\mu \neq 0$ sebuah kebergantungan, dengan $P = \{i : \mu_i > 0\}$ dan $N = \{i : \mu_i < 0\}$ : keduanya tak kosong (sebab $\sum\mu_i = 0$ dan $\mu \neq 0$ ) sekaligus menyeluruh (sebab tak ada koefisien yang nol). Konstruksi Radon (Latihan 17.7) menghasilkan titik bungkus bersamanya persis dari pemartisian ini. Karena kebergantungannya tunggal hingga sebuah skalar tak nol (pertanyaan 7), pasangan tak terurut $\{P, N\}$ — sehingga pemartisian Radonnya — bersifat tunggal.

9. Bloknya tak kosong, jadi tipenya $(1,3)$ atau $(2,2)$ . Tipe $(1,3)$ dengan blok $\{j\}$ : titik Radonnya terletak di $\operatorname{conv}\{A_j\} = \{A_j\}$ , jadi $A_j \in \operatorname{conv}$ ketiga lainnya; dan ia tak dapat terletak pada sebuah rusuk (sebab tiga titiknya akan segaris, yang melawan posisi umumnya), jadi $A_j$ berada di dalam segitiganya. Tipe $(2,2)$ dengan blok $\{i,j\} \mid \{k,l\}$ : titik Radonnya $z$ terletak di $\intcc{A_i}{A_j} \cap \intcc{A_k}{A_l}$ , dan $z$ bukan titik ujungnya (sebab itu akan menyegariskan tiga titik): jadi kedua ruasnya bersilangan di sebuah titik dalam. Lebih jauh tak ada titik yang terletak di bungkus yang lain: sebab pemuatan semacam itu $A_l = \operatorname{bar}(A_i, \lambda_i)_{i \neq l}$ dengan $\lambda_i \geq 0$ merupakan kebergantungan afin berpola tanda $(+,+,+,-)$ , yang berkat ketunggalannya (pertanyaan 8) akan membuat pemartisiannya $(1,3)$ . Jadi pada kasus $(2,2)$ keempat titiknya berada pada posisi cembung dan ruas yang bersilangan itu adalah diagonalnya.

10. Persamaan $\mu_2 + \mu_3 = 0$ , $\mu_3 + \mu_4 = 0$ , $\sum\mu_i = 0$ memberi kebergantungan $(1, -1, 1, -1)$ : jadi pemartisian $\{(0,0), (1,1)\} \mid \{(1,0), (0,1)\}$ , dan

\operatorname{bar}\bigl((0,0), \tfrac12;\ (1,1), \tfrac12\bigr) = \bigl(\tfrac12, \tfrac12\bigr) = \operatorname{bar}\bigl((1,0), \tfrac12;\ (0,1), \tfrac12\bigr) :

titik Radonnya adalah pusat bujur sangkarnya, tempat kedua diagonalnya bersilangan — yakni tipe $(2,2)$ , seperti diramalkan gambarnya.

11. Radon yang diterapkan pada $x_1, \dots, x_4$ memberi blok $I \mid J$ beserta titik $z \in \operatorname{conv}\{x_i : i \in I\} \cap \operatorname{conv}\{x_j : j \in J\}$ . Tetapkan $k \in \{1, \dots, 4\}$ , katakanlah $k \in I$ . Setiap $j \in J$ memenuhi $j \neq k$ , jadi $x_j \in C_k$ berkat pemilihan $x_j \in \bigcap_{l \neq j}C_l$ ; lalu karena $C_k$ cembung, $z \in \operatorname{conv}\{x_j : j \in J\} \subseteq C_k$ . Karena $k$ sembarang, maka $z \in C_1 \cap C_2 \cap C_3 \cap C_4$ .

12. Secara induktif atas $m$ . Untuk $m = 3$ hipotesisnya adalah kesimpulannya; sedangkan $m = 4$ adalah pertanyaan 11. Misalkan $m \geq 4$ , lalu andaikan pernyataannya bagi $m$ himpunan, dan ambillah $C_1, \dots, C_{m+1}$ dengan sifat perpotongan bertiganya. Tetapkan $C_m' = C_m \cap C_{m+1}$ , yang cembung. Keluarga $C_1, \dots, C_{m-1}, C_m'$ punya $m$ anggota; adapun tripel yang menghindari $C_m'$ berpotongan berkat hipotesisnya, sedangkan tripel $\{C_i, C_j, C_m'\}$ punya perpotongan $C_i \cap C_j \cap C_m \cap C_{m+1}$ , yang tak kosong berkat pertanyaan 11 yang diterapkan pada $C_i, C_j, C_m, C_{m+1}$ (sebab setiap tiga di antaranya bertemu, menurut hipotesisnya). Kini hipotesis induksinya menghasilkan sebuah titik bersama keluarga barunya, yakni bagi semua $m+1$ himpunannya.

13. (a) Rusuk tertutup $\intcc PQ$ , $\intcc QR$ , $\intcc RP$ sebuah segitiga tak merosot: setiap duanya berbagi sebuah titik sudut, tetapi titik bersama ketiganya akan terletak di $\intcc PQ \cap \intcc RP = \{P\}$ sekaligus di $\intcc QR$ , yang justru mengecualikan $P$ . (b) Setiap tiga di antara himpunan $S_i = \{x_1, \dots, x_4\} \setminus \{x_i\}$ menghilangkan tiga dari keempat titiknya, sehingga menyisakan tepat satu titik bersama; sedangkan perpotongan totalnya menghilangkan setiap titiknya. Adapun $S_i$ bersifat berhingga, tak cembung: jadi kecembungannya hakiki. (c) Berhingga banyak $H_k = \intco{k}{+\infty} \times \R$ berpotongan di $\intco{k_{\max}}{+\infty} \times \R \neq \emptyset$ , namun tak ada titik yang $x \geq k$ untuk setiap $k \in \N$ : jadi bagi keluarga tak hingga, kekompakannya hakiki.

14. Andaikan $\bigcap_{i \in I}K_i = \emptyset$ lalu tetapkan $i_0$ . Setiap $x \in K_{i_0}$ meleset dari suatu $K_i$ , jadi $K_{i_0} \subseteq \bigcup_{i \in I}(\R^2 \setminus K_i)$ , yakni sebuah peliput oleh himpunan terbuka (sebab $K_i$ kompak, sehingga tertutup). Menurut Borel–Lebesgue (Teorema 4.20), berhingga banyak sudah cukup: $K_{i_0} \cap K_{i_1} \cap \dots \cap K_{i_N} = \emptyset$ . Tetapi setiap tiga anggota keluarga berhingga himpunan cembung ini berpotongan, jadi pertanyaan 12 membuat perpotongannya tak kosong: sehingga kontradiksi.

15. Tetapkan $D_p = \overline D(p, r)$ untuk $p \in S$ : yakni himpunan kompak yang cembung. Untuk $p, q, s \in S$ , hipotesisnya memberi cakram tertutup $\overline D(z, r)$ yang memuat $p, q, s$ ; lalu $\norm{\vect{zp}}, \norm{\vect{zq}}, \norm{\vect{zs}} \leq r$ , yakni $z \in D_p \cap D_q \cap D_s$ . Jadi menurut Helly (pertanyaan 12; sebab keluarganya berhingga) ada $c \in \bigcap_{p \in S}D_p$ : sehingga setiap $p \in S$ memenuhi $\norm{\vect{cp}} \leq r$ , jadi $S \subseteq \overline D(c, r)$ .

16. Misalkan $c = x_{\lceil n/2\rceil}$ . Sebuah setengah garis tertutup yang memuat $c$ berbentuk $\intoc{-\infty}{t}$ dengan $t \geq c$ atau $\intco{t}{+\infty}$ dengan $t \leq c$ . Yang pertama memuat $x_1, \dots, x_{\lceil n/2\rceil}$ : jadi sekurangnya $\lceil n/2\rceil \geq n/2$ titik. Yang kedua memuat $x_{\lceil n/2\rceil}, \dots, x_n$ : yakni tepat $n - \lceil n/2\rceil + 1 = \floor{n/2} + 1 > n/2$ titik.

17. Berlaku $\abs{A \cap B} = \abs A + \abs B - \abs{A \cup B} \geq \abs A + \abs B - n > \tfrac{4n}3 - n = \tfrac n3$ , lalu

\abs{A \cap B \cap C} \geq \abs{A \cap B} + \abs C - n > \tfrac n3 + \tfrac{2n}3 - n = 0 .

18. Perhatikan $m > 2n/3$ . Untuk $T_1, T_2, T_3 \subseteq S$ yang berkardinalitas $m$ , pertanyaan 17 menyediakan titik $x \in T_1 \cap T_2 \cap T_3$ ; lalu $x \in \operatorname{conv}(T_i)$ untuk tiap $i$ : jadi setiap tiga anggota $\mathcal F$ bertemu. Keluarganya berhingga (sebab berhingga banyak himpunan bagian $S$ ) dan terdiri atas himpunan cembung, jadi Helly (pertanyaan 12) memberi $c \in \bigcap_{\abs T = m}\operatorname{conv}(T)$ .

19. Andaikan suatu setengah bidang tertutup $H \ni c$ memuat kurang dari $n/3$ titik $S$ . Maka komplemennya $U$ adalah setengah bidang terbuka yang cembung, dengan $\abs{S \cap U} > 2n/3$ , sehingga $\abs{S \cap U} \geq \floor{2n/3} + 1 = m$ ; jadi pilihlah $T \subseteq S \cap U$ dengan $\abs T = m$ . Lalu $\operatorname{conv}(T) \subseteq U$ berkat kecembungan $U$ , jadi $c \in \operatorname{conv}(T) \subseteq U$ : yang bertentangan dengan $c \in H$ . Karena itu setiap setengah bidang tertutup yang memuat $c$ memuat sekurangnya $n/3$ titik: jadi $c$ merupakan titik penyeimbang.

20. Ambillah segitiga sama sisi bersisi $L$ dan $\varepsilon = L/100$ . Misalkan $c$ sembarang titik; kita akan memamerkan setengah bidang tertutup yang memuat $c$ dan paling banyak $k$ titik.

Kasus 1: $c$ berjarak kurang dari $L/10$ dari sebuah titik sudut, katakanlah $B$ . Arah dari $c$ ke $A$ dan ke $C$ menyimpang dari arah $B \to A$ dan $B \to C$ paling banyak sebesar $\arcsin\bigl(\tfrac{L/10}{9L/10}\bigr) = \arcsin\tfrac19$ , jadi keduanya bersudut $\leq \tfrac\pi3 + 2\arcsin\tfrac19 < \tfrac{2\pi}3$ . Kasus 2: $c$ berjarak $> L/10$ dari semua titik sudutnya. Bila $c$ ada di segitiganya, maka ketiga senjang sudut di antara arah $u_A, u_B, u_C$ dari $c$ ke titik sudutnya berjumlah $2\pi$ , jadi suatu senjangnya $\leq 2\pi/3$ ; sedangkan bila $c$ di luarnya, ketiga arahnya terletak pada sebuah setengah bidang arah yang terbuka dan dua di antaranya bersudut $< \pi/2$ . Jadi pada setiap kasusnya dua arah, katakanlah ke $X$ dan $Y$ , bersudut $\leq 2\pi/3$ ; lalu misalkan $w$ pembagi dua satuannya, sehingga $\langle u_X, w\rangle, \langle u_Y, w\rangle \geq \cos\tfrac\pi3 = \tfrac12$ . Untuk sembarang titik $b$ pada cakram di sekitar $X$ :

\langle \vect{cb}, w\rangle \geq \tfrac12\norm{\vect{cX}} - \varepsilon > 0,

sebab $\norm{\vect{cX}} \geq L/10 > 2\varepsilon$ (dan demikian pula untuk $Y$ ): jadi setengah bidang terbuka $\{\langle \vect{cx}, w\rangle > 0\}$ menelan kedua gugusnya. Sedangkan komplemen tertutupnya memuat $c$ dan paling banyak $k$ titik gugus ketiganya. Jadi tak ada titik bidang yang mengalahkan $n/3$ : sehingga bersama pertanyaan 19, konstanta titik penyeimbangnya persis $1/3$ .

21. Urutkanlah sudutnya; maka yang terbesar, sebut $\theta$ , memenuhi $\theta \geq \pi/3$ (sebab ketiganya berjumlah $\pi$ ). Bila $\theta \geq \pi/2$ , katakanlah di $R$ , misalkan $M$ titik tengah sisi berhadapannya $\intcc PQ$ . Rumus garis beratnya (yakni $\vect{RM} = \tfrac12(\vect{RP} + \vect{RQ})$ , uraikan lalu hilangkan $\langle\vect{RP}, \vect{RQ}\rangle$ lewat hukum kosinusnya) memberi

\norm{\vect{RM}}^2 = \tfrac12\norm{\vect{RP}}^2 + \tfrac12\norm{\vect{RQ}}^2 - \tfrac14\norm{\vect{PQ}}^2 \leq \tfrac12\norm{\vect{PQ}}^2 - \tfrac14\norm{\vect{PQ}}^2 = \tfrac14\norm{\vect{PQ}}^2,

dengan memakai $\norm{\vect{PQ}}^2 = \norm{\vect{RP}}^2 + \norm{\vect{RQ}}^2 - 2\langle\vect{RP}, \vect{RQ}\rangle \geq \norm{\vect{RP}}^2 + \norm{\vect{RQ}}^2$ (sebab hasil kali dalamnya $\leq 0$ ). Jadi cakram bergaris tengah $\intcc PQ$ , yang berjari-jari $\leq \tfrac12 < \tfrac1{\sqrt3}$ , memuat ketiga titiknya (sedangkan tripel segaris yang merosot masuk ke $\theta = \pi$ ). Bila $\theta < \pi/2$ segitiganya lancip; jadi menurut hukum sinusnya jari-jari lingkar luarnya $R_c = a/(2\sin\theta)$ dengan $a \leq 1$ sisi yang berhadapan dengan $\theta$ , lalu $\theta \in \intco{\pi/3}{\pi/2}$ memberi $\sin\theta \geq \sqrt3/2$ , jadi $R_c \leq 1/\sqrt3$ : sehingga cakram lingkar luarnya menuntaskannya.

22. Untuk $p \in S$ misalkan $K_p = \overline D(p, 1/\sqrt3)$ : yakni kompak dan cembung. Sembarang tiga titik $p, q, s$ milik $S$ berjarak berpasangan $\leq 1$ , jadi pertanyaan 21 memberi sebuah cakram berjari-jari $1/\sqrt3$ yang memuatnya: sehingga pusatnya terletak di $K_p \cap K_q \cap K_s$ . Jadi menurut Helly kompak (pertanyaan 14, sebab keluarga sembarang diizinkan) ada $c \in \bigcap_{p\in S}K_p$ : sehingga setiap $p \in S$ berjarak $1/\sqrt3$ dari $c$ , yakni $S \subseteq \overline D(c, 1/\sqrt3)$ . Inilah teorema Jung pada bidangnya.

23. Dengan $G$ sebagai titik beratnya, $\sum_i\vect{GA_i} = 0$ , jadi

\sum_i\norm{\vect{OA_i}}^2 = \sum_i\norm{\vect{OG} + \vect{GA_i}}^2 = 3\norm{\vect{OG}}^2 + 2\Bigl\langle \vect{OG}, \sum_i\vect{GA_i}\Bigr\rangle + \sum_i\norm{\vect{GA_i}}^2,

lalu suku tengahnya lenyap: itulah kesamaan Leibniz. Untuk segitiga sama sisi bersisi $1$ , berlaku $\norm{\vect{GA_i}} = 1/\sqrt3$ (yakni dua pertiga tingginya $\sqrt3/2$ ), jadi $\sum_i\norm{\vect{GA_i}}^2 = 1$ . Bila $\overline D(O, r)$ memuat titik sudutnya, maka $3r^2 \geq \sum_i\norm{\vect{OA_i}}^2 = 3\norm{\vect{OG}}^2 + 1 \geq 1$ : jadi $r \geq 1/\sqrt3$ , dengan kesamaannya memaksa $O = G$ dan ketiga jaraknya sama dengan $r$ — yakni cakram lingkar luarnya. Jadi konstanta Jung $1/\sqrt3$ bersifat tajam.

24. Helly di $\R^n$ : bila $C_1, \dots, C_m$ (dengan $m \geq n + 1$ ) himpunan bagian cembung $\R^n$ dan setiap $n + 1$ di antaranya berpotongan, maka semuanya berpotongan. Kasus dasarnya $m = n + 2$ : pilihlah $x_i \in \bigcap_{j\neq i}C_j$ ; lalu lema Radon (Latihan 17.7) memecah $x_1, \dots, x_{n+2}$ menjadi blok $I \mid J$ dengan titik bungkus bersama $z$ , dan untuk tiap $k$ , blok yang tak memuat $k$ terdiri atas titik $C_k$ , jadi $z \in C_k$ berkat kecembungannya, persis seperti pada pertanyaan 11. Adapun langkah induksinya untuk $m \geq n + 2$ : gantilah $C_m, C_{m+1}$ dengan $C_m \cap C_{m+1}$ ; sebab sebuah $(n+1)$ -tupel keluarga barunya yang memuat anggota terpotong itu setara dengan $n + 2$ himpunan lamanya, yang ditangani kasus dasarnya, sedangkan tupel lainnya tercakup hipotesisnya. Jadi rampungkanlah lewat hipotesis induksinya.

25. Aljabar linear masuk satu kali: sebab $n + 2$ vektor pada ruang berdimensi $(n+1)$ berisi pasangan (yakni bobot total dan posisi terbobot) mestilah bergantungan — dan itulah kebergantungan afinnya. Adapun tanda koefisiennya memecah titiknya menjadi kedua blok Radonnya lalu mengubah satu hubungan linear menjadi kesamaan dua barisentrum taknegatif. Sedangkan kecembungannya dipakai persis dua kali: pada langkah Helly (sebab bungkus titik $C_k$ tinggal di $C_k$ ) dan pada penerapannya (sebab setengah bidang dan cakramnya cembung). Adapun dimensi bidangnya hanya masuk lewat bilangan $4 = 2 + 2$ titik yang disuapkan ke Radon, yakni lewat “ $3 = 2 + 1$ ” pada hipotesis Helly; sedangkan selebihnya bebas dimensi, seperti ditegaskan pertanyaan 24. Di $\R^n$ konstantanya menjadi: bilangan Helly $n + 1$ ; konstanta titik penyeimbang $\frac1{n+1}$ (yakni setiap himpunan berhingga punya titik yang setiap setengah ruang tertutup lewatnya memuat pecahan $\geq \frac1{n+1}$ darinya); dan jari-jari Jung $\sqrt{\frac{n}{2(n+1)}}$ bagi himpunan berdiameter $1$ — yang sama dengan $1/\sqrt3$ ketika $n = 2$ .

Istilah yang didefinisikan dalam bab ini

Lihat semua 395 istilah di glosarium