linalg/matrix_rank.hpp

• View this file on GitHub
• Last update: 2024-01-19 02:38:11+09:00
• Include: #include "linalg/matrix_rank.hpp"

Required by

• graph/maximum_matching_size.hpp
• linalg/matrix_lowrank_update.hpp

Verified with

• test/library_checker/graph/general_matching.test.cpp
• test/library_checker/matrix/solve_linear.test.cpp
• test/mytest/matching.test.cpp
• test/mytest/matching_line_graph.test.cpp
• test/mytest/tutte.test.cpp
• test/yukicoder/1774.test.cpp

Code

template <typename T>
int matrix_rank(vc<vc<T>> a, int n = -1, int m = -1) {
  if (n == 0) return 0;
  if (n == -1) { n = len(a), m = len(a[0]); }
  assert(n == len(a) && m == len(a[0]));
  int rk = 0;
  FOR(j, m) {
    if (rk == n) break;
    if (a[rk][j] == 0) {
      FOR(i, rk + 1, n) if (a[i][j] != T(0)) {
        swap(a[rk], a[i]);
        break;
      }
    }
    if (a[rk][j] == 0) continue;
    T c = T(1) / a[rk][j];
    FOR(k, j, m) a[rk][k] *= c;
    FOR(i, rk + 1, n) {
      T c = a[i][j];
      FOR3(k, j, m) { a[i][k] -= a[rk][k] * c; }
    }
    ++rk;
  }
  return rk;
}

#line 1 "linalg/matrix_rank.hpp"
template <typename T>
int matrix_rank(vc<vc<T>> a, int n = -1, int m = -1) {
  if (n == 0) return 0;
  if (n == -1) { n = len(a), m = len(a[0]); }
  assert(n == len(a) && m == len(a[0]));
  int rk = 0;
  FOR(j, m) {
    if (rk == n) break;
    if (a[rk][j] == 0) {
      FOR(i, rk + 1, n) if (a[i][j] != T(0)) {
        swap(a[rk], a[i]);
        break;
      }
    }
    if (a[rk][j] == 0) continue;
    T c = T(1) / a[rk][j];
    FOR(k, j, m) a[rk][k] *= c;
    FOR(i, rk + 1, n) {
      T c = a[i][j];
      FOR3(k, j, m) { a[i][k] -= a[rk][k] * c; }
    }
    ++rk;
  }
  return rk;
}

Back to top page