Quelle  semiboolmat.xml  Sprache: unbekannt

#############################################################################
##
#W  semiboolmat.xml
#Y  Copyright (C) 2017                                      Wilf A. Wilson
##
##  Licensing information can be found in the README file of this package.
##
#############################################################################
##

<#GAPDoc Label="FullBooleanMatMonoid">
   <ManSection>
    <Oper Name="FullBooleanMatMonoid" Arg="d"/>
    <Returns>The monoid of all boolean matrices of dimension <A>d</A>.</Returns>
    <Description>
      If <A>d</A> is a positive integer less than or equal to <C>5</C>, then
      this operation returns the full boolean matrix monoid of dimension
      <A>d</A>. The <E>full boolean matrix monoid of dimension <A>d</A></E> is
      the monoid consisting of all <A>d</A> by <A>d</A> boolean matrices, and
      has <C>2 ^ (<A>n</A> ^ 2)</C> matrices. <P/>

      <C>FullBooleanMatMonoid</C> returns a monoid with a generating set that is
      minimal in size. These generating sets are pre-computed.

      <Example><![CDATA[
gap> S := FullBooleanMatMonoid(3);
<monoid of 3x3 boolean matrices with 5 generators>
gap> Size(S);
512]]></Example>
    </Description>
  </ManSection>
<#/GAPDoc>

<#GAPDoc Label="RegularBooleanMatMonoid">
<ManSection>
  <Oper Name="RegularBooleanMatMonoid" Arg="d"/>
  <Returns>A monoid of boolean matrices.</Returns>
  <Description>
    If <A>d</A> is a positive integer, then
    <C>RegularBooleanMatMonoid</C> returns the monoid generated by the
    regular <A>d</A> by <A>d</A> boolean matrices. Note that this monoid is
    <E>not</E> regular in general.  <C>RegularBooleanMatMonoid(<A>d</A>)</C> is
    generated by the four boolean matrices <C>A, B, C, D</C>, whose <K>true</K>
    entries are:
    <List>
      <Item>
        <C>A[i][i + 1]</C> and <C>A[n][1]</C>, for
        <M>i \in \{1, \ldots, n - 1\}</M>;
      </Item>
      <Item>
        <C>B[1][2]</C>, <C>B[2][1]</C>, and <C>B[i][i]</C> for <M>i \in \{3,
          \ldots, n\}</M>;
      </Item>
      <Item>
        <C>C[1][2]</C> and <C>C[i][i]</C>, for <M>i \in \{2, \ldots, n -
          1\}</M>; and
      </Item>
      <Item>
        <C>D[1][2]</C>, <C>D[i][i]</C>, for <M>i \in \{2, \ldots, n\}</M>,
        and <C>D[n][1]</C>.
      </Item>
    </List>
    This monoid has nearly <C>2 ^ (n ^ 2)</C> elements.
      <Example><![CDATA[
gap> S := RegularBooleanMatMonoid(3);
<monoid of 3x3 boolean matrices with 4 generators>
gap> Size(S);
506]]></Example>
  </Description>
</ManSection>
<#/GAPDoc>

<#GAPDoc Label="ReflexiveBooleanMatMonoid">
   <ManSection>
    <Oper Name="ReflexiveBooleanMatMonoid" Arg="d"/>
    <Returns>A monoid of boolean matrices.</Returns>
    <Description>
      If <A>d</A> is a positive integer less than or equal to <C>5</C>, then
      this operation returns the monoid consisting of all reflexive <A>d</A> by
      <A>d</A> boolean matrices. A boolean matrix <C>mat</C> is <E>reflexive</E>
      if each entry of its leading diagonal is <K>true</K>, i.e. if
      <C>mat[i][i]</C> is <K>true</K> for all <M>i \in \{1, \ldots, d\}</M>.
      <P/>

      The generating sets for the monoids returned by
      <C>ReflexiveBooleanMatMonoid</C> are pre-computed, and read from a file.
      Small generating sets are not known for <M><A>d</A> \geq 6</M>.

      <Example><![CDATA[
gap> S := ReflexiveBooleanMatMonoid(3);
<monoid of 3x3 boolean matrices with 8 generators>
gap> Size(S);
64]]></Example>
    </Description>
  </ManSection>
