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*)

$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

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

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]$

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$
- recall the row picture from Matrix Multiplication

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]