# Construction of Incidence Structures and Designs

## `IncidenceStructure< v | X >: RngIntElt, List -> Inc`

## `IncidenceStructure< P | X >: SetIndx, List -> Inc`

Construct the incidence structure $D$ having point set $P = \lbrace @ p_1, p_2, \ldots, p_v @ \rbrace$ (where $p_i = i$ for each $i$ if the first form of the constructor is used), and block set $B = \lbrace B_1, B_2, \ldots, B_b \rbrace$ given by $X$. The value of $X$ must be either:

**(a)**
A list of subsets of the set $P$.

**(b)**
A sequence, set or indexed set of subsets of $P$.

**(c)**
A list of blocks of an existing incidence structure.

**(d)**
A sequence, set or indexed set of blocks of an existing incidence structure.

**(e)**
A combination of the above.

**(f)**
A $v \times b$ $(0,1)$-matrix $A$, where $A$ may be defined over any coefficient ring. The matrix $A$ will be interpreted as the incidence matrix for the incidence structure $D$.

**(g)**
A set of codewords of a linear code with length $v$. The block set of $D$ is taken to be the set of supports of the codewords.

The incidence structure $D$ produced by this constructor will have $P$ as its point set and $B$ as its set of blocks. The function returns three values:

**(i)**
The incidence structure $D$;

**(ii)**
The point-set $P$ for $D$; and

**(iii)**
The block-set $B$ for $D$.

## `NearLinearSpace< v | X : parameters >: RngIntElt, List -> IncNsp`

## `NearLinearSpace< P | X : parameters >: SetIndx, List -> IncNsp`

```magma
Check: BoolElt                    Default: true
```

Construct the near–linear space $S$ on the set of points $P = \lbrace @ p_1, p_2, \ldots, p_v @ \rbrace$ (where $p_i = i$ for each $i$ if the first form of the constructor is used), with lines $L = \lbrace L_1, L_2, \ldots, L_b \rbrace$ given by $X$. The value of $X$ must be either:

**(a)**
A list of subsets of the set $P$.

**(b)**
A sequence, set or indexed set of subsets of $P$.

**(c)**
A list of blocks of an existing incidence structure.

**(d)**
A sequence, set or indexed set of blocks of an existing incidence structure.

**(e)**
A combination of the above.

**(f)**
A $v \times b$ $(0,1)$-matrix $A$, where $A$ may be over any coefficient ring. The matrix $A$ will be interpreted as the incidence matrix for the near–linear space $S$.

**(g)**
A set of codewords of a linear code with length $v$. The line set of $S$ is taken to be the set of supports of the codewords.

The set of lines $L$ defined by $X$ must satisfy two properties:

**(a)**
Each line of $L$ must contain at least two points;

**(b)**
Any two points of $P$ may lie on at most one line.

The optional boolean argument `Check` indicates whether or not to check that these two properties are satisfied.

The near–linear space $S$ produced by this constructor will have $P$ as its point set and $L$ as its set of lines. The function returns three values:

**(i)**
The near–linear space $S$;

**(ii)**
The point-set $P$ for $S$; and

**(iii)**
The line-set $L$ for $S$.

## `LinearSpace< v | X : parameters >: RngIntElt, List -> IncLsp`

## `LinearSpace< P | X : parameters >: SetIndx, List -> IncLsp`

```magma
Check: BoolElt                    Default: true
```

Construct the linear space $S$ on the set of points $P = \lbrace @ p_1, p_2, \ldots, p_v @ \rbrace$ (where $p_i = i$ for each $i$ if the first form of the constructor is used), with lines $L = \lbrace L_1, L_2, \ldots, L_b \rbrace$ given by $X$. The value of $X$ must be either:

**(a)**
A list of subsets of the set $P$.

**(b)**
A sequence, set or indexed set of subsets of $P$.

**(c)**
A list of blocks of an existing incidence structure.

**(d)**
A sequence, set or indexed set of blocks of an existing incidence structure.

**(e)**
A combination of the above.

**(f)**
A $v \times b$ $(0,1)$-matrix $A$, where $A$ may be defined over any coefficient ring. The matrix $A$ will be interpreted as the incidence matrix for the linear space $S$.

**(g)**
A set of codewords of a linear code with length $v$. The line set of $S$ is taken to be the set of supports of the codewords.

The set of lines $L$ defined by $X$ must satisfy two properties:

**(a)**
Each line of $L$ must contain at least two points;

**(b)**
Any two points of $P$ must lie on precisely one line.

The optional boolean argument `Check` indicates whether or not to check that these two properties are satisfied.

The linear space $S$ produced by this constructor will have $P$ as its point set and $L$ as its set of lines. The function returns three values:

**(i)**
The linear space $S$;

**(ii)**
The point-set $P$ for $S$; and

**(iii)**
The line-set $L$ for $S$.

