Skip to Content
ReferenceLibrary

matrix

A dense rows x cols matrix stored flat in row-major order.

Generated from spec/std/matrix.cp by cpl doc --format json.

Mat

pub struct Mat<T>

A dense rows x cols matrix stored flat in row-major order.

Source

Mat.new

fn new<R, C, S>(a: [R, C]T, over: ?S = None) -> Mat<T>

A matrix from a 2-D table, multiplied under over (default Semiring(+, *)): Mat(over: Semiring(min, +), d). m * m2, pow(m, k) and a SegTree(*, ...) of matrices all use it. O(rows * cols).

Row i is R's i-th position and column j is C's j-th, so get(i, j) reads a[R.nth(i), C.nth(j)]; the matrix has |R| rows and |C| columns. The keys are not kept.

  • cost: O(rows * cols) time and space
  • empty: a matrix with zero rows or columns
  • traps: never

Examples:

  • domain R = 0..2; domain C = 0..3; Mat([R, C] (r, c) => 10 * Int(r) + Int(c)).get(1, 2) == 12

Source

Mat.filled

fn filled<S>(rows: Int, cols: Int, fill: T, over: ?S = None) -> Mat<T>

A rows x cols matrix with every entry fill, multiplied under over (default Semiring(+, *)).

  • cost: O(rows * cols) time and space
  • traps: when rows < 0 or cols < 0

Examples:

  • Mat<Int>.filled(2, 3, 7).get(1, 2) == 7

Source

Mat.zeros

fn zeros(rows: Int, cols: Int) -> Mat<T>

A rows x cols matrix of T.zero.

  • cost: O(rows * cols) time and space
  • traps: when rows < 0 or cols < 0

Examples:

  • Mat<Int>.zeros(2, 3).get(1, 2) == 0

Source

Mat.identity

fn identity(n: Int) -> Mat<T>

The n x n identity matrix: T.one on the diagonal, T.zero elsewhere.

  • cost: O(n^2) time and space
  • traps: when n < 0

Examples:

  • let m = Mat<Int>.identity(3); m.get(1, 1) == 1 and m.get(1, 2) == 0

Source

Mat.from_flat

fn from_flat(rows: Int, cols: Int, data: List<T>) -> Mat<T>

Build a rows x cols matrix from a flat row-major list of length rows * cols: entry (r, c) is data[r * cols + c].

  • cost: O(rows * cols) time and space
  • empty: a matrix with zero rows or columns when data is empty
  • traps: when rows < 0, cols < 0 or data.len != rows * cols

Examples:

  • Mat<Int>.from_flat(2, 3, [1, 2, 3, 4, 5, 6]).get(1, 0) == 4

Source

Mat.from_rows

fn from_rows(grid: List<List<T>>) -> Mat<T>

Build a matrix from a list of equal-length rows: grid[r][c] is entry (r, c).

  • cost: O(rows * cols) time and space
  • empty: [] gives the 0 x 0 matrix
  • traps: when the rows differ in length

Examples:

  • Mat<Int>.from_rows([[1, 2], [3, 4]]).get(1, 0) == 3

Source

Mat.get

fn get(self, r: Int, c: Int) -> T

The entry at (r, c), 0-based.

  • cost: O(1)
  • traps: when r is not in 0..rows or c is not in 0..cols

Examples:

  • Mat<Int>.from_rows([[1, 2], [3, 4]]).get(0, 1) == 2

Source

Mat.set

fn set(mut self, r: Int, c: Int, val: T)

Set the entry at (r, c) to val.

  • cost: O(1)
  • traps: when r is not in 0..rows or c is not in 0..cols

Examples:

  • var m = Mat<Int>.zeros(2, 2); m.set(1, 0, 5); m.get(1, 0) == 5

Source

Mat.at

fn at(self, r: Int, c: Int) -> lends mut T

The entry at (r, c), lent in place: m.at(i, j) += x.

  • cost: O(1)
  • traps: when r is not in 0..rows or c is not in 0..cols

Examples:

  • var m = Mat<Int>.identity(2); m.at(0, 0) += 4; m.get(0, 0) == 5

Source

Mat.transpose

fn transpose(self) -> Mat<T>

The transpose, a new cols x rows matrix with entry (c, r) equal to self's (r, c).

  • cost: O(rows * cols) time and space
  • traps: never

