galois.FieldArray.null_space() Self

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

Returns

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

Notes

Given an \(m \times n\) matrix \(\mathbf{A}\) over \(\mathrm{GF}(q)\), the null space of \(\mathbf{A}\) is the vector space \(\{\mathbf{x} \in \mathrm{GF}(q)^n\}\) that annihilates the columns of \(\mathbf{A}\), i.e. \(\mathbf{A}\mathbf{x} = \mathbf{0}\).

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

Examples

The null_space() method defines basis vectors (its rows) that span the null 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([[ 9, 16, 17,  1, 15],
    [30, 15, 21, 19, 24],
    [24,  4, 14, 15, 10]], order=31)

In [4]: N = A.null_space(); N
Out[4]: 
GF([[ 1,  0, 28, 13,  4],
    [ 0,  1,  8, 17, 28]], order=31)

The null space is the set of vectors that sum the columns to 0.

In [5]: A @ N.T
Out[5]: 
GF([[0, 0],
    [0, 0],
    [0, 0]], order=31)

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

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

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