Computing a Basis for the Left Null Space

The Left Null Space as a Homogeneous System

For a matrix \(\mathbf{A}\), the left null space records the vectors that become zero when multiplied by \(\mathbf{A}^{\top}\). Computing it is therefore a null-space problem, but the transpose determines both the equations and the number of unknowns. Keeping those dimensions straight is essential: if \(\mathbf{A}\) has \(m\) rows and \(n\) columns, a vector in its left null space has \(m\) entries, not \(n\).

To compute this basis, form \(\mathbf{A}^{\top}\) and solve \(\mathbf{A}^{\top}\mathbf{y}=\mathbf{0}\) by row reduction. The unknowns are the entries of \(\mathbf{y}\), so there are \(m\) variables. Every nonpivot column of the reduced matrix corresponds to a free variable. Assigning one free variable the value \(1\) and the others \(0\), then solving for the pivot variables, produces one candidate basis vector.

Row operations are valid here because each elementary row operation replaces a system of equations by an equivalent system: it does not change which \(\mathbf{y}\) satisfy the system. In particular, row-reducing \(\mathbf{A}^{\top}\) preserves the solution set of \(\mathbf{A}^{\top}\mathbf{y}=\mathbf{0}\). This does not mean row operations preserve the left null space of \(\mathbf{A}\) itself; the matrix being reduced is the coefficient matrix of the system we are solving.

Why the Free-Variable Vectors Form a Basis

Proof. Row reduction preserves the solutions of a homogeneous system, so it is enough to consider \(\mathbf{R}\mathbf{x}=\mathbf{0}\). Let the free-variable indices be \(f_1,\dots,f_q\). In each nonzero row of \(\mathbf{R}\), the pivot variable equals a linear combination of the free variables, because the right-hand side is zero. Thus every solution \(\mathbf{x}\) is determined by its free-variable values \(t_1,\dots,t_q\). Let \(\mathbf{z}_j\) be the solution obtained by setting \(x_{f_j}=1\), setting the other free variables to \(0\), and solving for the pivots. The pivot equations are linear, so the solution with free-variable values \(t_1,\dots,t_q\) is \(t_1\mathbf{z}_1+\cdots+t_q\mathbf{z}_q\). Hence these vectors span the solution space. To prove independence, suppose \(c_1\mathbf{z}_1+\cdots+c_q\mathbf{z}_q=\mathbf{0}\). In free-variable coordinate \(f_j\), the left side has value \(c_j\), so \(c_j=0\) for every \(j\). The vectors are independent. If \(q=0\), every variable is a pivot variable and the homogeneous equations force all variables to be zero; the empty list spans \(\{\mathbf{0}\}\) and is linearly independent by the definition of independence. \(\square\)

Applying the theorem with \(\mathbf{B}=\mathbf{A}^{\top}\) gives the basis procedure for the left null space. The basis vectors have \(m\) entries, one for each row of \(\mathbf{A}\). As a final check, multiply \(\mathbf{A}^{\top}\) by each proposed vector. A nonzero result means that either the row reduction or the translation from free variables to vectors contains an error.

Full Row Rank: The Left Null Space Can Be Trivial

This example illustrates why the empty-list case matters. The zero space does have a basis: the empty list is independent, and its span is defined to be \(\{\mathbf{0}\}\). Writing a zero vector as a basis vector would not work, since any list containing \(\mathbf{0}\) is dependent.

Deficient Row Rank: Free Variables Give the Basis

Each basis vector in this calculation also gives a relation among the rows of \(\mathbf{A}\). For example, \((-2,1,0)^{\top}\) corresponds to \(-2\) times row 1 plus row 2 plus \(0\) times row 3, which is the zero row. This interpretation follows directly from the entries of \(\mathbf{A}^{\top}\mathbf{y}\): its coordinates are the corresponding linear combinations of the rows of \(\mathbf{A}\).

Full Column Rank Does Not Force a Zero Left Null Space

Full column rank concerns dependencies among the columns of \(\mathbf{A}\); the left null space concerns dependencies among its rows. For a rectangular matrix, these are different questions. A nonzero left null space is compatible with independent columns, as the example demonstrates.

Common Mistake: Solving the Wrong Homogeneous System

A common error is to row-reduce \(\mathbf{A}\) and interpret the solutions of \(\mathbf{A}\mathbf{x}=\mathbf{0}\) as vectors in the left null space. For the matrix in the previous example, that mistaken calculation gives

This calculation is correct for \(\operatorname{Nul}\mathbf{A}\), but it answers a different question: \(\mathbf{x}\) has two entries, whereas a left-null vector must have three entries. The correction is to transpose first and solve \(\mathbf{A}^{\top}\mathbf{y}=\mathbf{0}\). That system gives the nonzero vector \((-1,-1,1)^{\top}\) found above. Always check the dimensions before interpreting a null-space computation.

In practice, the procedure is short: identify the number of rows \(m\), form the \(n\times m\) matrix \(\mathbf{A}^{\top}\), reduce it, and parameterize its homogeneous solutions. Convert each free variable into one basis vector, then verify by multiplication. The final number of basis vectors is determined by the free variables in this particular system; no conclusion about it requires reducing the original matrix instead.