library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub maspypy/library

:heavy_check_mark: linalg/matrix_rank.hpp

Required by

Verified with

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