Soving Ax = 0: pivot variables, special solutions

We have definition for the column space and the nullspace of a matrix, but how do we compute these subspaces?

Computing the nullspace

The nullspace of a matrix \(A\) is made up of the vectors \(\mathbf{x}\) for which \(A\mathbf{x} = \mathbf{0}\).

\[ A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix} \]

(Note that the columns of this matrix \(A\) are not independent.) Our algorithm for computing the nullspace of this matrix uses the method of elimination, despite the fact that \(A\) is not invertible. We don't need to use an augmented matrix because the right side (the vector \(\mathbf{b}\)) is \(\mathbf{0}\) in this computation.

The row operations used in the method of elimination don't change the solution to \(A\mathbf{x} = \mathbf{b}\) so they don't change the nullspace. (They do affect the column space.)

The first step of elimination gives us:

\[ A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix} \to \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 2 & 4 \end{bmatrix} \]

We don't find a pivot in the second column, so our next pivot is the 2 in the third column of the second row:

\[ A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 2 & 4 \\ \end{bmatrix} \to \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} = U \]

The matrix \(U\) is in echelon(staircase) form. The third row is zero because row 3 was a linear combination of rows 1 and 2; it was eliminated.

The rank of a matrix A equals the number of pivots it has. In this example, the rank of \(A\) (and of \(U\)) is \(2\).

Special solutions

Once we've found \(U\), we can back-substitution to find the solution \(\mathbf{x}\) to the equation \(U\mathbf{x} = \mathbf{0}\). In our example, columns 1 and 3 are pivot columns containing pivots, and columns 2 and 4 are free columns. We can assign any value to \(x_2\) and \(x_4\); we call these free variables. Suppose \(x_2 = 1\) and \(x_4 = 0\). Then:

\[ 2 x_3 + 4 x_4 = 0 \to x_3 = 0 \]

and:

\[ x_1 + 2x_2 + 2x_3 + 2x_4 = 0 \to x_1 = -2 \]

So one solution is \(\mathbf{x} = \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix}\) (because the second column is just twice the first column). Any multiple of this vector is in the nullspace.

Letting a different free variable equal 1 and setting the other free variables equal to zero gives us other vectors in the nullspace. For example:

\[ \mathbf{x} = \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} \]

has \(x_4 = 1\) and \(x_2 = 0\). The nullspace of \(A\) is the collection of all linear combinations of these "special solution" vectors.

The rank \(r\) of \(A\) equals the number of pivot columns, so the number of free columns is \(n - r\): the number of columns(variables) minus the number of pivot columns. This equals the number of special solution vectors and the dimension of the nullspace.

Reduced row echelon form

By continuing to use the method of elimination we can convert \(U\) to a matrix \(R\) in reduced row echelon form(rref), which pivots equal to 1 and zeros above and below the pivots.

\[ U = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} \to \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} \to \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} = R \]

By exchanging some columns, \(R\) can be rewritten with a copy of the identity matrix in the upper left corner, possibly followed by some free columns on the right. If some rows of \(A\) are linearly dependent, the lower rows of the matrix \(R\) will be filled with zeros:

\[ R = \begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix} \]

Here \(I\) is an \(r\) by \(r\) square matrix.

If \(N\) is the nullspace matrix \(N = \begin{bmatrix} -F \\ I \end{bmatrix}\) then \(RN = 0\). Here \(I\) is an \(n - r\) by \(n - r\) square matrix and \(0\) is an \(m\) by \(n - r\) matrix. The columns of \(N\) are the special solutions.