Linear Matroid
(matroid/linear_matroid.hpp)

• View this file on GitHub
• Last update: 2026-07-01 14:07:14+09:00
• Include: #include "matroid/linear_matroid.hpp"

Overview

LinearMatroid<Field> uses vectors over a field as its ground elements. A subset is independent exactly when its vectors are linearly independent.

BinaryLinearMatroid is the faster specialization for vectors over $\mathbb{F}_2$ that fit in 64 bits.

Oracle inputs must contain distinct valid vector indices.

Requirements

For LinearMatroid<Field>, Field must support construction from 0 and 1, equality, subtraction, multiplication, and division. Static modular integers over a prime modulus satisfy these requirements.

All input vectors must have the same dimension.

Interface

Method	Description	Complexity
LinearMatroid(std::vector<std::vector<Field>> vectors)	Stores the field vectors.	$O(ND)$
int size() const	Returns the number of ground elements.	$O(1)$
int dimension() const	Returns vector dimension $D$.	$O(1)$
const std::vector<std::vector<Field>>& vectors() const	Returns the vectors.	$O(1)$
bool independent(const std::vector<int>& subset) const	Tests independence by Gaussian elimination.	$O(	S	D^2)$
bool operator()(const std::vector<int>& subset) const	Independence-oracle shorthand.	$O(	S	D^2)$
BinaryLinearMatroid(std::vector<std::uint64_t> vectors)	Stores binary vectors.	$O(N)$
bool BinaryLinearMatroid::independent(const std::vector<int>& subset) const	Tests XOR-basis independence.	$O(64	S	)$

BinaryLinearMatroid also provides size(), dimension(), vectors(), and operator() with the same meanings. Its dimension() returns 64.

Example

#include "matroid/linear_matroid.hpp"
#include <cstdint>
#include <vector>

std::vector<std::uint64_t> vectors = {1, 2, 3, 4};
m1une::matroid::BinaryLinearMatroid matroid(vectors);

bool independent = matroid(std::vector<int>{0, 1}); // true
bool dependent = matroid(std::vector<int>{0, 1, 2}); // false: 1 xor 2 = 3

Required by

• Matroid All (matroid/all.hpp)

Verified with

• verify/matroid/linear_matroid_intersection.test.cpp
• verify/matroid/matroid_intersection.test.cpp
• verify/matroid/matroids.test.cpp

Code

#ifndef M1UNE_MATROID_LINEAR_MATROID_HPP
#define M1UNE_MATROID_LINEAR_MATROID_HPP 1

#include <array>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

namespace m1une {
namespace matroid {

template <class Field>
class LinearMatroid {
   private:
    int _dimension;
    std::vector<std::vector<Field>> _vectors;

   public:
    LinearMatroid() : _dimension(0) {}

    explicit LinearMatroid(std::vector<std::vector<Field>> vectors)
        : _dimension(vectors.empty() ? 0 : int(vectors[0].size())),
          _vectors(std::move(vectors)) {
#ifndef NDEBUG
        for (const auto& vector : _vectors) assert(int(vector.size()) == _dimension);
#endif
    }

    int size() const {
        return int(_vectors.size());
    }

    int dimension() const {
        return _dimension;
    }

    const std::vector<std::vector<Field>>& vectors() const {
        return _vectors;
    }

    bool independent(const std::vector<int>& subset) const {
        if (int(subset.size()) > _dimension) return false;

        std::vector<std::vector<Field>> basis(_dimension);
        std::vector<char> has_pivot(_dimension, false);
        for (int element : subset) {
            assert(0 <= element && element < int(_vectors.size()));
            std::vector<Field> vector = _vectors[element];
            bool inserted = false;
            for (int column = 0; column < _dimension; column++) {
                if (vector[column] == Field(0)) continue;
                if (!has_pivot[column]) {
                    Field inverse = Field(1) / vector[column];
                    for (int j = column; j < _dimension; j++) vector[j] *= inverse;
                    basis[column] = std::move(vector);
                    has_pivot[column] = true;
                    inserted = true;
                    break;
                }
                Field factor = vector[column];
                for (int j = column; j < _dimension; j++) {
                    vector[j] -= factor * basis[column][j];
                }
            }
            if (!inserted) return false;
        }
        return true;
    }