Examples:

  • Mat<Int>.from_rows([[1, 2, 3], [4, 5, 6]]).transpose().get(2, 1) == 6

Source

Mat.mul_vec

fn mul_vec(self, v: List<T>) -> List<T>

The matrix-vector product self * v under the matrix's semiring: entry r folds get(r, c) * v[c] over c with the semiring's addition.

  • cost: O(rows * cols) time, O(rows) space
  • empty: rows copies of the semiring's zero when cols == 0
  • order: indexed by row
  • traps: when v.len != cols

Examples:

  • Mat<Int>.from_rows([[1, 2], [3, 4]]).mul_vec([1, 1]) == [3, 7]

Source

Mat.product

fn product(n: Int) -> Monoid<Mat<T>>

The matrix-multiplication monoid for n x n matrices (usable in SegTree): identity Mat.identity(n), op *, which is associative but not commutative.

  • cost: O(n^2) time and space (for the identity)
  • traps: when n < 0

Examples:

  • let m = Mat<Int>.product(2); m.op(m.id, Mat<Int>.from_rows([[1, 2], [3, 4]])).get(1, 1) == 4

Source

Mat.det

fn det(self) -> T

The determinant over an exact field (such as Mod<P> for prime P), by Gaussian elimination. The 0 x 0 determinant is T.one.

  • cost: O(n^3) time, O(n^2) space
  • traps: when the matrix is not square, or an inverse it needs does not exist (a non-field T)

Examples:

  • Mat<Mod<7>>.from_rows([[1, 2], [3, 4]]).det() == Mod<7>(5)
  • Mat<Mod<7>>.from_rows([[1, 2], [2, 4]]).det() == Mod<7>(0)

Source

Mat.rank

fn rank(self) -> Int

The rank over an exact field: the number of pivots elimination finds.

  • cost: O(rows * cols * min(rows, cols)) time, O(rows * cols) space
  • empty: zero
  • traps: never for a field T

Examples:

  • Mat<Mod<7>>.from_rows([[1, 2], [2, 4]]).rank() == 1

Source

Mat.solve_space

fn solve_space(self, b: List<T>) -> ?(List<T>, List<List<T>>)

Solve self * x = b over an exact field. Returns (particular, nullspace_basis) or None. Every solution has the form particular + sum(c_i * basis[i]). O(rows * cols * min(rows, cols)).

particular is the solution with every free variable zero (what solve returns). The basis has one vector per free (non-pivot) column of the reduced row echelon form, in increasing column order; the vector for free column f has 1 at f, 0 at the other free columns, and whatever the pivot columns need. It is empty when the solution is unique.

  • cost: O(rows * cols * min(rows, cols)) time, O(rows * cols) space
  • empty: with cols == 0, Some(([], [])) when b is all zero, else None
  • order: basis vectors by increasing free column
  • traps: when b.len != rows

Examples:

  • Mat<Mod<7>>.from_rows([[1, 2], [2, 4]]).solve_space([1, 2]) == Some(([Mod<7>(1), Mod<7>(0)], [[Mod<7>(5), Mod<7>(1)]]))
  • Mat<Mod<7>>.from_rows([[1, 2], [2, 4]]).solve_space([1, 0]) == None

Source

Mat.solve

fn solve(self, b: List<T>) -> ?List<T>

Solve self * x = b over an exact field. Returns one solution (free variables 0) or None.

The solution is solve_space(b)'s particular one: each free (non-pivot) column's variable is zero.

  • cost: O(rows * cols * min(rows, cols)) time, O(rows * cols) space
  • empty: with cols == 0, Some([]) when b is all zero, else None
  • order: indexed by column (variable)
  • traps: when b.len != rows

Examples:

  • Mat<Mod<7>>.from_rows([[1, 2], [3, 4]]).solve([5, 6]) == Some([Mod<7>(3), Mod<7>(1)])
  • Mat<Mod<7>>.from_rows([[1, 2], [2, 4]]).solve([1, 0]) == None

Source

Mat.inverse

fn inverse(self) -> ?Mat<T>

The multiplicative inverse of a square matrix over an exact field, or None if singular, by Gauss-Jordan elimination.

  • cost: O(n^3) time, O(n^2) space
  • empty: the 0 x 0 matrix is its own inverse
  • traps: when the matrix is not square

