Line 24: Line 24:
 
* i.e. all such $\mathbf x$ that solve $A \mathbf x = \mathbf 0$  
 
* i.e. all such $\mathbf x$ that solve $A \mathbf x = \mathbf 0$  
 
* $\mathbf 0 \in N(A)$ always
 
* $\mathbf 0 \in N(A)$ always
* $\begin{bmatrix}
+
* <math>\begin{bmatrix}
 
1 \\ 1 \\ -1
 
1 \\ 1 \\ -1
\end{bmatrix}$ or any multiple of this vector $c \cdot \begin{bmatrix}
+
\end{bmatrix}</math> or any multiple of this vector <math>c \cdot \begin{bmatrix}
 
1 \\ 1 \\ -1
 
1 \\ 1 \\ -1
\end{bmatrix}$
+
\end{bmatrix}</math>
 
* so it's a subspace - a line in $\mathbb R^3$ through the origin
 
* so it's a subspace - a line in $\mathbb R^3$ through the origin
  
Line 66: Line 66:
  
 
Let $A$ be some rectangular matrix and we find it's rref $R$
 
Let $A$ be some rectangular matrix and we find it's rref $R$
* $A = \begin{bmatrix}
+
* <math>A = \begin{bmatrix}
 
1 & 2 & 3 & 1 \\
 
1 & 2 & 3 & 1 \\
 
1 & 1 & 2 & 1 \\
 
1 & 1 & 2 & 1 \\
Line 75: Line 75:
 
0 & 1 & 1 & 0 \\
 
0 & 1 & 1 & 0 \\
 
0 & 0 & 0 & 0 \\
 
0 & 0 & 0 & 0 \\
\end{bmatrix} = R$
+
\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$
 
* we see that one of the rows are $\mathbf 0$ - so the nullspace of $A^T$ should have something apart from $\mathbf 0$
  
Line 88: Line 88:
  
 
Example cont'd  
 
Example cont'd  
* $\left[ \begin{array}{cccc|ccc}
+
* <math>\left[ \begin{array}{cccc|ccc}
 
1 & 2 & 3 & 1 & 1 & 0 & 0 \\
 
1 & 2 & 3 & 1 & 1 & 0 & 0 \\
 
1 & 1 & 2 & 1 & 0 & 1 & 0 \\
 
1 & 1 & 2 & 1 & 0 & 1 & 0 \\
Line 97: Line 97:
 
0 & 1 & 1 & 0 & 1 & -1 & 0 \\
 
0 & 1 & 1 & 0 & 1 & -1 & 0 \\
 
0 & 0 & 0 & 0 & -1 & 0 & 1 \\
 
0 & 0 & 0 & 0 & -1 & 0 & 1 \\
\end{array}\right]$
+
\end{array}\right]</math>
* now if we take $E = \begin{bmatrix}
+
* now if we take <math>E = \begin{bmatrix}
 
-1 & 2 & 0 \\
 
-1 & 2 & 0 \\
 
1 & -1 & 0 \\
 
1 & -1 & 0 \\
 
-1 & 0 & 1 \\
 
-1 & 0 & 1 \\
\end{bmatrix}$ and multiply it by $A$, we get  
+
\end{bmatrix}</math> and multiply it by $A$, we get  
** $\begin{bmatrix}
+
** <math>\begin{bmatrix}
 
-1 & 2 & 0 \\
 
-1 & 2 & 0 \\
 
1 & -1 & 0 \\
 
1 & -1 & 0 \\
Line 117: Line 117:
 
- & - & - & - \\
 
- & - & - & - \\
 
0 & 0 & 0 & 0 \\
 
0 & 0 & 0 & 0 \\
\end{bmatrix}$
+
\end{bmatrix}</math>
 
** so indeed we manage to get the last row with zeros  
 
** so indeed we manage to get the last row with zeros  
 
* so we need the last row of $E$ to get $\mathbf 0^T$
 
* so we need the last row of $E$ to get $\mathbf 0^T$
Line 128: Line 128:
 
* vectors of $V$ that correspond to $\sigma_i = 0$ are from the nullspace  
 
* vectors of $V$ that correspond to $\sigma_i = 0$ are from the nullspace  
  
 
+
def null(A, eps=1e-15):
<pre>
+
    u, s, vh = np.linalg.svd(A)
def null(A, eps=1e-15):
+
    null_space = np.compress(s <= eps, vh, axis=0)
    u, s, vh = np.linalg.svd(A)
+
    return null_space.T
    null_space = np.compress(s <= eps, vh, axis=0)
+
    return null_space.T
+
</pre>
+
  
 
From [http://stackoverflow.com/questions/1835246/how-to-solve-homogeneous-linear-equations-with-numpy]
 
From [http://stackoverflow.com/questions/1835246/how-to-solve-homogeneous-linear-equations-with-numpy]

Latest revision as of 12:51, 25 June 2017

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 of $N(A)$

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