Matrix Rank and Linear Independence

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute rank of an m x n real matrix using RREF with partial pivoting.
5
// Numerical stability: choose largest absolute pivot; treat |x| < eps as zero.
6
int rank_real(vector<vector<double>> A, double eps = 1e-9) {
7
    int m = (int)A.size();
8
    if (m == 0) return 0;
9
    int n = (int)A[0].size();
10
    int r = 0; // current pivot row, also counts pivots
11
    for (int c = 0; c < n && r < m; ++c) {
12
        // Find pivot row with max |A[i][c]| for i >= r
13
        int piv = r;
14
        for (int i = r + 1; i < m; ++i) {
15
            if (fabs(A[i][c]) > fabs(A[piv][c])) piv = i;
16
        }
17
        if (fabs(A[piv][c]) < eps) continue; // no pivot in this column
18
        swap(A[piv], A[r]);
19
        // Normalize pivot row so pivot becomes 1
20
        double div = A[r][c];
21
        for (int j = c; j < n; ++j) A[r][j] /= div;
22
        // Eliminate this column from all other rows
23
        for (int i = 0; i < m; ++i) if (i != r) {
24
            double factor = A[i][c];
25
            if (fabs(factor) < eps) continue;
26
            for (int j = c; j < n; ++j) A[i][j] -= factor * A[r][j];
27
        }
28
        ++r; // found a pivot
29
    }
30
    return r;
31
}
32
33
int main() {
34
    ios::sync_with_stdio(false);
35
    cin.tie(nullptr);
36
37
    int m, n;
38
    // Example input: first line m n, followed by m lines each with n entries.
39
    // 3 4
40
    // 1 2 3 4
41
    // 2 4 6 8
42
    // 0 1 0 1
43
    if (!(cin >> m >> n)) {
44
        // Demo fallback
45
        vector<vector<double>> A = {{1,2,3,4},{2,4,6,8},{0,1,0,1}};
46
        cout << rank_real(A) << "\n"; // Expected rank: 2
47
        return 0;
48
    }
49
    vector<vector<double>> A(m, vector<double>(n));
50
    for (int i = 0; i < m; ++i)
51
        for (int j = 0; j < n; ++j)
52
            cin >> A[i][j];
53
    cout << rank_real(A) << "\n";
54
    return 0;
55
}
56

