galois.FieldArray.column_space() Self

Computes the column space of the matrix \(\mathbf{A}\).

Returns

The column space basis matrix. The rows of the basis matrix are the basis vectors that span the column space. The number of rows of the basis matrix is the dimension of the column space.

Notes

Given an \(m \times n\) matrix \(\mathbf{A}\) over \(\mathrm{GF}(q)\), the column space of \(\mathbf{A}\) is the vector space \(\{\mathbf{x} \in \mathrm{GF}(q)^m\}\) defined by all linear combinations of the columns of \(\mathbf{A}\). The column space has at most dimension \(\textrm{min}(m, n)\).

The column space has properties \(\mathcal{C}(\mathbf{A}) = \mathcal{R}(\mathbf{A}^T)\) and \(\textrm{dim}(\mathcal{C}(\mathbf{A})) + \textrm{dim}(\mathcal{N}(\mathbf{A})) = n\).

Examples

The column_space() method defines basis vectors (its rows) that span the column space of \(\mathbf{A}\).

In [1]: m, n = 3, 5

In [2]: GF = galois.GF(31)

In [3]: A = GF.Random((m, n)); A
Out[3]: 
GF([[ 0,  1, 30,  3, 14],
    [ 3, 16, 24,  5, 26],
    [ 2,  3, 23,  9, 18]], order=31)

In [4]: C = A.column_space(); C
Out[4]: 
GF([[1, 0, 0],
    [0, 1, 0],
    [0, 0, 1]], order=31)

The dimension of the column space and null space sum to \(n\).

In [5]: N = A.null_space(); N
Out[5]: 
GF([[ 1,  0, 14, 11, 23],
    [ 0,  1, 27, 22,  6]], order=31)

In [6]: C.shape[0] + N.shape[0] == n
Out[6]: True