<#/GAPDoc>

<#GAPDoc Label="HallMonoid">
   <ManSection>
    <Oper Name="HallMonoid" Arg="d"/>
    <Returns>A monoid of boolean matrices.</Returns>
    <Description>
      If <A>d</A> is a positive integer less than or equal to <C>5</C>, then
      this operation returns the monoid consisting Hall matrices of degree
      <A>d</A>. A <E>Hall matrix</E> is a boolean matrix in which every column
      and every row contains at least one <K>true</K> entry.  Equivalently, a
      Hall matrix is a boolean matrix than contains a permutation. <P/>

      A Hall matrix of dimension <A>d</A> corresponds to a solution to Hall's
      Marriage Problem, when there are two collection of <A>d</A> people.  Thus
      the number of solutions to Hall's Marriage Problem in this instance is the
      number of elements of <C>HallMonoid(<A>d</A>)</C>. <P/>

      The operation <C>HallMonoid</C> returns a monoid with a generating set
      that is minimal in size. These generating sets are pre-computed, and a
      minimal generating set is not known for larger dimensions.

      <Example><![CDATA[
gap> S := HallMonoid(3);
<monoid of 3x3 boolean matrices with 4 generators>
gap> Size(S);
247]]></Example>
    </Description>
  </ManSection>
<#/GAPDoc>

<#GAPDoc Label="GossipMonoid">
   <ManSection>
    <Oper Name="GossipMonoid" Arg="d"/>
    <Returns>A monoid of boolean matrices.</Returns>
    <Description>
      If <A>d</A> is a positive integer, then this operation returns the
      <A>d</A> by <A>d</A> gossip monoid. The <E>gossip monoid</E> is defined to
      be the monoid generated by the collection of all <A>d</A> by <A>d</A>
      boolean matrices that define an equivalence relation; see <Ref
        Prop="IsEquivalenceBooleanMat" />. <P/>

      For <M><A>d</A> \geq 2</M>, <C>GossipMonoid(<A>d</A>)</C> returns a monoid
      with <M>{d \choose 2}</M> generators. The generating set is the
      collection of boolean matrices that define an equivalence relation that
      has one equivalence class of size <C>2</C>, and no other non-trivial
      equivalence classes.  Note that this generating set is strictly contained
      within the collection of all equivalence relation boolean matrices. <P/>

      The number of elements of <C>GossipMonoid(<A>d</A>)</C> is known for some
      small values of <A>d</A> &#8212; see <Cite Key="Brouwer2015aa"/> for more
      information about the gossip monoid, and its size for <M><A>d</A> \leq
        9</M>.

      <Example><![CDATA[
gap> S := GossipMonoid(3);
<monoid of 3x3 boolean matrices with 3 generators>
gap> Size(S);
11]]></Example>
    </Description>
  </ManSection>
<#/GAPDoc>

<#GAPDoc Label="TriangularBooleanMatMonoid">
   <ManSection>
    <Oper Name="TriangularBooleanMatMonoid" Arg="d"/>
    <Oper Name="UnitriangularBooleanMatMonoid" Arg="d"/>
    <Returns>A monoid of boolean matrices.</Returns>
    <Description>
      If <A>d</A> is a positive integer, then <C>TriangularBooleanMatMonoid</C>
      returns the monoid consisting of the upper-triangular <A>d</A> by <A>d</A>
      boolean matrices. A boolean matrix is <E>upper-triangular</E> if the entry
      in row <C>i</C>, column <C>j</C> is <K>false</K> whenever <C>i > j</C>.
      <P/>

      <C>UnitriangularBooleanMatMonoid</C> returns the subsemigroup of the
      <C>TriangularBooleanMatMonoid</C> that consists of reflexive
      upper-triangular boolean matrices; see <Ref
        Oper="ReflexiveBooleanMatMonoid" />.

      <Example><![CDATA[
gap> S := TriangularBooleanMatMonoid(3);
<monoid of 3x3 boolean matrices with 6 generators>
gap> Size(S);
64
gap> T := UnitriangularBooleanMatMonoid(4);
<monoid of 4x4 boolean matrices with 6 generators>
gap> Size(T);
64]]></Example>
    </Description>
  </ManSection>
<#/GAPDoc>