Examples:

  • let inv = Mat<Mod<7>>.from_rows([[1, 2], [3, 4]]).inverse()!; inv.get(0, 0) == Mod<7>(5) and inv.get(1, 1) == Mod<7>(3)
  • Mat<Mod<7>>.from_rows([[1, 2], [2, 4]]).inverse() == None

Source

Mat.rref

fn rref(self) -> (mat: Mat<T>, rank: Int, pivots: List<Int>)

The reduced row echelon form (rref_mat, rank, pivot_cols) over a field. Every pivot is T.one, every other entry of a pivot column is zero, the nonzero rows come first, and the rank pivot columns are listed in increasing order. The RREF is unique, so so is the result.

  • cost: O(rows * cols * min(rows, cols)) time, O(rows * cols) space
  • empty: rank zero, no pivots
  • order: pivot columns increasing
  • traps: never for a field T

Examples:

  • let (mat: e, rank: k, pivots: p) = Mat<Mod<7>>.from_rows([[2, 4], [1, 2]]).rref(); k == 1 and p == [0] and e.get(0, 1) == Mod<7>(2) and e.get(1, 1) == Mod<7>(0)

Source

Mat.det_mod

fn det_mod(self, m: Int) -> Int

The determinant modulo any (possibly composite) m >= 1, in 0..m, by Euclidean (gcd-style) row elimination, so no inverse is needed. Entries are reduced modulo m first, negative ones included.

  • cost: O(n^3 log m)
  • empty: 1 % m for the 0 x 0 matrix
  • traps: when the matrix is not square or m < 1

Examples:

  • Mat<Int>.from_rows([[1, 2], [3, 4]]).det_mod(6) == 4
  • Mat<Int>.from_rows([[2, 0], [0, 3]]).det_mod(6) == 0

Source

Mat.char_poly

fn char_poly(self) -> List<T>

The characteristic polynomial det(xI - self), lowest degree first, via Hessenberg reduction: n + 1 coefficients, the last one T.one.

  • cost: O(n^3) time, O(n^2) space
  • empty: [T.one] for the 0 x 0 matrix
  • order: coefficient of x^0 first
  • traps: when the matrix is not square

Examples:

  • Mat<Mod<7>>.from_rows([[1, 2], [3, 4]]).char_poly() == [Mod<7>(5), Mod<7>(2), Mod<7>(1)]

Source

Mat.pfaffian

fn pfaffian(self) -> T

The Pfaffian of an even-order skew-symmetric matrix over a field, with the sign convention pf([[0, a], [-a, 0]]) == a; pf(A)^2 == det(A). Only the entries above the diagonal are read; skew-symmetry is not checked.

  • cost: O(n^3) time, O(n^2) space
  • empty: T.one for the 0 x 0 matrix
  • traps: when the matrix is not square or n is odd

Examples:

  • Mat<Mod<7>>.from_rows([[0, 3], [4, 0]]).pfaffian() == Mod<7>(3)

Source

Mat.adjugate

fn adjugate(self) -> Mat<T>

The adjugate matrix adj(self), the transpose of the cofactor matrix, so self * adj(self) == det(self) * I. Defined even when rank == n - 1 (and zero when rank < n - 1).

  • cost: O(n^3) time, O(n^2) space
  • empty: the 0 x 0 matrix
  • traps: when the matrix is not square

Examples:

  • let a = Mat<Mod<7>>.from_rows([[1, 2], [3, 4]]).adjugate(); a.get(0, 0) == Mod<7>(4) and a.get(0, 1) == Mod<7>(5)
  • Mat<Mod<7>>.from_rows([[5]]).adjugate().get(0, 0) == Mod<7>(1)

Source

Mat<T>

impl Add for Mat<T>

Source

Mat<T>.add

fn add(a, b)

Source

Mat<T>

impl Sub for Mat<T>

Source

Mat<T>.sub

fn sub(a, b)

Source

Mat<T>

impl Mul for Mat<T>

Source

Mat<T>.mul

fn mul(a, b)

Source

Mat<T>

impl Pow for Mat<T>

Source

Mat<T>.pow

fn pow(a, e: Int) -> Mat<T>

Source

XorBasis

pub struct XorBasis

