Dalam kombinatorial polihedral, transformasi
Gale mengubah sudut dari setiap politop cembung menjadi sebuah himpunan dari vektor-vektor atau titik-titik dalam sebuah ruang dari sebuah dimensi yang berbeda,
Diagram Gale dari politop. Ini bisa digunakan untuk menggambarkan politop-politop dimensi tinggi dengan beberapa sudut, dengan mengubah mereka menjadi himpunan-himpunan dari titik-titik dalam sebuah ruang dari banyaknya dimensi rendah. Proses bisa juga dibalikkan, untuk membangun politop-politop dengan sifat-sifat yang diinginkan dari
Diagram Gale mereka. Transform Glae dan
Diagram Gale dinamakan oleh David
Gale, yang memperkenalkan metode-metode ini dalam sebuah makalah pada tahun 1956 pada politop-politop bertetangga
Definisi
= Transformasi
=
Diberikan sebuah politop
d
{\displaystyle d}
-dimensi, dengan
n
{\displaystyle n}
sudut, berbatasan 1 ke koordinat Kartesius dari setiap verteks, untuk memperoleh sebuah vektor kolom
(
d
+
1
)
{\displaystyle (d+1)}
-dimensi. Matriks
A
{\displaystyle A}
dari vektor-vektor kolom
n
{\displaystyle n}
ini memiliki dimensi
(
d
+
1
)
×
n
{\displaystyle (d+1)\times n}
dan pangkat
d
{\displaystyle d}
. Transformasi
Gale menggantikan matriks ini oleh sebuah matriks
B
{\displaystyle B}
dari dimensi
n
×
(
n
−
d
−
1
)
{\displaystyle n\times (n-d-1)}
, dimana vektor-vektor kolom adalah sebuah basis untuk kernel dari
A
{\displaystyle A}
. Kemudian
B
{\displaystyle B}
memiliki vektor-vektor baris
n
{\displaystyle n}
, dari dimensi
n
−
d
−
1
{\displaystyle n-d-1}
. Vektor-vektor baris ini membentuk
Diagram Gale dari politop. Terdapat sebuah pilihan yang menjadi basis untuk kernel untuk digunakan.
Sebuah subhimpunan yang tepat dari sudut-sudut dari sebuah politop membentuk himpunan verteks
dari sebuah permukaan politop, jika dan hanya jika himpunan komplemen dari vektor dari transformasi
Gale memiliki lambang cembung yang mengandung asal dalam interior relatifnya. Secara ekuivalen, subhimpunan dari sudut-sudut membentuk sebuah permukaan jika dan hanya jika tidak terdapat fungsi linear yang menetapkan nilai-nilai non-negatif untuk vektor-vektor yang saling melengkapi.
=
Karena transformasi
Gale didefinisikan hanya sampai sebuah transformasi linear, vektor-vektor tak negatifnya bisa dinormalisasikan untuk semua vektor satuan
(
n
−
d
−
1
)
{\displaystyle (n-d-1)}
-dimensi. Linear
Diagram Gale merupakan sebuah versi yang dinormalisasikan dari transformasi
Gale, di mana semua vektor-vektor adalah nol atau vektor satuan.
=
Diberikan sebuah
Diagram Gale dari sebuah politop, sebuah himpunan dari vektor satuan
n
{\displaystyle n}
dalam ruang
(
n
−
d
−
1
)
{\displaystyle (n-d-1)}
-dimensi, salah satu bisa memilih sebuah subruang
(
n
−
d
−
2
)
{\displaystyle (n-d-2)}
-dimensi
S
{\displaystyle S}
melalui asalnya, dan sebuah subruang
S
′
{\displaystyle S'}
paralel yang tidak melewati ke asalnya. Kemudian, sebuah proyeksi pusat dari asalnya ke
S
′
{\displaystyle S'}
akan menghasilkan sebuah himpunan dari titik-titik
(
n
−
d
−
2
)
{\displaystyle (n-d-2)}
-dimensi. Proyeksi ini kehilangan informasi tentang vektor-vektor yang terletak di atas
S
{\displaystyle S}
dan yang terletak di bawahnya, tetapi informasi ini bisa diwakli dengan menetapkan sebuah tanda (positif, negatif, atau, nol) atau tepatnya (hitam, putih, atau abu-abu) untuk setia titik. Hasil himpunan yang sudah ditetapkan atau titik-titik yang diwarnai meruakan
Diagram Gale afin dari politop yang diberikan. Pembuatan ini memiliki keunggulan, dibandingkan transformasi
Gale, menggunakan satu dimensi lebih sedikit untuk mewakili struktur dari politop yang diberikan.
Transformasi
Gale dan linear serta
Diagram Gale affine bisa juga digambarkan lewat kemangroan dari matriod yang berorientasi. Seperti
Diagram linear, sebuah himpunan bagian dari sudut-sudut membentuk sebuah permukaan jika dan hanya jika tidak terdapat fungsi afin (sebuah fungsi linear dengan kemungkinan istilah konstanta bukan nol) yang menetapkan sebuah nilai bukan negatif untuk setiap vektor positif dalam himpunan yang saling melengkapi dan nilai bukan positif untuk setiap vektor negatif dalam himpunan yang saling melengkapi.
Contoh
Diagram Gale secara khusus efektif dalam menggambarkan polihedra dimana bilangan-bilangan dari sudut-sudut hanya sedikit lebih besar daripada dimensi-dimensi mereka.
= Kesederhanaan
=
Sebuah politop
d
{\displaystyle d}
-dimensi dengan sudut
n
=
d
+
1
{\displaystyle n=d+1}
., kemungkinan minimum, sebuah simpleks. Dalam kasus ini,
Diagram Gale linear adalah 0 dimensi, terdiri hanya dari vektor nol.
Diagram afin memiliki
n
{\displaystyle n}
titik abu-abu.
= Satu sudut tambahan
=
Dalam sebuah politop
d
{\displaystyle d}
-dimensi dengan sudut
n
=
d
+
2
{\displaystyle n=d+2}
,
Diagram Gale linear adalah satu dimensi, dengan vektor mewakili setiap titik-titik menjadi salah satu dari tiga bilangan
−
1
{\displaystyle -1}
,
0
{\displaystyle 0}
, atau
+
1
{\displaystyle +1}
. Dalam
Diagram afin, titik-titik adalah nol dimensi, jadi mereka bisa diwakili hanya oleh tanda atau warna tanpa setiap nilai lokasi. Dalam perintah untuk mewakili sebuah politop,
Diagram harus memiliki setidaknya dua titik dengan setiap tanda bukan nol. Dua
Diagram mewakili kelas ekuvalen kombinatorial yang sama dari politop dari setiap tanda, atau ketika mereka bisa diperoleh dari satu sama lain dengan meniadakan semua tandanya.
Untuk
d
=
2
{\displaystyle d=2}
, hanya kemungkinan dua titik dari setiap tanfa bukan nol, mewakili sebuah kuadraliteral cembung. Untuk
d
=
3
{\displaystyle d=3}
, terdapat dua kemungkinan
Diagram Galeː
Diagram dengan dua titik dari setiap tanda bukan nol dan satu titik nol mewakili sebuah piramida persegi, meskipun
Diagram dengan dua titik dari satu tanda bukan nol dan tiga titik dengan tanda lain mewakili bipiramida segitiga.
Secara umum, bilangan dari
Diagram Gale yang berbeda dengan
n
=
d
+
2
{\displaystyle n=d+2}
, dan bilangan dari kelas ekuivalen kombinatorial dari politop
d
{\displaystyle d}
-dimensi dengan
n
{\displaystyle n}
sudut, adalah
⌊
d
2
4
⌋
{\displaystyle \left\lfloor {\frac {d^{2}}{4}}\right\rfloor }
.
= Dua sudut tambahan
=
Dalam sebuah poltiop
d
{\displaystyle d}
-dimensi dengan sudut
n
=
d
+
3
{\displaystyle n=d+3}
,
Diagram Gale linear terdiri dari titik-titik pada lingkaran satuan (vektor satuan) dan di tengahnya.
Diagram Gale afin terdiri dari titik-titik yang dilabelkan atau gugusan dari titik-titik pada sebuah garis. Tidak seperti untuk kasus dari sudut
n
=
d
+
3
{\displaystyle n=d+3}
, ini tidak sepenuhnya diremehkan untuk menentukan ketika dua
Diagram Gale mewakili politop yang sama.
Polihedra tiga dimensi dengan enam sudut menyediakan cara yang alami ketika polihedron biasa memiliki dimensi yang cukup rendah untuk membayangkan, tetapi tempat
Diagram Gale masih menyediakan sebuah efek penurunan dimensi. Ini termasuk keduanya, oktahedron biasa dan prisma segitiga.
Diagram Gale linear dari sebuah oktahedron biasa terdiri dari tiga pasangan dari titik-titik yang sama pada lingkaran satuan (mewakili pasangan-pasangan dari sudut-sudut yang berlawanan dari oktahedron), dibagi lingkaran menjadi busur dari sudut yang kurang dari
π
{\displaystyle \pi }
.
Diagram Gale afinnya terdiri dari tiga pasangan-pasangan dari titik-titik ditandai yang sama pada garis, dengan pasangan tengah memiliki tanda yang berlawanan ke dua pasangan diluar.
Diagram Gale linear dari sebuah prisma segitiga terdiri dari enam titik pada lingkaran, dalam tiga pasangan berseberangan, dengan setiap pasang mewakili sudut-sudut dari prisma yang berdekatan pada dua permukaan persegi dari prisma. Sesuai
Diagram Gale afin memiliki tiga pasangan dari titik-titik pada sebuah garis, seperti oktahedron biasa, tetapi dengan satu titik dari setiap tanda dalam setiap pasang.
Penerapan
Diagram Gale telah digunakan untuk menyediakan sebuah pencacahan kombinatorial lengkap dari politop
d
{\displaystyle d}
-dimensi dengan sudut
n
=
d
+
3
{\displaystyle n=d+3}
, dan untuk membangun politop-politop yang memiliki sifat-sifat yang luar biasa.
Poltop-politop dibangun dalam cara ini termasukː
Politop Perles, sebuah politop 8 dimensi dengan 12 sudut yang tidak bisa dilakukan dengan koordinat Kartesius rasional. Politop ini dibangun oleh Micha Perles dari konfigurasi Perles (sembilan titik dan sembilan garis dalam bidang yang tidak bisa dilakukan dengan koordinat-koordinat rasional) dengan menggandakan tiga titik dari konfigurasi Perles, menetapkan tanda-tanda untuk 12 titik yang dihasilkan, dan memperlakukan hasil konfigurasi yang ditandai sebagai
Diagram Gale dari sebuah politop. Meskipun politop-politop irasional dikenal dengan dimensi serendah empat, tidak ada yang diketahui dengan sudut lebih sedikit.
Politop Kleinschmidt, sebuah politop 4 dimensi dengan 8 sudut, 10 segi tetradehral, dan satu segi oktahedral, diciptakan oleh Peter Kelinschmidt. Meskipun segi oktahedral meniliki struktur kombinatorial yang sama sebagai sebuah oktahedron biasa, ini tidak mungkin untuk menjadi biasa. Dua salinan dari politop ini bisa direkatkan bersama pada segi oktahedral mereka untuk menghasilkan sebuah politop 10 titik yang beberapa pasangan dari realisasi tidak bisa terus-menerus berubah bentuk menjadi satu sama lain.
Bipiramida diatas piramida persegi adalah sebuah politop 4 dimensi dengan 7 sudut memiliki sifat ganda, yang bentuk dari salah satu dari gambar titik (puncak dari piramid tengahnya) tidak bisa ditentukan. Awalnya ditemukan oleh David W. Barnette, contoh ini ditemukan kembali oleh Bernd Sturmfels menggunakan
Diagram Gale.
Bangunan dari "politop-politop tidak bersebelahan" yang kecil, yaitu, politop-politop tanpa sebuah titik universal, dan "politop-politop yang digambar", di mana setiap titik insiden ke sebuah diagonal yang melewati interior dari politop. Politop lintasan memiliki sifat-sifat ini, tetapi dalam 16 atau lebih dimensi ada politop-politop yang digambar dengan sudut-sudut lebih sedikit, dan dalam 6 atau lebih dimensi politop-politop yang digambar dengan sudut-sudut yang paling sedikit tidak perlu sederhana. Konstruksinya melibatkan
Diagram Gale
Catatan
Referensi
Gale, David (1956), "Neighboring vertices on a convex polyhedron", Linear inequalities and related system, Annals of Mathematics Studies, no. 38, Princeton University Press, Princeton, N.J., hlm. 255–263, MR 0085552
Sturmfels, Bernd (1988), "Some applications of affine
Gale diagrams to polytopes with few vertices", SIAM Journal on Discrete Mathematics, 1 (1): 121–133, doi:10.1137/0401014, MR 0936614
Thomas, Rekha R. (2006), "Chapter 5:
Gale Diagrams", Lectures in Geometric Combinatorics, Student Mathematical Library, 33, Institute for Advanced Study (IAS), Princeton, NJ, hlm. 37–45, doi:10.1090/stml/033, ISBN 0-8218-4140-8, MR 2237292
Wotzlaw, Ronald F.; Ziegler, Günter M. (2011), "A lost counterexample and a problem on illuminated polytopes", American Mathematical Monthly, 118 (6): 534–543, doi:10.4169/amer.math.monthly.118.06.534, MR 2812284
Ziegler, Günter M. (1995), "Chapter 6: Duality,
Gale Diagrams, and Applications", Lectures on Polytopes, Graduate Texts in Mathematics, 152, New York: Springer-Verlag, hlm. 149–190, doi:10.1007/978-1-4613-8431-1_6, ISBN 0-387-94365-X, MR 1311028
