Construct a matroid from a matrix, or from explicit list of hyperplanes
# S3 method for matrix
matroid( x, e0=0, e1=1.e-6, e2=1.e-10, ground=NULL, ... )# S3 method for list
matroid( x, ground=NULL, ... )
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.
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.
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.
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.
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.
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
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.
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
rank(),
simplify(),
getsimplified()