mersenneforum.org > Math Do I need group theory for this?
 Register FAQ Search Today's Posts Mark Forums Read

 2005-01-20, 20:43 #1 Orgasmic Troll Cranksta Rap Ayatollah     Jul 2003 10100000012 Posts Do I need group theory for this? Consider an n x n matrix where all the entries are either 1 or 0. How many possible matrices are there for each n, allowing for rotation and reflection. I get 1,2,6,... for n=0,1,2... I've been enumerating n=3, but I haven't finished yet. 1,2,6 isn't much to go on at OLEIS, otherwise I'd poke around there. I know that group theory deals with operations on a set and relates to symmetry, but I don't know much more than that. Would there be an application here? (if there is an application of group theory here, but a better approach, please put both as I would like a concrete example to apply group theory to)
 2005-01-21, 12:50 #2 geoff     Mar 2003 New Zealand 13·89 Posts Hi, I think the application of group theory you are alluding to is group action on a set, where the group in this case is the symmetries of a square, and the set is all nxn binary matrices. I studied this topic (but not this particular problem) in an algebra paper last year, but I failed the paper so you should check everything below for yourself. :-) By Burnside's theorem, if X is a finite G-set then the number of distinguishable elements in X under the action of finite group G is the sum Sigma |X_g|/|G| where X_g is the subset of X fixed by the action g in G. (A G-set X is one where ex = x for all x in X, and where (gh)x = g(hx) for all g,h in G and all x in X. I think it is clear that the set of nxn binary matrices is a G-set when G is the symmetries of a square). To work out the 3x3 case (where |X| = 2^9) I label the positions in the matrix: aba bcb aba Every matrix is fixed by the identity rotation, so |X_1| = 2^9; The matrices fixed by a 90 degree rotation in either direction are those which have all 'a' entries identical and all 'b' entries identical, so |X_2| = |X_3| = 2^3; The matrices fixed by a 180 degree rotation are those which have non-adjacent 'a' entries identical and non-adjacent 'b' entries identical, so |X_4| = 2^5; The matrices fixed by a horizontal (vertical) reflection are those which have identical first and third rows (columns), so |X_5| = |X_6| = 2^6; The diagonal reflections are similar, so |X_7| = |X_8| = 2^6; Then the number of distinguishable 3x3 matrices is [2^9 + 2(2^3) + 2^5 + 2(2^6) + 2(2^6)] / 8 = 102 I think you could get a general formula for the nth term by using a similar method, perhaps by considering odd and even cases separately. Last fiddled with by geoff on 2005-01-21 at 13:01 Reason: fix mistakes

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 0 2017-01-19 20:22 Xyzzy Math 153 2015-11-26 02:42 wpolly Math 1 2008-06-09 12:14 ixfd64 Lounge 13 2007-03-23 15:06 TTn 15k Search 15 2003-09-23 16:28

All times are UTC. The time now is 17:19.

Tue Aug 9 17:19:43 UTC 2022 up 33 days, 12:07, 1 user, load averages: 0.96, 1.11, 1.15

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