some comments

Tag: Ruby

Cosets, Abelian groups and Pauli matrices

Cayley graph of the 16-element Pauli group, using three generators. Posted by user Maproom on Wikipedia.

Cayley graph of the 16-element Pauli group, using three generators. Posted by user Maproom on Wikipedia.

The Group.rb class is updated with functions to calculate subgroup cosets and check commutativity. The attached test set uses Pauli matrices as an example of a non-commutative/non-Abelian group.

Group.rb:

class Group
#Alexander Farley, March 2014
#
#This class can be used to verify and compute basic properties of finite discrete groups.
#Useage:
#  sign = [-1,1]
#  mult = Proc.new{ |a,b| a*b }
#  mult_sign = Group.new(sign, mult)
#  mult_sign.isGroup? => true
#

require 'set'

  def initialize(set, block)
    @set = set
    @block = block
  end

  def isGroup?
    has_identity = self.has_identity?
    is_associative = self.is_associative?
    is_closed = self.is_closed?
    has_inverses = self.has_inverses?
    isGroup = has_identity && is_associative && is_closed && has_inverses
    if not has_identity
      p 'missing identity'
    end
    if not is_associative
      p 'not associative'
    end
    if not is_closed
      p 'not closed'
    end
    if not has_inverses
      p 'missing inverse'
    end
    return isGroup
  end

  def is_closed?
    is_closed = true
    @set.each do |element|
      @set.each do |other_element|
        next_element = @block.call(element, other_element)
        if not @set.include?(next_element)
          is_closed = false
        end
      end
    end
    return is_closed
  end

  def has_identity?
    @set.each do |element|
      candidate_identity = true
      @set.each do |other_element|
        next_element = @block.call(element, other_element)
        if not next_element == other_element
          candidate_identity = false
        end
      end
      if candidate_identity == true
        return true
      end
    end
    return false
  end

  def identity
    has_identity = false
    @set.each do |element|
      candidate_identity = true
      @set.each do |other_element|
        next_element = @block.call(element, other_element)
        if not next_element == other_element
          candidate_identity = false
        end
      end
      if candidate_identity == true
        return element
      end
    end
    puts 'No identity exists'
    return nil
  end

  def is_associative?
    is_associative = true
    @set.each do |a|
      @set.each do |b|
        @set.each do |c|
        element_ab_c = @block.call(@block.call(a, b), c)
        element_a_bc = @block.call(a, @block.call(b,c))
        if not element_ab_c == element_a_bc
          is_associative = false
        end
        end
      end
    end
    return is_associative
  end

  def has_inverses?
    has_inverses = true
    id = self.identity
    @set.each do |element|
      found_inverse = false
      @set.each do |other_element|
        next_element = @block.call(element, other_element)
        if next_element == id
          found_inverse = true
        end
      end
      if found_inverse == false
        has_inverses = false
      end
    end
    return has_inverses
  end

  def lcoset(subgroup,group_element)
    lcoset = Array.new
    subgroup.each do |subgroup_element|
      result = @block.call group_element, subgroup_element
      if not lcoset.include? result
        lcoset << result
      end
    end
    return lcoset
  end

  def rcoset(subgroup,group_element)
    rcoset = Array.new
    subgroup.each do |subgroup_element|
      result = @block.call subgroup_element, group_element
      if not rcoset.include? result
        rcoset << result
      end
    end
    return rcoset
  end

  def lcosets(subgroup)
    lcosets = []
    @set.each do |element|
      lcoset = self.lcoset subgroup, element
      if not lcosets.include? lcoset.to_set
        lcosets << lcoset.to_set
      end
    end
    return lcosets
  end

  def rcosets(subgroup)
    rcosets = []
    @set.each do |element|
      rcoset = self.rcoset subgroup, element
      if not rcosets.include? rcoset.to_set
        rcosets << rcoset.to_set
      end
    end
    return rcosets
  end

  def isAbelian?
    isAbelian = true
    @set.each do |element_a|
      @set.each do |element_b|
        result_ab = @block.call element_a, element_b
        result_ba = @block.call element_b, element_a
        if not result_ab == result_ba
          isAbelian = false
        end
      end
    end
    return isAbelian
  end

end

test_group.rb:

require './group'
require 'test/unit'

