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([[12, 22, 11,  3,  7],
    [29,  6, 19, 13, 16],
    [16,  5, 13, 18, 21]], order=31)

In [4]: N = A.null_space(); N
Out[4]: 
GF([[ 1,  0,  8, 20, 17],
    [ 0,  1, 17, 17, 16]], 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