Linear basis over GF(2) for non-negative 63-bit integers (0 <= x < 2^63). Every operation is O(W) where W <= 63 (merge is O(W * rank)).

Source

XorBasis.new

fn new() -> XorBasis

An empty basis of rank 0, whose span is {0}.

  • cost: O(W)
  • traps: never

Examples:

  • XorBasis().rank == 0

Source

XorBasis.rank

fn rank(self) -> Int

The number of linearly independent vectors in the basis: the span has 2^rank elements.

  • cost: O(1)
  • traps: never

Examples:

  • var b = XorBasis(); b.add(6); b.add(5); b.add(3); b.rank == 2

Source

XorBasis.add

fn add(mut self, x: Int) -> Bool

Insert x >= 0 into the basis. Returns true iff the rank increased, that is, iff x was not already in the span (0 never is new). The basis is kept fully reduced: no vector has another vector's highest bit set.

  • cost: O(W)
  • traps: when x < 0

Examples:

  • var b = XorBasis(); let p = b.add(6); let q = b.add(5); let r = b.add(3); p and q and not r
  • not XorBasis().add(0)

Source

XorBasis.reduce

fn reduce(self, x: Int) -> Int

Reduce x >= 0 against the basis: the minimum of x ^ s over s in the span, which is 0 iff x is in the span.

  • cost: O(W)
  • traps: when x < 0

Examples:

  • var b = XorBasis(); b.add(6); b.add(5); b.reduce(4) == 1 and b.reduce(3) == 0

Source

XorBasis.contains

fn contains(self, x: Int) -> Bool

Whether x >= 0 is a XOR-combination of basis vectors: reduce(x) == 0.

  • cost: O(W)
  • traps: when x < 0

Examples:

  • var b = XorBasis(); b.add(6); b.add(5); b.contains(3) and not b.contains(4)

Source

XorBasis.max_xor

fn max_xor(self, init: Int = 0) -> Int

The maximum value of init ^ s over all s in the span.

  • cost: O(W)
  • ties: None possible; the maximum value is unique
  • traps: when init < 0

Examples:

  • var b = XorBasis(); b.add(6); b.add(5); b.max_xor() == 6 and b.max_xor(1) == 7

Source

XorBasis.min_xor

fn min_xor(self, init: Int = 0) -> Int

The minimum value of init ^ s over all s in the span: the same as reduce(init), and 0 for the default init.

  • cost: O(W)
  • ties: None possible; the minimum value is unique
  • traps: when init < 0

Examples:

  • var b = XorBasis(); b.add(6); b.add(5); b.min_xor(4) == 1 and b.min_xor() == 0

Source

XorBasis.kth

fn kth(self, k: Int) -> ?Int

The 0-indexed k-th smallest value in the span, or None if k < 0 or k >= 2^rank. kth(0) is 0, and kth over 0..2^rank is strictly increasing and lists the whole span.

  • cost: O(W^2)
  • empty: only kth(0) == Some(0) for an empty basis
  • ties: None possible; span values are distinct
  • traps: never

Examples:

  • var b = XorBasis(); b.add(6); b.add(5); [b.kth(k) for k in 0..5] == [Some(0), Some(3), Some(5), Some(6), None]

Source

XorBasis.merge

fn merge(mut self, o: XorBasis)

Merge another basis into self, so self spans the union of both spans; o is unchanged.

  • cost: O(W * o.rank)
  • traps: never

Examples:

  • var a = XorBasis(); a.add(6); var b = XorBasis(); b.add(8); a.merge(b); a.rank == 2 and a.contains(14)

Source

XorBasis.monoid

fn monoid() -> Monoid<XorBasis>

The monoid under basis merge (usable in SegTree): identity the empty basis, op the merged basis. Commutative and idempotent on spans.

  • cost: O(W) (for the identity)
  • traps: never

Examples:

  • let m = XorBasis.monoid(); m.id.rank == 0

Source

XorBasis.basis_vecs

fn basis_vecs(self) -> List<Int>

