GF2::Matrix — Echelon Forms
Converts a matrix to row-echelon form or reduced-row-echelon form
Member functions that work in-place
Matrix& to_echelon_form(Vector *p = 0); (1)
Matrix& to_reduced_echelon_form(Vector *p = 0); (2)| 1 | Converts this matrix in place to row-echelon form. |
| 2 | Converts this matrix in place to reduced-row-echelon form. |
Non-member functions that work on copies
Matrix GF2::echelon_form(const Matrix &A, Vector *p = 0); (1)
Matrix GF2::reduced_echelon_form(const Matrix &A, Vector *p = 0); (2)| 1 | Returns the row-echelon form of A. Leaves A unchanged. |
| 2 | Returns the reduced-row-echelon form of A. Leaves A unchanged. |
Pivots & free variables
The methods both take an optional pointer to another bit-vector p.
If that p is present then on return p→element(j) == 1 means that column j now contains a pivot for the bit-matrix.
The rank of the bit-matrix will be p→count() and the number of free variables will be rows() - p→count().
The indices of the free variables will be indicated by p→flip();.
See the example below.
If present, the bit-vector pointed to by p will be resized appropriately.
Example
#include <GF2/GF2.h>
int
main()
{
// Create a matrix and get its echelon & reduced echelon forms
auto A = GF2::Matrix<>::random(12);
GF2::Vector<> pivots;
std::cout << "Original, Row-Echelon, Reduced-Row-Echelon versions of a GF2::Matrix:\n";
GF2::print(A, echelon_form(A), reduced_echelon_form(A, &pivots));
// Analyze the rank of the matrix etc.
auto n = A.rows();
auto r = pivots.count();
auto f = n - r;
std::cout << "Matrix size: " << n << " x " << n << '\n';
std::cout << "Matrix rank: " << r << '\n';
std::cout << "Number of free variables: " << f << "\n";
if (f > 0) {
std::cout << "Indices of free variables: ";
pivots.flip().if_set_call([](std::size_t k) { std::cout << k << ' '; });
}
std::cout << std::endl;
return 0;
}Output (specific values depends on the random fill)
Original, Row-Echelon, Reduced-Row-Echelon versions of a GF2::Matrix:
010000000111 111001001001 100000000001
001001000000 010000000111 010000000000
111001001001 001001000000 001001000000
001100111111 000101111111 000101000001
001010110000 000011110000 000011000001
000011100000 000000100110 000000100001
110011100110 000000011111 000000010000
000011110010 000000001111 000000001000
101111011001 000000000111 000000000101
100101010111 000000000010 000000000010
001100111101 000000000000 000000000000
110101001010 000000000000 000000000000
Matrix size: 12 x 12
Matrix rank: 10
Number of free variables: 2
Indices of free variables: 5 11See Also