Nhân ma trận, DFT, và lý thuyết biểu diễn nhóm (4)

Ngô Quang Hưng | 16 tháng 01, 2007 | Bản để in Bản để in

Trong bài trước ta kết thúc với định lý Maschke rằng bất kỳ phép biểu diễn (phức) nào trên một nhóm hữu hạn G đều là tổng của các phép biểu diễn tối giản. (Biểu diễn các nhóm vô hạn cũng được, nhưng ta không xét ở đây.)

Như vậy, ta có thể nghiên cứu các phép biểu diễn dùng các phép biểu diễn “đơn giản” hơn một chút. Tuy nhiên, một phép biểu diễn vẫn là một đối tượng rất phức tạp để mô tả (nó là một phép đồng cấu thỏa mãn một số tính chất đại số, hoặc cũng có thể xem nó là một ma trận nếu ta chọn trước một hệ cơ sở trên không gian V). Thậm chí, có bao nhiêu phép biểu diễn (không isomorphic với nhau) ta cũng không biết. Có thể có vô hạn các phép biểu diễn không? Làm thế nào để phân loại chúng?

Để phân loại các phép biểu diễn, có một cách để loại bỏ đa số thông tin về phép biểu diễn, chỉ giữ lại một vài con số! Các con số này chứa rất nhiều thông tin về phép biểu diễn, và ta có thể dùng chúng để phân loại các phép biểu diễn. Kết quả này là một trong những định lý đẹp nhất trong đại số.

Các con số “kỳ diệu” này được chứa trong một hàm gọi là đặc trưng (character) của phép biểu diễn. Đặc trưng \chi của phép biểu diễn \rho trên nhóm G là một hàm \chi: G \to \mathbb{C} định nghĩa như sau

\chi(g) = trace(\rho_g)

(Nhớ rằng \rho_g là một toán tử tuyến tính khả nghịch trên không gian phức V, cái trace của \rho_g là tổng các eigenvalues — trị đặc trưng — của nó.) Hàm đặc trưng \chi cũng có thể được xem như một vector mà các tọa độ được đánh chỉ sổ bởi các thành viên của nhóm G.

Định nghĩa số chiều (dimension) của một character là số chiều của không gian V của phép biểu diễn. Định nghĩa một tích vô hướng Hermitian giữa các characters như sau:

\langle \chi, \chi' \rangle = \frac{1}{|G|}\sum_{g \in G} \chi(g)^*\chi'(g)

(a^* là complex conjugate của a.) Đặc trưng của phép biểu diễn chứa cực kỳ nhiều thông tin về phép biểu diễn. Sau đây tôi trích ra vài kết luận quan trọng:

  • \chi(1) chính là số chiều của phép biểu diễn
  • \chi(g) = \chi(hgh^{-1}), với mọi phần tử g, h \in G, nghĩa là character có giá trị như nhau trên mỗi conjugacy class của nhóm.
  • \chi(g^{-1}) = \chi(g)^*
  • Character của \rho \oplus \rho' là tổng \chi + \chi' của các characters thành phần \chi, \chi'.
  • Gọi N = |G|, và \rho_1, \rho_2, \dots là các đại diện của các isomorphism classes của các phép biểu diễn tối giản trên G, và gọi \chi_i là character của \rho_i. Ta có:
    • Các vectors \chi_i vuông góc với nhau và có chiều dài đơn vị. (Orthogonality relation.) Gọi c là tổng số các conjugacy classes của nhóm. Gọi \mathcal{C} là không gian vector của các hàm f: G \to \mathbb{C} sao cho f có giá trị như nhau trên mỗi conjugacy class của G. Ta có, các characters \chi_i tạo thành một hệ cơ sở trực chuẩn của \mathcal{C}. Ta sẽ dùng tính chất này để nói thêm về DFT trên các nhóm Abel trong bài tới.
    • Tổng số các isomorphism classes của các phép biểu diễn tối giản bằng với tổng số các conjugacy classes của nhóm G. Gọi r là tổng số này.
    • Gọi d_i là số chiều của \rho_i, ta có d_i chia hết cho N, và
      N = d_1^2 + \cdots + d_r^2
  • Một character bất kỳ của nhóm đều có thể biểu diễn (theo một cách duy nhất) thành tổ hợp tuyến tính của các characters tối giản.
  • Hai phép biểu diễn có character giống nhau thì isomorphic với nhau
  • Một character \chi là tối giản nếu và chỉ nếu nó có chiều dài đơn vị (nghĩa là \langle \chi, \chi \rangle = 1)
  • Nếu G là một nhóm Abel thì các characters tối giản của nó đều có số chiều bằng 1.

Có một hệ quả tuyệt đẹp của lý thuyết biểu diễn nhóm khi G là nhóm các hoán vị của n phần tử. Gọi f^{\lambda} là số các standard Young tableaux dạng \lambda. Ta có:

\sum_{\lambda \vdash n} (f^{\lambda})^2 = n!

Định lý này cũng có thể chứng minh bằng giải thuật Robinson-Schensted.

Chủ đề: Thuật Toán |

