Nullspace
Nullspace $N(A)$ of a matrix $A$ is one of the Four Fundamental Subspaces of the matrix $A$
The nullspace of $A$ contains all $\mathbf x$ that solve the system $A \mathbf x = \mathbf 0$ (this system is called homogeneous)
Example
$A = \begin{bmatrix}
1 & 1 & 2 \\
2 & 1 & 3 \\
3 & 1 & 4 \\
4 & 1 & 5 \\
\end{bmatrix}$, $\mathbf x = \begin{bmatrix}
x_1 \\ x_2 \\ x_3
\end{bmatrix}$, $\mathbf b = \mathbf 0_4 = \begin{bmatrix}
0 \\ 0 \\ 0 \\ 0
\end{bmatrix}$
- There are 3 columns and they are 4-dim vectors
- the Column Space $C(A)$ is a subspace of $\mathbb R^4$, but $\text{dim } C(A) = 2$ (because the rank of this matrix is 2)
- since there are only 3 columns, the number of unknowns is 3 - so $N(A)$ is a subspace of $\mathbb R^3$
Let's find what's inside $N(A)$
- i.e. all such $\mathbf x$ that solve $A \mathbf x = \mathbf 0$
- $\mathbf 0 \in N(A)$ always
- [math]\begin{bmatrix}
1 \\ 1 \\ -1
\end{bmatrix}[/math] or any multiple of this vector [math]c \cdot \begin{bmatrix}
1 \\ 1 \\ -1
\end{bmatrix}[/math]
- so it's a subspace - a line in $\mathbb R^3$ through the origin
Is $N(A)$ a Subspace?
Does it form a Vector Space on its own?
- so we need to check that all possible $\mathbf x$ for that solve $A \mathbf x = \mathbf 0$ form a subspace
- let $\mathbf v$ and $\mathbf w$ be two solutions
- $A \cdot (\mathbf v + \mathbf w) = A \mathbf v + A \mathbf w = \mathbf 0 + \mathbf 0 = \mathbf 0$. so $\mathbf v + \mathbf w$ is also a solution
- if $A \mathbf v = 0$, then $A \cdot (c \cdot \mathbf v) = (c \cdot A) \cdot \mathbf v = 0$
- this would just multiply all columns of $A$ on the same number
- so yes, it is a subspace
Basis for $N(A)$ is formed by the "special" solutions
Left Nullspace
We can also consider another nullspace of $A$ - the nullspace of $A^T$ (this is the 4th fundamental subspace of a matrix)
Let's have a look at a system $A^T \mathbf y = \mathbf 0$
- $A$ is an $n \times m$ matrix, so $A^T$ is $m \times n$
- $y$ is $n$-len column vector
Let's take the transpose of $A^T \mathbf y = \mathbf 0$:
- $(A^T \mathbf y)^T = \mathbf 0^T$
- $\mathbf y^T A = \mathbf 0^T$
- so now we have a row vector $\mathbf y^T$ that is on the left side of $A$
$\big[ - \, \mathbf y^T - \big] \Bigg[ ~ ~ ~ ~ ~ {A} ~ ~ ~ ~ ~ \Bigg] = \big[ - \, \mathbf 0^T - \big]$
Basis of $N(A^T)$
Let's consider this example
Let $A$ be some rectangular matrix and we find it's rref $R$
- [math]A = \begin{bmatrix}
1 & 2 & 3 & 1 \\
1 & 1 & 2 & 1 \\
2 & 3 & 5 & 2 \\
\end{bmatrix} \leadsto
\begin{bmatrix}
1 & 0 & 1 & 1 \\
0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 \\
\end{bmatrix} = R[/math]
- we see that one of the rows are $\mathbf 0$ - so the nullspace of $A^T$ should have something apart from $\mathbf 0$
How to best find this left nullspace?
- Let's do Gauss-Jordan Elimination: create the augmented matrix by appending $I$ and reduce it to the echelon form:
- $\big[ A_{m \times n} \ I_{n \times n} \big] \to \big[ R_{m \times n} \ E_{n \times n} \big]$
- So $E$ is the elimination matrix - the matrix that brings $A$ to rref $R$
- $E A = R$
- If $A$ is square and invertible, then $E \equiv A^{-1}$
- but since $A$ is rectangular, it has no inverse
Example cont'd
- [math]\left[ \begin{array}{cccc|ccc}
1 & 2 & 3 & 1 & 1 & 0 & 0 \\
1 & 1 & 2 & 1 & 0 & 1 & 0 \\
2 & 3 & 5 & 2 & 0 & 0 & 1 \\
\end{array}\right] \leadsto
\left[ \begin{array}{cccc|ccc}
1 & 0 & 1 & 1 & -1 & 2 & 0 \\
0 & 1 & 1 & 0 & 1 & -1 & 0 \\
0 & 0 & 0 & 0 & -1 & 0 & 1 \\
\end{array}\right][/math]
- now if we take [math]E = \begin{bmatrix}
-1 & 2 & 0 \\
1 & -1 & 0 \\
-1 & 0 & 1 \\
\end{bmatrix}[/math] and multiply it by $A$, we get
- [math]\begin{bmatrix}
-1 & 2 & 0 \\
1 & -1 & 0 \\
-1 & 0 & 1 \\
\end{bmatrix} \cdot
\begin{bmatrix}
1 & 2 & 3 & 1 \\
1 & 1 & 2 & 1 \\
2 & 3 & 5 & 2 \\
\end{bmatrix} =
\begin{bmatrix}
- & - & - & - \\
- & - & - & - \\
0 & 0 & 0 & 0 \\
\end{bmatrix}[/math]
- so indeed we manage to get the last row with zeros
- so we need the last row of $E$ to get $\mathbf 0^T$
Numerical Computation
Use SVD to compute the nullspace
- $A = U \Sigma V^T$
- vectors of $V$ that correspond to $\sigma_i = 0$ are from the nullspace
def null(A, eps=1e-15):
u, s, vh = np.linalg.svd(A)
null_space = np.compress(s <= eps, vh, axis=0)
return null_space.T
From [1]
Sources