1
#include <bits/stdc++.h>
2
using namespace std;
3
using int64 = long long;
4
5
int64 mod_pow(int64 a, int64 e, int64 p) {
6
    int64 r = 1 % p;
7
    a %= p;
8
    while (e) {
9
        if (e & 1) r = (__int128)r * a % p;
10
        a = (__int128)a * a % p;
11
        e >>= 1;
12
    }
13
    return r;
14
}
15
16
int64 mod_inv(int64 a, int64 p) {
17
    // p is prime: a^(p-2) mod p
18
    a %= p; if (a < 0) a += p;
19
    return mod_pow(a, p - 2, p);
20
}
21
22
int rank_mod_prime(vector<vector<int64>> A, int64 p) {
23
    int m = (int)A.size();
24
    if (m == 0) return 0;
25
    int n = (int)A[0].size();
26
    int r = 0;
27
    for (int c = 0; c < n && r < m; ++c) {
28
        int piv = -1;
29
        for (int i = r; i < m; ++i) if (A[i][c] % p != 0) { piv = i; break; }
30
        if (piv == -1) continue;
31
        swap(A[piv], A[r]);
32
        int64 inv = mod_inv(A[r][c], p);
33
        // Normalize pivot row
34
        for (int j = c; j < n; ++j) {
35
            A[r][j] = (__int128)A[r][j] * inv % p;
36
        }
37
        // Eliminate this column from other rows
38
        for (int i = 0; i < m; ++i) if (i != r) {
39
            int64 factor = A[i][c] % p; if (factor < 0) factor += p;
40
            if (factor == 0) continue;
41
            for (int j = c; j < n; ++j) {
42
                A[i][j] = (A[i][j] - (__int128)factor * A[r][j]) % p;
43
                if (A[i][j] < 0) A[i][j] += p;
44
            }
45
        }
46
        ++r;
47
    }
48
    return r;
49
}
50
51
int main() {
52
    ios::sync_with_stdio(false);
53
    cin.tie(nullptr);
54
55
    int m, n; long long p;
56
    // Input: m n p, then m lines each with n entries modulo p.
57
    // Example: 2 3 7 \n 1 2 3 \n 2 4 6  -> rank is 1 over GF(7)
58
    if (!(cin >> m >> n >> p)) {
59
        vector<vector<int64>> A = {{1,2,3},{2,4,6}}; p = 7;
60
        cout << rank_mod_prime(A, p) << "\n"; // 1
61
        return 0;
62
    }
63
    vector<vector<int64>> A(m, vector<int64>(n));
64
    for (int i = 0; i < m; ++i)
65
        for (int j = 0; j < n; ++j)
66
            cin >> A[i][j];
67
    int r = rank_mod_prime(A, p);
68
    cout << r << "\n";
69
    return 0;
70
}
71

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Maintain a linear basis over GF(2) for 64-bit integers.
5
// Insertion reduces the vector; if it becomes zero, it's dependent; otherwise it adds a new basis vector.
6
struct XorBasis64 {
7
    uint64_t b[64]{}; // b[i] has leading bit i
8
    int sz = 0;
9
10
    void insert(uint64_t x) {
11
        for (int i = 63; i >= 0; --i) if (x & (1ull << i)) {
12
            if (!b[i]) { b[i] = x; ++sz; return; }
13
            x ^= b[i];
14
        }
15
        // if x becomes 0, it's dependent and ignored
16
    }
17
18
    bool canRepresent(uint64_t x) const {
19
        for (int i = 63; i >= 0; --i) if (x & (1ull << i)) {
20
            if (!b[i]) return false;
21
            x ^= b[i];
22
        }
23
        return true; // reduced to 0
24
    }
25
26
    // Maximize x XOR y over all y in span
27
    uint64_t maximize(uint64_t x = 0) const {
28
        uint64_t res = x;
29
        for (int i = 63; i >= 0; --i) if (b[i]) {
30
            res = max(res, res ^ b[i]);
31
        }
32
        return res;
33
    }
34
};
35
36
int main() {
37
    ios::sync_with_stdio(false);
38
    cin.tie(nullptr);
39
40
    int n; // number of vectors
41
    // Example: n then n numbers; then q queries: type t and value v
42
    // t=1: ask if v is representable; t=2: print max XOR with v; t=3: print basis size (rank)
43
    if (!(cin >> n)) {
44
        XorBasis64 B; B.insert(5); B.insert(7); B.insert(2); // {0101, 0111, 0010}
45
        cout << B.sz << "\n";              // rank over GF(2)
46
        cout << B.canRepresent(5 ^ 7) << "\n"; // 1 (true)
47
        cout << B.maximize(0) << "\n";      // maximum XOR attainable
48
        return 0;
49
    }
50
    XorBasis64 B;
51
    for (int i = 0; i < n; ++i) { uint64_t x; cin >> x; B.insert(x); }
52
    int q; cin >> q;
53
    while (q--) {
54
        int t; uint64_t v; cin >> t >> v;
55
        if (t == 1) cout << (B.canRepresent(v) ? "YES" : "NO") << "\n";
56
        else if (t == 2) cout << B.maximize(v) << "\n";
57
        else if (t == 3) cout << B.sz << "\n";
58
    }
59
    return 0;
60
}
61

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct RREFResult {
5
    int rank;
6
    vector<int> pivot_col;     // pivot column indices in order of pivot rows
7
    vector<vector<double>> M;  // RREF of augmented matrix [A|b]
8
    bool consistent;
9
};
10
11
RREFResult rref_augmented(vector<vector<double>> Ab, double eps = 1e-9) {
12
    int m = (int)Ab.size();
13
    int n_aug = (int)Ab[0].size(); // n + 1 (augmented)
14
    int n = n_aug - 1;
15
    int r = 0; // pivot row
16
    vector<int> pivcol;
17
    for (int c = 0; c < n && r < m; ++c) {
18
        int piv = r;
19
        for (int i = r + 1; i < m; ++i)
20
            if (fabs(Ab[i][c]) > fabs(Ab[piv][c])) piv = i;
21
        if (fabs(Ab[piv][c]) < eps) continue;
22
        swap(Ab[piv], Ab[r]);
23
        double div = Ab[r][c];
24
        for (int j = c; j < n_aug; ++j) Ab[r][j] /= div;
25
        for (int i = 0; i < m; ++i) if (i != r) {
26
            double f = Ab[i][c]; if (fabs(f) < eps) continue;
27
            for (int j = c; j < n_aug; ++j) Ab[i][j] -= f * Ab[r][j];
28
        }
29
        pivcol.push_back(c);
30
        ++r;
31
    }
32
    // Check consistency: any row with all zeros in A part but nonzero in b?
33
    bool consistent = true;
34
    for (int i = 0; i < m; ++i) {
35
        bool allzero = true;
36
        for (int j = 0; j < n; ++j) allzero &= fabs(Ab[i][j]) < eps;
37
        if (allzero && fabs(Ab[i][n]) > eps) { consistent = false; break; }
38
    }
39
    return {r, pivcol, Ab, consistent};
40
}
41
42
int main() {
43
    ios::sync_with_stdio(false);
44
    cin.tie(nullptr);
45
46
    int m, n;
47
    // Input: m n, then A (m x n), then b (m entries)
48
    // Example:
49
    // 2 3
50
    // 1 2 0
51
    // 0 1 1
52
    // 3 2
53
    if (!(cin >> m >> n)) {
54
        vector<vector<double>> A = {{1,2,0},{0,1,1}}; vector<double> b = {3,2};
55
        vector<vector<double>> Ab(m, vector<double>(n+1));
56
        for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) Ab[i][j] = A[i][j]; Ab[i][n] = b[i]; }