    bool operator()(const std::vector<int>& subset) const {
        return independent(subset);
    }
};

class BinaryLinearMatroid {
   private:
    std::vector<std::uint64_t> _vectors;

   public:
    BinaryLinearMatroid() = default;
    explicit BinaryLinearMatroid(std::vector<std::uint64_t> vectors)
        : _vectors(std::move(vectors)) {}

    int size() const {
        return int(_vectors.size());
    }

    int dimension() const {
        return 64;
    }

    const std::vector<std::uint64_t>& vectors() const {
        return _vectors;
    }

    bool independent(const std::vector<int>& subset) const {
        if (subset.size() > 64) return false;

        std::array<std::uint64_t, 64> basis = {};
        for (int element : subset) {
            assert(0 <= element && element < int(_vectors.size()));
            std::uint64_t value = _vectors[element];
            for (int bit = 63; bit >= 0; bit--) {
                if ((value >> bit & 1) == 0) continue;
                if (basis[bit] == 0) {
                    basis[bit] = value;
                    break;
                }
                value ^= basis[bit];
            }
            if (value == 0) return false;
        }
        return true;
    }

    bool operator()(const std::vector<int>& subset) const {
        return independent(subset);
    }
};

}  // namespace matroid
}  // namespace m1une

#endif  // M1UNE_MATROID_LINEAR_MATROID_HPP

#line 1 "matroid/linear_matroid.hpp"



#include <array>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

namespace m1une {
namespace matroid {

template <class Field>
class LinearMatroid {
   private:
    int _dimension;
    std::vector<std::vector<Field>> _vectors;

   public:
    LinearMatroid() : _dimension(0) {}

    explicit LinearMatroid(std::vector<std::vector<Field>> vectors)
        : _dimension(vectors.empty() ? 0 : int(vectors[0].size())),
          _vectors(std::move(vectors)) {
#ifndef NDEBUG
        for (const auto& vector : _vectors) assert(int(vector.size()) == _dimension);
#endif
    }

    int size() const {
        return int(_vectors.size());
    }

    int dimension() const {
        return _dimension;
    }

    const std::vector<std::vector<Field>>& vectors() const {
        return _vectors;
    }

    bool independent(const std::vector<int>& subset) const {
        if (int(subset.size()) > _dimension) return false;

        std::vector<std::vector<Field>> basis(_dimension);
        std::vector<char> has_pivot(_dimension, false);
        for (int element : subset) {
            assert(0 <= element && element < int(_vectors.size()));
            std::vector<Field> vector = _vectors[element];
            bool inserted = false;
            for (int column = 0; column < _dimension; column++) {
                if (vector[column] == Field(0)) continue;
                if (!has_pivot[column]) {
                    Field inverse = Field(1) / vector[column];
                    for (int j = column; j < _dimension; j++) vector[j] *= inverse;
                    basis[column] = std::move(vector);
                    has_pivot[column] = true;
                    inserted = true;
                    break;
                }
                Field factor = vector[column];
                for (int j = column; j < _dimension; j++) {
                    vector[j] -= factor * basis[column][j];
                }
            }
            if (!inserted) return false;
        }
        return true;
    }

    bool operator()(const std::vector<int>& subset) const {
        return independent(subset);
    }
};

class BinaryLinearMatroid {
   private:
    std::vector<std::uint64_t> _vectors;

   public:
    BinaryLinearMatroid() = default;
    explicit BinaryLinearMatroid(std::vector<std::uint64_t> vectors)
        : _vectors(std::move(vectors)) {}

    int size() const {
        return int(_vectors.size());
    }

    int dimension() const {
        return 64;
    }

    const std::vector<std::uint64_t>& vectors() const {
        return _vectors;
    }

    bool independent(const std::vector<int>& subset) const {
        if (subset.size() > 64) return false;

        std::array<std::uint64_t, 64> basis = {};
        for (int element : subset) {
            assert(0 <= element && element < int(_vectors.size()));
            std::uint64_t value = _vectors[element];
            for (int bit = 63; bit >= 0; bit--) {
                if ((value >> bit & 1) == 0) continue;
                if (basis[bit] == 0) {
                    basis[bit] = value;
                    break;
                }
                value ^= basis[bit];
            }
            if (value == 0) return false;
        }
        return true;
    }

    bool operator()(const std::vector<int>& subset) const {
        return independent(subset);
    }
};

}  // namespace matroid
}  // namespace m1une

Back to top page