Linear Matroid Intersection
(matroid/linear_matroid_intersection.hpp)
- View this file on GitHub
- Last update: 2026-07-29 16:26:14+09:00
- Include:
#include "matroid/linear_matroid_intersection.hpp"
Overview
linear_matroid_intersection_size returns the maximum size of a set that is
linearly independent in each of two vector families on the same ground set.
Unlike general matroid intersection, it computes only the cardinality, not a
maximizing set.
For vectors $a_e$ and $b_e$, the answer is the symbolic rank of
\[\sum_e x_e a_e b_e^T.\]The algorithm substitutes random field values for $x_e$ and applies Gaussian
elimination. It never returns more than the correct answer, and can return less
with small probability. Over a field of size $q$, the failure probability of
one evaluation is at most $R/q$, where $R$ is the answer. Use a large prime
field such as modint998244353; small fields such as $\mathbb F_2$ are not
suitable.
Each outer vector is one ground-set element. Thus both arguments have size $N$, while their inner vector dimensions may differ.
Requirements
Field must be a field type supporting construction from integers, equality,
addition, subtraction, multiplication, and division. Every vector within one
family must have the same dimension.
For the generator overload, random() must return a value from which Field
can be constructed. Independent uniform field values give the stated error
bound.
Interface
template <class Field>
int linear_matroid_intersection_size(
const std::vector<std::vector<Field>>& first_vectors,
const std::vector<std::vector<Field>>& second_vectors);
template <class Field, class RandomNumberGenerator>
int linear_matroid_intersection_size(
const std::vector<std::vector<Field>>& first_vectors,
const std::vector<std::vector<Field>>& second_vectors,
RandomNumberGenerator& random);
template <class Field>
int linear_matroid_intersection_size_with_weights(
const std::vector<std::vector<Field>>& first_vectors,
const std::vector<std::vector<Field>>& second_vectors,
const std::vector<Field>& weights);
| Function | Description | Complexity |
|---|---|---|
linear_matroid_intersection_size(first, second) |
Returns the maximum common independent-set size using an internally seeded random evaluation. | $O(N(1+D_1D_2)+D_1D_2\min(D_1,D_2))$ |
linear_matroid_intersection_size(first, second, random) |
Uses the supplied random-number generator. | $O(N(1+D_1D_2)+D_1D_2\min(D_1,D_2))$ |
linear_matroid_intersection_size_with_weights(first, second, weights) |
Uses the explicit values weights[e] for $x_e$. This is deterministic, but adversarial values need not preserve the symbolic rank. |
$O(N(1+D_1D_2)+D_1D_2\min(D_1,D_2))$ |
Here $N$ is the ground-set size and $D_1,D_2$ are the two vector dimensions.
The randomized overloads use $O(N+D_1D_2)$ auxiliary memory, and the explicit
weight overload uses $O(D_1D_2)$. Inputs are not modified. weights must have
size $N$.
Example
#include "math/modint.hpp"
#include "matroid/linear_matroid_intersection.hpp"
#include <vector>
using mint = m1une::math::modint998244353;
int main() {
std::vector<std::vector<mint>> first(3), second(3);
first[0] = {1, 0};
first[1] = {0, 1};
first[2] = {1, 1};
second[0] = {1, 0};
second[1] = {1, 0};
second[2] = {0, 1};
int size =
m1une::matroid::linear_matroid_intersection_size(first, second);
// size == 2
}
Required by
Verified with
Code
#ifndef M1UNE_MATROID_LINEAR_MATROID_INTERSECTION_HPP
#define M1UNE_MATROID_LINEAR_MATROID_INTERSECTION_HPP 1
#include <cassert>
#include <chrono>
#include <cstdint>
#include <utility>
#include <vector>
namespace m1une {
namespace matroid {
namespace internal {
inline std::uint64_t linear_matroid_intersection_random() {
static std::uint64_t state = std::uint64_t(
std::chrono::steady_clock::now().time_since_epoch().count());
state += 0x9e3779b97f4a7c15ULL;
std::uint64_t value = state;
value = (value ^ (value >> 30)) * 0xbf58476d1ce4e5b9ULL;
value = (value ^ (value >> 27)) * 0x94d049bb133111ebULL;
return value ^ (value >> 31);
}
template <class Field>
int linear_matroid_intersection_matrix_rank(
std::vector<std::vector<Field>> matrix) {
const int row_count = int(matrix.size());
const int column_count = row_count == 0 ? 0 : int(matrix[0].size());
int rank = 0;
for (int column = 0; column < column_count && rank < row_count; column++) {
int pivot = rank;
while (pivot < row_count && matrix[pivot][column] == Field(0)) pivot++;
if (pivot == row_count) continue;
std::swap(matrix[rank], matrix[pivot]);
Field inverse = Field(1) / matrix[rank][column];
for (int j = column; j < column_count; j++) matrix[rank][j] *= inverse;
for (int row = rank + 1; row < row_count; row++) {
if (matrix[row][column] == Field(0)) continue;
Field factor = matrix[row][column];
for (int j = column; j < column_count; j++) {
matrix[row][j] -= factor * matrix[rank][j];
}
}
rank++;
}
return rank;
}
} // namespace internal
template <class Field>
int linear_matroid_intersection_size_with_weights(
const std::vector<std::vector<Field>>& first_vectors,
const std::vector<std::vector<Field>>& second_vectors,
const std::vector<Field>& weights) {
const int ground_size = int(first_vectors.size());
assert(int(second_vectors.size()) == ground_size);
assert(int(weights.size()) == ground_size);
if (ground_size == 0) return 0;
const int first_dimension = int(first_vectors[0].size());
const int second_dimension = int(second_vectors[0].size());
#ifndef NDEBUG
for (const auto& vector : first_vectors) {
assert(int(vector.size()) == first_dimension);
}
for (const auto& vector : second_vectors) {
assert(int(vector.size()) == second_dimension);
}
#endif
const bool transpose = second_dimension < first_dimension;
const int row_count = transpose ? second_dimension : first_dimension;
const int column_count = transpose ? first_dimension : second_dimension;
std::vector<std::vector<Field>> matrix(
row_count, std::vector<Field>(column_count, Field(0)));
for (int element = 0; element < ground_size; element++) {
const auto& row_vector =
transpose ? second_vectors[element] : first_vectors[element];
const auto& column_vector =
transpose ? first_vectors[element] : second_vectors[element];
for (int row = 0; row < row_count; row++) {
Field coefficient = weights[element] * row_vector[row];
if (coefficient == Field(0)) continue;
for (int column = 0; column < column_count; column++) {
matrix[row][column] += coefficient * column_vector[column];
}
}
}
return internal::linear_matroid_intersection_matrix_rank(std::move(matrix));
}
template <class Field, class RandomNumberGenerator>
int linear_matroid_intersection_size(
const std::vector<std::vector<Field>>& first_vectors,
const std::vector<std::vector<Field>>& second_vectors,
RandomNumberGenerator& random) {
assert(first_vectors.size() == second_vectors.size());
std::vector<Field> weights(first_vectors.size());
for (Field& weight : weights) weight = Field(random());
return linear_matroid_intersection_size_with_weights(
first_vectors, second_vectors, weights);
}
template <class Field>
int linear_matroid_intersection_size(
const std::vector<std::vector<Field>>& first_vectors,
const std::vector<std::vector<Field>>& second_vectors) {
assert(first_vectors.size() == second_vectors.size());
std::vector<Field> weights(first_vectors.size());
for (Field& weight : weights) {
weight = Field(internal::linear_matroid_intersection_random());
}
return linear_matroid_intersection_size_with_weights(
first_vectors, second_vectors, weights);
}
} // namespace matroid
} // namespace m1une
#endif // M1UNE_MATROID_LINEAR_MATROID_INTERSECTION_HPP#line 1 "matroid/linear_matroid_intersection.hpp"
#include <cassert>
#include <chrono>
#include <cstdint>
#include <utility>
#include <vector>
namespace m1une {
namespace matroid {
namespace internal {
inline std::uint64_t linear_matroid_intersection_random() {
static std::uint64_t state = std::uint64_t(
std::chrono::steady_clock::now().time_since_epoch().count());
state += 0x9e3779b97f4a7c15ULL;
std::uint64_t value = state;
value = (value ^ (value >> 30)) * 0xbf58476d1ce4e5b9ULL;
value = (value ^ (value >> 27)) * 0x94d049bb133111ebULL;
return value ^ (value >> 31);
}
template <class Field>
int linear_matroid_intersection_matrix_rank(
std::vector<std::vector<Field>> matrix) {
const int row_count = int(matrix.size());
const int column_count = row_count == 0 ? 0 : int(matrix[0].size());
int rank = 0;
for (int column = 0; column < column_count && rank < row_count; column++) {
int pivot = rank;
while (pivot < row_count && matrix[pivot][column] == Field(0)) pivot++;
if (pivot == row_count) continue;
std::swap(matrix[rank], matrix[pivot]);
Field inverse = Field(1) / matrix[rank][column];
for (int j = column; j < column_count; j++) matrix[rank][j] *= inverse;
for (int row = rank + 1; row < row_count; row++) {
if (matrix[row][column] == Field(0)) continue;
Field factor = matrix[row][column];
for (int j = column; j < column_count; j++) {
matrix[row][j] -= factor * matrix[rank][j];
}
}
rank++;
}
return rank;
}
} // namespace internal
template <class Field>
int linear_matroid_intersection_size_with_weights(
const std::vector<std::vector<Field>>& first_vectors,
const std::vector<std::vector<Field>>& second_vectors,
const std::vector<Field>& weights) {
const int ground_size = int(first_vectors.size());
assert(int(second_vectors.size()) == ground_size);
assert(int(weights.size()) == ground_size);
if (ground_size == 0) return 0;
const int first_dimension = int(first_vectors[0].size());
const int second_dimension = int(second_vectors[0].size());
#ifndef NDEBUG
for (const auto& vector : first_vectors) {
assert(int(vector.size()) == first_dimension);
}
for (const auto& vector : second_vectors) {
assert(int(vector.size()) == second_dimension);
}
#endif
const bool transpose = second_dimension < first_dimension;
const int row_count = transpose ? second_dimension : first_dimension;
const int column_count = transpose ? first_dimension : second_dimension;
std::vector<std::vector<Field>> matrix(
row_count, std::vector<Field>(column_count, Field(0)));
for (int element = 0; element < ground_size; element++) {
const auto& row_vector =
transpose ? second_vectors[element] : first_vectors[element];
const auto& column_vector =
transpose ? first_vectors[element] : second_vectors[element];
for (int row = 0; row < row_count; row++) {
Field coefficient = weights[element] * row_vector[row];
if (coefficient == Field(0)) continue;
for (int column = 0; column < column_count; column++) {
matrix[row][column] += coefficient * column_vector[column];
}
}
}
return internal::linear_matroid_intersection_matrix_rank(std::move(matrix));
}
template <class Field, class RandomNumberGenerator>
int linear_matroid_intersection_size(
const std::vector<std::vector<Field>>& first_vectors,
const std::vector<std::vector<Field>>& second_vectors,
RandomNumberGenerator& random) {
assert(first_vectors.size() == second_vectors.size());
std::vector<Field> weights(first_vectors.size());
for (Field& weight : weights) weight = Field(random());
return linear_matroid_intersection_size_with_weights(
first_vectors, second_vectors, weights);
}
template <class Field>
int linear_matroid_intersection_size(
const std::vector<std::vector<Field>>& first_vectors,
const std::vector<std::vector<Field>>& second_vectors) {
assert(first_vectors.size() == second_vectors.size());
std::vector<Field> weights(first_vectors.size());
for (Field& weight : weights) {
weight = Field(internal::linear_matroid_intersection_random());
}
return linear_matroid_intersection_size_with_weights(
first_vectors, second_vectors, weights);
}
} // namespace matroid
} // namespace m1une