class TestGroup < Test::Unit::TestCase

	def test_add_mod10_int_mod10_isGroup
	  int_mod10 = [0,1,2,3,4,5,6,7,8,9]
	  add_mod10 = Proc.new{ |a,b| (a+b)%10 }
	  add_int_mod10 = Group.new(int_mod10, add_mod10)
	  assert_equal true, add_int_mod10.isGroup?
	end

	def test_mult_int_mod10_isNotGroup
	  int_mod10 = [0,1,2,3,4,5,6,7,8,9]
	  mult = Proc.new{ |a,b| a*b }
	  mult_int_mod10 = Group.new(int_mod10, mult)
	  assert_equal false, mult_int_mod10.isGroup?
	end

	def test_add_bool_isNotGroup
		bool = [0,1]
		add = Proc.new{ |a,b| a+b }
		add_bool = Group.new(bool, add)
		assert_equal false, add_bool.isGroup?
	end

	def test_add_mod2_bool_isGroup
		bool = [0,1]
		add_mod2 = Proc.new{ |a,b| (a+b)%2 }
		add_mod2_bool = Group.new(bool, add_mod2)
		assert_equal true, add_mod2_bool.isGroup?
	end

	def test_mult_sign_isGroup
		sign = [-1,1]
		mult = Proc.new{ |a,b| a*b }
		mult_sign = Group.new(sign, mult)
		assert_equal true, mult_sign.isGroup?
	end

	def test_lcoset_of_sign_one_is_one #From Wikipedia cosets example, http://en.wikipedia.org/wiki/Coset
		sign = [-1,1]
		one = [1]
		mult = Proc.new{ |a,b| a*b }
		mult_sign = Group.new(sign, mult)
		assert_equal one, mult_sign.lcoset(one,1) #Note that the single group element (g in gH) should not be an array
	end

	def test_lcosets_of_add_mod8 #From Wikipedia cosets example, http://en.wikipedia.org/wiki/Coset
		int_mod8 = [0, 1, 2, 3, 4, 5, 6, 7]
		sg = [0,4]
		add_mod8 = Proc.new{ |a,b| (a+b)%8 }
		add_int_mod8 = Group.new(int_mod8, add_mod8)

		assert_equal [0,4], add_int_mod8.lcoset(sg,0) 
		assert_equal [1,5], add_int_mod8.lcoset(sg,1)
		assert_equal [2,6], add_int_mod8.lcoset(sg,2)
		assert_equal [3,7], add_int_mod8.lcoset(sg,3)

		assert_equal [[0,4].to_set, [1,5].to_set, [2,6].to_set, [3,7].to_set], add_int_mod8.lcosets(sg)
	end

	def test_rcosets_of_add_mod8 #From Wikipedia cosets example, http://en.wikipedia.org/wiki/Coset
		int_mod8 = [0, 1, 2, 3, 4, 5, 6, 7]
		sg = [0,4]
		add_mod8 = Proc.new{ |a,b| (a+b)%8 }
		add_int_mod8 = Group.new(int_mod8, add_mod8)

		assert_equal [0,4], add_int_mod8.rcoset(sg,0) 
		assert_equal [1,5], add_int_mod8.rcoset(sg,1)
		assert_equal [2,6], add_int_mod8.rcoset(sg,2)
		assert_equal [3,7], add_int_mod8.rcoset(sg,3)

		assert_equal [[0,4].to_set, [1,5].to_set, [2,6].to_set, [3,7].to_set], add_int_mod8.rcosets(sg)
	end

	def test_add_mod8_isAbelian
		int_mod8 = [0, 1, 2, 3, 4, 5, 6, 7]
		add_mod8 = Proc.new{ |a,b| (a+b)%8 }
		add_int_mod8 = Group.new(int_mod8, add_mod8)		

		assert_equal true, add_int_mod8.isAbelian?
	end

	def test_mult_pauli_isNotAbelian #http://en.wikipedia.org/wiki/Pauli_group
		require 'matrix'
		id = Matrix[ [Complex(1), Complex(0)], [Complex(0), Complex(1)]]; id_neg = -1*id; id_i = Complex(0,1)*id; id_negi = Complex(0,-1)*id
		p1 = Matrix[ [Complex(0), Complex(1)], [Complex(1), Complex(0)]]; p1_neg = -1*p1; p1_i = Complex(0,1)*p1; p1_negi = Complex(0,-1)*p1
		p2 = Matrix[ [Complex(0), Complex(0,-1)], [Complex(0,1), Complex(0)]]; p2_neg = -1*p2; p2_i = Complex(0,1)*p2; p2_negi = Complex(0,-1)*p2
		p3 = Matrix[ [Complex(1), Complex(0)], [Complex(0), Complex(-1)]]; p3_neg = -1*p3; p3_i = Complex(0,1)*p3; p3_negi = Complex(0,-1)*p3
		pauli_matrices = [id, id_neg, id_i, id_negi, p1, p1_neg, p1_i, p1_negi, p2, p2_neg, p2_i, p2_negi, p3, p3_neg, p3_i, p3_negi]

		mult = Proc.new{ |a,b| a*b }
		mult_pauli_matrices = Group.new(pauli_matrices, mult)
		assert_equal false, mult_pauli_matrices.isAbelian?
	end

	def test_mult_pauli_isGroup #http://en.wikipedia.org/wiki/Pauli_group
		require 'matrix'
		id = Matrix[ [Complex(1), Complex(0)], [Complex(0), Complex(1)]]; id_neg = -1*id; id_i = Complex(0,1)*id; id_negi = Complex(0,-1)*id
		p1 = Matrix[ [Complex(0), Complex(1)], [Complex(1), Complex(0)]]; p1_neg = -1*p1; p1_i = Complex(0,1)*p1; p1_negi = Complex(0,-1)*p1
		p2 = Matrix[ [Complex(0), Complex(0,-1)], [Complex(0,1), Complex(0)]]; p2_neg = -1*p2; p2_i = Complex(0,1)*p2; p2_negi = Complex(0,-1)*p2
		p3 = Matrix[ [Complex(1), Complex(0)], [Complex(0), Complex(-1)]]; p3_neg = -1*p3; p3_i = Complex(0,1)*p3; p3_negi = Complex(0,-1)*p3
		pauli_matrices = [id, id_neg, id_i, id_negi, p1, p1_neg, p1_i, p1_negi, p2, p2_neg, p2_i, p2_negi, p3, p3_neg, p3_i, p3_negi]

		mult = Proc.new{ |a,b| a*b }
		mult_pauli_matrices = Group.new(pauli_matrices, mult)
		assert_equal true, mult_pauli_matrices.isGroup?
	end