The independent basis vectors currently stored, fully reduced (no vector has another's highest bit set), so the list depends only on the span. One vector per rank.

  • cost: O(W) time and space
  • empty: []
  • order: decreasing (by highest set bit)
  • traps: never

Examples:

  • var b = XorBasis(); b.add(6); b.add(5); b.basis_vecs() == [5, 3]

Source

XorBasis.intersect

fn intersect(self, o: XorBasis) -> XorBasis

A new basis spanning the intersection of the two GF(2) vector subspaces.

  • cost: O(W^2)
  • traps: never

Examples:

  • var a = XorBasis(); a.add(6); a.add(5); var b = XorBasis(); b.add(3); b.add(8); let c = a.intersect(b); c.rank == 1 and c.contains(3)

Source

MatPow

pub struct MatPow<T>

O(n^3 log max_exp) build, O(n^2 log e) query. Precomputed binary powers of a square matrix for fast multi-query A^e * v.

Source

MatPow.new

fn new(a: Mat<T>, max_exp: Int) -> MatPow<T>

Precompute a^(2^k) for every k with 2^k <= max_exp, multiplied under a's semiring.

  • cost: O(n^3 log max_exp) time, O(n^2 log max_exp) space
  • traps: when a is not square or max_exp < 0

Examples:

  • let p = MatPow(Mat<Int>.from_rows([[1, 1], [1, 0]]), 10); p.apply_pow(5, [1, 0]) == [8, 5]

Source

MatPow.apply_pow

fn apply_pow(self, e: Int, v: List<T>) -> List<T>

Compute a^e * v for 0 <= e <= max_exp, as matrix-vector products with the stored powers for the set bits of e. e == 0 returns v.

  • cost: O(n^2 log e) time, O(n) space
  • empty: v itself when e == 0
  • order: indexed by row
  • traps: when e is not in 0..=max_exp or v.len != n

Examples:

  • let p = MatPow(Mat<Int>.from_rows([[1, 1], [1, 0]]), 10); p.apply_pow(0, [1, 0]) == [1, 0]

Source

BitMat

pub struct BitMat(rows: Int, cols: Int)

O(n * m / 64) storage. Bit-packed dense matrix over GF(2) with word-parallel elimination.

Source

BitMat.new

fn new(rows: Int, cols: Int) -> BitMat

A zero GF(2) matrix of rows x cols, one bit per entry.

  • cost: O(rows * cols / 64) time and space
  • traps: when rows < 0 or cols < 0

Examples:

  • BitMat(2, 3).rank() == 0

Source

BitMat.identity

fn identity(n: Int) -> BitMat

The n x n GF(2) identity matrix.

  • cost: O(n^2 / 64) time and space
  • traps: when n < 0

Examples:

  • BitMat.identity(3).get(1, 1) and not BitMat.identity(3).get(1, 2)

Source

BitMat.get

fn get(self, r: Int, c: Int) -> Bool

Read bit (r, c).

  • cost: O(1)
  • traps: when r is not in 0..rows or c is not in 0..cols

Examples:

  • var m = BitMat(2, 2); m.set(0, 1, true); m.get(0, 1) and not m.get(1, 0)

Source

BitMat.set

fn set(mut self, r: Int, c: Int, v: Bool)

Write bit (r, c).

  • cost: O(1)
  • traps: when r is not in 0..rows or c is not in 0..cols

Examples:

  • var m = BitMat(2, 2); m.set(0, 1, true); m.set(0, 1, false); not m.get(0, 1)

Source

BitMat.det

fn det(self) -> Bool

The determinant over GF(2): true iff the matrix is invertible. The 0 x 0 determinant is true.

  • cost: O(n^3 / 64)
  • traps: when the matrix is not square

Examples:

  • var m = BitMat.identity(2); m.set(0, 1, true); m.det()
  • var m = BitMat(2, 2); m.set(0, 0, true); m.set(1, 0, true); not m.det()

Source

BitMat.rank

fn rank(self) -> Int

The rank over GF(2).

  • cost: O(rows * cols * min(rows, cols) / 64)
  • empty: zero
  • traps: never

Examples:

  • var m = BitMat(2, 2); m.set(0, 0, true); m.set(0, 1, true); m.set(1, 0, true); m.set(1, 1, true); m.rank() == 1

Source

BitMat.solve

fn solve(self, b: List<Bool>) -> ?List<Bool>

Any solution to self * x == b over GF(2), or None: the one with every free (non-pivot) variable false, as in Mat.solve.

  • cost: O(rows * cols * min(rows, cols) / 64)
  • empty: with cols == 0, Some([]) when b is all false, else None
  • order: indexed by column (variable)
  • traps: when b.len != rows

Examples:

  • var m = BitMat.identity(2); m.set(0, 1, true); m.solve([true, true]) == Some([false, true])
  • var m = BitMat(2, 2); m.set(0, 0, true); m.set(0, 1, true); m.set(1, 0, true); m.set(1, 1, true); m.solve([true, false]) == None

Source

BitMat.solve_space

fn solve_space(self, b: List<Bool>) -> ?(x0: List<Bool>, basis: List<List<Bool>>)

One solution x0 and a nullspace basis over GF(2), or None. x0 is solve(b)'s solution; the basis has one vector per free column, in increasing column order, with true at that column and false at the other free columns, as in Mat.solve_space.

  • cost: O(rows * cols * min(rows, cols) / 64)
  • empty: with cols == 0, Some(([], [])) when b is all false, else None
  • order: basis vectors by increasing free column
  • traps: when b.len != rows

Examples:

  • var m = BitMat(2, 2); m.set(0, 0, true); m.set(0, 1, true); m.set(1, 0, true); m.set(1, 1, true); m.solve_space([true, true]) == Some((x0: [true, false], basis: [[true, true]]))

Source

BitMat.inverse

fn inverse(self) -> ?BitMat

The inverse of a square GF(2) matrix, or None when it is singular.

  • cost: O(n^3 / 64)
  • empty: the 0 x 0 matrix
  • traps: when the matrix is not square

Examples:

  • var m = BitMat.identity(2); m.set(0, 1, true); let inv = m.inverse()!; inv.get(0, 1) and inv.get(1, 1) and not inv.get(1, 0)

Source

BitMat.mul

fn mul(self, o: BitMat) -> BitMat

The matrix product self * o over GF(2) (AND for multiply, XOR for add).

  • cost: O(rows * cols * o.cols / 64)
  • traps: when self.cols != o.rows

Examples:

  • var m = BitMat.identity(2); m.set(0, 1, true); let p = m.mul(m); not p.get(0, 1) and p.get(0, 0)

Source

PrefixXorBasis

pub struct PrefixXorBasis

O(62) per push and query. Online prefix linear basis answering subarray XOR queries over any range r.

Source

PrefixXorBasis.new

fn new() -> PrefixXorBasis

An empty prefix XOR basis, with no positions pushed.

  • cost: O(1)
  • traps: never

Examples:

  • PrefixXorBasis().rank(0..0) == 0

Source

PrefixXorBasis.push

fn push(mut self, x: Int)

Append x at the next position (0, 1, ...), keeping for each bit the basis vector with the rightmost source index, so any subarray's span reads off the vectors whose index lies in it.

  • cost: O(62) time and space
  • traps: when x < 0 or x >= 2^62

Examples:

  • var p = PrefixXorBasis(); p.push(6); p.push(5); p.rank(0..2) == 2

Source

PrefixXorBasis.max_xor

fn max_xor(self, r: Range<Int>, init: Int = 0) -> Int

The maximum init ^ s for s in the span of the values at positions r.

  • cost: O(62)
  • empty: init (the span of nothing is {0})
  • ties: None possible; the maximum value is unique
  • traps: when r is non-empty and reaches outside 0..len, or init < 0

Examples:

  • var p = PrefixXorBasis(); p.push(6); p.push(5); p.push(3); p.max_xor(1..3) == 6 and p.max_xor(2..3) == 3

Source

PrefixXorBasis.contains

fn contains(self, r: Range<Int>, x: Int) -> Bool

Whether x is in the span of the values at positions r.

  • cost: O(62)
  • empty: true only for x == 0
  • traps: when r is non-empty and reaches outside 0..len, or x < 0

Examples:

  • var p = PrefixXorBasis(); p.push(6); p.push(5); p.push(3); p.contains(1..3, 6) and not p.contains(1..2, 3)

Source

PrefixXorBasis.rank

fn rank(self, r: Range<Int>) -> Int

The rank (dimension) of the span of the values at positions r.

  • cost: O(62)
  • empty: zero
  • traps: when r is non-empty and reaches outside 0..len

Examples:

  • var p = PrefixXorBasis(); p.push(6); p.push(5); p.push(3); p.rank(0..3) == 2 and p.rank(2..3) == 1

Source

On this page