57
        auto res = rref_augmented(Ab);
58
        cout << (res.consistent ? "CONSISTENT\n" : "INCONSISTENT\n");
59
        cout << "rank(A) = " << res.rank << "\n";
60
        if (res.consistent) {
61
            // Particular solution: set all free vars = 0, read pivot vars from RHS
62
            vector<double> x(n, 0.0);
63
            for (int i = 0; i < (int)res.pivot_col.size(); ++i) {
64
                int c = res.pivot_col[i];
65
                x[c] = res.M[i][n];
66
            }
67
            cout << "one solution:";
68
            for (int j = 0; j < n; ++j) cout << ' ' << fixed << setprecision(9) << x[j];
69
            cout << "\n";
70
            // Null space basis: one vector per free variable f
71
            vector<int> is_pivot(n, 0);
72
            for (int c : res.pivot_col) is_pivot[c] = 1;
73
            vector<int> free_cols;
74
            for (int j = 0; j < n; ++j) if (!is_pivot[j]) free_cols.push_back(j);
75
            cout << "nullity = " << free_cols.size() << "\n";
76
            for (int idx = 0; idx < (int)free_cols.size(); ++idx) {
77
                int f = free_cols[idx];
78
                vector<double> v(n, 0.0);
79
                v[f] = 1.0; // set free var = 1
80
                // For each pivot row i with pivot at c, x_c = -sum_j (row[i][j] * x_j) when j is free
81
                for (int i = 0; i < (int)res.pivot_col.size(); ++i) {
82
                    int c = res.pivot_col[i];
83
                    v[c] = -res.M[i][f];
84
                }
85
                cout << "null vector " << idx << ":";
86
                for (int j = 0; j < n; ++j) cout << ' ' << fixed << setprecision(9) << v[j];
87
                cout << "\n";
88
            }
89
        }
90
        return 0;
91
    }
92
93
    vector<vector<double>> Ab(m, vector<double>(n+1));
94
    for (int i = 0; i < m; ++i)
95
        for (int j = 0; j < n; ++j)
96
            cin >> Ab[i][j];
97
    for (int i = 0; i < m; ++i) cin >> Ab[i][n];
98
99
    auto res = rref_augmented(Ab);
100
    cout << (res.consistent ? "CONSISTENT\n" : "INCONSISTENT\n");
101
    cout << "rank(A) = " << res.rank << "\n";
102
    if (res.consistent) {
103
        vector<double> x(n, 0.0);
104
        for (int i = 0; i < (int)res.pivot_col.size(); ++i) x[res.pivot_col[i]] = res.M[i][n];
105
        cout << "one solution:";
106
        for (int j = 0; j < n; ++j) cout << ' ' << fixed << setprecision(9) << x[j];
107
        cout << "\n";
108
        vector<int> is_pivot(n, 0);
109
        for (int c : res.pivot_col) is_pivot[c] = 1;
110
        vector<int> free_cols; for (int j = 0; j < n; ++j) if (!is_pivot[j]) free_cols.push_back(j);
111
        cout << "nullity = " << free_cols.size() << "\n";
112
        for (int idx = 0; idx < (int)free_cols.size(); ++idx) {
113
            int f = free_cols[idx];
114
            vector<double> v(n, 0.0); v[f] = 1.0;
115
            for (int i = 0; i < (int)res.pivot_col.size(); ++i) v[res.pivot_col[i]] = -res.M[i][f];
116
            cout << "null vector " << idx << ":";
117
            for (int j = 0; j < n; ++j) cout << ' ' << fixed << setprecision(9) << v[j];
118
            cout << "\n";
119
        }
120
    }
121
    return 0;
122
}
123