end

Groups with Ruby

This image was generated by Vladimir Bulatov's Polyhedra Stellations Applet: http://bulatov.org/polyhedra/stellation_applet

This image was generated by Vladimir Bulatov’s Polyhedra Stellations Applet: http://bulatov.org/polyhedra/stellation_applet

I’ve started writing some functions for verifying introductory group theory results in order to gain a better understanding of group theory. So far, my Group class is able to determine whether a particular discrete set and operator combination is a group.

Corrections or suggestions for more functionality would be appreciated. I plan on adding functions to calculate cosets and verify Lagrange’s theorem.

class Group

  def initialize(set, block)
    @set = set
    @block = block
  end

  def isGroup?
    has_identity = self.has_identity?
    is_associative = self.is_associative?
    is_closed = self.is_closed?
    has_inverses = self.has_inverses?
    isGroup = has_identity &amp;&amp; is_associative &amp;&amp; is_closed &amp;&amp; has_inverses
    if not has_identity
      p 'No identity'
    end
    if not is_associative
      p 'Not associative'
    end
    if not is_closed
      p 'Not closed'
    end
    if not has_inverses
      p 'Missing inverses'
    end
    return isGroup
  end

  def is_closed?
    is_closed = true
    @set.each do |element|
      @set.each do |other_element|
        next_element = @block.call(element, other_element)
        if not @set.include?(next_element)
          is_closed = false
        end
      end
    end
    return is_closed
  end

  def has_identity?
    @set.each do |element|
      candidate_identity = true
      @set.each do |other_element|
        next_element = @block.call(element, other_element)
        if not next_element == other_element
          candidate_identity = false
        end
      end
      if candidate_identity == true
        return true
      end
    end
    return false
  end

  def identity
    has_identity = false
    @set.each do |element|
      candidate_identity = true
      @set.each do |other_element|
        next_element = @block.call(element, other_element)
        if not next_element == other_element
          candidate_identity = false
        end
      end
      if candidate_identity == true
        return element
      end
    end
    puts 'No identity exists'
    return nil
  end

  def is_associative?
    is_associative = true
    @set.each do |a|
      @set.each do |b|
        @set.each do |c|
        element_ab_c = @block.call(@block.call(a, b), c)
        element_a_bc = @block.call(a, @block.call(b,c))
        if not element_ab_c == element_a_bc
          is_associative = false
        end
        end
      end
    end
    return is_associative
  end

  def has_inverses?
    has_inverses = true
    id = self.identity
    @set.each do |element|
      found_inverse = false
      @set.each do |other_element|
        next_element = @block.call(element, other_element)
        if next_element == id
          found_inverse = true
        end
      end
      if found_inverse == false
        has_inverses = false
      end
    end
    return has_inverses
  end

end

Unit tests:

require './group'
require 'test/unit'

class TestGroup &lt; Test::Unit::TestCase

	def test_add_mod10_int_mod10_isGroup
	  int_mod10 = [0,1,2,3,4,5,6,7,8,9]
	  add_mod10 = Proc.new{ |a,b| (a+b)%10 }
	  add_int_mod10 = Group.new(int_mod10, add_mod10)
	  assert_equal true, add_int_mod10.isGroup?
	end

	def test_mult_int_mod10_isNotGroup
	  int_mod10 = [0,1,2,3,4,5,6,7,8,9]
	  mult = Proc.new{ |a,b| a*b }
	  mult_int_mod10 = Group.new(int_mod10, mult)
	  assert_equal false, mult_int_mod10.isGroup?
	end

	def test_add_bool_isNotGroup
		bool = [0,1]
		add = Proc.new{ |a,b| a+b }
		add_bool = Group.new(bool, add)
		assert_equal false, add_bool.isGroup?
	end

	def test_add_mod2_bool_isGroup
		bool = [0,1]
		add_mod2 = Proc.new{ |a,b| (a+b)%2 }
		add_mod2_bool = Group.new(bool, add_mod2)
		assert_equal true, add_mod2_bool.isGroup?
	end

end