3.1. Tác động nhóm¶
Tác động nhóm (Group Action) cho phép chúng ta đếm những cấu hình tổ hợp mà việc vét cạn rồi loại bỏ sẽ tốn nhiều công sức cũng như sai sót.
Cho tập hợp \(M\) và nhóm \(G\). Ta nói \(G\) tác động trái lên \(M\) với ánh xạ:
thỏa mãn hai tiên đề sau:
identity: \(\alpha (e, m) = m\) với mọi \(m \in M\) và \(e\) là phần tử đơn vị của \(G\);
compatibility: \(\alpha (g, \alpha (h, m)) = \alpha (g h, x)\).
Ta thường kí hiệu \(\alpha (g, m)\) bởi \(g(m)\) hay thậm chí đơn giản hơn là \(gm\). Kí hiệu \(gm\) sẽ được sử dụng từ đây về sau.
Khi đó hai tiên đề trên tương đương với:
identity: \(e m = m\) với mọi \(m \in M\);
compatibility: \(g(hm) = (gh) m\) với mọi \(m \in M\) và \(g, h \in G\).
Định nghĩa 3.1 (Nhóm con ổn định)
Với phần tử \(m \in M\) cho trước, tập hợp các phần tử \(g \in G\) mà \(gm = m\) được gọi là nhóm con ổn định (hay stabilizer) của nhóm \(G\). Ta kí hiệu
Định nghĩa 3.2 (Quỹ đạo)
Quỹ đạo (hay orbit) của phần tử \(m \in M\) là tập hợp
Nhận xét 3.2
Hai orbit của hai phần tử bất kì hoặc rời nhau, hoặc trùng nhau.
Chứng minh
Giả sử ta có \(m_1, m_2 \in M\) mà \(G(m_1) \cap G(m_2) \neq \emptyset\).
Khi đó tồn tại \(g_1, g_2 \in G\) để \(g_1 m_1 = g_2 m_2\), suy ra \(m_1 = g_1^{-1} g_2 m_2\).
Thêm nữa, mọi phần tử trong \(G(m_1)\) có dạng \(g m_1\) nên \(g m_1 = g g_1^{-1} g_2 m_2\), suy ra \(G(m_1) \subseteq G(m_2)\).
Chứng minh tương tự ta cũng có \(G(m_2) \subseteq G(m_1)\) nên \(G(m_1) \equiv G(m_2)\).
Nhận xét 3.3
Tập hợp \(M\) là giao của các orbit rời nhau. Giả sử ta có \(t\) orbit rời nhau \(G(m_1)\), \(G(m_2)\), ..., \(G(m_t)\) thì
Ví dụ 3.5
Cho nhóm \(\mathcal{S}_3\) có \(6\) phần tử \((1)(2)(3)\), \((1)(2,3)\), \((2)(1,3)\), \((3)(1,2)\), \((1,2,3)\), \((1,3,2)\).
Xét tập hợp \(M = \{1, 2, 3\}\). Khi đó, xét từng hoán vị trên, ta có:
và
Ta nhận thấy \(G(1) = G(2) = G(3)\), và \(\lvert G \rvert = 6 = \lvert G_1 \rvert \cdot \lvert G(1) \rvert\).
Hay nói cách khác, \(\lvert G(m) \rvert = [G: G_m]\) với \(G_m\) là stabilizer của phần tử \(m\) và \([G: G_m]\) là subgroup index của \(G_m \subset G\), và bằng \(\dfrac{\lvert G \rvert}{\lvert G_m \rvert}\) nếu là nhóm hữu hạn.
Định nghĩa 3.3
Hai phần tử \(m, n \in M\) được gọi là có quan hệ với nhau dưới tác động của nhóm \(G\) nếu tồn tại phần tử \(g \in G\) sao cho \(m = g n\).
Ta kí hiệu là \(m \tilde{G} n\).
Nhận xét 3.4
Quan hệ được định nghĩa như trên là quan hệ tương đương.
Chứng minh
Để chứng minh một quan hệ là tương đương, ta cần chứng minh tính phản xạ, đối xứng và bắc cầu.
Đối với tính phản xạ, mọi vector đều có quan hệ với chính nó qua phần tử đơn vị \(e \in G\).
Đối với tính đối xứng, nếu \(m\) có quan hệ với \(n\) thì tồn tại \(g \in G\) sao cho \(m = gn\). Theo tính chất nhóm thì tồn tại phần tử \(g^{-1}\) là nghịch đảo của \(g\) trong \(G\). Do đó \(g^{-1} m = n\). Nói cách khác \(n\) cũng có quan hệ với \(m\). Như vậy ta có tính đối xứng.
Đối với tính bắc cầu, nếu \(m\) có quan hệ với \(n\) thì tồn tại \(g_1 \in G\) sao cho \(m = g_1 n\). Tiếp theo, nếu \(n\) có quan hệ với \(p\) thì tồn tại \(g_2 \in G\) sao cho \(n = g_2 p\), suy ra
Do \(g_1, g_2 \in G\) nên \(g_1 g_2 \in G\). Như vậy \(m\) cũng có quan hệ với \(p\) nên quan hệ có tính bắc cầu.
Vậy quan hệ được định nghĩa như trên là quan hệ tương đương.