How to Solve Homogeneous Equations with the SVD

A homogeneous linear system has the form

$$A x=0,$$

where $A$ is an $m\times n$ matrix and $x\in\mathbb{R}^n$. The singular value decomposition (SVD) gives a direct way to identify every solution, including the dimension and a basis of the null space.

The key fact is simple: with a full SVD, the null space of $A$ is spanned by the right singular vectors associated with zero singular values.

The SVD and the null-space equation

Write the SVD of $A$ as

$$A=U\Sigma V^T.$$

For a full SVD, $U$ is an $m\times m$ orthogonal matrix, $V$ is an $n\times n$ orthogonal matrix, and $\Sigma$ is an $m\times n$ rectangular diagonal matrix. Let $p=\min(m,n)$. The usual singular values are

$$\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_p\geq 0.$$

When $m<n$, the full matrix $V$ has $n$ columns but only $p$ diagonal positions occur in $\Sigma$. To index all columns of $V$, extend the list by setting $\sigma_i=0$ for $p<i\leq n$. Thus, for this null-space calculation, we use

$$\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_n\geq 0,$$

where any appended values are zero.

Suppose $x$ satisfies $Ax=0$. Since $V$ is orthogonal, write

$$x=Vz,$$

where $z=V^Tx$. Substituting this into the equation gives

$$Ax=U\Sigma V^T Vz=U\Sigma z=0.$$

Multiplying by $U^T$ produces

$$\Sigma z=0.$$

Thus, each component $z_i$ must satisfy

$$\sigma_i z_i=0.$$

If $\sigma_i\ne 0$, then $z_i=0$. If $\sigma_i=0$, then $z_i$ can be arbitrary. Therefore, if $v_i$ denotes the $i$th column of $V$,

$$\operatorname{null}(A)=\operatorname{span}\{v_i:\sigma_i=0\}.$$

This also agrees with the rank–nullity theorem. If $A$ has $n$ columns and rank $r$, then exactly $n-r$ independent right singular vectors belong to the null space:

$$\dim\operatorname{null}(A)=n-r.$$

Step-by-step procedure

Given $A$:

1. Compute a full SVD $A=U\Sigma V^T$.
2. Determine which singular values are zero.
3. Select the corresponding columns of $V$.
4. Form arbitrary linear combinations of those columns.

If the zero-singular-value columns are $v_{r+1},\ldots,v_n$, then the general solution is

$$x=c_{r+1}v_{r+1}+\cdots+c_nv_n,$$

where the coefficients are arbitrary real numbers.

If there are no zero singular values, the only solution is $x=0$. In that case, $A$ has full column rank and its null space is trivial.

Worked example

Consider

$$A=\begin{bmatrix} 1&1&0\\ 0&0&2 \end{bmatrix}.$$

Instead of computing the entire SVD from scratch, calculate the eigenvectors of $A^TA$:

$$A^TA= \begin{bmatrix} 1&1&0\\ 1&1&0\\ 0&0&4 \end{bmatrix}.$$

Its orthonormal eigenvectors can be chosen as

$$v_1=\begin{bmatrix}0\\0\\1\end{bmatrix}, \qquad v_2=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\\0\end{bmatrix}, \qquad v_3=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\-1\\0\end{bmatrix}.$$

The corresponding eigenvalues are $4$, $2$, and $0$. Using the zero-extended list for the three columns of $V$, the corresponding singular values are $2$, $\sqrt{2}$, and $0$. The vector $v_3$ is associated with the zero singular value, and therefore spans the null space:

$$\operatorname{null}(A)=\operatorname{span}\left\{ \frac{1}{\sqrt{2}}\begin{bmatrix}1\\-1\\0\end{bmatrix} \right\}.$$

Consequently, every solution is

$$x=t\begin{bmatrix}1\\-1\\0\end{bmatrix}, \qquad t\in\mathbb{R}.$$

Direct substitution confirms this:

$$A\begin{bmatrix}t\\-t\\0\end{bmatrix} = \begin{bmatrix}t-t\\0\end{bmatrix} = \begin{bmatrix}0\\0\end{bmatrix}.$$

The matrix has rank $2$ and $3$ columns, so rank–nullity predicts a one-dimensional null space, as obtained from the SVD.

Reduced SVD notation

For an $m\times n$ matrix, a compact SVD is often written

$$A=U_r\Sigma_r V_r^T,$$

where only the $r$ positive singular values are retained. Some sources call this a reduced SVD; terminology varies. This factorization is useful for representing the action of $A$, but it does not display the null space explicitly: the null-space vectors are omitted from $V_r$.

To obtain a basis for the null space, use a full SVD, or compute the remaining orthonormal columns of $V$. In the example above, a compact SVD contains the two right singular vectors associated with singular values $2$ and $\sqrt{2}$, while the third right singular vector is needed to describe the solutions of $Ax=0$.

Numerical SVD: what counts as zero?

For exact symbolic matrices, a singular value is either zero or nonzero. In floating-point computation, a theoretically zero singular value may appear as a small number such as $10^{-14}$. It should not automatically be treated as nonzero.

A common numerical rank rule is to regard $\sigma_i$ as zero when

$$\sigma_i\leq \tau,$$

where a scale-dependent tolerance might be chosen as

$$\tau=\max(m,n)\,\sigma_1\,\varepsilon,$$

with $\varepsilon$ the machine precision. Software packages may use a related threshold, and the appropriate tolerance also depends on measurement or modeling error.

The columns of $V$ corresponding to singular values below the chosen threshold provide a numerical basis for an approximate null space. Such vectors satisfy $Ax\approx 0$, rather than necessarily satisfying the equation exactly.

Common mistakes

Using columns of $U$

The null-space vectors belong to the domain of $A$, which is $\mathbb{R}^n$. They are columns of $V$, not columns of $U$. The columns of $U$ describe directions in the output space $\mathbb{R}^m$.

Looking for zero rows in $\Sigma$ only

The important information is the zero singular values and their associated right singular vectors. For a rectangular matrix, the shape of $\Sigma$ can make zero rows or columns appear because of dimensions, even when those entries do not by themselves identify the null-space basis.

Forgetting the arbitrary coefficients

The null-space basis vectors are not usually the complete answer. If two columns of $V$ correspond to zero singular values, the complete solution is every linear combination of those two vectors.

Treating a small singular value as exactly zero

A small singular value indicates near dependence, not necessarily exact dependence. In numerical applications, state the tolerance used and distinguish an exact null space from an approximate one.