## `Design< t, v | X : parameters >: RngIntElt, RngIntElt, List -> Dsgn`

## `Design< t, P | X : parameters >: RngIntElt, SetIndx, List -> Dsgn`

```magma
Check: BoolElt                    Default: true
Al   : MonStg                     Default: "NoOrbits"
```

Construct the $t$–design $D$ on the set of points $P = \lbrace @ p_1, p_2, \ldots, p_v @ \rbrace$ (where $p_i = i$ for each $i$ if the first form of the constructor is used), with blocks $B = \lbrace B_1, B_2, \ldots, B_b \rbrace$ given by $X$. The value of $X$ must be either:

**(a)**
A list of subsets of the set $P$.

**(b)**
A sequence, set or indexed set of subsets of $P$.

**(c)**
A list of blocks of an existing incidence structure.

**(d)**
A sequence, set or indexed set of blocks of an existing incidence structure.

**(e)**
A combination of the above.

**(f)**
A $v \times b$ $(0,1)$-matrix $A$, where $A$ may be over any coefficient ring. The matrix $A$ will be interpreted as the incidence matrix for the $t$–$(v,k,\lambda)$ design $D$.

**(g)**
A set of codewords of a linear code with length $v$. The block set of $D$ is taken to be the set of supports of the codewords.

The set of blocks $B$ defined by $X$ must satisfy three properties:

**(a)**
Each block must contain the same number, $k$ say, of points.

**(b)**
Every $t$–subset of $P$ must lie in the same number, $\lambda$ say (where $\lambda > 0$), of blocks.

**(c)**
There must be no repeated blocks.

The optional boolean argument `Check` indicates whether or not to check that these three properties are satisfied. The optional parameter `Al` can be used to specify the algorithm used for balance testing, see the introduction to Section [Elementary Properties of Incidence Structures and Designs](boolean.md#design-sec-prop) for a full description of its usage.

The $t$–$(v,k,\lambda)$ design $D$ produced by this constructor will have $P$ as its point set and $B$ as its set of blocks. The function returns three values:

**(i)**
The design $D$;

**(ii)**
The point-set $P$ for $D$; and

**(iii)**
The block-set $B$ for $D$.

## `Example: Constructors (ex-3bf146)`

The Fano plane, considered as a $2$-$(7,3,1)$ design, may be constructed by the following statement:

```magma
> F := Design< 2, 7 | {1,2,3}, {1,4,5}, {1,6,7}, {2,4,7},
>                                {2,5,6}, {3,5,7}, {3,4,6} >;
> F: Maximal;
2-(7, 3, 1) Design with 7 blocks
Points: {@ 1, 2, 3, 4, 5, 6, 7 @}
Blocks:
    {1, 2, 3},
    {1, 4, 5},
    {1, 6, 7},
    {2, 4, 7},
    {2, 5, 6},
    {3, 5, 7},
    {3, 4, 6}

```

General incidence structures are allowed repeated blocks, as in the following:

```magma
> S := IncidenceStructure< {@ 4, 5, 7, 9 @} | [{4, 5, 7}, {7, 9},
>                                              {5, 7, 9} , {7, 9}] >;
> S: Maximal;
Incidence Structure on 4 points with 4 blocks
Points: {@ 4, 5, 7, 9 @}
Blocks:
    {4, 5, 7},
    {7, 9},
    {5, 7, 9},
    {7, 9}

```

We now construct a linear space by giving its incidence matrix:

```magma
> R := RMatrixSpace(Integers(), 5, 6);
> I := R![ 1, 0, 1, 1, 0, 0,
>          1, 0, 0, 0, 1, 1,
>          1, 1, 0, 0, 0, 0,
>          0, 1, 1, 0, 1, 0,
>          0, 1, 0, 1, 0, 1];
> L := LinearSpace< 5 | I >;
> L: Maximal;
Linear Space on 5 points with 6 lines
Points: {@ 1, 2, 3, 4, 5 @}
Lines:
    {1, 2, 3},
    {3, 4, 5},
    {1, 4},
    {1, 5},
    {2, 4},
    {2, 5}

```

Finally, we use the minimum weight codewords of the unextended binary Golay code to construct a 4-(23, 7, 1) design. Since we know that this is indeed a 4-design, we set the checking parameter to `false`.

```magma
> C := GolayCode(GF(2), false);
> C;
[23, 12, 7] Unextended Golay Code over GF(2)
Generator matrix:
[1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1]
[0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1]
[0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1]
[0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1]
[0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0]
[0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1]
[0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1]
[0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1 0]
[0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1]
> minwt := MinimumWeight(C);
> minwt;
7
> wds := Words(C, minwt);
> D := Design< 4, Length(C) | wds : Check := false >;
> D;
4-(23, 7, 1) Design with 253 blocks

```