13 lời bình cho bài “Nhân ma trận, DFT, và lý thuyết biểu diễn nhóm (4)”

  1. 1
    16 tháng 01, 2007, vào lúc 11:23 am dongta viết:

    Một chủ đề rất thú vị. Mong anh Hưng viết tiếp. Em hiện giờ đang mở cuốn Algebra dính đầy bụi của Serge Lang để đọc về Group Representation nên chưa thể bình luận được gì.

  2. 2
    17 tháng 01, 2007, vào lúc 7:24 am Ngô Quang Hưng viết:

    Tôi viết đến đây lại nổi máu combinatorialist :-). Một trong những thứ đầu tiên tôi học về combinatorics là giải thuật Robinson-Schensted-Knuth. Chắc sẽ có một chuỗi bài khác về hook-length formula và các thứ liên quan.

  3. 3
    17 tháng 01, 2007, vào lúc 7:52 am manhtranlinh viết:

    Em cũng đang học lại đại số ở quyển của Serge Lang , tại lần trước em tìm cuốn của Artin như bác giới thiệu ko thấy đâu có ebook mà thấy cuốn của học trò của ông thôi :D đi hỏi các anh học toán thì các bác ấy bảo của Serge Lang viết hay hơn :D,

  4. 4
    17 tháng 01, 2007, vào lúc 8:13 am Ngô Quang Hưng viết:

    Linh: quyển tôi giới thiệu là của Micheal Artin, con trai của Emil Artin.

    Tôi không có quyển của Serge Lang, nên không biết so với quyển của Micheal thì nó hay dở thế nào. Nếu các hủ toán bảo hay thì chắc là hay rồi. Serge Lang là thành viên của nhóm Bourbaki, nên chắc viết sách rất chặt chẽ.

    Quyển của Micheal viết khá đặc, nhưng đúng kiểu tôi cần. Thậm chí tôi cảm thấy mình học được nhiều đại số tuyến tính từ quyển này hơn là từ Gilbert Strang. (BTW, quyển sách hay nhất về đại số tuyến tính mà tôi biết là quyển Matrix Analysis của Horn và Johnson, như đã có lần giới thiệu trên blog.)

  5. 5
    26 tháng 01, 2007, vào lúc 12:04 am khoat viết:

    Mình có vấn đề này liên quan đến Ma trận cần hỏi các anh:
    cho một ma trận A nguyên vuông cấp n. Hỏi rằng có phương pháp nào tốt để phân tích A
    thành tích của hai ma trận nguyên vuông E và D thoả mãn det(D)>1 và det(E)>1 ?

    Nếu có thì rất mong các anh chỉ giúp với !

  6. 6
    26 tháng 01, 2007, vào lúc 7:24 am Ngô Quang Hưng viết:

    Câu hỏi hay quá.

    Nếu det(A) đã nhỏ hơn 1 sẵn rồi (là 0 hay âm) thì sẽ không tồn tại phân tích này.

    Nếu det(A) lớn hơn 1 thì tôi đoán là (trong một số trường hợp) có thể dùng LDU factorization, sau đó viết D thành D1 nhân D2 với phân bố đủ nhuyễn sao cho det(LD1) > 1, det(D2U) > 1

  7. 7
    14 tháng 06, 2007, vào lúc 10:50 pm diep_nv viết:

    Anh Hưng có Source của 2 thuật toán DFT và FFT không ? Nếu có thì cho em xin được không? Em đang làm đề tài mà có liên quan tới 2 thuật toán này, rất cần Source của 2 thuật toán này. Mong anh giúp đỡ. Thanks!
    _________________________
    Name: Nguyen Van Diep
    Email: nguyendiepcntt@gmail.com
    Tel : 0978721668

  8. 8
    15 tháng 06, 2007, vào lúc 6:45 am Ngô Quang Hưng viết:

    Hi diep_nv, vào đây (cụ thể là đây) xem có dùng được không? Nếu chỉ cần một sub-routine thì dùng Matlab cũng được.

  9. 9
    16 tháng 06, 2007, vào lúc 3:38 am diep_nv viết:

    Cảm ơn anh đã quan tâm, nhưng đường link anh cho em không vào được. Nếu anh có thì có thể gửi cho em qua mail được không ? Em cần Source ( Viết bằng C hoặc Java thì càng tốt ). Một lần nữa cảm ơn anh!

  10. 10
    18 tháng 10, 2007, vào lúc 11:33 am Nguyen Phuc Son viết:

    Bác Hưng khi nào có thời gian viết tiếp loạt bài này nhé. Em đợi xem tiếp các phần sau. Cám ơn bác

  11. 11
    18 tháng 10, 2007, vào lúc 12:01 pm Ngô Quang Hưng viết:

    Hi Sơn, dĩ nhiên là tôi sẽ tìm thời gian viết tiếp.

  12. 12
    09 tháng 03, 2008, vào lúc 6:06 am AustinN viết:

    Em muốn hỏi là Đại số trừu tượng thì ứng dụng vào CS thế nào ạ? Em đọc cái undergraduate syllabus của CS trường em ko thấy có môn này.

  13. 13
    12 tháng 03, 2008, vào lúc 2:34 am HaThuyAnh viết:

    diep_nv: Toi co doan chuong trinh thuc hien DFT va FFT viet bang Matlab, rat ngan, khong biet anh co can khong?

Ghi lời bình của bạn: