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

Returns:¶

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

Notes¶

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

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

Examples¶

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

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

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

In [3]: A = GF.Random((m, n)); A
Out[3]: 
GF([[18, 13, 12],
    [23, 30,  6],
    [13, 10, 27],
    [ 4, 25, 16],
    [24, 16, 25]], order=31)

In [4]: LN = A.left_null_space(); LN
Out[4]: 
GF([[ 1,  0,  8, 24,  9],
    [ 0,  1,  8, 22, 13]], order=31)

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

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

The dimension of the row space and left null space sum to \(m\).

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

In [7]: R.shape[0] + LN.shape[0] == m
Out[7]: True