matroid {zonohedra}

matroid construction

Description

Construct a matroid from a matrix, or from explicit list of hyperplanes

Usage

## S3 method for class 'matrix'
matroid( x, e0=0, e1=1.e-6, e2=1.e-10, ground=NULL, ... )

## S3 method for class 'list'
matroid( x, ground=NULL, ... )

Arguments

x

x can be a numeric matrix with 3, 2, or 1 rows whose columns determine the matroid. The matrix must be either square or "wide", i.e. more columns than rows. The matrix must be full-rank, i.e. the rank must be equal to the number of rows, which is then the rank of the constructed matroid. Such a matroid is often called a column matroid or vector matroid.

x can also be a list of vectors of positive integers, which are thought of as sets, and are the hyperplanes of the matroid. The hyperplanes are checked that they satisfy the matroid hyperplane axioms. The rank of the constructed matroid is determined automatically, and must be 3, 2, or 1.

ground

The ground set of the matroid - a vector of positive integers in strictly increasing order.

When x is a matrix, length(ground) must be equal to ncol(x). The point ground[i] corresponds to the i'th column of x. If ground is NULL, the column names of x are converted to such a vector if possible. If this is not possible, ground is set to 1:ncol(x).

When x is a list, every set in the list must be a subset of ground. If ground is NULL, it is set to the union of all the sets in x. For technical reasons, when the rank is 1, ground is required and cannot be NULL, see Details.

e0

threshold, in the L^{\infty} norm, for a column vector of x to be considered 0, and thus that the corresponding point in the matroid is a loop. Since the default is e0=0, by default a column vector must be exactly 0 to become a loop.

e1

threshold, in a pseudo-angular sense, for column vectors to be multiples of each other, and thus members of a group of multiple (aka parallel) points in the matroid. This tolerance is only used when the rank is 2 or 3.

e2

threshold, in a pseudo-angular sense, for the planes spanned by pairs of column vectors to be considered coincident, and thus the columns to be in the same hyperplane of the matroid. This tolerance is used when the rank is 3.

...

not used

Details

It was mentioned above that the tolerances e1 and e2 are pseudo-angular. Specifically, vectors are normalized to the L^2 unit sphere and the distance between them is computed in the L^{\infty} norm.

Matroids are well-known to have many cryptomorphic definitions, e.g. independent sets, bases, circuits, rank function, closure operator, flats, and hyperplanes. See Matroid - Wikipedia. In this package, matroids can only be constructed from hyperplanes, but there are functions rank() and is_independent() that can be used after construction.

Checking that the hyperplanes satisfy the matroid hyperplane axioms is made easier by the fact that all simple matroids of rank 3 or less are paving matroids, see Paving Matroid - Wikipedia

Rank 1 matroids are extremely simple - the loops form the single hyperplane (possibly empty), and the non-loops form a multiple group. If ground=NULL the non-loops are unknown, so this is why ground is required when the rank is 1.

Value

matroid() returns an object with S3 class 'matroid'.
In case of error, e.g. invalid x or computed hyperplanes, the function prints an error message and returns NULL.

Note

The ground set of positive integers should not be too sparse; otherwise performance may suffer.

When x is a matrix with 3 rows, it may happen that the computed hyperplanes do not satisfy the axioms for a matroid. In that case, the user will be prompted to try reducing tolerance e2. Getting the expected hyperplanes may require some a priori knowledge of the expected hyperplanes. For best results, the matrix should be given with maximum precision.

References

Matroid - Wikipedia.
https://en.wikipedia.org/w/index.php?title=Matroid&oldid=1086234057

Paving Matroid - Wikipedia.
https://en.wikipedia.org/w/index.php?title=Paving_matroid&oldid=1021966244

See Also

rank(), simplify(), getsimplified()